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 $Z F$ 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)]

$H S$ 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.

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

$H S$ is closed under Gödel operations and so $HS\models ZF^{-}$ . The class $H S$ 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 $H S$ .

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
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