Intuition behind Unprovable Truths: Godel
$begingroup$
Godel's Incompleteness Theorem says there are statements in an axiomatic system which are TRUE but UNPROVABLE. I have read other answers here, but none of them captures the essence of such statements. So, my question is
- What is the nature of such True statements which cannot be proved syntactically? What do they talk about? What are the requirements for a truth to be proved syntactically?
- If there are truths that cannot be proved by manipulation of symbols, does this mean that manipulation rules/symbols are not capable enough to express some Truths?
logic intuition first-order-logic
$endgroup$
|
show 3 more comments
$begingroup$
Godel's Incompleteness Theorem says there are statements in an axiomatic system which are TRUE but UNPROVABLE. I have read other answers here, but none of them captures the essence of such statements. So, my question is
- What is the nature of such True statements which cannot be proved syntactically? What do they talk about? What are the requirements for a truth to be proved syntactically?
- If there are truths that cannot be proved by manipulation of symbols, does this mean that manipulation rules/symbols are not capable enough to express some Truths?
logic intuition first-order-logic
$endgroup$
3
$begingroup$
I think you're hoping we can dumb down a technical result with misleading analogies that make you feel like you understand when you don't. I'd prefer to recommend you learn about $omega$-inconsistency.
$endgroup$
– J.G.
Dec 10 '18 at 6:18
1
$begingroup$
See Gödel, Escher, Bach: an Eternal Golden Braid for at least some intuition.
$endgroup$
– Shaun
Dec 10 '18 at 6:20
$begingroup$
You can start from an exposition of Gödel's Incompleteness Theorems.
$endgroup$
– Mauro ALLEGRANZA
Dec 10 '18 at 8:15
$begingroup$
Thinking to Godel's incompleteness theorems as corollaries of the halting problem helped me a lot.
$endgroup$
– reuns
Dec 10 '18 at 8:20
$begingroup$
True where? In arithmetic we have a canonical and natural model, so "true" implicitly mean "true in the standard model". But truth is always relative to a structure. And what does it even mean "truth that cannot be captured by syntax"? Truth is relative to an interpretation of a language. What does it mean for a true statement if you cannot write it in the relevant language?
$endgroup$
– Asaf Karagila♦
Dec 10 '18 at 8:23
|
show 3 more comments
$begingroup$
Godel's Incompleteness Theorem says there are statements in an axiomatic system which are TRUE but UNPROVABLE. I have read other answers here, but none of them captures the essence of such statements. So, my question is
- What is the nature of such True statements which cannot be proved syntactically? What do they talk about? What are the requirements for a truth to be proved syntactically?
- If there are truths that cannot be proved by manipulation of symbols, does this mean that manipulation rules/symbols are not capable enough to express some Truths?
logic intuition first-order-logic
$endgroup$
Godel's Incompleteness Theorem says there are statements in an axiomatic system which are TRUE but UNPROVABLE. I have read other answers here, but none of them captures the essence of such statements. So, my question is
- What is the nature of such True statements which cannot be proved syntactically? What do they talk about? What are the requirements for a truth to be proved syntactically?
- If there are truths that cannot be proved by manipulation of symbols, does this mean that manipulation rules/symbols are not capable enough to express some Truths?
logic intuition first-order-logic
logic intuition first-order-logic
edited Dec 10 '18 at 8:54
Ajax
asked Dec 10 '18 at 6:06
AjaxAjax
986
986
3
$begingroup$
I think you're hoping we can dumb down a technical result with misleading analogies that make you feel like you understand when you don't. I'd prefer to recommend you learn about $omega$-inconsistency.
$endgroup$
– J.G.
Dec 10 '18 at 6:18
1
$begingroup$
See Gödel, Escher, Bach: an Eternal Golden Braid for at least some intuition.
$endgroup$
– Shaun
Dec 10 '18 at 6:20
$begingroup$
You can start from an exposition of Gödel's Incompleteness Theorems.
$endgroup$
– Mauro ALLEGRANZA
Dec 10 '18 at 8:15
$begingroup$
Thinking to Godel's incompleteness theorems as corollaries of the halting problem helped me a lot.
$endgroup$
– reuns
Dec 10 '18 at 8:20
$begingroup$
True where? In arithmetic we have a canonical and natural model, so "true" implicitly mean "true in the standard model". But truth is always relative to a structure. And what does it even mean "truth that cannot be captured by syntax"? Truth is relative to an interpretation of a language. What does it mean for a true statement if you cannot write it in the relevant language?
$endgroup$
– Asaf Karagila♦
Dec 10 '18 at 8:23
|
show 3 more comments
3
$begingroup$
I think you're hoping we can dumb down a technical result with misleading analogies that make you feel like you understand when you don't. I'd prefer to recommend you learn about $omega$-inconsistency.
$endgroup$
– J.G.
Dec 10 '18 at 6:18
1
$begingroup$
See Gödel, Escher, Bach: an Eternal Golden Braid for at least some intuition.
$endgroup$
– Shaun
Dec 10 '18 at 6:20
$begingroup$
You can start from an exposition of Gödel's Incompleteness Theorems.
$endgroup$
– Mauro ALLEGRANZA
Dec 10 '18 at 8:15
$begingroup$
Thinking to Godel's incompleteness theorems as corollaries of the halting problem helped me a lot.
$endgroup$
– reuns
Dec 10 '18 at 8:20
$begingroup$
True where? In arithmetic we have a canonical and natural model, so "true" implicitly mean "true in the standard model". But truth is always relative to a structure. And what does it even mean "truth that cannot be captured by syntax"? Truth is relative to an interpretation of a language. What does it mean for a true statement if you cannot write it in the relevant language?
$endgroup$
– Asaf Karagila♦
Dec 10 '18 at 8:23
3
3
$begingroup$
I think you're hoping we can dumb down a technical result with misleading analogies that make you feel like you understand when you don't. I'd prefer to recommend you learn about $omega$-inconsistency.
$endgroup$
– J.G.
Dec 10 '18 at 6:18
$begingroup$
I think you're hoping we can dumb down a technical result with misleading analogies that make you feel like you understand when you don't. I'd prefer to recommend you learn about $omega$-inconsistency.
$endgroup$
– J.G.
Dec 10 '18 at 6:18
1
1
$begingroup$
See Gödel, Escher, Bach: an Eternal Golden Braid for at least some intuition.
$endgroup$
– Shaun
Dec 10 '18 at 6:20
$begingroup$
See Gödel, Escher, Bach: an Eternal Golden Braid for at least some intuition.
$endgroup$
– Shaun
Dec 10 '18 at 6:20
$begingroup$
You can start from an exposition of Gödel's Incompleteness Theorems.
$endgroup$
– Mauro ALLEGRANZA
Dec 10 '18 at 8:15
$begingroup$
You can start from an exposition of Gödel's Incompleteness Theorems.
$endgroup$
– Mauro ALLEGRANZA
Dec 10 '18 at 8:15
$begingroup$
Thinking to Godel's incompleteness theorems as corollaries of the halting problem helped me a lot.
$endgroup$
– reuns
Dec 10 '18 at 8:20
$begingroup$
Thinking to Godel's incompleteness theorems as corollaries of the halting problem helped me a lot.
$endgroup$
– reuns
Dec 10 '18 at 8:20
$begingroup$
True where? In arithmetic we have a canonical and natural model, so "true" implicitly mean "true in the standard model". But truth is always relative to a structure. And what does it even mean "truth that cannot be captured by syntax"? Truth is relative to an interpretation of a language. What does it mean for a true statement if you cannot write it in the relevant language?
$endgroup$
– Asaf Karagila♦
Dec 10 '18 at 8:23
$begingroup$
True where? In arithmetic we have a canonical and natural model, so "true" implicitly mean "true in the standard model". But truth is always relative to a structure. And what does it even mean "truth that cannot be captured by syntax"? Truth is relative to an interpretation of a language. What does it mean for a true statement if you cannot write it in the relevant language?
$endgroup$
– Asaf Karagila♦
Dec 10 '18 at 8:23
|
show 3 more comments
1 Answer
1
active
oldest
votes
$begingroup$
I'll try to provide an explanation that doesn't need such proof technicalities as arithmoquines. It'll still probably require some readers to learn a little bit of theory, but I hope it'll be accessible.
Peano arithmetic is an axiomatisation of the arithmetic of non-negative integers. It is a first-order theory, i.e. the only types of object we can talk about are non-negative integers. For instance, $forall n (phi(n))$ means all non-negative integers have the property $phi$, which can be written with a formula such as $n=n$, but can't be an object in its own right in this formalism. Such a $phi$ is called a unary predicate, unary meaning it takes one argument. For each individual unary predicate $phi$ we can write down, Peano arithmetic includes the following as an axiom:
$$phi(0)landforall n (phi(n)tophi(Sn))toforall n(phi(n))$$(where $Sn$ means $n+1$). This is called induction. Note that because we can't put a "for all $phi$" wrapper around the above statement in a first-order theory, we have to install induction with an infinite collection of axioms called an axiom schema, not a single axiom.
How many such axioms are there? You might think there's one for every set of non-negative integers. Just as a set with $12$ elements has $2^{12}$ subsets (because each individual element either does or doesn't make the cut), there are $2^{aleph_0}$ sets of non-negative integers, where $aleph_0$ (pronounced aleph null) is the name of how many non-negative integers there are. But you'd be wrong. Each unary predicate is a formula of finite length, and there are only finitely many symbols in the language, and it can be shown we can only write down $aleph_0$ formulae that way. (Even if you had $aleph_0$ symbols, this conclusion would remain true.) And because every set has more subsets than elements (a result called Cantor's theorem), Peano arithmetic doesn't guarantee induction for every set you might think it would.
Meanwhile, second-order approaches to arithmetic can talk about two kinds of object, the non-negative integers and predicates on them. This allows a for-all-$phi$ wrapper on the induction described above, so one axiom covers all $2^{aleph_0}$ scenarios.
Given axioms, a model of them is a hypothetical scenario in which they're all valid (that's not the rigorous definition, but it'll do here). In accord with intuition, all models of second-order arithmetic have the same properties (we say they're isomorphic), so there's "only one" such arithmetic. But given any set $S$ of non-negative integers for which no $phi$ you can write down satisfies $forall n (phi(n)leftrightarrow nin S)$ (where $forall$ quantifies over non-negative integers), in at least one model of Peano arithmetic induction doesn't work on $S$. Why? Because a model exists iff a contradiction can't be derived, and of course Peano arithmetic doesn't assume enough to prove induction works on $S$. This is why there are statements that are "true" in second-order arithmetic but not provable in Peano arithmetic. Note in particular that Peano arithmetic's models aren't in general isomorphic, because they include but aren't limited to second-order arithmetic's unique-up-to-isomorphism model.
Most interestingly of all, this limitation even includes some statements Peano arithmetic can write down. Why? Well, at this point a simple explanation can only go so far. A theory's non-isomorphic models can still be elementarily equivalent, meaning that the language of the theory is inadequate to express the differences between them, i.e. each statement in that language is true in either all or none of the models.That's actually what happens in a weaker version of arithmetic called Presburger arithmetic (which is therefore incomplete), but it doesn't happen to Peano arithmetic (which therefore isn't). Both theories aren't the whole second-order story, but Peano arithmetic's greater ability to discuss multiplication is what makes it incomplete. Why does that make all the difference? Because a theorem says so, I guess.
In any first-order theory that models Peano arithmetic, such as set theories, the same predicate-counting logic reaches much the same conclusion. In fact, Peano arithmetic has an induction-lacking fragment called Robinson arithmetic that has the same problem. When an incomplete theory can't be made complete by adding axioms to it, because its language is too expressive for such an extension's models to end up all elementarily equivalent, we say it's essentially undecidable, and that is true of both Robinson and Peano.
$endgroup$
$begingroup$
Both Peano and Presberger arithmetic have many non-isomorphic models. As does the complete first order theory of $mathbb N$ in the language with addition and multiplication. It's not about isomorphism, it's about elementary equivalence (i.e. satisfying the same first order sentences). All models of Presberger arithmetic satisfy the exact same sentences in the first order language with addition (even though they aren't necessarily isomorphic), whereas Peano arithmetic has models that differ on some first order sentences in the language with addition and multiplication.
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:01
$begingroup$
More to the point: "If Peano arithmetic were complete, then all its models would be isomorphic" is false. (Well, I suppose actually it's true, since PA is not complete... but the general statement complete -> categorical is false and Presberger arithmetic is a counterexample.)
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:05
$begingroup$
@spaceisdarkgreen Thank you very much for both of your comments. They helped me work out how to provide an accessible explanation of what's really going on (more so, at least, than I thought I'd be able to; I knew about elementary equivalence, but I was still trying to work out how to explain it clearly). I've made some edits.
$endgroup$
– J.G.
Dec 14 '18 at 8:08
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%2f3033524%2fintuition-behind-unprovable-truths-godel%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$
I'll try to provide an explanation that doesn't need such proof technicalities as arithmoquines. It'll still probably require some readers to learn a little bit of theory, but I hope it'll be accessible.
Peano arithmetic is an axiomatisation of the arithmetic of non-negative integers. It is a first-order theory, i.e. the only types of object we can talk about are non-negative integers. For instance, $forall n (phi(n))$ means all non-negative integers have the property $phi$, which can be written with a formula such as $n=n$, but can't be an object in its own right in this formalism. Such a $phi$ is called a unary predicate, unary meaning it takes one argument. For each individual unary predicate $phi$ we can write down, Peano arithmetic includes the following as an axiom:
$$phi(0)landforall n (phi(n)tophi(Sn))toforall n(phi(n))$$(where $Sn$ means $n+1$). This is called induction. Note that because we can't put a "for all $phi$" wrapper around the above statement in a first-order theory, we have to install induction with an infinite collection of axioms called an axiom schema, not a single axiom.
How many such axioms are there? You might think there's one for every set of non-negative integers. Just as a set with $12$ elements has $2^{12}$ subsets (because each individual element either does or doesn't make the cut), there are $2^{aleph_0}$ sets of non-negative integers, where $aleph_0$ (pronounced aleph null) is the name of how many non-negative integers there are. But you'd be wrong. Each unary predicate is a formula of finite length, and there are only finitely many symbols in the language, and it can be shown we can only write down $aleph_0$ formulae that way. (Even if you had $aleph_0$ symbols, this conclusion would remain true.) And because every set has more subsets than elements (a result called Cantor's theorem), Peano arithmetic doesn't guarantee induction for every set you might think it would.
Meanwhile, second-order approaches to arithmetic can talk about two kinds of object, the non-negative integers and predicates on them. This allows a for-all-$phi$ wrapper on the induction described above, so one axiom covers all $2^{aleph_0}$ scenarios.
Given axioms, a model of them is a hypothetical scenario in which they're all valid (that's not the rigorous definition, but it'll do here). In accord with intuition, all models of second-order arithmetic have the same properties (we say they're isomorphic), so there's "only one" such arithmetic. But given any set $S$ of non-negative integers for which no $phi$ you can write down satisfies $forall n (phi(n)leftrightarrow nin S)$ (where $forall$ quantifies over non-negative integers), in at least one model of Peano arithmetic induction doesn't work on $S$. Why? Because a model exists iff a contradiction can't be derived, and of course Peano arithmetic doesn't assume enough to prove induction works on $S$. This is why there are statements that are "true" in second-order arithmetic but not provable in Peano arithmetic. Note in particular that Peano arithmetic's models aren't in general isomorphic, because they include but aren't limited to second-order arithmetic's unique-up-to-isomorphism model.
Most interestingly of all, this limitation even includes some statements Peano arithmetic can write down. Why? Well, at this point a simple explanation can only go so far. A theory's non-isomorphic models can still be elementarily equivalent, meaning that the language of the theory is inadequate to express the differences between them, i.e. each statement in that language is true in either all or none of the models.That's actually what happens in a weaker version of arithmetic called Presburger arithmetic (which is therefore incomplete), but it doesn't happen to Peano arithmetic (which therefore isn't). Both theories aren't the whole second-order story, but Peano arithmetic's greater ability to discuss multiplication is what makes it incomplete. Why does that make all the difference? Because a theorem says so, I guess.
In any first-order theory that models Peano arithmetic, such as set theories, the same predicate-counting logic reaches much the same conclusion. In fact, Peano arithmetic has an induction-lacking fragment called Robinson arithmetic that has the same problem. When an incomplete theory can't be made complete by adding axioms to it, because its language is too expressive for such an extension's models to end up all elementarily equivalent, we say it's essentially undecidable, and that is true of both Robinson and Peano.
$endgroup$
$begingroup$
Both Peano and Presberger arithmetic have many non-isomorphic models. As does the complete first order theory of $mathbb N$ in the language with addition and multiplication. It's not about isomorphism, it's about elementary equivalence (i.e. satisfying the same first order sentences). All models of Presberger arithmetic satisfy the exact same sentences in the first order language with addition (even though they aren't necessarily isomorphic), whereas Peano arithmetic has models that differ on some first order sentences in the language with addition and multiplication.
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:01
$begingroup$
More to the point: "If Peano arithmetic were complete, then all its models would be isomorphic" is false. (Well, I suppose actually it's true, since PA is not complete... but the general statement complete -> categorical is false and Presberger arithmetic is a counterexample.)
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:05
$begingroup$
@spaceisdarkgreen Thank you very much for both of your comments. They helped me work out how to provide an accessible explanation of what's really going on (more so, at least, than I thought I'd be able to; I knew about elementary equivalence, but I was still trying to work out how to explain it clearly). I've made some edits.
$endgroup$
– J.G.
Dec 14 '18 at 8:08
add a comment |
$begingroup$
I'll try to provide an explanation that doesn't need such proof technicalities as arithmoquines. It'll still probably require some readers to learn a little bit of theory, but I hope it'll be accessible.
Peano arithmetic is an axiomatisation of the arithmetic of non-negative integers. It is a first-order theory, i.e. the only types of object we can talk about are non-negative integers. For instance, $forall n (phi(n))$ means all non-negative integers have the property $phi$, which can be written with a formula such as $n=n$, but can't be an object in its own right in this formalism. Such a $phi$ is called a unary predicate, unary meaning it takes one argument. For each individual unary predicate $phi$ we can write down, Peano arithmetic includes the following as an axiom:
$$phi(0)landforall n (phi(n)tophi(Sn))toforall n(phi(n))$$(where $Sn$ means $n+1$). This is called induction. Note that because we can't put a "for all $phi$" wrapper around the above statement in a first-order theory, we have to install induction with an infinite collection of axioms called an axiom schema, not a single axiom.
How many such axioms are there? You might think there's one for every set of non-negative integers. Just as a set with $12$ elements has $2^{12}$ subsets (because each individual element either does or doesn't make the cut), there are $2^{aleph_0}$ sets of non-negative integers, where $aleph_0$ (pronounced aleph null) is the name of how many non-negative integers there are. But you'd be wrong. Each unary predicate is a formula of finite length, and there are only finitely many symbols in the language, and it can be shown we can only write down $aleph_0$ formulae that way. (Even if you had $aleph_0$ symbols, this conclusion would remain true.) And because every set has more subsets than elements (a result called Cantor's theorem), Peano arithmetic doesn't guarantee induction for every set you might think it would.
Meanwhile, second-order approaches to arithmetic can talk about two kinds of object, the non-negative integers and predicates on them. This allows a for-all-$phi$ wrapper on the induction described above, so one axiom covers all $2^{aleph_0}$ scenarios.
Given axioms, a model of them is a hypothetical scenario in which they're all valid (that's not the rigorous definition, but it'll do here). In accord with intuition, all models of second-order arithmetic have the same properties (we say they're isomorphic), so there's "only one" such arithmetic. But given any set $S$ of non-negative integers for which no $phi$ you can write down satisfies $forall n (phi(n)leftrightarrow nin S)$ (where $forall$ quantifies over non-negative integers), in at least one model of Peano arithmetic induction doesn't work on $S$. Why? Because a model exists iff a contradiction can't be derived, and of course Peano arithmetic doesn't assume enough to prove induction works on $S$. This is why there are statements that are "true" in second-order arithmetic but not provable in Peano arithmetic. Note in particular that Peano arithmetic's models aren't in general isomorphic, because they include but aren't limited to second-order arithmetic's unique-up-to-isomorphism model.
Most interestingly of all, this limitation even includes some statements Peano arithmetic can write down. Why? Well, at this point a simple explanation can only go so far. A theory's non-isomorphic models can still be elementarily equivalent, meaning that the language of the theory is inadequate to express the differences between them, i.e. each statement in that language is true in either all or none of the models.That's actually what happens in a weaker version of arithmetic called Presburger arithmetic (which is therefore incomplete), but it doesn't happen to Peano arithmetic (which therefore isn't). Both theories aren't the whole second-order story, but Peano arithmetic's greater ability to discuss multiplication is what makes it incomplete. Why does that make all the difference? Because a theorem says so, I guess.
In any first-order theory that models Peano arithmetic, such as set theories, the same predicate-counting logic reaches much the same conclusion. In fact, Peano arithmetic has an induction-lacking fragment called Robinson arithmetic that has the same problem. When an incomplete theory can't be made complete by adding axioms to it, because its language is too expressive for such an extension's models to end up all elementarily equivalent, we say it's essentially undecidable, and that is true of both Robinson and Peano.
$endgroup$
$begingroup$
Both Peano and Presberger arithmetic have many non-isomorphic models. As does the complete first order theory of $mathbb N$ in the language with addition and multiplication. It's not about isomorphism, it's about elementary equivalence (i.e. satisfying the same first order sentences). All models of Presberger arithmetic satisfy the exact same sentences in the first order language with addition (even though they aren't necessarily isomorphic), whereas Peano arithmetic has models that differ on some first order sentences in the language with addition and multiplication.
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:01
$begingroup$
More to the point: "If Peano arithmetic were complete, then all its models would be isomorphic" is false. (Well, I suppose actually it's true, since PA is not complete... but the general statement complete -> categorical is false and Presberger arithmetic is a counterexample.)
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:05
$begingroup$
@spaceisdarkgreen Thank you very much for both of your comments. They helped me work out how to provide an accessible explanation of what's really going on (more so, at least, than I thought I'd be able to; I knew about elementary equivalence, but I was still trying to work out how to explain it clearly). I've made some edits.
$endgroup$
– J.G.
Dec 14 '18 at 8:08
add a comment |
$begingroup$
I'll try to provide an explanation that doesn't need such proof technicalities as arithmoquines. It'll still probably require some readers to learn a little bit of theory, but I hope it'll be accessible.
Peano arithmetic is an axiomatisation of the arithmetic of non-negative integers. It is a first-order theory, i.e. the only types of object we can talk about are non-negative integers. For instance, $forall n (phi(n))$ means all non-negative integers have the property $phi$, which can be written with a formula such as $n=n$, but can't be an object in its own right in this formalism. Such a $phi$ is called a unary predicate, unary meaning it takes one argument. For each individual unary predicate $phi$ we can write down, Peano arithmetic includes the following as an axiom:
$$phi(0)landforall n (phi(n)tophi(Sn))toforall n(phi(n))$$(where $Sn$ means $n+1$). This is called induction. Note that because we can't put a "for all $phi$" wrapper around the above statement in a first-order theory, we have to install induction with an infinite collection of axioms called an axiom schema, not a single axiom.
How many such axioms are there? You might think there's one for every set of non-negative integers. Just as a set with $12$ elements has $2^{12}$ subsets (because each individual element either does or doesn't make the cut), there are $2^{aleph_0}$ sets of non-negative integers, where $aleph_0$ (pronounced aleph null) is the name of how many non-negative integers there are. But you'd be wrong. Each unary predicate is a formula of finite length, and there are only finitely many symbols in the language, and it can be shown we can only write down $aleph_0$ formulae that way. (Even if you had $aleph_0$ symbols, this conclusion would remain true.) And because every set has more subsets than elements (a result called Cantor's theorem), Peano arithmetic doesn't guarantee induction for every set you might think it would.
Meanwhile, second-order approaches to arithmetic can talk about two kinds of object, the non-negative integers and predicates on them. This allows a for-all-$phi$ wrapper on the induction described above, so one axiom covers all $2^{aleph_0}$ scenarios.
Given axioms, a model of them is a hypothetical scenario in which they're all valid (that's not the rigorous definition, but it'll do here). In accord with intuition, all models of second-order arithmetic have the same properties (we say they're isomorphic), so there's "only one" such arithmetic. But given any set $S$ of non-negative integers for which no $phi$ you can write down satisfies $forall n (phi(n)leftrightarrow nin S)$ (where $forall$ quantifies over non-negative integers), in at least one model of Peano arithmetic induction doesn't work on $S$. Why? Because a model exists iff a contradiction can't be derived, and of course Peano arithmetic doesn't assume enough to prove induction works on $S$. This is why there are statements that are "true" in second-order arithmetic but not provable in Peano arithmetic. Note in particular that Peano arithmetic's models aren't in general isomorphic, because they include but aren't limited to second-order arithmetic's unique-up-to-isomorphism model.
Most interestingly of all, this limitation even includes some statements Peano arithmetic can write down. Why? Well, at this point a simple explanation can only go so far. A theory's non-isomorphic models can still be elementarily equivalent, meaning that the language of the theory is inadequate to express the differences between them, i.e. each statement in that language is true in either all or none of the models.That's actually what happens in a weaker version of arithmetic called Presburger arithmetic (which is therefore incomplete), but it doesn't happen to Peano arithmetic (which therefore isn't). Both theories aren't the whole second-order story, but Peano arithmetic's greater ability to discuss multiplication is what makes it incomplete. Why does that make all the difference? Because a theorem says so, I guess.
In any first-order theory that models Peano arithmetic, such as set theories, the same predicate-counting logic reaches much the same conclusion. In fact, Peano arithmetic has an induction-lacking fragment called Robinson arithmetic that has the same problem. When an incomplete theory can't be made complete by adding axioms to it, because its language is too expressive for such an extension's models to end up all elementarily equivalent, we say it's essentially undecidable, and that is true of both Robinson and Peano.
$endgroup$
I'll try to provide an explanation that doesn't need such proof technicalities as arithmoquines. It'll still probably require some readers to learn a little bit of theory, but I hope it'll be accessible.
Peano arithmetic is an axiomatisation of the arithmetic of non-negative integers. It is a first-order theory, i.e. the only types of object we can talk about are non-negative integers. For instance, $forall n (phi(n))$ means all non-negative integers have the property $phi$, which can be written with a formula such as $n=n$, but can't be an object in its own right in this formalism. Such a $phi$ is called a unary predicate, unary meaning it takes one argument. For each individual unary predicate $phi$ we can write down, Peano arithmetic includes the following as an axiom:
$$phi(0)landforall n (phi(n)tophi(Sn))toforall n(phi(n))$$(where $Sn$ means $n+1$). This is called induction. Note that because we can't put a "for all $phi$" wrapper around the above statement in a first-order theory, we have to install induction with an infinite collection of axioms called an axiom schema, not a single axiom.
How many such axioms are there? You might think there's one for every set of non-negative integers. Just as a set with $12$ elements has $2^{12}$ subsets (because each individual element either does or doesn't make the cut), there are $2^{aleph_0}$ sets of non-negative integers, where $aleph_0$ (pronounced aleph null) is the name of how many non-negative integers there are. But you'd be wrong. Each unary predicate is a formula of finite length, and there are only finitely many symbols in the language, and it can be shown we can only write down $aleph_0$ formulae that way. (Even if you had $aleph_0$ symbols, this conclusion would remain true.) And because every set has more subsets than elements (a result called Cantor's theorem), Peano arithmetic doesn't guarantee induction for every set you might think it would.
Meanwhile, second-order approaches to arithmetic can talk about two kinds of object, the non-negative integers and predicates on them. This allows a for-all-$phi$ wrapper on the induction described above, so one axiom covers all $2^{aleph_0}$ scenarios.
Given axioms, a model of them is a hypothetical scenario in which they're all valid (that's not the rigorous definition, but it'll do here). In accord with intuition, all models of second-order arithmetic have the same properties (we say they're isomorphic), so there's "only one" such arithmetic. But given any set $S$ of non-negative integers for which no $phi$ you can write down satisfies $forall n (phi(n)leftrightarrow nin S)$ (where $forall$ quantifies over non-negative integers), in at least one model of Peano arithmetic induction doesn't work on $S$. Why? Because a model exists iff a contradiction can't be derived, and of course Peano arithmetic doesn't assume enough to prove induction works on $S$. This is why there are statements that are "true" in second-order arithmetic but not provable in Peano arithmetic. Note in particular that Peano arithmetic's models aren't in general isomorphic, because they include but aren't limited to second-order arithmetic's unique-up-to-isomorphism model.
Most interestingly of all, this limitation even includes some statements Peano arithmetic can write down. Why? Well, at this point a simple explanation can only go so far. A theory's non-isomorphic models can still be elementarily equivalent, meaning that the language of the theory is inadequate to express the differences between them, i.e. each statement in that language is true in either all or none of the models.That's actually what happens in a weaker version of arithmetic called Presburger arithmetic (which is therefore incomplete), but it doesn't happen to Peano arithmetic (which therefore isn't). Both theories aren't the whole second-order story, but Peano arithmetic's greater ability to discuss multiplication is what makes it incomplete. Why does that make all the difference? Because a theorem says so, I guess.
In any first-order theory that models Peano arithmetic, such as set theories, the same predicate-counting logic reaches much the same conclusion. In fact, Peano arithmetic has an induction-lacking fragment called Robinson arithmetic that has the same problem. When an incomplete theory can't be made complete by adding axioms to it, because its language is too expressive for such an extension's models to end up all elementarily equivalent, we say it's essentially undecidable, and that is true of both Robinson and Peano.
edited Dec 14 '18 at 8:07
answered Dec 10 '18 at 10:06
J.G.J.G.
27.2k22843
27.2k22843
$begingroup$
Both Peano and Presberger arithmetic have many non-isomorphic models. As does the complete first order theory of $mathbb N$ in the language with addition and multiplication. It's not about isomorphism, it's about elementary equivalence (i.e. satisfying the same first order sentences). All models of Presberger arithmetic satisfy the exact same sentences in the first order language with addition (even though they aren't necessarily isomorphic), whereas Peano arithmetic has models that differ on some first order sentences in the language with addition and multiplication.
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:01
$begingroup$
More to the point: "If Peano arithmetic were complete, then all its models would be isomorphic" is false. (Well, I suppose actually it's true, since PA is not complete... but the general statement complete -> categorical is false and Presberger arithmetic is a counterexample.)
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:05
$begingroup$
@spaceisdarkgreen Thank you very much for both of your comments. They helped me work out how to provide an accessible explanation of what's really going on (more so, at least, than I thought I'd be able to; I knew about elementary equivalence, but I was still trying to work out how to explain it clearly). I've made some edits.
$endgroup$
– J.G.
Dec 14 '18 at 8:08
add a comment |
$begingroup$
Both Peano and Presberger arithmetic have many non-isomorphic models. As does the complete first order theory of $mathbb N$ in the language with addition and multiplication. It's not about isomorphism, it's about elementary equivalence (i.e. satisfying the same first order sentences). All models of Presberger arithmetic satisfy the exact same sentences in the first order language with addition (even though they aren't necessarily isomorphic), whereas Peano arithmetic has models that differ on some first order sentences in the language with addition and multiplication.
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:01
$begingroup$
More to the point: "If Peano arithmetic were complete, then all its models would be isomorphic" is false. (Well, I suppose actually it's true, since PA is not complete... but the general statement complete -> categorical is false and Presberger arithmetic is a counterexample.)
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:05
$begingroup$
@spaceisdarkgreen Thank you very much for both of your comments. They helped me work out how to provide an accessible explanation of what's really going on (more so, at least, than I thought I'd be able to; I knew about elementary equivalence, but I was still trying to work out how to explain it clearly). I've made some edits.
$endgroup$
– J.G.
Dec 14 '18 at 8:08
$begingroup$
Both Peano and Presberger arithmetic have many non-isomorphic models. As does the complete first order theory of $mathbb N$ in the language with addition and multiplication. It's not about isomorphism, it's about elementary equivalence (i.e. satisfying the same first order sentences). All models of Presberger arithmetic satisfy the exact same sentences in the first order language with addition (even though they aren't necessarily isomorphic), whereas Peano arithmetic has models that differ on some first order sentences in the language with addition and multiplication.
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:01
$begingroup$
Both Peano and Presberger arithmetic have many non-isomorphic models. As does the complete first order theory of $mathbb N$ in the language with addition and multiplication. It's not about isomorphism, it's about elementary equivalence (i.e. satisfying the same first order sentences). All models of Presberger arithmetic satisfy the exact same sentences in the first order language with addition (even though they aren't necessarily isomorphic), whereas Peano arithmetic has models that differ on some first order sentences in the language with addition and multiplication.
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:01
$begingroup$
More to the point: "If Peano arithmetic were complete, then all its models would be isomorphic" is false. (Well, I suppose actually it's true, since PA is not complete... but the general statement complete -> categorical is false and Presberger arithmetic is a counterexample.)
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:05
$begingroup$
More to the point: "If Peano arithmetic were complete, then all its models would be isomorphic" is false. (Well, I suppose actually it's true, since PA is not complete... but the general statement complete -> categorical is false and Presberger arithmetic is a counterexample.)
$endgroup$
– spaceisdarkgreen
Dec 14 '18 at 4:05
$begingroup$
@spaceisdarkgreen Thank you very much for both of your comments. They helped me work out how to provide an accessible explanation of what's really going on (more so, at least, than I thought I'd be able to; I knew about elementary equivalence, but I was still trying to work out how to explain it clearly). I've made some edits.
$endgroup$
– J.G.
Dec 14 '18 at 8:08
$begingroup$
@spaceisdarkgreen Thank you very much for both of your comments. They helped me work out how to provide an accessible explanation of what's really going on (more so, at least, than I thought I'd be able to; I knew about elementary equivalence, but I was still trying to work out how to explain it clearly). I've made some edits.
$endgroup$
– J.G.
Dec 14 '18 at 8:08
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%2f3033524%2fintuition-behind-unprovable-truths-godel%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
3
$begingroup$
I think you're hoping we can dumb down a technical result with misleading analogies that make you feel like you understand when you don't. I'd prefer to recommend you learn about $omega$-inconsistency.
$endgroup$
– J.G.
Dec 10 '18 at 6:18
1
$begingroup$
See Gödel, Escher, Bach: an Eternal Golden Braid for at least some intuition.
$endgroup$
– Shaun
Dec 10 '18 at 6:20
$begingroup$
You can start from an exposition of Gödel's Incompleteness Theorems.
$endgroup$
– Mauro ALLEGRANZA
Dec 10 '18 at 8:15
$begingroup$
Thinking to Godel's incompleteness theorems as corollaries of the halting problem helped me a lot.
$endgroup$
– reuns
Dec 10 '18 at 8:20
$begingroup$
True where? In arithmetic we have a canonical and natural model, so "true" implicitly mean "true in the standard model". But truth is always relative to a structure. And what does it even mean "truth that cannot be captured by syntax"? Truth is relative to an interpretation of a language. What does it mean for a true statement if you cannot write it in the relevant language?
$endgroup$
– Asaf Karagila♦
Dec 10 '18 at 8:23