tag:blogger.com,1999:blog-264226589944705290.post2602226764139987126..comments2022-11-19T01:08:31.131-08:00Comments on God Plays Dice: Who proved the rationals are countable?iMichael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-264226589944705290.post-13953790677457379272008-03-21T12:24:00.000-07:002008-03-21T12:24:00.000-07:00You saw Brent's nice post about this counting back...You saw Brent's nice post about this counting back in January? In case you didn't: <A HREF="http://www.mathlesstraveled.com/?p=100" REL="nofollow">Recounting the Rationals Part III</A><BR/><BR/>JonathanAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-75328961068140485652008-03-20T15:19:00.000-07:002008-03-20T15:19:00.000-07:00Harald,I like that enumeration as well. Surprisin...Harald,<BR/><BR/>I like that enumeration as well. Surprisingly, it has combinatorial significance; see <A HREF="http://www.math.upenn.edu/~wilf/website/recounting.pdf" REL="nofollow">this paper of Calkin and Wilf</A>. Your <I>n</I>th node is b(n-1)/b(n) where b(n) is the number of ways to write n as a sum of powers of two, where each power of two is used at most twice.Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-78836469755977934872008-03-20T15:16:00.000-07:002008-03-20T15:16:00.000-07:00For enumerating the positive rationals, my favouri...For enumerating the positive rationals, my favourite method is this: Put one rational at each vertex of an infinite binary tree. At the root, put 1/1=1. At the two children of a vertex where you find m/n with gcd(m,n)=1, put m/(m+n) and (m+n)/n. To prove that all rational numbers appear, and they appear just once, employ the Euclidean algorithm.<BR/><BR/>Now it only remains to enumerate the vertices of the infinite binary tree. Do so in the obvious order, with number 1 at the root, 2 and 3 below it, 4, 5, 6, 7 below them, then 8, 9,...,15, and so on. The two children of node number n will bear the numbers 2n and 2n+1.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-70435653840842788942008-03-20T11:25:00.000-07:002008-03-20T11:25:00.000-07:00Since all natural numbers can be expressed as a po...Since all natural numbers can be expressed as a power of 2 multiplied by the remaining odd prime factors, you can also use f(x,y) = 2^y(2x+1)-1 as a nice 1-1 correspondence between the natural numbers and an ordered pair.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-87527848740685841732008-03-19T20:56:00.000-07:002008-03-19T20:56:00.000-07:00In fact, Zachary Abel (Harvard) in one of his arti...In fact, Zachary Abel (Harvard) in one of his articles titled "Bert and Ernie" (in the HCMR) points out an explicit enumeration in terms of a rational polynomial (which I think is not very well-known):<BR/><BR/>p(x, y) = (x+y-2)(x+y-1)/2 + yAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-35777053254429223882008-03-19T18:39:00.000-07:002008-03-19T18:39:00.000-07:00I always assume that the answer to any question co...I always assume that the answer to any question containing the words "who" and "countable" is Cantor.dfanhttps://www.blogger.com/profile/16523251716744122695noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-21618881359618394392008-03-19T17:19:00.000-07:002008-03-19T17:19:00.000-07:00As far as I can tell it's Cantor. That seems to b...As far as I can tell it's Cantor. That seems to be the standard attribution, and in fact the proof is in <A HREF="http://books.google.com/books?hl=en&id=W1gNAAAAYAAJ&dq=Contributions+to+the+founding+of+the+theory+of+Transfinite&printsec=frontcover&source=web&ots=FbCEC3qQAm&sig=axugMrhzXjbn_IAJ5flmkFxWYXs" REL="nofollow">Contributions to the Founding of the Theory of Transfinite Numbers</A>, p. 107. (The proof there is actually a proof that the set of ordered pairs of positive integers are countable, but that's the main idea.) But nobody seems willing to just come out and credit this to him; it's always "well, it must have been Cantor, because he [came up with the idea of countability/proved the reals were uncountable/...]"Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-20748134550141883472008-03-19T17:13:00.000-07:002008-03-19T17:13:00.000-07:00I second Kelly.I second Kelly.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-688355631009164022008-03-19T17:12:00.000-07:002008-03-19T17:12:00.000-07:00Who proved the rationals are countable? I would gu...Who proved the rationals are countable? I would guess Cantor, since he came up with the idea of countability, after all, and I can't imagine he would have let that question slide. Why, is it someone else?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-84666821037411957532008-03-19T17:10:00.001-07:002008-03-19T17:10:00.001-07:00I heart Cantor.I heart Cantor.Kelly Mathislifehttps://www.blogger.com/profile/10545624266712358140noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-75529861701898502372008-03-19T17:10:00.000-07:002008-03-19T17:10:00.000-07:00This comment has been removed by the author.Kelly Mathislifehttps://www.blogger.com/profile/10545624266712358140noreply@blogger.com