The goal is to construct an uncountable set, that is, an infinite set that does not have a one-to-one, onto mapping from the natural numbers. Our first tool toward this goal is the power set. A power set is the set of all possible subsets of a given set. It's clear that the cardinality of a power set of a finite set is larger than the cardinality of the finite set. Given our experience with countable sets, whether the cardinality of a power set of a countable set could believably be the same as the cardinality of the countable set is unclear.

Our second tool is indicator functions. Here's the idea. Start with a set Ω. For the sake of example, let's say that Ω has three members, and Ω={a,b,c}. Now take some subset of Ω, call it A. Again, for example, let's say that A={b}. Now, we are going to build a function, called I_{A}, which indicates whether each member of Ω is in A. Pick any point in Ω and call it ω. If ω is in A, then I_{A}(ω)=1. If ω is not in A, then I_{A}(ω)=0. In our example, I_{A}(a)=0, I_{A}(b)=1, and I_{A}(c)=0. Of course, if we were looking at a different subset of Ω, we would get different values for the function.

I_{A} is called an indicator function, because for each point in Ω, it indicates whether that point is in A. I_{A} is a particular mapping from the set Ω to the set {0,1}. We can easily imagine the set of all possible mappings from Ω to the set {0,1}, and give the set of mappings the notation {0,1}^{Ω}. We can generalize this notation and say that if f is a potential function mapping from the set X to the set Y, then the set of all possible functions from X to Y is written Y^{X} and is called set exponentiation.

Looking specifically at {0,1}^{Ω}, we can see that this set of functions is directly related to ℘(Ω), the power set of Ω. Take a particular function f which is a member of {0,1}^{Ω}. Now, for that function, take the set in Ω of all values ω such that f(ω)=1. Reusing terminology from previously, find the preimage of {1} in Ω. Every subset of Ω, which is a member of ℘(Ω), has a corresponding function f in {0,1}^{Ω}, and vice versa. Each function f in {0,1}^{Ω} is an indicator function, I_{A}, for some subset A of Ω.

Now we're ready to prove that the power set of the natural numbers is not countable. We are going to use the fact that ℘(ℕ) has a one-to-one correspondence with {0,1}^{ℕ}, and show that {0,1}^{ℕ} is not countable. And, following Cantor's diagonalization proof, we're going to do it by contradiction.

Assume that there exists a one-to-one, onto function that maps from ℕ to {0,1}^{ℕ}. For every natural number n in ℕ, there is a corresponding function f_{n} in {0,1}^{ℕ}. We aren't trying to specify the function, just asserting that it exists. Now, f_{n} has the natural numbers as its domain. So n is in the domain of f_{n}, and f_{n}(n) is valid, and must have the value of either 0 or 1. This is true for every n in the natural numbers, so we can construct a new function g, such that g(n)=f_{n}(n).

If we were to construct a table, with values of f_{n} corresponding to rows and values of n corresponding to columns, we could look up f_{a}(b) by looking up the value, either 0 or 1, in row a and column b of the table. The function g gets its values by running down the diagonal of the table. Importantly, g has as its domain the natural numbers, and has as its range the values {0,1}, so g is itself a member of {0,1}^{ℕ}.

Now for the twist. Let's generate an anti-g. The rule is simple. If for some value n, g(n)=1, then anti-g(n)=0. If g(n)=0, then anti-g(n)=1. Anti-g is also a member of {0,1}^{ℕ}, since its domain is again the natural numbers, and its range is {0,1}. Therefore, anti-g must also be in our table of functions. And here is the contradiction. For all n, anti-g(n)≠g(n). But g(n)=f_{n}(n) for all n, so anti-g(n)≠f_{n}(n) for all n. But since anti-g is in {0,1}^{ℕ}, and there is a one-to-one, onto mapping from ℕ to {0,1}^{ℕ}, there must be some x such that f_{x}(n)=anti-g(n) for all n.

We have shown that f_{n}(n)≠anti-g(n) for all n. Therefore, there is no x such that f_{x}(n)=anti-g(n) for all n, because f_{x}(x) can never equal anti-g(x). The only conclusion is that it is not possible to construct a one-to-one, onto mapping from ℕ to {0,1}^{ℕ}, and therefore that the cardinality of ℘(ℕ) is greater than the cardinality of ℕ. ℘(ℕ) is not countable.

A couple of points: This argument works for any set. The table was a useful visual reference, but we did not depend on its existence for the proof. For any set Ω, we can define {0,1}^{Ω}. Then our proposed mapping from Ω to {0,1}^{Ω} has a function f_{ω} for any point ω in Ω, and anti-g(ω)≠f_{ω}(ω) for all ω. (Okay, there were a lot of symbols in that last sentence. But there are a lot of symbols in this whole post. I apologize if your eyes are glazing over.)

In particular, this means that ℘(℘(ℕ)) has greater cardinality than ℘(ℕ), and so forth. So we need notation to represent differing cardinalities of different infinite sets. The cardinality of ℕ, the natural numbers, is ℵ_{0}. (This is the cardinality of the integers, the rational numbers, ordered pairs of natural numbers, etc., of course.) The cardinality of the power set of the natural numbers, ℘(ℕ), is ℵ_{1}. The cardinality of ℘(℘(ℕ)) is ℵ_{2}. And so on. Note that the subscripts are whole numbers. I don't know if ℵ_{∞}, or maybe ℵ_{ℵ0}, is a meaningful concept, or what it would mean. That's outside the scope of what I'm currently studying.

My second point: over the weekend, I raised the question of the size of an infinite dimensional coordinate space of natural numbers. Borrowing the current notation, what's the cardinality of a natural ℵ_{0}-space? Well, 0 isn't a natural number, but {0,1}^{ℕ} is obviously the same size as {1,2}^{ℕ}. Take some function f(n) in {1,2}^{ℕ}. Then in the infinite tuple (x_{1}, x_{2},…,x_{i},…), set x_{i}=f(i) for every i. It's clear that every function corresponds to a point in the infinite dimensional space, so since this subset of the space is uncountable, the space as a whole is uncountable. The follow up question is whether the space is the same size as ℘(ℕ), or if it is in fact larger. Proving it one way or the other isn't obvious off the top of my head, so I'll have to give it more thought.