Mixing
How to prove A→B is equivalent to ¬B→¬A? [duplicate]
$begingroup$
This question already has an answer here:
$(A implies B) implies (neg B implies neg A)$?
5 answers
A→B is equivalent to ¬B→¬A This comes from a member called 6005 as an answer to my question: Why $F rightarrow T implies neg F rightarrow neg T implies T rightarrow F$ is wrong?
Any proof or reference for this rule ?
discrete-mathematics logic
asked Jan 11 at 19:28
FriendlyFullStackFriendlyFullStack
62
$endgroup$
marked as duplicate by Mauro ALLEGRANZA logic
Users with the logic badge can single-handedly close logic questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 11 at 20:29
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
$(A implies B) implies (neg B implies neg A)$?
5 answers
A→B is equivalent to ¬B→¬A This comes from a member called 6005 as an answer to my question: Why $F rightarrow T implies neg F rightarrow neg T implies T rightarrow F$ is wrong?
Any proof or reference for this rule ?
discrete-mathematics logic
asked Jan 11 at 19:28
FriendlyFullStackFriendlyFullStack
62
$endgroup$
marked as duplicate by Mauro ALLEGRANZA logic
Users with the logic badge can single-handedly close logic questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 11 at 20:29
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
$begingroup$
This is highly dependant on your system of axioms and the method of proving.
$endgroup$
– ajotatxe
Jan 11 at 19:30
$begingroup$
This comes from member called: "6005" as an answer to my question math.stackexchange.com/q/3070216/633862
$endgroup$
– FriendlyFullStack
Jan 11 at 19:32
$begingroup$
This is called contraposition.
$endgroup$
– Clive Newstead
Jan 11 at 19:33
add a comment |
$begingroup$
This question already has an answer here:
$(A implies B) implies (neg B implies neg A)$?
5 answers
A→B is equivalent to ¬B→¬A This comes from a member called 6005 as an answer to my question: Why $F rightarrow T implies neg F rightarrow neg T implies T rightarrow F$ is wrong?
Any proof or reference for this rule ?
discrete-mathematics logic
asked Jan 11 at 19:28
FriendlyFullStackFriendlyFullStack
62
$endgroup$
This question already has an answer here:
$(A implies B) implies (neg B implies neg A)$?
5 answers
A→B is equivalent to ¬B→¬A This comes from a member called 6005 as an answer to my question: Why $F rightarrow T implies neg F rightarrow neg T implies T rightarrow F$ is wrong?
Any proof or reference for this rule ?
This question already has an answer here:
$(A implies B) implies (neg B implies neg A)$?
5 answers
discrete-mathematics logic
discrete-mathematics logic
asked Jan 11 at 19:28
FriendlyFullStackFriendlyFullStack
62
asked Jan 11 at 19:28
FriendlyFullStackFriendlyFullStack
62
edited Jan 11 at 19:33
FriendlyFullStack
asked Jan 11 at 19:28
FriendlyFullStackFriendlyFullStack
62
asked Jan 11 at 19:28
FriendlyFullStackFriendlyFullStack
62
asked Jan 11 at 19:28
FriendlyFullStackFriendlyFullStack
62
62
marked as duplicate by Mauro ALLEGRANZA logic
Users with the logic badge can single-handedly close logic questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 11 at 20:29
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Mauro ALLEGRANZA logic
Users with the logic badge can single-handedly close logic questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 11 at 20:29
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
$begingroup$
This is highly dependant on your system of axioms and the method of proving.
$endgroup$
– ajotatxe
Jan 11 at 19:30
$begingroup$
This comes from member called: "6005" as an answer to my question math.stackexchange.com/q/3070216/633862
$endgroup$
– FriendlyFullStack
Jan 11 at 19:32
$begingroup$
This is called contraposition.
$endgroup$
– Clive Newstead
Jan 11 at 19:33
add a comment |
2
$begingroup$
This is highly dependant on your system of axioms and the method of proving.
$endgroup$
– ajotatxe
Jan 11 at 19:30
$begingroup$
This comes from member called: "6005" as an answer to my question math.stackexchange.com/q/3070216/633862
$endgroup$
– FriendlyFullStack
Jan 11 at 19:32
$begingroup$
This is called contraposition.
$endgroup$
– Clive Newstead
Jan 11 at 19:33
2
2
$begingroup$
This is highly dependant on your system of axioms and the method of proving.
$endgroup$
– ajotatxe
Jan 11 at 19:30
$begingroup$
This is highly dependant on your system of axioms and the method of proving.
$endgroup$
– ajotatxe
Jan 11 at 19:30
$begingroup$
This comes from member called: "6005" as an answer to my question math.stackexchange.com/q/3070216/633862
$endgroup$
– FriendlyFullStack
Jan 11 at 19:32
$begingroup$
This comes from member called: "6005" as an answer to my question math.stackexchange.com/q/3070216/633862
$endgroup$
– FriendlyFullStack
Jan 11 at 19:32
$begingroup$
This is called contraposition.
$endgroup$
– Clive Newstead
Jan 11 at 19:33
$begingroup$
This is called contraposition.
$endgroup$
– Clive Newstead
Jan 11 at 19:33
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
I believe you could simply check the truth table.
You have $4$ options:
$A,B$ are true. In this case $Arightarrow B$ is true because true implies true is true. and $lnot B rightarrow lnot A$ is true because $lnot B$ is false.
$A,B$ are false. Then $lnot A ,lnot B$ are true so the same argument as above works.
$A$ is true but $B$ is false. so $Arightarrow B$ is false (as true implies false is false). Moreover $lnot B rightarrow lnot A$ is also false because $lnot B$ is true and $lnot A$ is false.
$A$ is false and $B$ is true. Then $Arightarrow B$ is true because $A$ is false and $lnot Brightarrow lnot A$ is true because $lnot B$ is false.
answered Jan 11 at 19:33
YankoYanko
6,7241529
$endgroup$
add a comment |
$begingroup$
Basic argument from first principles is like this. Assume $A implies B$, and $B$ is not true. If $A$ is true, then $A implies B$ so $B$ is true, which contradicts $B$ is not true. Hence, $A$ must be false.
In other words, $(Aimplies B) implies (lnot B implies lnot A).$
The other way is just a negation in the above identity.
edited Jan 11 at 19:34
Yanko
6,7241529
answered Jan 11 at 19:33
gt6989bgt6989b
34k22455
$endgroup$
1
$begingroup$
I changed your $not$ with $lnot$. I would +1 but I reached the limit for today :(
$endgroup$
– Yanko
Jan 11 at 19:34
$begingroup$
@Yanko did not know there is a limit for those
$endgroup$
– gt6989b
Jan 11 at 19:36
$begingroup$
There's a daily limit, whenever I try to vote it says "Daily vote limit reached; vote again in 4 hours". I did vote quit a lot today. I'll just need to remember to up vote tommorow.
$endgroup$
– Yanko
Jan 11 at 19:43
$begingroup$
@Yanko thank you for making the site better, I really appreciate it. It is a blessing to have people like you who put in a lot of energy and effort into helping others and helping others help others :)
$endgroup$
– gt6989b
Jan 11 at 20:05
add a comment |
$begingroup$
The implication $neg B Rightarrow neg A$ is called the contrapositive of $A Rightarrow B$.
The fact that $A Rightarrow B$ entails $neg B Rightarrow neg A$ is valid even in constructive logic: suppose $A Rightarrow B$ is true, and assume $neg B$. If $A$ were true, then $B$ would be true by modus ponens (implication elimination), and so we obtain the contradiction $B wedge neg B$. Thus $neg A$ is true. Hence $neg B Rightarrow neg A$ is true by implication introduction.
The fact that $neg B Rightarrow neg A$ entails $A Rightarrow B$ relies on double negation elimination: suppose $neg B Rightarrow neg A$ is true, and assume $A$. If $neg B$ were true, then $neg A$ would be true by modus ponens, so we obtain the contradiction $A wedge neg A$. Thus $neg neg B$ is true, so that $B$ is true by double negation elimination. Hence $A Rightarrow B$ is true by implication introduction.
Since $A Rightarrow B$ entails and is entailed by $neg B Rightarrow neg A$, they are logically equivalent.
Of course, you could just check a truth table, but that would be boring :)
answered Jan 11 at 19:37
Clive NewsteadClive Newstead
51.6k474135
$endgroup$
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I believe you could simply check the truth table.
You have $4$ options:
$A,B$ are true. In this case $Arightarrow B$ is true because true implies true is true. and $lnot B rightarrow lnot A$ is true because $lnot B$ is false.
$A,B$ are false. Then $lnot A ,lnot B$ are true so the same argument as above works.
$A$ is true but $B$ is false. so $Arightarrow B$ is false (as true implies false is false). Moreover $lnot B rightarrow lnot A$ is also false because $lnot B$ is true and $lnot A$ is false.
$A$ is false and $B$ is true. Then $Arightarrow B$ is true because $A$ is false and $lnot Brightarrow lnot A$ is true because $lnot B$ is false.
answered Jan 11 at 19:33
YankoYanko
6,7241529
$endgroup$
add a comment |
$begingroup$
I believe you could simply check the truth table.
You have $4$ options:
$A,B$ are true. In this case $Arightarrow B$ is true because true implies true is true. and $lnot B rightarrow lnot A$ is true because $lnot B$ is false.
$A,B$ are false. Then $lnot A ,lnot B$ are true so the same argument as above works.
$A$ is true but $B$ is false. so $Arightarrow B$ is false (as true implies false is false). Moreover $lnot B rightarrow lnot A$ is also false because $lnot B$ is true and $lnot A$ is false.
$A$ is false and $B$ is true. Then $Arightarrow B$ is true because $A$ is false and $lnot Brightarrow lnot A$ is true because $lnot B$ is false.
answered Jan 11 at 19:33
YankoYanko
6,7241529
$endgroup$
add a comment |
$begingroup$
I believe you could simply check the truth table.
You have $4$ options:
$A,B$ are true. In this case $Arightarrow B$ is true because true implies true is true. and $lnot B rightarrow lnot A$ is true because $lnot B$ is false.
$A,B$ are false. Then $lnot A ,lnot B$ are true so the same argument as above works.
$A$ is true but $B$ is false. so $Arightarrow B$ is false (as true implies false is false). Moreover $lnot B rightarrow lnot A$ is also false because $lnot B$ is true and $lnot A$ is false.
$A$ is false and $B$ is true. Then $Arightarrow B$ is true because $A$ is false and $lnot Brightarrow lnot A$ is true because $lnot B$ is false.
answered Jan 11 at 19:33
YankoYanko
6,7241529
$endgroup$
I believe you could simply check the truth table.
You have $4$ options:
$A,B$ are true. In this case $Arightarrow B$ is true because true implies true is true. and $lnot B rightarrow lnot A$ is true because $lnot B$ is false.
$A,B$ are false. Then $lnot A ,lnot B$ are true so the same argument as above works.
$A$ is true but $B$ is false. so $Arightarrow B$ is false (as true implies false is false). Moreover $lnot B rightarrow lnot A$ is also false because $lnot B$ is true and $lnot A$ is false.
$A$ is false and $B$ is true. Then $Arightarrow B$ is true because $A$ is false and $lnot Brightarrow lnot A$ is true because $lnot B$ is false.
answered Jan 11 at 19:33
YankoYanko
6,7241529
answered Jan 11 at 19:33
YankoYanko
6,7241529
answered Jan 11 at 19:33
YankoYanko
6,7241529
answered Jan 11 at 19:33
YankoYanko
6,7241529
6,7241529
add a comment |
add a comment |
$begingroup$
Basic argument from first principles is like this. Assume $A implies B$, and $B$ is not true. If $A$ is true, then $A implies B$ so $B$ is true, which contradicts $B$ is not true. Hence, $A$ must be false.
In other words, $(Aimplies B) implies (lnot B implies lnot A).$
The other way is just a negation in the above identity.
edited Jan 11 at 19:34
Yanko
6,7241529
answered Jan 11 at 19:33
gt6989bgt6989b
34k22455
$endgroup$
1
$begingroup$
I changed your $not$ with $lnot$. I would +1 but I reached the limit for today :(
$endgroup$
– Yanko
Jan 11 at 19:34
$begingroup$
@Yanko did not know there is a limit for those
$endgroup$
– gt6989b
Jan 11 at 19:36
$begingroup$
There's a daily limit, whenever I try to vote it says "Daily vote limit reached; vote again in 4 hours". I did vote quit a lot today. I'll just need to remember to up vote tommorow.
$endgroup$
– Yanko
Jan 11 at 19:43
$begingroup$
@Yanko thank you for making the site better, I really appreciate it. It is a blessing to have people like you who put in a lot of energy and effort into helping others and helping others help others :)
$endgroup$
– gt6989b
Jan 11 at 20:05
add a comment |
$begingroup$
Basic argument from first principles is like this. Assume $A implies B$, and $B$ is not true. If $A$ is true, then $A implies B$ so $B$ is true, which contradicts $B$ is not true. Hence, $A$ must be false.
In other words, $(Aimplies B) implies (lnot B implies lnot A).$
The other way is just a negation in the above identity.
edited Jan 11 at 19:34
Yanko
6,7241529
answered Jan 11 at 19:33
gt6989bgt6989b
34k22455
$endgroup$
1
$begingroup$
I changed your $not$ with $lnot$. I would +1 but I reached the limit for today :(
$endgroup$
– Yanko
Jan 11 at 19:34
$begingroup$
@Yanko did not know there is a limit for those
$endgroup$
– gt6989b
Jan 11 at 19:36
$begingroup$
There's a daily limit, whenever I try to vote it says "Daily vote limit reached; vote again in 4 hours". I did vote quit a lot today. I'll just need to remember to up vote tommorow.
$endgroup$
– Yanko
Jan 11 at 19:43
$begingroup$
@Yanko thank you for making the site better, I really appreciate it. It is a blessing to have people like you who put in a lot of energy and effort into helping others and helping others help others :)
$endgroup$
– gt6989b
Jan 11 at 20:05
add a comment |
$begingroup$
Basic argument from first principles is like this. Assume $A implies B$, and $B$ is not true. If $A$ is true, then $A implies B$ so $B$ is true, which contradicts $B$ is not true. Hence, $A$ must be false.
In other words, $(Aimplies B) implies (lnot B implies lnot A).$
The other way is just a negation in the above identity.
edited Jan 11 at 19:34
Yanko
6,7241529
answered Jan 11 at 19:33
gt6989bgt6989b
34k22455
$endgroup$
Basic argument from first principles is like this. Assume $A implies B$, and $B$ is not true. If $A$ is true, then $A implies B$ so $B$ is true, which contradicts $B$ is not true. Hence, $A$ must be false.
In other words, $(Aimplies B) implies (lnot B implies lnot A).$
The other way is just a negation in the above identity.
edited Jan 11 at 19:34
Yanko
6,7241529
answered Jan 11 at 19:33
gt6989bgt6989b
34k22455
edited Jan 11 at 19:34
Yanko
6,7241529
edited Jan 11 at 19:34
Yanko
6,7241529
edited Jan 11 at 19:34
Yanko
6,7241529
6,7241529
answered Jan 11 at 19:33
gt6989bgt6989b
34k22455
answered Jan 11 at 19:33
gt6989bgt6989b
34k22455
answered Jan 11 at 19:33
gt6989bgt6989b
34k22455
34k22455
1
$begingroup$
I changed your $not$ with $lnot$. I would +1 but I reached the limit for today :(
$endgroup$
– Yanko
Jan 11 at 19:34
$begingroup$
@Yanko did not know there is a limit for those
$endgroup$
– gt6989b
Jan 11 at 19:36
$begingroup$
There's a daily limit, whenever I try to vote it says "Daily vote limit reached; vote again in 4 hours". I did vote quit a lot today. I'll just need to remember to up vote tommorow.
$endgroup$
– Yanko
Jan 11 at 19:43
$begingroup$
@Yanko thank you for making the site better, I really appreciate it. It is a blessing to have people like you who put in a lot of energy and effort into helping others and helping others help others :)
$endgroup$
– gt6989b
Jan 11 at 20:05
add a comment |
1
$begingroup$
I changed your $not$ with $lnot$. I would +1 but I reached the limit for today :(
$endgroup$
– Yanko
Jan 11 at 19:34
$begingroup$
@Yanko did not know there is a limit for those
$endgroup$
– gt6989b
Jan 11 at 19:36
$begingroup$
There's a daily limit, whenever I try to vote it says "Daily vote limit reached; vote again in 4 hours". I did vote quit a lot today. I'll just need to remember to up vote tommorow.
$endgroup$
– Yanko
Jan 11 at 19:43
$begingroup$
@Yanko thank you for making the site better, I really appreciate it. It is a blessing to have people like you who put in a lot of energy and effort into helping others and helping others help others :)
$endgroup$
– gt6989b
Jan 11 at 20:05
1
1
$begingroup$
I changed your $not$ with $lnot$. I would +1 but I reached the limit for today :(
$endgroup$
– Yanko
Jan 11 at 19:34
$begingroup$
I changed your $not$ with $lnot$. I would +1 but I reached the limit for today :(
$endgroup$
– Yanko
Jan 11 at 19:34
$begingroup$
@Yanko did not know there is a limit for those
$endgroup$
– gt6989b
Jan 11 at 19:36
$begingroup$
@Yanko did not know there is a limit for those
$endgroup$
– gt6989b
Jan 11 at 19:36
$begingroup$
There's a daily limit, whenever I try to vote it says "Daily vote limit reached; vote again in 4 hours". I did vote quit a lot today. I'll just need to remember to up vote tommorow.
$endgroup$
– Yanko
Jan 11 at 19:43
$begingroup$
There's a daily limit, whenever I try to vote it says "Daily vote limit reached; vote again in 4 hours". I did vote quit a lot today. I'll just need to remember to up vote tommorow.
$endgroup$
– Yanko
Jan 11 at 19:43
$begingroup$
@Yanko thank you for making the site better, I really appreciate it. It is a blessing to have people like you who put in a lot of energy and effort into helping others and helping others help others :)
$endgroup$
– gt6989b
Jan 11 at 20:05
$begingroup$
@Yanko thank you for making the site better, I really appreciate it. It is a blessing to have people like you who put in a lot of energy and effort into helping others and helping others help others :)
$endgroup$
– gt6989b
Jan 11 at 20:05
add a comment |
$begingroup$
The implication $neg B Rightarrow neg A$ is called the contrapositive of $A Rightarrow B$.
The fact that $A Rightarrow B$ entails $neg B Rightarrow neg A$ is valid even in constructive logic: suppose $A Rightarrow B$ is true, and assume $neg B$. If $A$ were true, then $B$ would be true by modus ponens (implication elimination), and so we obtain the contradiction $B wedge neg B$. Thus $neg A$ is true. Hence $neg B Rightarrow neg A$ is true by implication introduction.
The fact that $neg B Rightarrow neg A$ entails $A Rightarrow B$ relies on double negation elimination: suppose $neg B Rightarrow neg A$ is true, and assume $A$. If $neg B$ were true, then $neg A$ would be true by modus ponens, so we obtain the contradiction $A wedge neg A$. Thus $neg neg B$ is true, so that $B$ is true by double negation elimination. Hence $A Rightarrow B$ is true by implication introduction.
Since $A Rightarrow B$ entails and is entailed by $neg B Rightarrow neg A$, they are logically equivalent.
Of course, you could just check a truth table, but that would be boring :)
answered Jan 11 at 19:37
Clive NewsteadClive Newstead
51.6k474135
$endgroup$
add a comment |
$begingroup$
The implication $neg B Rightarrow neg A$ is called the contrapositive of $A Rightarrow B$.
The fact that $A Rightarrow B$ entails $neg B Rightarrow neg A$ is valid even in constructive logic: suppose $A Rightarrow B$ is true, and assume $neg B$. If $A$ were true, then $B$ would be true by modus ponens (implication elimination), and so we obtain the contradiction $B wedge neg B$. Thus $neg A$ is true. Hence $neg B Rightarrow neg A$ is true by implication introduction.
The fact that $neg B Rightarrow neg A$ entails $A Rightarrow B$ relies on double negation elimination: suppose $neg B Rightarrow neg A$ is true, and assume $A$. If $neg B$ were true, then $neg A$ would be true by modus ponens, so we obtain the contradiction $A wedge neg A$. Thus $neg neg B$ is true, so that $B$ is true by double negation elimination. Hence $A Rightarrow B$ is true by implication introduction.
Since $A Rightarrow B$ entails and is entailed by $neg B Rightarrow neg A$, they are logically equivalent.
Of course, you could just check a truth table, but that would be boring :)
answered Jan 11 at 19:37
Clive NewsteadClive Newstead
51.6k474135
$endgroup$
add a comment |
$begingroup$
The implication $neg B Rightarrow neg A$ is called the contrapositive of $A Rightarrow B$.
The fact that $A Rightarrow B$ entails $neg B Rightarrow neg A$ is valid even in constructive logic: suppose $A Rightarrow B$ is true, and assume $neg B$. If $A$ were true, then $B$ would be true by modus ponens (implication elimination), and so we obtain the contradiction $B wedge neg B$. Thus $neg A$ is true. Hence $neg B Rightarrow neg A$ is true by implication introduction.
The fact that $neg B Rightarrow neg A$ entails $A Rightarrow B$ relies on double negation elimination: suppose $neg B Rightarrow neg A$ is true, and assume $A$. If $neg B$ were true, then $neg A$ would be true by modus ponens, so we obtain the contradiction $A wedge neg A$. Thus $neg neg B$ is true, so that $B$ is true by double negation elimination. Hence $A Rightarrow B$ is true by implication introduction.
Since $A Rightarrow B$ entails and is entailed by $neg B Rightarrow neg A$, they are logically equivalent.
Of course, you could just check a truth table, but that would be boring :)
answered Jan 11 at 19:37
Clive NewsteadClive Newstead
51.6k474135
$endgroup$
The implication $neg B Rightarrow neg A$ is called the contrapositive of $A Rightarrow B$.
The fact that $A Rightarrow B$ entails $neg B Rightarrow neg A$ is valid even in constructive logic: suppose $A Rightarrow B$ is true, and assume $neg B$. If $A$ were true, then $B$ would be true by modus ponens (implication elimination), and so we obtain the contradiction $B wedge neg B$. Thus $neg A$ is true. Hence $neg B Rightarrow neg A$ is true by implication introduction.
The fact that $neg B Rightarrow neg A$ entails $A Rightarrow B$ relies on double negation elimination: suppose $neg B Rightarrow neg A$ is true, and assume $A$. If $neg B$ were true, then $neg A$ would be true by modus ponens, so we obtain the contradiction $A wedge neg A$. Thus $neg neg B$ is true, so that $B$ is true by double negation elimination. Hence $A Rightarrow B$ is true by implication introduction.
Since $A Rightarrow B$ entails and is entailed by $neg B Rightarrow neg A$, they are logically equivalent.
Of course, you could just check a truth table, but that would be boring :)
answered Jan 11 at 19:37
Clive NewsteadClive Newstead
51.6k474135
answered Jan 11 at 19:37
Clive NewsteadClive Newstead
51.6k474135
answered Jan 11 at 19:37
Clive NewsteadClive Newstead
51.6k474135
answered Jan 11 at 19:37
Clive NewsteadClive Newstead
51.6k474135
51.6k474135
add a comment |
add a comment |
2
$begingroup$
This is highly dependant on your system of axioms and the method of proving.
$endgroup$
– ajotatxe
Jan 11 at 19:30
$begingroup$
This comes from member called: "6005" as an answer to my question math.stackexchange.com/q/3070216/633862
$endgroup$
– FriendlyFullStack
Jan 11 at 19:32
$begingroup$
This is called contraposition.
$endgroup$
– Clive Newstead
Jan 11 at 19:33