Infinite Musings
What do you mean when you use the word “infinity”? I am going to show you, using a few facts about functions and sets that you should have learned during your K-12 education, that there are two infinite sets that are not the same size. In fact, we’ll do better than that: we’ll show that there are an infinite number of infinite sets, no two of which are the same size!
First, though, we have to agree on what we mean when we say that two sets are the same size. For finite sets, that is easy: just count the number of elements in the two sets and compare the numbers. Either they are the same, or they are not. But if we are comparing sets, some of which may be finite and some of which may be infinite, we need a different approach.
The standard mathematical solution to this problem is to pair up elements of the two sets to be compared. Let us say we have two sets named S and T. If each element of S is paired with exactly one element of T, and every element of T can be found in one of these pairings, then we say that the two sets are cardinally equal: they have the same size.
Here’s a little terminology you may recall from K-12 mathematics. A function from S to T that maps every element of S to a unique element of T is called a 1-to-1 or injective function. A function from S to T where every element of T is the result of applying the function to some element of S is called an onto or surjective function. A function that does both is called 1-to-1 and onto, or bijective. In short, two sets S and T are the same size if there exists some bijective function from S to T. (Why not from T to S, you may ask? Every bijective function has an inverse function, that does the pairing in the opposite way. So it doesn’t matter. If you find a bijective function going one way, you automatically have a bijective function going the other way, too.)
Many of the infinite sets you can think of off the top of your head are thei same size. Here is an example: let S be the set of integers \(\left\{ ..., -2, -1, 0, 1, 2, ... \right\}\), and let T be the set of natural numbers \(\left\{1, 2, 3, ... \right\}\). Even though it looks like S is “bigger”, because it is infinite in both directions, these two sets are actually the same size. To prove that, I have to give you a way of pairing up elements from the two sets so that nothing is left out. Here is one way to do that:
| Element of T | Element of S |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | -1 |
| 3 | 2 |
| 4 | -2 |
| 5 | 3 |
| 6 | -3 |
| … | … |
See how that works? We are “zigzagging” back and forth to cover all of the elements of S. We can even write this as a function from T to S:
\[f(x)=\cases{-x/2,&if $x$ is even;\cr(x+1)/2,&if $x$ is odd.\cr}\]or we can write it as a function from S to T:
\[g(y)=\cases{2y-1,&if $y$ is positive;\cr-2y&otherwise.\cr}\]The functions f and g are both bijective, and are inverses of each other. That means that, for any integer i, \(f(g(i)) = i\), and for any natural number n, \(g(f(n)) = n\). Try a few numbers to convince yourself that is true.
Do you recall the notion of a power set? Given a set S, the power set P(S) is the set of all subsets of S. So, for example, if \(S = \left\{0, 1, 2\right\}\), then:
\[P(S) = \left\{ \left\{\right\}, \left\{0\right\}, \left\{1\right\}, \left\{2\right\}, \left\{0,1\right\}, \left\{0,2\right\}, \left\{1,2\right\}, \left\{0,1,2\right\} \right\}\]It is called the power set because, for finite sets, the size of the power set is 2 to the power of the size of the original set. In our example above, the set S has 3 elements, and P(S) has 23 = 8 elements.
Does the power set of an infinite set have the same size as the original set? Let’s suppose that that is the case. Let’s pick some arbitrary infinite set and call it A to distinguish it from all of our example sets above. If A and P(A) are the same size, then there is some bijective function h from A to P(A). Since everything is paired up, I can pick any element of P(A) (i.e., any subset of A), and there is some element of A paired with it.
Consider the set of all elements a of A such that a is not an element of h(a). That is, we’re making the set N (for “not in its paired element”) like this:
\[N=\left\{ a \mid a \notin h(a) \right\}\]N may be the empty set. N may be equal to A. It may be somewhere in between. In any case, N is a subset of A, and therefore it is an element of P(A). This means that for some element b of A, \(h(b) = N\).
Is b in N? We said that N is the set of all elements that are not in their pairs, so no: b cannot be in N. But then b is not in the element it is paired with, which is the definition of N, so b must be in N. But wait, …
We have found a contradiction: b must be in N and b must not be in N, simultaneously. We therefore conclude that b does not, in fact, exist. Since b does not exist, nothing is paired with N, so h is not a bijection, which means that A and P(A) are not the same size. Notice that we never assumed that A is finite. This proof works for both finite and infinite sets. So now we can pick two infinite sets that are not the same size:
- I = the set of integers
- P(I) = the power set of the set of integers
But why stop there? We can keep going for as long as we like:
- P(P(I)) = the power set of the power set of the set of integers
- P(P(P(I))) = the power set of the power set of the power set of the set of integers
- …
There you go: an infinite number of infinite sets, no two of which are the same size. Each one is “bigger” than the one before it in the list (although we didn’t prove this). You may now leave the classroom to go boggle for awhile.