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. ${\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, and so on.

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

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

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

Inline references

1. K. Devlin, An introduction to the fine structure of the constructible hierarchy (1974, p.11). Accessed 2022-02-26.