Gödel operation

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. Template:Harvs 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

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

1. ${𝔉}_1(X,Y)=\{X,Y\}$
2. ${𝔉}_2(X,Y)=E\cdot X=\{(a,b)\in X\mid a\in b\}$
3. ${𝔉}_3(X,Y)=X-Y$
4. ${𝔉}_4(X,Y)=X\upharpoonright Y=X\cdot (V\times Y)=\{(a,b)\in X\mid b\in Y\}$
5. ${𝔉}_5(X,Y)=X\cdot 𝔇(Y)=\{b\in X\mid \mathrm{\exists }a(a,b)\in Y\}$
6. ${𝔉}_6(X,Y)=X\cdot Y^{-1}=\{(a,b)\in X\mid (b,a)\in Y\}$
7. ${𝔉}_7(X,Y)=X\cdot {ℭ𝔫𝔳}_2(Y)=\{(a,b,c)\in X\mid (a,c,b)\in Y\}$
8. ${𝔉}_8(X,Y)=X\cdot {ℭ𝔫𝔳}_3(Y)=\{(a,b,c)\in X\mid (c,a,b)\in Y\}$

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, $𝔇$ denotes range and so on. (Here the symbol $\upharpoonright$ is used to restrict range, unlike the contemporary meaning of restriction.)

Template:Harvtxt uses the following set of 10 Gödel operations.

1. $G_1(X,Y)=\{X,Y\}$
2. $G_2(X,Y)=X\times Y$
3. $G_3(X,Y)=\{(x,y)\mid x\in X,y\in Y,x\in y\}$
4. $G_4(X,Y)=X-Y$
5. $G_5(X,Y)=X\cap Y$
6. $G_6(X)=\cup X$
7. $G_7(X)=\text{dom}(X)$
8. $G_8(X)=\{(x,y)\mid (y,x)\in X\}$
9. $G_9(X)=\{(x,y,z)\mid (x,z,y)\in X\}$
10. $G_{10}(X)=\{(x,y,z)\mid (y,z,x)\in X\}$

The reason for including the functions $\{(x,y,z)\mid (x,z,y)\in X\}$ and $\{(x,y,z)\mid (y,z,x)\in X\}$ which permute the entries of an ordered tuple is that, for example, the tuple $(x_1,x_2,x_3,x_4)$ can be formed easily from $x_1$ and $(x_2,x_3,x_4)$ since it equals $(x_1,(x_2,x_3,x_4))$, but it is more difficult to form when the entries are given in a different order, such as from $x_4$ and $(x_1,x_2,x_3)$.^{p. 63}

Properties

Gödel's normal form theorem states that if $\varphi (x_1,\dots ,x_n)$ is a formula in the language of set theory with all quantifiers bounded, then the function $\{(x_1,\dots ,x_n)\in X\mid (x_1,\dots ,x_n)\in (X_1\times \dots \times X_n)\wedge \varphi (x_1,\dots ,x_n)\}$ of $X_1$, $\dots$, $X_n$ is given by a composition of some Gödel operations. This result is closely related to Jensen's rudimentary functions.

Jon Barwise showed that a version of Gödel's normal form theorem with his own set of 12 Gödel operations is provable in $\mathrm{K}\mathrm{P}\mathrm{U}$, a variant of Kripke-Platek set theory admitting urelements.^{p. 64}

References

• Template:Cite book
• Template:Citation