wherein is detailed Matt's experiences as he tries to figure out what to do with his life. Right now, that means lots of thinking about math.

Monday, March 12, 2012

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 IA, which indicates whether each member of Ω is in A. Pick any point in Ω and call it ω. If ω is in A, then IA(ω)=1. If ω is not in A, then IA(ω)=0. In our example, IA(a)=0, IA(b)=1, and IA(c)=0. Of course, if we were looking at a different subset of Ω, we would get different values for the function.

IA is called an indicator function, because for each point in Ω, it indicates whether that point is in A. IA 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 YX 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, IA, 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 fn in {0,1}. We aren't trying to specify the function, just asserting that it exists. Now, fn has the natural numbers as its domain. So n is in the domain of fn, and fn(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)=fn(n).

If we were to construct a table, with values of fn corresponding to rows and values of n corresponding to columns, we could look up fa(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)=fn(n) for all n, so anti-g(n)≠fn(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 fx(n)=anti-g(n) for all n.

We have shown that fn(n)≠anti-g(n) for all n. Therefore, there is no x such that fx(n)=anti-g(n) for all n, because fx(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 (x1, x2,…,xi,…), set xi=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.

FAQ

What does "rolls a hoover" mean, anyway?

"Roll a hoover" was coined by Christopher Locke, aka RageBoy (not worksafe). He enumerated some Hooverian Principles, but that might not be too helpful. My interpretation is that rolling a hoover means doing something that you know is stupid without any clear sense of what the outcome will be, just to see what will happen. In my case, I quit my job in an uncertain economy to try to start a business. I'm still not sure how that will work out.