From oliver@math.ucla.edu Sat Feb 10 17:29:33 1996 Date: Sat, 10 Feb 96 14:29:27 PST From: Mike Oliver To: rose@garnet.acns.fsu.edu Subject: Re: axiom of determinacy Newsgroups: sci.logic Organization: UCLA Mathematics Department Cc: oliver@math.ucla.edu In article <4fg0n8$45j@news.fsu.edu> you write: >The Axiom of Determinacy is said to be an alternative axiom to the axiom >of choice. Exactly what does the axiom of determinacy claim? Let A be a set of omega-sequences of natural numbers. Given any such A, the game G_A for two players is as follows: Player I names a natural number, then player II names a natural number, then player I again, and so on. At the end (i.e. the first point at which both players have named infinitely many numbers), you examine the omega-sequence of natural numbers given by: I's first move, followed by II's first move, followed by I's second move, etc. If this sequence is in the set A, then player I has won; otherwise player II has won. The game G_A is said to be *determined* if either player I or player II has a strategy that is guaranteed to win. Notice that a "strategy" does not have to be given by any definable rule; it's simply a function that, given a position in the game, returns a move. A strategy is "winning" if you are guaranteed to win when you play that strategy, regardless of what your opponent plays. The Axiom of Determinacy says that for *any* set A of omega-sequences of natural numbers, G_A is determined. From rar@csla.csl.sri.com Fri Feb 9 20:00:10 1996 Date: Fri, 9 Feb 1996 16:59:52 -0800 (PST) From: Bob Riemenschneider To: rose@garnet.acns.fsu.edu (Kermit Rose) In-reply-to: rose@garnet.acns.fsu.edu's message of 9 Feb 1996 17:36:40 GMT Subject: axiom of determinacy In article <4fg0n8$45j@news.fsu.edu> rose@garnet.acns.fsu.edu (Kermit Rose) writes: > The Axiom of Determinacy is said to be an alternative axiom to the axiom > of choice. Exactly what does the axiom of determinacy claim? (The following is cribbed from Moschovakis' _Descriptive Set Theory_, which is where you want to go for more details.) Let X be a fixed nonempty set. The two person game on a set A of sequences from X of length omega is played as follows: Players I and II take turns choosing members of X, for omega rounds. That is, I chooses a_0 from X, then II chooses a_1 from X, then I chooses a_2, and so on. Player I wins the game if the resulting sequence a = is in A; if it isn't, then player II wins. A strategy for player I is a function s from the finite sequences of members of X that have even length to members of X. To say that player I follows strategy s means that, when the play so far has produced the finite sequence , player I always chooses s() for a_2i. Similarly, a strategy for player II is a function from odd-length finite sequences to X. Strategy S is a winning strategy for player I if, by following s, (s)he will win no matter what choices II makes. Similarly, s is a winning strategy for player II if, by following it, (s)he will always win. A game is determined if one of the two players has a winning strategy. A set is determined if the game on that set is determined. The axiom of determinacy (AD) says that every subset of natural numbers is determined. Any subset of the natural numbers you can "write down" is determined, but it follows from the axiom of choice (AC) that some subsets are not determined. AD has some nice consequences -- all pointsets are measurable, have the property of Baire, etc., if AD is true -- so nice that some people looked at it very seriously 20 to 30 years ago. But I think most everyone would now agree with Moschovakis' assessment: Mycielski and Steinhaus [1962] suggested that we replace the (true) axiom of choice by the (false) hypothesis AD in our development of ordinary mathematics: our results must then be interpreted in some universe of sets smaller than the usual collection of all sets (where AD fails and AC holds). -- rar