Hacker News Reader

Comment by pndmnm | Hacker News Reader

There are the same number of whole numbers as there are fractions/rational numbers (my favorite quick proof -- every whole number is a rational number (itself over 1). Map each n/m in lowest terms to 2^n*3^m for an injection of rationals into the integers (by the fundamental theorem of arithmetic)).

View on HN

> There are the same number of whole numbers as there are fractions/rational numbers (my favorite quick proof -- every whole number is a rational number (itself over 1). Map each n/m in lowest terms to 2^n*3^m for an injection of rationals into the integers (by the fundamental theorem of arithmetic)).

Notice that this shows only that there are no more whole numbers than rational numbers, and no more rational numbers than whole numbers. To conclude that there is the same number of each (more generally, that cardinal numbers are totally ordered (EDIT: as ionfish (http://news.ycombinator.com/item?id=4251492) points out, I should have said that the inclusion relation on cardinals is antisymmetric)) is actually a bit delicate; it's called the Schröder–Bernstein theorem (although Wikipedia attaches more names, in a different order: https://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80...).

True, though this "proof" assumes a large amount of additional mathematical machinery in addition to SB (I learned it as Cantor-Schröder–Bernstein originally... I wonder where the inconsistency in the naming comes from). It's not so much a formal set-theoretic proof (of course it could be made so) as a quick demonstration that has a stronger pull on mathematical intuition than the standard proof (and is demonstrating an otherwise provable thing).

The history of the proof is a little messy; the Wikipedia page has a decent summary.

http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theo...

Yes, it does rely implicitly on Cantor–Schröder–Bernstein. That might be a downside, but I think when working informally (that is to say, when not teaching a set theory course) one can simply assert that if there exist injective functions from sets A and B into one another then they are equinumerous.

That being said, although important in the theory of the order of the cardinal numbers, Cantor–Schröder–Bernstein doesn't show that the cardinals are totally ordered. That statement is actually equivalent to the Axiom of Choice, whereas as far as I'm aware Cantor–Schröder–Bernstein holds in ZF.

That's absolutely correct -- trichotomy for arbitrary cardinals (any two cardinals are cardinal-size-comparable) requires AC, but SB doesn't require AC. Trichotomy for the cardinal numbers of well-ordered sets (e.g. ordinals) doesn't require AC.

It's a little irrelevant to this thread... but as long as I'm quoting non-proofs that require lots of extra machinery, I'll give my favorite appeal-to-intuition equivalent of choice: the product of non-empty sets is non-empty (any point in the product of a collection of non-empty sets is a choice function on those sets).

AC is equivalent to a lot of things. There's a collection of them on the Wikipedia page.

http://en.wikipedia.org/wiki/Axiom_of_choice#Equivalents

Something I find pretty interesting is that some of these equivalences break down in weak systems.

http://www.math.uchicago.edu/~antonio/RM11/RM%20talks/mummer...

Yup, I did a few projects on equivalents of AC back in the day. That's just my favorite "appeal to intuition" one (my favorite "appeal to intuition" against AC is: the identity function is the sum of two periodic functions (though this is a consequence and not equivalent)).

Equivalence breakdown in alternate systems is a wonderful topic. I've been trying for a couple years now to figure out how to get back into set theory now that I'm out of academia. Maybe later this summer...

> That being said, although important in the theory of the order of the cardinal numbers, Cantor–Schröder–Bernstein doesn't show that the cardinals are totally ordered.

Good point, thanks; I've corrected my post accordingly.

My favorite proof uses the Wilf-Calkin formula, which provides an explicit enumeration of the rationals without repetition. The Wilf-Calkin tree is related, and provides the basic principles.

http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree

In the tree every rational appears exactly once in lowest terms, and is easily generated recursively.

That's a really nice way to show that, thanks. I may borrow it for future use.

Reply on news.ycombinator.com