4 ms·

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 o

by pndmnm 14y ago

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

ionfish 14y ago
That's a really nice way to show that, thanks. I may borrow it for future use.
JadeNB 14y ago
> 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 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%93Schroeder_theorem https://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80...).
- pndmnm 14y ago
  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).
  - ionfish 14y ago
    The history of the proof is a little messy; the Wikipedia page has a decent summary. http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theorem http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theo...
- ionfish 14y ago
  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.
  - pndmnm 14y ago
    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).
    - ionfish 14y ago
      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 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/mummert.pdf http://www.math.uchicago.edu/~antonio/RM11/RM%20talks/mummer...
      - pndmnm 14y ago
        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...
ColinWright 14y ago
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 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.

by pndmnm 14y ago

ionfish 14y ago

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

JadeNB 14y ago

> 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 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%93Schroeder_theorem https://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80...).

pndmnm 14y ago
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).
- ionfish 14y ago
  The history of the proof is a little messy; the Wikipedia page has a decent summary. http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theorem http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theo...
ionfish 14y ago
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.
- pndmnm 14y ago
  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).
  - ionfish 14y ago
    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 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/mummert.pdf http://www.math.uchicago.edu/~antonio/RM11/RM%20talks/mummer...
    - pndmnm 14y ago
      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...

ColinWright 14y ago

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