Does Cantor’s Diagonalization Proof Cheat? | Hacker News Reader

Does Cantor’s Diagonalization Proof Cheat?

rjlipton.wordpress.com

13 pointsbdr33 comments

Good Math, Bad Math has a series of posts about attempts to disprove the uncountability of reals:

http://scienceblogs.com/goodmath/bad_math/cantor_crankery/

Especially frustrating is the credibility Knol can provide to crackpots like this.

Where I part ways with mathematicians is the intuition we should ascribe to Cantor's argument. They say that "almost all" real numbers are irrational. What Cantor's argument says is that "at least one" is irrational.

I know the arguments about measure and probability and such, but, there is also the fact that for every two real numbers, there is an infinity of rational numbers in between! So that makes me (personally, not mathematically) not like the "almost all" intuition, instead of an intuition of there always being at least one more, in a particularly slippery way.

Ah, but Cantor's proof doesn't just prove that there's "at least one", it proves that there are infinite irrationals.

It's just the way this proof is often presented that leads people to believe that it only proves that at least one is irrational; but once you accept that there is one irrational number, you can "index" it and add it to your denumerable list (pretend it's rational, say) and then run the diagonlization argument again, yielding yet another irrational number. Do this ad infinitum. Or, rather, stop: this will not halt ;)

Other proofs prove that the rationals are not equinumerous to the reals, but that there is a one-to-one function from the rationals to the reals… but that's another story.

(EDIT: as I'm getting a lot of hate and downvotes for this, I suppose I could delete the comment. It was intended to try to clear matters up for the parent of this thread. It wasn't intended as a deep explanation of anything at all. Forgive my triviality.)

If you said that right, my mind's blown. Wouldn't that prove the reals are countable?

Which part? One-to-one means that there's an unique element in the range for every element in the domain. That doesn't mean there are the same number of elements.

(EDIT: typo strike second range, replace with domain!)

(EDIT2: To reply to a reply below: it's absolutely trivial to provide the function: to prove it's true wouldn't be, at least set theoretically, which is how I'd do it.)

So is the proof you're referring to actually asserting anything that isn't trivial? The identity function is one-to-one from the rationals to the reals.

Could you provide a link to the argument that there is a one-to-one function from the rationals to the reals or at least provide more details about what you mean.

Thanks.

Absolutely:

Say there's a function ƒ: Q -> R (Q: rationals, R: reals).

ƒ(x) = x where x∈Q and x∈R.

It's a trivial function, but clearly every rational number is also a real. I could bring it back down to set theory to prove it further, but I that should clear it up!

EDIT: One-to-one is not a bijection. It is an injection. A one-to-one correspondence is a bijection. Look at Wikipedia, for instance.

It doesn't just prove that there's infinitely many irrationals -- that is trivially easy to prove. For instance we know pi is irrational, therefore 2pi, 3pi, 4pi, 5pi,... etc are all irrational as well.

Cantor's proof proves that there's no one-to-one correspondence between reals and integers (whereas there is a one-to-one correspondence between integers and rationals), and therefore the infinite set of reals is "bigger" than the infinite set of rationals.

That there is an infinite number of irrationals should follow as a trivial consequence of this. (Left as an exercise for the reader...)

I understand this: I was attempting to show, intuitively, how his theory could demonstrate that there is more than one irrational number.

Apologies if I wasn't clear: this was something that popped into my head to help clear this up!

What's also somewhat interesting is there's a non-trivial countable set of irrational numbers: those formed by taking the roots of polynomials with raitonal coefficients. http://en.wikipedia.org/wiki/Algebraic_number has the low-down, but it's definitely neat that square roots, etc. are still a countable set.

I think ihodes is using "one-to-one" to mean injective. Sometimes "one-to-one" is used to mean bijective.

This confusion is why the term "one-to-one" should never be used!

One-to-one correspondence is bijective. One-to-one is injective. Sorry for the confusion, but this is a standard definition, even if it's one you're not used to.

(EDIT: as you keep editing and replying, let me clarify: your confusion is not shared among informed others. Bijective and injective are wonderful terms, yes. One-to-one and one-to-one correspondence are equally informative and useful.)

OK, well it's fine to use whatever terminology you like if there are standard definitions, but I think terms including "one-to-one" are unnecessarily confusing, whereas "injective" and "bijective" are perfectly clear.

I have a degree in math, I know about Lesbegue measure and probability. My math knowledge is slightly more sophisticated than you give me credit for, if not much more!

What you're describing is, to me, the "slippery way" that there is always one more. Yes, one more than a countable set implies infinitely many more, clearly, because there will always be one more even after adding another (or a countable number.)

However... the point I'm attempting to articulate - which is not defined precisely and hence is not mathematical, is that almost all just doesn't work in my brain if there are an infinity of "countable" numbers between any two "uncountable" ones!

There are a countable number of countable numbers between any two uncountable ones.

But there are an uncountable number of uncountable numbers between any two countable ones.

This is not correct.

It says that for any countable collection of real numbers, there's another real number that doesn't occur in that collection. (Hence the collection of real numbers cannot be countable).

[You don't need Cantor to show that there are irrational real numbers. sqrt(2) is irrational, for example. These kinds of numbers are called algebraic, and there are still only countably many of them.]

[Edit: I corrected "transcendental" to "algebraic". Thanks to RiderOfGiraffes for the correction]

Er, what you have written is wrong. sqrt(2) is not transcendental, and there are uncountably many transcendentals, not countably many.

You may have meant algebraic. sqrt(2) is algebraic, and there are countably many of them.

Yes, I meant algebraic. Thanks for the correction. The transcendentals are the reals that are not algebraic.

Cantor's diagonalisation argument is usually presented as constructing just one number not in your contable list, but it can be seen to construct more.

Take your list of numbers as decimal expansions. In the first place use any of the digits not in the first number, then in the second place use any of the digits not in the second number, etc. That immediately gives you infinitely many numbers not in your list.

But we can do better.

In the second place put any digit not in the second place of the first number, then in the first place put any digit not in the first place of the second number. Similarly with 3rd and 4th, and so on.

But we're not done.

Take any permutation of your list and do it again.

In this way you can see that there isn't just one number missing, there really are lots and lots and lots and lots missing.

And there's more, but this isn't the place for that. I hope this is enough that you can see why most numbers aren't in any countable list.

What you're describing is the "slippery" part of my "slippery one more". Yes I know the arguments. What I don't have is trust that intuitive concepts like "almost all" fit! To me the real numbers are something quite alien. The fact that they are Well-Ordered is one weird part, as is the fact that for any two there is a countable infinity of rationals in between.

I just think that if I have "almost all" of the stuff, you shouldn't be able to have an infinite amount of stuff between every given two pieces of my stuff!

So I prefer another intuition. And I know mathematicians disagree with me and assume I don't understand the basic facts about cardinality, bijections, measure, etc. I do!

I know there are a ton of cranks who doubt Cantor's argument. Yes I've been to sci.math before! I like to think I'm not one of them so I'm careful to state I'm not talking within math itself but rather the about way that mathematicians describe an intuition about math.

The reals are not Well-Ordered under the usual ordering, and they arenot Well Ordered at all. Certainly if you create a Well Ordering of the reals then it's not the usual ordering.

And you are free to work with your own intuition, but it's very, very likely that your intuition will be inconsistent with other axioms that you accept to be true. Once you have worked with them enough there is nothing bizarre about every two reals having coutnably many rationals between them, and every two rationals having uncountably many reals between them.

  I just think that if I have "almost all" of the stuff,
  you shouldn't be able to have an infinite amount of
  stuff between every given two pieces of my stuff!

This strikes me as very strange. If the rationals (or algebraics) are countable, then "almost all" of the reals are not rationals. Why should it not be that between any two transcendentals (of which there are uncountably many) there are "a few" (by which I mean only countably many) rationals?

I think the point to make is that for centuries, perhaps millennia, people grappled unsuccessfully with the ideas of infinite cardinalities. Many, many mistakes were made, and finally there is now a coherent, consistent way of working with them. To say they don't match your intuition is simply to say that your intuition is at odds with the centuries of work done by people who devoted their lives to working on it.

In short, you are welcome to your intuitions, but I suspect they are hindering you substantially from understanding things better. You can develop better intuition by working with these ideas "properly." But that's harder than just saying "My intuition doesn't agree with what the mathematicians say."

> The reals are not Well-Ordered under the usual ordering, and they arenot Well Ordered at all. Certainly if you create a Well Ordering of the reals then it's not the usual ordering.

Again, you assume I don't have a basic math education! I do!! I know about choice and Zorn's and stuff like that! Obviously the usual ordering of the reals is not a well-ordering.

> intuition will be inconsistent with other axioms that you accept to be true.

Like?

> Why should it not be that between any two transcendentals (of which there are uncountably many) there are "a few" (by which I mean only countably many) rationals?

Your intuitive argument here strikes me as circular. Yes there are uncountable reals between two rationals, and countable rationals between two reals. But that only implies "almost all" if you accept that "uncountable" already means "almost all" a priori! Where does my intuition break down if I think of it as a "slippery little bit" more?

Please don't assume I don't have basic knowledge of undergrad pure math in your answer, as mathematicians always do.

OK, in short, I don't understand your position. It seems indistinguishable from someone who doesn't understand anything about the infinities, and then you assert that you have a degree in math.

OK. Let me quote you:

    Where I part ways with mathematicians is the intuition
    we should ascribe to Cantor's argument.  They say that
    "almost all" real numbers are irrational.

As you know, that claim does not arise from Cantor's argument at all, it comes from measure theory. Cantor's argument about the uncountability of the reals (or of the set of subsets of a countable set, or the fact that the power set is always strictly bigger) says nothing about "almost all."

If you want to talk about "almost all" then you have to go to measure theory.

Having said that, certainly if you color all the rationals red, and all the irrationals blue, then there are more blue than reds, and the amount by which it's more is a lot.

    What Cantor's argument says is that "at least one" is
    irrational.

No. Cantor's argument says that for every countable set of reals, at least one is missing. Cantor's argument actually says nothing about rationals or irrationals.

    I know the arguments about measure and probability and
    such,

OK - I'll take that as a true statement.

    ... there is also the fact that for every two real
    numbers, there is an infinity of rational numbers
    in between!

So? What do you think is the problem with that? Why does this cause you difficulty? In particular, it's only a small infinity. Between any two rationals there is a bigger infinity of irrationals.

Your problem seems to be that you are trying to visulaise this in terms of finite collections and finding inconsistencies/contradictions. It's like being confused that the set of even numbers is the same size as the set of integers, when it should be "half the size." It's pretty much the same type of confusion, but at the next level up.

    So that makes me (personally, not mathematically)
    not like the "almost all" intuition, instead of an
    intuition of there always being at least one more,
    in a particularly slippery way.

This doesn't make any sense to me - it communicates no knowledge or understanding of your position. You will need to expand it substantially before I can try to help you adjust your intuition to be more in tune with mainstream mathematics.

> If you want to talk about "almost all" then you have to go to measure theory.

From my understanding, "almost all" is somewhat imprecise and can mean many different things even in math, e.g. all but countably many, all but for a set with Lesbegue measure 0, with the precise meaning either stated explicitly or depending on the context. So if it's "almost all" by definition, that fine, that's your definition. That's math. That's why I stress, again, that I'm not talking about precise math.

I do feel that mathematicians tend to use "almost all" in the common sense though as well when talking about uncountable sets, where it isn't precise, and isn't well defined, and actually isn't entirely consistent with our usual intuition. That is where I disagree.

> Having said that, certainly if you color all the rationals red, and all the irrationals blue, then there are more blue than reds, and the amount by which it's more is a lot.

Again, circular argument! If I say the difference between uncountable and countable isn't "a lot", but actually more like "a little", it doesn't follow. One way of stating my proposed intuition would be that there is a big difference between finite and infinite, and a "slippery little" between countable and uncountable. (Where they nonetheless have some important theoretical distinctions, including the idea of measure.)

Against this intuition is probability (whatever choosing a real number at random actually means...) But for it is the idea of the symmetry between these infinities, that there is an infinity of one between the other and vice versa.

> Your problem seems to be that you are trying to visualise this in terms of finite collections and finding inconsistencies/contradictions.

Yes, when you start using imprecise terms like "almost all", you're talking about intuition, and our intuitions are of course based on finite sets.

I think your problem is that you think that one set of math facts (including probability, measure, lack of a bijection) that is sort of analogous to an intuition of finite sets, is the preferred viewpoint, over another set of math facts (infinity of rationals between reals) in shaping your intuition.

To your credit, all mathematicians seem to be on your side:)

I'm looking for the killer fact that destroys my intuition, but nobody has ever been able to give it to me beyond the standard undergrad stuff that everyone who knows anything about math knows.

I don't have time now to go over this in detail, but again, you're not communicating things to me clearly.

However,

    >> Having said that, certainly if you color all the
    >> rationals red, and all the irrationals blue, then
    >> there are more blue than reds, and the amount by
    >> which it's more is a lot.

    > Again, circular argument!

No, it's no argument, it's an attempt to give you the right intuition. It is what's true, and I'm trying to help you visualise it.

    >> Your problem seems to be that you are trying to
    >> visualise this in terms of finite collections and
    >> finding inconsistencies/contradictions.

    > Yes, when you start using imprecise terms like
    > "almost all", you're talking about intuition, and
    > our intuitions are of course based on finite sets.

Not when you've worked for sufficiently long with these things. As you work with them - not just learn the definitions and a few standard proofs - you start to gain an intuition for what's really going on. People are trying to help you gain that intuition by telling you these things, and you're simply rejecting it and arguing from your existing intuition.

    > I think your problem is that you think that one set
    > of math facts (including probability, measure, lack
    > of a bijection) that is sort of analogous to an
    > intuition of finite sets, is the preferred viewpoint,
    > over another set of math facts (infinity of rationals
    > between reals) in shaping your intuition.

    > To your credit, all mathematicians seem to be on
    > your side:)

My intuition isn't just based on a few facts, it's based on working with these things for years, and the intuition developed.

And the cardinality of the reals isn't just "a bit bigger". Cantor's standard proof may have left you with that feeling, but go back to the proof I gave earlier. Start with a countable collection of reals. The standard diagonal argument gives you one that's missing. Now look at just how many ways you can generate new reals from that one list. You can take the first from the second and the second fromthe first, 3rd from 4th and 4th from 3rd, etc. In fact, any permutation of the infinite list (with certain restrictions as to hitting everything) gives you missing elements.

It's not just "a slippery bit bigger" (a term for which you have given me no efinition and no intuition), it's enormously bigger.

The one intuition you come back to is the "in between" bit. Again I give you the example of the evens. Surely since between every pair of even numbers there's an integer, that means there must be more integers? No, it doesn't, and it's just like that.

You say that because there are infinitely many rationals between each pair of reals then there must be a similar number of reals (ok, maybe "a slippery bit more"). Well, no, that's not true. It just isn't like that.

In short, your existing intuition is leading you astray, you haven't worked enough with the infinities and their applications to develop an appropriate intuition, and you're rejecting every attempt to help you gain the right intuition.

So I'll stop there until you can help me understand your problem better.

Ok, let's take another one. Consider me to be doing fuzzy experimental math philosophy. I am not a mathematician and never want to be one so the universe won't explode.

I'm going to reject the Continuum Hypothesis, ok? (Math tells me I can take it or leave it, so I'm going to leave it.) Now I take a subset of the reals, including Q, with lower cardinality but uncountable still. So now "almost all" of reals aren't these guys? And "almost all" of these guys are transcendental or uncomputable? And I can keep injecting infinities in there like this, ok...

Math doesn't tell me I can or can't do this!! So I think I can choose my intuition, and math isn't even going to tell me otherwise.

    > I'm going to reject the Continuum Hypothesis, ok?

OK.

    > Now I take a subset of the reals, including Q,
    > with lower cardinality but uncountable still.

Call it K, so K contains Q, and |Q| < |K| < c=|R|. OK.

    > So now "almost all" of reals aren't these guys?

Yes. Almost all the K aren't Q, and almost all the R aren't K.

    > And I can keep injecting infinities in there like
    > this, ok...

Yes.

    > Math doesn't tell me I can or can't do this!!

Correct.

    > So I think I can choose my intuition, and math
    > isn't even going to tell me otherwise.

Non-sequitur. The purpose of intuition is to guide you in developing proofs or solving problems. Feel free to use your own intuition and reject that of others. If you're not going to be proving theorems or solving problems, there's nothing wrong with having an intuition at odds with everyone else's.

However, as a data point, the intuition that's developed over the last two centuries or so, the one you reject, seems to work in proving theorems and solving problems.

The concepts of infinity contain much that seems contradictory. Intuitions based on your finite world simply don't work. The best way to develop new ones is to work with these things, or to accept the visualisations that others provide.

No, that's not right. Cantor's argument says that it's impossible to create a bijection between the rationals and the irrationals. It does this by considering an arbitrary bijection and then showing there is at least one irrational not in that bijections image (a contradiction).

In that sense there are "more" irrationals than rationals.

There is another field of mathematics called measure theory in which the notion of "almost all" is made precise and in that case, yes, almost all reals are irrational. But that has nothing to do with Cantor's proof, which is pure set theory.

This is an interesting article. But I think he's being too mysterious about this notion of "cheating".

Consider a far smaller set: {1, 2, 3}. Bob wants to prove that there are at most 3 elements in this set. (Yes, I know this is trivial.) His strategy: name 3 elements in the set (1, 2, 3), and no matter what Alice picks from the set, he will name her choice. Obviously, this strategy works.

Now suppose that Bob wants to prove that there is only 1 element in the set {1, 2, 3}. His strategy is similar: name 1 element in the set (2, say), and -- he hopes -- no matter what Alice picks from the set, he will name her choice. Of course, this doesn't work. However, in order to be sure that Bob does not name her choice: Alice must know his strategy. Does that mean she is "cheating"? Hardly.

The above "cheating" issue is the same as that in the article. So we're not talking about some mysterious property of infinite sets.

The "real" problem here is that the POV the post argues against appears to include the idea that mathematical proofs must be isomorphic to some game between two (or perhaps more) people that a human brain would consider "fair". This is not a generally useful way to approach proofs.

(The word "generally" is not extraneous in this post.)

Reply on news.ycombinator.com