8:45 PM

We've shown that the natural numbers, integers, and rational numbers, along with a bunch of other things, all have the same cardinality. There's one set of numbers that we conspicuously haven't looked at: the real numbers. I don't want to show a formal proof about the cardinality of the reals today, but I expect to in the future. Instead, I want to do some informal thinking about the topic without necessarily coming to any conclusions.

This approach is in keeping with the lecture notes, which defers to the textbook, and the textbook, which implies that we could construct a proof based on indicator sets and Cantor diagonalization, but pushes off a full proof to a later topic, where it will use a different approach.

So, let's start with the obvious. By definition, the rational numbers are a subset of the real numbers. The rational numbers have holes (the standard example being √2) and the real numbers are defined as the set of numbers which fills those holes. This implies that the set of real numbers could be larger than the set of rational numbers. However, we know that the natural numbers are a subset of the rational numbers, and yet the set of rational numbers and the set of natural numbers are the same size. By now, we have enough experience with infinite sets to not trust our first intuitions.

The real numbers can be constructed from sets of rational numbers. Each set is called a Dedekind cut, and each set corresponds to a particular real number. I haven't discussed Dedekind cuts previously, but as we become more comfortable with infinite sets it may make sense to look at them in detail. The important thing for our purposes is that each set consists of all the rational numbers less than a particular real number. Note that this is strictly less than, so that the set which corresponds to the real number 1/2 includes all rational numbers less than 1/2. It does not include 1/2 even though 1/2 is a rational number.

My first thought was that, well then, every set has a greatest member, and so really, there should be a one-to-one relationship from each real number to the greatest member of that set. As usual, this thinking is completely wrong. In an earlier post, I looked at the proof that there is always a rational number between any two real numbers. The signficance here is that for each set, if you claim a particular number as the greatest rational number in that set, you can always find a rational number between that number and the real number the set corresponds to. The number you have found is in the set and is greater than the supposed greatest number, so the only conclusion is that each set has no greatest member. (Every number in the set for 1/2 is less than 1/2, but there is no greatest rational number less than 1/2.)

So we can't establish a relationship between the greatest member of each set and the corresponding real number, which is just as well, because if we could, the sets wouldn't be very good for filling the holes in the rational numbers anyway.

What else can we do with these sets? Well, talking about sets of rational numbers reminds me of power sets, which we just used to prove that uncountable infinite sets exist. A power set is the collection of all possible subsets of a set, and Dedekind cuts are subsets of the rational numbers. Unfortunately, Dedekind cuts do not include all possible subsets of the rational numbers, so the power set of the rational numbers is not equal to the set of all Dedekind cuts.

You can kick around some other power sets, like the power set of all natural numbers, but I don't see an obvious way to map a power set to the set of all Dedekind cuts. (I'm open to the possibility that there's a non-obvious way. After all, I don't think that the diagonalization that shows that ordered pairs of natural numbers are countable is obvious. But if there is a non-obvious way, I don't know what it is.)

You could argue that maybe you don't need all of the subsets of the rational numbers. Maybe Cantor's diagonalization would work on just the Dedekind cuts. This might be worth exploring, but in order for it to work, the set generated by the anti-g function would have to be a Dedekind cut. Unless you can prove that any set generated by any potential ordering must be a Dedekind cut, I don't think it works. If the set generated by anti-g isn't a Dedekind cut, there's no problem. The set was designed to not be in the list of all Dedekind cuts, it's not a Dedekind cut, and it's not on the list.

If it's not clear, I'm just throwing out ideas here. If I'm missing anything, feel free to jump in and leave a comment.

There is one statement we have to work with, which you can develop if you're interested. This comes from the textbook. Consider the output from the indicator functions of subsets of the natural numbers. Compare this to binary representations of real numbers.

I'm stopping there. I'm not drawing any conclusions, just exploring ways of thinking about the question. Next time I'm moving on to new and different topics.

4 comments