Mixing
Arithmetic systems without Induction
$begingroup$
It's often said that AC is a controversial axiom and so often in my math classes when it is used a brief comment is made to the effect of "we can prove this without Zorn's Lemma but it's more work". And the attitude is that it doesn't matter, after all we can get the result by other means and the subject is geometry, analysis, etc. and not foundations (so it's not a big deal really).
However, Induction and the Well-Ordering Principle (its equivalent) are more common axioms however if we subtract these the same results seem to be true but at the same time I am not sure how to prove them.
So my question is: If we toss out WOP/Induction does it follow that everything falls apart? Robinson arithmetic is an example of such a system and it is essentially undecidable. I'm wanting clarification on what this means by way of examples (from Peano arithmetic); specifically, I'm wondering if in cases where we would have used Induction (or the equivalent) if we can't write a proof of the result do we conclude the result is unprovable or do we need a separate proof that it is "unprovable" (whatever that means). Do results have definite truth or false values or is it possible to be neither. If we can prove that the result is provable (i.e. that the result is either true or false and not neither) but we don't have an explicit proof of the result itself, does it follow that the result in our weaker system must be the same as it was in the stronger system (when we used Induction or whatever). If the result is "neither" can we tack on whatever we want the result to be as a new axiom in a consistent manner? I realize there are many questions here... here are some examples to help.
(1) "$sum_{j=1}^n j= frac{n(n+1)}{2}$"; this result is often how induction is introduced though induction is not required therefore it is clear the result would still hold in Robinson.
(2) "Any $nin N$ has a unique expression $n=c_11!+c_22!+cdots +c_kk!$ for some $kge1$, each $0le c_jle j$ and $c_kneq0$."
When I proved this, I used induction and the proof was rather messy and detailed; so while the result appears to always hold I cannot imagine proving it without induction. So it seems that induction is necessary... but I'm not sure of its truth value in Robinson arithmetic.
(3) "Every subset of $mathbb{N}$ is countable":Infinite sets with cardinality less than the natural numbers
It seems here that you either use AC (making the proof trivial) or you use the Well-Ordering Principle and then the proof is still easy but a little more work. But if we toss out these axioms then I'm not sure how to it prove the result. What's really interesting about this case, is that unlike the previous example where the result seems true (because we can test it for various cases) there is no way to test it here. It seems on par with the Continuum Hypothesis in terms of weirdness; I'm guessing in the absence of Induction there is no positive truth value to (3) but I'm not sure... and I'm guessing we could simply make an axiom about the existence of smaller infinities in a perfectly consistent way... though this is offensive to all intuition.
induction philosophy proof-theory meta-math
edited Jan 26 at 21:43
Asaf Karagila♦
307k33438769
asked Jan 26 at 16:28
SquirtleSquirtle
4,2081741
$endgroup$
add a comment |
$begingroup$
It's often said that AC is a controversial axiom and so often in my math classes when it is used a brief comment is made to the effect of "we can prove this without Zorn's Lemma but it's more work". And the attitude is that it doesn't matter, after all we can get the result by other means and the subject is geometry, analysis, etc. and not foundations (so it's not a big deal really).
However, Induction and the Well-Ordering Principle (its equivalent) are more common axioms however if we subtract these the same results seem to be true but at the same time I am not sure how to prove them.
So my question is: If we toss out WOP/Induction does it follow that everything falls apart? Robinson arithmetic is an example of such a system and it is essentially undecidable. I'm wanting clarification on what this means by way of examples (from Peano arithmetic); specifically, I'm wondering if in cases where we would have used Induction (or the equivalent) if we can't write a proof of the result do we conclude the result is unprovable or do we need a separate proof that it is "unprovable" (whatever that means). Do results have definite truth or false values or is it possible to be neither. If we can prove that the result is provable (i.e. that the result is either true or false and not neither) but we don't have an explicit proof of the result itself, does it follow that the result in our weaker system must be the same as it was in the stronger system (when we used Induction or whatever). If the result is "neither" can we tack on whatever we want the result to be as a new axiom in a consistent manner? I realize there are many questions here... here are some examples to help.
(1) "$sum_{j=1}^n j= frac{n(n+1)}{2}$"; this result is often how induction is introduced though induction is not required therefore it is clear the result would still hold in Robinson.
(2) "Any $nin N$ has a unique expression $n=c_11!+c_22!+cdots +c_kk!$ for some $kge1$, each $0le c_jle j$ and $c_kneq0$."
When I proved this, I used induction and the proof was rather messy and detailed; so while the result appears to always hold I cannot imagine proving it without induction. So it seems that induction is necessary... but I'm not sure of its truth value in Robinson arithmetic.
(3) "Every subset of $mathbb{N}$ is countable":Infinite sets with cardinality less than the natural numbers
It seems here that you either use AC (making the proof trivial) or you use the Well-Ordering Principle and then the proof is still easy but a little more work. But if we toss out these axioms then I'm not sure how to it prove the result. What's really interesting about this case, is that unlike the previous example where the result seems true (because we can test it for various cases) there is no way to test it here. It seems on par with the Continuum Hypothesis in terms of weirdness; I'm guessing in the absence of Induction there is no positive truth value to (3) but I'm not sure... and I'm guessing we could simply make an axiom about the existence of smaller infinities in a perfectly consistent way... though this is offensive to all intuition.
induction philosophy proof-theory meta-math
edited Jan 26 at 21:43
Asaf Karagila♦
307k33438769
asked Jan 26 at 16:28
SquirtleSquirtle
4,2081741
$endgroup$
$begingroup$
Your question is very unclear to me. Is it about induction or about choice? is it about arithmetic or about set theory?
$endgroup$
– Asaf Karagila♦
Jan 26 at 20:42
$begingroup$
Neither AC or induction per se but rather (1) do usual theorems fail to obtain in any sense whatsoever if we subtract our favorite axioms (induction, for example (but not necessarily induction)). (2) If we fail to be able to prove our old theorems should we then prove they cannot be proven in a weaker system and therefore they are neither true nor false? (3) If something is neither true nor false can we add it as an axiom and (4) If we can prove something has a proof but cannot prove it directly, does it follow that its value is the same as in the stronger system?
$endgroup$
– Squirtle
Jan 26 at 21:15
$begingroup$
@Squirtle This is all over the place, but (1) Sure, subtract axioms and you can prove fewer things. For instance, Robinson arithmetic cannot even prove $forall x,y(x+y=y+x).$ In general it is bad at proving universal statements, although it can often prove every instance separately. (2) We often can prove that the weaker system cannot prove a given statement, as is true with my previous example. It makes no sense to say something is true or false in a system, only provable, refutable (i.e. negation is provable) or neither. Truth is about structures (e.g. $mathbb N$), not formal systems.
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:43
$begingroup$
@Squirtle (3) If something is not refutable in a system, it is consistent to add it as an axiom. For instance, it's well known that (assuming PA is consistent), Con(PA) is not provable in PA, so it follows that PA + $lnot$Con(PA) is a consistent system. (4) Not sure what you mean here. Prove something has a proof where?
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:54
$begingroup$
I don't understand your example (1): what do you mean when you claim that it's clear induction isn't needed? At a glance, I don't even think Q can prove "For all $n$, $sum_{i=1}^ni$ exists." Keep in mind that even expressing this statement in the language of arithmetic is nontrivial - to define $sum_{i=1}^ni$ we need to talk about finite sequences of natural numbers (that is, $sum_{i=1}^ni$ is the unique number $x$ such that there is a sequence of length $n$ whose first term is $1$, whose $n$th term is $x$, and such that the $j+1$th term is the $j$th term plus $j+1$ for all $j<n$).
$endgroup$
– Noah Schweber
Feb 8 at 19:01
add a comment |
$begingroup$
It's often said that AC is a controversial axiom and so often in my math classes when it is used a brief comment is made to the effect of "we can prove this without Zorn's Lemma but it's more work". And the attitude is that it doesn't matter, after all we can get the result by other means and the subject is geometry, analysis, etc. and not foundations (so it's not a big deal really).
However, Induction and the Well-Ordering Principle (its equivalent) are more common axioms however if we subtract these the same results seem to be true but at the same time I am not sure how to prove them.
So my question is: If we toss out WOP/Induction does it follow that everything falls apart? Robinson arithmetic is an example of such a system and it is essentially undecidable. I'm wanting clarification on what this means by way of examples (from Peano arithmetic); specifically, I'm wondering if in cases where we would have used Induction (or the equivalent) if we can't write a proof of the result do we conclude the result is unprovable or do we need a separate proof that it is "unprovable" (whatever that means). Do results have definite truth or false values or is it possible to be neither. If we can prove that the result is provable (i.e. that the result is either true or false and not neither) but we don't have an explicit proof of the result itself, does it follow that the result in our weaker system must be the same as it was in the stronger system (when we used Induction or whatever). If the result is "neither" can we tack on whatever we want the result to be as a new axiom in a consistent manner? I realize there are many questions here... here are some examples to help.
(1) "$sum_{j=1}^n j= frac{n(n+1)}{2}$"; this result is often how induction is introduced though induction is not required therefore it is clear the result would still hold in Robinson.
(2) "Any $nin N$ has a unique expression $n=c_11!+c_22!+cdots +c_kk!$ for some $kge1$, each $0le c_jle j$ and $c_kneq0$."
When I proved this, I used induction and the proof was rather messy and detailed; so while the result appears to always hold I cannot imagine proving it without induction. So it seems that induction is necessary... but I'm not sure of its truth value in Robinson arithmetic.
(3) "Every subset of $mathbb{N}$ is countable":Infinite sets with cardinality less than the natural numbers
It seems here that you either use AC (making the proof trivial) or you use the Well-Ordering Principle and then the proof is still easy but a little more work. But if we toss out these axioms then I'm not sure how to it prove the result. What's really interesting about this case, is that unlike the previous example where the result seems true (because we can test it for various cases) there is no way to test it here. It seems on par with the Continuum Hypothesis in terms of weirdness; I'm guessing in the absence of Induction there is no positive truth value to (3) but I'm not sure... and I'm guessing we could simply make an axiom about the existence of smaller infinities in a perfectly consistent way... though this is offensive to all intuition.
induction philosophy proof-theory meta-math
edited Jan 26 at 21:43
Asaf Karagila♦
307k33438769
asked Jan 26 at 16:28
SquirtleSquirtle
4,2081741
$endgroup$
It's often said that AC is a controversial axiom and so often in my math classes when it is used a brief comment is made to the effect of "we can prove this without Zorn's Lemma but it's more work". And the attitude is that it doesn't matter, after all we can get the result by other means and the subject is geometry, analysis, etc. and not foundations (so it's not a big deal really).
However, Induction and the Well-Ordering Principle (its equivalent) are more common axioms however if we subtract these the same results seem to be true but at the same time I am not sure how to prove them.
So my question is: If we toss out WOP/Induction does it follow that everything falls apart? Robinson arithmetic is an example of such a system and it is essentially undecidable. I'm wanting clarification on what this means by way of examples (from Peano arithmetic); specifically, I'm wondering if in cases where we would have used Induction (or the equivalent) if we can't write a proof of the result do we conclude the result is unprovable or do we need a separate proof that it is "unprovable" (whatever that means). Do results have definite truth or false values or is it possible to be neither. If we can prove that the result is provable (i.e. that the result is either true or false and not neither) but we don't have an explicit proof of the result itself, does it follow that the result in our weaker system must be the same as it was in the stronger system (when we used Induction or whatever). If the result is "neither" can we tack on whatever we want the result to be as a new axiom in a consistent manner? I realize there are many questions here... here are some examples to help.
(1) "$sum_{j=1}^n j= frac{n(n+1)}{2}$"; this result is often how induction is introduced though induction is not required therefore it is clear the result would still hold in Robinson.
(2) "Any $nin N$ has a unique expression $n=c_11!+c_22!+cdots +c_kk!$ for some $kge1$, each $0le c_jle j$ and $c_kneq0$."
When I proved this, I used induction and the proof was rather messy and detailed; so while the result appears to always hold I cannot imagine proving it without induction. So it seems that induction is necessary... but I'm not sure of its truth value in Robinson arithmetic.
(3) "Every subset of $mathbb{N}$ is countable":Infinite sets with cardinality less than the natural numbers
It seems here that you either use AC (making the proof trivial) or you use the Well-Ordering Principle and then the proof is still easy but a little more work. But if we toss out these axioms then I'm not sure how to it prove the result. What's really interesting about this case, is that unlike the previous example where the result seems true (because we can test it for various cases) there is no way to test it here. It seems on par with the Continuum Hypothesis in terms of weirdness; I'm guessing in the absence of Induction there is no positive truth value to (3) but I'm not sure... and I'm guessing we could simply make an axiom about the existence of smaller infinities in a perfectly consistent way... though this is offensive to all intuition.
induction philosophy proof-theory meta-math
induction philosophy proof-theory meta-math
edited Jan 26 at 21:43
Asaf Karagila♦
307k33438769
asked Jan 26 at 16:28
SquirtleSquirtle
4,2081741
edited Jan 26 at 21:43
Asaf Karagila♦
307k33438769
asked Jan 26 at 16:28
SquirtleSquirtle
4,2081741
edited Jan 26 at 21:43
Asaf Karagila♦
307k33438769
edited Jan 26 at 21:43
Asaf Karagila♦
307k33438769
edited Jan 26 at 21:43
Asaf Karagila♦
307k33438769
307k33438769
asked Jan 26 at 16:28
SquirtleSquirtle
4,2081741
asked Jan 26 at 16:28
SquirtleSquirtle
4,2081741
asked Jan 26 at 16:28
SquirtleSquirtle
4,2081741
4,2081741
$begingroup$
Your question is very unclear to me. Is it about induction or about choice? is it about arithmetic or about set theory?
$endgroup$
– Asaf Karagila♦
Jan 26 at 20:42
$begingroup$
Neither AC or induction per se but rather (1) do usual theorems fail to obtain in any sense whatsoever if we subtract our favorite axioms (induction, for example (but not necessarily induction)). (2) If we fail to be able to prove our old theorems should we then prove they cannot be proven in a weaker system and therefore they are neither true nor false? (3) If something is neither true nor false can we add it as an axiom and (4) If we can prove something has a proof but cannot prove it directly, does it follow that its value is the same as in the stronger system?
$endgroup$
– Squirtle
Jan 26 at 21:15
$begingroup$
@Squirtle This is all over the place, but (1) Sure, subtract axioms and you can prove fewer things. For instance, Robinson arithmetic cannot even prove $forall x,y(x+y=y+x).$ In general it is bad at proving universal statements, although it can often prove every instance separately. (2) We often can prove that the weaker system cannot prove a given statement, as is true with my previous example. It makes no sense to say something is true or false in a system, only provable, refutable (i.e. negation is provable) or neither. Truth is about structures (e.g. $mathbb N$), not formal systems.
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:43
$begingroup$
@Squirtle (3) If something is not refutable in a system, it is consistent to add it as an axiom. For instance, it's well known that (assuming PA is consistent), Con(PA) is not provable in PA, so it follows that PA + $lnot$Con(PA) is a consistent system. (4) Not sure what you mean here. Prove something has a proof where?
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:54
$begingroup$
I don't understand your example (1): what do you mean when you claim that it's clear induction isn't needed? At a glance, I don't even think Q can prove "For all $n$, $sum_{i=1}^ni$ exists." Keep in mind that even expressing this statement in the language of arithmetic is nontrivial - to define $sum_{i=1}^ni$ we need to talk about finite sequences of natural numbers (that is, $sum_{i=1}^ni$ is the unique number $x$ such that there is a sequence of length $n$ whose first term is $1$, whose $n$th term is $x$, and such that the $j+1$th term is the $j$th term plus $j+1$ for all $j<n$).
$endgroup$
– Noah Schweber
Feb 8 at 19:01
add a comment |
$begingroup$
Your question is very unclear to me. Is it about induction or about choice? is it about arithmetic or about set theory?
$endgroup$
– Asaf Karagila♦
Jan 26 at 20:42
$begingroup$
Neither AC or induction per se but rather (1) do usual theorems fail to obtain in any sense whatsoever if we subtract our favorite axioms (induction, for example (but not necessarily induction)). (2) If we fail to be able to prove our old theorems should we then prove they cannot be proven in a weaker system and therefore they are neither true nor false? (3) If something is neither true nor false can we add it as an axiom and (4) If we can prove something has a proof but cannot prove it directly, does it follow that its value is the same as in the stronger system?
$endgroup$
– Squirtle
Jan 26 at 21:15
$begingroup$
@Squirtle This is all over the place, but (1) Sure, subtract axioms and you can prove fewer things. For instance, Robinson arithmetic cannot even prove $forall x,y(x+y=y+x).$ In general it is bad at proving universal statements, although it can often prove every instance separately. (2) We often can prove that the weaker system cannot prove a given statement, as is true with my previous example. It makes no sense to say something is true or false in a system, only provable, refutable (i.e. negation is provable) or neither. Truth is about structures (e.g. $mathbb N$), not formal systems.
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:43
$begingroup$
@Squirtle (3) If something is not refutable in a system, it is consistent to add it as an axiom. For instance, it's well known that (assuming PA is consistent), Con(PA) is not provable in PA, so it follows that PA + $lnot$Con(PA) is a consistent system. (4) Not sure what you mean here. Prove something has a proof where?
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:54
$begingroup$
I don't understand your example (1): what do you mean when you claim that it's clear induction isn't needed? At a glance, I don't even think Q can prove "For all $n$, $sum_{i=1}^ni$ exists." Keep in mind that even expressing this statement in the language of arithmetic is nontrivial - to define $sum_{i=1}^ni$ we need to talk about finite sequences of natural numbers (that is, $sum_{i=1}^ni$ is the unique number $x$ such that there is a sequence of length $n$ whose first term is $1$, whose $n$th term is $x$, and such that the $j+1$th term is the $j$th term plus $j+1$ for all $j<n$).
$endgroup$
– Noah Schweber
Feb 8 at 19:01
$begingroup$
Your question is very unclear to me. Is it about induction or about choice? is it about arithmetic or about set theory?
$endgroup$
– Asaf Karagila♦
Jan 26 at 20:42
$begingroup$
Your question is very unclear to me. Is it about induction or about choice? is it about arithmetic or about set theory?
$endgroup$
– Asaf Karagila♦
Jan 26 at 20:42
$begingroup$
Neither AC or induction per se but rather (1) do usual theorems fail to obtain in any sense whatsoever if we subtract our favorite axioms (induction, for example (but not necessarily induction)). (2) If we fail to be able to prove our old theorems should we then prove they cannot be proven in a weaker system and therefore they are neither true nor false? (3) If something is neither true nor false can we add it as an axiom and (4) If we can prove something has a proof but cannot prove it directly, does it follow that its value is the same as in the stronger system?
$endgroup$
– Squirtle
Jan 26 at 21:15
$begingroup$
Neither AC or induction per se but rather (1) do usual theorems fail to obtain in any sense whatsoever if we subtract our favorite axioms (induction, for example (but not necessarily induction)). (2) If we fail to be able to prove our old theorems should we then prove they cannot be proven in a weaker system and therefore they are neither true nor false? (3) If something is neither true nor false can we add it as an axiom and (4) If we can prove something has a proof but cannot prove it directly, does it follow that its value is the same as in the stronger system?
$endgroup$
– Squirtle
Jan 26 at 21:15
$begingroup$
@Squirtle This is all over the place, but (1) Sure, subtract axioms and you can prove fewer things. For instance, Robinson arithmetic cannot even prove $forall x,y(x+y=y+x).$ In general it is bad at proving universal statements, although it can often prove every instance separately. (2) We often can prove that the weaker system cannot prove a given statement, as is true with my previous example. It makes no sense to say something is true or false in a system, only provable, refutable (i.e. negation is provable) or neither. Truth is about structures (e.g. $mathbb N$), not formal systems.
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:43
$begingroup$
@Squirtle This is all over the place, but (1) Sure, subtract axioms and you can prove fewer things. For instance, Robinson arithmetic cannot even prove $forall x,y(x+y=y+x).$ In general it is bad at proving universal statements, although it can often prove every instance separately. (2) We often can prove that the weaker system cannot prove a given statement, as is true with my previous example. It makes no sense to say something is true or false in a system, only provable, refutable (i.e. negation is provable) or neither. Truth is about structures (e.g. $mathbb N$), not formal systems.
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:43
$begingroup$
@Squirtle (3) If something is not refutable in a system, it is consistent to add it as an axiom. For instance, it's well known that (assuming PA is consistent), Con(PA) is not provable in PA, so it follows that PA + $lnot$Con(PA) is a consistent system. (4) Not sure what you mean here. Prove something has a proof where?
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:54
$begingroup$
@Squirtle (3) If something is not refutable in a system, it is consistent to add it as an axiom. For instance, it's well known that (assuming PA is consistent), Con(PA) is not provable in PA, so it follows that PA + $lnot$Con(PA) is a consistent system. (4) Not sure what you mean here. Prove something has a proof where?
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:54
$begingroup$
I don't understand your example (1): what do you mean when you claim that it's clear induction isn't needed? At a glance, I don't even think Q can prove "For all $n$, $sum_{i=1}^ni$ exists." Keep in mind that even expressing this statement in the language of arithmetic is nontrivial - to define $sum_{i=1}^ni$ we need to talk about finite sequences of natural numbers (that is, $sum_{i=1}^ni$ is the unique number $x$ such that there is a sequence of length $n$ whose first term is $1$, whose $n$th term is $x$, and such that the $j+1$th term is the $j$th term plus $j+1$ for all $j<n$).
$endgroup$
– Noah Schweber
Feb 8 at 19:01
$begingroup$
I don't understand your example (1): what do you mean when you claim that it's clear induction isn't needed? At a glance, I don't even think Q can prove "For all $n$, $sum_{i=1}^ni$ exists." Keep in mind that even expressing this statement in the language of arithmetic is nontrivial - to define $sum_{i=1}^ni$ we need to talk about finite sequences of natural numbers (that is, $sum_{i=1}^ni$ is the unique number $x$ such that there is a sequence of length $n$ whose first term is $1$, whose $n$th term is $x$, and such that the $j+1$th term is the $j$th term plus $j+1$ for all $j<n$).
$endgroup$
– Noah Schweber
Feb 8 at 19:01
add a comment |
0
active
oldest
votes
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%2f3088449%2farithmetic-systems-without-induction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3088449%2farithmetic-systems-without-induction%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$
Your question is very unclear to me. Is it about induction or about choice? is it about arithmetic or about set theory?
$endgroup$
– Asaf Karagila♦
Jan 26 at 20:42
$begingroup$
Neither AC or induction per se but rather (1) do usual theorems fail to obtain in any sense whatsoever if we subtract our favorite axioms (induction, for example (but not necessarily induction)). (2) If we fail to be able to prove our old theorems should we then prove they cannot be proven in a weaker system and therefore they are neither true nor false? (3) If something is neither true nor false can we add it as an axiom and (4) If we can prove something has a proof but cannot prove it directly, does it follow that its value is the same as in the stronger system?
$endgroup$
– Squirtle
Jan 26 at 21:15
$begingroup$
@Squirtle This is all over the place, but (1) Sure, subtract axioms and you can prove fewer things. For instance, Robinson arithmetic cannot even prove $forall x,y(x+y=y+x).$ In general it is bad at proving universal statements, although it can often prove every instance separately. (2) We often can prove that the weaker system cannot prove a given statement, as is true with my previous example. It makes no sense to say something is true or false in a system, only provable, refutable (i.e. negation is provable) or neither. Truth is about structures (e.g. $mathbb N$), not formal systems.
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:43
$begingroup$
@Squirtle (3) If something is not refutable in a system, it is consistent to add it as an axiom. For instance, it's well known that (assuming PA is consistent), Con(PA) is not provable in PA, so it follows that PA + $lnot$Con(PA) is a consistent system. (4) Not sure what you mean here. Prove something has a proof where?
$endgroup$
– spaceisdarkgreen
Jan 27 at 0:54
$begingroup$
I don't understand your example (1): what do you mean when you claim that it's clear induction isn't needed? At a glance, I don't even think Q can prove "For all $n$, $sum_{i=1}^ni$ exists." Keep in mind that even expressing this statement in the language of arithmetic is nontrivial - to define $sum_{i=1}^ni$ we need to talk about finite sequences of natural numbers (that is, $sum_{i=1}^ni$ is the unique number $x$ such that there is a sequence of length $n$ whose first term is $1$, whose $n$th term is $x$, and such that the $j+1$th term is the $j$th term plus $j+1$ for all $j<n$).
$endgroup$
– Noah Schweber
Feb 8 at 19:01