Uncountability of the Rationals?
in [Math]
|
Prev: Collatz conjecture
Next: Beginner-ish question
From: Transfer Principle on 2 Jun 2010 17:10 On Jun 2, 12:27 pm, Brian Chandler <imaginator...(a)despammed.com> wrote: > > 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) This is a thinly veiled reference to me, and my argument that those who post via free web-based news access have a lower reputation than those who post via traditional NNTP newsreaders to sci.math. (If Chandler doesn't believe me, he can just look at the poster Spotter, all of whose posts are one-liners disparaging those who post via Google or Mathforum or make even the slightest spelling error. At least one of his posts is racist. In no case does Spotter ever address the argument per se.) Since I'm here in a thread that attacks Cantor anyway, I might as well address the subject at hand. > only those who > understand it (as distinct from those who don't, of course). I agree with TO here, except that instead of "subscriber," I prefer to use a word like "adherent" (so as to avoid the money issue). So I refer to the adherents of ZFC. Some posters may have different reasons for not being an adherent of ZFC -- perhaps because they're constructivists who oppose AC, perhaps they are finitists who oppose the Axiom of Infinity, and so on. The word "adherent" often describes those who have a particular religion. Notice that Herc, whose posts TO has read before starting this thread, even refers to standard set theory based on Cantor as being a "religion." And I somewhat agree. Adherents of ZFC believe that its axioms are true, just as adherents of a religion believe that its unprovable claims are true. I have nothing against ZFC or religion per se -- just that adhering to either is somewhat similar. > > 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".) TO admits that he's read Herc, and so it's not surprising that he makes a Herc-like argument here. Herc and TO ask if Cantor proves that R is uncountable, why doesn't the same proof show N or Q, respectively, to be uncountable? As I told Cooper in the other thread, because of the defintion of countable and the way that quantifiers work, proving a set to be countable only requires that _one_ list of its elements be complete, while showing that it's uncountable requires that _all_ (not just _one_) lists of its elements be incomplete. But unlike Herc, we _know_ that TO is interested in his own theory (thus putting him in Case 1 of my list of possible cases), since he's gone as far as to give the proposed theory a name, the T-riffics. In the T-riffics, the set N of natural numbers is said to have a cardinality (or "bigulosity") of Big'Un. In the T-riffics, sets have distinct bigulosity from their proper subsets, and thus Q must have a bigulosity strictly more than Big'Un. (I forget what TO claims to be the bigulosities of Q or R.) So unlike Cooper, at least we know what TO is attempting to accomplish here.
From: Tony Orlow on 2 Jun 2010 18:47 On Jun 2, 5:10 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > On Jun 2, 12:27 pm, Brian Chandler <imaginator...(a)despammed.com> > wrote: > > > > 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) > > This is a thinly veiled reference to me, and my argument > that those who post via free web-based news access have > a lower reputation than those who post via traditional > NNTP newsreaders to sci.math. (If Chandler doesn't > believe me, he can just look at the poster Spotter, all > of whose posts are one-liners disparaging those who > post via Google or Mathforum or make even the slightest > spelling error. At least one of his posts is racist. In > no case does Spotter ever address the argument per se.) > > Since I'm here in a thread that attacks Cantor anyway, > I might as well address the subject at hand. > > > only those who > > understand it (as distinct from those who don't, of course). > > I agree with TO here, except that instead of "subscriber," > I prefer to use a word like "adherent" (so as to avoid the > money issue). So I refer to the adherents of ZFC. Some > posters may have different reasons for not being an > adherent of ZFC -- perhaps because they're constructivists > who oppose AC, perhaps they are finitists who oppose the > Axiom of Infinity, and so on. > > The word "adherent" often describes those who have a > particular religion. Notice that Herc, whose posts TO has > read before starting this thread, even refers to standard > set theory based on Cantor as being a "religion." And I > somewhat agree. Adherents of ZFC believe that its axioms > are true, just as adherents of a religion believe that its > unprovable claims are true. > > I have nothing against ZFC or religion per se -- just that > adhering to either is somewhat similar. > > > > 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".) > > TO admits that he's read Herc, and so it's not surprising > that he makes a Herc-like argument here. Herc and TO ask > if Cantor proves that R is uncountable, why doesn't the > same proof show N or Q, respectively, to be uncountable? > > As I told Cooper in the other thread, because of the > defintion of countable and the way that quantifiers work, > proving a set to be countable only requires that _one_ > list of its elements be complete, while showing that it's > uncountable requires that _all_ (not just _one_) lists of > its elements be incomplete. > > But unlike Herc, we _know_ that TO is interested in his > own theory (thus putting him in Case 1 of my list of > possible cases), since he's gone as far as to give the > proposed theory a name, the T-riffics. In the T-riffics, > the set N of natural numbers is said to have a cardinality > (or "bigulosity") of Big'Un. In the T-riffics, sets have > distinct bigulosity from their proper subsets, and thus Q > must have a bigulosity strictly more than Big'Un. (I > forget what TO claims to be the bigulosities of Q or R.) > > So unlike Cooper, at least we know what TO is attempting > to accomplish here. Hi Transfer et al - Thanks for (most of) the responses. I get what I missed, but probably have to play with it a little to be fully convinced intuitively that the diagonal of a list of all rationals must produce an irrational real. That would be a good response. I am by no means trying to equate |N| with |R| or any such thing, nor |Q| with |R|. I was just wondering off the cuff how the logic broke there and it makes sense. BTW, Transfer, your rendition of Bigulosity Theory is a little off, but no worries. Hopefully I'll have at least a preliminary version ready soon for release, review, and excoriation. Thanks to Mike and Christian, too. Adam, I think you know where you can stick your comment. Virgil and Brian, nice to see you still holding down the fort. Martin, you left your medication in the CD ROM drive again.... Have a nice day! Tony
From: christian.bau on 2 Jun 2010 21:38 On Jun 2, 11:47 pm, Tony Orlow <t...(a)lightlink.com> wrote: > Thanks for (most of) the responses. I get what I missed, but probably > have to play with it a little to be fully convinced intuitively that > the diagonal of a list of all rationals must produce an irrational > real. That would be a good response. That's quite easy if you go the other way round. Instead of proving that applying the Cantor process to a complete list of all rational numbers will necessarily produce a real number, you can show: If the Cantor process applied to an infinite list of numbers produces a rational result, then there is a rational number which is not in the list. So take a list of numbers (we don't even care if they are rational). Construct a real number x by taking the first digit of the first number in the list, the second decimal digit of the first number and so on, and increasing each digit by 1 (changing a digit 9 to a 0). Assume the result x is a rational number. Now construct a number y by subtracting 2 from each digit of x, replacing 0 with 8 and 1 with 9. A number is rational if and only if its decimal representation is periodic. x is periodic, therefore y is periodic, therefore y is rational. But y cannot be in the list of numbers, because if it was element number n, then the n-th decimal digit of x would be 1 higher than the n-th decimal digit of y, but it is 2 higher. So: The Cantor process applied to _any_ infinite list of real numbers produces a result x which is either rational or irrational. If x is rational then there is a different rational number y which is not in the list. So if the list contains all rational numbers (plus possibly a finite or infinite number of irrational numbers), then the result of the Cantor process must be irrational.
From: Tim Little on 2 Jun 2010 22:48 On 2010-06-02, Tony Orlow <tony(a)lightlink.com> wrote: > In Cantor's list of reals, for every digit added, the list doubles in > length. In Cantor's list of reals, there are no digits "added", nor changes in length of the list. The list is presumed to be given, and regardless of what it contains, is shown to be necessarily incomplete. > 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. No, it is not always true. It is not difficult to demonstrate a list of rationals for which the antidiagonal is irrational. - Tim
From: Brian Chandler on 3 Jun 2010 04:07
Transfer Principle wrote: > On Jun 2, 12:27 pm, Brian Chandler <imaginator...(a)despammed.com> > wrote: > > > 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) > > This is a thinly veiled reference to me, I'd have called it a "weak joke", rather than a "thinly-veiled reference", but never mind. FWIW, you might notice I'm posting this from Google, so you and I share the same low esteem rating, it seems. > > only those who > > understand it (as distinct from those who don't, of course). > > I agree with TO here, except that instead of "subscriber," > I prefer to use a word like "adherent" ... > > The word "adherent" often describes those who have a > particular religion. ... Adherents of ZFC believe that its axioms > are true, just as adherents of a religion believe that its > unprovable claims are true. Hmm. But non-adherents of religion (and possible adherents, too, with respect to all but the one they adhere to*) can generally say just where they disagree with the axioms of the religion. "Non-adherents" to ZFC typically flunk out when challenged to exactly what they disagree with. * I'm reminded of the review of Martin Gardner's seminal anti-woo bookl published around 1950. The second edition is generally preferred because it includes samples of the hate mail he received after the first edition, from people who generally loved all chapters but exactly one of the book. ** ** Sorry, I chickened out, because I just couldn't choose between "all but exactly one chapter" and "all but exactly one chapters" ... > I have nothing against ZFC or religion per se -- just that > adhering to either is somewhat similar. Ah, now I'm stuck. Brian Chandler |