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\}$

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 {(x₁,...,x_n) ∈ X₁×...×X_n | φ(x₁, ..., x_n)) of X₁, ..., X_n is given by a composition of some Gödel operations. This result is closely related to Jensen's rudimentary functions.

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