Another AC anomaly?
in [Math]
|
Prev: Dumb Question on Inference For Regression (Ho:= No Linear Relation)
Next: Is this a valid statement?
From: Butch Malahide on 23 Nov 2009 18:29 On Nov 23, 5:20 pm, Butch Malahide <fred.gal...(a)gmail.com> wrote: > On Nov 23, 5:01 pm, Herman Jurjus <hjm...(a)hetnet.nl> wrote: > > > > > > > Butch Malahide wrote: > > > On Nov 23, 5:22 am, Herman Jurjus <hjm...(a)hetnet.nl> wrote: > > >> Has anyone seen this before? > > > >>http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-resul.... > > > > In plain mathematical terms: for any set X, there is a function f:X^N- > > >> X such that, for each sequence (x_1, x_2, ...} in X^N, the equality > > > x_n = f(x_{n+1}, x_{n+2}, ...) holds for all but finitely many n. > > > > This is old hat: see Problem 5348, American Mathematical Monthly, > > > volume 72 (1965), p. 1136. (This has been discussed on sci.math in the > > > past.) > > > Good to know that! > > When was that, approximately (I mean the sci.math discussion)? > > And under what name was/is it known? > > It has probably come up more than once. I found some stuff by googling > on "problem 5348". OK, I find two sci.math threads: "Ill-defined puzzle" and "An astonishing application of the AC". The first one has no mathematical content. Problem 5348 is also mentioned (with an application) in the sci.math.research thread "Trick property".
From: William Hughes on 23 Nov 2009 20:18 On Nov 23, 2:41 pm, "Mike Terry" <news.dead.person.sto...(a)darjeeling.plus.com> wrote: > "William Hughes" <wpihug...(a)hotmail.com> wrote in message > > news:0210e1fa-23fa-4af9-a59b-17e2f0b2d0fc(a)m33g2000vbi.googlegroups.com... > > > > > On Nov 23, 10:09 am, Herman Jurjus <hjm...(a)hetnet.nl> wrote: > > > William Hughes wrote: > > > > On Nov 23, 7:22 am, Herman Jurjus <hjm...(a)hetnet.nl> wrote: > > > >> Has anyone seen this before? > > >>http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-resul.... > > > > >> I'm not sure yet what to conclude from it; that AC is horribly wrong, > or > > > >> that WM is horribly right, or something else altogether. > > > > >> In short the story goes like this: > > > > >> A game is played, in which infinitely many coins are tossed, and > there's > > > >> one player, who makes infinitely many guesses. Both are done over a > > > >> finite period of time. The tosses and guesses are not made faster and > > > >> faster, however, but slower and slower: at t = 1/n. There's no > 'first' > > > >> move. > > > > >> Claim: > > > >> There exists a strategy with which you're certain to guess all > entries > > > >> correctly except for at most finitely many mistakes. Not 'certain' as > in > > > >> 'probability is 100%', but absolutely certain. > > > > >> Reasoning: > > > >> On 2^w, consider the equivalence relation that makes x equivalent to > y > > > >> when x(n) =/= y(n) for at most finitely many n. Next, using AC, > create a > > > >> set S that contains precisely one element from every equivalence > class. > > > >> Strategy: at every move, you already know the results of the previous > > > >> tosses, which is an infinite tail of some sequence in 2^w. Now take > the > > > >> unique element from S associated to that tail, take the n'th element > of > > > >> that sequence from S, and deliver that as your move. > > > >> After some thinking, you will see that with this strategy, you're > indeed > > > >> certain to guess wrong at most finitely many times. > > > > >> Thanks, AC! Another nice mess you've gotten us into. > > > > > Note you can avoid AC, by defining > > > > a_n(m)= s(m) m>n, a_n(k) heads otherwise. > > > > What's s(m) ? > > > > As a matter of fact, what's a_n(m) ? > > > The game involves tosses and guesses, i.e. two sequences with one index: > > > toss(n), guess(n). > > > > -- > > > Cheers, > > > Herman Jurjus > > > s is the sequence of tosses, so s(n) = toss(n) > > > As above, a_n(m) is equal to the toss if m>n, otherwise > > is a head. Note that a_n is equal to s except perhaps on > > a finite set. > > > For any n, a_n(n) is heads, so guess(n)=a_n(n) is heads. > > > I don't think the fact that time is reversed has any > > real bearing on this. If the tosses are independent, perfect > > knowledge of the future is of no help for the present. > > > From the quoted page > > > Now, since the representative sequence and the actual > > sequence of heads and tails that occurs are in the same > > equivalence class, they must only differ at finitely many > > places. > > > Correct. Note this is true of sequence a_n. > > Yes, but there is not one sequence a_n, but rather one for every > n My notation is confusing as often "sequence a_n" means sequence a with nth term a_n. However by sequence a_n I mean a sequence (nth term a_n(n)). Sequences a_n and a_m may not be the same for n =/= m. I.e. there is a different sequence for every n. <snip> > > In the article, r(n) is just one sequence, and our g(n) = r(n) for all n. Yes and no. It does in fact follow that there is only one sequence r(n) and this is the key to the "paradox". However, my reading of the article was that it implied it was enough to take at each step, a sequence which differed from the sequence of tosses at only a finite number of points. As my example shows, this can be done without using AC and is not sufficient. However, to get a single sequence, r, we need to associate a representative element to each equivalence class. For this we need AC. However, I do not see any problem here and though the result of being able to choose (nonconstructively) a representative sequence may be seen as counterintuitive it is certainly no more so than the fact that a infinite set can be put in one to one correspondence with a subset. I am not sure to what extent the "reverse supertask" is of interest. Since it is impossible to start a game with no first move, talk of strategy is not very interesting. - William Hughes
From: Tim Little on 23 Nov 2009 23:29 On 2009-11-23, Herman Jurjus <hjmotz(a)hetnet.nl> wrote: > http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-result-of-infinitely-many-coin-tosses/ Yes; with weird premises of things like infinite supertasks and decision-making with uncountably infinite amounts of information, AC (among other things) implies some odd results. > I'm not sure yet what to conclude from it; that AC is horribly > wrong, or that WM is horribly right, or something else altogether. I'd conclude that weird premises result in weird conclusions. - Tim
From: Tim Little on 24 Nov 2009 00:42 On 2009-11-23, William Hughes <wpihughes(a)hotmail.com> wrote: > If you could start the game with only a finite number of wrong > guesses you are done. However, the game has no first move, so how > do you start? Indeed. That's one point where the premise is screwy to begin with. The same paradox is much better expressed in the "prisoners and hats" version. Although it has the same uncountably infinite information load, at least it has a beginning. - Tim
From: David C. Ullrich on 24 Nov 2009 06:39
On Mon, 23 Nov 2009 15:03:25 +0100, Herman Jurjus <hjmotz(a)hetnet.nl> wrote: >David C. Ullrich wrote: >> On Mon, 23 Nov 2009 12:22:17 +0100, Herman Jurjus <hjmotz(a)hetnet.nl> >> wrote: >> >>> Has anyone seen this before? >>> >>> http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-result-of-infinitely-many-coin-tosses/ >>> >>> I'm not sure yet what to conclude from it; that AC is horribly wrong, or >>> that WM is horribly right, or something else altogether. >>> >>> In short the story goes like this: >>> >>> A game is played, in which infinitely many coins are tossed, and there's >>> one player, who makes infinitely many guesses. Both are done over a >>> finite period of time. The tosses and guesses are not made faster and >>> faster, however, but slower and slower: at t = 1/n. There's no 'first' >>> move. >> >> In case I'm not the only one who couldn't figure out exactly what's >> going on from that paragraph, the description on the page seems >> more clear: >> >> "For each n > 0, at \frac{1}{n} hours past 12pm the following is going >> to happen: aware of the time, you are going to guess either heads or >> tails, and then I am going to flip a coin and show you the result so >> you can see if you are right or wrong. This process may have to be >> done at different speeds to fit it all in to the hour between 12pm and >> 1pm." >> >>> Claim: >>> There exists a strategy with which you're certain to guess all entries >>> correctly except for at most finitely many mistakes. Not 'certain' as in >>> 'probability is 100%', but absolutely certain. >>> >>> Reasoning: >>> On 2^w, consider the equivalence relation that makes x equivalent to y >>> when x(n) =/= y(n) for at most finitely many n. Next, using AC, create a >>> set S that contains precisely one element from every equivalence class. >>> Strategy: at every move, you already know the results of the previous >>> tosses, which is an infinite tail of some sequence in 2^w. Now take the >>> unique element from S associated to that tail, take the n'th element of >>> that sequence from S, and deliver that as your move. >>> After some thinking, you will see that with this strategy, you're indeed >>> certain to guess wrong at most finitely many times. >>> >>> Thanks, AC! Another nice mess you've gotten us into. >> >> I think the moral is not that AC leads to the weirdness but that >> this is a highly weird situation to begin with. At the time when >> we make any given guess we've already been told the result of >> infinitely many coin tosses... > >Yup - it's a game without a first move. So 'weird' is an accurate >qualification. Yet, it's not particularly difficult to give a >mathematical description of the situation, reason about it, and convince >ourselves that, mathematically, there's no problem with it. Ideally, it >should be much harder to make mathematical sense of a game like this. Why should this be hard? You wouldn't expect that being given infinitely much information would be very powerful? >That's why I included "WM is horribly right" as a possible moral. > >Apparently there's something wrong with backward supertasks (and not >with ordinary, 'forward' supertasks). But why should that be? David C. Ullrich "Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.) |