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 𝔉1,...,𝔉8 under the name fundamental operations. Other authors sometimes use a slightly different set of about 8 to 10 operations, usually denoted G1, G2,...
Definition
Gödel (1940) used the following eight operations as a set of Gödel operations (which he called fundamental operations):
![{\displaystyle {\mathfrak {F}}_{1}(X,Y)=\{X,Y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88d68f2d3ff4a927579c6bea0269a8d6b887f9f2)
![{\displaystyle {\mathfrak {F}}_{2}(X,Y)=E\cdot X=\{(a,b)\in X\mid a\in b\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/148e1cf9b35ee793c104d4773c31d6c04abe89a0)
![{\displaystyle {\mathfrak {F}}_{3}(X,Y)=X-Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddc4adcef4dcf8ff0c043d4052414e79450dabb2)
![{\displaystyle {\mathfrak {F}}_{4}(X,Y)=X\upharpoonright Y=X\cdot (V\times Y)=\{(a,b)\in X\mid b\in Y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/608b4c57b5a4f098ea8119ac8a59631abe3e659c)
![{\displaystyle {\mathfrak {F}}_{5}(X,Y)=X\cdot {\mathfrak {D}}(Y)=\{b\in X\mid \exists a(a,b)\in Y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/705761a90a1a2e33cb091e7b5358f327468f8426)
![{\displaystyle {\mathfrak {F}}_{6}(X,Y)=X\cdot Y^{-1}=\{(a,b)\in X\mid (b,a)\in Y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ca4842307a35e059897ef59d3219d1a578daa07)
![{\displaystyle {\mathfrak {F}}_{7}(X,Y)=X\cdot {\mathfrak {Cnv}}_{2}(Y)=\{(a,b,c)\in X\mid (a,c,b)\in Y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/989c3a82cccccf245edd2eca8eb14879b34ab21c)
![{\displaystyle {\mathfrak {F}}_{8}(X,Y)=X\cdot {\mathfrak {Cnv}}_{3}(Y)=\{(a,b,c)\in X\mid (c,a,b)\in Y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a30497db12f380afeb50e2655143c9693fe51ba)
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,
denotes range and so on. (Here the symbol
is used to restrict range, unlike the contemporary meaning of restriction.)
Jech (2003) uses the following set of 10 Gödel operations.
![{\displaystyle G_{1}(X,Y)=\{X,Y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd74e8272f512fdf6ee0c8a34b5d8c657112da14)
![{\displaystyle G_{2}(X,Y)=X\times Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b8b4d34469bae1794ce2fae455ea5037ceae63f)
![{\displaystyle G_{3}(X,Y)=\{(x,y)\mid x\in X,y\in Y,x\in y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1687252ecc30dfdf011b67a96cab5bf177bba5a0)
![{\displaystyle G_{4}(X,Y)=X-Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b19d4c9771696bdb1087cc7dc4dd48a513359923)
![{\displaystyle G_{5}(X,Y)=X\cap Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1675d199d8020a8100c002b3499080439522040)
![{\displaystyle G_{6}(X)=\cup X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52d87913a45da4996a283327ea5db95d83382f08)
![{\displaystyle G_{7}(X)={\text{dom}}(X)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ebf26f0d6e17ea4ba9068d186df6b0135d6002c)
![{\displaystyle G_{8}(X)=\{(x,y)\mid (y,x)\in X\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96b2c19ef290b2ce073036c4a61c5061820c76bd)
![{\displaystyle G_{9}(X)=\{(x,y,z)\mid (x,z,y)\in X\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4aba32b43425f8d5c7226ef11c580bb66df6898f)
![{\displaystyle G_{10}(X)=\{(x,y,z)\mid (y,z,x)\in X\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88248afabcba2a9b6caf369f5743e0c8de066bbe)
Properties
Gödel's normal form theorem states that if φ(x1,...xn) is a formula in the language of set theory with all quantifiers bounded, then the function {(x1,...,xn) ∈ X1×...×Xn | φ(x1, ..., xn)) of X1, ..., Xn 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
- ^ K. Devlin, An introduction to the fine structure of the constructible hierarchy (1974, p.11). Accessed 2022-02-26.