How to Understand proof by contradiction. [duplicate]
$begingroup$
This question already has an answer here:
Why, logically, is proof by contradiction valid?
4 answers
What is the meaning of this following passage?
"An indirect proof always begins by negating what it is we would like to prove. The argument then proceeds until (hopefully) a logical contradiction with some other accepted fact is uncovered. Many times this accepted fact is part of the hypothesis of the theorem. When the contradiction is with the theorems hypothesis, we technically have what is called a contrapositive proof."
I know how to negate statements and have tried proof by contradiction. I'm not sure what the writer means by "uncovering some other fact" and "when the contradiction is with the theorems hypothesis, we have a contrapositive proof" can someone please make this clear for me.
I know that theorems are of the form A implies B, and contrapositive is of the form not(B) implies not(A).
logic proof-writing proof-explanation
$endgroup$
marked as duplicate by Mauro ALLEGRANZA
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();
}
);
});
});
Dec 24 '18 at 9:16
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:
Why, logically, is proof by contradiction valid?
4 answers
What is the meaning of this following passage?
"An indirect proof always begins by negating what it is we would like to prove. The argument then proceeds until (hopefully) a logical contradiction with some other accepted fact is uncovered. Many times this accepted fact is part of the hypothesis of the theorem. When the contradiction is with the theorems hypothesis, we technically have what is called a contrapositive proof."
I know how to negate statements and have tried proof by contradiction. I'm not sure what the writer means by "uncovering some other fact" and "when the contradiction is with the theorems hypothesis, we have a contrapositive proof" can someone please make this clear for me.
I know that theorems are of the form A implies B, and contrapositive is of the form not(B) implies not(A).
logic proof-writing proof-explanation
$endgroup$
marked as duplicate by Mauro ALLEGRANZA
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();
}
);
});
});
Dec 24 '18 at 9:16
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.
$begingroup$
Welcome to Maths SX! In my opinion, a proof by contrapositive is not really a proof by contradiction (= ‘Reductio ad absurdum’).
$endgroup$
– Bernard
Dec 23 '18 at 22:10
$begingroup$
Thank you :) . Yes, I understand that they're different methods of proof, but confused about what the author means by the contradiction being with the assumption.
$endgroup$
– user606466
Dec 23 '18 at 22:19
$begingroup$
Well, all proofs by contradiction consist in proving , from the conclusion being supposed false, there exists an assertion which is both true (either by assumption or by an already proved theorem) and false. A standard example is the classical proof that $sqrt 2$ is irrational: you suppose the contrary, i.e. $sqrt2=frac ab$, which you may suppose an irreducible fraction, and in the end, you obtain the fraction can be simplified.
$endgroup$
– Bernard
Dec 23 '18 at 22:24
add a comment |
$begingroup$
This question already has an answer here:
Why, logically, is proof by contradiction valid?
4 answers
What is the meaning of this following passage?
"An indirect proof always begins by negating what it is we would like to prove. The argument then proceeds until (hopefully) a logical contradiction with some other accepted fact is uncovered. Many times this accepted fact is part of the hypothesis of the theorem. When the contradiction is with the theorems hypothesis, we technically have what is called a contrapositive proof."
I know how to negate statements and have tried proof by contradiction. I'm not sure what the writer means by "uncovering some other fact" and "when the contradiction is with the theorems hypothesis, we have a contrapositive proof" can someone please make this clear for me.
I know that theorems are of the form A implies B, and contrapositive is of the form not(B) implies not(A).
logic proof-writing proof-explanation
$endgroup$
This question already has an answer here:
Why, logically, is proof by contradiction valid?
4 answers
What is the meaning of this following passage?
"An indirect proof always begins by negating what it is we would like to prove. The argument then proceeds until (hopefully) a logical contradiction with some other accepted fact is uncovered. Many times this accepted fact is part of the hypothesis of the theorem. When the contradiction is with the theorems hypothesis, we technically have what is called a contrapositive proof."
I know how to negate statements and have tried proof by contradiction. I'm not sure what the writer means by "uncovering some other fact" and "when the contradiction is with the theorems hypothesis, we have a contrapositive proof" can someone please make this clear for me.
I know that theorems are of the form A implies B, and contrapositive is of the form not(B) implies not(A).
This question already has an answer here:
Why, logically, is proof by contradiction valid?
4 answers
logic proof-writing proof-explanation
logic proof-writing proof-explanation
asked Dec 23 '18 at 22:05
user606466
marked as duplicate by Mauro ALLEGRANZA
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();
}
);
});
});
Dec 24 '18 at 9:16
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
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();
}
);
});
});
Dec 24 '18 at 9:16
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.
$begingroup$
Welcome to Maths SX! In my opinion, a proof by contrapositive is not really a proof by contradiction (= ‘Reductio ad absurdum’).
$endgroup$
– Bernard
Dec 23 '18 at 22:10
$begingroup$
Thank you :) . Yes, I understand that they're different methods of proof, but confused about what the author means by the contradiction being with the assumption.
$endgroup$
– user606466
Dec 23 '18 at 22:19
$begingroup$
Well, all proofs by contradiction consist in proving , from the conclusion being supposed false, there exists an assertion which is both true (either by assumption or by an already proved theorem) and false. A standard example is the classical proof that $sqrt 2$ is irrational: you suppose the contrary, i.e. $sqrt2=frac ab$, which you may suppose an irreducible fraction, and in the end, you obtain the fraction can be simplified.
$endgroup$
– Bernard
Dec 23 '18 at 22:24
add a comment |
$begingroup$
Welcome to Maths SX! In my opinion, a proof by contrapositive is not really a proof by contradiction (= ‘Reductio ad absurdum’).
$endgroup$
– Bernard
Dec 23 '18 at 22:10
$begingroup$
Thank you :) . Yes, I understand that they're different methods of proof, but confused about what the author means by the contradiction being with the assumption.
$endgroup$
– user606466
Dec 23 '18 at 22:19
$begingroup$
Well, all proofs by contradiction consist in proving , from the conclusion being supposed false, there exists an assertion which is both true (either by assumption or by an already proved theorem) and false. A standard example is the classical proof that $sqrt 2$ is irrational: you suppose the contrary, i.e. $sqrt2=frac ab$, which you may suppose an irreducible fraction, and in the end, you obtain the fraction can be simplified.
$endgroup$
– Bernard
Dec 23 '18 at 22:24
$begingroup$
Welcome to Maths SX! In my opinion, a proof by contrapositive is not really a proof by contradiction (= ‘Reductio ad absurdum’).
$endgroup$
– Bernard
Dec 23 '18 at 22:10
$begingroup$
Welcome to Maths SX! In my opinion, a proof by contrapositive is not really a proof by contradiction (= ‘Reductio ad absurdum’).
$endgroup$
– Bernard
Dec 23 '18 at 22:10
$begingroup$
Thank you :) . Yes, I understand that they're different methods of proof, but confused about what the author means by the contradiction being with the assumption.
$endgroup$
– user606466
Dec 23 '18 at 22:19
$begingroup$
Thank you :) . Yes, I understand that they're different methods of proof, but confused about what the author means by the contradiction being with the assumption.
$endgroup$
– user606466
Dec 23 '18 at 22:19
$begingroup$
Well, all proofs by contradiction consist in proving , from the conclusion being supposed false, there exists an assertion which is both true (either by assumption or by an already proved theorem) and false. A standard example is the classical proof that $sqrt 2$ is irrational: you suppose the contrary, i.e. $sqrt2=frac ab$, which you may suppose an irreducible fraction, and in the end, you obtain the fraction can be simplified.
$endgroup$
– Bernard
Dec 23 '18 at 22:24
$begingroup$
Well, all proofs by contradiction consist in proving , from the conclusion being supposed false, there exists an assertion which is both true (either by assumption or by an already proved theorem) and false. A standard example is the classical proof that $sqrt 2$ is irrational: you suppose the contrary, i.e. $sqrt2=frac ab$, which you may suppose an irreducible fraction, and in the end, you obtain the fraction can be simplified.
$endgroup$
– Bernard
Dec 23 '18 at 22:24
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let's elucidate each of these confusing phrases with its own example.
First I'll discuss a proof by contradiction that $sqrt{2}$ is irrational. The argument will uncover a contradiction with another accepted fact. If $sqrt{2}=a/b$ with $a,,b$ non-zero integers then $a^2=2b^2$ is even, so $a$ is even, say $a=2c$. Then $b^2=2c^2$ is also even, as is $b$. In particular, we can cancel a factor of $2$ from the numerator and denominator of any fraction equal to $sqrt{2}$, so there's no lowest terms for such a fraction. This uncovers a contradiction with another accepted fact, namely that every fraction can be cancelled into lowest terms.
Next I'll discuss a proof by contradiction that if some finite number $n$ of people attend a party, some two shake hands with the same number of people. The number of people with whom a given attendee can shake hands ranges from $0$ to $n-1$ inclusive, which is only $n$ options. Since the number of options equals the number of people, we can restate our hypothesis as some number of handshakes from $0$ to $n-1$ inclusive isn't achieved. Well, let's get a contradiction from that. In this argument the contradiction is with the theorem's hypothesis. Suppose instead they all are. Since someone shakes hands with no-one ($0$ shakes), say Alice, no-one shakes hands with everyone, because Alice is always missed. But that means $n-1$ is unachieved, so we don't achieve all totals after all! Note here the potential truth of the claim we wished to refute has implied its own falsity; or equivalently, the hypothesis being false implied it is true.
$endgroup$
add a comment |
$begingroup$
A proof by contradiction of a statement $B$ is when we start with the assumption of $lnot B,$ derive something false from that assumption, and then conclude that the assumption must have been wrong (i.e. $B$ is true).
But often times are theorems are if/then statements, in other words of the form $Ato B.$ A proof of $Ato B$ by contrapositive is a proof of $lnot Bto lnot A,$ which we typically prove by assuming $lnot B$ and deriving $lnot A.$ This is valid since the contrapositive $lnot Bto lnot A$ is logically equivalent to $Ato B.$
People often confuse these two and say a proof is 'by contradiction' even if it actually takes the second form. There is a good reason for this. When we're proving $Ato B,$ the way we generally think about it is that we assume $A$ and then prove $B$ under that assumption. One route we might take is to prove $B$ by contradiction by assuming $lnot B$ and then proving $lnot A,$ which is a false statement under our assumption of $A.$
Whereas in a proof by contradiction we derive any false statement whatsoever, in the pattern above, we derive a very specific statement $lnot A$ which is only false under the assumption of $A$ that we made. This is what the author meant by "where the contradiction is with the theorem's hypothesis."
Notice the part where all the work was done was in assuming $lnot B$ and then deriving $lnot A,$ i.e. directly proving the contrapositive $lnot Bto lnot A$. However, we mentally framed it as a proof by contradiction of $B$, under the assumption $A$, which amounts to a proof of $Ato B$. Note this is not at all the same thing as a true proof by contradiction of the statement $Ato B,$ which would consist of assuming $lnot(Ato B)$ and deriving a false statement.
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let's elucidate each of these confusing phrases with its own example.
First I'll discuss a proof by contradiction that $sqrt{2}$ is irrational. The argument will uncover a contradiction with another accepted fact. If $sqrt{2}=a/b$ with $a,,b$ non-zero integers then $a^2=2b^2$ is even, so $a$ is even, say $a=2c$. Then $b^2=2c^2$ is also even, as is $b$. In particular, we can cancel a factor of $2$ from the numerator and denominator of any fraction equal to $sqrt{2}$, so there's no lowest terms for such a fraction. This uncovers a contradiction with another accepted fact, namely that every fraction can be cancelled into lowest terms.
Next I'll discuss a proof by contradiction that if some finite number $n$ of people attend a party, some two shake hands with the same number of people. The number of people with whom a given attendee can shake hands ranges from $0$ to $n-1$ inclusive, which is only $n$ options. Since the number of options equals the number of people, we can restate our hypothesis as some number of handshakes from $0$ to $n-1$ inclusive isn't achieved. Well, let's get a contradiction from that. In this argument the contradiction is with the theorem's hypothesis. Suppose instead they all are. Since someone shakes hands with no-one ($0$ shakes), say Alice, no-one shakes hands with everyone, because Alice is always missed. But that means $n-1$ is unachieved, so we don't achieve all totals after all! Note here the potential truth of the claim we wished to refute has implied its own falsity; or equivalently, the hypothesis being false implied it is true.
$endgroup$
add a comment |
$begingroup$
Let's elucidate each of these confusing phrases with its own example.
First I'll discuss a proof by contradiction that $sqrt{2}$ is irrational. The argument will uncover a contradiction with another accepted fact. If $sqrt{2}=a/b$ with $a,,b$ non-zero integers then $a^2=2b^2$ is even, so $a$ is even, say $a=2c$. Then $b^2=2c^2$ is also even, as is $b$. In particular, we can cancel a factor of $2$ from the numerator and denominator of any fraction equal to $sqrt{2}$, so there's no lowest terms for such a fraction. This uncovers a contradiction with another accepted fact, namely that every fraction can be cancelled into lowest terms.
Next I'll discuss a proof by contradiction that if some finite number $n$ of people attend a party, some two shake hands with the same number of people. The number of people with whom a given attendee can shake hands ranges from $0$ to $n-1$ inclusive, which is only $n$ options. Since the number of options equals the number of people, we can restate our hypothesis as some number of handshakes from $0$ to $n-1$ inclusive isn't achieved. Well, let's get a contradiction from that. In this argument the contradiction is with the theorem's hypothesis. Suppose instead they all are. Since someone shakes hands with no-one ($0$ shakes), say Alice, no-one shakes hands with everyone, because Alice is always missed. But that means $n-1$ is unachieved, so we don't achieve all totals after all! Note here the potential truth of the claim we wished to refute has implied its own falsity; or equivalently, the hypothesis being false implied it is true.
$endgroup$
add a comment |
$begingroup$
Let's elucidate each of these confusing phrases with its own example.
First I'll discuss a proof by contradiction that $sqrt{2}$ is irrational. The argument will uncover a contradiction with another accepted fact. If $sqrt{2}=a/b$ with $a,,b$ non-zero integers then $a^2=2b^2$ is even, so $a$ is even, say $a=2c$. Then $b^2=2c^2$ is also even, as is $b$. In particular, we can cancel a factor of $2$ from the numerator and denominator of any fraction equal to $sqrt{2}$, so there's no lowest terms for such a fraction. This uncovers a contradiction with another accepted fact, namely that every fraction can be cancelled into lowest terms.
Next I'll discuss a proof by contradiction that if some finite number $n$ of people attend a party, some two shake hands with the same number of people. The number of people with whom a given attendee can shake hands ranges from $0$ to $n-1$ inclusive, which is only $n$ options. Since the number of options equals the number of people, we can restate our hypothesis as some number of handshakes from $0$ to $n-1$ inclusive isn't achieved. Well, let's get a contradiction from that. In this argument the contradiction is with the theorem's hypothesis. Suppose instead they all are. Since someone shakes hands with no-one ($0$ shakes), say Alice, no-one shakes hands with everyone, because Alice is always missed. But that means $n-1$ is unachieved, so we don't achieve all totals after all! Note here the potential truth of the claim we wished to refute has implied its own falsity; or equivalently, the hypothesis being false implied it is true.
$endgroup$
Let's elucidate each of these confusing phrases with its own example.
First I'll discuss a proof by contradiction that $sqrt{2}$ is irrational. The argument will uncover a contradiction with another accepted fact. If $sqrt{2}=a/b$ with $a,,b$ non-zero integers then $a^2=2b^2$ is even, so $a$ is even, say $a=2c$. Then $b^2=2c^2$ is also even, as is $b$. In particular, we can cancel a factor of $2$ from the numerator and denominator of any fraction equal to $sqrt{2}$, so there's no lowest terms for such a fraction. This uncovers a contradiction with another accepted fact, namely that every fraction can be cancelled into lowest terms.
Next I'll discuss a proof by contradiction that if some finite number $n$ of people attend a party, some two shake hands with the same number of people. The number of people with whom a given attendee can shake hands ranges from $0$ to $n-1$ inclusive, which is only $n$ options. Since the number of options equals the number of people, we can restate our hypothesis as some number of handshakes from $0$ to $n-1$ inclusive isn't achieved. Well, let's get a contradiction from that. In this argument the contradiction is with the theorem's hypothesis. Suppose instead they all are. Since someone shakes hands with no-one ($0$ shakes), say Alice, no-one shakes hands with everyone, because Alice is always missed. But that means $n-1$ is unachieved, so we don't achieve all totals after all! Note here the potential truth of the claim we wished to refute has implied its own falsity; or equivalently, the hypothesis being false implied it is true.
answered Dec 23 '18 at 22:51
J.G.J.G.
27.5k22843
27.5k22843
add a comment |
add a comment |
$begingroup$
A proof by contradiction of a statement $B$ is when we start with the assumption of $lnot B,$ derive something false from that assumption, and then conclude that the assumption must have been wrong (i.e. $B$ is true).
But often times are theorems are if/then statements, in other words of the form $Ato B.$ A proof of $Ato B$ by contrapositive is a proof of $lnot Bto lnot A,$ which we typically prove by assuming $lnot B$ and deriving $lnot A.$ This is valid since the contrapositive $lnot Bto lnot A$ is logically equivalent to $Ato B.$
People often confuse these two and say a proof is 'by contradiction' even if it actually takes the second form. There is a good reason for this. When we're proving $Ato B,$ the way we generally think about it is that we assume $A$ and then prove $B$ under that assumption. One route we might take is to prove $B$ by contradiction by assuming $lnot B$ and then proving $lnot A,$ which is a false statement under our assumption of $A.$
Whereas in a proof by contradiction we derive any false statement whatsoever, in the pattern above, we derive a very specific statement $lnot A$ which is only false under the assumption of $A$ that we made. This is what the author meant by "where the contradiction is with the theorem's hypothesis."
Notice the part where all the work was done was in assuming $lnot B$ and then deriving $lnot A,$ i.e. directly proving the contrapositive $lnot Bto lnot A$. However, we mentally framed it as a proof by contradiction of $B$, under the assumption $A$, which amounts to a proof of $Ato B$. Note this is not at all the same thing as a true proof by contradiction of the statement $Ato B,$ which would consist of assuming $lnot(Ato B)$ and deriving a false statement.
$endgroup$
add a comment |
$begingroup$
A proof by contradiction of a statement $B$ is when we start with the assumption of $lnot B,$ derive something false from that assumption, and then conclude that the assumption must have been wrong (i.e. $B$ is true).
But often times are theorems are if/then statements, in other words of the form $Ato B.$ A proof of $Ato B$ by contrapositive is a proof of $lnot Bto lnot A,$ which we typically prove by assuming $lnot B$ and deriving $lnot A.$ This is valid since the contrapositive $lnot Bto lnot A$ is logically equivalent to $Ato B.$
People often confuse these two and say a proof is 'by contradiction' even if it actually takes the second form. There is a good reason for this. When we're proving $Ato B,$ the way we generally think about it is that we assume $A$ and then prove $B$ under that assumption. One route we might take is to prove $B$ by contradiction by assuming $lnot B$ and then proving $lnot A,$ which is a false statement under our assumption of $A.$
Whereas in a proof by contradiction we derive any false statement whatsoever, in the pattern above, we derive a very specific statement $lnot A$ which is only false under the assumption of $A$ that we made. This is what the author meant by "where the contradiction is with the theorem's hypothesis."
Notice the part where all the work was done was in assuming $lnot B$ and then deriving $lnot A,$ i.e. directly proving the contrapositive $lnot Bto lnot A$. However, we mentally framed it as a proof by contradiction of $B$, under the assumption $A$, which amounts to a proof of $Ato B$. Note this is not at all the same thing as a true proof by contradiction of the statement $Ato B,$ which would consist of assuming $lnot(Ato B)$ and deriving a false statement.
$endgroup$
add a comment |
$begingroup$
A proof by contradiction of a statement $B$ is when we start with the assumption of $lnot B,$ derive something false from that assumption, and then conclude that the assumption must have been wrong (i.e. $B$ is true).
But often times are theorems are if/then statements, in other words of the form $Ato B.$ A proof of $Ato B$ by contrapositive is a proof of $lnot Bto lnot A,$ which we typically prove by assuming $lnot B$ and deriving $lnot A.$ This is valid since the contrapositive $lnot Bto lnot A$ is logically equivalent to $Ato B.$
People often confuse these two and say a proof is 'by contradiction' even if it actually takes the second form. There is a good reason for this. When we're proving $Ato B,$ the way we generally think about it is that we assume $A$ and then prove $B$ under that assumption. One route we might take is to prove $B$ by contradiction by assuming $lnot B$ and then proving $lnot A,$ which is a false statement under our assumption of $A.$
Whereas in a proof by contradiction we derive any false statement whatsoever, in the pattern above, we derive a very specific statement $lnot A$ which is only false under the assumption of $A$ that we made. This is what the author meant by "where the contradiction is with the theorem's hypothesis."
Notice the part where all the work was done was in assuming $lnot B$ and then deriving $lnot A,$ i.e. directly proving the contrapositive $lnot Bto lnot A$. However, we mentally framed it as a proof by contradiction of $B$, under the assumption $A$, which amounts to a proof of $Ato B$. Note this is not at all the same thing as a true proof by contradiction of the statement $Ato B,$ which would consist of assuming $lnot(Ato B)$ and deriving a false statement.
$endgroup$
A proof by contradiction of a statement $B$ is when we start with the assumption of $lnot B,$ derive something false from that assumption, and then conclude that the assumption must have been wrong (i.e. $B$ is true).
But often times are theorems are if/then statements, in other words of the form $Ato B.$ A proof of $Ato B$ by contrapositive is a proof of $lnot Bto lnot A,$ which we typically prove by assuming $lnot B$ and deriving $lnot A.$ This is valid since the contrapositive $lnot Bto lnot A$ is logically equivalent to $Ato B.$
People often confuse these two and say a proof is 'by contradiction' even if it actually takes the second form. There is a good reason for this. When we're proving $Ato B,$ the way we generally think about it is that we assume $A$ and then prove $B$ under that assumption. One route we might take is to prove $B$ by contradiction by assuming $lnot B$ and then proving $lnot A,$ which is a false statement under our assumption of $A.$
Whereas in a proof by contradiction we derive any false statement whatsoever, in the pattern above, we derive a very specific statement $lnot A$ which is only false under the assumption of $A$ that we made. This is what the author meant by "where the contradiction is with the theorem's hypothesis."
Notice the part where all the work was done was in assuming $lnot B$ and then deriving $lnot A,$ i.e. directly proving the contrapositive $lnot Bto lnot A$. However, we mentally framed it as a proof by contradiction of $B$, under the assumption $A$, which amounts to a proof of $Ato B$. Note this is not at all the same thing as a true proof by contradiction of the statement $Ato B,$ which would consist of assuming $lnot(Ato B)$ and deriving a false statement.
answered Dec 24 '18 at 0:54
spaceisdarkgreenspaceisdarkgreen
33.1k21753
33.1k21753
add a comment |
add a comment |
$begingroup$
Welcome to Maths SX! In my opinion, a proof by contrapositive is not really a proof by contradiction (= ‘Reductio ad absurdum’).
$endgroup$
– Bernard
Dec 23 '18 at 22:10
$begingroup$
Thank you :) . Yes, I understand that they're different methods of proof, but confused about what the author means by the contradiction being with the assumption.
$endgroup$
– user606466
Dec 23 '18 at 22:19
$begingroup$
Well, all proofs by contradiction consist in proving , from the conclusion being supposed false, there exists an assertion which is both true (either by assumption or by an already proved theorem) and false. A standard example is the classical proof that $sqrt 2$ is irrational: you suppose the contrary, i.e. $sqrt2=frac ab$, which you may suppose an irreducible fraction, and in the end, you obtain the fraction can be simplified.
$endgroup$
– Bernard
Dec 23 '18 at 22:24