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. Gödel (1940) 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

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

1. ${\mathfrak {F}}_{1}(X,Y)=\{X,Y\}$
2. ${\mathfrak {F}}_{2}(X,Y)=E\cdot X=\{(a,b)\in X\mid a\in b\}$
3. ${\mathfrak {F}}_{3}(X,Y)=X-Y$
4. ${\mathfrak {F}}_{4}(X,Y)=X\upharpoonright Y=X\cdot (V\times Y)=\{(a,b)\in X\mid b\in Y\}$
5. ${\mathfrak {F}}_{5}(X,Y)=X\cdot {\mathfrak {D}}(Y)=\{b\in X\mid \exists a(a,b)\in Y\}$
6. ${\mathfrak {F}}_{6}(X,Y)=X\cdot Y^{-1}=\{(a,b)\in X\mid (b,a)\in Y\}$
7. ${\mathfrak {F}}_{7}(X,Y)=X\cdot {\mathfrak {Cnv}}_{2}(Y)=\{(a,b,c)\in X\mid (a,c,b)\in Y\}$
8. ${\mathfrak {F}}_{8}(X,Y)=X\cdot {\mathfrak {Cnv}}_{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, ${\mathfrak {D}}$ denotes range and so on. (Here the symbol $\upharpoonright$ is used to restrict range, unlike the contemporary meaning of restriction.)

Jech (2003) 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 $\phi (x_{1},\ldots ,x_{n})$ is a formula in the language of set theory with all quantifiers bounded, then the function $\{(x_{1},\ldots ,x_{n})\in X\mid (x_{1},\ldots ,x_{n})\in (X_{1}\times \ldots \times X_{n})\land \phi (x_{1},\ldots ,x_{n})\}$ of $X_{1}$, $\ldots$, $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 {KPU}$, a variant of Kripke-Platek set theory admitting urelements.^{p. 64}

References

• Gödel, Kurt (1940). The Consistency of the Continuum Hypothesis. Annals of Mathematics Studies. Vol. 3. Princeton, N. J.: Princeton University Press. ISBN 978-0-691-07927-1. MR 0002514.
• Jech, Thomas (2003), Set Theory: Millennium Edition, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-3-540-44085-7