Question about Goedel's incompleteness Proof
$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?
logic incompleteness
New contributor
$endgroup$
|
show 1 more comment
$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?
logic incompleteness
New contributor
$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
|
show 1 more comment
$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?
logic incompleteness
New contributor
$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
logic incompleteness
New contributor
New contributor
edited Apr 7 at 20:07
Batuhan Erdogan
New contributor
asked Apr 7 at 18:24
Batuhan ErdoganBatuhan Erdogan
183
183
New contributor
New contributor
$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
|
show 1 more comment
$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
|
show 1 more comment
2 Answers
2
active
oldest
votes
$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 "$underline{n}$" 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 $underline{varphi}$ (or $underline{varphi(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(underline{mu(theta)})].$$
Note that we do not require $theta$ to literally be the sentence $varphi(underline{mu(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(underline{mu(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 $underline{n}$.
Now the expression $G=H(underline{n})$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underline{n}$ - 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(underline{k}).$$ Note that the expression $H(underline{k})$ 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.
$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
add a comment |
$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 $mathsf{PA}$’.
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...
$endgroup$
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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 "$underline{n}$" 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 $underline{varphi}$ (or $underline{varphi(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(underline{mu(theta)})].$$
Note that we do not require $theta$ to literally be the sentence $varphi(underline{mu(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(underline{mu(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 $underline{n}$.
Now the expression $G=H(underline{n})$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underline{n}$ - 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(underline{k}).$$ Note that the expression $H(underline{k})$ 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.
$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
add a comment |
$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 "$underline{n}$" 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 $underline{varphi}$ (or $underline{varphi(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(underline{mu(theta)})].$$
Note that we do not require $theta$ to literally be the sentence $varphi(underline{mu(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(underline{mu(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 $underline{n}$.
Now the expression $G=H(underline{n})$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underline{n}$ - 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(underline{k}).$$ Note that the expression $H(underline{k})$ 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.
$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
add a comment |
$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 "$underline{n}$" 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 $underline{varphi}$ (or $underline{varphi(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(underline{mu(theta)})].$$
Note that we do not require $theta$ to literally be the sentence $varphi(underline{mu(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(underline{mu(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 $underline{n}$.
Now the expression $G=H(underline{n})$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underline{n}$ - 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(underline{k}).$$ Note that the expression $H(underline{k})$ 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.
$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 "$underline{n}$" 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 $underline{varphi}$ (or $underline{varphi(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(underline{mu(theta)})].$$
Note that we do not require $theta$ to literally be the sentence $varphi(underline{mu(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(underline{mu(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 $underline{n}$.
Now the expression $G=H(underline{n})$ - by which I mean the string you get by replacing each "$y$" in $H$ by the string $underline{n}$ - 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(underline{k}).$$ Note that the expression $H(underline{k})$ 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.
edited Apr 7 at 21:58
answered Apr 7 at 19:37
Noah SchweberNoah Schweber
128k10152294
128k10152294
$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
add a comment |
$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
add a comment |
$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 $mathsf{PA}$’.
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...
$endgroup$
add a comment |
$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 $mathsf{PA}$’.
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...
$endgroup$
add a comment |
$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 $mathsf{PA}$’.
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...
$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 $mathsf{PA}$’.
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...
edited 2 days ago
answered Apr 7 at 19:42
Mauro ALLEGRANZAMauro ALLEGRANZA
67.8k449117
67.8k449117
add a comment |
add a comment |
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.
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$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