From: ross@math.hawaii.NOSPAM.edu (D. Ross) Subject: Re: Axiom of Choice Date: Mon, 12 Feb 2001 00:43:49 GMT Newsgroups: sci.math Summary: Axiom of Determinacy and Solovay's work on its consistency J.Mycielski, H.Steinhaus. A mathematical axiom contradicting the axiom of choice. "Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys.", 1962, vol. 10, pp. 1-3 (Also many later articles by Mycielski and others - I think it is discussed in the Handbook of Mathematical Logic as well.) Essentially says that all games (in the sense of Gale/Stewart) are determined, i.e., one player or the other has a strategy. Contradicts V=L and AC - in particular, there is a relatively easy proof from it that all subsets of R are are Lebesgue measurable. - David R. Stephen Montgomery-Smith wrote: | Herman Rubin wrote: | > | > If the Axiom of Determinateness is consistent, and most | > believe it is, no such set could be explicitly given. | > | | What is the axiom of determinateness? | | -- | Stephen Montgomery-Smith | stephen@math.missouri.edu | http://www.math.missouri.edu/~stephen ============================================================================== From: hrubin@odds.stat.purdue.edu (Herman Rubin) Subject: Axiom of Determinateness Was: Re: Axiom of Choice Date: 12 Feb 2001 20:40:34 -0500 Newsgroups: sci.math In article <3A86B95F.9BEF4583@math.missouri.edu>, Stephen Montgomery-Smith wrote: >Herman Rubin wrote: >> If the Axiom of Determinateness is consistent, and most >> believe it is, no such set could be explicitly given. >What is the axiom of determinateness? Consider the game where the players alternately put down bits in a binary expansion (or digits in a decimal expansion). each knowing what has gone before. So this is a game of perfect information. Player I tries to get the final real number in a set A, and Player II in its complement. Finite games of perfect information have values, and the players have good strategies. Banach and Mazur showed (actually for a somewhat different game) that the Axiom of Choice implies there are such games which are undecidable; these use "nasty" sets. Myczielski(sp?) and Steinhaus proposed instead the axiom that all such games have values, and the winning player has a good strategy. This axiom is adequate for countable dependent choice, needed for much of analysis, and guarantees all subsets of the reals are Lebesgue measurable. Solovay has shown that the consistency of AD is equivalent to that of a measurable cardinal; we know that this cannot be proved if set theory is consistent, as it would enable the proof of the consistency of set theory within itself. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 ============================================================================== From: Fred Galvin Subject: Re: Axiom of Determinateness Was: Re: Axiom of Choice Date: Mon, 12 Feb 2001 21:52:42 -0600 Newsgroups: sci.math On 12 Feb 2001, Herman Rubin wrote: > Banach and Mazur showed (actually for a somewhat different > game) that the Axiom of Choice implies there are such games > which are undecidable; these use "nasty" sets. Myczielski(sp?) Mycielski. > Solovay has shown that the consistency of AD is equivalent to > that of a measurable cardinal; we know that this cannot be > proved if set theory is consistent, as it would enable the > proof of the consistency of set theory within itself. If I remember right, Solovay proved that AD is *stronger* than a measurable cardinal. -- It takes steel balls to play pinball. [quotes of previous message trimmed --djr] ============================================================================== From: Mike Oliver Subject: Re: Axiom of Determinateness Was: Re: Axiom of Choice Date: Mon, 12 Feb 2001 20:00:22 -0800 Newsgroups: sci.math Fred Galvin wrote: > > On 12 Feb 2001, Herman Rubin wrote: >> Solovay has shown that the consistency of AD is equivalent to >> that of a measurable cardinal; we know that this cannot be >> proved if set theory is consistent, as it would enable the >> proof of the consistency of set theory within itself. > > If I remember right, Solovay proved that AD is *stronger* than a > measurable cardinal. I don't know exactly what Solovay proved a proposito, but AD is quite a bit stronger than a measurable cardinal. In fact, ZF+AD is equiconsistent with ZFC+"there exist infinitely many Woodin cardinals". I'm not going to go into exactly what a Woodin cardinal is, but a number of distinct steps can be identified above measurable and below Woodin. (BTW the first Woodin cardinal is not itself measurable. It is however a stationary limit of measurables.) ============================================================================== From: Mike Oliver Subject: Re: Axiom of Choice Date: Tue, 13 Feb 2001 02:05:29 -0800 Newsgroups: sci.math Mike Oliver wrote: > If you strengthen the notion of "give explicitly" to require > the existence of a proof in ZF (rather than ZFC) that the > set is nonmeasurable, then we can get by with much less; the > consistency of a single inaccessible is enough, using the > Solovay model. I wouldn't be surprised if the plan of > the above two paragraphs could be adapted to the Solovay > model to show that a single inaccessible is enough even > if we're allowed to prove nonmeasurability in ZFC. OK, figured it out (actually, I think this has come up before; perhaps what I did was remember it). Yes, a single inaccessible is enough to show that no definable set of reals can be proved in ZFC to be nonmeasurable. The proof is the same as in the previous article, except substituting "measurable" for "determined". I.e., start with M equals the Solovay model, in which all sets of reals are measurable. Restrict down to L(R)^M. If S is a set of reals in L(R)^M, then S is Lebesgue measurable in M. The fact that it's measurable, however, can be expressed quantifying only over reals; therefore, S is also measurable in L(R)^M. Now as before, force inside L(R)^M to add a wellorder of R, obtaining a generic extension N which is a model of ZFC, and such that HOD(R)^N = HOD(R)^{L(R)^M} = L(R)^M. Now N satisfies that every set of reals in HOD(R) is Lebesgue measurable. The only remaining little doubt in my mind is whether it's really true that when you force inside L(R) with countable partial bijections between Aleph_1 and R, you really do preserve HOD(R). I haven't checked that but I think it should be right. ============================================================================== From: Martin Goldstern Subject: Solovay's models Date: 14 Feb 2001 14:49:55 GMT Newsgroups: sci.math Mike Oliver wrote: : OK, figured it out [...] Yes, a : single inaccessible is enough to show that no definable : set of reals can be proved in ZFC to be nonmeasurable. : The proof is the same as in the previous article, except : substituting "measurable" for "determined". I.e., start : with M equals the Solovay model, in which all sets of : reals are measurable. : [construction omitted] The construction is probably correct, but not necessary. "The Solovay model M" was originally obtained as a substructure of a model N of "ZFC + all definable sets are measurable" . (Where "definable" means: definable from an omega-sequence of ordinals) In his famous paper (Annals of Math, 1970), Solovay *first* constructs N by Levy-collapsing an inaccessible, and then finds M as the set of all hereditarily definable sets inside N. "Two days of research can easily save you 10 minutes in the library." (ok, I admit that finding things on your own can be more fun...) -- Martin.Goldstern@tuwien.ac.at ============================================================================== From: AndrEs Eduardo Caicedo Subject: Re: Axiom of Determinateness Was: Re: Axiom of Choice Date: Sat, 17 Feb 2001 00:36:13 -0800 Newsgroups: sci.math > On 12 Feb 2001, Herman Rubin wrote: > > > In article <3A86B95F.9BEF4583@math.missouri.edu>, > > Stephen Montgomery-Smith wrote: > > >Herman Rubin wrote: > > > > >> If the Axiom of Determinateness is consistent, and most > > >> believe it is, no such set could be explicitly given. > > > > > > >What is the axiom of determinateness? > > > >[ ... ] > > > Solovay has shown that the consistency of AD is equivalent to > > that of a measurable cardinal; we know that this cannot be > > proved if set theory is consistent, as it would enable the > > proof of the consistency of set theory within itself. No. Solovay showed that the consistency of "All sets of reals are Lebesgue measurable" (which I think is why 'determinateness' was first mentioned in this tread) is at most that of an inaccessible cardinal. Way, way below a measurable. He also showed that aleph_1 and aleph_2 are measurable if AD holds. In AD models choice fails, but by passing to an appropriate inner model of choice, this gives that AD is indeed stronger than a measurable cardinal. BTW, the standard usage nowadays is 'determinacy', not 'determinateness'. AndrEs