First Order Logic Peano arithmetic Proof Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to better understand “ x occurs free in a wff ” in first order logic?First Order Logic problem using instant axiomShowing Inconsistency in Monadic Predicate LogicPeano Arithmetic - formulasHow to use nonlogical axioms of Peano ArithmeticProve that for every formula in the first-order logic language $l$ there is a quantifier free formula($B$) that have the following property.First order logic - Translating from spoken word to logic syntax and simple proofReplacement theorem for first-order logic and restrictionsPeano axioms and Herbrand's theoremNatural deduction in first-order logic
Is the Standard Deduction better than Itemized when both are the same amount?
Why is black pepper both grey and black?
What makes black pepper strong or mild?
Is there a way in Ruby to make just any one out of many keyword arguments required?
How much radiation do nuclear physics experiments expose researchers to nowadays?
What's the purpose of writing one's academic bio in 3rd person?
Do you forfeit tax refunds/credits if you aren't required to and don't file by April 15?
List *all* the tuples!
How to recreate this effect in Photoshop?
Is above average number of years spent on PhD considered a red flag in future academia or industry positions?
When to stop saving and start investing?
How can I fade player when goes inside or outside of the area?
IndentationError when pasting code in Python 3 interpreter mode
Is it true that "carbohydrates are of no use for the basal metabolic need"?
Should I call the interviewer directly, if HR aren't responding?
Does surprise arrest existing movement?
Is there a documented rationale why the House Ways and Means chairman can demand tax info?
Antler Helmet: Can it work?
Does the Giant Rocktopus have a Swim Speed?
Did Xerox really develop the first LAN?
What do you call a plan that's an alternative plan in case your initial plan fails?
ListPlot join points by nearest neighbor rather than order
Is it true to say that an hosting provider's DNS server is what links the entire hosting environment to ICANN?
If a contract sometimes uses the wrong name, is it still valid?
First Order Logic Peano arithmetic Proof
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to better understand “ x occurs free in a wff ” in first order logic?First Order Logic problem using instant axiomShowing Inconsistency in Monadic Predicate LogicPeano Arithmetic - formulasHow to use nonlogical axioms of Peano ArithmeticProve that for every formula in the first-order logic language $l$ there is a quantifier free formula($B$) that have the following property.First order logic - Translating from spoken word to logic syntax and simple proofReplacement theorem for first-order logic and restrictionsPeano axioms and Herbrand's theoremNatural deduction in first-order logic
$begingroup$
I'm trying to prove:
$forall xforall y((x=y)longrightarrow(xnot<y)$
I tried starting off with
$u=v, u+s(z) = vvdash u = v$
$u=v, u+s(z) = vvdash u+s(z) = v$
.
.
.
$u=v, u+s(z) = vvdash s(z) = 0$
and try to get a contradiction (since $s(z) not = 0$, is a theorem), but I'm having a lot of difficulty proving that $s(z) = 0$.
Any help would be greatly appreciated.
first-order-logic predicate-logic peano-axioms
asked Mar 31 at 23:20
Thomas FormalThomas Formal
134
$endgroup$
add a comment |
$begingroup$
I'm trying to prove:
$forall xforall y((x=y)longrightarrow(xnot<y)$
I tried starting off with
$u=v, u+s(z) = vvdash u = v$
$u=v, u+s(z) = vvdash u+s(z) = v$
.
.
.
$u=v, u+s(z) = vvdash s(z) = 0$
and try to get a contradiction (since $s(z) not = 0$, is a theorem), but I'm having a lot of difficulty proving that $s(z) = 0$.
Any help would be greatly appreciated.
first-order-logic predicate-logic peano-axioms
asked Mar 31 at 23:20
Thomas FormalThomas Formal
134
$endgroup$
$begingroup$
Hint: prove $u+a=u+bimplies a=b$ by induction on $u$.
$endgroup$
– Berci
Mar 31 at 23:28
$begingroup$
If im able to prove that, how would I apply it to my proof?
$endgroup$
– Thomas Formal
Mar 31 at 23:32
$begingroup$
Oh I understand, could you give a hint on how to prove the statement you stated?
$endgroup$
– Thomas Formal
Mar 31 at 23:33
$begingroup$
It can depend on the exact forms of the Peano axioms you're using, and/or basic statements that are already proved, e.g. commutativity of addition.
$endgroup$
– Berci
Apr 1 at 0:35
$begingroup$
More specifically, you need $s(u+y) =s(u)+y$ for the induction step.
$endgroup$
– Berci
Apr 1 at 0:37
add a comment |
$begingroup$
I'm trying to prove:
$forall xforall y((x=y)longrightarrow(xnot<y)$
I tried starting off with
$u=v, u+s(z) = vvdash u = v$
$u=v, u+s(z) = vvdash u+s(z) = v$
.
.
.
$u=v, u+s(z) = vvdash s(z) = 0$
and try to get a contradiction (since $s(z) not = 0$, is a theorem), but I'm having a lot of difficulty proving that $s(z) = 0$.
Any help would be greatly appreciated.
first-order-logic predicate-logic peano-axioms
asked Mar 31 at 23:20
Thomas FormalThomas Formal
134
$endgroup$
I'm trying to prove:
$forall xforall y((x=y)longrightarrow(xnot<y)$
I tried starting off with
$u=v, u+s(z) = vvdash u = v$
$u=v, u+s(z) = vvdash u+s(z) = v$
.
.
.
$u=v, u+s(z) = vvdash s(z) = 0$
and try to get a contradiction (since $s(z) not = 0$, is a theorem), but I'm having a lot of difficulty proving that $s(z) = 0$.
Any help would be greatly appreciated.
first-order-logic predicate-logic peano-axioms
first-order-logic predicate-logic peano-axioms
asked Mar 31 at 23:20
Thomas FormalThomas Formal
134
asked Mar 31 at 23:20
Thomas FormalThomas Formal
134
asked Mar 31 at 23:20
Thomas FormalThomas Formal
134
asked Mar 31 at 23:20
Thomas FormalThomas Formal
134
asked Mar 31 at 23:20
Thomas FormalThomas Formal
134
134
$begingroup$
Hint: prove $u+a=u+bimplies a=b$ by induction on $u$.
$endgroup$
– Berci
Mar 31 at 23:28
$begingroup$
If im able to prove that, how would I apply it to my proof?
$endgroup$
– Thomas Formal
Mar 31 at 23:32
$begingroup$
Oh I understand, could you give a hint on how to prove the statement you stated?
$endgroup$
– Thomas Formal
Mar 31 at 23:33
$begingroup$
It can depend on the exact forms of the Peano axioms you're using, and/or basic statements that are already proved, e.g. commutativity of addition.
$endgroup$
– Berci
Apr 1 at 0:35
$begingroup$
More specifically, you need $s(u+y) =s(u)+y$ for the induction step.
$endgroup$
– Berci
Apr 1 at 0:37
add a comment |
$begingroup$
Hint: prove $u+a=u+bimplies a=b$ by induction on $u$.
$endgroup$
– Berci
Mar 31 at 23:28
$begingroup$
If im able to prove that, how would I apply it to my proof?
$endgroup$
– Thomas Formal
Mar 31 at 23:32
$begingroup$
Oh I understand, could you give a hint on how to prove the statement you stated?
$endgroup$
– Thomas Formal
Mar 31 at 23:33
$begingroup$
It can depend on the exact forms of the Peano axioms you're using, and/or basic statements that are already proved, e.g. commutativity of addition.
$endgroup$
– Berci
Apr 1 at 0:35
$begingroup$
More specifically, you need $s(u+y) =s(u)+y$ for the induction step.
$endgroup$
– Berci
Apr 1 at 0:37
$begingroup$
Hint: prove $u+a=u+bimplies a=b$ by induction on $u$.
$endgroup$
– Berci
Mar 31 at 23:28
$begingroup$
Hint: prove $u+a=u+bimplies a=b$ by induction on $u$.
$endgroup$
– Berci
Mar 31 at 23:28
$begingroup$
If im able to prove that, how would I apply it to my proof?
$endgroup$
– Thomas Formal
Mar 31 at 23:32
$begingroup$
If im able to prove that, how would I apply it to my proof?
$endgroup$
– Thomas Formal
Mar 31 at 23:32
$begingroup$
Oh I understand, could you give a hint on how to prove the statement you stated?
$endgroup$
– Thomas Formal
Mar 31 at 23:33
$begingroup$
Oh I understand, could you give a hint on how to prove the statement you stated?
$endgroup$
– Thomas Formal
Mar 31 at 23:33
$begingroup$
It can depend on the exact forms of the Peano axioms you're using, and/or basic statements that are already proved, e.g. commutativity of addition.
$endgroup$
– Berci
Apr 1 at 0:35
$begingroup$
It can depend on the exact forms of the Peano axioms you're using, and/or basic statements that are already proved, e.g. commutativity of addition.
$endgroup$
– Berci
Apr 1 at 0:35
$begingroup$
More specifically, you need $s(u+y) =s(u)+y$ for the induction step.
$endgroup$
– Berci
Apr 1 at 0:37
$begingroup$
More specifically, you need $s(u+y) =s(u)+y$ for the induction step.
$endgroup$
– Berci
Apr 1 at 0:37
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Use the following lemma:
$$forall a,b,u:, u+a=u+bto a=b$$
This can be proved by induction on $u$, provided we already know $s(x+y)=s(x)+y,$ (which is another lemma if the axiom is stated in the other argument).
The base case $u=0$ is immediate.
Now suppose $s(u)+a=s(u)+b$. Then using the above statement, we have $s(u+a)=s(u+b)$. Then injectivity of $s$ implies $u+a=u+b$ which implies $a=b$ by induction hypothesis.
answered Apr 1 at 0:54
BerciBerci
62k23776
$endgroup$
$begingroup$
thanks!, this would just be induction on u right? Not a triple induction on a , b and u?
$endgroup$
– Thomas Formal
Apr 1 at 2:08
$begingroup$
I was able to prove this result, but our version of the lemma was $x+s(y) = s(x + y)$, would proving the one you wrote require induction again?
$endgroup$
– Thomas Formal
Apr 1 at 2:10
add a comment |
Your Answer
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%2f3170009%2ffirst-order-logic-peano-arithmetic-proof%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$
Use the following lemma:
$$forall a,b,u:, u+a=u+bto a=b$$
This can be proved by induction on $u$, provided we already know $s(x+y)=s(x)+y,$ (which is another lemma if the axiom is stated in the other argument).
The base case $u=0$ is immediate.
Now suppose $s(u)+a=s(u)+b$. Then using the above statement, we have $s(u+a)=s(u+b)$. Then injectivity of $s$ implies $u+a=u+b$ which implies $a=b$ by induction hypothesis.
answered Apr 1 at 0:54
BerciBerci
62k23776
$endgroup$
$begingroup$
thanks!, this would just be induction on u right? Not a triple induction on a , b and u?
$endgroup$
– Thomas Formal
Apr 1 at 2:08
$begingroup$
I was able to prove this result, but our version of the lemma was $x+s(y) = s(x + y)$, would proving the one you wrote require induction again?
$endgroup$
– Thomas Formal
Apr 1 at 2:10
add a comment |
$begingroup$
Use the following lemma:
$$forall a,b,u:, u+a=u+bto a=b$$
This can be proved by induction on $u$, provided we already know $s(x+y)=s(x)+y,$ (which is another lemma if the axiom is stated in the other argument).
The base case $u=0$ is immediate.
Now suppose $s(u)+a=s(u)+b$. Then using the above statement, we have $s(u+a)=s(u+b)$. Then injectivity of $s$ implies $u+a=u+b$ which implies $a=b$ by induction hypothesis.
answered Apr 1 at 0:54
BerciBerci
62k23776
$endgroup$
$begingroup$
thanks!, this would just be induction on u right? Not a triple induction on a , b and u?
$endgroup$
– Thomas Formal
Apr 1 at 2:08
$begingroup$
I was able to prove this result, but our version of the lemma was $x+s(y) = s(x + y)$, would proving the one you wrote require induction again?
$endgroup$
– Thomas Formal
Apr 1 at 2:10
add a comment |
$begingroup$
Use the following lemma:
$$forall a,b,u:, u+a=u+bto a=b$$
This can be proved by induction on $u$, provided we already know $s(x+y)=s(x)+y,$ (which is another lemma if the axiom is stated in the other argument).
The base case $u=0$ is immediate.
Now suppose $s(u)+a=s(u)+b$. Then using the above statement, we have $s(u+a)=s(u+b)$. Then injectivity of $s$ implies $u+a=u+b$ which implies $a=b$ by induction hypothesis.
answered Apr 1 at 0:54
BerciBerci
62k23776
$endgroup$
Use the following lemma:
$$forall a,b,u:, u+a=u+bto a=b$$
This can be proved by induction on $u$, provided we already know $s(x+y)=s(x)+y,$ (which is another lemma if the axiom is stated in the other argument).
The base case $u=0$ is immediate.
Now suppose $s(u)+a=s(u)+b$. Then using the above statement, we have $s(u+a)=s(u+b)$. Then injectivity of $s$ implies $u+a=u+b$ which implies $a=b$ by induction hypothesis.
answered Apr 1 at 0:54
BerciBerci
62k23776
answered Apr 1 at 0:54
BerciBerci
62k23776
answered Apr 1 at 0:54
BerciBerci
62k23776
answered Apr 1 at 0:54
BerciBerci
62k23776
62k23776
$begingroup$
thanks!, this would just be induction on u right? Not a triple induction on a , b and u?
$endgroup$
– Thomas Formal
Apr 1 at 2:08
$begingroup$
I was able to prove this result, but our version of the lemma was $x+s(y) = s(x + y)$, would proving the one you wrote require induction again?
$endgroup$
– Thomas Formal
Apr 1 at 2:10
add a comment |
$begingroup$
thanks!, this would just be induction on u right? Not a triple induction on a , b and u?
$endgroup$
– Thomas Formal
Apr 1 at 2:08
$begingroup$
I was able to prove this result, but our version of the lemma was $x+s(y) = s(x + y)$, would proving the one you wrote require induction again?
$endgroup$
– Thomas Formal
Apr 1 at 2:10
$begingroup$
thanks!, this would just be induction on u right? Not a triple induction on a , b and u?
$endgroup$
– Thomas Formal
Apr 1 at 2:08
$begingroup$
thanks!, this would just be induction on u right? Not a triple induction on a , b and u?
$endgroup$
– Thomas Formal
Apr 1 at 2:08
$begingroup$
I was able to prove this result, but our version of the lemma was $x+s(y) = s(x + y)$, would proving the one you wrote require induction again?
$endgroup$
– Thomas Formal
Apr 1 at 2:10
$begingroup$
I was able to prove this result, but our version of the lemma was $x+s(y) = s(x + y)$, would proving the one you wrote require induction again?
$endgroup$
– Thomas Formal
Apr 1 at 2:10
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%2f3170009%2ffirst-order-logic-peano-arithmetic-proof%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Hint: prove $u+a=u+bimplies a=b$ by induction on $u$.
$endgroup$
– Berci
Mar 31 at 23:28
$begingroup$
If im able to prove that, how would I apply it to my proof?
$endgroup$
– Thomas Formal
Mar 31 at 23:32
$begingroup$
Oh I understand, could you give a hint on how to prove the statement you stated?
$endgroup$
– Thomas Formal
Mar 31 at 23:33
$begingroup$
It can depend on the exact forms of the Peano axioms you're using, and/or basic statements that are already proved, e.g. commutativity of addition.
$endgroup$
– Berci
Apr 1 at 0:35
$begingroup$
More specifically, you need $s(u+y) =s(u)+y$ for the induction step.
$endgroup$
– Berci
Apr 1 at 0:37