Book of Proof

Home > Other > Book of Proof > Page 32
Book of Proof Page 32

by Richard Hammack


  not reduced, and in fact their reduced forms appear in the column headed

  by 1. You should examine this table and convince yourself that it contains

  all rational numbers in Q.

  Countable and Uncountable Sets

  225

  0

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  · · ·

  0

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  1

  1

  1

  1

  1

  1

  1

  1

  1

  1

  1

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  2

  2

  3

  3

  2

  2

  3

  3

  2

  2

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  3

  3

  5

  5

  4

  4

  5

  5

  3

  3

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  4

  4

  7

  7

  5

  5

  7

  7

  4

  4

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  5

  5

  9

  9

  7

  7

  9

  9

  6

  6

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  6

  6

  11

  11

  8

  8

  11

  11

  7

  7

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  7

  7

  13

  13

  10

  10

  13

  13

  8

  8

  · · ·

  ..

  .

  .

  .

  .

  .

  .

  .

  .

  .

  .

  .

  ..

  ..

  ..

  ..

  ..

  ..

  ..

  ..

  ..

  . .

  0

  Next, draw an infinite path in this array, beginning at 1 and snaking

  back and forth as indicated below. Every rational number is on this path.

  0

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  · · ·

  0

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  1

  1

  1

  1

  1

  1

  1

  1

  1

  1

  1

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  2

  2

  3

  3

  2

  2

  3

  3

  2

  2

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  3

  3

  5

  5

  4

  4

  5

  5

  3

  3

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  4

  4

  7

  7

  5

  5

  7

  7

  4

  4

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  5

  5

  9

  9

  7

  7

  9

  9

  6

  6

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  6

  6

  11

  11

  8

  8

  11

  11

  7

  7

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  7

  7

  13

  13

  10

  10

  13

  13

  8

  8

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  8

  8

  15

  15

  11

  11

  15

  15

  9

  9

  · · ·

  1

  −1

  2

  −2

  3

  −3

  4

  −4

  5

  −5

  9

  9

  17

  17

  13

  13

  17

  17

&nb
sp; 11

  11

  · · ·

  ..

  .

  .

  .

  .

  .

  .

  .

  .

  .

  .

  .

  ..

  ..

  ..

  ..

  ..

  ..

  ..

  ..

  ..

  . .

  226

  Cardinality of Sets

  0

  Beginning at 1 and following the path, we get an infinite list of all

  rational numbers:

  1

  1

  2 2

  1 1 1

  1 2

  2

  2

  2

  2

  3

  0, 1,

  , − , −1, 2, , , − , , , − , , − , − , − , − , −2, 3, , ...

  2

  2

  3 5

  3 3 4

  4 7

  7

  5

  3

  3

  2

  By Theorem 13.3, it follows that Q is countably infinite, that is, |Q| = |N|.

  ■

  It is also true that the Cartesian product of two countably infinite sets

  is itself countably infinite, as our next theorem states.

  Theorem 13.5

  If A and B are both countably infinite, then so is A × B.

  Proof. Suppose A and B are both countably infinite. By Theorem 13.3, we

  know we can write A and B in list form as

  A

  = ©a1, a2, a3, a4, . . . ª,

  B

  = ©b1, b2, b3, b4, . . . ª.

  Figure 13.2 shows how to form an infinite path winding through all of A ×B.

  Therefore A × B can be written in list form, so it is countably infinite.

  ■

  B ..

  .

  .

  .

  .

  .

  .

  .

  .

  ..

  ..

  ..

  ..

  ..

  ..

  ..

  b

  (a

  7

  1, b7) (a2, b7) (a3, b7) (a4, b7) (a5, b7) (a6, b7) (a7, b7) · · ·

  b

  (a

  6

  1, b6) (a2, b6) (a3, b6) (a4, b6) (a5, b6) (a6, b6) (a7, b6) · · ·

  b

  (a

  5

  1, b5) (a2, b5) (a3, b5) (a4, b5) (a5, b5) (a6, b5) (a7, b5) · · ·

  b

  (a

  4

  1, b4) (a2, b4) (a3, b4) (a4, b4) (a5, b4) (a6, b4) (a7, b4) · · ·

  b

  (a

  3

  1, b3) (a2, b3) (a3, b3) (a4, b3) (a5, b3) (a6, b3) (a7, b3) · · ·

  b

  (a

  2

  1, b2) (a2, b2) (a3, b2) (a4, b2) (a5, b2) (a6, b2) (a7, b2) · · ·

  b

  (a

  1

  1, b1) (a2, b1) (a3, b1) (a4, b1) (a5, b1) (a6, b1) (a7, b1) · · ·

  a1

  a2

  a3

  a4

  a5

  a6

  a7

  · · ·

  A

  Figure 13.2. A product of two countably infinite sets is countably infinite

  Countable and Uncountable Sets

  227

  As an example of a consequence of this theorem, notice that since Q is

  countably infinite, the set Q × Q is also countably infinite.

  Recall that the word “corollary” means a result that follows easily from

  some other result. We have the following corollary of Theorem 13.5.

  Corollary 13.1

  Given n countably infinite sets A1, A2, A3, . . . , An, with

  n ≥ 2, the Cartesian product A1 × A2 × A3 ×···× An is also countably infinite.

  Proof. The proof is by induction on n. For the basis step, notice that when

  n = 2 the statement asserts that for countably infinite sets A1 and A2, the

  product A1 × A2 is countably infinite, and this is true by Theorem 13.5.

  Assume that for k ≥ 2, any product A1 × A2 × A3 × · · · ×Ak of countably

  infinite sets is countably infinite. Consider a product A1 × A2 × A3 ×· · ·× Ak+1

  of k + 1 countably infinite sets. It is easily confirmed that the function

  f : A1 × A2 × A3 × ··· × Ak × Ak+1 −→ (A1 × A2 × A3 × ··· × Ak) × Ak+1

  f (x

  ¢

  1, x2, . . . , xk, xk+1)

  =

  ¡(x1, x2,..., xk), xk+1

  is bijective, so |A1 × A2 × A3 × · · · × Ak × Ak+1| = |(A1 × A2 × A3 × · · · × Ak) × Ak+1|.

  By the induction hypothesis, (A1 × A2 × A3 × · · · × Ak) × Ak+1 is a product of

  two countably infinite sets, so it is countably infinite by Theorem 13.5. As

  noted above, A1 × A2 × A3 × · · · × Ak × Ak+1 has the same cardinality, so it too

  is countably infinite.

  ■

  Theorem 13.6

  If A and B are both countably infinite, then A ∪ B is

  countably infinite.

  Proof. Suppose A and B are both countably infinite. By Theorem 13.3, we

  know we can write A and B in list form as

  A

  = ©a1, a2, a3, a4, . . . ª,

  B

  = ©b1, b2, b3, b4, . . . ª.

  We can “shuffle” A and B into one infinite list for A ∪ B as follows.

  A ∪ B = ©a1, b1, a2, b2, a3, b3, a4, b4,...ª.

  (We agree not to list an element twice if it belongs to both A and B.)

  Therefore, by Theorem 13.3, it follows that A ∪ B is countably infinite.

  ■

  228

  Cardinality of Sets

  Exercises for Section 13.2

  1. Prove that the set A = ©ln(n) : n ∈ Nª ⊆ R is countably infinite.

  2. Prove that the set A = ©(m, n) ∈ N × N : m ≤ nª is countably infinite.

  3. Prove that the set A = ©(5n,−3n) : n ∈ Zª is countably infinite.

  4. Prove that the set of all irrational numbers is uncountable. (Suggestion:

  Consider proof by contradiction using Theorems 13.4 and 13.6.)

  5. Prove or disprove: There exists a countably infinite subset of the set of irrational

  numbers.

  6. Prove or disprove: There exists a bijective function f : Q → R.

  7. Prove or disprove: The set Q100 is countably infinite.

  8. Prove or disprove: The set Z × Q is countably infinite.

  9.

  ©

  Prove or disprove: The set 0, 1ª × N is countably infinite.

  p

  10.

  2

  Prove or disprove: The set A = ©

  : n

  n

  ∈ Nª countably infinite.

  11. Describe a partition of N that divides N into eight countably infinite subsets.

  12. Describe a partition of N that divides N into ℵ0 countably infinite subsets.

  13. Prove or disprove: If A = {X ⊆ N : X is finite}, then |A| = ℵ0.

  14. Suppose A = ©(m, n) ∈ N × R : n = π mª. Is it true that |N| = |A|?

  15. Theorem 13.5 implies that N × N is countably infinite. Construct an alternate

  proof of this fact by showing that the function ϕ : N × N → N defined as ϕ(m, n) =

  2n−1(2m − 1) is bijective.

  13.3 Comparing Cardinalities

  At this point we know that there are at least two different kinds of infinity.

  On one hand, there are countably infinite sets such as N, of cardinality ℵ0.

  Then there is the uncountable set R. Are there other kinds of infinit
y

  beyond these two kinds? The answer is “yes,” but to see why we first need

  to introduce some new definitions and theorems.

  Our first task will be to formulate a definition for what we mean by

  |A| < |B|. Of course if A and B are finite we know exactly what this means:

  |A| < |B| means that when the elements of A and B are counted, A is found

  to have fewer elements than B. But this process breaks down if A or B is

  infinite, for then the elements can’t be counted.

  The language of functions helps us overcome this difficulty. Notice

  that for finite sets A and B it is intuitively clear that |A| < |B| if and only

  if there exists an injective function f : A → B but there are no surjective

  functions f : A → B. The following diagram illustrates this:

  Comparing Cardinalities

  229

  A

  B

  f

  a

  0

  b

  1

  c

  2

  d

  3

  4

  We will use this idea to define what is meant by |A| < |B| and |A| ≤ |B|. For

  emphasis, the following definition also restates what is meant by |A| = |B|.

  Definition 13.4

  Suppose A and B are sets.

  (1) |A| = |B| means there is a bijection A → B.

  (2) |A| < |B| means there is an injection A → B, but no surjection A → B.

  (3) |A| ≤ |B| means |A| < |B| or |A| = |B|.

  For example, consider N and R. The function f : N → R defined as f (n) = n

  1

  is clearly injective, but it is not surjective because given the element 2 ∈ R,

  we have f (n) 6= 12 for every n ∈ N. In fact, Theorem 13.2 of Section 13.1

  asserts that there is no surjection N → R. Definition 13.4 yields

  |N| < |R|.

  (13.1)

  Said differently, ℵ0 < |R|.

  Is there a set X for which |R| < |X |? The answer is “yes,” and the next

  theorem explains why. It implies |R| < |P(R)|. (Recall that P(A) denotes

  the power set of A.)

  Theorem 13.7

  If A is any set, then |A| < |P(A)|.

  Proof. Before beginning the proof, we remark that this statement is obvious

  if A is finite, for then |A| < 2|A| = |P(A)|. But our proof must apply to all

  sets A, both finite and infinite, so it must use Definition 13.4.

  We prove the theorem with direct proof. Let A be an arbitrary set.

  According to Definition 13.4, to prove |A| < |P(A)| we must show that there

  is an injection f : A → P(A), but no surjection f : A → P(A).

  To see that there is an injection f : A → P(A), define f by the rule

  f (x) = ©xª. In words, f sends any element x of A to the one-element set

  ©xª ∈ P(A). Then f : A → P(A) is injective, as follows. Suppose f (x) = f (y).

  ©

  ©

  ©

  Then xª = © yª. Now, the only way that xª and

  yª can be equal is if x = y,

  so it follows that x = y. Thus f is injective.

  Next we need to show that there exists no surjection f : A → P(A).

  Suppose for the sake of contradiction that there does exist a surjection

  230

  Cardinality of Sets

  f : A → P(A). Notice that for any element x ∈ A, we have f (x) ∈ P(A), so

  f (x) is a subset of A. Thus f is a function that sends elements of A to

  subsets of A. It follows that for any x ∈ A, either x is an element of the

  subset f (x) or it is not. Using this idea, define the following subset B of A:

  B = ©x ∈ A : x ∉ f (x)ª ⊆ A.

  Now since B ⊆ A we have B ∈ P(A), and since f is surjective there is an

  a ∈ A for which f (a) = B. Now, either a ∈ B or a ∉ B. We will consider these

  two cases separately, and show that each leads to a contradiction.

 

‹ Prev