Mixing
About proofs by contrapositive and proofs by contradiction
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I'm a little confused about the difference between these two types of proof. As I have been taught them, it seems like proofs by contrapositive are just a subset of proofs by contradiction.
Say we want to prove $P implies Q$. Here is how I've been taught to use both proofs:
Contrapositive: We assume $lnot Q$ and from this we try to conclude $lnot P$.
Contradiction: We assume $P$ and $lnot Q$ and from this we try to deduce a contradiction.
My question is, let say we proved $P implies Q$ by contrapositive, so we proved $lnot Q implies lnot P$. Wouldn't this be equivalent to assuming $P$ and $lnot Q$ and then use $lnot Q$ to prove $lnot P$, so we would deduce the contradiction $P land lnot P$?
logic proof-writing proof-theory
edited Aug 6 at 12:08
Taroccoesbrocco
3,60441431
asked Aug 6 at 11:19
Yagger
5441315
add a comment |Â
up vote
2
down vote
favorite
I'm a little confused about the difference between these two types of proof. As I have been taught them, it seems like proofs by contrapositive are just a subset of proofs by contradiction.
Say we want to prove $P implies Q$. Here is how I've been taught to use both proofs:
Contrapositive: We assume $lnot Q$ and from this we try to conclude $lnot P$.
Contradiction: We assume $P$ and $lnot Q$ and from this we try to deduce a contradiction.
My question is, let say we proved $P implies Q$ by contrapositive, so we proved $lnot Q implies lnot P$. Wouldn't this be equivalent to assuming $P$ and $lnot Q$ and then use $lnot Q$ to prove $lnot P$, so we would deduce the contradiction $P land lnot P$?
logic proof-writing proof-theory
edited Aug 6 at 12:08
Taroccoesbrocco
3,60441431
asked Aug 6 at 11:19
Yagger
5441315
They're very similar. When contraposition works, a proof by contradiction feels unneccesarily clunky (you've just added a few lines to the top and bottom for me to read and process with no actual value), while some times a proof by contradiction (or, equivalently, by contraposition and then splitting into the two cases $P$ and $lnot P$) is necessary.
– Arthur
Aug 6 at 11:35
@Arthur sorry for wasting your time sir. Feel free to edit the question so no one else has to process useless information.
– Yagger
Aug 6 at 11:42
1
I'm sorry. That's not what I meant. Your question is fine. I meant that when you make such a proof (i.e. a proof by contradiction which is basically a proof by contraposition with an added assumption of $P$ at the top), there are lines in that proof with no value. Specifically, the lines "assume $P$" at the top of the proof and "Thus $P$ and $lnot P$, which is a contradiction" at the bottom.
– Arthur
Aug 6 at 11:43
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm a little confused about the difference between these two types of proof. As I have been taught them, it seems like proofs by contrapositive are just a subset of proofs by contradiction.
Say we want to prove $P implies Q$. Here is how I've been taught to use both proofs:
Contrapositive: We assume $lnot Q$ and from this we try to conclude $lnot P$.
Contradiction: We assume $P$ and $lnot Q$ and from this we try to deduce a contradiction.
My question is, let say we proved $P implies Q$ by contrapositive, so we proved $lnot Q implies lnot P$. Wouldn't this be equivalent to assuming $P$ and $lnot Q$ and then use $lnot Q$ to prove $lnot P$, so we would deduce the contradiction $P land lnot P$?
logic proof-writing proof-theory
edited Aug 6 at 12:08
Taroccoesbrocco
3,60441431
asked Aug 6 at 11:19
Yagger
5441315
I'm a little confused about the difference between these two types of proof. As I have been taught them, it seems like proofs by contrapositive are just a subset of proofs by contradiction.
Say we want to prove $P implies Q$. Here is how I've been taught to use both proofs:
Contrapositive: We assume $lnot Q$ and from this we try to conclude $lnot P$.
Contradiction: We assume $P$ and $lnot Q$ and from this we try to deduce a contradiction.
My question is, let say we proved $P implies Q$ by contrapositive, so we proved $lnot Q implies lnot P$. Wouldn't this be equivalent to assuming $P$ and $lnot Q$ and then use $lnot Q$ to prove $lnot P$, so we would deduce the contradiction $P land lnot P$?
logic proof-writing proof-theory
edited Aug 6 at 12:08
Taroccoesbrocco
3,60441431
asked Aug 6 at 11:19
Yagger
5441315
edited Aug 6 at 12:08
Taroccoesbrocco
3,60441431
edited Aug 6 at 12:08
Taroccoesbrocco
3,60441431
edited Aug 6 at 12:08
Taroccoesbrocco
3,60441431
3,60441431
asked Aug 6 at 11:19
Yagger
5441315
asked Aug 6 at 11:19
Yagger
5441315
asked Aug 6 at 11:19
Yagger
5441315
5441315
They're very similar. When contraposition works, a proof by contradiction feels unneccesarily clunky (you've just added a few lines to the top and bottom for me to read and process with no actual value), while some times a proof by contradiction (or, equivalently, by contraposition and then splitting into the two cases $P$ and $lnot P$) is necessary.
– Arthur
Aug 6 at 11:35
@Arthur sorry for wasting your time sir. Feel free to edit the question so no one else has to process useless information.
– Yagger
Aug 6 at 11:42
1
I'm sorry. That's not what I meant. Your question is fine. I meant that when you make such a proof (i.e. a proof by contradiction which is basically a proof by contraposition with an added assumption of $P$ at the top), there are lines in that proof with no value. Specifically, the lines "assume $P$" at the top of the proof and "Thus $P$ and $lnot P$, which is a contradiction" at the bottom.
– Arthur
Aug 6 at 11:43
add a comment |Â
They're very similar. When contraposition works, a proof by contradiction feels unneccesarily clunky (you've just added a few lines to the top and bottom for me to read and process with no actual value), while some times a proof by contradiction (or, equivalently, by contraposition and then splitting into the two cases $P$ and $lnot P$) is necessary.
– Arthur
Aug 6 at 11:35
@Arthur sorry for wasting your time sir. Feel free to edit the question so no one else has to process useless information.
– Yagger
Aug 6 at 11:42
1
I'm sorry. That's not what I meant. Your question is fine. I meant that when you make such a proof (i.e. a proof by contradiction which is basically a proof by contraposition with an added assumption of $P$ at the top), there are lines in that proof with no value. Specifically, the lines "assume $P$" at the top of the proof and "Thus $P$ and $lnot P$, which is a contradiction" at the bottom.
– Arthur
Aug 6 at 11:43
They're very similar. When contraposition works, a proof by contradiction feels unneccesarily clunky (you've just added a few lines to the top and bottom for me to read and process with no actual value), while some times a proof by contradiction (or, equivalently, by contraposition and then splitting into the two cases $P$ and $lnot P$) is necessary.
– Arthur
Aug 6 at 11:35
They're very similar. When contraposition works, a proof by contradiction feels unneccesarily clunky (you've just added a few lines to the top and bottom for me to read and process with no actual value), while some times a proof by contradiction (or, equivalently, by contraposition and then splitting into the two cases $P$ and $lnot P$) is necessary.
– Arthur
Aug 6 at 11:35
@Arthur sorry for wasting your time sir. Feel free to edit the question so no one else has to process useless information.
– Yagger
Aug 6 at 11:42
@Arthur sorry for wasting your time sir. Feel free to edit the question so no one else has to process useless information.
– Yagger
Aug 6 at 11:42
1
1
I'm sorry. That's not what I meant. Your question is fine. I meant that when you make such a proof (i.e. a proof by contradiction which is basically a proof by contraposition with an added assumption of $P$ at the top), there are lines in that proof with no value. Specifically, the lines "assume $P$" at the top of the proof and "Thus $P$ and $lnot P$, which is a contradiction" at the bottom.
– Arthur
Aug 6 at 11:43
I'm sorry. That's not what I meant. Your question is fine. I meant that when you make such a proof (i.e. a proof by contradiction which is basically a proof by contraposition with an added assumption of $P$ at the top), there are lines in that proof with no value. Specifically, the lines "assume $P$" at the top of the proof and "Thus $P$ and $lnot P$, which is a contradiction" at the bottom.
– Arthur
Aug 6 at 11:43
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
The two approaches are not equivalent, even if they are quite similar and related. More precisely, proofs by contrapositive are a proper subset of proofs by contradiction.
Every proof by contraposition can be reformulated as a proof by contradiction, as you correctly noticed. Indeed, suppose you have a proof $pi$ of $lnot Q implies lnot P$; then you can prove $P implies Q$ by contradiction, by assuming $P$ and $lnot Q$, which yields a proof of $lnot P$ (via modus ponens between the assumption $lnot Q$ and the conclusion $lnot Q implies lnot P$ of $pi$) and then you get the contradiction $P land lnot P$.
But not every proof by contradiction can be reformulated as a proof by contraposition, as well explained in the accepted answer of this question. Indeed, proofs by contradiction are "more general" (i.e. they can be applied to a wider set of propositions to prove) because you can stop when you find any contradiction, not only a contradiction directly involving the hypotheses. More precisely, in a proof by contradiction of $P implies Q$, we assume $P$ and $lnot Q$ and we deduce a contradiction $R land lnot R$; in the particular case where $R = P$ then (usually) you can reformulate your proof as a proof by contraposition, otherwise you cannot.
Remark. Both proofs by contraposition and proofs by contradiction are valid in classical logic, but in general they are not valid in intuitionistic logic (roughly speaking, a constructive logic that does not admit the excluded middle law). For a more detailed analysis of the validity of these kinds of proofs, see for instance here.
answered Aug 6 at 11:36
Taroccoesbrocco
3,60441431
oh, that's an eye opener, thanks!
– Alvin Lepik
Aug 6 at 11:39
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
The two approaches are not equivalent, even if they are quite similar and related. More precisely, proofs by contrapositive are a proper subset of proofs by contradiction.
Every proof by contraposition can be reformulated as a proof by contradiction, as you correctly noticed. Indeed, suppose you have a proof $pi$ of $lnot Q implies lnot P$; then you can prove $P implies Q$ by contradiction, by assuming $P$ and $lnot Q$, which yields a proof of $lnot P$ (via modus ponens between the assumption $lnot Q$ and the conclusion $lnot Q implies lnot P$ of $pi$) and then you get the contradiction $P land lnot P$.
But not every proof by contradiction can be reformulated as a proof by contraposition, as well explained in the accepted answer of this question. Indeed, proofs by contradiction are "more general" (i.e. they can be applied to a wider set of propositions to prove) because you can stop when you find any contradiction, not only a contradiction directly involving the hypotheses. More precisely, in a proof by contradiction of $P implies Q$, we assume $P$ and $lnot Q$ and we deduce a contradiction $R land lnot R$; in the particular case where $R = P$ then (usually) you can reformulate your proof as a proof by contraposition, otherwise you cannot.
Remark. Both proofs by contraposition and proofs by contradiction are valid in classical logic, but in general they are not valid in intuitionistic logic (roughly speaking, a constructive logic that does not admit the excluded middle law). For a more detailed analysis of the validity of these kinds of proofs, see for instance here.
answered Aug 6 at 11:36
Taroccoesbrocco
3,60441431
oh, that's an eye opener, thanks!
– Alvin Lepik
Aug 6 at 11:39
add a comment |Â
up vote
6
down vote
accepted
The two approaches are not equivalent, even if they are quite similar and related. More precisely, proofs by contrapositive are a proper subset of proofs by contradiction.
Every proof by contraposition can be reformulated as a proof by contradiction, as you correctly noticed. Indeed, suppose you have a proof $pi$ of $lnot Q implies lnot P$; then you can prove $P implies Q$ by contradiction, by assuming $P$ and $lnot Q$, which yields a proof of $lnot P$ (via modus ponens between the assumption $lnot Q$ and the conclusion $lnot Q implies lnot P$ of $pi$) and then you get the contradiction $P land lnot P$.
But not every proof by contradiction can be reformulated as a proof by contraposition, as well explained in the accepted answer of this question. Indeed, proofs by contradiction are "more general" (i.e. they can be applied to a wider set of propositions to prove) because you can stop when you find any contradiction, not only a contradiction directly involving the hypotheses. More precisely, in a proof by contradiction of $P implies Q$, we assume $P$ and $lnot Q$ and we deduce a contradiction $R land lnot R$; in the particular case where $R = P$ then (usually) you can reformulate your proof as a proof by contraposition, otherwise you cannot.
Remark. Both proofs by contraposition and proofs by contradiction are valid in classical logic, but in general they are not valid in intuitionistic logic (roughly speaking, a constructive logic that does not admit the excluded middle law). For a more detailed analysis of the validity of these kinds of proofs, see for instance here.
answered Aug 6 at 11:36
Taroccoesbrocco
3,60441431
oh, that's an eye opener, thanks!
– Alvin Lepik
Aug 6 at 11:39
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
The two approaches are not equivalent, even if they are quite similar and related. More precisely, proofs by contrapositive are a proper subset of proofs by contradiction.
Every proof by contraposition can be reformulated as a proof by contradiction, as you correctly noticed. Indeed, suppose you have a proof $pi$ of $lnot Q implies lnot P$; then you can prove $P implies Q$ by contradiction, by assuming $P$ and $lnot Q$, which yields a proof of $lnot P$ (via modus ponens between the assumption $lnot Q$ and the conclusion $lnot Q implies lnot P$ of $pi$) and then you get the contradiction $P land lnot P$.
But not every proof by contradiction can be reformulated as a proof by contraposition, as well explained in the accepted answer of this question. Indeed, proofs by contradiction are "more general" (i.e. they can be applied to a wider set of propositions to prove) because you can stop when you find any contradiction, not only a contradiction directly involving the hypotheses. More precisely, in a proof by contradiction of $P implies Q$, we assume $P$ and $lnot Q$ and we deduce a contradiction $R land lnot R$; in the particular case where $R = P$ then (usually) you can reformulate your proof as a proof by contraposition, otherwise you cannot.
Remark. Both proofs by contraposition and proofs by contradiction are valid in classical logic, but in general they are not valid in intuitionistic logic (roughly speaking, a constructive logic that does not admit the excluded middle law). For a more detailed analysis of the validity of these kinds of proofs, see for instance here.
answered Aug 6 at 11:36
Taroccoesbrocco
3,60441431
The two approaches are not equivalent, even if they are quite similar and related. More precisely, proofs by contrapositive are a proper subset of proofs by contradiction.
Every proof by contraposition can be reformulated as a proof by contradiction, as you correctly noticed. Indeed, suppose you have a proof $pi$ of $lnot Q implies lnot P$; then you can prove $P implies Q$ by contradiction, by assuming $P$ and $lnot Q$, which yields a proof of $lnot P$ (via modus ponens between the assumption $lnot Q$ and the conclusion $lnot Q implies lnot P$ of $pi$) and then you get the contradiction $P land lnot P$.
But not every proof by contradiction can be reformulated as a proof by contraposition, as well explained in the accepted answer of this question. Indeed, proofs by contradiction are "more general" (i.e. they can be applied to a wider set of propositions to prove) because you can stop when you find any contradiction, not only a contradiction directly involving the hypotheses. More precisely, in a proof by contradiction of $P implies Q$, we assume $P$ and $lnot Q$ and we deduce a contradiction $R land lnot R$; in the particular case where $R = P$ then (usually) you can reformulate your proof as a proof by contraposition, otherwise you cannot.
Remark. Both proofs by contraposition and proofs by contradiction are valid in classical logic, but in general they are not valid in intuitionistic logic (roughly speaking, a constructive logic that does not admit the excluded middle law). For a more detailed analysis of the validity of these kinds of proofs, see for instance here.
answered Aug 6 at 11:36
Taroccoesbrocco
3,60441431
edited Aug 6 at 12:30
answered Aug 6 at 11:36
Taroccoesbrocco
3,60441431
answered Aug 6 at 11:36
Taroccoesbrocco
3,60441431
answered Aug 6 at 11:36
Taroccoesbrocco
3,60441431
3,60441431
oh, that's an eye opener, thanks!
– Alvin Lepik
Aug 6 at 11:39
add a comment |Â
oh, that's an eye opener, thanks!
– Alvin Lepik
Aug 6 at 11:39
oh, that's an eye opener, thanks!
– Alvin Lepik
Aug 6 at 11:39
oh, that's an eye opener, thanks!
– Alvin Lepik
Aug 6 at 11:39
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873785%2fabout-proofs-by-contrapositive-and-proofs-by-contradiction%23new-answer', 'question_page');
);
Post as a guest
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
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
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
They're very similar. When contraposition works, a proof by contradiction feels unneccesarily clunky (you've just added a few lines to the top and bottom for me to read and process with no actual value), while some times a proof by contradiction (or, equivalently, by contraposition and then splitting into the two cases $P$ and $lnot P$) is necessary.
– Arthur
Aug 6 at 11:35
@Arthur sorry for wasting your time sir. Feel free to edit the question so no one else has to process useless information.
– Yagger
Aug 6 at 11:42
1
I'm sorry. That's not what I meant. Your question is fine. I meant that when you make such a proof (i.e. a proof by contradiction which is basically a proof by contraposition with an added assumption of $P$ at the top), there are lines in that proof with no value. Specifically, the lines "assume $P$" at the top of the proof and "Thus $P$ and $lnot P$, which is a contradiction" at the bottom.
– Arthur
Aug 6 at 11:43