While I’ve been writing about the Surreal numbers lately, it reminded me of some of the fun of Set theory. As a result, I’ve been going back to look at some old books. Since I’ve been enjoying it, I thought you folks would as well.
Set theory, along with its cousin, first order predicate logic, is pretty much the
foundation of nearly all modern math. You can construct math from a lot of
different foundations, but axiomatic set theory is currently pretty much the dominant approach. (Although Topoi seem to be making some headway…)
There’s a reason for that. Set theory starts with some of the simplest ideas, and extends in a reasonably straightforward way to encompass the most astonishingly complicated one. It’s truly remarkable in that – none of the competitors to set theory
as a foundation can approach the intuitive simplicity of set theory.
So I’m going to write a bit about set theory as I explore my old books. And I thought that a good place to start was Cantor’s diagonalization. Cantor is the inventor of set theory, and the diagonalization is an example of one of the first major results that Cantor published. It’s also a good excuse for talking a little bit about where set theory came from, which is not what most people expect. Set theory was originally created as a tool for talking about the relative sizes of different infinities.
Almost anyone who went to school in the last 40 years has had some exposure to sets, so we tend to think of them in terms of foundations. It surprises most people that sets were not proposed as a foundation at all: in fact, set theory started as
an outgrowth of number theory! Back in the 19th century, Cantor was doing work on
number theory and algebra, and invented what grew into set theory as a tool for comparing
the sizes of various sets of numbers. The original motivation behind the ideas that ended up growing into set theory was Cantors recognition of the fact that there’s a difference between the size of the set of rational numbers, and the size of the set of real numbers. They’re both infinite – but they’re not the same!
Cantor’s original idea was to abstract away the details of numbers – order, structure, etc., and just look at them as collections of objects – that is, as sets. Then, if you can create a one-to-one correspondence between two sets of numbers, then those sets must be the same size. But when you look at the set of real numbers and the set of rational numbers, there’s no way to create a one-to-one mapping: in fact, you can easily prove that any one-to-one mapping between the rationals and the reals will necessarily
omit some of the real numbers.
It’s worth taking the time to repeat that basic proof here. I’m going to use a slightly simplified version, which shows that you can’t map between the natural numbers and the reals between 0 and 1; since it’s easy to show that there’s a one-to-one mapping between the natural numbers and the rationals; and that there’s a one-to-one mapping between the set of all reals between 0 and 1 and the set of all reals, it means the same thing, but there are less tricks involved.
It’s a basic proof by contradiction. Suppose that we can create a one-to-one correspondence between the natural numbers and the reals between 0 and 1. What that would mean is that there would be a total one-to-one onto function R from the natural numbers to the reals. So we could create a complete list of all of the real numbers: R(0), R(1), R(2), …
If we could do that, then we could also create another function, D (for digit), where D(x,y)=the yth digit of the binary expansion of R(x). So D is effectively a table where every row is a real number, and every column is a digit position in the binary expansion of a real number. D(x,3) is the third digit of the binary expansion of x. So, for example, if x=3/8, then the binary expansion of x is 0.011. So D(3/8,1)=0, D(3/8,2)=1, D(3/8,3)=1, D(3/8,4)=0, …
Now, here comes the nifty part. Take the table for D, and start walking down the diagonal. So we’re going to go down the table looking at D(1,1), D(2,2), D(3,3), and so on. And as we walk down that diagonal, we’re going to write down digits. For D(0,0), the first digit, we’ll write 0 if D(0,0)=1, and 1 if D(0,0)=0. We’ll do the same thing for each digit. For the ith digit, if D(i,i)=0, we’ll write 1, and if D(i,i)=1, we’ll write 0.
The result that we get is a series of binary digits – that is, a binary expansion of some number. Let’s call that number T. T is different from every row in D in at least one digit – for the ith row, T is different at digit i. So there’s no x where R(x)=T. But T is clearly a real number between 0 and 1. So the mapping can’t
possible work. And since we didn’t specify the structure of the mapping – we just assumed that there was one, that means that there’s no possible mapping that will work: this construction will always create a counterexample showing that the mapping is incomplete.
So the set of all real numbers between 0 and 1 is strictly larger than the set of all natural numbers. And by extension, the set of all real numbers is strictly larger than the set of all rational numbers.
That argument is called Cantor’s diagonalization. And it’s pretty much the argument
that put set theory on the map.