Friday, September 16, 2011

Cantor's proof

As we are close to the subject, and because it is beautiful and remarkable, here is Cantor's proof of the uncountability of the reals*.

1. For all s, for some n, s = f(n).
2. f(n) = {m: x not in f(m)} (from 1).
3. If n in f(n) then n not in f(n), and if n not in f(n) then n in f(n) (from 2).
4. Contradiction.

It is beautiful because it is short, and all short things are beautiful.  It is remarkable because the scholastic philosophers never produced anything close to it.  In nearly all matters of logic, the culture of the renaissance and early modern period never approached the heights that logic attained in the early 14th century.  But not this.
 
It needs a little explanation, of course.  The first statement follows from the claim that sets of natural numbers are 'countable', i.e. to do this, to any set s of natural numbers, there must correspond some natural number n.
 
The second follows from the first.  There must be some natural number corresponding to the set of natural numbers that are not in the set corresponding to them.  The third draws a simple conclusion from that.  The fourth states that the third is a contradiction.  We can therefore infer that one of the first two statements is false.
 
To forestall impudent hairsplitters, I should add that (as far as I know) Cantor never gave a proof in precisely that form.  His actual proof is in the Logic Museum, with my English translation. 
 
To any other quibblers, I reply that I am not a mathematician.

*Modified this evening o/a of Belette's complaint of sloppiness.

12 comments:

William M. Connolley said...

I'm not familiar with this version, and it took me quite a while to decode your compressed version. And I did set theory as part of my maths degree, 30 years ago. I humbly suggest that most of your readers are going to be lost.

1 is std: if the reals are countable, there must be a function mapping from the integers to the reals; you call it f.

However, you haven't told us what set the individual s are coming from. I think you mean the set of all subsets of the integers. That isn't the reals, nor is it known to have the same cardinality (http://en.wikipedia.org/wiki/Continuum_hypothesis).

2 I can't parse as you've written it. What is "fx"? Did you mean f(x)? But what is "x"? One of the reals? It can't be, because f is only defined on the integers. OK, so its an integer (would be more obvious if you'd called it n). Ah, in this case this is the power set version of the diagonal argument, I think.

Your proof can't be directly on the reals, though, because you haven't used any properties of the reals. Instead, you're proving that a set isn't of-the-same-cardinality as its power set? That isn't quite the same thing as the uncountability of the reals.

Notice that nothing in your proof requires that n (and the elements of the various s) need to be drawn from the integers or indeed an infinite set.

William M. Connolley said...

Rats. I was wrong to say:

> That isn't the reals, nor is it known to have the same cardinality (http://en.wikipedia.org/wiki/Continuum_hypothesis).

As http://en.wikipedia.org/wiki/Cardinality_of_the_real_numbers will say.

So card(2^N) = card(R). But 2^N is not = R, at least not directly.

Edward Ockham said...

>>Did you mean f(x)? But what is "x"? One of the reals?

I tidied it up - I am a bit lazy about brackets. And altered 'x' to a more integer-like variable.

>>I think you mean the set of all subsets of the integers.

>>Your proof can't be directly on the reals, though, because you haven't used any properties of the reals.

A property of the reals is that they can be represented as a decimal expansion, i.e. a set of naturals. I admit I skipped this bit of the explanation.

Edward Ockham said...

Even in Wikipedia it says this http://en.wikipedia.org/wiki/Power_set

"Cantor's theorem shows that the power set of a countably infinite set is uncountably infinite. For example, the power set of the set of natural numbers can be put in a one-to-one correspondence with the set of real numbers (see cardinality of the continuum)."

So it's kind of obvious.

Edward Ockham said...

>>I'm not familiar with this version

It was called 'Cantors Theorem' by Ernst Zermelo in 1908. It is much more elegant and beautiful than the diagonal proof.

William M. Connolley said...

> the power set of the set of natural numbers can be put in a one-to-one correspondence with the set of real numbers

I agree. But it isn't obvious; it requires another proof to show it.

> I tidied it up

Thanks. That make things clearer. But I still think in your quest for shortness you have omitted vital supporting details. To make sense, the proof needs to say that s <- S (I'm using <- for "member of"; S is the power set of N; and n<- N). You lose elegance if you insist that N is the natural numbers; the elegant version works for any N.

David Brightly said...

Yes, it is beautiful. A quibble though, logical not mathematical. 'n' occurs free in (2). Shouldn't it read

(2*) for some n f(n) = {m: m not in f(m)} (from 1).

But then we seem to be 'exporting' the *variable* n into line (3). A mathematician would prefix (3) with 'For this n, ' and would see the whole as a respectable argument. But you chide me for this here. What's the logician's take on this? Presumably there is an ∃-elimination rule of some sort, but I'm hazy as to how it goes, and for once WP isn't helping.

Edward Ockham said...

>>Shouldn't it read

Yes. The point you make further on is very funny.

The point you are making presumably is that a tidied up version would involve changing the exported free variable into a constant, then proving that the constant could not refer to anything. Whereas I have argued that, strictly speaking, this is illegitimate.

William M. Connolley said...

What did Galileo know about infinity?

David Brightly said...

Precisely.

Edward Ockham said...

>>What did Galileo know about infinity?

Ah now I see what you are on about. The problem of anachronism. Good luck

William M. Connolley said...

It is better now.