Intereting Posts

If $a$ is a quadratic residue modulo every prime $p$, it is a square – without using quadratic reciprocity.
A problem on range of a trigonometric function: what is the range of $\frac{\sqrt{3}\sin x}{2+\cos x}$?
What is the smallest square into which one can pack a trisected disc?
The big O notation
Proving by induction that $2^n \le 2^{n+1}-2^{n-1} – 1$ . Does my proof make sense?
What is the degree of the zero polynomial and why is it so?
Why does the largest Jordan block determine the degree for that factor in the minimal polynomial?
Localisation is isomorphic to a quotient of polynomial ring
What is the value of $\int_0^1 \frac{\arctan x}{1+x^{2}} dx$?
Find area bounded by two unequal chords and an arc in a disc
Least Upper Bound Property $\implies$ Complete
Connected Implies Path (Polygonally) Connected
line at infinity
Is $\left|\,_4F_3\left(\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5};\frac{1}{2},\frac{3}{4},\frac{5}{4};\sqrt{\phi }\right)\right|$ a radical?
Evaluating $\int{\frac{1}{\sqrt{x^2-1}(x^2+1)}dx}$

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!

- Mathematical questions whose answer depends on the Axiom of Choice
- Relationships between AC, Ultrafilter Lemma/BPIT, Non-measurable sets
- Can the generalized continuum hypothesis be disguised as a principle of logic?
- Without AC, it is consistent that there is a function with domain $\mathbb{R}$ whose range has cardinality strictly larger than that of $\mathbb{R}$?
- The relationship of ${\frak m+m=m}$ to AC
- Existence of a Boolean algebra with a unique ultrafilter in ZF

- Unprovable statements in ZF
- Proving Dedekind finite implies finite assuming countable choice
- The “set” of equivalence classes of things.
- Over ZF, does “every Hilbert space have a basis” imply AC?
- How do I choose an element from a non-empty set?
- Non-aleph infinite cardinals
- Existence in ZF of a set with countable power set
- Existence of Hamel basis, choice and regularity
- Axiom of choice and compactness.
- What is the cardinality of the set of all topologies on $\mathbb{R}$?

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.

- Bijection between $\mathbb{R}^n$ and $\mathbb{R}^m$
- Image of unit ball dense under continuous map between banach spaces
- Limit of $h_n(x)=x^{1+\frac{1}{2n-1}}$
- Prisoners Problem
- $\epsilon$-$\delta$ limit proof, $\lim_{x \to 2} \frac{x^{2}-2x+9}{x+1}$
- Entailment relations that are not partial orders
- n-th roots of unity form a cyclic group in a field of characteristic p if gcd(n,p) = 1
- Method of characteristics for the PDE $xu_x +y u_y = 0$ with an initial condition on a circle
- What is CDF – Cumulative distribution function?
- Questions about Serre duality
- Why is $\sqrt{2\sqrt{2\sqrt{2\cdots}}} = 2$?
- Why is $\mathbb{Q}(t,\sqrt{t^3-t})$ not a purely transcendental extension of $\mathbb{Q}$?
- What is the fallacy in this proof?
- $e^{e^{e^{79}}}$ and ultrafinitism
- Link between the negative pell equation $x^2-dy^2=-1$ and a certain continued fraction