• Images
• Videos
• Documents
• Books
• Articles

Definition

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

1. F 1 ( X , Y ) = { X , Y } {\displaystyle {\mathfrak {F}}_{1}(X,Y)=\{X,Y\}}
2. F 2 ( X , Y ) = E ⋅ X = { ( a , b ) ∈ X ∣ a ∈ b } {\displaystyle {\mathfrak {F}}_{2}(X,Y)=E\cdot X=\{(a,b)\in X\mid a\in b\}}
3. F 3 ( X , Y ) = X − Y {\displaystyle {\mathfrak {F}}_{3}(X,Y)=X-Y}
4. F 4 ( X , Y ) = X ↾ Y = X ⋅ ( V × Y ) = { ( a , b ) ∈ X ∣ b ∈ Y } {\displaystyle {\mathfrak {F}}_{4}(X,Y)=X\upharpoonright Y=X\cdot (V\times Y)=\{(a,b)\in X\mid b\in Y\}}
5. F 5 ( X , Y ) = X ⋅ D ( Y ) = { b ∈ X ∣ ∃ a ( a , b ) ∈ Y } {\displaystyle {\mathfrak {F}}_{5}(X,Y)=X\cdot {\mathfrak {D}}(Y)=\{b\in X\mid \exists a(a,b)\in Y\}}
6. F 6 ( X , Y ) = X ⋅ Y − 1 = { ( a , b ) ∈ X ∣ ( b , a ) ∈ Y } {\displaystyle {\mathfrak {F}}_{6}(X,Y)=X\cdot Y^{-1}=\{(a,b)\in X\mid (b,a)\in Y\}}
7. F 7 ( X , Y ) = X ⋅ C n v 2 ( Y ) = { ( a , b , c ) ∈ X ∣ ( a , c , b ) ∈ Y } {\displaystyle {\mathfrak {F}}_{7}(X,Y)=X\cdot {\mathfrak {Cnv}}_{2}(Y)=\{(a,b,c)\in X\mid (a,c,b)\in Y\}}
8. F 8 ( X , Y ) = X ⋅ C n v 3 ( Y ) = { ( a , b , c ) ∈ X ∣ ( c , a , b ) ∈ Y } {\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, D {\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. G 1 ( X , Y ) = { X , Y } {\displaystyle G_{1}(X,Y)=\{X,Y\}}
2. G 2 ( X , Y ) = X × Y {\displaystyle G_{2}(X,Y)=X\times Y}
3. G 3 ( X , Y ) = { ( x , y ) ∣ x ∈ X , y ∈ Y , x ∈ y } {\displaystyle G_{3}(X,Y)=\{(x,y)\mid x\in X,y\in Y,x\in y\}}
4. G 4 ( X , Y ) = X − Y {\displaystyle G_{4}(X,Y)=X-Y}
5. G 5 ( X , Y ) = X ∩ Y {\displaystyle G_{5}(X,Y)=X\cap Y}
6. G 6 ( X ) = ∪ X {\displaystyle G_{6}(X)=\cup X}
7. G 7 ( X ) = dom ( X ) {\displaystyle G_{7}(X)={\text{dom}}(X)}
8. G 8 ( X ) = { ( x , y ) ∣ ( y , x ) ∈ X } {\displaystyle G_{8}(X)=\{(x,y)\mid (y,x)\in X\}}
9. G 9 ( X ) = { ( x , y , z ) ∣ ( x , z , y ) ∈ X } {\displaystyle G_{9}(X)=\{(x,y,z)\mid (x,z,y)\in X\}}
10. G 10 ( X ) = { ( x , y , z ) ∣ ( y , z , x ) ∈ X } {\displaystyle G_{10}(X)=\{(x,y,z)\mid (y,z,x)\in X\}}

The reason for including the functions { ( x , y , z ) ∣ ( x , z , y ) ∈ X } {\displaystyle \{(x,y,z)\mid (x,z,y)\in X\}} and { ( x , y , z ) ∣ ( y , z , x ) ∈ X } {\displaystyle \{(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 ) {\displaystyle (x_{1},x_{2},x_{3},x_{4})} can be formed easily from x 1 {\displaystyle x_{1}} and ( x 2 , x 3 , x 4 ) {\displaystyle (x_{2},x_{3},x_{4})} since it equals ( x 1 , ( x 2 , x 3 , x 4 ) ) {\displaystyle (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 {\displaystyle x_{4}} and ( x 1 , x 2 , x 3 ) {\displaystyle (x_{1},x_{2},x_{3})} .¹p. 63

Properties

Gödel's normal form theorem states that if ϕ ( x 1 , … , x n ) {\displaystyle \phi (x_{1},\ldots ,x_{n})} is a formula in the language of set theory with all quantifiers bounded, then the function { ( x 1 , … , x n ) ∈ X ∣ ( x 1 , … , x n ) ∈ ( X 1 × … × X n ) ∧ ϕ ( x 1 , … , x n ) } {\displaystyle \{(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 {\displaystyle X_{1}} , … {\displaystyle \ldots } , X n {\displaystyle 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 K P U {\displaystyle \mathrm {KPU} } , a variant of Kripke-Platek set theory admitting urelements.³p. 64

• 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. {{cite book}}: ISBN / Date incompatibility (help)
• Jech, Thomas (2003), Set Theory: Millennium Edition, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-3-540-44085-7

Inline references

References

1. Barwise, Jon (1975). Admissible Sets and Structures. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-07451-1. 3-540-07451-1 ↩

2. K. Devlin, An introduction to the fine structure of the constructible hierarchy (1974, p.11). Accessed 2022-02-26. https://core.ac.uk/download/pdf/30905237.pdf ↩

3. Barwise, Jon (1975). Admissible Sets and Structures. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-07451-1. 3-540-07451-1 ↩