Principles of Mathematics in Operations Research

9.6 Countable and Uncountable Sets 129

Definition 9.5.2 An equivalence relation in X is a binary relation (where ~

means equivalent) with the following properties:

(a) Vx G X, x ~ x (reflexibility).

(b) x ~ y => y ~ x (symmetry).

(c) x ~ y, y ~ z => x ~ z (transitivity).

Definition 9.5.3 7/~ is an equivalence relation in X, we define the equiva-

lence class of any x G X as the following set:

[x] = {y G X : x ~ y}.

Remark 9.5.4 7/~ is an equivalence relation in X, then the collection of all

equivalence classes forms a partition of X; and conversely, given any partition

of X there is an equivalence relation in X such that equivalence classes are

the sets in the partition.

Remark 9.5.5 Let C be any collection of nonempty sets. For X,Y G C,

define X ~ Y (X and Y are numerically equivalent) if there exists a one-

to one and onto function f : X i-> Y (or f~l : Y H-> X). Then, ~ is an

equivalence relation in C.

9.6 Countable and Uncountable Sets

Definition 9.6.1 Let Jn = {1,2,... ,n}, n = 1,2,.... Let X ^ 0. We say

i) X is finite if 3n G N, X ~ Jn.

ii) X is infinite if X is not finite.

Hi) X is countable if X ~ N

(i.e. 3/:N4l, 1-1 onto, or3g:X^N, 1-1 onto),

iv) X is uncountable if X is not finite and not countable,

v) X is at most countable if X is finite or countable.

Example 9.6.2 X = N is countable. Let f : N n- N be the identity function.

Example 9.6.3 X = Z is countable. Define f : N H> Z as

/(»)=( n-l

§, if n is even;

2 , if n is odd.

Example 9.6.4 Q+ is countable. Let r G Q+, then r = — where m,n G N.
List elements of Q+ in this order as in Table 9.1. If we apply the counting
schema given in Figure 9.1, we get the sequence

! I 2 I 3 i ^ 3

'2' '3' '4'3'2' '""