Book of Proof

Home > Other > Book of Proof > Page 33
Book of Proof Page 33

by Richard Hammack


  Case 1. If a ∈ B, then the definition of B implies a ∉ f (a), and since f (a) = B

  we have a ∉ B, which is a contradiction.

  Case 2. If a ∉ B, then the definition of B implies a ∈ f (a), and since f (a) = B

  we have a ∈ B, again a contradiction.

  Since the assumption that there is a surjection f : A → P(A) leads to a

  contradiction, we conclude that there are no such surjective functions.

  In conclusion, we have seen that there exists an injection A → P(A) but

  no surjection A → P(A), so Definition 13.4 implies that |A| < |P(A)|.

  ■

  Beginning with the set A = N and applying Theorem 13.7 over and over

  again, we get the following chain of infinite cardinalities.

  ℵ0 = |N| < |P(N)| < |P(P(N))| < |P(P(P(N)))| < ···

  (13.2)

  Thus there is an infinite sequence of different types of infinity, starting

  with ℵ0 and becoming ever larger. The set N is countable, and all the sets

  P(N), P(P(N)), etc., are uncountable.

  In the next section we will prove that |P(N)| = |R|. Thus |N| and |R|

  are the first two entries in the chain (13.2) above. They are are just two

  relatively tame infinities in a long list of other wild and exotic infinities.

  Unless you plan on studying advanced set theory or the foundations

  of mathematics, you are unlikely to ever encounter any types of infinity

  beyond ℵ0 and |R|. Still you will in future mathematics courses need to

  distinguish between countably infinite and uncountable sets, so we close

  with two final theorems that can help you do this.

  Theorem 13.8

  An infinite subset of a countably infinite set is countably

  infinite.

  Proof. Suppose A is an infinite subset of the countably infinite set B.

  Because B is countably infinite, its elements can be written in a list

  Comparing Cardinalities

  231

  b1, b2, b3, b4, . . . Then we can also write A’s elements in list form by proceed-

  ing through the elements of B, in order, and selecting those that belong to

  A. Thus A can be written in list form, and since A is infinite, its list will

  be infinite. Consequently A is countably infinite.

  ■

  Theorem 13.9

  If U ⊆ A, and U is uncountable, then A is uncountable.

  Proof. Suppose for the sake of contradiction that U ⊆ A, and U is uncount-

  able but A is not uncountable. Then since U ⊆ A and U is infinite, then A

  must be infinite too. Since A is infinite, and not uncountable, it must be

  countably infinite. Then U is an infinite subset of a countably infinite set

  A, so U is countably infinite by Theorem 13.8. Thus U is both uncountable

  and countably infinite, a contradiction.

  ■

  Theorems 13.8 and 13.9 can be useful when we need to decide whether

  a set is countably infinite or uncountable. They sometimes allow us to

  decide its cardinality by comparing it to a set whose cardinality is known.

  For example, suppose we want to decide whether or not the set A = R2

  is uncountable.

  Since the x-axis U = ©(x, 0) : x ∈ Rª ⊆ R2 has the same

  cardinality as R, it is uncountable.

  Theorem 13.9 implies that R2 is

  uncountable. Other examples can be found in the exercises.

  Exercises for Section 13.3

  1. Suppose B is an uncountable set and A is a set. Given that there is a surjective

  function f : A → B, what can be said about the cardinality of A?

  2. Prove that the set C of complex numbers is uncountable.

  3. Prove or disprove: If A is uncountable, then |A| = |R|.

  4. Prove or disprove: If A ⊆ B ⊆ C and A and C are countably infinite, then B is

  countably infinite.

  5.

  ©

  Prove or disprove: The set 0, 1ª × R is uncountable.

  6. Prove or disprove: Every infinite set is a subset of a countably infinite set.

  7. Prove or disprove: If A ⊆ B and A is countably infinite and B is uncountable,

  then B − A is uncountable.

  8.

  ©

  Prove or disprove: The set (a1, a2, a3, . . .) : ai ∈ Z} of infinite sequences of integers

  is countably infinite.

  9. Prove that if A and B are finite sets with |A| = |B|, then any injection f : A → B

  is also a surjection. Show this is not necessarily true if A and B are not finite.

  10. Prove that if A and B are finite sets with |A| = |B|, then any surjection f : A → B

  is also an injection. Show this is not necessarily true if A and B are not finite.

  232

  Cardinality of Sets

  13.4 The Cantor-Bernstein-Schröeder Theorem

  An often used property of numbers is that if a ≤ b and b ≤ a, then a = b. It

  is reasonable to ask if the same property applies to cardinality. If |A| ≤ |B|

  and |B| ≤ |A|, is it true that |A| = |B|? This is in fact true, and this section’s

  goal is to prove it. This will yield an alternate (and highly effective) method

  of proving that two sets have the same cardianlity.

  Recall (Definition 13.4) that |A| ≤ |B| means that |A| < |B| or |A| = |B|. If

  |A| < |B| then (by Definition 13.4) there is an injection A → B. On the other

  hand, if |A| = |B|, then there is a bijection (hence also an injection) A → B.

  Thus |A| ≤ |B| implies that there is an injection f : A → B.

  Likewise, |B| ≤ |A| implies that there is an injection g : B → A.

  Our aim is to show that if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. In

  other words, we aim to show that if there are injections f : A → B and

  g : B → A, then there is a bijection h : A → B. The proof of this fact, though

  not particularly difficult, is not entirely trivial, either. The fact that f and

  g guarantee that such an h exists is called the the Cantor-Bernstein-

  Schröeder theorem. This theorem is very useful for proving two sets A

  and B have the same cardinality: it says that instead of finding a bijection

  A → B, it suffices to find injections A → B and B → A. This is useful because

  injections are often easier to find than bijections.

  We will prove the Cantor-Bernstein-Schröeder theorem, but before

  doing so let’s work through an informal visual argument that will guide

  us through (and illustrate) the proof.

  Suppose there are injections f : A → B and g : B → A. We want to use

  them to produce a bijection h : A → B. Sets A and B are sketched below.

  For clarity, each has the shape of the letter that denotes it, and to help

  distinguish them the set A is shaded.

  A

  B

  Figure 13.3. The sets A and B

  The injections f : A → B and g : B → A are illustrated in Figure 13.4.

  Think of f as putting a “copy” f (A) = © f (x) : x ∈ Aª of A into B, as illustrated.

  This copy, the range of f , does not fill up all of B (unless f happens to be

  surjective). Likewise, g puts a “copy” g(B) of B into A. Because they are

  The Cantor-Bernstein-Schröeder Theorem

  233

  not necessarily bijective, neither f nor g is guaranteed to have an inverse.

  But the map g : B → g(B) from B to g(B) = {g(x) : x ∈ B} is bijective, so there

  is an inverse g−1 : g(B) → B. (We will need this inverse soon.)

  g

  f

  g−1

&n
bsp; Figure 13.4. The injections f : A → B and g : B → A

  Consider the chain of injections illustrated in Figure 13.5. On the left,

  g puts a copy of B into A. Then f puts a copy of A (containing the copy of

  B) into B. Next, g puts a copy of this B-containing-A-containing-B into A,

  and so on, always alternating g and f .

  f

  f

  f

  g

  g

  g

  · · ·

  Figure 13.5. An infinite chain of injections

  The first time A occurs in this sequence, it has a shaded region A − g(B).

  In the second occurrence of A, the shaded region is (A− g(B))∪(g◦ f )(A− g(B)).

  In the third occurrence of A, the shaded region is

  (A − g(B)) ∪ (g ◦ f )(A − g(B)) ∪ (g ◦ f ◦ g ◦ f )(A − g(B)).

  To tame the notation, let’s say (g ◦ f )2 = (g ◦ f ) ◦ (g ◦ f ), and (g ◦ f )3 =

  (g ◦ f )◦(g◦ f )◦(g◦ f ), and so on. Let’s also agree that (g◦ f )0 = ι A, that is, it is

  the identity function on A. Then the shaded region of the nth occurrence

  of A in the sequence is

  n−1

  [ (g ◦ f )k(A − g(B)).

  k=0

  This process divides A into gray and white regions: the gray region is

  ∞

  G = [ (g ◦ f )k(A − g(B)),

  k=0

  234

  Cardinality of Sets

  and the white region is A − G. (See Figure 13.6.)

  Figure 13.6 suggests our desired bijection h : A → B. The injection f

  sends the gray areas on the left bijectively to the gray areas on the right.

  The injection g−1 : g(B) → B sends the white areas on the left bijectively

  to the white areas on the right. We can thus define h : A → B so that

  h(x) = f (x) if x is a gray point, and h(x) = g−1(x) if x is a white point.

  A

  B

  f

  g−1

  f

  g−1

  ...

  Figure 13.6. The bijection h : A → B

  This informal argument suggests that given injections f : A → B and

  g : B → A, there is a bijection h : A → B. But it is not a proof. We now

  present this as a theorem and tighten up our reasoning in a careful proof,

  with the above diagrams and ideas as a guide.

  Theorem 13.10 (The Cantor-Bernstein-Schröeder Theorem)

  If |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. In other words, if there are injections

  f : A → B and g : B → A, then there is a bijection h : A → B.

  Proof. (Direct) Suppose there are injections f : A → B and g : B → A. Then,

  in particular, g : B → g(B) is a bijection from B onto the range of g, so it

  has an inverse g−1 : g(B) → B. (Note that g : B → A itself has no inverse

  g−1 : A → B unless g is surjective.) Consider the subset

  ∞

  G = [ (g ◦ f )k(A − g(B)) ⊆ A.

  k=0

  The Cantor-Bernstein-Schröeder Theorem

  235

  Let W = A − G, so A = G ∪ W is partitioned into two sets G (think gray) and

  W (think white). Define a function h : A → B as

  (

  f (x)

  if x ∈ G

  h(x) =

  g−1(x)

  if x ∈ W.

  Notice that this makes sense: if x ∈ W, then x ∉ G, so x ∉ A − g(B) ⊆ G, hence

  x ∈ g(B), so g−1(x) is defined.

  To finish the proof, we must show that h is both injective and surjective.

  For injective, we assume h(x) = h( y), and deduce x = y. There are three

  cases to consider. First, if x and y are both in G, then h(x) = h( y) means

  f (x) = f (y), so x = y because f is injective. Second, if x and y are both in W,

  then h(x) = h( y) means g−1(x) = g−1( y), and applying g to both sides gives

  x = y. In the third case, one of x and y is in G and the other is in W.

  Say x ∈ G and y ∈ W. The definition of G gives x = (g ◦ f )k(z) for some

  k ≥ 0 and z ∈ A − g(B). Note h(x) = h(y) now implies f (x) = g−1(y), that is,

  f ((g ◦ f )k(z)) = g−1(y). Applying g to both sides gives (g ◦ f )k+1(z) = y, which

  means y ∈ G. But this is impossible, as y ∈ W. Thus this third case cannot

  happen. But in the first two cases h(x) = h( y) implies x = y, so h is injective.

  To see that h is surjective, take any b ∈ B. We will find an x ∈ A with

  h(x) = b. Note that g(b) ∈ A, so either g(b) ∈ W or g(b) ∈ G. In the first case,

  h(g(b)) = g−1(g(b)) = b, so we have an x = g(b) ∈ A for which h(x) = b. In the

  second case, g(b) ∈ G. The definition of G shows

  g(b) = (g ◦ f )k(z)

  for some k > 0, and z ∈ A − g(B). Thus

  g(b) = (g ◦ f ) ◦ (g ◦ f )k−1(z).

  Rewriting this,

  ³

  ´

  g(b) = g f ¡(g ◦ f )k−1(z)¢ .

  Because g is injective, this implies

  b = f ¡(g ◦ f )k−1(z)¢.

  Let x = (g ◦ f )k−1(z), so x ∈ G by definition of G. Observe that h(x) = f (x) =

  f ¡(g ◦ f )k−1(z)¢ = b. We have now seen that for any b ∈ B, there is an x ∈ A

  for which h(x) = b. Thus h is surjective.

  Since h : A → B is both injective and surjective, it is also bijective.

  ■

  236

  Cardinality of Sets

  Here are some examples illustrating how the Cantor-Bernstein-Schröeder

  theorem can be used. This includes a proof that |R| = |P(N)|.

  Example 13.6

  The intervals [0, 1) and (0, 1) in R have equal cardinalities.

  Surely this fact is plausible, for the two intervals are identical except for

  the endpoint 0. Yet concocting a bijection [0, 1) → (0, 1) is tricky. (Though

  not particularly difficult: see the solution of Exercise 11 of Section 13.1.)

  For a simpler approach, note that f (x) = 1

  x

  4 + 1

  2

  is an injection [0, 1) → (0, 1).

  Also, g(x) = x is an injection (0, 1) → [0, 1). The Cantor-Bernstein-Schröeder

  theorem guarantees a bijection h : [0, 1) → (0, 1), so |[0, 1)| = |(0, 1)|.

  Theorem 13.11

  The sets R and P(N) have the same cardinality.

  Proof. Example 13.4 shows that |R| = |(0,1)|, and Example 13.6 shows

  |(0, 1)| = |[0, 1)|. Thus |R| = |[0,1)|, so to prove the theorem we just need to

  show that |[0, 1)| = |P(N)|. By the Cantor-Bernstein-Schröeder theorem, it

  suffices to find injections f : [0, 1) → P(N) and g : P(N) → [0, 1).

  To define f : [0, 1) → P(N), we use the fact that any number in [0, 1) has

  a unique decimal representation 0.b1b2b3b4 . . ., where each bi one of the

  digits 0, 1, 2, . . . , 9, and there is not a repeating sequence of 9’s at the end.

  (Recall that, e.g., 0.359999 = 0.360, etc.) Define f : [0, 1) → P(N) as

  f ¡0.b1b2b3b4 . . . ¢ = ©10b1, 102b2, 103b3, ...ª.

  For example, f (0.121212) = ©10, 200, 1000, 20000, 100000, . . . ª, and f (0.05) =

  ©0,500ª. Also f (0.5) = f (0.50) = ©0,50ª. To see that f is injective, take two

  unequal numbers 0.b1b2b3b4 . . . and 0.d1d2d3d4 . . . in [0, 1). Then bi 6= di for

  some index i. Hence bi10i ∈ f (0.b1b2b3b4 . . .) but bi10i ∉ f (0.d1d2d3d4 . . .), so

  f (0.b1b2b3b4 . . .) 6= f (0.d1d2d3d4 ...). Consequently f is injective.

  Next, define g : P(N) → [0, 1), where g(X ) = 0.b1b2b3b4 . . . is the number

  for which bi = 1 if i ∈ X and bi
= 0 if i ∉ X . For example, g¡©1, 3ª¢ = 0.101000,

  and g¡©2, 4, 6, 8, . . . ª¢ = 0.01010101. Also g(;) = 0 and g(N) = 0.1111. To see

  that g is injective, suppose X 6= Y . Then there is at least one integer i

  that belongs to one of X or Y , but not the other. Consequently g(X ) 6= g(Y )

  because they differ in the ith decimal place. This shows g is injective.

  From the injections f : [0, 1) → P(N) and g : P(N) → [0, 1), the Cantor-

  Bernstein-Schröeder theorem guarantees a bijection h : [0, 1) → P(N). Hence

  |[0, 1)| = |P(N)|. As |R| = |[0,1)|, we conclude |R| = |P(N)|.

  ■

  The Cantor-Bernstein-Schröeder Theorem

  237

  We know that |R| 6= |N|. But we just proved |R| = |P(N)|. This suggests

  that the cardinality of R is not “too far” from |N| = ℵ0. We close with a few

  informal remarks on this mysterious relationship between ℵ0 and |R|.

  We established earlier in this chapter that ℵ0 < |R|. For nearly a century

  after Cantor formulated his theories on infinite sets, mathematicians

  struggled with the question of whether or not there exists a set A for which

  ℵ0 < |A| < |R|.

  It was commonly suspected that no such set exists, but no one was able

  to prove or disprove this. The assertion that no such A exists came to be

  called the continuum hypothesis.

  Theorem 13.11 states that |R| = |P(N)|. Placing this in the context of

  the chain (13.2) on page 230, we have the following relationships.

  ℵ0

  |R|

  =

  =

  |N| < |P(N)| < |P(P(N))| < |P(P(P(N)))| < ···

  From this, we can see that the continuum hypothesis asserts that no set

  has a cardinality between that of N and its power set.

  Although this may seem intuitively plausible, it eluded proof since

  Cantor first posed it in the 1880s. In fact, the real state of affairs is

  almost paradoxical. In 1931, the logician Kurt Gödel proved that for any

  sufficiently strong and consistent axiomatic system, there exist statements

  which can neither be proved nor disproved within the system.

  Later he proved that the negation of the continuum hypothesis cannot

  be proved within the standard axioms of set theory (i.e., the Zermelo-

  Fraenkel axioms, mentioned in Section 1.10). This meant that either the

  continuum hypothesis is false and cannot be proven false, or it is true.

  In 1964, Paul Cohen discovered another startling truth: Given the laws

  of logic and the axioms of set theory, no proof can deduce the continuum

 

‹ Prev