Mixing
Gödel diagonalization and formulas not holding for themselves
$begingroup$
Is there a formula $varphi (n)$ in one free variable $n$ in ZFC (PA etc.) such that for every formula $psi(n)$ in one variable the equivalence
$$ varphi ( ulcornerpsiurcorner) leftrightarrow neg psi (ulcornerpsiurcorner) $$
is provable? Because this would imply the meta-equivalence
$$vdash varphi (ulcornervarphiurcorner) quad Leftrightarrow quad vdash neg varphi (ulcornervarphiurcorner) $$
so that the consistency of our formal system leads to neither $varphi (ulcornervarphiurcorner)$ nor its negation being provable.
My philosophy is: Formulas like $psi (n)$ represent subsets of the natural numbers and gödelization seems to be an injection from the set of those formulas into $mathbb{N}$. The $varphi$ above corresponds exactly to the subset, that produces the contradiction in the proof of Cantor's theorem.
I once read a prove of the first incompleteness theorem but I remember the Gödel formula to be more complicate. What do you know about the suggested $varphi$?
I also observe the resemblence between Cantor's theorem, the liar paradox, the Russel set and the Grelling–Nelson paradox. These paradoxes always arise if one considers properties of properties. Because a property can be associated to the class of all objects it holds for, the consideration of properties as objects, that can be inserted into properties, creates an injection from the totality of classes into the class of all objects and these injection, by Cantor's theorem, cannot exist. The paradoxes (Does a sentence holding for those sentences not holding for themselves hold for itself?, does a set containing those sets not containing themselves contain itself?, does a word describing those words not describing themselves describe itself?) now simply imitate the proof technique of Cantor's theorem. So I am interested if Cantor's theorem can be used to prove Gödel's inconsistency theorems.
incompleteness paradoxes
asked Jan 12 at 2:17
LucinaLucina
605
$endgroup$
add a comment |
$begingroup$
Is there a formula $varphi (n)$ in one free variable $n$ in ZFC (PA etc.) such that for every formula $psi(n)$ in one variable the equivalence
$$ varphi ( ulcornerpsiurcorner) leftrightarrow neg psi (ulcornerpsiurcorner) $$
is provable? Because this would imply the meta-equivalence
$$vdash varphi (ulcornervarphiurcorner) quad Leftrightarrow quad vdash neg varphi (ulcornervarphiurcorner) $$
so that the consistency of our formal system leads to neither $varphi (ulcornervarphiurcorner)$ nor its negation being provable.
My philosophy is: Formulas like $psi (n)$ represent subsets of the natural numbers and gödelization seems to be an injection from the set of those formulas into $mathbb{N}$. The $varphi$ above corresponds exactly to the subset, that produces the contradiction in the proof of Cantor's theorem.
I once read a prove of the first incompleteness theorem but I remember the Gödel formula to be more complicate. What do you know about the suggested $varphi$?
I also observe the resemblence between Cantor's theorem, the liar paradox, the Russel set and the Grelling–Nelson paradox. These paradoxes always arise if one considers properties of properties. Because a property can be associated to the class of all objects it holds for, the consideration of properties as objects, that can be inserted into properties, creates an injection from the totality of classes into the class of all objects and these injection, by Cantor's theorem, cannot exist. The paradoxes (Does a sentence holding for those sentences not holding for themselves hold for itself?, does a set containing those sets not containing themselves contain itself?, does a word describing those words not describing themselves describe itself?) now simply imitate the proof technique of Cantor's theorem. So I am interested if Cantor's theorem can be used to prove Gödel's inconsistency theorems.
incompleteness paradoxes
asked Jan 12 at 2:17
LucinaLucina
605
$endgroup$
$begingroup$
Another theorem of this type is Tarski's Theorem on the Non-Definability of Truth: There cannot exist a formula $phi$ in one free variable such that $phi (ulcorner psi urcorner) iff psi$ for every sentence $psi$.
$endgroup$
– DanielWainfleet
Jan 12 at 2:44
add a comment |
$begingroup$
Is there a formula $varphi (n)$ in one free variable $n$ in ZFC (PA etc.) such that for every formula $psi(n)$ in one variable the equivalence
$$ varphi ( ulcornerpsiurcorner) leftrightarrow neg psi (ulcornerpsiurcorner) $$
is provable? Because this would imply the meta-equivalence
$$vdash varphi (ulcornervarphiurcorner) quad Leftrightarrow quad vdash neg varphi (ulcornervarphiurcorner) $$
so that the consistency of our formal system leads to neither $varphi (ulcornervarphiurcorner)$ nor its negation being provable.
My philosophy is: Formulas like $psi (n)$ represent subsets of the natural numbers and gödelization seems to be an injection from the set of those formulas into $mathbb{N}$. The $varphi$ above corresponds exactly to the subset, that produces the contradiction in the proof of Cantor's theorem.
I once read a prove of the first incompleteness theorem but I remember the Gödel formula to be more complicate. What do you know about the suggested $varphi$?
I also observe the resemblence between Cantor's theorem, the liar paradox, the Russel set and the Grelling–Nelson paradox. These paradoxes always arise if one considers properties of properties. Because a property can be associated to the class of all objects it holds for, the consideration of properties as objects, that can be inserted into properties, creates an injection from the totality of classes into the class of all objects and these injection, by Cantor's theorem, cannot exist. The paradoxes (Does a sentence holding for those sentences not holding for themselves hold for itself?, does a set containing those sets not containing themselves contain itself?, does a word describing those words not describing themselves describe itself?) now simply imitate the proof technique of Cantor's theorem. So I am interested if Cantor's theorem can be used to prove Gödel's inconsistency theorems.
incompleteness paradoxes
asked Jan 12 at 2:17
LucinaLucina
605
$endgroup$
Is there a formula $varphi (n)$ in one free variable $n$ in ZFC (PA etc.) such that for every formula $psi(n)$ in one variable the equivalence
$$ varphi ( ulcornerpsiurcorner) leftrightarrow neg psi (ulcornerpsiurcorner) $$
is provable? Because this would imply the meta-equivalence
$$vdash varphi (ulcornervarphiurcorner) quad Leftrightarrow quad vdash neg varphi (ulcornervarphiurcorner) $$
so that the consistency of our formal system leads to neither $varphi (ulcornervarphiurcorner)$ nor its negation being provable.
My philosophy is: Formulas like $psi (n)$ represent subsets of the natural numbers and gödelization seems to be an injection from the set of those formulas into $mathbb{N}$. The $varphi$ above corresponds exactly to the subset, that produces the contradiction in the proof of Cantor's theorem.
I once read a prove of the first incompleteness theorem but I remember the Gödel formula to be more complicate. What do you know about the suggested $varphi$?
I also observe the resemblence between Cantor's theorem, the liar paradox, the Russel set and the Grelling–Nelson paradox. These paradoxes always arise if one considers properties of properties. Because a property can be associated to the class of all objects it holds for, the consideration of properties as objects, that can be inserted into properties, creates an injection from the totality of classes into the class of all objects and these injection, by Cantor's theorem, cannot exist. The paradoxes (Does a sentence holding for those sentences not holding for themselves hold for itself?, does a set containing those sets not containing themselves contain itself?, does a word describing those words not describing themselves describe itself?) now simply imitate the proof technique of Cantor's theorem. So I am interested if Cantor's theorem can be used to prove Gödel's inconsistency theorems.
incompleteness paradoxes
incompleteness paradoxes
asked Jan 12 at 2:17
LucinaLucina
605
asked Jan 12 at 2:17
LucinaLucina
605
asked Jan 12 at 2:17
LucinaLucina
605
asked Jan 12 at 2:17
LucinaLucina
605
asked Jan 12 at 2:17
LucinaLucina
605
605
$begingroup$
Another theorem of this type is Tarski's Theorem on the Non-Definability of Truth: There cannot exist a formula $phi$ in one free variable such that $phi (ulcorner psi urcorner) iff psi$ for every sentence $psi$.
$endgroup$
– DanielWainfleet
Jan 12 at 2:44
add a comment |
$begingroup$
Another theorem of this type is Tarski's Theorem on the Non-Definability of Truth: There cannot exist a formula $phi$ in one free variable such that $phi (ulcorner psi urcorner) iff psi$ for every sentence $psi$.
$endgroup$
– DanielWainfleet
Jan 12 at 2:44
$begingroup$
Another theorem of this type is Tarski's Theorem on the Non-Definability of Truth: There cannot exist a formula $phi$ in one free variable such that $phi (ulcorner psi urcorner) iff psi$ for every sentence $psi$.
$endgroup$
– DanielWainfleet
Jan 12 at 2:44
$begingroup$
Another theorem of this type is Tarski's Theorem on the Non-Definability of Truth: There cannot exist a formula $phi$ in one free variable such that $phi (ulcorner psi urcorner) iff psi$ for every sentence $psi$.
$endgroup$
– DanielWainfleet
Jan 12 at 2:44
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Unless I'm missing something, this isn't possible unless the theory in question, which I'll call "$T$," is false: taking $psi=varphi$ we would have $$Tvdash (varphi(ulcornervarphiurcorner)leftrightarrownegvarphi(ulcornervarphiurcorner)).$$
That is, there is a sentence $alpha$ (namely, $alphaequivvarphi(ulcornervarphiurcorner)$) such that $Tvdash (alphaleftrightarrownegalpha)$. This clearly means that $T$ is inconsistent.
In a bit more detail, to make it clear that all rules are being followed, your assumption is that for each $psi$ we have $$Tvdash (varphi(ulcornerpsiurcorner)leftrightarrownegpsi(ulcornerpsiurcorner)).$$ So taking $psi$ to be $varphi$ yields as a specific instance the contradiction-inducing sequent above; there's no need to pass to a "meta-equivalence."
Re: the role of diagonalization as a general framework for such arguments, see e.g. A universal approach to self-referential paradoxes, incompleteness and fixed points. My brief spiel on the matter would be that Lawvere's fixed point theorem has many such results as instances, but in no way "trivializes" them - you still need to set up the category in question and check its relevant properties. But there is definitely something real there.
answered Jan 12 at 4:57
Noah SchweberNoah Schweber
124k10150287
$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
});
}
});
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%2f3070532%2fg%25c3%25b6del-diagonalization-and-formulas-not-holding-for-themselves%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Unless I'm missing something, this isn't possible unless the theory in question, which I'll call "$T$," is false: taking $psi=varphi$ we would have $$Tvdash (varphi(ulcornervarphiurcorner)leftrightarrownegvarphi(ulcornervarphiurcorner)).$$
That is, there is a sentence $alpha$ (namely, $alphaequivvarphi(ulcornervarphiurcorner)$) such that $Tvdash (alphaleftrightarrownegalpha)$. This clearly means that $T$ is inconsistent.
In a bit more detail, to make it clear that all rules are being followed, your assumption is that for each $psi$ we have $$Tvdash (varphi(ulcornerpsiurcorner)leftrightarrownegpsi(ulcornerpsiurcorner)).$$ So taking $psi$ to be $varphi$ yields as a specific instance the contradiction-inducing sequent above; there's no need to pass to a "meta-equivalence."
Re: the role of diagonalization as a general framework for such arguments, see e.g. A universal approach to self-referential paradoxes, incompleteness and fixed points. My brief spiel on the matter would be that Lawvere's fixed point theorem has many such results as instances, but in no way "trivializes" them - you still need to set up the category in question and check its relevant properties. But there is definitely something real there.
answered Jan 12 at 4:57
Noah SchweberNoah Schweber
124k10150287
$endgroup$
add a comment |
$begingroup$
Unless I'm missing something, this isn't possible unless the theory in question, which I'll call "$T$," is false: taking $psi=varphi$ we would have $$Tvdash (varphi(ulcornervarphiurcorner)leftrightarrownegvarphi(ulcornervarphiurcorner)).$$
That is, there is a sentence $alpha$ (namely, $alphaequivvarphi(ulcornervarphiurcorner)$) such that $Tvdash (alphaleftrightarrownegalpha)$. This clearly means that $T$ is inconsistent.
In a bit more detail, to make it clear that all rules are being followed, your assumption is that for each $psi$ we have $$Tvdash (varphi(ulcornerpsiurcorner)leftrightarrownegpsi(ulcornerpsiurcorner)).$$ So taking $psi$ to be $varphi$ yields as a specific instance the contradiction-inducing sequent above; there's no need to pass to a "meta-equivalence."
Re: the role of diagonalization as a general framework for such arguments, see e.g. A universal approach to self-referential paradoxes, incompleteness and fixed points. My brief spiel on the matter would be that Lawvere's fixed point theorem has many such results as instances, but in no way "trivializes" them - you still need to set up the category in question and check its relevant properties. But there is definitely something real there.
answered Jan 12 at 4:57
Noah SchweberNoah Schweber
124k10150287
$endgroup$
add a comment |
$begingroup$
Unless I'm missing something, this isn't possible unless the theory in question, which I'll call "$T$," is false: taking $psi=varphi$ we would have $$Tvdash (varphi(ulcornervarphiurcorner)leftrightarrownegvarphi(ulcornervarphiurcorner)).$$
That is, there is a sentence $alpha$ (namely, $alphaequivvarphi(ulcornervarphiurcorner)$) such that $Tvdash (alphaleftrightarrownegalpha)$. This clearly means that $T$ is inconsistent.
In a bit more detail, to make it clear that all rules are being followed, your assumption is that for each $psi$ we have $$Tvdash (varphi(ulcornerpsiurcorner)leftrightarrownegpsi(ulcornerpsiurcorner)).$$ So taking $psi$ to be $varphi$ yields as a specific instance the contradiction-inducing sequent above; there's no need to pass to a "meta-equivalence."
Re: the role of diagonalization as a general framework for such arguments, see e.g. A universal approach to self-referential paradoxes, incompleteness and fixed points. My brief spiel on the matter would be that Lawvere's fixed point theorem has many such results as instances, but in no way "trivializes" them - you still need to set up the category in question and check its relevant properties. But there is definitely something real there.
answered Jan 12 at 4:57
Noah SchweberNoah Schweber
124k10150287
$endgroup$
Unless I'm missing something, this isn't possible unless the theory in question, which I'll call "$T$," is false: taking $psi=varphi$ we would have $$Tvdash (varphi(ulcornervarphiurcorner)leftrightarrownegvarphi(ulcornervarphiurcorner)).$$
That is, there is a sentence $alpha$ (namely, $alphaequivvarphi(ulcornervarphiurcorner)$) such that $Tvdash (alphaleftrightarrownegalpha)$. This clearly means that $T$ is inconsistent.
In a bit more detail, to make it clear that all rules are being followed, your assumption is that for each $psi$ we have $$Tvdash (varphi(ulcornerpsiurcorner)leftrightarrownegpsi(ulcornerpsiurcorner)).$$ So taking $psi$ to be $varphi$ yields as a specific instance the contradiction-inducing sequent above; there's no need to pass to a "meta-equivalence."
Re: the role of diagonalization as a general framework for such arguments, see e.g. A universal approach to self-referential paradoxes, incompleteness and fixed points. My brief spiel on the matter would be that Lawvere's fixed point theorem has many such results as instances, but in no way "trivializes" them - you still need to set up the category in question and check its relevant properties. But there is definitely something real there.
answered Jan 12 at 4:57
Noah SchweberNoah Schweber
124k10150287
edited Jan 12 at 5:26
answered Jan 12 at 4:57
Noah SchweberNoah Schweber
124k10150287
answered Jan 12 at 4:57
Noah SchweberNoah Schweber
124k10150287
answered Jan 12 at 4:57
Noah SchweberNoah Schweber
124k10150287
124k10150287
add a comment |
add a comment |
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%2f3070532%2fg%25c3%25b6del-diagonalization-and-formulas-not-holding-for-themselves%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$
Another theorem of this type is Tarski's Theorem on the Non-Definability of Truth: There cannot exist a formula $phi$ in one free variable such that $phi (ulcorner psi urcorner) iff psi$ for every sentence $psi$.
$endgroup$
– DanielWainfleet
Jan 12 at 2:44