Uncountability of the Rationals?
in [Math]
|
Prev: Collatz conjecture
Next: Beginner-ish question
From: Tony Orlow on 2 Jun 2010 14:56 Hi All - Looking at some of Herc's recent threads about Cantor's diagonal proof of the uncountability of the reals, a question occurs to me which I actually don't know how a subscriber to transfinite set theory would answer. I'm curious. In Cantor's list of reals, for every digit added, the list doubles in length. In order to follow his logic, we need not consider any real numbers which are not rational. In any such list of rationals, it is always true that we can concoct another rational which is not on the list. Irrational numbers need not even be considered. So, are the rationals not to be considered uncountable, by Cantor's own logic? BTW, I understand that the rationals are considered countable because of a rather artificial bijection with N, but if Cantor's argument really has anything to do with the reals, as opposed to the powerset (which is what it's really all about), then why is it entirely unnecessary to even consider irrational reals in his construction? Thanks and Smiles, Tony
From: Virgil on 2 Jun 2010 15:26 In article <b65b2a33-7335-410a-8da7-91026e63755e(a)q13g2000vbm.googlegroups.com>, Tony Orlow <tony(a)lightlink.com> wrote: > Hi All - > > Looking at some of Herc's recent threads about Cantor's diagonal proof > of the uncountability of the reals, a question occurs to me which I > actually don't know how a subscriber to transfinite set theory would > answer. I'm curious. > > In Cantor's list of reals, for every digit added, the list doubles in > length. In order to follow his logic, we need not consider any real > numbers which are not rational. In any such list of rationals, it is > always true that we can concoct another rational which is not on the > list. Irrational numbers need not even be considered. So, are the > rationals not to be considered uncountable, by Cantor's own logic? > > BTW, I understand that the rationals are considered countable because > of a rather artificial bijection with N Countability of any set is established by ANY bijection with N, no matter how "artificial" it may seem to Tony Orlow, or anyone else. > but if Cantor's argument > really has anything to do with the reals, as opposed to the powerset > (which is what it's really all about), then why is it entirely > unnecessary to even consider irrational reals in his construction? Since Cantor has provided at least two proofs based on two entirely different lines of argument, TO should make clear what proof he is talking about, particularly as both proofs require consideration of irrationals so that TO's comment is nonsense with respect to either.
From: Brian Chandler on 2 Jun 2010 15:27 Tony Orlow wrote: > Hi All - Hello Tony! > Looking at some of Herc's recent threads about Cantor's diagonal proof > of the uncountability of the reals, a question occurs to me which I > actually don't know how a subscriber to transfinite set theory would > answer. I'm curious. There are no "subscribers" to set theory (unless this has something curious to do with using a "full-price" newsreader), only those who understand it (as distinct from those who don't, of course). > In Cantor's list of reals, for every digit added, the list doubles in > length. It does? Reference please to a textbooks talking about "Cantor's list of reals", with digits being progressively added. (For extra marks, you could just explain why you think there's a relation between "adding a digit" and doubling the number of somethings. This sounds much more to me like a list of terminating binary fractions of length not more than n, for some n -- not related in any obvious way to a "list of reals".) Brian Chandler
From: Mike Terry on 2 Jun 2010 16:20 "Tony Orlow" <tony(a)lightlink.com> wrote in message news:b65b2a33-7335-410a-8da7-91026e63755e(a)q13g2000vbm.googlegroups.com... > Hi All - > > Looking at some of Herc's recent threads about Cantor's diagonal proof > of the uncountability of the reals, a question occurs to me which I > actually don't know how a subscriber to transfinite set theory would > answer. I'm curious. > > In Cantor's list of reals, for every digit added, the list doubles in > length. In order to follow his logic, we need not consider any real > numbers which are not rational. In any such list of rationals, it is > always true that we can concoct another rational which is not on the > list. Irrational numbers need not even be considered. So, are the > rationals not to be considered uncountable, by Cantor's own logic? I don't understand the "list doubles in length" bit. However, I think maybe I can see what you're trying to do. You want to: 1) treat rationals as real numbers, with a decimal expansion 2) given a listing of all the rational numbers, apply Cantor's argument regarding the anti-diagonal to construct a new number not on the list 3) conclude that this means that the rationals would not be countable? Is this what you're doing? If so, don't bother explaining about the list doubling stuff, as it doesn't matter - there's an easy explanation for your problem! The explanation is that steps (1) and (2) are fine. However the "antidiagonal number" generated in (2) will not be a rational number, so the conclusion (3) breaks down. Note the difference with Reals instead of Rationals: when applied to Reals, the antidiagonal number is a *Real* number not in the list... Regards, Mike. > > BTW, I understand that the rationals are considered countable because > of a rather artificial bijection with N, but if Cantor's argument > really has anything to do with the reals, as opposed to the powerset > (which is what it's really all about), then why is it entirely > unnecessary to even consider irrational reals in his construction? > > Thanks and Smiles, > > Tony
From: christian.bau on 2 Jun 2010 16:21
On Jun 2, 7:56 pm, Tony Orlow <t...(a)lightlink.com> wrote: > BTW, I understand that the rationals are considered countable because > of a rather artificial bijection with N, but if Cantor's argument > really has anything to do with the reals, as opposed to the powerset > (which is what it's really all about), then why is it entirely > unnecessary to even consider irrational reals in his construction? You call this a "rather artificial bijection", but here is what being "countable" really means: A set is countable if you can choose a first element, a second element, a third element, and so on, in such a way that every single element will be chosen eventually. In other words, you can systematically count through all the elements. So what is "artificial" about the bijection between rationals and natural numbers? If you tried to count the integers (positive and negative) by starting 1, 2, 3, 4 and so on and then follow with the negative numbers and zero last, then obviously we will _not_ manage to eventually reach every integer, because we never finish with the positive ones. But that is just because we took a stupid ordering: If you count 0, +1, -1, +2, -2, +3, -3, +4, -4 and so on, then _every_ integer will turn up eventually. Same with the rationals. Start with zero. Then all fractions where numerator + denominator = 2, followed by the negative ones, then those where numerator + denominator = 3, the negatives, and so on. There is nothing "artificial" about this, just a straightforward way to achieve what you want. And every fraction will eventually turn up. Cantor's argument breaks down for rational numbers: Assume we have a list of all rational numbers. Now we create a rational number that is not on the list by taking the first decimal of the first number on the list and adding 1, the second decimal of the second number on the list and adding one, then the third decimal of the third number adding one and so on. The resulting number is not in the list. So where does the argument break down? Very simple: The resulting number is not rational. |