From: Mike Oliver Subject: Re: Continued fractions vs. real numbers Date: Wed, 26 Jan 2000 17:50:45 -0800 Newsgroups: sci.math Summary: What is the "Axiom of Determinacy"? munafo@gcctech.com wrote: > But what > is "AD"? Algorithmic Determinacy? It stands for "Axiom of Determinacy". As you will have been able to deduce from what I wrote previously, it's inconsistent with ZFC ( which is ZF+AC; AC is the Axiom of Choice). ZF+AD, however, is not (known to be) inconsistent. I don't know how much you know about determinacy so I'll start from ground zero. A "game of perfect information" is a game, like chess, in which the players move alternately and each player knows all previous moves, the state of the game, and the precise winning conditions. For any such game which is *finite* in the sense that it must terminate after finitely many moves, and in which there are no draws, it is easy to see that one player or the other must have a *winning*strategy*; i.e. a function that looks at the moves played so far and suggests a move, such that if you always accept the suggestion, you are guaranteed to win. A game in which one player or the other has a winning strategy is called *determined*; what I've said so far is that all finite games are determined. When you move to infinite games the situation becomes more complicated and more interesting. We can characterize one large class of games in the following way: Suppose A is a set of real numbers. Then we consider the game G_A, which is played as follows: Player I selects a digit from 0 to 9, which we'll call a_0 Player II selects a digit from 0 to 9, which we'll call a_1 Player I selects a_2 Player II selects a_3 ... The players play forever, selecting a_n for every natural number n. Then we look at the real number between 0 and 1 formed by putting all the a_n's after the decimal point: 0 . a_0 a_1 a_2 a_3 a_4 ... Then player I wins if this number is an element of our pre-chosen set A; otherwise player II wins. The Axiom of Determinacy is the statement that for every set of real numbers A, the game G_A is determined (i.e. either player I or player II has a winning strategy). Note that the winning strategy does not need to be in any way computable; it only has to exist.