Comment by ihodes | Hacker News Reader

Comment by ihodes | Hacker News Reader

Parent Full thread

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.)

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 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.

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.

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.

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.

Reply on news.ycombinator.com