Proving "every set can be totally ordered" without using Axiom of Choice
It is known that the statement "every set can be totally ordered" is strictly weaker than Axiom of choice. How does one go about proving without using AC?
Solution 1:
Introduction to the answer:
I began writing, hoping to have a relatively short answer. However as I originally expected this is not a simple proof at all. I wrote a short guide to the construction of symmetric extensions and permutation models - the two canonical ways of proving independence from the axiom of choice. I do assume the reader is somewhat familiar with forcing and ZFA.
I discussed some basic forcing concepts in my answer here and some ZFA related answer can be found in my answer here.
The general idea is that we can have that if the universe is generated by an inner model and an additional set $A$ (the forcing conditions in the forcing case, atoms in the ZFA case), permutations of $A$ endow permutations of the universe. Thus, by choosing certain permutations, we can filter out sets which behave too "freely". The result is a model of ZF, and usually can be made so that the axiom of choice does not hold in it.
Given adequate structure on $A$ (Cohen reals in the forcing version, dense linear order on the atoms in ZFA), we can ensure the existence of a map from the universe into a linearly ordered class, while filtering out all the functions that well-order $A$. Thus negating choice, but leaving the order principle unharmed.
The full details can be found in Jech The Axiom of Choice, both on Ch. 4 and 5 (ZFA and forcing proofs respectively), although minor mistakes and extraneous assumptions are made. (There is an assumption of Global Choice, which the proof below is clear of, as well a mistake at one point regarding minimal supports which is also corrected below).
And now without further ado, the answer:
There are two versions of this proof; the first was given by Mostowski in 1939 in the theory of ZFA (ZF+Atoms, i.e. elements which are not sets and have no members) and the second by Levy and Halpern in 1964 by methods of forcing.
I will give a general review of symmetric extensions (and similarly permutation models) and explain the general idea how to prove this independence result.
[For those of you familiar with the definitions of symmetric extensions and permutation models of ZFA, feel free to skip to the next section separated by a horizontal line.]
Suppose $V$ is a model of ZFC, $P\in V$ is a notion of forcing, and $V[G]$ is a generic extension where $G$ is $V$-generic filter over $P$.
Let $\mathcal G$ be a group of permutations of $P$ (of course we require them to preserve the ordering and thus the forcing relation). In particular we have that $p\Vdash \varphi(\dot x)$ then $\pi p\Vdash \varphi(\pi\dot x)$ for $\pi\in\mathcal G$.
Inductively the permutations of $P$ induce permutations on $V^P$, the class of $P$-names (equivalently on $V^B$, the Boolean-valued model induced from $B=B(P)$ the complete Boolean algebra densely embedding the separative quotient of $P$), and for a name $\dot x\in V^P$ we define:
- $\operatorname{sym}(\dot x)=\{\pi\in\mathcal G\mid\pi\dot x=\dot x\}$, and
- $\operatorname{fix}(\dot x)=\{\pi\in\mathcal G\mid\forall \dot y\ \tilde\in\ \dot x(\pi\dot y=\dot y)\}$ (where $\dot y\ \tilde\in\ \dot x\iff \exists p\Vdash \dot y\in \dot x$) .
We can define a filter of subgroups over $\mathcal G$ as a collection of subgroups which is closed under intersections and upwards inclusion (we usually require nontriviality as well, that is the trivial subgroup is not there). A filter of subgroups is normal if it is closed under conjugation, that is if $\mathcal F$ is a filter of subgroups of $\mathcal G$ then it is normal if and only if: $$\pi\in\mathcal G,\, H\in\mathcal F\implies\pi H\pi^{-1} = \{\pi\sigma\pi^{-1}\mid\sigma\in H\}\in\mathcal F.$$
We next say a name $\dot x$ is symmetric [with respect to $\mathcal F$] when $\operatorname{sym}(\dot x)\in\mathcal F$, we say that a name $\dot x$ is hereditarily symmetric when $\dot x$ is symmetric and every $\dot y\in\dot x$ is also hereditarily symmetric. (Note that this form is of course circular, but hides a very standard definition by induction on the rank of $\dot x$)
Lastly, an ideal $I\subseteq\mathcal P(P)$ which extends the ideal of finite subsets is an ideal of supports for $\mathcal F$, for a filter of subgroups over $\mathcal G$ when:
- $\{x\}\in I$ for every $x\in P$ (that is to say, $I$ extends the finite subsets ideal); and
- $\mathcal F$ can be generated by $\{\operatorname{fix}(A)\mid A\in I\}$, while we did define $\operatorname{fix}$ on names, and not sets of conditions, the definition is very much the same.
If $E\in I$ such that for some name $\dot x$ we have $\operatorname{fix}(E)\subseteq\operatorname{sym}(\dot x)$ then we say that $E$ is a support of $\dot x$.
Suppose now that you take the class of names which is hereditarily symmetric (usually under some group of permutations and ideal of finite supports) the interpretation under the generic filter $G$ gives us a class $\mathcal N$ which is a model of ZF (usually without choice) and $V\subseteq\mathcal N\subseteq V[G]$.
$\mathcal N$ is called a symmetric extension (of $V$).
In a model of ZFA, the sets are generated by atoms and "pure" sets. We can consider permutations of atoms instead of permutations of the forcing conditions and names. From here the construction is more or less the same.
We consider those elements which are fixed whenever a small (which is really context-dependent) collection of atoms is fixed as symmetric. The resulting model is called a permutation model. In permutation models every set in the ideal of supports is hereditarily symmetric, as well $A$ as the set of atoms is hereditarily symmetric.
It is an important fact that $x\in\mathcal U$ can be well ordered (in $\mathcal U$ that is) if and only if $\operatorname{fix}(x)\in\mathcal F$. Therefore if we take the ideal of finite subsets of $A$ then in the permutation model $A$ cannot be well ordered.
The reason I brought ZFA into play is that independence results are far less technical in ZFA, since no interpretation comes into play. (This proof is due to Specker, 1957)
Suppose $A$ is the set of atoms, which is countable. Endow it with an order isomorphic to $\mathbb Q$ (that is fix a bijection of $A$ with $\mathbb Q$ and let $a < b\iff f(a) < f(b)$). Now consider the group of permutations of $A$ which preserve this ordering, and the ideal of finite sets of $A$ as supports. Since the order is preserved by the permutations, it will be a symmetric set with respect to the filter generated.
This creates a permutation model, $\mathcal U$, which we claimed can be linearly ordered (therefore every set can be linearly ordered by the induced ordering). The idea comes from symmetric classes, which as the name suggests a natural extension of symmetric elements.
We say that $C$ is a symmetric class, if the group $\operatorname{sym}(C)=\{\pi\in\mathcal G\mid \pi''C = C\}\in\mathcal F$.
Every class of the form $\{(x,E)\mid E\in I, x\in\mathcal U, \operatorname{fix}(E)\subseteq\operatorname{sym}(x)\}$, that is $x$ and $E$, a support of $x$. It is a symmetric class (this stems from the fact that $\pi\in\mathcal G$ then $\pi E$ is a support for $\pi x$).
Here comes the tricky parts: For every $x\in\mathcal U$ there exists a minimal support. We prove this by showing that the intersection of two supports is also a support (since we only chose order preserving permutations, and requires some technical arguments) and thus the intersection of all supports for $x$ is a minimal support for $x$.
We also have that if $E$ is a support for $x$, and $\pi E=E$ then $\pi x=x$, that is not only $\operatorname{fix}(E)$ is a subgroup of $\operatorname{sym}(x)$, but rather $\operatorname{sym}(E)$. (This is given by the fact $\pi$ preserves the order of $A$).
Now we can take the class $\Delta=\{(x,E)\mid E\text{ is the minimal support of } x\}$, which by the above claim is symmetric. Since $E$ is unique, and all supports are in the permutation model, this is in fact a class-function in $\mathcal U$, we let $\Delta(x)$ be $E$ which is the minimal support of $x$.
We are nearing the end of the proof. For every $x\in\mathcal U$ consider the orbit of $x$ defined as $\operatorname{orb}(x)=\{\pi x\mid\pi\in\mathcal G\}$. These are pairwise disjoint, and if $\pi\in\mathcal G$ then $\pi\operatorname{orb}(x) = \operatorname{orb}(\pi x)=\operatorname{orb}(x)$. Therefore every orbit is symmetric, and every set collection of orbits can be well ordered in $\mathcal U$.
Since $\pi$ preserves the rank of $x$, for every fixed $\alpha$ we have that the class $O_\alpha$ defined below is a set: $$O_\alpha=\{\operatorname{orb}(x)\mid\operatorname{rank}(x)=\alpha\}$$
From this we can deduce that:
$$\operatorname{orb}(x)=\operatorname{y},\ E=\Delta(x)=\Delta(y)\implies x=y$$
This is because there exists $\pi$ such that $\pi x=y$ we have that $\pi E$ is a support for $y$, however it is still the minimal support therefore $\pi E=E$ and so $y=\pi x=x$.
Given $x\in\mathcal U$, let $\alpha$ be such that $\operatorname{rank}(x)\le\alpha$. Let $\mathcal O=\bigcup_{\beta<\alpha}O_\beta$. Define the following function $f\colon x\to\mathcal O\times I$ defined by $$f(y)=\left(\varphi(\operatorname{orb}(y)),\Delta(y)\right)$$
From the previous argument we have that $f$ is injective (since having the same orbit and minimal support implies equality). Therefore we only need to linearly order the range, and $f$ will induce a linear ordering of $x$.
Fix $\varphi\colon\mathcal O\to\operatorname{Ord}$ a well ordering of $\mathcal O$ (this can be done since $\operatorname{fix}(\mathcal O)=\mathcal G$), and order $I$ lexicographically (as finite subsets of a linearly ordered set this is possible), then take the lexicographic order on $\mathcal O\times I$ induced by these two linear ordering - which is linear as well.
Thus, every set can be linearly ordered in $\mathcal U$, and as the fact mentioned at the end of the previous section tells us - $A$ (the set of atoms) cannot be well ordered in $\mathcal U$.
The forcing proof is very similar, we begin with adding countably many Cohen reals and preform about the same process with them. Note that we drop the requirement for the isomorphism to $\mathbb Q$ since the generic Cohen reals are already have this order type within $\mathbb R$.
Though, we need to prove the claims on the names, which is a far more technical process. The result, however is the same.
One last remark is that since $\mathcal U$ defined here is a support model (every set has a least support) we can use the second Jech-Sochor embedding theorem to have the model of ZF simply by invoking this theorem.