permutation model

A permutation model is a model of the axioms of set theory in which there is a non trivial automorphism of the set theoretic universe. Such models are used to show the consistency of the negation of the Axiom of Choice (AC).

A typical construction of a permutation model is done here. By $Z{F}^{-}$ we denote the axioms of $ZF$ minus the axiom of foundation. In particular we allow sets $a$ such that $a=\{a\}$ which we will call atoms. Let $A$ be an infinite set of atoms.

Define $V_{\alpha }(A)$ by induction on $\alpha$ as follows:

$V_0(A)$$=A$

$V_{\alpha +1}(A)$$=𝒫(V_{\alpha })$

$V_{\alpha }(A)$

Finally define $V={\bigcup }_{\alpha \in \text{ON}}{V}_{\alpha }(A)$. Then we have

$$A=V_0(A)\subseteq V_1(A)\subseteq \mathrm{\cdots }\subseteq V_{\alpha }(A)\mathrm{\cdots }\subseteq V$$

For any $x\in V$ we can assign a rank,

$$\mathrm{rank}(x)=\text{ least }\alpha [x\in V_{\alpha +1}(A)]$$

Let $G$ be the group of permutations of $A$. For $\pi \in G$ we extend $\pi$ toa permutation of $V$ by induction on $\in$ by defining

$$\pi (x)=\{\pi (y):y\in x\}$$

and letting $\pi (\mathrm{\varnothing })=\mathrm{\varnothing }$. Then $G$ permutes $V$ and fixes the well founded sets $WF\subseteq V$.

Lemma.

For all $x\mathrm{,}y\mathrm{\in }V$ and any $\pi \mathrm{\in }G$.

$$x\in y\iff \pi (x)\in \pi (y)$$

That is, $\pi$ is an $\in$-automorphism of $V$. From this we can prove that $\pi (\{X,Y\})=\{\pi (X),\pi (Y)\}$ and so

$\pi ((X,Y))$$=(\pi (X),\pi (Y))$

$\pi ((X,Y,Z))$$=(\pi (X),\pi (Y),\pi (Z))$

Also by induction on $\alpha$ it is easy to show that

$$\mathrm{rank}(x)=\mathrm{rank}(\pi (x))$$

for all $x\in V$.

Let $a_1,\mathrm{\cdots },a_n\in A$ and define

$$[a_1,\mathrm{\cdots },a_n]=\{\pi \in G:\pi (a_i)=a_i,\text{ for }i=1,\mathrm{\cdots },n\}$$

Call a set $X\in V$ symmetric if there exists $a_1,\mathrm{\cdots },a_n\in A$ such that $\pi (X)=X$ for all $\pi \in [a_1,\mathrm{\cdots },a_n]$. Define the class $HS\subseteq V$ of hereditarily symmetric sets

$$HS=\{x\in V:x\text{ is symmetric and }x\subseteq HS\}$$

Call a class $N$ transitive if

$$\forall x\in N[x\subseteq N]$$

and call $N$ almost universal if (for sets S)

$$\forall S\subseteq N[\exists Y\in N(S\subseteq Y)]$$

$HS$ is transitive and almost universal.

To show that a class $N\vDash Z{F}^{-}$ is straightforward for most axioms of $Z{F}^{-}$ except for the axiom of Comprehension. To show $N$ is a model of Comprehension it suffices to show that $N$ is closed under Gödel Operations:

$G_1(X,Y)$$=\{X,Y\}$

$G_2(X,Y)$$=X\setminus Y$

$G_3(X,Y)$$=X\times Y$

$G_4(X)$$=\text{dom}(X)$

$G_5(X)$$=\in \cap X^2$

$G_6(X)$$=\{(a,b,c):(b,c,a)\in X\}$

$G_7(X)$$=\{(a,b,c):(c,b,a)\in X\}$

$G_8(X)$$=\{(a,b,c):(a,c,b)\in X\}$

Theorem.

($Z\mathit{}F$) If $N$ is transitive, almost universal and closed under Gödel Operations, then $N\mathrm{\vDash }Z\mathit{}F$.

$HS$ is closed under Gödel operations and so $HS\vDash Z{F}^{-}$. The class $HS$ is a permutation model. The set of atoms $A\in HS$ and furthermore:

Lemma.

Let $f\mathrm{:}\omega \mathrm{\to }A$ be a one to one function. Then $f\mathrm{\notin }H\mathit{}S$ and so $A$ cannot be well ordered in $H\mathit{}S$.

Which proves the theorem:

Theorem.

$HS\vDash Z{F}^{-}+\mathrm{\neg }AC$.

which completes the proof that $\text{Con}(Z{F}^{-})⟹\text{Con}(Z{F}^{-}+\mathrm{\neg }AC)$. In particular we have that $Z{F}^{-}⊬AC$.