Question about Goedel's incompleteness Proof The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)What philosophical consequence of Goedel's incompleteness theorems?An ignorant question about the incompleteness theoremQuestion about quantifier logicQuestion about the incompleteness proof (Theorem V)What sort of sentence is the Goedel Sentence (for the First Incompleteness Theorem)?Gödel's incompleteness theorem - question about self referenceQuestion about Gödel's Incompleteness TheoremProof by contrapositive, what should I be assuming?True yet unprovable statement?Godel's theorem incompleteness, truth vs.provability

How to copy the contents of all files with a certain name into a new file?

What aspect of planet Earth must be changed to prevent the industrial revolution?

University's motivation for having tenure-track positions

Searching for a differential characteristic (differential cryptanalysis)

Can the prologue be the backstory of your main character?

When did F become S in typeography, and why?

The following signatures were invalid: EXPKEYSIG 1397BC53640DB551

Are my PIs rude or am I just being too sensitive?

How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time

Can a novice safely splice in wire to lengthen 5V charging cable?

Cooking pasta in a water boiler

Does Parliament need to approve the new Brexit delay to 31 October 2019?

Did God make two great lights or did He make the great light two?

What are these Gizmos at Izaña Atmospheric Research Center in Spain?

Scientific Reports - Significant Figures

How to delete random line from file using Unix command?

ELI5: Why do they say that Israel would have been the fourth country to land a spacecraft on the Moon and why do they call it low cost?

Segmentation fault output is suppressed when piping stdin into a function. Why?

Keeping a retro style to sci-fi spaceships?

"... to apply for a visa" or "... and applied for a visa"?

Would an alien lifeform be able to achieve space travel if lacking in vision?

Problems with Ubuntu mount /tmp

Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?

What is special about square numbers here?



Question about Goedel's incompleteness Proof



The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)What philosophical consequence of Goedel's incompleteness theorems?An ignorant question about the incompleteness theoremQuestion about quantifier logicQuestion about the incompleteness proof (Theorem V)What sort of sentence is the Goedel Sentence (for the First Incompleteness Theorem)?Gödel's incompleteness theorem - question about self referenceQuestion about Gödel's Incompleteness TheoremProof by contrapositive, what should I be assuming?True yet unprovable statement?Godel's theorem incompleteness, truth vs.provability










3












$begingroup$


There is only one problem I have with Goedel's proof as explained in Nagel & Newman's book.



It assumes that you can actually construct a G statement along the lines described in the proof in PM, but as far as I'm aware there is no guarantee that such a G statement can be written down in finitude. In fact, the term denoted by sub(n, 17,n) itself looks like it needs to have a greater Goedel number than sub(n, 17,n), which is by definition the Goedel number of the entire G statement (which implies it's represented by a longer string / formula than the statement it's a part of)! We already know that in order for any formula to have a Goedel number associated with it, it needs to be able to be represented by a finite string of signs!



It appears to me that you would encounter the same problem regardless of what formal system you use. Using the sample PM the authors introduce would get you stuck writing the statement ad infinitum!



Thanks in advance for any help.



edit 1:
The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, the resulting statement would have a g-number greater than sub(n, 17, n). (Even the representation of the number sub(n, 17, n) alone in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4). So, how can we actually write down such a statement?










share|cite|improve this question









New contributor




Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$











  • $begingroup$
    Not very clear... A formula is a finite stirng of symbols and thus its godel number is a finite number, however huge.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:28










  • $begingroup$
    In a nutshell : we have a formula $varphi(x)$ with a free var $x$. We compute its g-number $ulcorner varphi(x) urcorner$ and substitute the numeral (the "name" of the number) into the previous formula. The result is a sentence (a formula without free vars). See Gödel’s Incompleteness Theorems.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:31











  • $begingroup$
    In other terms, you have a formula $varphi(x)$ with g-number $n$. Then you apply the substitution operation $text subst(n, 17,n)$ that means replace into the formula with g-number $n$ the free var $x$ (the number $17$ is the code of the first free var) with the numeral for the number $n$. the result is a new formula $G$ that is a sentence because the free var $x$ has been replaced by a term.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:48










  • $begingroup$
    The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, (…)
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 18:52











  • $begingroup$
    (...) the resulting statement would have a g-number greater than sub(n, 17, n). [[ Even the representation of the number sub(n, 17, n) in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4 ]]. So, how can we actually write down such a statement?
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 18:57















3












$begingroup$


There is only one problem I have with Goedel's proof as explained in Nagel & Newman's book.



It assumes that you can actually construct a G statement along the lines described in the proof in PM, but as far as I'm aware there is no guarantee that such a G statement can be written down in finitude. In fact, the term denoted by sub(n, 17,n) itself looks like it needs to have a greater Goedel number than sub(n, 17,n), which is by definition the Goedel number of the entire G statement (which implies it's represented by a longer string / formula than the statement it's a part of)! We already know that in order for any formula to have a Goedel number associated with it, it needs to be able to be represented by a finite string of signs!



It appears to me that you would encounter the same problem regardless of what formal system you use. Using the sample PM the authors introduce would get you stuck writing the statement ad infinitum!



Thanks in advance for any help.



edit 1:
The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, the resulting statement would have a g-number greater than sub(n, 17, n). (Even the representation of the number sub(n, 17, n) alone in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4). So, how can we actually write down such a statement?










share|cite|improve this question









New contributor




Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$











  • $begingroup$
    Not very clear... A formula is a finite stirng of symbols and thus its godel number is a finite number, however huge.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:28










  • $begingroup$
    In a nutshell : we have a formula $varphi(x)$ with a free var $x$. We compute its g-number $ulcorner varphi(x) urcorner$ and substitute the numeral (the "name" of the number) into the previous formula. The result is a sentence (a formula without free vars). See Gödel’s Incompleteness Theorems.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:31











  • $begingroup$
    In other terms, you have a formula $varphi(x)$ with g-number $n$. Then you apply the substitution operation $text subst(n, 17,n)$ that means replace into the formula with g-number $n$ the free var $x$ (the number $17$ is the code of the first free var) with the numeral for the number $n$. the result is a new formula $G$ that is a sentence because the free var $x$ has been replaced by a term.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:48










  • $begingroup$
    The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, (…)
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 18:52











  • $begingroup$
    (...) the resulting statement would have a g-number greater than sub(n, 17, n). [[ Even the representation of the number sub(n, 17, n) in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4 ]]. So, how can we actually write down such a statement?
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 18:57













3












3








3





$begingroup$


There is only one problem I have with Goedel's proof as explained in Nagel & Newman's book.



It assumes that you can actually construct a G statement along the lines described in the proof in PM, but as far as I'm aware there is no guarantee that such a G statement can be written down in finitude. In fact, the term denoted by sub(n, 17,n) itself looks like it needs to have a greater Goedel number than sub(n, 17,n), which is by definition the Goedel number of the entire G statement (which implies it's represented by a longer string / formula than the statement it's a part of)! We already know that in order for any formula to have a Goedel number associated with it, it needs to be able to be represented by a finite string of signs!



It appears to me that you would encounter the same problem regardless of what formal system you use. Using the sample PM the authors introduce would get you stuck writing the statement ad infinitum!



Thanks in advance for any help.



edit 1:
The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, the resulting statement would have a g-number greater than sub(n, 17, n). (Even the representation of the number sub(n, 17, n) alone in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4). So, how can we actually write down such a statement?










share|cite|improve this question









New contributor




Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




There is only one problem I have with Goedel's proof as explained in Nagel & Newman's book.



It assumes that you can actually construct a G statement along the lines described in the proof in PM, but as far as I'm aware there is no guarantee that such a G statement can be written down in finitude. In fact, the term denoted by sub(n, 17,n) itself looks like it needs to have a greater Goedel number than sub(n, 17,n), which is by definition the Goedel number of the entire G statement (which implies it's represented by a longer string / formula than the statement it's a part of)! We already know that in order for any formula to have a Goedel number associated with it, it needs to be able to be represented by a finite string of signs!



It appears to me that you would encounter the same problem regardless of what formal system you use. Using the sample PM the authors introduce would get you stuck writing the statement ad infinitum!



Thanks in advance for any help.



edit 1:
The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, the resulting statement would have a g-number greater than sub(n, 17, n). (Even the representation of the number sub(n, 17, n) alone in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4). So, how can we actually write down such a statement?







logic incompleteness






share|cite|improve this question









New contributor




Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited Apr 7 at 20:07







Batuhan Erdogan













New contributor




Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked Apr 7 at 18:24









Batuhan ErdoganBatuhan Erdogan

183




183




New contributor




Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Batuhan Erdogan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











  • $begingroup$
    Not very clear... A formula is a finite stirng of symbols and thus its godel number is a finite number, however huge.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:28










  • $begingroup$
    In a nutshell : we have a formula $varphi(x)$ with a free var $x$. We compute its g-number $ulcorner varphi(x) urcorner$ and substitute the numeral (the "name" of the number) into the previous formula. The result is a sentence (a formula without free vars). See Gödel’s Incompleteness Theorems.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:31











  • $begingroup$
    In other terms, you have a formula $varphi(x)$ with g-number $n$. Then you apply the substitution operation $text subst(n, 17,n)$ that means replace into the formula with g-number $n$ the free var $x$ (the number $17$ is the code of the first free var) with the numeral for the number $n$. the result is a new formula $G$ that is a sentence because the free var $x$ has been replaced by a term.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:48










  • $begingroup$
    The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, (…)
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 18:52











  • $begingroup$
    (...) the resulting statement would have a g-number greater than sub(n, 17, n). [[ Even the representation of the number sub(n, 17, n) in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4 ]]. So, how can we actually write down such a statement?
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 18:57
















  • $begingroup$
    Not very clear... A formula is a finite stirng of symbols and thus its godel number is a finite number, however huge.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:28










  • $begingroup$
    In a nutshell : we have a formula $varphi(x)$ with a free var $x$. We compute its g-number $ulcorner varphi(x) urcorner$ and substitute the numeral (the "name" of the number) into the previous formula. The result is a sentence (a formula without free vars). See Gödel’s Incompleteness Theorems.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:31











  • $begingroup$
    In other terms, you have a formula $varphi(x)$ with g-number $n$. Then you apply the substitution operation $text subst(n, 17,n)$ that means replace into the formula with g-number $n$ the free var $x$ (the number $17$ is the code of the first free var) with the numeral for the number $n$. the result is a new formula $G$ that is a sentence because the free var $x$ has been replaced by a term.
    $endgroup$
    – Mauro ALLEGRANZA
    Apr 7 at 18:48










  • $begingroup$
    The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, (…)
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 18:52











  • $begingroup$
    (...) the resulting statement would have a g-number greater than sub(n, 17, n). [[ Even the representation of the number sub(n, 17, n) in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4 ]]. So, how can we actually write down such a statement?
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 18:57















$begingroup$
Not very clear... A formula is a finite stirng of symbols and thus its godel number is a finite number, however huge.
$endgroup$
– Mauro ALLEGRANZA
Apr 7 at 18:28




$begingroup$
Not very clear... A formula is a finite stirng of symbols and thus its godel number is a finite number, however huge.
$endgroup$
– Mauro ALLEGRANZA
Apr 7 at 18:28












$begingroup$
In a nutshell : we have a formula $varphi(x)$ with a free var $x$. We compute its g-number $ulcorner varphi(x) urcorner$ and substitute the numeral (the "name" of the number) into the previous formula. The result is a sentence (a formula without free vars). See Gödel’s Incompleteness Theorems.
$endgroup$
– Mauro ALLEGRANZA
Apr 7 at 18:31





$begingroup$
In a nutshell : we have a formula $varphi(x)$ with a free var $x$. We compute its g-number $ulcorner varphi(x) urcorner$ and substitute the numeral (the "name" of the number) into the previous formula. The result is a sentence (a formula without free vars). See Gödel’s Incompleteness Theorems.
$endgroup$
– Mauro ALLEGRANZA
Apr 7 at 18:31













$begingroup$
In other terms, you have a formula $varphi(x)$ with g-number $n$. Then you apply the substitution operation $text subst(n, 17,n)$ that means replace into the formula with g-number $n$ the free var $x$ (the number $17$ is the code of the first free var) with the numeral for the number $n$. the result is a new formula $G$ that is a sentence because the free var $x$ has been replaced by a term.
$endgroup$
– Mauro ALLEGRANZA
Apr 7 at 18:48




$begingroup$
In other terms, you have a formula $varphi(x)$ with g-number $n$. Then you apply the substitution operation $text subst(n, 17,n)$ that means replace into the formula with g-number $n$ the free var $x$ (the number $17$ is the code of the first free var) with the numeral for the number $n$. the result is a new formula $G$ that is a sentence because the free var $x$ has been replaced by a term.
$endgroup$
– Mauro ALLEGRANZA
Apr 7 at 18:48












$begingroup$
The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, (…)
$endgroup$
– Batuhan Erdogan
Apr 7 at 18:52





$begingroup$
The G sentence in the book is defined as: ~(E x) Dem (x, Sub (n, 17, n)) , where n is the g-number of the statement "~(E x) Dem (x, Sub (y, 17, y))" (lets call this A). Therefore G basically means that the statement you obtain by substituting for variable "y" in A is not provable, and since replacing y in A gives you G itself, we understand that G refers to itself. The problem I have is that G by definition has a g-number g = sub (n, 17, n), which is a substring of G. Since representing G would require using both the numeral of Sub( n , 17, n) and some other signs, (…)
$endgroup$
– Batuhan Erdogan
Apr 7 at 18:52













$begingroup$
(...) the resulting statement would have a g-number greater than sub(n, 17, n). [[ Even the representation of the number sub(n, 17, n) in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4 ]]. So, how can we actually write down such a statement?
$endgroup$
– Batuhan Erdogan
Apr 7 at 18:57




$begingroup$
(...) the resulting statement would have a g-number greater than sub(n, 17, n). [[ Even the representation of the number sub(n, 17, n) in PM has a g-number greater than sub(n, 17, n), just as representing 4 as "ssss0" would have a greater g-number than 4 ]]. So, how can we actually write down such a statement?
$endgroup$
– Batuhan Erdogan
Apr 7 at 18:57










2 Answers
2






active

oldest

votes


















4












$begingroup$

You are right that there's no reason to believe that we can write down a sentence which includes (the numeral for) its Godel number as a subterm; however, that's not what we actually need to do here.



Below, $T$ is the particular theory we're looking at - e.g. PA - and I write "$underlinen$" for the numeral corresponding to the number $n$.



Before addressing Nagel/Newman's presentation, let me first give a self-contained summary of what we're trying to do; then I'll say exactly what's going on with their exposition in particular.




On the face of it, we might consider a formula $varphi$ to be self-referential if $underlinevarphi$ (or $underlinevarphi(t)$ for some term $t$) occurs in $varphi$ as a term. However, as you correctly observe this is an extremely hard to satisfy property, and perhaps no such formulas exist.



Instead, fixing a given Godel numbering function $mu$, we'll be satisfied with a weaker notion of self-reference:




Fix a formula $varphi$ with one free variable. We say that a sentence $theta$ asserts its own $varphi$-ness via $mu$ if $$Tvdash[thetaiffvarphi(underlinemu(theta))].$$




Note that we do not require $theta$ to literally be the sentence $varphi(underlinemu(theta))$, merely that these two sentences be ($T$-provably) equivalent. Now there is no "size barrier" to self-reference at all; perhaps $theta$ looks nothing like $varphi(underlinemu(theta))$ on the face of it! (And indeed this can happen.)



The choice of $mu$ matters, of course - there's no reason to suspect a priori that sentences which are assert their own $varphi$-ness via $mu$ actually exist. This is where most of the work of Godel's argument comes in: picking a "good enough" map $mu$ and analyzing it appropriately.




Now how is this reflected in Nagel/Newman?



Well, we have a formula in one free variable $y$ (not a sentence; this matters a bit) which I'll abbreviate $H$; it has some Godel number $n$ with corresponding numeral $underlinen$.



Now the expression $G=H(underlinen)$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underlinen$ - clearly makes sense. Note that $n$ is fixed before I do this, so there's no self-referentiality shenanigans going on here.



OK, now where do we get self-reference? Well, the resulting sentence $G$ has its own Godel number $k$, and presumably $knot=n$. However, we are nonetheless able to prove that $$Tvdash Giff H(underlinek).$$ Note that the expression $H(underlinek)$ has its own Godel number $j$, which - again - presumably is neither $m$ nor $k$.



So there's no "perfect" self-reference going on, only the weaker "coincidental" version we've described above; but this is enough for our purposes.




EDIT: A lingering question, after all this, is whether "strong" self-reference is possible at all. Note that it's easy to rule out strong self-reference for some specific Godel numberings, but that doesn't mean that there aren't approaches which do allow strong self-reference.



It turns out that this is indeed possible! So that's neat. In my opinion, though, the approach above is more fundamental: the "punchline theorem" is that any Godel numbering method satisfying a list of non-syntactical properties automatically allows weak self-reference, whereas there doesn't seem to be a similarly non-syntactical condition guaranteeing strong self-reference.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Thanks a lot! I understand it much better now.
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 21:49










  • $begingroup$
    @BatuhanErdogan Glad to help! And I've added a bit which I only just remembered, which I think you'll find quite interesting.
    $endgroup$
    – Noah Schweber
    Apr 7 at 21:58


















3












$begingroup$

We have $text Sub(a, x, b)$, where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation outputs the formula that results from formula $a$ when we replace every free occurrence of variable $x$ in $a$ with term $b$.



Obviously, $text Sub(a, x, b)$ is different from $a$.



Consider the example (page 87) of formula $exists x(x=sy)$ (where variable $y$ is free) with Gödel number $m$. Then we replace the "name" for $m$, i.e. the numeral $ss ldots s0$ ($m$ copies of $s$), in place of variable $y$, thus performing the operation $text sub(m, 17, m)$.



What we get is a new formula (without free variables) $exists x(x=sss ldots s0)$ which has a new Gödel-number $r$ (see footnote page 88 for the instructions on how to compute it).



This machinery is used (see page 96) to manufacture the crucial formula $lnot text Dem(x, text Sub(y, 17, y)).$



It is a formula $Q(x,y)$ with two free vars.



Consider its universal closure $P(x)= forall x Q(x,y)$, i.e. $lnot exists x text Dem(x, text Sub(y, 17, y)).$



It is a formula with only one free var : $y$.



This formula has a code (its Gödel-number) $p = ulcorner P(y) urcorner$.



Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the corersponding numeral (a term of the language). We get a new formula $G$ with its own code :




$ulcorner G urcorner = text Sub(p, 17, p)$.




The new formual $G$ has no more free variables, because the only free variable $y$ of the formula $P(y)$ has been "filled" withe the numeral for $p$ (i.e. the corresponding closed term $SS ldots s0$, $p$ copies of $s$, with no variables inside it).



This process is called diagonalization :




This is the idea of taking a wff $varphi(y)$, and substituting (the numeral for) its own code number in place of the free variable. Think of a code number as a way of referring to a wff. Then the operation of ‘diagonalization’ allows us to form a wff that as it were indirectly refers to itself (refers to itself via the Gödel coding). We will use this trick [...] to form a Gödel sentence that encodes ‘I am unprovable in $mathsfPA$’.




Thus, if formula $Q(x, y)$ above "means" : "$x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of the (only) free variable", we have that $P(x) = forall x Q(x,y)$ means : "for all $x$, $x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of its only free variable".



I.e. $P(x)$ means "the formula ... is unprovable".



This formula has a code $p$; repeat the process and what we get is a sentence $G$ that says...






share|cite|improve this answer











$endgroup$













    Your Answer








    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "69"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );






    Batuhan Erdogan is a new contributor. Be nice, and check out our Code of Conduct.









    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3178598%2fquestion-about-goedels-incompleteness-proof%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    4












    $begingroup$

    You are right that there's no reason to believe that we can write down a sentence which includes (the numeral for) its Godel number as a subterm; however, that's not what we actually need to do here.



    Below, $T$ is the particular theory we're looking at - e.g. PA - and I write "$underlinen$" for the numeral corresponding to the number $n$.



    Before addressing Nagel/Newman's presentation, let me first give a self-contained summary of what we're trying to do; then I'll say exactly what's going on with their exposition in particular.




    On the face of it, we might consider a formula $varphi$ to be self-referential if $underlinevarphi$ (or $underlinevarphi(t)$ for some term $t$) occurs in $varphi$ as a term. However, as you correctly observe this is an extremely hard to satisfy property, and perhaps no such formulas exist.



    Instead, fixing a given Godel numbering function $mu$, we'll be satisfied with a weaker notion of self-reference:




    Fix a formula $varphi$ with one free variable. We say that a sentence $theta$ asserts its own $varphi$-ness via $mu$ if $$Tvdash[thetaiffvarphi(underlinemu(theta))].$$




    Note that we do not require $theta$ to literally be the sentence $varphi(underlinemu(theta))$, merely that these two sentences be ($T$-provably) equivalent. Now there is no "size barrier" to self-reference at all; perhaps $theta$ looks nothing like $varphi(underlinemu(theta))$ on the face of it! (And indeed this can happen.)



    The choice of $mu$ matters, of course - there's no reason to suspect a priori that sentences which are assert their own $varphi$-ness via $mu$ actually exist. This is where most of the work of Godel's argument comes in: picking a "good enough" map $mu$ and analyzing it appropriately.




    Now how is this reflected in Nagel/Newman?



    Well, we have a formula in one free variable $y$ (not a sentence; this matters a bit) which I'll abbreviate $H$; it has some Godel number $n$ with corresponding numeral $underlinen$.



    Now the expression $G=H(underlinen)$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underlinen$ - clearly makes sense. Note that $n$ is fixed before I do this, so there's no self-referentiality shenanigans going on here.



    OK, now where do we get self-reference? Well, the resulting sentence $G$ has its own Godel number $k$, and presumably $knot=n$. However, we are nonetheless able to prove that $$Tvdash Giff H(underlinek).$$ Note that the expression $H(underlinek)$ has its own Godel number $j$, which - again - presumably is neither $m$ nor $k$.



    So there's no "perfect" self-reference going on, only the weaker "coincidental" version we've described above; but this is enough for our purposes.




    EDIT: A lingering question, after all this, is whether "strong" self-reference is possible at all. Note that it's easy to rule out strong self-reference for some specific Godel numberings, but that doesn't mean that there aren't approaches which do allow strong self-reference.



    It turns out that this is indeed possible! So that's neat. In my opinion, though, the approach above is more fundamental: the "punchline theorem" is that any Godel numbering method satisfying a list of non-syntactical properties automatically allows weak self-reference, whereas there doesn't seem to be a similarly non-syntactical condition guaranteeing strong self-reference.






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      Thanks a lot! I understand it much better now.
      $endgroup$
      – Batuhan Erdogan
      Apr 7 at 21:49










    • $begingroup$
      @BatuhanErdogan Glad to help! And I've added a bit which I only just remembered, which I think you'll find quite interesting.
      $endgroup$
      – Noah Schweber
      Apr 7 at 21:58















    4












    $begingroup$

    You are right that there's no reason to believe that we can write down a sentence which includes (the numeral for) its Godel number as a subterm; however, that's not what we actually need to do here.



    Below, $T$ is the particular theory we're looking at - e.g. PA - and I write "$underlinen$" for the numeral corresponding to the number $n$.



    Before addressing Nagel/Newman's presentation, let me first give a self-contained summary of what we're trying to do; then I'll say exactly what's going on with their exposition in particular.




    On the face of it, we might consider a formula $varphi$ to be self-referential if $underlinevarphi$ (or $underlinevarphi(t)$ for some term $t$) occurs in $varphi$ as a term. However, as you correctly observe this is an extremely hard to satisfy property, and perhaps no such formulas exist.



    Instead, fixing a given Godel numbering function $mu$, we'll be satisfied with a weaker notion of self-reference:




    Fix a formula $varphi$ with one free variable. We say that a sentence $theta$ asserts its own $varphi$-ness via $mu$ if $$Tvdash[thetaiffvarphi(underlinemu(theta))].$$




    Note that we do not require $theta$ to literally be the sentence $varphi(underlinemu(theta))$, merely that these two sentences be ($T$-provably) equivalent. Now there is no "size barrier" to self-reference at all; perhaps $theta$ looks nothing like $varphi(underlinemu(theta))$ on the face of it! (And indeed this can happen.)



    The choice of $mu$ matters, of course - there's no reason to suspect a priori that sentences which are assert their own $varphi$-ness via $mu$ actually exist. This is where most of the work of Godel's argument comes in: picking a "good enough" map $mu$ and analyzing it appropriately.




    Now how is this reflected in Nagel/Newman?



    Well, we have a formula in one free variable $y$ (not a sentence; this matters a bit) which I'll abbreviate $H$; it has some Godel number $n$ with corresponding numeral $underlinen$.



    Now the expression $G=H(underlinen)$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underlinen$ - clearly makes sense. Note that $n$ is fixed before I do this, so there's no self-referentiality shenanigans going on here.



    OK, now where do we get self-reference? Well, the resulting sentence $G$ has its own Godel number $k$, and presumably $knot=n$. However, we are nonetheless able to prove that $$Tvdash Giff H(underlinek).$$ Note that the expression $H(underlinek)$ has its own Godel number $j$, which - again - presumably is neither $m$ nor $k$.



    So there's no "perfect" self-reference going on, only the weaker "coincidental" version we've described above; but this is enough for our purposes.




    EDIT: A lingering question, after all this, is whether "strong" self-reference is possible at all. Note that it's easy to rule out strong self-reference for some specific Godel numberings, but that doesn't mean that there aren't approaches which do allow strong self-reference.



    It turns out that this is indeed possible! So that's neat. In my opinion, though, the approach above is more fundamental: the "punchline theorem" is that any Godel numbering method satisfying a list of non-syntactical properties automatically allows weak self-reference, whereas there doesn't seem to be a similarly non-syntactical condition guaranteeing strong self-reference.






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      Thanks a lot! I understand it much better now.
      $endgroup$
      – Batuhan Erdogan
      Apr 7 at 21:49










    • $begingroup$
      @BatuhanErdogan Glad to help! And I've added a bit which I only just remembered, which I think you'll find quite interesting.
      $endgroup$
      – Noah Schweber
      Apr 7 at 21:58













    4












    4








    4





    $begingroup$

    You are right that there's no reason to believe that we can write down a sentence which includes (the numeral for) its Godel number as a subterm; however, that's not what we actually need to do here.



    Below, $T$ is the particular theory we're looking at - e.g. PA - and I write "$underlinen$" for the numeral corresponding to the number $n$.



    Before addressing Nagel/Newman's presentation, let me first give a self-contained summary of what we're trying to do; then I'll say exactly what's going on with their exposition in particular.




    On the face of it, we might consider a formula $varphi$ to be self-referential if $underlinevarphi$ (or $underlinevarphi(t)$ for some term $t$) occurs in $varphi$ as a term. However, as you correctly observe this is an extremely hard to satisfy property, and perhaps no such formulas exist.



    Instead, fixing a given Godel numbering function $mu$, we'll be satisfied with a weaker notion of self-reference:




    Fix a formula $varphi$ with one free variable. We say that a sentence $theta$ asserts its own $varphi$-ness via $mu$ if $$Tvdash[thetaiffvarphi(underlinemu(theta))].$$




    Note that we do not require $theta$ to literally be the sentence $varphi(underlinemu(theta))$, merely that these two sentences be ($T$-provably) equivalent. Now there is no "size barrier" to self-reference at all; perhaps $theta$ looks nothing like $varphi(underlinemu(theta))$ on the face of it! (And indeed this can happen.)



    The choice of $mu$ matters, of course - there's no reason to suspect a priori that sentences which are assert their own $varphi$-ness via $mu$ actually exist. This is where most of the work of Godel's argument comes in: picking a "good enough" map $mu$ and analyzing it appropriately.




    Now how is this reflected in Nagel/Newman?



    Well, we have a formula in one free variable $y$ (not a sentence; this matters a bit) which I'll abbreviate $H$; it has some Godel number $n$ with corresponding numeral $underlinen$.



    Now the expression $G=H(underlinen)$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underlinen$ - clearly makes sense. Note that $n$ is fixed before I do this, so there's no self-referentiality shenanigans going on here.



    OK, now where do we get self-reference? Well, the resulting sentence $G$ has its own Godel number $k$, and presumably $knot=n$. However, we are nonetheless able to prove that $$Tvdash Giff H(underlinek).$$ Note that the expression $H(underlinek)$ has its own Godel number $j$, which - again - presumably is neither $m$ nor $k$.



    So there's no "perfect" self-reference going on, only the weaker "coincidental" version we've described above; but this is enough for our purposes.




    EDIT: A lingering question, after all this, is whether "strong" self-reference is possible at all. Note that it's easy to rule out strong self-reference for some specific Godel numberings, but that doesn't mean that there aren't approaches which do allow strong self-reference.



    It turns out that this is indeed possible! So that's neat. In my opinion, though, the approach above is more fundamental: the "punchline theorem" is that any Godel numbering method satisfying a list of non-syntactical properties automatically allows weak self-reference, whereas there doesn't seem to be a similarly non-syntactical condition guaranteeing strong self-reference.






    share|cite|improve this answer











    $endgroup$



    You are right that there's no reason to believe that we can write down a sentence which includes (the numeral for) its Godel number as a subterm; however, that's not what we actually need to do here.



    Below, $T$ is the particular theory we're looking at - e.g. PA - and I write "$underlinen$" for the numeral corresponding to the number $n$.



    Before addressing Nagel/Newman's presentation, let me first give a self-contained summary of what we're trying to do; then I'll say exactly what's going on with their exposition in particular.




    On the face of it, we might consider a formula $varphi$ to be self-referential if $underlinevarphi$ (or $underlinevarphi(t)$ for some term $t$) occurs in $varphi$ as a term. However, as you correctly observe this is an extremely hard to satisfy property, and perhaps no such formulas exist.



    Instead, fixing a given Godel numbering function $mu$, we'll be satisfied with a weaker notion of self-reference:




    Fix a formula $varphi$ with one free variable. We say that a sentence $theta$ asserts its own $varphi$-ness via $mu$ if $$Tvdash[thetaiffvarphi(underlinemu(theta))].$$




    Note that we do not require $theta$ to literally be the sentence $varphi(underlinemu(theta))$, merely that these two sentences be ($T$-provably) equivalent. Now there is no "size barrier" to self-reference at all; perhaps $theta$ looks nothing like $varphi(underlinemu(theta))$ on the face of it! (And indeed this can happen.)



    The choice of $mu$ matters, of course - there's no reason to suspect a priori that sentences which are assert their own $varphi$-ness via $mu$ actually exist. This is where most of the work of Godel's argument comes in: picking a "good enough" map $mu$ and analyzing it appropriately.




    Now how is this reflected in Nagel/Newman?



    Well, we have a formula in one free variable $y$ (not a sentence; this matters a bit) which I'll abbreviate $H$; it has some Godel number $n$ with corresponding numeral $underlinen$.



    Now the expression $G=H(underlinen)$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underlinen$ - clearly makes sense. Note that $n$ is fixed before I do this, so there's no self-referentiality shenanigans going on here.



    OK, now where do we get self-reference? Well, the resulting sentence $G$ has its own Godel number $k$, and presumably $knot=n$. However, we are nonetheless able to prove that $$Tvdash Giff H(underlinek).$$ Note that the expression $H(underlinek)$ has its own Godel number $j$, which - again - presumably is neither $m$ nor $k$.



    So there's no "perfect" self-reference going on, only the weaker "coincidental" version we've described above; but this is enough for our purposes.




    EDIT: A lingering question, after all this, is whether "strong" self-reference is possible at all. Note that it's easy to rule out strong self-reference for some specific Godel numberings, but that doesn't mean that there aren't approaches which do allow strong self-reference.



    It turns out that this is indeed possible! So that's neat. In my opinion, though, the approach above is more fundamental: the "punchline theorem" is that any Godel numbering method satisfying a list of non-syntactical properties automatically allows weak self-reference, whereas there doesn't seem to be a similarly non-syntactical condition guaranteeing strong self-reference.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Apr 7 at 21:58

























    answered Apr 7 at 19:37









    Noah SchweberNoah Schweber

    129k10152294




    129k10152294











    • $begingroup$
      Thanks a lot! I understand it much better now.
      $endgroup$
      – Batuhan Erdogan
      Apr 7 at 21:49










    • $begingroup$
      @BatuhanErdogan Glad to help! And I've added a bit which I only just remembered, which I think you'll find quite interesting.
      $endgroup$
      – Noah Schweber
      Apr 7 at 21:58
















    • $begingroup$
      Thanks a lot! I understand it much better now.
      $endgroup$
      – Batuhan Erdogan
      Apr 7 at 21:49










    • $begingroup$
      @BatuhanErdogan Glad to help! And I've added a bit which I only just remembered, which I think you'll find quite interesting.
      $endgroup$
      – Noah Schweber
      Apr 7 at 21:58















    $begingroup$
    Thanks a lot! I understand it much better now.
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 21:49




    $begingroup$
    Thanks a lot! I understand it much better now.
    $endgroup$
    – Batuhan Erdogan
    Apr 7 at 21:49












    $begingroup$
    @BatuhanErdogan Glad to help! And I've added a bit which I only just remembered, which I think you'll find quite interesting.
    $endgroup$
    – Noah Schweber
    Apr 7 at 21:58




    $begingroup$
    @BatuhanErdogan Glad to help! And I've added a bit which I only just remembered, which I think you'll find quite interesting.
    $endgroup$
    – Noah Schweber
    Apr 7 at 21:58











    3












    $begingroup$

    We have $text Sub(a, x, b)$, where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation outputs the formula that results from formula $a$ when we replace every free occurrence of variable $x$ in $a$ with term $b$.



    Obviously, $text Sub(a, x, b)$ is different from $a$.



    Consider the example (page 87) of formula $exists x(x=sy)$ (where variable $y$ is free) with Gödel number $m$. Then we replace the "name" for $m$, i.e. the numeral $ss ldots s0$ ($m$ copies of $s$), in place of variable $y$, thus performing the operation $text sub(m, 17, m)$.



    What we get is a new formula (without free variables) $exists x(x=sss ldots s0)$ which has a new Gödel-number $r$ (see footnote page 88 for the instructions on how to compute it).



    This machinery is used (see page 96) to manufacture the crucial formula $lnot text Dem(x, text Sub(y, 17, y)).$



    It is a formula $Q(x,y)$ with two free vars.



    Consider its universal closure $P(x)= forall x Q(x,y)$, i.e. $lnot exists x text Dem(x, text Sub(y, 17, y)).$



    It is a formula with only one free var : $y$.



    This formula has a code (its Gödel-number) $p = ulcorner P(y) urcorner$.



    Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the corersponding numeral (a term of the language). We get a new formula $G$ with its own code :




    $ulcorner G urcorner = text Sub(p, 17, p)$.




    The new formual $G$ has no more free variables, because the only free variable $y$ of the formula $P(y)$ has been "filled" withe the numeral for $p$ (i.e. the corresponding closed term $SS ldots s0$, $p$ copies of $s$, with no variables inside it).



    This process is called diagonalization :




    This is the idea of taking a wff $varphi(y)$, and substituting (the numeral for) its own code number in place of the free variable. Think of a code number as a way of referring to a wff. Then the operation of ‘diagonalization’ allows us to form a wff that as it were indirectly refers to itself (refers to itself via the Gödel coding). We will use this trick [...] to form a Gödel sentence that encodes ‘I am unprovable in $mathsfPA$’.




    Thus, if formula $Q(x, y)$ above "means" : "$x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of the (only) free variable", we have that $P(x) = forall x Q(x,y)$ means : "for all $x$, $x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of its only free variable".



    I.e. $P(x)$ means "the formula ... is unprovable".



    This formula has a code $p$; repeat the process and what we get is a sentence $G$ that says...






    share|cite|improve this answer











    $endgroup$

















      3












      $begingroup$

      We have $text Sub(a, x, b)$, where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation outputs the formula that results from formula $a$ when we replace every free occurrence of variable $x$ in $a$ with term $b$.



      Obviously, $text Sub(a, x, b)$ is different from $a$.



      Consider the example (page 87) of formula $exists x(x=sy)$ (where variable $y$ is free) with Gödel number $m$. Then we replace the "name" for $m$, i.e. the numeral $ss ldots s0$ ($m$ copies of $s$), in place of variable $y$, thus performing the operation $text sub(m, 17, m)$.



      What we get is a new formula (without free variables) $exists x(x=sss ldots s0)$ which has a new Gödel-number $r$ (see footnote page 88 for the instructions on how to compute it).



      This machinery is used (see page 96) to manufacture the crucial formula $lnot text Dem(x, text Sub(y, 17, y)).$



      It is a formula $Q(x,y)$ with two free vars.



      Consider its universal closure $P(x)= forall x Q(x,y)$, i.e. $lnot exists x text Dem(x, text Sub(y, 17, y)).$



      It is a formula with only one free var : $y$.



      This formula has a code (its Gödel-number) $p = ulcorner P(y) urcorner$.



      Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the corersponding numeral (a term of the language). We get a new formula $G$ with its own code :




      $ulcorner G urcorner = text Sub(p, 17, p)$.




      The new formual $G$ has no more free variables, because the only free variable $y$ of the formula $P(y)$ has been "filled" withe the numeral for $p$ (i.e. the corresponding closed term $SS ldots s0$, $p$ copies of $s$, with no variables inside it).



      This process is called diagonalization :




      This is the idea of taking a wff $varphi(y)$, and substituting (the numeral for) its own code number in place of the free variable. Think of a code number as a way of referring to a wff. Then the operation of ‘diagonalization’ allows us to form a wff that as it were indirectly refers to itself (refers to itself via the Gödel coding). We will use this trick [...] to form a Gödel sentence that encodes ‘I am unprovable in $mathsfPA$’.




      Thus, if formula $Q(x, y)$ above "means" : "$x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of the (only) free variable", we have that $P(x) = forall x Q(x,y)$ means : "for all $x$, $x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of its only free variable".



      I.e. $P(x)$ means "the formula ... is unprovable".



      This formula has a code $p$; repeat the process and what we get is a sentence $G$ that says...






      share|cite|improve this answer











      $endgroup$















        3












        3








        3





        $begingroup$

        We have $text Sub(a, x, b)$, where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation outputs the formula that results from formula $a$ when we replace every free occurrence of variable $x$ in $a$ with term $b$.



        Obviously, $text Sub(a, x, b)$ is different from $a$.



        Consider the example (page 87) of formula $exists x(x=sy)$ (where variable $y$ is free) with Gödel number $m$. Then we replace the "name" for $m$, i.e. the numeral $ss ldots s0$ ($m$ copies of $s$), in place of variable $y$, thus performing the operation $text sub(m, 17, m)$.



        What we get is a new formula (without free variables) $exists x(x=sss ldots s0)$ which has a new Gödel-number $r$ (see footnote page 88 for the instructions on how to compute it).



        This machinery is used (see page 96) to manufacture the crucial formula $lnot text Dem(x, text Sub(y, 17, y)).$



        It is a formula $Q(x,y)$ with two free vars.



        Consider its universal closure $P(x)= forall x Q(x,y)$, i.e. $lnot exists x text Dem(x, text Sub(y, 17, y)).$



        It is a formula with only one free var : $y$.



        This formula has a code (its Gödel-number) $p = ulcorner P(y) urcorner$.



        Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the corersponding numeral (a term of the language). We get a new formula $G$ with its own code :




        $ulcorner G urcorner = text Sub(p, 17, p)$.




        The new formual $G$ has no more free variables, because the only free variable $y$ of the formula $P(y)$ has been "filled" withe the numeral for $p$ (i.e. the corresponding closed term $SS ldots s0$, $p$ copies of $s$, with no variables inside it).



        This process is called diagonalization :




        This is the idea of taking a wff $varphi(y)$, and substituting (the numeral for) its own code number in place of the free variable. Think of a code number as a way of referring to a wff. Then the operation of ‘diagonalization’ allows us to form a wff that as it were indirectly refers to itself (refers to itself via the Gödel coding). We will use this trick [...] to form a Gödel sentence that encodes ‘I am unprovable in $mathsfPA$’.




        Thus, if formula $Q(x, y)$ above "means" : "$x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of the (only) free variable", we have that $P(x) = forall x Q(x,y)$ means : "for all $x$, $x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of its only free variable".



        I.e. $P(x)$ means "the formula ... is unprovable".



        This formula has a code $p$; repeat the process and what we get is a sentence $G$ that says...






        share|cite|improve this answer











        $endgroup$



        We have $text Sub(a, x, b)$, where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation outputs the formula that results from formula $a$ when we replace every free occurrence of variable $x$ in $a$ with term $b$.



        Obviously, $text Sub(a, x, b)$ is different from $a$.



        Consider the example (page 87) of formula $exists x(x=sy)$ (where variable $y$ is free) with Gödel number $m$. Then we replace the "name" for $m$, i.e. the numeral $ss ldots s0$ ($m$ copies of $s$), in place of variable $y$, thus performing the operation $text sub(m, 17, m)$.



        What we get is a new formula (without free variables) $exists x(x=sss ldots s0)$ which has a new Gödel-number $r$ (see footnote page 88 for the instructions on how to compute it).



        This machinery is used (see page 96) to manufacture the crucial formula $lnot text Dem(x, text Sub(y, 17, y)).$



        It is a formula $Q(x,y)$ with two free vars.



        Consider its universal closure $P(x)= forall x Q(x,y)$, i.e. $lnot exists x text Dem(x, text Sub(y, 17, y)).$



        It is a formula with only one free var : $y$.



        This formula has a code (its Gödel-number) $p = ulcorner P(y) urcorner$.



        Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the corersponding numeral (a term of the language). We get a new formula $G$ with its own code :




        $ulcorner G urcorner = text Sub(p, 17, p)$.




        The new formual $G$ has no more free variables, because the only free variable $y$ of the formula $P(y)$ has been "filled" withe the numeral for $p$ (i.e. the corresponding closed term $SS ldots s0$, $p$ copies of $s$, with no variables inside it).



        This process is called diagonalization :




        This is the idea of taking a wff $varphi(y)$, and substituting (the numeral for) its own code number in place of the free variable. Think of a code number as a way of referring to a wff. Then the operation of ‘diagonalization’ allows us to form a wff that as it were indirectly refers to itself (refers to itself via the Gödel coding). We will use this trick [...] to form a Gödel sentence that encodes ‘I am unprovable in $mathsfPA$’.




        Thus, if formula $Q(x, y)$ above "means" : "$x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of the (only) free variable", we have that $P(x) = forall x Q(x,y)$ means : "for all $x$, $x$ does not prove the formula obtained from the formula with code $y$ by subst of the numeral for $y$ in place of its only free variable".



        I.e. $P(x)$ means "the formula ... is unprovable".



        This formula has a code $p$; repeat the process and what we get is a sentence $G$ that says...







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Apr 8 at 15:54

























        answered Apr 7 at 19:42









        Mauro ALLEGRANZAMauro ALLEGRANZA

        67.9k449117




        67.9k449117




















            Batuhan Erdogan is a new contributor. Be nice, and check out our Code of Conduct.









            draft saved

            draft discarded


















            Batuhan Erdogan is a new contributor. Be nice, and check out our Code of Conduct.












            Batuhan Erdogan is a new contributor. Be nice, and check out our Code of Conduct.











            Batuhan Erdogan is a new contributor. Be nice, and check out our Code of Conduct.














            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3178598%2fquestion-about-goedels-incompleteness-proof%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            រឿង រ៉ូមេអូ និង ហ្ស៊ុយលីយេ សង្ខេបរឿង តួអង្គ បញ្ជីណែនាំ

            Crop image to path created in TikZ? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Crop an inserted image?TikZ pictures does not appear in posterImage behind and beyond crop marks?Tikz picture as large as possible on A4 PageTransparency vs image compression dilemmaHow to crop background from image automatically?Image does not cropTikzexternal capturing crop marks when externalizing pgfplots?How to include image path that contains a dollar signCrop image with left size given

            Romeo and Juliet ContentsCharactersSynopsisSourcesDate and textThemes and motifsCriticism and interpretationLegacyScene by sceneSee alsoNotes and referencesSourcesExternal linksNavigation menu"Consumer Price Index (estimate) 1800–"10.2307/28710160037-3222287101610.1093/res/II.5.31910.2307/45967845967810.2307/2869925286992510.1525/jams.1982.35.3.03a00050"Dada Masilo: South African dancer who breaks the rules"10.1093/res/os-XV.57.1610.2307/28680942868094"Sweet Sorrow: Mann-Korman's Romeo and Juliet Closes Sept. 5 at MN's Ordway"the original10.2307/45957745957710.1017/CCOL0521570476.009"Ram Leela box office collections hit massive Rs 100 crore, pulverises prediction"Archived"Broadway Revival of Romeo and Juliet, Starring Orlando Bloom and Condola Rashad, Will Close Dec. 8"Archived10.1075/jhp.7.1.04hon"Wherefore art thou, Romeo? To make us laugh at Navy Pier"the original10.1093/gmo/9781561592630.article.O006772"Ram-leela Review Roundup: Critics Hail Film as Best Adaptation of Romeo and Juliet"Archived10.2307/31946310047-77293194631"Romeo and Juliet get Twitter treatment""Juliet's Nurse by Lois Leveen""Romeo and Juliet: Orlando Bloom's Broadway Debut Released in Theaters for Valentine's Day"Archived"Romeo and Juliet Has No Balcony"10.1093/gmo/9781561592630.article.O00778110.2307/2867423286742310.1076/enst.82.2.115.959510.1080/00138380601042675"A plague o' both your houses: error in GCSE exam paper forces apology""Juliet of the Five O'Clock Shadow, and Other Wonders"10.2307/33912430027-4321339124310.2307/28487440038-7134284874410.2307/29123140149-661129123144728341M"Weekender Guide: Shakespeare on The Drive""balcony"UK public library membership"romeo"UK public library membership10.1017/CCOL9780521844291"Post-Zionist Critique on Israel and the Palestinians Part III: Popular Culture"10.2307/25379071533-86140377-919X2537907"Capulets and Montagues: UK exam board admit mixing names up in Romeo and Juliet paper"Istoria Novellamente Ritrovata di Due Nobili Amanti2027/mdp.390150822329610820-750X"GCSE exam error: Board accidentally rewrites Shakespeare"10.2307/29176390149-66112917639"Exam board apologises after error in English GCSE paper which confused characters in Shakespeare's Romeo and Juliet""From Mariotto and Ganozza to Romeo and Guilietta: Metamorphoses of a Renaissance Tale"10.2307/37323537323510.2307/2867455286745510.2307/28678912867891"10 Questions for Taylor Swift"10.2307/28680922868092"Haymarket Theatre""The Zeffirelli Way: Revealing Talk by Florentine Director""Michael Smuin: 1938-2007 / Prolific dance director had showy career"The Life and Art of Edwin BoothRomeo and JulietRomeo and JulietRomeo and JulietRomeo and JulietEasy Read Romeo and JulietRomeo and Julieteeecb12003684p(data)4099369-3n8211610759dbe00d-a9e2-41a3-b2c1-977dd692899302814385X313670221313670221