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: Bill Taylor on 29 Oct 2009 22:10 stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > In a finite game, we can always in theory work backwards from > a winning position. Let W_0 be the set of winning positions > for the first player. Back up two moves and let W_1 be the > set of positions such that there is a move by the first player > such that no matter what countermove the second player makes, > he will end up in a position in W_0. Keep backing up to form > W_0, W_1, W_2, etc. > > Now, let W = the union of all the W_i. This is the set of all > positions such that it is possible for the first player to force > a win, starting in that position. If the starting position is included > in set W, then the first player can force a win. If not, then the > second player can *avoid* the positions in W. In other words, the > second player can avoid losing. But in a finite game, if the > second player avoids losing for long enough, then he wins. That is a wonderfully succinct way of writing up this classic backwards induction! > This argument doesn't work for infinite games, because > there is no way to "back up" from a winning position. Quite so! The situation is somewhat parallel to the case where AC can be proved for finite sets, but not for infinite ones, though we take the finite case as powerful evidence to support our intuitions of the infinite. -- Back-to-front Bill
From: Daryl McCullough on 29 Oct 2009 22:30 Bill Taylor says... > >> > choice seems to strike many as evident, both in the sense people >> > explicitly state so >> >> Might i humbly suggest that that is explainable by the fact that many >> people are confronted with choice in the earliest stages of their >> studies, and not with AD? > >Another contributing factor being that almost all students are >introduced to it, motivated to it, by thoughts of making an infinite >sequence of choices. This convinces them of the common sense >of Countable Choice, which is a far less questionable assumption >than Wholesale Choice. Then the latter is slipped in more or >less surreptitiously alongside the former. I don't think psychological or familiarity explains why people adopt choice. People assume the axiom of choice because reasoning without is an incredible pain. For example, without choice, we can't reason about cardinality based on bigger/smaller. There are many different notions of cardinality that are *inequivalent*: X < Y can be defined by the existence of an injection from X to Y, or the existence of a surjection from Y to X, and the two definitions are inequivalent. You can't prove things for all elements of a set by well-ordering them and using (ordinal) induction. Various definitions of "finite" become inequivalent (Dedekind finite versus Tarski finite). We can't reason from "A_i is a family of nonempty sets" to "the cross-product A_0 x A_1 x A_2 ... is non-empty. Reasoning without choice is a pain. Things become much complicated, and seemingly not in an interesting way. -- Daryl McCullough Ithaca, NY
From: Bill Taylor on 29 Oct 2009 22:33 Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > 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 is quite correct. That is why Daryl's infinite-depth quantifier argument is so telling - everything in it appears to be valid, on the face of it; (obviously ignoring the ugly feature that we have no formalism for it as yet!!) > (I really couldn't make anything of your comments about > the law of excluded middle, which isn't involved.) Well actually it is, as I think Daryl may have observed. If he didn't, I'll do it myself later. > my grasp of the conceptual picture involved. (This is of course a very > boring observation, since it amounts to merely stating I conceive of > sets in such a manner as to make choice a triviality. This is a very astute observation!! I have read, here and there, the arguments in favour of general AC, on the basis of sets being regarded "as a combinatorial concept", whatever that may mean. Well, if you look into it carefully, and see just what it is expected to mean, it turns out that what it means is most accurately summed up by saying that AC always applies! Didactically, one variant of an informal idea is being used to support a differently-worded variant! HUH!! > Those who declare that choice, powerset, > etc. aren't evident aren't presumably objecting to this, but to the > conception involved itself, finding it "vague", "indeterminate", > "theological", and so on. Yes indeed, any or all of those terms could be applied. The key is that things are being declared so, *by fiat*, when there is some "legitimate" doubt that they exist, in whatever sense math objects exist at all. The other axioms - pairs, unions, separation, finitely depthed cross-products (in the absence of Powerset), and even Replacement do not suffer the same objection, they are essentially just "book-keeping" axioms, asserting that we can do what we've already been doing for ages. They are not essentially creative, like the other lot (including even powerset). It all rather reminds one of Russell's saying that, "Postulation has all the advantages over construction that theft does over honest toil!" OC, the whole of C20 math, even math in general, is to make things as SLICK and UNIFIED as possible. But that may have led us, unwittingly, onto a slippery slick slope. > Göran Sundholm once put it to me, that "There's too much > slack in the classical 'meaning explanation' for set theoretic talk".) This sounds very interesting indeed! Could you please elaborate on this idea, Aatu - it would be a very great favour to many of us! > And, Maddy's articles on set theoretic axioms haven't lost any of > their currency by being less current owing to the passage of time.) And if we're quoting the authority of giants, let me also recall the mighty Dana Scott's mournful lament at the end of his much-overlooked but should-be-seminal paper on constructing sets by "Stages" - where he wails:- "If only there were an equally obvious way of deriving AC from these considerations!" -- Tiny Taylor
From: Bill Taylor on 29 Oct 2009 22:40 Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > > Well, don't look at me; i said right from the start that both AD and > > AC are evidently true. > > What do you mean by this? On the face of it, it makes about as much > sense as thunderously declaiming that there are infinitely many twin > primes but there are only finitely many twin primes. Hardly an apt parallel! Twin primes is an arithmetical statement, and thus has some kind of "absolute character", regarding its meaning and truth. (This belief, or at least stance, is essentially what makes us mathematicians in the first place!) The same does NOT apply to infinite set theory. You can say whatever you like about that, especially if it has no arithmetical consequence. As I said before, one can adopt any of AC, ~AC, AD, CH, Suslin, etc, and prove whatever you like, secure in the knowledge that the contrary can NOT be proved without all these. Care must be taken with contradictory assumptions, of course! I think this idea might lie behind Herman's otherwise ludicrous-sounding declaration. But you'd have to check with him - I may have got him all wrong. -- Wrong-enough William
From: Daryl McCullough on 29 Oct 2009 22:41
Bill Taylor says... > >stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > >> I don't understand why you think that "all games are determined" is >> intuitively true. > >You gave the answer yourself, in terms of infinite-depth quantifiers. But I really don't have an intuition about what infinitely many alternations of quantifiers *mean*, unless I can do the Skolem trick of replacing them by a single quantifier over strategies. That trick is only valid if we assume choice. >> It's not *obvious* that chess or checkers has a >> winning strategy; it's *provable*. > >It IS. (That is, a winning strategy or a drawing strategy for both.) > >This just plain OBVIOUS to any game player. As I said, I can see that it is obvious from the point of view of "backing up" from a winning position, but that only makes sense for finite games. >It was obvious to me even before I started high school. I'm sure you never played infinite games before high school. >>To prove it, you have to use the >> fact that they are finite-length games > >Yes, the proof requires finitude, but the intuition does NOT. I don't agree. Once you introduce infinite games, the intuition disappears completely for me. I know that some things that are true for finite objects are not true for infinite objects, and I have absolutely no reason to think it's not the case for determinacy. >Again, consider your own i-d quantifiers! That's a *notation*. Nothing follows from a notation. Using infinite quantifiers, we can't (as far as I know) make the distinction between "Player 1 has no winning strategy" and "Player 2 has a winning strategy". It's not expressive enough to make that distinction. But that doesn't mean anything, other than we chose a notation that is only appropriate for determined games. -- Daryl McCullough Ithaca, NY |