08 Sep 22
@moonbus saidIt's very late for me, but a quick drive-by: the rationals are countable. Cantor used a "diagonalization argument" to prove it. It is the real numbers that are uncountably infinite.
It's hard to think about infinity. One easily gets into a mind cramp. Regarding numbers, there are countable infinities and non-countable infinities. You know this already, but for the benefit of other readers here: the integers are countable, and any set which can be put into 1:1 correspondence with the integers is also countable. The even numbers, for example, are a countab ...[text shortened]... of physical space with nothing in it)? But now we really do have old Zeno breathing down our necks.
- Joined
- 18 Jan 07
- Moves
- 12477
09 Sep 22
@soothfast saidHm, almost right. The diagonal argument didn't prove that the rationals are countable, but that the reals are not. The conclusion remains the same, though. (And I don't know who proved that the rationals are countable, although I do know how.)
It's very late for me, but a quick drive-by: the rationals are countable. Cantor used a "diagonalization argument" to prove it. It is the real numbers that are uncountably infinite.
@shallow-blue saidA "diagonal argument" is a proof technique that can prove a lot of different things in set theory.
Hm, almost right. The diagonal argument didn't prove that the rationals are countable, but that the reals are not. The conclusion remains the same, though. (And I don't know who proved that the rationals are countable, although I do know how.)
Here's a diagonal argument that the reals are uncountable:
http://mathonline.wikidot.com/the-set-of-real-numbers-is-uncountable
Here's a diagonal argument that the rationals are countable, and also another presentation of the diagonal argument that the reals are uncountable:
https://aminsaied.wordpress.com/2012/05/21/diagonal-arguments/
In the latter link note that the word "diagonal" is apt in two senses: by zig-zagging through an infinite array of fractions along diagonal pathways, or creating a vertical list of numbers aligned by their decimal points and looking at the nth decimal place of the nth item on the list.
I believe Cantor did both of these proofs originally, though the history of mathematics is not my specialty. Maybe he didn't do the zig-zagging along an array approach.
09 Sep 22
@shallow-blue saidIt occurs to me that it is curious how the word "diagonal" arises in two different ways: from working with a list of decimal expansions of reals in the interval [0,1], and from working with an array of fractions.
Hm, almost right. The diagonal argument didn't prove that the rationals are countable, but that the reals are not. The conclusion remains the same, though. (And I don't know who proved that the rationals are countable, although I do know how.)
I'm not sure Georg Cantor, over 120 years ago, ever diddled with an array of fractions to prove the rationals are countable. Maybe he devised an explicit bijection. Four different proofs are here:
https://proofwiki.org/wiki/Rational_Numbers_are_Countably_Infinite
And if you think the proof that the rationals are countable found at the top of the page at
https://aminsaied.wordpress.com/2012/05/21/diagonal-arguments/
is kind of hand-wavey or heuristic, I would tend to agree. I much prefer explicit bijection approaches.
Fun stuff.
@moonbus saidI figured you meant to say real. It's easy to slip up with these things. 😉
@Soothfast
Oh yes, right you are. Substitute’real’ for ‘ rational’ in my post.
- Joined
- 18 Jan 07
- Moves
- 12477
10 Sep 22
@moonbus saidI'd love to get a handle on the surreal ones.
@Soothfast
Personally, my favorites are imaginary numbers. 😆
11 Sep 22
@Shallow-Blue
Oh, those are the ones with limp clocks draped over them. Wouldn't touch 'em with a ten-foot barge pole.