THE CANTOR ARGUMENT SO FAR
in [Logic]
|
From: Tim Little on 21 Jun 2010 03:27 On 2010-06-21, Sylvia Else <sylvia(a)not.here.invalid> wrote: > If I require digit n to be d, and assuming it isn't already, I can > search down the list until I find a line with digit n equal to d, > and then permute the list so that that line is line n. You can do that for any single digit position, any finite set of positions, and in fact for many infinite sets of digit positions. However, you cannot do this for *all* digit positions. For example, suppose your desired real is 1/9 = 0.111..., and you have 2/9 = 0.222... in the list somewhere. There is nowhere you can swap it to get the correct real along the diagonal. In general if there exists a real y in the list that differs in every position from some real x, then you cannot put x along the diagonal. More generally still, it is not easy to define any reasonable meaning for an infinite composition of non-disjoint permutations. > Since this means the set of permutations must be uncountably infinite, > if follows that there are uncountably many permutations of a countably > infinite set. > > Does that stand up? The conclusion "there are uncountably many permutations of a countably infinite set" is true, but the reasoning by which you arrive at it is invalid. - Tim
From: Mike Terry on 21 Jun 2010 20:59 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1u52o.jrj.tim(a)soprano.little-possums.net... > On 2010-06-21, Sylvia Else <sylvia(a)not.here.invalid> wrote: > > If I require digit n to be d, and assuming it isn't already, I can > > search down the list until I find a line with digit n equal to d, > > and then permute the list so that that line is line n. > > You can do that for any single digit position, any finite set of > positions, and in fact for many infinite sets of digit positions. > However, you cannot do this for *all* digit positions. > > For example, suppose your desired real is 1/9 = 0.111..., and you have > 2/9 = 0.222... in the list somewhere. There is nowhere you can swap > it to get the correct real along the diagonal. > > In general if there exists a real y in the list that differs in every > position from some real x, then you cannot put x along the diagonal. > > > More generally still, it is not easy to define any reasonable meaning > for an infinite composition of non-disjoint permutations. > Aaaaargh, it's all starting to come back! This is how I started off with Herc a few years ago, and Herc believed that IF he could permute the list in order to achieve ANY diagonal of his choosing, then he could engineer it so that the corresponding antidiagonal was in the list, although by Cantor's argument it is not. Well, this much is correct, but obviously it won't be possible to permute the list in this way... But then Herc went on to invent a succession of ever more complex schemes involving building up these "permutations" by successively swapping/shuffling rows of a carefully constructed starting list. Actually the whole idea was quite good fun to think through by comparison with today's Herc issues, and in the end the problem boiled down to that, say, row 1 would initially be swapped to row 20, and then in step 20 it would be swapped to say row 1000, and in step 1000...etc. Well, in the end row 1 would end up being shuffled right out of the list altogether!, which seems a little weird, but it just means that the naive interpretation of the "infinite composition of permutations" wasn't in fact a valid permutation of the list. I.e. what you said! :-) > > > Since this means the set of permutations must be uncountably infinite, > > if follows that there are uncountably many permutations of a countably > > infinite set. > > > > Does that stand up? > > The conclusion "there are uncountably many permutations of a countably > infinite set" is true, but the reasoning by which you arrive at it is > invalid. > > > - Tim
From: Transfer Principle on 21 Jun 2010 23:34 On Jun 21, 12:27 am, Tim Little <t...(a)little-possums.net> wrote: > On 2010-06-21, Sylvia Else <syl...(a)not.here.invalid> wrote: > > If I require digit n to be d, and assuming it isn't already, I can > > search down the list until I find a line with digit n equal to d, > > and then permute the list so that that line is line n. > You can do that for any single digit position, any finite set of > positions, and in fact for many infinite sets of digit positions. > However, you cannot do this for *all* digit positions. > For example, suppose your desired real is 1/9 = 0.111..., and you have > 2/9 = 0.222... in the list somewhere. There is nowhere you can swap > it to get the correct real along the diagonal. Ah yes, I mentioned this back in one of the other Herc threads about a month ago. But then Herc pointed out that he was saying that any _randomly_ chosen real can appear on the diagonal. Recall that random probabilities in the unit interval are based on the notion of Lebesgue measure, and a set can be null (i.e., have Lebesgue measure zero) without being the empty set. Our conjecture, therefore, is that given the list of computable reals and a randomly chosen real in (0,1), then there exists a permutation of the list such that the chosen real will appear on the diagonal with probability 1 -- in other words, the set of all reals with can't appear on the diagonal is null (i.e., has Lebesgue measure zero). Recall that Herc originally based this argument using ternary, not decimal, reals. It's easy to find many reals which can't appear on the diagonal. The presence of 1/2 = 0.111... means that no number with only zeros and twos in its ternary expansion (i.e., no member of the Cantor middle-thirds set) can appear on the diagonal, but the Cantor set is null. Also, no computable number can appear on the diagonal, because we can either add or subtract 1/2 = 0.111... from it to find another computable number that's already in the list yet differs in every digit, but once again, the set of computable reals is countable hence null. So the conjecture remains open.
From: Transfer Principle on 21 Jun 2010 23:45 On Jun 21, 5:59 pm, "Mike Terry" <news.dead.person.sto...(a)darjeeling.plus.com> wrote: > "Tim Little" <t...(a)little-possums.net> wrote in message > > More generally still, it is not easy to define any reasonable meaning > > for an infinite composition of non-disjoint permutations. > Aaaaargh, it's all starting to come back! This is how I started off with > Herc a few years ago, and Herc believed that IF he could permute the list in > order to achieve ANY diagonal of his choosing, then he could engineer it so > that the corresponding antidiagonal was in the list, although by Cantor's > argument it is not. Well, this much is correct, but obviously it won't be > possible to permute the list in this way... > But then Herc went on to invent a succession of ever more complex schemes > involving building up these "permutations" by successively > swapping/shuffling rows of a carefully constructed starting list. Actually > the whole idea was quite good fun to think through by comparison with > today's Herc issues, and in the end the problem boiled down to that, say, > row 1 would initially be swapped to row 20, and then in step 20 it would be > swapped to say row 1000, and in step 1000...etc. > Well, in the end row 1 would end up being shuffled right out of the list > altogether! Ah yes, a bit similar to Hilbert's Hotel. I was wondering whether something like this could happen, but Little's comment about 0.111... = 1/9 (or 1/2 in the original ternary that Cooper is using) means that it is futile to put 1/2 on the diagonal before worrying about this Hilbert's Hotel paradox at all. But of course, I assume that Herc proposed some sort of _algorithm_ to get the real r on the diagonal. It most likely went something like this -- if the dth digit of the dth real doesn't match the dth digit of r, then we swap the dth real with the nth real, where n is the first natural greater than d such that the dth digit of the nth real is the correct dth digit of r. Since the list contains all the computable reals, and there are infinitely many computable reals with the correct digit in the dth place, and there have been only finitely many reals before reaching the dth real, there's guaranteed to be a computable real remaining in the list with the correct digit in the dth place. Thus r is guaranteed to appear on the diagonal. But if r were say, any member of the Cantor set (so that it contains only zeros and twos in its ternary expansion), then 1/2 = 0.111... will be swapped, and swapped again, indeed producing the Hilbert's Hotel effect as described by Terry. Still, will this happen with _almost_every_ real that we try to put on the diagonal?
From: Transfer Principle on 21 Jun 2010 23:49
On Jun 20, 8:14 pm, "|-|ercules" <radgray...(a)yahoo.com> wrote: > "Sylvia Else" <syl...(a)not.here.invalid> wrote > > Well, it's true that I rather assumed, without proof, that any number > > can be created in the diagonal. But I don't think anything relevant > > turns on that. > You admit your error to him but not me? But then again, Else made the same error that Herc made, namely assuming that any real can appear on the diagonal. Of course, the conjecture that _almost_every_ real (i.e., every real except in a set of Lebesgue measure zero) can appear on the diagonal remains open. > What are we married or something! Married? What's next -- will Herc claim that Else is actually Genesis Eve? > Atleast you dismissed your error as irrelevant in true [...] [snip sexism and homophobia] |