Axiom of Choice and Determinacy

In my set theory course we have been talking about the axiom of determinacy. One of the first things we showed was that $AD$ and $AC$ are incompatible. We later showed that $ZF+AD$ implies the consistency of ZFC by showing (in $ZF+AD$) that $\aleph_1$ is inaccessible in $L$.

This seems odd that $AD$ implies that $AC$ is false, but is consistent with $ZF$. I don’t have really a specific question, but was hoping for someone to explain why this isn’t really that odd. Or that it is odd, but is still ok. I feel like I understand the proofs of the statements, but it still doesn’t seem to fit together quite right for me.

Any thoughts would be appreciated, thanks!

Solutions Collecting From Web of "Axiom of Choice and Determinacy"

That $\mathsf{AD}$ holds means that every set of reals has a certain property (in this case, the associated Gale-Stewart game is determined). But recall that “Every set” means “every set, in the universe where the discussion takes place”. It may very well be that there are sets of reals that are not determined, but you are working in an inner model of the true universe, and do not see these sets. In fact, under appropriate large cardinal assumptions, in the set theoretic universe (where choice holds) we have that the inner model $L(\mathbb R)$ is a model of determinacy. Similarly, inside $L(\mathbb R)$ (or any model of set theory) we have $L$, which is always a model of choice. The constructible universe $L$ sees certain games and thinks they are not determined. This is simply because $L$ does not have all the reals, so it lacks some winning strategies. In fact, under the assumption that determinacy holds, $L$ only sees countably many reals. (Of course, $L$ “does not know this”. From the point of view of $L$ there are uncountably many reals, and any bijection between $\mathbb R^L$ and $\omega$ is not in $L$.)

Perhaps determinacy itself is too distracting an axiom for the issue here. All that is happening is that “truth” is relative to the universe of discourse, so it may very well be that, from the point of view of a certain inner model, we see a set and think it is not well-orderable. This does not mean it is not well-orderable in the universe of sets, simply that the model you are looking at does not contain any bijections between the set and an ordinal. In fact, in models of determinacy, $\mathbb R$ is not well-orderable. In any larger universe where we see a well-ordering of $\mathbb R$, we also see that many ordinals that in the model of determinacy we thought were cardinals actually are not, it is simply that in the determinacy model we did not have the bijections between these ordinals and smaller ones. Or, we may have a model that thinks that $V=L$, simply because it does not contain any sets not in $L$, but this does not mean that those sets are not present in the true universe.

One way of thinking about this is in terms of complexity: Sets in $L$ are “too simple”, so they cannot code certain bijections, for example, and it therefore looks as if some ordinals are cardinals, even large cardinals, while in the actual universe of sets they are countable. Sets in $L(\mathbb R)$ (under determinacy) are more “complex”, so we see many reals that $L$ lacked, coding elementary embeddings, or measures, or winning strategies, or homogeneous sets for partition relations, etc. But it may well be that sets in $L(\mathbb R)$ are also relatively simple compared with sets in the true universe, where we have well-orderings of the reals. Any such well-ordering is complex enough that from it we can define plenty of undetermined games, thus plenty of sets of reals, none of which is in $L(\mathbb R)$.

It is quite often that we can prove that if you have a set of axioms $\mathbb A$ and some additional axiom $A$, that if $\mathbb A+ A$ is consistent, then $\mathbb A + \lnot A$ is also consistent.

For example, in plane geometry, if $\mathbb A$ is all the usual axioms minus the parallel postulate, and $A$ is the parallel postulate, then in $\mathbb A+A$ we can construct internally a model for $\mathbb A+\lnot A$, implying that $\mathbb A+\lnot A$ is also consistent if $\mathbb A+A$ is consistent.

Clearly, $A$ and $\lnot A$ are incompatible – they are the extreme case of incompatibility.

Perhaps a simpler example would be to start with the bare bones Peano axioms, with just the single “successor” operator, $S(n)$, defined for every natural number $n$. Let $\mathbb A$ be the axioms other than the induction axioms, and let $A$ be the induction axiom scheme. ($A$ is not one axiom, really, but a collection of axioms…) Then if $\mathbb A+A$ is consistent, we can show that $\mathbb A+\lnot A$ is consistent. In this case, since $A$ is not an axiom, but a list of axioms, we’d just mean by $\lnot A$ that some element of the set of axioms $A$ is provably not true.

We do this by defining the operator $T(n)=S(S(n))$ and showing that $T$ satisfies all the axioms other than the induction axioms.

Basically, this means showing:

$$\forall n: S(S(n))\neq 0$$
$$\forall n,m: S(S(n))=S(S(m))\implies n=m$$

Then you have to show that there is some theorem that is true by induction but is not true if $S$ is replaced everywhere by $T$. A simple such proposition is:

$$\forall n: n=0 \lor \exists m: S(m)=n$$

This can be proven in $\mathbb A+A$, but is not true when $S(m)$ is replaced by $S(S(m))$, since $S(0)$ is a natural number, and $S(0)\neq 0$ and $S(0)\neq S(S(m)))$ for any $m$.

Here is a quick analogy, suppose that $\kappa$ is inaccessible. $2^\kappa=\kappa^{++}$ implies that $\sf GCH$ is false, but it also proves the consistency of $\sf GCH$.

Both $\sf AC$ and $\sf AD$ are additional axioms which extend the axioms of $\sf ZF$. Both are very strong and give you a lot of information, but at the same time both are incompatible.

Equally one could replace the above example with “$\mathcal P(\kappa)$ cannot be well-ordered“. This would be an axiom that proves that the axiom of choice as false, but $\kappa$ is still inaccessible in $L$ and therefore along with $\sf ZF$, this axiom proves the consistency of $\sf ZFC$.

Relative consistency is not direct implication, it’s a “workaround”. It means that given one universe of these axioms, we can generate a new universe of those axioms. Having a stronger consistency strength means that you can prove more. Often it means that you can prove the existence of a set which is a universe of a certain theory. $\sf ZFC$ cannot prove the existence of a set model, but $\sf ZF+AD$ can.