Cardinality Revisited

Definition: The cardinality of a set A is equal to the cardinality of a set B, denoted 

                  |A| = |B|,

if and only if there is a one-to-one correspondence (i.e., a bijection)  from A to B. 

• If there is a one-to-one function (i.e., an injection) from A to B, the cardinality of A is less than or the same as the cardinality of B and we write |A| ≤ |B|. 
• When |A| ≤ |B| and A and B have different cardinality, we say that the cardinality of A is less than the cardinality of B and write |A| < |B|. 

 

• Definition: A set that is either finite or has the same cardinality as the set of positive integers (Z+) is called countable. A set that is not countable is uncountable.

 

• The  set of real numbers R  is an uncountable set.
• When an infinite set is countable (countably infinite), its cardinality is ℵ0 (where ℵ is aleph, the 1st letter of the Hebrew alphabet). We write |S| = ℵ0  and say that S has cardinality “aleph null.”

 

Showing that a Set is Countable

• An infinite set is countable if and only if it is possible to list the elements of the set in a sequence (indexed by the positive integers). 
• The reason for this is that a one-to-one correspondence f from the set of positive integers to a set S can be expressed in terms of a sequence         a1,a2,…, an ,… where a1 = f(1), a2  = f(2),…, an = f(n),… 

Example 1: Show that the set of positive even integers E is countable set.

Solution: Let f(x) = 2x. 

   

 

Example 2: Show that the set of integers Z is countable.

Solution: Can list in a sequence:

      0, 1, − 1, 2, − 2, 3, − 3 ,………..

Or can define a bijection from N  to Z:

• When n is even:    f(n) = n/2
• When n is odd:     f(n) = −(n−1)/2

 

Set of Rational Numbers is Countable

Definition: A rational number can be expressed as the ratio of two integers p and q such that q ≠ 0.

• ¾ is a rational number
• √2  is not a rational number.

Example 3: Show that the positive rational numbers are countable.

Solution:The positive rational numbers are countable since they can be arranged in a sequence:

                       r1 , r2 , r3 ,…  

 

Strings

Example 4: Show that the set of finite strings S over a finite alphabet A is countably infinite.

Assume an alphabetical ordering of symbols in A

Solution: Show that the strings can be listed in a sequence. First list

1. All the strings of length 0 in alphabetical order.
2. Then all the strings of length 1 in lexicographic (as in a dictionary) order.
3. Then all the strings of length 2 in lexicographic order. 
4. And so on.

This implies a bijection from N to S and hence it is a countably infinite set.

 

Set of Reals is Uncountable

Example: Show that the set of real numbers is uncountable.

Solution: The method is called the Cantor diagnalization argument, and is a proof by contradiction.

1. Suppose R is countable. Then the real numbers between 0 and 1 are also countable (any subset of a countable set is countable).
2. The real numbers between 0 and 1 can be listed in order r1 , r2 , r3 ,… .
3. Let the decimal representation of this listing be
   1. 
4. Form a new real number with the decimal expansion
5. r is not equal to any of the r1 , r2 , r3 ,…  Because it differs from ri   in its ith position after the decimal point. Therefore there is a real number between 0 and 1 that is not on the list since every real number has a unique decimal expansion. Hence, all the real numbers between 0 and 1 cannot be listed, so the set of real numbers between 0 and 1 is uncountable.
6. Since a set with an uncountable subset is uncountable (an exercise), the set of real numbers is uncountable.

 

 

 

 

eof