Another AC anomaly?
in [Logic]
|
From: Butch Malahide on 23 Nov 2009 18:20 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".
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 |