Our goal is to show that there exist infinite sets that are not countable. In other words, there is no one-to-one, onto mapping between the two sets. Since there can be no infinite set smaller than the natural numbers, we are looking at sets larger than the natural numbers, i.e. no function from the naturals to the set can be onto, or no function from the set to the natural numbers can be one-to-one.

Phrased differently, the first statement implies that a function with the domain of the natural numbers and codomain of an uncountable set must have an uncountable subset in the codomain which is not part of the range. Even if the function is one-to-one, so every point in the domain maps to a distinct point in the range, the function can't hit every point in the codomain, and in fact must miss uncountably many points. (If the points that are not in the range are countable, then the uncountable set could be constructed as the union of two countable sets, and would therefore be countable.)

The second statement implies that any function with the domain of an uncountable set and codomain of the natural numbers must match an uncountable set to at least one natural number, even if the range is equal to the codomain. This is more or less the same thing as the first statement read backward. If the uncountable set is the domain of the function, every point in that set must go to one of the natural numbers. If the function is one-to-one, it must run out of natural numbers before it runs out of points in the uncountable set. Furthermore, even if it matches a countable set to every natural number, that can't include all of the points in the uncountable set, because then the set could be written as a union of countable sets, and would therefore be countable.

In order to show that uncountable sets exist, we need to develop a couple of other concepts first. The first concept is the power set, which I've mentioned briefly before. We've looked at various subsets of sets. In particular, when we looked at set functions, the function operates on any subset of the set. The collection of all possible subsets of a set is called a power set.

Let's look at a really simple example. Start with a set with three points, call them 1, 2, and 3. If we call the set A, then A={1,2,3}. The possible subsets of A include each point individually, or {1}, {2}, and {3}. The subsets also include each pair of points, or {1,2}, {1,3}, and {2,3}. Finally, the subsets include the null set, ∅, and A itself. The power set of A, written ℘(A), is a set of sets with 8 members, each member of which is a set. ℘(A)={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.

The power set is obviously bigger than the original set in this case. For any finite set of size n, the size of the power set is 2^{n}. I could formally prove it with induction, but I'll skip the proof for now. If I decide I have a good reason for it, I might come back to it later.

This has an implication, which I mentioned a couple of posts ago, about unions of finite sets. Start with a finite set of points. List every possible distinct subset of points. This is the power set of the original set, and it is finite. Therefore, as I previously stated, if you have a countable collection of distinct sets, even if each set is finite, the union of all the sets must have a countable number of points. If the union was finite, then the power set of the points would be finite, and we couldn't have started from a countable collection of distinct sets. (To avoid confusion, I will restate that the word countable implies infinite.)

The cardinality of the power set of any finite set is greater than the cardinality of the set itself. The question is, what happens with countable sets? Our previous experience with countable sets might give the expectation that the power set is also countable. On the other hand, I started this post the way I did for a reason.

Unfortunately, I'm out of time. See you next time.