Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Gödel operation
open-in-new
<h2 id="definition">Definition</h2> <p>Gödel (1940) used the following eight operations as a set of Gödel operations (which he called fundamental operations): </p> <ol><li> F 1 ( X , Y ) = { X , Y } {\displaystyle {\mathfrak {F}}_{1}(X,Y)=\{X,Y\}} </li> <li> 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\}} </li> <li> F 3 ( X , Y ) = X − Y {\displaystyle {\mathfrak {F}}_{3}(X,Y)=X-Y} </li> <li> 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\}} </li> <li> 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\}} </li> <li> 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\}} </li> <li> 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\}} </li> <li> 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\}} </li></ol> <p>The second expression in each line gives Gödel's definition in his original notation, where the dot means intersection, <i>V</i> is the universe, <i>E</i> 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 <a href="/facts/Restriction_(mathematics)/JV59DhKy">restriction</a>.) </p><p>Jech (2003) uses the following set of 10 Gödel operations. </p> <ol><li> G 1 ( X , Y ) = { X , Y } {\displaystyle G_{1}(X,Y)=\{X,Y\}} </li> <li> G 2 ( X , Y ) = X × Y {\displaystyle G_{2}(X,Y)=X\times Y} </li> <li> 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\}} </li> <li> G 4 ( X , Y ) = X − Y {\displaystyle G_{4}(X,Y)=X-Y} </li> <li> G 5 ( X , Y ) = X ∩ Y {\displaystyle G_{5}(X,Y)=X\cap Y} </li> <li> G 6 ( X ) = ∪ X {\displaystyle G_{6}(X)=\cup X} </li> <li> G 7 ( X ) = dom ( X ) {\displaystyle G_{7}(X)={\text{dom}}(X)} </li> <li> G 8 ( X ) = { ( x , y ) ∣ ( y , x ) ∈ X } {\displaystyle G_{8}(X)=\{(x,y)\mid (y,x)\in X\}} </li> <li> G 9 ( X ) = { ( x , y , z ) ∣ ( x , z , y ) ∈ X } {\displaystyle G_{9}(X)=\{(x,y,z)\mid (x,z,y)\in X\}} </li> <li> G 10 ( X ) = { ( x , y , z ) ∣ ( y , z , x ) ∈ X } {\displaystyle G_{10}(X)=\{(x,y,z)\mid (y,z,x)\in X\}} </li></ol> <p>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})} .<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>p. 63 </p> <h2 id="properties">Properties</h2> <p>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 <a href="/facts/Jensen_hierarchy/ECsoKzRv">rudimentary functions</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>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 <a href="/facts/Kripke-Platek_set_theory/nrA8tqBB">Kripke-Platek set theory</a> admitting <a href="/facts/Urelements/YLbuKp37">urelements</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>p. 64 </p> <ul><li>Gödel, Kurt (1940). <a href="http://press.princeton.edu/titles/1034.html"><i>The Consistency of the Continuum Hypothesis</i></a>. Annals of Mathematics Studies. Vol. 3. Princeton, N. J.: Princeton University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-691-07927-1. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0002514">0002514</a>. {{cite book}}: ISBN / Date incompatibility (help)</li> <li><a href="/facts/Thomas_Jech/E4JQu4Mk">Jech, Thomas</a> (2003), <i>Set Theory: Millennium Edition</i>, Springer Monographs in Mathematics, Berlin, New York: <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-44085-7</li></ul> <h2 id="inline-references">Inline references</h2> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Barwise, Jon (1975). Admissible Sets and Structures. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-07451-1. <a href="3-540-07451-1" target="_blank">3-540-07451-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>K. Devlin, An introduction to the fine structure of the constructible hierarchy (1974, p.11). Accessed 2022-02-26. <a href="https://core.ac.uk/download/pdf/30905237.pdf" target="_blank">https://core.ac.uk/download/pdf/30905237.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Barwise, Jon (1975). Admissible Sets and Structures. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-07451-1. <a href="3-540-07451-1" target="_blank">3-540-07451-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>