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₂,...

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

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

Jech (2003) uses the following set of 10 Gödel operations.

1. ${\displaystyle G_{1}(X,Y)=\{X,Y\}}$
2. ${\displaystyle G_{2}(X,Y)=X\times Y}$
3. ${\displaystyle G_{3}(X,Y)=\{(x,y)\mid x\in X,y\in Y,x\in y\}}$
4. ${\displaystyle G_{4}(X,Y)=X-Y}$
5. ${\displaystyle G_{5}(X,Y)=X\cap Y}$
6. ${\displaystyle G_{6}(X)=\cup X}$
7. ${\displaystyle G_{7}(X)={\text{dom}}(X)}$
8. ${\displaystyle G_{8}(X)=\{(x,y)\mid (y,x)\in X\}}$
9. ${\displaystyle G_{9}(X)=\{(x,y,z)\mid (x,z,y)\in X\}}$
10. ${\displaystyle G_{10}(X)=\{(x,y,z)\mid (y,z,x)\in X\}}$

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.^[1]

• 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