Can any proof by contrapositive be rephrased into a proof by contradiction?
$begingroup$
From my understanding,
Proof by contrapositive: Prove $P implies Q$, by proving that $neg Q implies neg P$ since they are logically equivalent.
Proof by contradiction: Prove $P implies Q$ by showing that $P wedge neg Q$ yields an absurdity and hence false. So $neg (P wedge neg Q)$ is equivalent to $neg (neg (P implies Q))$ and $P implies Q$ by double negation so showing that $neg (P wedge neg Q)$ proves $P implies Q$.
If the absurdity derived during the procedure for a proof by contradiction is $P wedge neg Q impliesneg P$, we have essentially already proven $P implies Q$ by contrapositive since $neg Q implies neg P$ is precisely the required condition for proof by contrapositive. But $(P wedge neg Q) implies neg P$ is also a contradictory statement which means that $P implies Q$ must be true.
Now the question is this. Is this proof by contradiction still a valid form of proof even though its a proof by contrapositive in disguise? To me, this proof by contradiction also seems to be a valid proof as it does seem to satisfy the conditions(if they are correct) for proof by contradiction.
Additionally, if you have a contrapositive proof, so you have shown that $neg Q implies neg P$, is it possible to rephrase this in a proof by contradiction by supposing that $P wedge neg Q$ instead of just $neg Q$.
If this is the case, what is the point in distinguishing proof by contradiction from proof by contrapositive?
edit: My thought is that proof by contrapositive is a direct proof while proof by contradiction, in this case, depends on the validity of the double negation law which apparently isn't valid in intuitionistic logic.
discrete-mathematics logic proof-writing propositional-calculus
asked Dec 26 '18 at 0:10
Sei SakataSei Sakata
10810
$endgroup$
add a comment |
$begingroup$
From my understanding,
Proof by contrapositive: Prove $P implies Q$, by proving that $neg Q implies neg P$ since they are logically equivalent.
Proof by contradiction: Prove $P implies Q$ by showing that $P wedge neg Q$ yields an absurdity and hence false. So $neg (P wedge neg Q)$ is equivalent to $neg (neg (P implies Q))$ and $P implies Q$ by double negation so showing that $neg (P wedge neg Q)$ proves $P implies Q$.
If the absurdity derived during the procedure for a proof by contradiction is $P wedge neg Q impliesneg P$, we have essentially already proven $P implies Q$ by contrapositive since $neg Q implies neg P$ is precisely the required condition for proof by contrapositive. But $(P wedge neg Q) implies neg P$ is also a contradictory statement which means that $P implies Q$ must be true.
Now the question is this. Is this proof by contradiction still a valid form of proof even though its a proof by contrapositive in disguise? To me, this proof by contradiction also seems to be a valid proof as it does seem to satisfy the conditions(if they are correct) for proof by contradiction.
Additionally, if you have a contrapositive proof, so you have shown that $neg Q implies neg P$, is it possible to rephrase this in a proof by contradiction by supposing that $P wedge neg Q$ instead of just $neg Q$.
If this is the case, what is the point in distinguishing proof by contradiction from proof by contrapositive?
edit: My thought is that proof by contrapositive is a direct proof while proof by contradiction, in this case, depends on the validity of the double negation law which apparently isn't valid in intuitionistic logic.
discrete-mathematics logic proof-writing propositional-calculus
asked Dec 26 '18 at 0:10
Sei SakataSei Sakata
10810
$endgroup$
3
$begingroup$
The $(neg Qimpliesneg P)implies(Pimplies Q)$ direction of the equivalence also requires something like double negation elimination assuming you are starting from a reasonably typical constructive logic.
$endgroup$
– Derek Elkins
Dec 26 '18 at 0:25
$begingroup$
If every proof by contrapositive can be rephrased into a proof by contradiction, why do so many mathematicians prefer proof by contrapositive when it can be shown that way?
$endgroup$
– Sei Sakata
Dec 26 '18 at 0:29
2
$begingroup$
@SeiSakata sometimes rephrasing the problem in the contrapositive form makes the proof easier or adds some intuition to the statement. Sometimes it's merely a matter of preference.
$endgroup$
– CyclotomicField
Dec 26 '18 at 0:33
$begingroup$
@spaceisdarkgreen But what we are discussing here is only in one direction. The statement that every proof by contrapositive can be rephrased into a proof by contradiction is seemingly true but the converse doesn't necessarily hold. I am not sure if you were referring to this in your comment" any proof by contradiction “can be rephrased” as a direct proof". BTW I said seemingly true since the line of reasoning that a proof by contrapositive can be rephrased into a proof by contradiction seems to be general enough to account for all cases. But I might be mistaken and not true at all.
$endgroup$
– Sei Sakata
Dec 26 '18 at 1:33
$begingroup$
Sorry, I didn't read your definition of what you're calling a proof by contradiction carefully... you are right that contrapositive is a special case of contradiction here (coincidentally, I wrote an answer about precisely this a couple days ago math.stackexchange.com/questions/3050738/…).
$endgroup$
– spaceisdarkgreen
Dec 26 '18 at 7:40
add a comment |
$begingroup$
From my understanding,
Proof by contrapositive: Prove $P implies Q$, by proving that $neg Q implies neg P$ since they are logically equivalent.
Proof by contradiction: Prove $P implies Q$ by showing that $P wedge neg Q$ yields an absurdity and hence false. So $neg (P wedge neg Q)$ is equivalent to $neg (neg (P implies Q))$ and $P implies Q$ by double negation so showing that $neg (P wedge neg Q)$ proves $P implies Q$.
If the absurdity derived during the procedure for a proof by contradiction is $P wedge neg Q impliesneg P$, we have essentially already proven $P implies Q$ by contrapositive since $neg Q implies neg P$ is precisely the required condition for proof by contrapositive. But $(P wedge neg Q) implies neg P$ is also a contradictory statement which means that $P implies Q$ must be true.
Now the question is this. Is this proof by contradiction still a valid form of proof even though its a proof by contrapositive in disguise? To me, this proof by contradiction also seems to be a valid proof as it does seem to satisfy the conditions(if they are correct) for proof by contradiction.
Additionally, if you have a contrapositive proof, so you have shown that $neg Q implies neg P$, is it possible to rephrase this in a proof by contradiction by supposing that $P wedge neg Q$ instead of just $neg Q$.
If this is the case, what is the point in distinguishing proof by contradiction from proof by contrapositive?
edit: My thought is that proof by contrapositive is a direct proof while proof by contradiction, in this case, depends on the validity of the double negation law which apparently isn't valid in intuitionistic logic.
discrete-mathematics logic proof-writing propositional-calculus
asked Dec 26 '18 at 0:10
Sei SakataSei Sakata
10810
$endgroup$
From my understanding,
Proof by contrapositive: Prove $P implies Q$, by proving that $neg Q implies neg P$ since they are logically equivalent.
Proof by contradiction: Prove $P implies Q$ by showing that $P wedge neg Q$ yields an absurdity and hence false. So $neg (P wedge neg Q)$ is equivalent to $neg (neg (P implies Q))$ and $P implies Q$ by double negation so showing that $neg (P wedge neg Q)$ proves $P implies Q$.
If the absurdity derived during the procedure for a proof by contradiction is $P wedge neg Q impliesneg P$, we have essentially already proven $P implies Q$ by contrapositive since $neg Q implies neg P$ is precisely the required condition for proof by contrapositive. But $(P wedge neg Q) implies neg P$ is also a contradictory statement which means that $P implies Q$ must be true.
Now the question is this. Is this proof by contradiction still a valid form of proof even though its a proof by contrapositive in disguise? To me, this proof by contradiction also seems to be a valid proof as it does seem to satisfy the conditions(if they are correct) for proof by contradiction.
Additionally, if you have a contrapositive proof, so you have shown that $neg Q implies neg P$, is it possible to rephrase this in a proof by contradiction by supposing that $P wedge neg Q$ instead of just $neg Q$.
If this is the case, what is the point in distinguishing proof by contradiction from proof by contrapositive?
edit: My thought is that proof by contrapositive is a direct proof while proof by contradiction, in this case, depends on the validity of the double negation law which apparently isn't valid in intuitionistic logic.
discrete-mathematics logic proof-writing propositional-calculus
discrete-mathematics logic proof-writing propositional-calculus
asked Dec 26 '18 at 0:10
Sei SakataSei Sakata
10810
asked Dec 26 '18 at 0:10
Sei SakataSei Sakata
10810
edited Dec 26 '18 at 0:18
Sei Sakata
asked Dec 26 '18 at 0:10
Sei SakataSei Sakata
10810
asked Dec 26 '18 at 0:10
Sei SakataSei Sakata
10810
asked Dec 26 '18 at 0:10
Sei SakataSei Sakata
10810
10810
3
$begingroup$
The $(neg Qimpliesneg P)implies(Pimplies Q)$ direction of the equivalence also requires something like double negation elimination assuming you are starting from a reasonably typical constructive logic.
$endgroup$
– Derek Elkins
Dec 26 '18 at 0:25
$begingroup$
If every proof by contrapositive can be rephrased into a proof by contradiction, why do so many mathematicians prefer proof by contrapositive when it can be shown that way?
$endgroup$
– Sei Sakata
Dec 26 '18 at 0:29
2
$begingroup$
@SeiSakata sometimes rephrasing the problem in the contrapositive form makes the proof easier or adds some intuition to the statement. Sometimes it's merely a matter of preference.
$endgroup$
– CyclotomicField
Dec 26 '18 at 0:33
$begingroup$
@spaceisdarkgreen But what we are discussing here is only in one direction. The statement that every proof by contrapositive can be rephrased into a proof by contradiction is seemingly true but the converse doesn't necessarily hold. I am not sure if you were referring to this in your comment" any proof by contradiction “can be rephrased” as a direct proof". BTW I said seemingly true since the line of reasoning that a proof by contrapositive can be rephrased into a proof by contradiction seems to be general enough to account for all cases. But I might be mistaken and not true at all.
$endgroup$
– Sei Sakata
Dec 26 '18 at 1:33
$begingroup$
Sorry, I didn't read your definition of what you're calling a proof by contradiction carefully... you are right that contrapositive is a special case of contradiction here (coincidentally, I wrote an answer about precisely this a couple days ago math.stackexchange.com/questions/3050738/…).
$endgroup$
– spaceisdarkgreen
Dec 26 '18 at 7:40
add a comment |
3
$begingroup$
The $(neg Qimpliesneg P)implies(Pimplies Q)$ direction of the equivalence also requires something like double negation elimination assuming you are starting from a reasonably typical constructive logic.
$endgroup$
– Derek Elkins
Dec 26 '18 at 0:25
$begingroup$
If every proof by contrapositive can be rephrased into a proof by contradiction, why do so many mathematicians prefer proof by contrapositive when it can be shown that way?
$endgroup$
– Sei Sakata
Dec 26 '18 at 0:29
2
$begingroup$
@SeiSakata sometimes rephrasing the problem in the contrapositive form makes the proof easier or adds some intuition to the statement. Sometimes it's merely a matter of preference.
$endgroup$
– CyclotomicField
Dec 26 '18 at 0:33
$begingroup$
@spaceisdarkgreen But what we are discussing here is only in one direction. The statement that every proof by contrapositive can be rephrased into a proof by contradiction is seemingly true but the converse doesn't necessarily hold. I am not sure if you were referring to this in your comment" any proof by contradiction “can be rephrased” as a direct proof". BTW I said seemingly true since the line of reasoning that a proof by contrapositive can be rephrased into a proof by contradiction seems to be general enough to account for all cases. But I might be mistaken and not true at all.
$endgroup$
– Sei Sakata
Dec 26 '18 at 1:33
$begingroup$
Sorry, I didn't read your definition of what you're calling a proof by contradiction carefully... you are right that contrapositive is a special case of contradiction here (coincidentally, I wrote an answer about precisely this a couple days ago math.stackexchange.com/questions/3050738/…).
$endgroup$
– spaceisdarkgreen
Dec 26 '18 at 7:40
3
3
$begingroup$
The $(neg Qimpliesneg P)implies(Pimplies Q)$ direction of the equivalence also requires something like double negation elimination assuming you are starting from a reasonably typical constructive logic.
$endgroup$
– Derek Elkins
Dec 26 '18 at 0:25
$begingroup$
The $(neg Qimpliesneg P)implies(Pimplies Q)$ direction of the equivalence also requires something like double negation elimination assuming you are starting from a reasonably typical constructive logic.
$endgroup$
– Derek Elkins
Dec 26 '18 at 0:25
$begingroup$
If every proof by contrapositive can be rephrased into a proof by contradiction, why do so many mathematicians prefer proof by contrapositive when it can be shown that way?
$endgroup$
– Sei Sakata
Dec 26 '18 at 0:29
$begingroup$
If every proof by contrapositive can be rephrased into a proof by contradiction, why do so many mathematicians prefer proof by contrapositive when it can be shown that way?
$endgroup$
– Sei Sakata
Dec 26 '18 at 0:29
2
2
$begingroup$
@SeiSakata sometimes rephrasing the problem in the contrapositive form makes the proof easier or adds some intuition to the statement. Sometimes it's merely a matter of preference.
$endgroup$
– CyclotomicField
Dec 26 '18 at 0:33
$begingroup$
@SeiSakata sometimes rephrasing the problem in the contrapositive form makes the proof easier or adds some intuition to the statement. Sometimes it's merely a matter of preference.
$endgroup$
– CyclotomicField
Dec 26 '18 at 0:33
$begingroup$
@spaceisdarkgreen But what we are discussing here is only in one direction. The statement that every proof by contrapositive can be rephrased into a proof by contradiction is seemingly true but the converse doesn't necessarily hold. I am not sure if you were referring to this in your comment" any proof by contradiction “can be rephrased” as a direct proof". BTW I said seemingly true since the line of reasoning that a proof by contrapositive can be rephrased into a proof by contradiction seems to be general enough to account for all cases. But I might be mistaken and not true at all.
$endgroup$
– Sei Sakata
Dec 26 '18 at 1:33
$begingroup$
@spaceisdarkgreen But what we are discussing here is only in one direction. The statement that every proof by contrapositive can be rephrased into a proof by contradiction is seemingly true but the converse doesn't necessarily hold. I am not sure if you were referring to this in your comment" any proof by contradiction “can be rephrased” as a direct proof". BTW I said seemingly true since the line of reasoning that a proof by contrapositive can be rephrased into a proof by contradiction seems to be general enough to account for all cases. But I might be mistaken and not true at all.
$endgroup$
– Sei Sakata
Dec 26 '18 at 1:33
$begingroup$
Sorry, I didn't read your definition of what you're calling a proof by contradiction carefully... you are right that contrapositive is a special case of contradiction here (coincidentally, I wrote an answer about precisely this a couple days ago math.stackexchange.com/questions/3050738/…).
$endgroup$
– spaceisdarkgreen
Dec 26 '18 at 7:40
$begingroup$
Sorry, I didn't read your definition of what you're calling a proof by contradiction carefully... you are right that contrapositive is a special case of contradiction here (coincidentally, I wrote an answer about precisely this a couple days ago math.stackexchange.com/questions/3050738/…).
$endgroup$
– spaceisdarkgreen
Dec 26 '18 at 7:40
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Yes it is valid... it doesn't really matter if it's something else 'in disguise', just that is it correct. And deriving $lnot P$ from $Plandlnot Q$ is certainly leads to a contradiction that implies $lnot (Pland lnot Q)$ is true, which implies that $Pto Q$ is true. One thing to note (that I think you have noticed based on your second question) is that you have an additional assumption of $P$ open and available for use when you derive $lnot P,$ unlike in the case of just deriving $lnot Qto lnot P$ by assuming $lnot Q$ and deriving $lnot P.$
So the second question amounts to whether it is admissible to assume $P$ in a proof of $lnot Qto lnot P.$ It is, and the easiest way to see this is reasoning semantically and using the completeness/soundness theorem. If $Pvdash lnot Qto lnot P$ then every interpretation in which $P$ is true has $Q$ true, which means precisely the same thing as $vdash Pto Q,$ so we have $vdash lnot Qto lnot P.$
As a result, proof by contrapositive is essentially a special case of what you're calling proof by contradiction, where the contradiction takes the special form $lnot P$ contradicting with $P.$
I think the reason you might have seen framing contrapositive proofs as proofs by contradiction discouraged is for style reasons. Unless the outstanding assumption of $P$ is used (unnecessarily), the part of the proof outside the inner proof of $lnot Qto lnot P$ is just boilerplate that can be omitted. It is also more informative to call it a proof by contrapositive since that is a special case of contradiction.
(As Derek indicates in the comments, proof by contrapositive is not intuitionistically valid, so it doesn't have anything to do with this.)
answered Dec 26 '18 at 7:51
spaceisdarkgreenspaceisdarkgreen
33.9k21754
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3052530%2fcan-any-proof-by-contrapositive-be-rephrased-into-a-proof-by-contradiction%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$
Yes it is valid... it doesn't really matter if it's something else 'in disguise', just that is it correct. And deriving $lnot P$ from $Plandlnot Q$ is certainly leads to a contradiction that implies $lnot (Pland lnot Q)$ is true, which implies that $Pto Q$ is true. One thing to note (that I think you have noticed based on your second question) is that you have an additional assumption of $P$ open and available for use when you derive $lnot P,$ unlike in the case of just deriving $lnot Qto lnot P$ by assuming $lnot Q$ and deriving $lnot P.$
So the second question amounts to whether it is admissible to assume $P$ in a proof of $lnot Qto lnot P.$ It is, and the easiest way to see this is reasoning semantically and using the completeness/soundness theorem. If $Pvdash lnot Qto lnot P$ then every interpretation in which $P$ is true has $Q$ true, which means precisely the same thing as $vdash Pto Q,$ so we have $vdash lnot Qto lnot P.$
As a result, proof by contrapositive is essentially a special case of what you're calling proof by contradiction, where the contradiction takes the special form $lnot P$ contradicting with $P.$
I think the reason you might have seen framing contrapositive proofs as proofs by contradiction discouraged is for style reasons. Unless the outstanding assumption of $P$ is used (unnecessarily), the part of the proof outside the inner proof of $lnot Qto lnot P$ is just boilerplate that can be omitted. It is also more informative to call it a proof by contrapositive since that is a special case of contradiction.
(As Derek indicates in the comments, proof by contrapositive is not intuitionistically valid, so it doesn't have anything to do with this.)
answered Dec 26 '18 at 7:51
spaceisdarkgreenspaceisdarkgreen
33.9k21754
$endgroup$
add a comment |
$begingroup$
Yes it is valid... it doesn't really matter if it's something else 'in disguise', just that is it correct. And deriving $lnot P$ from $Plandlnot Q$ is certainly leads to a contradiction that implies $lnot (Pland lnot Q)$ is true, which implies that $Pto Q$ is true. One thing to note (that I think you have noticed based on your second question) is that you have an additional assumption of $P$ open and available for use when you derive $lnot P,$ unlike in the case of just deriving $lnot Qto lnot P$ by assuming $lnot Q$ and deriving $lnot P.$
So the second question amounts to whether it is admissible to assume $P$ in a proof of $lnot Qto lnot P.$ It is, and the easiest way to see this is reasoning semantically and using the completeness/soundness theorem. If $Pvdash lnot Qto lnot P$ then every interpretation in which $P$ is true has $Q$ true, which means precisely the same thing as $vdash Pto Q,$ so we have $vdash lnot Qto lnot P.$
As a result, proof by contrapositive is essentially a special case of what you're calling proof by contradiction, where the contradiction takes the special form $lnot P$ contradicting with $P.$
I think the reason you might have seen framing contrapositive proofs as proofs by contradiction discouraged is for style reasons. Unless the outstanding assumption of $P$ is used (unnecessarily), the part of the proof outside the inner proof of $lnot Qto lnot P$ is just boilerplate that can be omitted. It is also more informative to call it a proof by contrapositive since that is a special case of contradiction.
(As Derek indicates in the comments, proof by contrapositive is not intuitionistically valid, so it doesn't have anything to do with this.)
answered Dec 26 '18 at 7:51
spaceisdarkgreenspaceisdarkgreen
33.9k21754
$endgroup$
add a comment |
$begingroup$
Yes it is valid... it doesn't really matter if it's something else 'in disguise', just that is it correct. And deriving $lnot P$ from $Plandlnot Q$ is certainly leads to a contradiction that implies $lnot (Pland lnot Q)$ is true, which implies that $Pto Q$ is true. One thing to note (that I think you have noticed based on your second question) is that you have an additional assumption of $P$ open and available for use when you derive $lnot P,$ unlike in the case of just deriving $lnot Qto lnot P$ by assuming $lnot Q$ and deriving $lnot P.$
So the second question amounts to whether it is admissible to assume $P$ in a proof of $lnot Qto lnot P.$ It is, and the easiest way to see this is reasoning semantically and using the completeness/soundness theorem. If $Pvdash lnot Qto lnot P$ then every interpretation in which $P$ is true has $Q$ true, which means precisely the same thing as $vdash Pto Q,$ so we have $vdash lnot Qto lnot P.$
As a result, proof by contrapositive is essentially a special case of what you're calling proof by contradiction, where the contradiction takes the special form $lnot P$ contradicting with $P.$
I think the reason you might have seen framing contrapositive proofs as proofs by contradiction discouraged is for style reasons. Unless the outstanding assumption of $P$ is used (unnecessarily), the part of the proof outside the inner proof of $lnot Qto lnot P$ is just boilerplate that can be omitted. It is also more informative to call it a proof by contrapositive since that is a special case of contradiction.
(As Derek indicates in the comments, proof by contrapositive is not intuitionistically valid, so it doesn't have anything to do with this.)
answered Dec 26 '18 at 7:51
spaceisdarkgreenspaceisdarkgreen
33.9k21754
$endgroup$
Yes it is valid... it doesn't really matter if it's something else 'in disguise', just that is it correct. And deriving $lnot P$ from $Plandlnot Q$ is certainly leads to a contradiction that implies $lnot (Pland lnot Q)$ is true, which implies that $Pto Q$ is true. One thing to note (that I think you have noticed based on your second question) is that you have an additional assumption of $P$ open and available for use when you derive $lnot P,$ unlike in the case of just deriving $lnot Qto lnot P$ by assuming $lnot Q$ and deriving $lnot P.$
So the second question amounts to whether it is admissible to assume $P$ in a proof of $lnot Qto lnot P.$ It is, and the easiest way to see this is reasoning semantically and using the completeness/soundness theorem. If $Pvdash lnot Qto lnot P$ then every interpretation in which $P$ is true has $Q$ true, which means precisely the same thing as $vdash Pto Q,$ so we have $vdash lnot Qto lnot P.$
As a result, proof by contrapositive is essentially a special case of what you're calling proof by contradiction, where the contradiction takes the special form $lnot P$ contradicting with $P.$
I think the reason you might have seen framing contrapositive proofs as proofs by contradiction discouraged is for style reasons. Unless the outstanding assumption of $P$ is used (unnecessarily), the part of the proof outside the inner proof of $lnot Qto lnot P$ is just boilerplate that can be omitted. It is also more informative to call it a proof by contrapositive since that is a special case of contradiction.
(As Derek indicates in the comments, proof by contrapositive is not intuitionistically valid, so it doesn't have anything to do with this.)
answered Dec 26 '18 at 7:51
spaceisdarkgreenspaceisdarkgreen
33.9k21754
edited Dec 26 '18 at 9:32
answered Dec 26 '18 at 7:51
spaceisdarkgreenspaceisdarkgreen
33.9k21754
answered Dec 26 '18 at 7:51
spaceisdarkgreenspaceisdarkgreen
33.9k21754
answered Dec 26 '18 at 7:51
spaceisdarkgreenspaceisdarkgreen
33.9k21754
33.9k21754
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3052530%2fcan-any-proof-by-contrapositive-be-rephrased-into-a-proof-by-contradiction%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$
The $(neg Qimpliesneg P)implies(Pimplies Q)$ direction of the equivalence also requires something like double negation elimination assuming you are starting from a reasonably typical constructive logic.
$endgroup$
– Derek Elkins
Dec 26 '18 at 0:25
$begingroup$
If every proof by contrapositive can be rephrased into a proof by contradiction, why do so many mathematicians prefer proof by contrapositive when it can be shown that way?
$endgroup$
– Sei Sakata
Dec 26 '18 at 0:29
2
$begingroup$
@SeiSakata sometimes rephrasing the problem in the contrapositive form makes the proof easier or adds some intuition to the statement. Sometimes it's merely a matter of preference.
$endgroup$
– CyclotomicField
Dec 26 '18 at 0:33
$begingroup$
@spaceisdarkgreen But what we are discussing here is only in one direction. The statement that every proof by contrapositive can be rephrased into a proof by contradiction is seemingly true but the converse doesn't necessarily hold. I am not sure if you were referring to this in your comment" any proof by contradiction “can be rephrased” as a direct proof". BTW I said seemingly true since the line of reasoning that a proof by contrapositive can be rephrased into a proof by contradiction seems to be general enough to account for all cases. But I might be mistaken and not true at all.
$endgroup$
– Sei Sakata
Dec 26 '18 at 1:33
$begingroup$
Sorry, I didn't read your definition of what you're calling a proof by contradiction carefully... you are right that contrapositive is a special case of contradiction here (coincidentally, I wrote an answer about precisely this a couple days ago math.stackexchange.com/questions/3050738/…).
$endgroup$
– spaceisdarkgreen
Dec 26 '18 at 7:40