permutation model


A permutation model is a model of the axioms of set theoryMathworldPlanetmath in which there is a non trivial automorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of the set theoretic universePlanetmathPlanetmath. Such models are used to show the consistency of the negationMathworldPlanetmath of the Axiom of ChoiceMathworldPlanetmath (AC).

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

Define Vα(A) by inductionMathworldPlanetmath on α as follows:

V0(A) =A
Vα+1(A) =𝒫(Vα)
Vα(A) =γ<αVγ(A) for α limit

Finally define V=αONVα(A). Then we have

A=V0(A)V1(A)Vα(A)V

For any xV we can assign a rank,

rank(x)= least α[xVα+1(A)]

Let G be the group of permutationsMathworldPlanetmath of A. For πG we extend π to a permutation of V by induction on by defining

π(x)={π(y):yx}

and letting π()=. Then G permutes V and fixes the well founded sets WFV.

Lemma.

For all x,yV and any πG.

xyπ(x)π(y)

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

π((X,Y)) =(π(X),π(Y))
π((X,Y,Z)) =(π(X),π(Y),π(Z))

Also by induction on α it is easy to show that

rank(x)=rank(π(x))

for all xV.

Let a1,,anA and define

[a1,,an]={πG:π(ai)=ai, for i=1,,n}

Call a set XV symmetricPlanetmathPlanetmath if there exists a1,,anA such that π(X)=X for all π[a1,,an]. Define the class HSV of hereditarily symmetric sets

HS={xV:x is symmetric and xHS}

Call a class N transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath if

xN[xN]

and call N almost universalPlanetmathPlanetmathPlanetmath if (for sets S)

SN[YN(SY)]

HS is transitive and almost universal.

To show that a class NZF- is straightforward for most axioms of ZF- except for the axiom of ComprehensionPlanetmathPlanetmath. To show N is a model of Comprehension it suffices to show that N is closed under Gödel Operations:

G1(X,Y) ={X,Y}
G2(X,Y) =XY
G3(X,Y) =X×Y
G4(X) =dom(X)
G5(X) =X2
G6(X) ={(a,b,c):(b,c,a)X}
G7(X) ={(a,b,c):(c,b,a)X}
G8(X) ={(a,b,c):(a,c,b)X}
Theorem.

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

HS is closed under Gödel operations and so HSZF-. The class HS is a permutation model. The set of atoms AHS and furthermore:

Lemma.

Let f:ωA be a one to one function. Then fHS and so A cannot be well ordered in HS.

Which proves the theorem:

Theorem.

HSZF-+¬AC.

which completesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof that Con(ZF-)Con(ZF-+¬AC). In particular we have that ZF-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