Page 195 - Discrete Mathematics and Its Applications

174 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

r = 0.d 1 d 2 d 3 d 4 ..., where the decimal digits are determined by the following rule:

4if d ii = 4
d i =
5if d ii = 4.
(As an example, suppose that r 1 = 0.23794102 ..., r 2 = 0.44590138 ..., r 3 =
0.09118764 ..., r 4 = 0.80553900 ..., and so on. Then we have r = 0.d 1 d 2 d 3 d 4 ... =
0.4544 ..., where d 1 = 4 because d 11 = 4, d 2 = 5 because d 22 = 4, d 3 = 4 because d 33 = 4,
d 4 = 4 because d 44 = 4, and so on.)
Every real number has a unique decimal expansion (when the possibility that the expansion
has a tail end that consists entirely of the digit 9 is excluded). Therefore, the real number r is not
A number with a decimal
expansion that terminates equal to any of r 1 ,r 2 ,... because the decimal expansion of r differs from the decimal expansion
has a second decimal of r i in the ith place to the right of the decimal point, for each i.
expansion ending with an Because there is a real number r between 0 and 1 that is not in the list, the assumption that all
infinite sequence of 9s the real numbers between 0 and 1 could be listed must be false. Therefore, all the real numbers
because 1 = 0.999 ....
between 0 and 1 cannot be listed, so the set of real numbers between 0 and 1 is uncountable.Any
set with an uncountable subset is uncountable (see Exercise 15). Hence, the set of real numbers
is uncountable. ▲

RESULTS ABOUT CARDINALITY We will now discuss some results about the cardinality
of sets. First, we will prove that the union of two countable sets is also countable.

THEOREM 1 If A and B are countable sets, then A ∪ B is also countable.

Proof: Suppose that A and B are both countable sets. Without loss of generality, we can assume
that A and B are disjoint. (If they are not, we can replace B by B − A, because A ∩ (B − A) =∅
and A ∪ (B − A) = A ∪ B.) Furthermore, without loss of generality, if one of the two sets is
This proof uses WLOG
and cases. countably infinite and other finite, we can assume that B is the one that is finite.
There are three cases to consider: (i) A and B are both finite, (ii) A is infinite and B is finite,
and (iii) A and B are both countably infinite.
Case (i): Note that when A and B are finite, A ∪ B is also finite, and therefore, countable.
Case (ii): Because A is countably infinite, its elements can be listed in an infinite sequence
a 1 , a 2 , a 3 , ..., a n , ... and because B is finite, its terms can be listed as b 1 , b 2 , ..., b m for
some positive integer m. We can list the elements of A ∪ B as b 1 , b 2 , ..., b m , a 1 , a 2 , a 3 ,
..., a n , .... This means that A ∪ B is countably infinite.
Case (iii): Because both A and B are countably infinite, we can list their elements as a 1 ,
a 2 , a 3 , ..., a n , ... and b 1 , b 2 , b 3 , ..., b n , ..., respectively. By alternating terms of these
two sequences we can list the elements of A ∪ B in the infinite sequence a 1 , b 1 , a 2 , b 2 , a 3 ,
b 3 , ..., a n , b n , .... This means A ∪ B must be countably infinite.
We have completed the proof, as we have shown that A ∪ B is countable in all three
cases.

Because of its importance, we now state a key theorem in the study of cardinality.

THEOREM 2 SCHRÖDER-BERNSTEIN THEOREM If A and B are sets with |A|≤|B| and |B|≤
|A|, then |A|=|B|. In other words, if there are one-to-one functions f from A to B and g
from B to A, then there is a one-to-one correspondence between A and B.