Counterintuitions and the well-ordering theorem
in [Logic]
|
Prev: Solutions manual to Entrepreneurship 1e Bygrave Zacharakis
Next: Solutions manual for Engineering Mechanics Statics (12th Edition) by Russell C. Hibbeler
From: Herman Jurjus on 28 Oct 2009 08:52 Aatu Koskensilta wrote: > There are certainly games for which this > quantifier switch isn't valid (and I'm still bewildered by your > suggestion this is an instance of failure of the law of excluded > middle), so any argument or explanation for the evidence of AD must > depend in an essential way on the games being subsets of the Baire space > of descriptive set theory. (The following won't convince Aatu, but i post it anyhow, for other readers, who perhaps are also puzzled why LEM was brought up.) Indeed, someone who considers AD to be true seems to be excluding 'too badly behaved' sets from set theory. Alternatively, however, he could hold that these complex sets do exist, but LEM fails for them. I.e. that "forall x in w^w [ x in A or x not-in A ]" is not true for them (true for Borel sets, etc., but not for all sets in general). By dropping LEM for non-Borel sets in this way, things suddenly start to make much more sense to me. Because you can still have the 'either player 1 can win, or player 2 can prevent 1 from winning' - but the defense is not necessarily a winning strategy for player 2 - the game is no longer one that satisfies the condition that 'at the end of the game, either player 1 has won or he has not'. (Anyway - just for what it's worth.) -- Cheers, Herman Jurjus
From: Daryl McCullough on 28 Oct 2009 09:00 Aatu Koskensilta says... >A very simple reason to be suspicious of AD is that it amounts to a >strong form of quantifier switch that is in general not valid. That's what I was arguing. >I really couldn't make anything of your comments about the law of excluded >middle, which isn't involved. Well, I think I can understand why it *seems* like excluded middle might be involved. Let W be a set of sequences of naturals. To say that the first player can force a win is to say, informally, that there is a move by the first player such that for any move of the second player, there is a countermove by the first player such that, blah, blah. We can introduce a notion of "infinitely many quantifiers" to express this: Ex_1 Ax_2 Ex_3 ... [x_1, x_2, ...] in W I haven't said what this notation means, precisely, but you should have a fuzzy notion of what it might mean. Using the same ... notation, we can express "the second player can force a win" as: Ax_1 Ex_2 Ax_3 ... [x_1, x_2, ...] not in W These two statements *appear* to be negations of each other, if we sloppily assume that the De Morgan's laws apply to infinitely many quantifiers. So, the law of excluded middle seems to say that one or the other must be the case. Of course, this depends on giving a precise semantics to infinitely many quantifiers, which I haven't done. To me, to say that something is intuitively true, but not provable, means that there actually is a sloppy proof, which possibly glosses over distinctions and subtleties. There is another point to be made about strategies and quantifiers. As Butch pointed out, even for a *single* alternation of quantifiers, the equivalence of Ax_1 Ex_2 [x_1, x_2] not in W and Ef Ax_1 [x_1, f(x_1)] not in W depends on the axiom of choice, in general. So if AD involves *denying* the axiom of choice, then we shouldn't accept alternations of quantifiers as meaning the same thing as the existence of strategies (represented as functions). So maybe there is a meaning of the infinite quantifier case Ax_1 Ex_2 ... [x_1, x_2, ...] not in W that is *not* equivalent (without choice) to "there is a winning strategy (in the sense of function) for the second player". -- Daryl McCullough Ithaca, NY
From: Herman Jurjus on 28 Oct 2009 09:07 Aatu Koskensilta wrote: > Rupert <rupertmccallum(a)yahoo.com> writes: > >> When I first read about AD I thought it was an interesting hypothesis, >> but I never had any feeling that it was intuitively plausible. On the >> other hand as soon as I encountered AC I was completely convinced that >> it was true. > > Our agreement on these matters is most touching. Let's hug! Before we do > that, I'll divulge the following piece of information about my personal > history: when I first encountered determinacy, it immediately struck me > as obviously false. Lo and behold: that was also my first reaction, many years ago. Must be a coincidence. -- Cheers, Herman Jurjus
From: Daryl McCullough on 28 Oct 2009 09:07 Herman Jurjus says... > >Daryl McCullough wrote: >> Herman Jurjus says... >> >>> But: either player 1 has a winning strategy or he hasn't. >>> Now what does it mean for player 1 to not have a winning strategy? >>> >>> I'd say that amounts to 'player 2 has some way to prevent player 1 from >>> winning'. >> >> But that isn't an accurate paraphrase. > >I agree that that's a shady part. And of course there's not much more i >can say. ZFC+AD is inconsistent, so the burden is on me to analyze my >intuitions further before saying anything more. > >> That's the reason I >> brought up rock/paper/scissors. > >Ah. You think that that analogy is good, but i think it isn't. It's a completely airtight argument that the *lack* of a strategy for one player does not imply (without additional assumptions) the existence of a strategy for the other player. What are those additional assumptions? >If it were, it should be piece-a-cake to come up with a counterexample >of AD. No, that doesn't follow. It's not an argument that AD is *false*. It shows that the argument *for* it uses an invalid principle: "If there is no winning strategy for the first player, then there must be a winning strategy for the second player". That's true for some types of games, and false for other types of games. So it can't be used as a general principle. -- Daryl McCullough Ithaca, NY
From: Herman Jurjus on 28 Oct 2009 09:21
Daryl McCullough wrote: > Herman Jurjus says... >> Daryl McCullough wrote: >>> Herman Jurjus says... >>> >>>> But: either player 1 has a winning strategy or he hasn't. >>>> Now what does it mean for player 1 to not have a winning strategy? >>>> >>>> I'd say that amounts to 'player 2 has some way to prevent player 1 from >>>> winning'. >>> But that isn't an accurate paraphrase. >> I agree that that's a shady part. And of course there's not much more i >> can say. ZFC+AD is inconsistent, so the burden is on me to analyze my >> intuitions further before saying anything more. >> >>> That's the reason I >>> brought up rock/paper/scissors. >> Ah. You think that that analogy is good, but i think it isn't. > > It's a completely airtight argument that the *lack* of a strategy > for one player does not imply (without additional assumptions) the > existence of a strategy for the other player. What are those > additional assumptions? No hidden moves (where this includes 'adjourned' moves and simultaneous moves), no chance-moves. -- Cheers, Herman Jurjus |