tag:blogger.com,1999:blog-1522013117369989006.post1926425200621503421..comments2013-05-15T05:05:54.994+03:00Comments on Turing Complete: A simple proof that the rationals are countableHarry Zisopouloshttps://plus.google.com/103086974555362960954noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-1522013117369989006.post-4153778560686706312013-05-15T05:05:54.994+03:002013-05-15T05:05:54.994+03:00Hello and thanks for your comment! When I was writ...Hello and thanks for your comment! When I was writing this the proofs I could find online either proofs that simply gave the rational spiral (thus informal) or proofs that either handwaved the uniqueness of the canonical form or went into quite some trouble to prove it.<br /><br />The point I want to make is that you can form a bijection with a subset of a countable set and still have a valid proof. This is similar to reducing a problem to another problem, where the instances you get from the reduction have a specific structure and do not cover all possible instances of the problem you reduce to.<br /><br />Perhaps the above is a trivial example, but the same proof idea could be used extensively.<br /><br />I find very interesting what you mention about an infinite cardinality smaller than aleph-naught. I would assume this is the smallest one by definition. Any pointers to such a proof or a discussion of this issue would be very interesting!Harry Zisopouloshttp://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-1522013117369989006.post-43829447386408732322013-05-13T10:22:31.619+03:002013-05-13T10:22:31.619+03:00Am I missing something, or did you just replace a ...Am I missing something, or did you just replace a method based on constructing a set S of fractions followed by taking a subset of S to get countability with a method based on constructing a set S of fractions followed by taking a subset of S to argue countability?<br /><br />I don't really see what this accomplishes. In both cases, you're hand-waving away the argument that there is no infinite cardinality smaller than aleph-naught.Anonymousnoreply@blogger.com