Gödel operation explained

In mathematical set theory, a set of Gödel operations is a finite collection of operations on sets that can be used to construct the constructible sets from ordinals. introduced the original set of 8 Gödel operations ₁,...,₈ under the name fundamental operations. Other authors sometimes use a slightly different set of about 8 to 10 operations, usually denoted G₁, G₂,...

Definition

used the following eight operations as a set of Gödel operations (which he called fundamental operations):

ak{F}_1(X,Y)=\{X,Y\}

ak{F}_2(X,Y)=E ⋅ X=\{(a,b)\isinX\mida\isinb\}

ak{F}_3(X,Y)=X-Y

ak{F}_4(X,Y)=X\upharpoonrightY=X ⋅ (V x Y)=\{(a,b)\isinX\midb\isinY\}

ak{F}_5(X,Y)=X ⋅ ak{D}(Y)=\{b\isinX\mid\existsa(a,b)\isinY\}

ak{F}_6(X,Y)=X ⋅ Y^-1=\{(a,b)\isinX\mid(b,a)\isinY\}

ak{F}_7(X,Y)=X ⋅ ak{Cnv}_2(Y)=\{(a,b,c)\isinX\mid(a,c,b)\isinY\}

ak{F}_8(X,Y)=X ⋅ ak{Cnv}_3(Y)=\{(a,b,c)\isinX\mid(c,a,b)\isinY\}

The second expression in each line gives Gödel's definition in his original notation, where the dot means intersection, V is the universe, E is the membership relation,

ak{D}

denotes range and so on. (Here the symbol

\upharpoonright

is used to restrict range, unlike the contemporary meaning of restriction.)

uses the following set of 10 Gödel operations.

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

G_2(X,Y)=X x Y

G_3(X,Y)=\{(x,y)\midx\isinX,y\isinY,x\isiny\}

G_4(X,Y)=X-Y

G_5(X,Y)=X\capY

G_6(X)=\cupX

G_7(X)=dom(X)

G_8(X)=\{(x,y)\mid(y,x)\isinX\}

G_9(X)=\{(x,y,z)\mid(x,z,y)\isinX\}

G₁₀(X)=\{(x,y,z)\mid(y,z,x)\isinX\}

Properties

Gödel's normal form theorem states that if φ(x₁,...x_n) is a formula in the language of set theory with all quantifiers bounded, then the function