Massachusetts Institute of Technology Lecture 18 6.042J/18.062J: Mathematics for Computer Science November 9, 2000 Professors Nancy Lynch and Srinivas Devadas

Infinite Sets

Topics for today:

• Finite vs. infinite Sets

• Countable sets

• Uncountable sets

• Cardinalities of infinite sets

• Even bigger infinite sets

Reading: Velleman Chapter 7; Rosen 1.7

The topic of this lecture is infinite sets.

Infinite sets can be tricky to think about. For for example, previously we saw the Pigeonhole Principle, which says that if a big set is mapped to a small set, then some two items of the big set must be mapped to the same item in the small set. We also saw that the Pigeonhole Principle appears to break down for infinite sets. In particular, the “big” set {0, 1, 2, 3, 4, … } of all natural numbers is mapped one-to-one to the “small” set {0, 2, 4, 6, 8, … } of even numbers by the function f(n) = 2n. This raises confusion about what is meant by “big” and “small” infinite sets. One of the key points of this lecture is sorting out the relative “bigness” of various infinite sets.

This subject is more abstract than others in 6.042. The techniques we develop for dealing with infinite sets will be useful later on in 6.045 when you learn about computability.

1 Finite Sets vs. Infinite Sets

Let’s start by defining what it means for a set to be “infinite”.

Definition A set S is finite if there exists an n ∈ N such that |S| = n.

Definition A set S is infinite if it is not finite.

These definitions imply that every set is either finite or infinite.

Let’s make sure we know what these definitions really mean. They depend on the definition of “cardinality” for finite sets, which we review here

Definition We say that set S has size, or cardinality, n, and write |S| = n, if and only if there is a bijection from S to the set of integers {1, …, n}.

This definition is unambiguous, as can be seen from the following lemma:

Lemma 1.1 There is at most one n such that |S| = n.

Proof. Suppose |S| = n and |S| = m. Then there is a bijection f from S to {1, …, n} and a bijection g from S to {1, …, m}. It follows that h = g ∘ f^{−1} is a bijection from {1, …, n} to {1, …, m}. If n > m then by the Pigeonhole Principle, h maps two elements of {1, …, n} to the same element of {1, …, m}, so is not a bijection. This is a contradiction. Similarly, if m > m, then h^{−1} (also a bijection) maps two elements of {1, …, m} to the same element of {1, …, n}. This is also a contradiction. The only remaining possibility is that m = n.

We just used the Pigeonhole Principle in a rather formal proof. In fact, we never really proved the Pigeonhole Principle. Here is a proof.

Theorem 1.2 (Pigeonhole Principle) If n > m, then there is no injection (and thus no bijection) from {1, …, n} to {1, …, m}

Proof. By well ordering on m. Suppose for contradiction that the claim is not always true, and consider the smallest m for which it fails—that is, there is some injection f : {1, …, n} → {1, …, m}.

Case 1. There is no i such that f(i) = m. Then in fact f : {1, …, n} → {1, …, m − 1} so m is not the smallest counterexample—a contradiction.

Case 2. For some i we have f(i) = m. Case 2a. i = n. Consider the function g : {1, …, n − 1} → {1, …, m − 1} defined by g(i) = f(i). Since f is an injection, no element of {1, …, n − 1} other than n is mapped by f to m, so every other element of {n − 1} is mapped to a number less than m. Therefore, g does indeed map {1, …, n − 1} to {1, …, m − 1}. And since f is an injection, and g has the same mapping, g is also an injection. But n − 1 > m − 1, so g is a counterexample for m − 1, which shows m was not the smallest counterexample—another contradiction.

Case 2b. i ≠ n. We define a slightly different g and argue as in case 2a. The function g is given by g(j) = f(j) for j ≠ i, but g(i) = f(n). Since f(i) = m and f is a bijection, we know that f(n) ≠ m, and thus f(n) < m. It follows that g(j) < m for every j < n. And once again, g is a bijection because f is, so we have a smaller counterexample—the last contradiction.

We have shown a contradiction in every case, so our initial assumption that the lemma is not true must be false.

So, our definitions of finite and infinite sets should be clear, both formally and informally. For example, for all n, the set {0, 1, 2, 3, …, n} is finite. On the other hand, the set of all natural numbers, N = {0, 1, 2, 3, … }, is infinite. A more interesting example arose in the very first lecture this term:

Theorem 1.3 The set P of all primes is infinite.

Proof. The proof is by contradiction. Assume for the purpose of contradiction that P is finite. Then by the definition of a finite set, there exists an n ∈ N such that |P | = n. Denote the elements of P by p_{1}, p_{2}, …, p_{n}. Now let m = p_{1}p_{2} ⋯ p_{n} + 1. Since m > p_{i} for all i, m cannot be a prime. Hence m must be divisible by some prime p_{i}:

p_{i} | m
⇒ p_{i} | p_{1}p_{2} ⋯ p_{n} + 1
⇒ p_{i} | 1

The first implication follows by substituting the definition of m. The second follows because p_{i} divides the product p_{1}p_{2} ⋯ p_{n}, and so must divide 1 in order to divide the sum. But no prime divides 1, so we have a contradiction. Therefore, there are an infinite number of primes.

Proving that the set of primes is infinite is relatively easy, but the next example shows that determining whether a set is finite or infinite can be tricky.

Definition A twin prime is a pair (n, n + 2) such that both n and n + 2 are prime.

Examples of twin primes include (3, 5), (5, 7), (11, 13), (17, 19), and (101, 103). Is the set of twin primes finite or infinite? If you settle this question, then you can probably wheedle a few extra credit points from your TA. Mathematicians have tried unsuccessfully to solve this problem for more than two thousand years!

Other examples of infinite sets: the natural numbers, the even natural numbers, the integers, the rationals, the reals.

Note that I haven’t yet talked about the “cardinality” of an infinite set, |S|. It’s not obvious what this means. We could just write |S| = ∞. But it turns out there are different “sizes” of infinity. In the rest of this lecture, we will try to classify different kinds of infinities. Sample question: What is the “smallest” kinds of infinite set?

2 Countable Sets

2.1 Definition

Countably infinite sets are the ones that are “like N” in the sense that we can enumerate them in a list format:

N = {0, 1, 2, 3, … }
even numbers = {0, 2, 4, 6, … }
squares = {0, 1, 4, 9, 16, … }
primes = {2, 3, 5, 7, 11, … }

Sets whose elements can be listed are called countable sets. Of course, we cannot write down every element, but the … imply that if we keep going, writing down more elements of the list, we will eventually get to any element that is supposed to be present. That is, there is a first element, a second element, etc. Equivalently, we can count through the items one after another so that every element of the set is eventually counted. Countable sets are formally defined in terms of bijections with the natural numbers.

Definition An infinite set S is said to be countably infinite iff there exists a bijection f : N ↦ S. A set is countable if it is finite or countably infinite.

This formal definition is equivalent to the notion of a listable set, since listing the elements of a set gives a bijection with N and vice versa. When we list the elements of S as s_{0}, s_{1}, s_{2}, …, we are actually defining a bijection f : N ↦ S by f(i) = s_{i}. In the reverse direction, if we have such a bijection, then f(0), f(1), f(2), … is a list of all the elements of S.

Caution: Sometimes we can list the elements of a set S, but the corresponding bijection f : N ↦ S is very hard to compute. For example, in principle we could list the elements in any subset of N. However, most of these subsets are bizarre and difficult to describe; writing a program to compute f(i) might be difficult or even impossible. The good news is that to prove that S is countable, we must only prove that a bijection f : N ↦ S exists; we do not have to write f explicitly or to give an algorithm to compute f(i).

Let’s use this definition to prove that some sets are countable.

Lemma 2.1 The set of even numbers is countably infinite.

Proof. An example of a bijection from N to {0, 2, 4, 6, 8, …} is the function f(x) = 2x.

Another example of a bijection between these sets is obtained by listing the even numbers in another order, say 2, 0, 6, 4, 10, 8, . . . .... This listing defines the desired bijection, e.g. f(0) = 2, f(1) = 0, f(2) = 6, f(3) = 4, etc. This is the typical way to prove that a set is countably infinite—just show that you can list all of the elements. This implicitly defines a bijection with N. Note that we only have to prove that a bijection f exists; it is not necessary to come up with a closed-form formula for computing f.

Example 2.2 Set B of finite length bit strings. Enumerate B as: λ, 0, 1, 00, 01, 10, 11, 000, . . ..

2.2 Integers

Theorem 2.3 The set Z of integers is countably infinite.

Proof. To prove that that the integers are countably infinite, we must prove that there exists a bijection f : N ↦ Z. The integers can be listed as follows: 0, 1, −1, 2, −2, 3, −3, 4, −4, . . ..

As noted above, we only have to prove that a bijection f exists; we don’t need a formula. In this case, however, f can be written as:

f(i) = \{ \begin{matrix}−\frac{i}{2} & if i is even, \\ \frac{i+1}{2} & if i is odd. \end{matrix}

The method of proving a set countable by listing elements has one potential pitfall. As an example, the following listing of the integers does not demonstrate countability:

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

The problem is that the “… ” in the middle of the list represents a infinite number of elements. As a result, we never actually get around to listing the positive integers; in particular, there is no i such that f(i) = 1. This means that the function f “defined” by this listing is not a bijection (actually, it is not properly “defined” at all).

2.3 Unions of Countable Sets

The integers can be viewed as the union of two countably infinite sets: the natural numbers and the negative integers. The natural numbers are obviously countably infinite. It is also easy to see that the negative integers are countably infinite. The “interleaving” strategy described above is a way to see that the union of these two countably infinite sets is also countably infinite.

Another example: Half integers. Define the set Z^{1/2} as follows:

Z^{1/2} = \{\frac{x}{2} | x ∈ Z\}
= \{0, 1, −1, 2, −2, … \} ∪ \{\frac{1}{2}, −\frac{1}{2}, \frac{3}{2}, −\frac{3}{2}, … \}

In other words, Z^{1/2} consists of all integers and all half integers. This set is countable. We have written Z^{1/2} above as the union of two countable sets. We can list all the elements of Z^{1/2} by interleaving these two lists:

Z^{1/2} = \{0, \frac{1}{2}, 1, −\frac{1}{2}, −1, \frac{3}{2}, 2, −\frac{3}{2}, −2, … \}

This trick generalizes to a theorem.

Theorem 2.4 If A and B are countable, then A ∪ B is countable.

Proof. From the definition of “countable”, we have four cases. Each of A and B may be countably infinite or finite. If both are countably infinite, we can list the elements:

A = {a_{1}, a_{2}, a_{3}, … }
B = {b_{1}, b_{2}, b_{3}, … }

Therefore, we can list the elements of the union as follows:

A ∪ B = {a_{1}, b_{1}, a_{2}, b_{2}, a_{3}, b_{3}, … }

There is a complication: sets A and B may contain common elements. Therefore, an element should be omitted from the list if it already appears in a smaller position.

If one of the sets is finite, we continue listing elements of the other set without interleaving.

If both are finite, then, as we already know, the union is finite, which means that it’s countable.

2.4 Rationals

Recall that the set Q of rational numbers consists of all ratios of integers with non-zero denominator:

Q = {a/b | a, b ∈ Z, b ≠ 0}

There are a lot of rational numbers! It is easy to imagine that we could not list all the rational numbers just as we could not list all the real numbers. In fact, however, there is a clever way to list all the rationals, and this proves that the set Q is countable.

Theorem 2.5 The set Q of rational numbers is countable.

Proof. (Failed attempt.) To prove that that the rational numbers are countable, we must prove that there exists a bijection f : N ↦ Q. The rational numbers can be listed as follows:

0, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, …, \frac{1}{2}, \frac{2}{2}, \frac{3}{2}, …, \frac{1}{3}, \frac{2}{3}, \frac{3}{3}, …

Omit from the listing all numbers that have already appeared. (For example, 2/2 and 3/3 should be omitted, since the rational number 1 already appeared as 1/1.) This listing implicitly defines the desired bijection f.

There are two problems with this “proof”, one minor and one serious. The minor problem is that we completely forgot the negative rational numbers. But the negative rationals are easy to add; we will show how in the correct proof given below. The killer problem is that we used “… ” in the middle of the list to represent an infinite number of elements. This means that we will never reach, say, 1/2; that is, there is no i such that f(i) = 1/2. This means that f is not a bijection as claimed. We need to list the rational numbers in a completely different order to make the proof work.

Proof. (Successful attempt.) We can list the positive rational numbers in the order indicated in Figure 1, omitting numbers that have already appeared in the list. This proves that the positive rationals are countable.

Figure 1: This digram shows the ordering of rationals used in the proof of Theorem 2.5. This ordering technique is called “dovetailing”.

Negating each number in the figure establishes that the negative rationals are countable. The set of all rationals is the union of positive rationals, negative rationals, and {0}. Since these three sets are countable, two applications of Theorem 2.4 show that the set of all rationals is countable.

2.5 Products of Countable Sets

The ordering technique used in the proof and indicated in Figure 1 is called “dovetailing”. This technique is often used in 6.045. We can use dovetailing to prove that the product of any two countable sets is countable:

Theorem 2.6 If A and B are countable, then A × B is countable.

Proof. Since A and B are countable, we can list the elements of A as {a_{1}, a_{2}, a_{3}, … } and the elements of B as {b_{1}, b_{2}, b_{3}, … }. We can obtain a listing of A × B by dovetailing:

(a_{1}, b_{1}),
(a_{1}, b_{2}), (a_{2}, b_{1}),
(a_{1}, b_{3}), (a_{2}, b_{2}), (a_{3}, b_{1}),
(a_{1}, b_{4}), (a_{2}, b_{3}), (a_{3}, b_{2}), (a_{4}, b_{1}),
…  …

If either or both sets A and B are finite, omit from the listing all pairs containing non-existent elements a_{i} or b_{j}.

Note that the ordering of elements in this proof corresponds to the ordering in Figure 1. In fact, the proof that the rationals are countable used the idea of the above proof with A = B = Z^{+}.

Example 2.7 The Cartesian product N × N is countable. That’s because it’s the product of two countable sets.

Another way of viewing the product examples is as countable unions of countable sets. E.g., for the N × N example, we can express the entire set as the countable union of sets A_{i}, i ∈ N, where A_{i} is defined to be the set of all pairs of the form (i, n), n ∈ N. In general, we have:

Theorem 2.8 If for all i ∈ N, A_{i} is a countable set, then ⋃_{i∈N} A_{i} is countable.

Proof. Use a dovetailing construction.

2.6 The Smallest Infinite Sets

Is N the smallest infinite set? We can show that it is, in the following sense:

Theorem 2.9 Suppose T is “no larger” than N, in the sense that T has a bijection with a subset of N. Then T is either countably infinite or finite.

Proof. Assume that there is a bijection between T and a subset A of N. Write A = {a_{0}, a_{1}, a_{2}, … }, listing the elements of A in the order in which they appear in N. If A is finite, then T is also finite because of the bijection.

On the other hand, if A is infinite, then there is a bijection from N to A, given by the enumeration of A above. Also, there is a bijection from A to T, by assumption. So by composition of bijections, there is a bijection from N to T. That says that T is countably infinite.

This theorem says that there is nothing whose “size” is between the countably infinite sets and the finite sets. We still haven’t defined the size of an infinite set; we’ll come back to this later in the lecture.

So far, we have finite sets and countably infinite sets. Let’s continue classifying. Are all infinite sets countably infinite?

3 Uncountable Sets

It turns out that many important sets are not countable. Sets that are not countable are called uncountable.

3.1 Reals

The most important example of an uncountable set is the reals:

Theorem The set R of real numbers is uncountable.

This theorem says that there is no way to make a list of all the real numbers. Naturally, one is immediately tempted to try anyway:

0, 1, 0.5, 0.75, 0.1, 0.05, 0.001, …

It looks like this is not going to be so easy! For example, where are we going to stick in \sqrt{2} and π^{−173}? We can actually prove that no such listing exists.

We’ll first work through the proof informally, and then make it more formal. The argument is by contradiction; we assume for the purpose of contradiction that R is countable. This means that there exists a bijection f : N ↦ R. We can then make a list of all the real numbers that looks something like the one shown below. (The extra spaces only serve to highlight a diagonal sequence of digits discussed below.)

                    f(0) =  76. 5 430000000...
                    f(1) = 163.7 7 77777777...
                    f(2) =   2.78 7 8787878...
                    f(3) =  -1.112 1 231234...
                    f(4) =   3.1415 9 26535...
                    f(5) = -15.37273 2 3928...
                    ...

The plan is to reach a contradiction by constructing a real number that appears nowhere in the list; this will prove that f is not surjective and contradict the assumption that f is a bijection.

Consider the number defined by the diagonal digits in the above table, 0.577192 . . .. Now suppose that we add 5 to every digit, working modulo 10. This gives 0.022647 …; call this value r. This quantity r is totally bizarre, but it is a well-defined real number, since we have specified all the digits.

By our construction of r, f(0) differs from r in the first position to the right of the decimal. Similarly, f(1) differs from r in the second decimal position, f(2) differs in the third position, and so forth. In general, f(i) differs from r in the (i + 1)-st position. So for all i, f(i) is not equal to r. This implies that the real number r does not appear anywhere in our list! That contradicts our assumption that the list contains all the reals.

There is one irritating problem in the preceding paragraph that must be fixed. Some numbers have two decimal representations. For example, 1 = 0.999 . . .. Therefore, distinct decimal representations do not necessarily correspond to distinct numbers. Even though r disagrees with f(i) in at least one digit, the two might be equal. However, our construction ensures that r actually differs from f(i) by at least 4 · 10^{−(i+1)}. For example, 1.0002999 … differs from 1.0007000 … by 4 · 10^{−4}.

Here is how the same argument might be written as a formal proof.

Proof. We must show that there is no bijection f : N ↦ R. The proof is by contradiction. Assume for the purpose of contradiction that such a bijection f exists. Let r be the real number with decimal expansion 0.r_{0}r_{1}r_{2}r_{3} … where r_{i} is 5 + the (i + 1)-st decimal digit of f(i), taken modulo 10. For all i, f(i) ≠ r, since the (i + 1)-st digits of f(i) and r disagree by 5 and so |r − f(i)| ≥ 4 · 10^{−(i+1)}. This implies that f is not surjective, contradicting the assumption that f is a bijection.

This is called a “diagonalization argument”, because of the construction based on diagonal entries. Diagonalization arguments are used all the time to prove that there is no bijection between two infinite sets. The generic idea is to assume for the purpose of contradiction that a bijection f exists. Then an element r of the range is constructed that differs from f(α) for every α in the domain. (In this case, for example, the real number r differs from f(k) in the (k + 1)-st decimal position for every natural k.) The existence of such an r shows that f is not surjective, contradicting the assumption that f is a bijection. We conclude that no bijection between the two sets exists.

Diagonalization arguments are important in logic and computer science. For example, this type of argument is used to show that there are some problems that cannot be solved by a computer no matter how much time you give them. A similar method is used in logic to prove Gödel’s Theorem, which says that there are some true theorems for which no proof exists!

As with countable sets, bijections provide the way to see that two uncountable sets are the “same size.”

Lemma 3.1 Let (0, 1) be the reals between 0 and 1. Let ℝ^{+} be the positive real numbers. Then there is a bijection between the interval (0, 1) and ℝ^{+}

Proof. The function f(x) = 1/(1 + x) is a bijection from the positive reals to (0, 1).

This is a bit surprising, as the positive reals seem much bigger.

Example 3.2 Countable or uncountable? Define S_{n} to be the set of n-digit decimal numbers. For example:

S_{1} = {.0, .1, .2, …, .9}
S_{2} = {.00, .01, .02, …, .99}

Now let S = ⋃_{n=1}^{∞} S_{n}. Is S countable?

Argument that S is uncountable: We will prove that S is uncountable by the same diagonalization argument that we used to prove that the set R of real numbers is uncountable. Assume for the purpose of contradiction that we can list the elements of S in some order s_{0}, s_{1}, s_{2}, . . .. Define r = .r_{0}r_{1}r_{2} … where r_{i} is 5 + the (i + 1)-st decimal digit of s_{i} taken modulo 10. Since S contains decimal numbers of every length, r must be in S. However, r differs from every element of S by at least one digit. Therefore, r is not in S, and we have a contradiction.

Argument that S is countable: We can list the elements of S by listing the elements of S_{1}, followed by S_{2}, followed by S_{3}, etc. Since each of these sets is finite, every set is fully listed eventually.

The first argument is incorrect, and the second argument is correct. The false statement in the first argument is, “Since S contains decimal numbers of every length, r must be in S.” The set S does contain decimal numbers of every finite length, but no numbers with an infinite number of non-zero digits to the right of the decimal. For example, the number 1/9 = 0.11111 … is not contained in any set S_{i} and therefore is not contained in the union S. As a result, there are many real numbers not in S. For this reason, the statement, “r must be in S” is false. This eliminates the contradiction from the proof by contradiction!

The second argument is correct; the union of a countable number of finite sets is always countable.

3.2 The Subsets of N

Theorem 3.3 The set P (N) of all subsets of N is uncountable.

In contrast, note that the set of all finite subsets of N is countable. That’s because we can list all of these (say, in order of size).

Proof. By contradiction, using a diagonalization construction like the one for the reals. It’s actually a little simpler, because we don’t have the complication of duplicate representations.

Represent each set S by a bit string, with a 1 in exactly the positions corresponding to numbers i ∈ S. (E.g., evens are represented by the string 1, 0, 1, 0, 1, . . ..) Every set has exactly one representation.

Suppose we could enumerate all these sets, e.g.: S_{0} : 1010101 … S_{1} : 0001000 … S_{2} : 1110110 … ...

So, the bit in position j of the string corresponding to S_{i} is 1 if j ∈ S_{i}, 0 if not.

Now get a contradiction by finding a subset T of N that doesn’t appear in the list. Construct T so that it differs from each set in the membership of the diagonal element, that is, it differs from S_{0} in the membership of 0, differs from S_{1} in the membership of 1, etc. Thus, 0 ∈ T iff 0 ∉ S_{0}, 1 ∈ T iff 1 ∉ S_{1}, and, in general, i ∈ T iff i ∉ S_{i}.

Obviously, T doesn’t appear in the list, so this list cannot contain all the subsets of N. This is a contradiction, so P (N) is uncountable.

Proof. (Alternative:) In the construction above, the set T can be written in a more-obscure-looking way as T = {i|i ∉ S_{i}}. That is, T is the set of all natural numbers that don’t belong to the set with that number as its index. The contradiction can be obtained by supposing that T does appear in the list, so it must be S_{j} for some j. Then we consider whether j ∈ T or not, and get a contradiction either way. For, if j ∈ T, it means that j ∈ S_{j}, which means that j ∉ T by definition of T. And if j ∉ T, then it means that n ∉ S_{j}, which means that j ∈ T by definition of T. Either way, a contradiction.

The idea of this tricky looking contradiction is drawn from “Russell’s Paradox”. We will see it again in a few minutes.

The distinction between countable and uncountable sets is so important that it distinguishes entire fields of mathematics. Discrete math is the study of countable sets; calculus, analysis, and continuous math all study uncountable sets. In this course, we will stick to discrete mathematics after today; all sets will be countable.

4 Cardinalities of Infinite Sets

There seems to be some similarity between the set of reals and the powerset of the naturals. Are the two sets the same size? It’s finally time to say more about what we mean by sizes of infinite sets.

4.1 Definition

Two sets are considered to be the “same size” if there is a bijection between them. For example, the set of natural numbers is the same size as the set of rational numbers because there is a bijection f : N ↦ Q. On the other hand, the set of natural numbers is not the same size as the set of real numbers because we proved there is no bijection between these sets.

More generally, we say that:

• |A| = |B| iff there exists a bijection f : A ↦ B

• |A| ≤ |B| iff there exists an injection f : A ↦ B

• |A| ≥ |B| iff there exists a surjection f : A ↦ B

• |A| < |B| iff |A| ≤ |B| and |A| ≠ |B|, that is, there is an injection but there is no bijection.

• |A| > |B| iff |A| ≥ |B| and |A| ≠ |B|, that is, there is a surjection but there is no bijection.

If you are being careful, you will see that we haven’t actually given a formal definition of the cardinality of an arbitrary set, but have only given some properties (axioms) that this notion has to satisfy. Some additional properties follow from these axioms, for instance:

Lemma 4.1 |A| ≤ |A|.

Proof. The function f : A → A given by f(a) = a is clearly an injection.

Lemma 4.2 |A| ≤ |B| and |B| ≤ |C| together imply |A| ≤ |C|.

Proof. Let f : A → B and g : B → C be the assumed injections. Then h : A → C given by h(a) = g(f(a)) is also an injection. For suppose that a ≠ a′. Then by injectivity of f, we know f(a) ≠ f(a′). But then by injectivity of g, we know that g(f(a)) ≠ g(f(a′)), that is h(a) ≠ h(a′).

Lemma 4.3 If |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. In other words, if there is an injection from A to B, and an injection from B to A, then there is a bijection from A to B.

Proof. This one is rather tricky. It took 3 famous mathematicians to prove what is now called the Cantor-Schroeder-Bernstein theorem. You can find it in Section 7.3 of Velleman. Basically, you have to construct the bijection by piecing together parts of the two injections.

4.2 Examples

Using CBS makes it easier to prove certain sets are the same size: instead of coming up with a bijection, you can come up with two injections:

Lemma 4.4 |(0, 1)| = |P (N)| where P (N) is the set of all subsets of N

Proof. We construct two injections, one in each direction. Here is an injection from (0, 1) to P (N). For any given real number, consider an expansion as an infinite sequence of binary digits b = 0.b_{0}b_{1}b_{2} … where each b_{i} = 0 or 1. Define S_{b} = {i | b_{i} = 1}. Since any two reals differ in some binary digit at some position i, they will map to different sets—one will contain i and one will not—so this is an injection.

Here is an injection from P (N) to (0, 1). Given S ⊆ N, define a real number 0.b_{0}b_{1}b_{2} … ∈ (0, 1) as follows: b_{i} = 3 if i ∈ S, and b_{i} = 7 otherwise.

One might think the first injection given above is a bijection, but it isn’t. Some sets of natural numbers (e.g.N itself) are not “hit” by the mapping: N would correspond to the real number 0.11111 ⋯ = 1 which is not in the interval at all. And this is not an isolated example. It is much easier to work with pairs of injections.

Corollary 4.5 |ℝ^{+}| = |P (N)|

This follows from Lemma 4.4 and 3.1.

Exercise: Show that |ℝ| = |P (N)|. LTTR.

You can also show that “|A| ≤ |B|” and “|B| ≥ |A|” are equivalent: that is, there is an injection from A to B if and only if there is a surjection from B to A:

Lemma 4.6 |A| ≤ |B| iff |B| ≥ |A|.

4.3 Sets Between ℝ and N?

We have seen that there aren’t any sets that are bigger than the finite sets yet smaller than the countably infinite sets. Are there any sets that are bigger than the countable infinite sets yet smaller than ℝ and P (N)?

It turns out that this is not so easy to answer. Cantor posed this question in the 1870s, but it was not resolved until 1963, by Cohen. He showed that there might or might not be such “in-between” sets—their existence is actually independent of the standard axioms of set theory! The Continuum Hypothesis is a new axiom saying that no such set exists.

5 Other Infinite Sets

We have seen that |N | < |R|. This fact follows from |N | ≤ |R| and |N | ≠ |R|. The first statement holds because there is an injection from N to R; namely, each natural number is mapped to itself. The second statement holds because we have proven that there is no bijection between N and R.

In this sense, N and R are two different kinds of infinities. In fact, there are many types of infinities, and there is a whole branch of mathematics to deal with them. The most common types of infinities are based on power sets. (For now, we will denote the power set of S by P(S).) These types of infinity are denoted by the Hebrew letter aleph, ℵ, with a subscript. A bigger subscript implies a bigger type of infinity. Here are the first few:

ℵ_{0} = |N |
ℵ_{1} = |P(N)| = |R|
ℵ_{2} = |P(P(N))| = |P(R)|
…

Each new type of infinity is obtained by taking the power set of the preceding type of infinity. It is not immediately clear, however, that sets of size ℵ_{2} are really any larger than sets of size ℵ_{1}, or more generally that taking the power set of S gives a larger set than S itself. This fact can be proven, however.

Theorem 5.1 For all sets S, |S| < |P(S)|.

This implies that ℵ_{0} < ℵ_{1} < ℵ_{2} < …, and so there is a whole infinite hierarchy of infinite sets! The statement generalizes that of Theorem 3.3. So we will prove it by generalizing the proof of that theorem, in particular, the “alternative proof” using the idea of Russell’s Paradox.

Proof. We have to prove that |S| ≤ |P(S)| and |S| ≠ |P(S)|.

|S| ≤ |P(S)|: We must show that there exists an injection f : S ↦ P(S). The function f(a) = {a} for all a ∈ S is just such an injection.

|S| ≠ |P(S)|: The proof is by contradiction. Assume for the purpose of contradiction that |S| = |P(S)|. Then there is a surjection f : S ↦ P(S). (In fact, there is a bijection, but we do not need this fact.) To show a contradiction, we will define an item in P(S) that is not covered by f; this will contradict the assertion that f is a surjection. In particular, let T = {a ∈ S|a ∉ f(a)}. The set T is a subset of S, and so T is an element of the power set of S. Since f is a surjection, there must be an a ∈ S such that f(a) = T; fix such an a. Now there are two cases: either a ∈ T or a ∉ T.

(a ∈ T): By the definition of the set T, this implies that a ∉ f(a) = T, a contradiction.

(a ∉ T): Now the definition of the set T implies that a ∈ f(a) = T, another contradiction.

The contradictions in both cases imply that our assumption was wrong; therefore, |S| ≠ |P(S)| and so |S| < |P(S)|.