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