# Failure of Choice only for sets above a certain rank

Let $\alpha$ be an ordinal. How can we show that the following theory is consistent?

$\mathrm{ZF}$ + "there exists a set with rank greater than $\alpha$ that is not well ordered" + "every set of rank lower than $\alpha$ is well ordered".

• Note that if your $\kappa$ is an "initial ordinal" (as opposed to some more abstract cardinal number arrived at, say, by using Scott's trick), then the last statement in your proposed theory is trivially satisfied as any set injectible into an ordinal is well-orderable: just use the order induced by the injection! – user642796 Mar 27 '13 at 17:04

The idea is to pick $$\kappa$$ which is large enough, and does not inject into $$V_\alpha$$. Then we add subsets to $$\kappa$$ and use them to generate subsets of $$2^\kappa$$ which cannot be well-ordered. These cannot be embedded into $$V_\alpha$$ either, so we finished our proof.

We begin with the forcing $$P$$ whose conditions are functions from $$\kappa\times\kappa$$ into $$2$$, with domain of cardinality $$<\kappa$$. $$q$$ is stronger than $$p$$ if $$p\subseteq q$$, and we denote this by $$q\leq p$$.

Easily, the forcing adds $$\kappa$$ new subsets to $$\kappa$$. But the forcing is $$\kappa$$-closed (or $$<\kappa$$-closed, depending on your flavor of terminology) so it doesn't add any subset to any smaller cardinal. In particular it doesn't add any subset to $$V_\alpha$$, so no sets of rank $$\alpha$$ are added.

We consider the following names, $$\dot r_\alpha=\{(p,\check\beta)\mid p(\alpha,\beta)=1\}$$, for $$\alpha<\kappa$$. These are the canonical names for the new subsets of $$\kappa$$ that are being added.

Let $$\scr G$$ be the group of all permutations of $$\kappa$$ in the ground model. Although it is enough to consider permutations which only move finitely many points at a time (as an analysis of the following argument will show). $$\scr G$$ acts on the poset $$P$$ in the following way: $$\pi p(\pi\alpha,\beta)=p(\alpha,\beta).$$

Extend those actions to actions of $$P$$-names, by defining $$\pi\dot x=\{(\pi p,\pi\dot y)\mid (p,\dot y)\in\dot x\}$$. We have now the following lemma,

The Symmetry Lemma: For every formula $$\varphi(\dot u_1,\ldots,\dot u_k)$$ and every condition $$p$$, and every $$\pi\in\scr G$$: $$p\Vdash\varphi(\dot u_1,\ldots,\dot u_k)\iff\pi p\Vdash\varphi(\pi\dot u_1,\ldots,\pi\dot u_k).$$

Proof. Induction on the formulas and the names.

Now take any regular $$\mu\leq\kappa$$, and we will define a model in which the name $$\dot R=\{(1,\dot r_\alpha)\mid\alpha<\kappa\}$$ is interpreted to have Hartogs number $$\mu$$ (the least cardinal cannot be injected into the set), and $$\sf DC_{<\mu}$$ holds. In particular it shows that that set cannot be well-ordered, because it should have the Hartogs number of $$\kappa^+$$.

Define $$\cal F$$ to be a filter of subgroups of $$\scr G$$ where $$H\in\cal F$$ if and only if there exists $$E\subseteq\kappa$$ such that $$|E|<\mu$$, and all the permutations in $$H$$ fix $$E$$ pointwise. We define by induction the class $$\sf HS$$. Given a $$P$$-name $$\dot x$$, we say that $$\dot x\in\sf HS$$ if there exists $$H\in\cal F$$ such that whenever $$\pi\in H$$, $$\pi\dot x=\dot x$$, and if every $$\dot y$$ which appears in $$\dot x$$ is already in $$\sf HS$$.

If $$H$$ is a subgroup which contains the pointwise stabilizer of $$E$$, and $$H$$ fixes $$\dot x$$, we say that $$E$$ is a support for $$\dot x$$, and we note that every permutation which fixes $$E$$ pointwise will fix $$\dot x$$ as well.

Lemma 1: The following holds.

1. For every $$x$$ in the ground model, $$\check x\in\sf HS$$. With $$\varnothing$$ as support.
2. For every $$\alpha<\kappa$$, $$\dot r_\alpha\in\sf HS$$ with support $$\{\alpha\}$$.
3. $$\dot R\in\sf HS$$ with the empty support.

Proof. Exercise.

Let $$G\subseteq P$$ be a generic filter. Let $$V[G]$$ be the generic extension of the universe and let $$N=\{\dot x^G\mid\dot x\in\sf HS\}$$ be the interpretation of all the names in $$\sf HS$$.

Lemma 2: $$N$$ is a transitive model of $$\sf ZF$$, and $$V\subseteq N$$.

Proof. Transitivity follows from the inductive definition of $$\sf HS$$; $$V\subseteq N$$ from the first point of the previous lemma; and $$N\models\sf ZF$$ because it is almost universal and closed under Goedel functions, but one can also verify the axioms directly (see also Jech "Set Theory", 3rd eds. Ch. 15). $$\square$$

Theorem: In $$N$$, $$\sf AC$$ fails.

Proof. Let $$R=\dot R^G\in V$$, we will show that it cannot be well-ordered in $$N$$, as promised.

From the last point of Lemma 1, $$R\in N$$. Suppose now that $$f\colon \mu\to R$$ is an injection, and $$f\in N$$. There exists some name $$\dot f\in\sf HS$$ and some $$E\in[\kappa]^{<\mu}$$ such that $$\dot f=f$$ and $$E$$ is a support for $$\dot f$$.

Let $$p$$ be a condition such that $$p\Vdash\dot f\colon\check\mu\to\dot R$$. We may assume without loss of generality that for some $$\alpha\notin E$$, and some $$\gamma<\kappa$$ we have $$p\Vdash\dot f(\check\gamma)=\dot r_\alpha$$.

Let $$\alpha<\beta<\kappa$$ such that $$\beta\notin E$$ and there is no ordinal $$\delta$$ such that $$(\beta,\delta)\in\operatorname{dom} p$$. We define the permutation $$\pi$$ to switch between $$\alpha$$ and $$\beta$$ and be the identity everywhere else.

Clearly $$\pi$$ fixes $$E$$ pointwise and therefore $$\pi\dot f=\dot f$$. Therefore by the symmetry lemma, $$\pi p\Vdash\dot f\colon\check\mu\to\dot R$$, and also $$\pi p\Vdash\dot f(\check\gamma)=\dot r_\beta$$.

If $$p$$ and $$\pi p$$ are compatible then we have a contradiction because $$q\leq p,\pi p$$ would have to force that $$\dot r_\alpha=\dot f(\check\gamma)=\dot r_\beta$$, and also $$\dot r_\alpha\neq\dot r_\beta$$!

And indeed if $$(\xi,\zeta)\in\operatorname{dom} p$$ then either $$\xi=\alpha$$ and then $$\pi\xi=\beta$$ and $$(\beta,\zeta)\notin\operatorname{dom} p$$ at all; or $$\pi\xi=\xi$$. Similarly for $$\pi p$$ exchanging $$\beta$$ with $$\alpha$$. Therefore the conditions $$p$$ and $$\pi p$$ are compatible and this is a contradiction. $$\square$$

Bonus Lemma: If $$f\colon V[G]\to N$$ such that $$\operatorname{dom} f<\mu$$, then there exists $$\dot f\in\sf H$$ such that $$\dot f^G=f$$.

Proof. Exercise (note that you have to use the fact that the forcing $$P$$ is $$\kappa$$-closed).

Now trivially $$\sf DC_{<\mu}$$ holds in $$N$$, because whenever $$S$$ is a subset of $$X^<\gamma\times X$$, for a non-empty $$X$$ and $$\gamma<\mu$$, satisfying the conditions of $$\sf DC_{\gamma}$$, there is a function $$f$$ witnessing that in $$V[G]$$ and by the bonus lemma, it is also in $$N$$.

Further bibliography:

Here is a list of places where these techniques are discussed, do note that the approaches and notations slightly differ from one place to another.

1. Jech, "Set Theory", 3rd eds. (Springer 2006)
2. Jech, "The Axiom of Choice". (North-Holland 1973)
3. Dimitriou, "Symmetric Models, Singular Cardinal Patterns, and Indiscernibles. (PhD dissertation, Universität Bonn 2011)
4. Karagila, "Vector Spaces and Antichains of Cardinals in Models of Set Theory". (MSc thesis, Ben-Gurion University of the Negev 2012)
• Huzzah at the shameless promotion of my thesis. – Asaf Karagila Mar 27 '13 at 18:13
• @Asaf : Thank you for your answer. Would it be possible to prove the same thing using some Fraenkel-Mostowksi permutation model in $\mathrm{ZFA}$ and then transferring it to $\mathrm{ZF}$ using Embedding Theorem? – Sumac Mar 28 '13 at 16:25
• @Sumac: Permutation models are such that they fail choice on rank $1$, because the set of atoms cannot be well-ordered. The pure sets can always be well-ordered in the classical FMS method. It's the embedding part which allows you to control where you are going to embed the atoms and the sets which is essentially a similar forcing to the one I present here (although slightly different choice for the names and permutations and whatnot) which allows you to construct the model of $\sf ZF$. If you choose $\kappa$ "wisely" you have what you would like. It's easier to just force and get it over with – Asaf Karagila Mar 28 '13 at 18:40
• @Sumac: Once choice fails, it fails. It is easy to increase the rank by taking the union with some ordinal or something like that. – Asaf Karagila May 25 '13 at 9:58
• @Sumac: No, you haven't read the revisions I made in the answer. If $\beta$ is the least rank of a set of cardinality $2^\kappa$, then choice fails at rank $\beta+1$. It doesn't matter than $\kappa$ is very very very large compared to $\kappa$. If $2^{\aleph_0}=\aleph_{\omega_{500}+1}$ then to make choice hold for sets of rank $\omega+1$ we will take $\kappa$ to be $\aleph_{\omega_{500}+2}$. I may be off by $\pm1$ on the rank, but generally this is how it goes. You find some cardinal which doesn't have equipotent sets of the rank we care about, and we work with that. – Asaf Karagila May 25 '13 at 10:56