I’d been completely side-tracked from this set of posts, and I only just realized I had forgotten to finish it. Last time we checked, we had finally figured out that there are different levels of infinity. We had, however, ended up with a rather strange idea: the idea that the set of all real numbers between 0 and 1 is somehow as big as the set of all real numbers in its entirely. In effect, we have shown that there is no difference between a mountain and a molehill!
We thus have two different lines of inquiry to pursue:
We begin with the idea of a power set: the power set of a set is defined as the set of all subsets of the set. Huh? An example should make things clearer: if \( A = \{ a, b, c \} \), then the power set of \( A \), sometimes written as \( \mathcal{P}(A) \) and sometimes \( 2^{A} \) (we’ll see why), is the set \( \mathcal{P}(A) = \{ \{ a \}, \{ b \}, \{ c \}, \{ a, b \}, \{ b, c \}, \{ a, c \}, \{ a, b, c \}, \{ \} \} \). All those braces are necessary, because every element of \( \mathcal{P}(A) \) is a subset (and not an element) of \( A \) itself. We note that \( A \) itself is an element of \( \mathcal{P}(A) \), as is the empty set \( \{ \} \).
Now it is fairly easy to show that if \( A \) is a finite set of cardinality \( n \) (written \( | A | = n \) ), then the cardinality of the power set of A is \( 2^{n} \). More picturesquely, \( | 2^{A} | = 2^{| A |} \).
Why? Well, let’s count the number of subsets of size \( k \) for every number less than or equal to \( n \):
… and so on.
When we add them all up, we somehow magically (a.k.a. the Binomial Theorem!) get \( 2^n \)! Quite magical (not).
This is all very cute, of course, but what happens when \( A \) is not finite? What happens when we take, say \( \mathbb{N} \), as our set? What, in other words, is \( 2^{\mathbb{N}} \)?
We know that for any finite number \( n \), \( 2^n > n \). One of the neat things about Cantor’s diagonalization theorem is that it tells us this is true for any \( n \)—including infinite \( n \)! How?
We recall that we had earlier defined “counting” as establishing a bijective correspondence between two sets. This is how we proved that \( \mathbb{N} \) and \( 2 \mathbb{N} \) were, in fact, the same “size”. So to prove that \( A \) and \( \mathcal{P}(A) \) are not, in fact, the same size, we must show that no correspondence between them can be bijective. And if we can show that no matter what correspondence we take, there is always some element of \( \mathcal{P}(A) \) which gets left out even while every single element of \( A \) is accounted for, then we can prove that \( \mathcal{P}(A) \) is, in fact, bigger than \( A \).
We begin by noting that \( \mathcal{P}(A) \) is at least as large as \( A \). This is true because there is a bijection between \( A \) and the elements of \( \mathcal{P}(A) \) that are all single-element subsets of \( A \). (In symbols, the collection \( \{ a, b, c \} \) has a bijective correspondence with \( \{ \{ a \}, \{ b \}, \{ c \} \} \).) Now consider any function f that maps an element of \( A \) to an element of \( \mathcal{P}(A) \). We need to show that there is at least one element of \( \mathcal{P}(A) \) that cannot be in \( A \) (and let us constantly remind ourselves that an element of \( \mathcal{P}(A) \) is a subset of \( A \) ). How can we find such an element of \( \mathcal{P}(A) \) that does not depend on the particular definition of a correspondence \( f \)?
This is the step in the diagonalization process analogous to picking one digit from every number on the list and modifying it in order to create a new number. But how do we do that with sets? We note that the correspondence \( f \) connects every element \( x \in A\) with an element \( f(x) \in \mathcal{P}(A) \) ; i.e., with a subset of \( A \). Depending on how we define our correspondence, it may be the case that \( x \) is actually an element of the subset that it maps to; or it may be the case that \( x \) is not an element of the subset it maps to. Clever devils that we are, we pick our element of \( \mathcal{P}(A) \) to be the set \( B \) of all those elements of \( A \) which are not elements of the subset they correspond to. (This is like changing the digit we pick so we know our new number differs from every existing number in at least one place.) In symbols, \( B = \{ x \in A | x \notin f(x) \} \).
How do we know that there is no element of \( A \) that can be mapped to \( B \) by \( f \) Why, by the very definition of \( B \) itself! Suppose, for the sake of contradiction, that there does exist a \( y \in A \) such that \( f(y) = B \). By the definition of \( B \), this must mean that \( y \notin B \). But then by the definition of \( B \), we have \( y \in B \)! This is a clear contradiction, which shows that there simply cannot be any such \( y \). In other words, \( \mathcal{P}(A) \) is always larger than \( A \)—regardless of whether \( A \) has finitely many elements or not!
Thus, \( 2^{\mathbb{N}} \) must needs be greater than \( \mathbb{N} \) in size. But we also know, through a different diagonalization proof, that \( \mathbb{R} \) is greater than \( \mathbb{N} \) in size. Is it in fact true that \( \mathbb{R} = 2^{\mathbb{N}} \)? As it turns out, this question is better answered by taking \( \mathbb{Q} \) rather than \( \mathbb{N} \) (but as we saw earlier, these two sets are the same size, and so it doesn’t really matter). And the answer, which I will not go into in any detail, is yes. When we construct real numbers by the method of Dedekind cuts, we do in fact map every real number to a subset of \( \mathbb{Q} \). The converse can also be shown to be true.
But regardless, the power set argument shows that there have to be infinities greater than the uncountable set of the real numbers. The power set of the real numbers, \( \mathcal{P}(\mathbb{R}) \), is strictly larger than \( \mathbb{R} \), and its own power set \( \mathcal{P}(\mathcal{P}(\mathbb{R})) = 2^{2^{\mathbb{R}}}\) is larger still, and so on, ad infinitum! (A more concrete example of a set that is of cardinality \( 2^{\mathbb{R}} \) is the set of all functions from \( \mathbb{R} \) to \( \mathbb{R} \).)
We thus have two different lines of inquiry to pursue:
- Are there levels of infinity beyond the infinity of the real numbers?
- Are there ways to measure the size of a set that can distinguish mountains from molehills?
We begin with the idea of a power set: the power set of a set is defined as the set of all subsets of the set. Huh? An example should make things clearer: if \( A = \{ a, b, c \} \), then the power set of \( A \), sometimes written as \( \mathcal{P}(A) \) and sometimes \( 2^{A} \) (we’ll see why), is the set \( \mathcal{P}(A) = \{ \{ a \}, \{ b \}, \{ c \}, \{ a, b \}, \{ b, c \}, \{ a, c \}, \{ a, b, c \}, \{ \} \} \). All those braces are necessary, because every element of \( \mathcal{P}(A) \) is a subset (and not an element) of \( A \) itself. We note that \( A \) itself is an element of \( \mathcal{P}(A) \), as is the empty set \( \{ \} \).
Now it is fairly easy to show that if \( A \) is a finite set of cardinality \( n \) (written \( | A | = n \) ), then the cardinality of the power set of A is \( 2^{n} \). More picturesquely, \( | 2^{A} | = 2^{| A |} \).
Why? Well, let’s count the number of subsets of size \( k \) for every number less than or equal to \( n \):
- For \( k = 0 \): There is exactly one subset of \( A \) with zero elements, and that is the empty set
- For \( k = 1 \): There are \( n \) subsets with one element each
- For \( k = 2\): There are \( \binom{n}{2} \) subsets with two elements (where I am using one of many different notations to represent combinations. More on them elsewhere)
… and so on.
When we add them all up, we somehow magically (a.k.a. the Binomial Theorem!) get \( 2^n \)! Quite magical (not).
This is all very cute, of course, but what happens when \( A \) is not finite? What happens when we take, say \( \mathbb{N} \), as our set? What, in other words, is \( 2^{\mathbb{N}} \)?
We know that for any finite number \( n \), \( 2^n > n \). One of the neat things about Cantor’s diagonalization theorem is that it tells us this is true for any \( n \)—including infinite \( n \)! How?
We recall that we had earlier defined “counting” as establishing a bijective correspondence between two sets. This is how we proved that \( \mathbb{N} \) and \( 2 \mathbb{N} \) were, in fact, the same “size”. So to prove that \( A \) and \( \mathcal{P}(A) \) are not, in fact, the same size, we must show that no correspondence between them can be bijective. And if we can show that no matter what correspondence we take, there is always some element of \( \mathcal{P}(A) \) which gets left out even while every single element of \( A \) is accounted for, then we can prove that \( \mathcal{P}(A) \) is, in fact, bigger than \( A \).
We begin by noting that \( \mathcal{P}(A) \) is at least as large as \( A \). This is true because there is a bijection between \( A \) and the elements of \( \mathcal{P}(A) \) that are all single-element subsets of \( A \). (In symbols, the collection \( \{ a, b, c \} \) has a bijective correspondence with \( \{ \{ a \}, \{ b \}, \{ c \} \} \).) Now consider any function f that maps an element of \( A \) to an element of \( \mathcal{P}(A) \). We need to show that there is at least one element of \( \mathcal{P}(A) \) that cannot be in \( A \) (and let us constantly remind ourselves that an element of \( \mathcal{P}(A) \) is a subset of \( A \) ). How can we find such an element of \( \mathcal{P}(A) \) that does not depend on the particular definition of a correspondence \( f \)?
This is the step in the diagonalization process analogous to picking one digit from every number on the list and modifying it in order to create a new number. But how do we do that with sets? We note that the correspondence \( f \) connects every element \( x \in A\) with an element \( f(x) \in \mathcal{P}(A) \) ; i.e., with a subset of \( A \). Depending on how we define our correspondence, it may be the case that \( x \) is actually an element of the subset that it maps to; or it may be the case that \( x \) is not an element of the subset it maps to. Clever devils that we are, we pick our element of \( \mathcal{P}(A) \) to be the set \( B \) of all those elements of \( A \) which are not elements of the subset they correspond to. (This is like changing the digit we pick so we know our new number differs from every existing number in at least one place.) In symbols, \( B = \{ x \in A | x \notin f(x) \} \).
How do we know that there is no element of \( A \) that can be mapped to \( B \) by \( f \) Why, by the very definition of \( B \) itself! Suppose, for the sake of contradiction, that there does exist a \( y \in A \) such that \( f(y) = B \). By the definition of \( B \), this must mean that \( y \notin B \). But then by the definition of \( B \), we have \( y \in B \)! This is a clear contradiction, which shows that there simply cannot be any such \( y \). In other words, \( \mathcal{P}(A) \) is always larger than \( A \)—regardless of whether \( A \) has finitely many elements or not!
Thus, \( 2^{\mathbb{N}} \) must needs be greater than \( \mathbb{N} \) in size. But we also know, through a different diagonalization proof, that \( \mathbb{R} \) is greater than \( \mathbb{N} \) in size. Is it in fact true that \( \mathbb{R} = 2^{\mathbb{N}} \)? As it turns out, this question is better answered by taking \( \mathbb{Q} \) rather than \( \mathbb{N} \) (but as we saw earlier, these two sets are the same size, and so it doesn’t really matter). And the answer, which I will not go into in any detail, is yes. When we construct real numbers by the method of Dedekind cuts, we do in fact map every real number to a subset of \( \mathbb{Q} \). The converse can also be shown to be true.
But regardless, the power set argument shows that there have to be infinities greater than the uncountable set of the real numbers. The power set of the real numbers, \( \mathcal{P}(\mathbb{R}) \), is strictly larger than \( \mathbb{R} \), and its own power set \( \mathcal{P}(\mathcal{P}(\mathbb{R})) = 2^{2^{\mathbb{R}}}\) is larger still, and so on, ad infinitum! (A more concrete example of a set that is of cardinality \( 2^{\mathbb{R}} \) is the set of all functions from \( \mathbb{R} \) to \( \mathbb{R} \).)
Nice again!
ReplyDeletethe cardinality of the power set of A is 2ⁿ. ... Quite magical (not).
Yes, more direct than the binomial theorem is the counting proof: to make a subset of A, for each element of A you have two choices (whether to include it in the subset or not), so the number of subsets you can make is 2×2×... = 2ⁿ.
I await your sure-to-be-interesting post on your second line of inquiry too. :-)