# 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 $ZF^{-}$ 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:

 $\displaystyle V_{0}(A)$ $\displaystyle=A$ $\displaystyle V_{\alpha+1}(A)$ $\displaystyle=\mathcal{P}(V_{\alpha})$ $\displaystyle V_{\alpha}(A)$ $\displaystyle=\bigcup_{\gamma<\alpha}V_{\gamma}(A)\text{ for \alpha limit}$

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

 $A=V_{0}(A)\subseteq V_{1}(A)\subseteq\cdots\subseteq V_{\alpha}(A)\cdots\subseteq V$

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

 $\operatorname{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$ to a permutation of $V$ by induction on $\in$ by defining

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

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

###### Lemma.

For all $x,y\in V$ and any $\pi\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

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

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

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

for all $x\in V$.

Let $a_{1},\cdots,a_{n}\in A$ and define

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

Call a set $X\in V$ symmetric if there exists $a_{1},\cdots,a_{n}\in A$ such that $\pi(X)=X$ for all $\pi\in[a_{1},\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\models ZF^{-}$ is straightforward for most axioms of $ZF^{-}$ 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:

 $\displaystyle G_{1}(X,Y)$ $\displaystyle=\{X,Y\}$ $\displaystyle G_{2}(X,Y)$ $\displaystyle=X\setminus Y$ $\displaystyle G_{3}(X,Y)$ $\displaystyle=X\times Y$ $\displaystyle G_{4}(X)$ $\displaystyle=\text{dom}(X)$ $\displaystyle G_{5}(X)$ $\displaystyle=\ \in\!\cap X^{2}$ $\displaystyle G_{6}(X)$ $\displaystyle=\{(a,b,c):(b,c,a)\in X\}$ $\displaystyle G_{7}(X)$ $\displaystyle=\{(a,b,c):(c,b,a)\in X\}$ $\displaystyle G_{8}(X)$ $\displaystyle=\{(a,b,c):(a,c,b)\in X\}$
###### Theorem.

($ZF$) If $N$ is transitive, almost universal and closed under Gödel Operations, then $N\models ZF$.

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

###### Lemma.

Let $f:\omega\rightarrow A$ be a one to one function. Then $f\notin HS$ and so $A$ cannot be well ordered in $HS$.

Which proves the theorem:

###### Theorem.

$HS\models ZF^{-}+\neg AC$.

which completes the proof that $\text{Con}(ZF^{-})\implies\text{Con}(ZF^{-}+\neg AC)$. In particular we have that $ZF^{-}\nvdash AC$.

Title permutation model PermutationModel 2013-03-22 14:46:48 2013-03-22 14:46:48 ratboy (4018) ratboy (4018) 13 ratboy (4018) Definition msc 03E25 Gödel Operations