Question about Goedel's incompleteness ProofWhat 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 is the claim "I am in New York only if I am in America" the same as "If I am in New York, then I am in America?

Do airline pilots ever risk not hearing communication directed to them specifically, from traffic controllers?

What is the meaning of "of trouble" in the following sentence?

Is there a minimum number of transactions in a block?

Can Medicine checks be used, with decent rolls, to completely mitigate the risk of death from ongoing damage?

How can I fix this gap between bookcases I made?

"The augmented fourth (A4) and the diminished fifth (d5) are the only augmented and diminished intervals that appear in diatonic scales"

Why is "Reports" in sentence down without "The"

How do I create uniquely male characters?

What is the command to reset a PC without deleting any files

How to determine if window is maximised or minimised from bash script

What Brexit solution does the DUP want?

Modification to Chariots for Heavy Cavalry Analogue for 4-armed race

Why did the Germans forbid the possession of pet pigeons in Rostov-on-Don in 1941?

Download, install and reboot computer at night if needed

Copenhagen passport control - US citizen

Where to refill my bottle in India?

Copycat chess is back

Can a German sentence have two subjects?

Why does not dark matter gather and form celestial bodies?

What is the offset in a seaplane's hull?

Could a US political party gain complete control over the government by removing checks & balances?

How does one intimidate enemies without having the capacity for violence?

Why has Russell's definition of numbers using equivalence classes been finally abandoned? ( If it has actually been abandoned).



Question about Goedel's incompleteness Proof


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
    12 hours ago










  • $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
    12 hours ago











  • $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
    11 hours ago










  • $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
    11 hours ago











  • $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
    11 hours ago















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
    12 hours ago










  • $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
    12 hours ago











  • $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
    11 hours ago










  • $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
    11 hours ago











  • $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
    11 hours ago













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 10 hours ago







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 12 hours ago









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
    12 hours ago










  • $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
    12 hours ago











  • $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
    11 hours ago










  • $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
    11 hours ago











  • $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
    11 hours ago
















  • $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
    12 hours ago










  • $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
    12 hours ago











  • $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
    11 hours ago










  • $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
    11 hours ago











  • $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
    11 hours ago















$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
12 hours ago




$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
12 hours ago












$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
12 hours ago





$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
12 hours ago













$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
11 hours ago




$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
11 hours ago












$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
11 hours ago





$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
11 hours ago













$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
11 hours ago




$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
11 hours ago










2 Answers
2






active

oldest

votes


















3












$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
    8 hours ago










  • $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
    8 hours ago


















3












$begingroup$

Long comment



We have $text sub(a, x, b)$ (where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation output the formula that results from formula $a$ if in $a$ we replace $x$, wherever it is free, by $b$.



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



Consider e.g. as $a$ the formula $(x=0)$ and as the term $b$ the numeral $1$; then $text sub(a, v, b)$ will be $(1=0)$.



We arrive at the 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 Godel-number) $p = ulcorner P(y) urcorner$.



Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the said term. 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 number term $p$ (using the corresponding numeral $S(S( ldots (0) ldots)$, i.e. a term with no variables inside).



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.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    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









    3












    $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
      8 hours ago










    • $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
      8 hours ago















    3












    $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
      8 hours ago










    • $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
      8 hours ago













    3












    3








    3





    $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 8 hours ago

























    answered 11 hours ago









    Noah SchweberNoah Schweber

    128k10152294




    128k10152294











    • $begingroup$
      Thanks a lot! I understand it much better now.
      $endgroup$
      – Batuhan Erdogan
      8 hours ago










    • $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
      8 hours ago
















    • $begingroup$
      Thanks a lot! I understand it much better now.
      $endgroup$
      – Batuhan Erdogan
      8 hours ago










    • $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
      8 hours ago















    $begingroup$
    Thanks a lot! I understand it much better now.
    $endgroup$
    – Batuhan Erdogan
    8 hours ago




    $begingroup$
    Thanks a lot! I understand it much better now.
    $endgroup$
    – Batuhan Erdogan
    8 hours ago












    $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
    8 hours ago




    $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
    8 hours ago











    3












    $begingroup$

    Long comment



    We have $text sub(a, x, b)$ (where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation output the formula that results from formula $a$ if in $a$ we replace $x$, wherever it is free, by $b$.



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



    Consider e.g. as $a$ the formula $(x=0)$ and as the term $b$ the numeral $1$; then $text sub(a, v, b)$ will be $(1=0)$.



    We arrive at the 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 Godel-number) $p = ulcorner P(y) urcorner$.



    Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the said term. 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 number term $p$ (using the corresponding numeral $S(S( ldots (0) ldots)$, i.e. a term with no variables inside).



    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$

      Long comment



      We have $text sub(a, x, b)$ (where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation output the formula that results from formula $a$ if in $a$ we replace $x$, wherever it is free, by $b$.



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



      Consider e.g. as $a$ the formula $(x=0)$ and as the term $b$ the numeral $1$; then $text sub(a, v, b)$ will be $(1=0)$.



      We arrive at the 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 Godel-number) $p = ulcorner P(y) urcorner$.



      Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the said term. 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 number term $p$ (using the corresponding numeral $S(S( ldots (0) ldots)$, i.e. a term with no variables inside).



      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$

        Long comment



        We have $text sub(a, x, b)$ (where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation output the formula that results from formula $a$ if in $a$ we replace $x$, wherever it is free, by $b$.



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



        Consider e.g. as $a$ the formula $(x=0)$ and as the term $b$ the numeral $1$; then $text sub(a, v, b)$ will be $(1=0)$.



        We arrive at the 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 Godel-number) $p = ulcorner P(y) urcorner$.



        Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the said term. 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 number term $p$ (using the corresponding numeral $S(S( ldots (0) ldots)$, i.e. a term with no variables inside).



        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$



        Long comment



        We have $text sub(a, x, b)$ (where $a$ stands for a formula, $x$ for a variable, and $b$ for a term. The operation output the formula that results from formula $a$ if in $a$ we replace $x$, wherever it is free, by $b$.



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



        Consider e.g. as $a$ the formula $(x=0)$ and as the term $b$ the numeral $1$; then $text sub(a, v, b)$ will be $(1=0)$.



        We arrive at the 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 Godel-number) $p = ulcorner P(y) urcorner$.



        Finally, we use the number $p$ and replace the free variables $y$ in the above formula with the said term. 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 number term $p$ (using the corresponding numeral $S(S( ldots (0) ldots)$, i.e. a term with no variables inside).



        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










        answered 11 hours ago









        Mauro ALLEGRANZAMauro ALLEGRANZA

        67.8k449117




        67.8k449117




















            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

            Disable / Remove link to Product Items in Cart Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How can I limit products that can be bought / added to cart?Remove item from cartHide “Add to Cart” button if specific products are already in cart“Prettifying” the custom options in cart pageCreate link in cart sidebar to view all added items After limit reachedLink products together in checkout/cartHow to Get product from cart and add it againHide action-edit on cart page if simple productRemoving Cart items - ObserverRemove wishlist items when added to cart

            Helsingin valtaus Sisällysluettelo Taustaa | Yleistä sotatoimista | Osapuolet | Taistelut Helsingin ympäristössä | Punaisten antautumissuunnitelma | Taistelujen kulku Helsingissä | Valtauksen jälkeen | Tappiot | Muistaminen | Kirjallisuutta | Lähteet | Aiheesta muualla | NavigointivalikkoTeoksen verkkoversioTeoksen verkkoversioGoogle BooksSisällissota Helsingissä päättyi tasan 95 vuotta sittenSaksalaisten ylivoima jyräsi punaisen HelsinginSuomalaiset kuvaavat sotien jälkiä kaupungeissa – katso kuvat ja tarinat tutuilta kulmiltaHelsingin valtaus 90 vuotta sittenSaksalaiset valtasivat HelsinginHyökkäys HelsinkiinHelsingin valtaus 12.–13.4. 1918Saksalaiset käyttivät ihmiskilpiä Helsingin valtauksessa 1918Teoksen verkkoversioTeoksen verkkoversioSaksalaiset hyökkäävät Etelä-SuomeenTaistelut LeppävaarassaSotilaat ja taistelutLeppävaara 1918 huhtikuussa. KapinatarinaHelsingin taistelut 1918Saksalaisten voitonparaati HelsingissäHelsingin valtausta juhlittiinSaksalaisten Helsinki vuonna 1918Helsingin taistelussa kaatuneet valkokaartilaisetHelsinkiin haudatut taisteluissa kaatuneet punaiset12.4.1918 Helsingin valtauksessa saksalaiset apujoukot vapauttavat kaupunginVapaussodan muistomerkkejä Helsingissä ja pääkaupunkiseudullaCrescendo / Vuoden 1918 Kansalaissodan uhrien muistomerkkim

            Adjektiivitarina Tarinan tekeminen | Esimerkki: ennen | Esimerkki: jälkeen | Navigointivalikko