# 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)$ | $=\mathcal{P}({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 $ to
a 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}^{-})\u27f9\text{Con}(Z{F}^{-}+\mathrm{\neg}AC)$. In particular we have that $Z{F}^{-}\u22acAC$.

Title | permutation model |
---|---|

Canonical name | PermutationModel |

Date of creation | 2013-03-22 14:46:48 |

Last modified on | 2013-03-22 14:46:48 |

Owner | ratboy (4018) |

Last modified by | ratboy (4018) |

Numerical id | 13 |

Author | ratboy (4018) |

Entry type | Definition |

Classification | msc 03E25 |

Defines | Gödel Operations |