I know what axiom of determinacy is, but I am having a hard time finding out information regarding AD+. Wikipedia page seems a lot confusing and Jech's set theory book does not seem to have AD+, though as I did not read everything in the book, I am unsure if this really is the case. Can anyone present what exactly AD+ is? Is it just a slight extension of AD, and therefore goes against axiom of choice?

  • 1
    $\begingroup$ It is an extension of the axiom of determinacy, yes. Therefore it contradicts the axiom of choice. $\endgroup$ – Asaf Karagila Mar 28 '14 at 1:20
  • $\begingroup$ You might want to read Koellner-Woodin's chapter in the Handbook of Set Theory. In particular Definition 8.10. $\endgroup$ – Asaf Karagila Mar 28 '14 at 1:27
  • 1
    $\begingroup$ Note that the second clause of the definition in the Wikipedia article implies the Axiom of Determinacy (consider $\lambda = \omega$ and $\pi$ to be the identity function): en.wikipedia.org/wiki/AD%2B $\endgroup$ – tci Mar 28 '14 at 1:59

$\mathsf{AD}^+$ is an extension of the axiom of determinacy, due to W. Hugh Woodin. The axiomatization is somewhat technical. Before I state it, let me explain the motivation:

The first wave of results under determinacy focused on its consequences for the model $L(\mathbb R)$. It became clear that some of those results generalized to other models (of the form $L(A,\mathbb R)$) as long as these models had some of the "fine structure" that (provably in $\mathsf{ZF}$) the model $L(\mathbb R)$ has. Actually, some of this fine structure turned out to be provable from strong versions of determinacy. Many results began to appear not confined to $L(\mathbb R)$ but instead under the assumption of $\mathsf{AD}_{\mathbb R}$, the version of determinacy where players use reals as moves rather than integers. This version fails in $L(\mathbb R)$, but several of these consequences were known in $L(\mathbb R)$ under $\mathsf{AD}$. Trying to reconcile these two lines of argument, it became apparent that in many cases rather than $\mathsf{AD}_{\mathbb R}$, what was really being used was the existence of certain "scales" or Suslin representations.

The idea became clear that the right set of assumptions was not $\mathsf{AD}$ in $L(\mathbb R)$, but instead "determinacy within scales". There followed a period (probably ten to fifteen years, but I am not clear on that) where different axiomatizations were suggested, trying to formalize this theory. What we now call $\mathsf{AD}^+$ is the final version of these suggestions.

My paper with Richard Ketchersid listed below contains a long discussion of this motivation, and an introduction to the axiom that I think you will find useful.

Andres Caicedo, and Richard Ketchersid. A trichotomy theorem in natural models of $\mathsf{AD}^+$. In Set Theory and Its Applications, Contemporary Mathematics, vol. 533, Amer. Math. Soc., Providence, RI, 2011, pp. 227-258. MR2777751.

Over the base theory $\mathsf{ZF}$, the axiom $\mathsf{AD}^+$ is the conjunction of the following:

  • $\mathsf{DC}_{\mathbb R}$.
  • All sets of reals are $\infty$-Borel.
  • $<\Theta$-ordinal determinacy, i.e., all $(A,f)$-induced games on ordinals $\lambda<\Theta$ are determined, for any $A\subseteq\mathbb R$ and any continuous $f:\lambda^\omega\to\mathbb R$.

Here, $\mathsf{DC}_{\mathbb R}$ is unfortunate notation for what should more properly be called $\mathsf{DC}_\omega(\mathbb R)$. This the statement that whenever $R\subseteq\mathbb R^2$ is such that for any real $x$ there is a $y$ with $x\mathrel{R}y$, then there is a function $f:\omega\to\mathbb R$ such that for all $n$, we have $f(n)\mathrel{R}f(n+1)$. This can also be stated as saying that any tree $T$ on (a subset of) $\mathbb R$ with no end nodes has an infinite branch.

This is a choice principle. It is stronger than countable choice for sets of reals, which is an easy consequence of $\mathsf{AD}$. The stronger principle we assume here (dependent choice for sets of reals) is a consequence of determinacy in $L(\mathbb R)$, as first proved by Kechris.

It is a bit delicate to explain what $\infty$-Borel is. A simple description is that when forming the Borel sets, we start with the open sets of reals, and close under the operations of complementation and countable union. Here, instead of countable, we allow instead arbitrary (well-ordered) unions. Actually, without choice, this is a bit unsatisfactory, since a set could be $\infty$-Borel without us having a way of "verifying" this. For instance, in a famous model of Feferman and Levy, the reals are a countable union of countable sets, but we have no way of assigning to each of these countable sets an enumeration simultaneously (of course, there are enumerations for each of them, what we cannot do is find a sequence whose $n$th term is an enumeration of the $n$th set). Similarly, we could have a set to be union of sets, each of which we know is $\infty$-Borel, without it being possible for us to exhibit simultaneously why each of these sets is indeed $\infty$-Borel. For this reason, instead of the sets, we use "codes", and what we require is that all sets of reals have a code. The code is essentially a witness to the fact that the set is $\infty$-Borel: A labelled tree whose nodes tell us precisely what open sets are used in what unions, what complements are formed, etc, until we reach the set in question. There are different formalizations of this idea, and the paper presents them in detail. Each formalization gives rise to a hierarchy of sets of reals, stratified in various $\kappa$-Borel sets, for each well-ordered cardinal $\kappa$. Different authors prefer different formalizations of the hierarchy, and so there is no universal consensus on what precisely $\kappa$-Borel means (as the hierarchies do not match up level by level).

Above, $\Theta$ denotes the supremum of the ordinals onto which $\mathbb R$ can be mapped surjectively. An early result in the theory of determinacy in $L(\mathbb R)$, due to Kechris-Kleinberg-Moschovakis-Woodin, shows that if $\lambda<\Theta$, games on ordinals below $\lambda$ with payoff Suslin-coSuslin are determined. Here, a subset of $\lambda^\omega$ is coSuslin iff its complement is Suslin, and the set $A$ is Suslin iff for some cardinal $\kappa$, $A$ is the first coordinate projection of a closed subset of $(\lambda\times\kappa)^\omega$, where $\lambda\times\kappa$ carries the discrete topology, and the product carries the product topology. Over $L(\mathbb R)$, this can be restated as the third clause above (for further details, I refer you to my paper with Richard. The point is that there is a continuous reduction of these games to games whose payoff is a set of reals, and so we can transfer the determinacy of one to the determinacy of the other). This clause proves a really useful tool in establishing combinatorial consequences of determinacy, such as the existence of partition cardinals. Note that it also implies the usual $\mathsf{AD}$ in particular (and therefore it is incompatible with choice). Other applications are more technical, via what we call generic coding.

The above does not quite help see why the theory $\mathsf{AD}^+$ is so useful, but I hope that reading the introduction and section 2 of my paper with Richard may clarify this. What we explain there is that if $M\subseteq N$ are transitive models of $\mathsf{AD}$ with the same reals (that is, the same $\omega^\omega$), and all sets of reals in $M$ are Suslin in $N$, then $\mathsf{AD}^+$ holds in $M$. In fact, it is not necessary that the same $N$ sees that all sets of reals of $M$ are Suslin, it suffices that for each set of reals of $M$ there is such an $N$. What became apparent when these matters were first being studied is that often we do not need the Suslin representation (the closed set, given by a tree, whose projection is the set in question), but rather, some consequences of the existence of the representation are enough to establish many of the properties one is after. And what Woodin realized is that the three consequences that make up $\mathsf{AD}^+$ are really all that is needed to carry out the detailed analysis that was previously only available in $L(\mathbb R)$.

Beyond this, let me add that it is an open problem whether $\mathsf{AD}^+$ already follows from $\mathsf{AD}$. Our tools for producing models of determinacy actually give us models of $\mathsf{AD}^+$, and all "natural" models of determinacy that we can study in reasonable detail actually satisfy the (apparently) stronger version.

  • $\begingroup$ I knew that if I waited long enough you'd write an excellent answer. Two points: (1) You have a small inaccuracy in the definition of $\sf DC_\omega(\Bbb R)$ with trees, it should be a tree on a set of reals, rather than all the real line; (2) In the Feferman-Levy model we can assign each of the countable sets an enumeration, but we can't do it uniformly for all them, and the way you wrote it can be interpreted the wrong way. $\endgroup$ – Asaf Karagila Mar 28 '14 at 2:44
  • $\begingroup$ Hi Asaf. Re (1), yes, that's what I meant: By a tree on $A$ I just mean a tree ordering on a subset of $A$ -- this may even be the standard usage. Anyway, I clarified (1) and (2). Thanks. $\endgroup$ – Andrés E. Caicedo Mar 28 '14 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.