Proof by contradiction or contrapositive are both indirect proofs. For a proof of contrapositive, we
assume that the conclusion is false and prove that the hypothesis is also false. For a proof of
contradiction, we assume that the negation of the hypothesis is true, then we find a contradiction
proving it to be false, thus proving the hypothesis true.
Here is an example of proof by contrapositive.
The claim is that for any integer a and b,
a+b≥15
implies that
a≥8
or
b≥8
.
Here is the proof. Let us assume that for any integer a and b,
a<8
and
b<8
.
We can say
a+b=7+7
Then
a+b=14
This means
a+b≤15
By showing that when a and b are less than 8, a+b is less than 15. Therefore, we have proven that
for a+b to be greater than or equal to 15, a or b must be greater than or equal to 8.
With proof of contradiction, we assume the opposite of what we are trying to prove and get a
contradiction that is logical. Therefore, our assumption is false, and we need to prove that it is
true.
With proof of contrapositive, we use the rule of inference where one infers a conditional
statement from its contrapositive. For example, “if X, then B” is what is inferred we need to
construct a proof of our claim “if not X, then not B” instead.
Proof by contrapositive:
If a is even, then 3a + 1 is odd.
We assume a is an even integer.
Of integers, a=2k for some integer k.
So,
3a+1 = 3(2k) +1
d d d d d d d d =2(3k) +1
d d d d d d d =2m+1, for some integer m, that m=3k
This goes after 3a+1 = 2m +1 which naturally is an odd integer.
So, it is shown that for any integer a, if 3a+1 is even, then a is odd, by proof of contrapositive.
Proof by contrapositive is done by negating the conclusion then evaluating and directly proving
the negation of the original hypothesis.
Proof by contradiction is done by negating only the conclusion and proving it the original
hypothesis to derive a contradiction.
An example would be for every pair of integers x and y, if x-y is odd, then x is odd or y is odd.
For proof by contrapositive, we assume x is even and y is even. X = 2i and Y = 2j, for some integers
i and j.
x-y = 2(i-y). Therefore, x-y will always be 2 times an integer. Therefore, x-y is even, thus proving
the contrapositive.
Proof by contradiction and contrapositive are somewhat similar. There are, however, a couple of
defining characteristics. Proof by contradiction proves the proposition by assuming it is false, and
when solving the proof a contradiction arises, showing that the proposition was indeed true. Proof
by contrapositive takes the proposition and assumes that if the outcome is false, so is the
proposition. I will provide an example of proof by contrapositive below.
Let x be some integer.
Prove if x2is even, then x is even.
Proof by contrapositive:
If x is not even, then x2 is not even.
If x is not even, x=2k+1for some integer k.
Plugging in 2k+1 for x, we get:
d d (2k+1)2=4k2+4k+1=2(2k2+2k) +1
Since x=2k+1,
and (2k+1)2=2∗ some integer (2k2+2k) +1, x2 is not even.
Thus, having proved the contrapositive, we can infer that if x2 is even, then x is even. d
Some statements are more difficult to prove using a direct proof so instead we use an indirect
proof. An indirect proof may include a proof of contradiction or a proof of contrapositive. A proof
of contradiction starts with the assumption that the theorem is false, which eventually leads to a
contradiction. When working out a proof of contrapositive, on the other hand, for a conditional
statement,
a→b
, we assume the conclusion is false, therefore the hypothesis is false,
¬b→¬a
. A simple example of proof of contrapositive is:
Theorem: If 5n+3 is an odd number, then n must be an even number.
Proof:
Assume n represents an odd integer (the negation of the conclusion).
Since n is an odd integer, n=2k+1 for some integer k.
We then substitute n into the equation to get 5(2k+1) +3.
10k+8=2(5k+4)
(5k+4) is still an integer.
When you multiply any integer by 2, it results in an even integer (the negation of the hypothesis).
In mathematics, proof by contradiction refers to the proof that validates a proposition or
establishes a truth by showing that when the proposition is assumed to be false, it can lead to a
contradiction. It is an indirect kind of proof that is since when something leads to a contradiction,
it is not possible for it to be true. Thus, in such a case, the opposite must be true (An introduction
to proof by contradiction. NRICH, 2021).
Proof by contrapositive, on the other hand, refers to the rule of inference that is created by
negating both the terms in a conditional statement and reversing the very direction of the
inference. Thus, instead of assuming that the hypothesis and associated conclusion is true, the
technique assumes that the conclusion is false and subsequently proves that the associated
hypothesis is also false (Indirect proof explained (contradiction vs contrapositive). Cal workshop,
2021). It is since an ‘implication’ is equivalent to the ‘contrapositive.’ (Libre texts, 2020).
An example of proof by contrapositive has been presented below:
Claim: For every integer a and b, a + b >= 15 implies a >= 8 or b >= 8
Proof: By using the proof of contraposition, it is equivalent to prove that “if a < 8 and b < 8, then a
+ b < 15”
It can be assumed for both the integers a and b, a < 8 and b < 8,
Thus, it follows that a <= 7 and b <= 7
a + b = 7 + 7
= 14 which is < 15
The computation shows that a < 8 and b < 8, a + b < 15 are true. Thus, it has been proven that for
every integer a and b, a + b >= 15 implies that a >= 8 or b >= 8 by the proof of contrapositive.
Within mathematics proof by contrapositive essentially means that we are saying the proposition
to be false. An example of this would be saying that p -> q then its contrapositive of ~q -> ~p to be
equivalent. We say this because p (x) -> q (x) is infact true for x then ~q (x) -> ~p (x) would also be
true. This would be true because it is way easier when proving contrapositive statement to solve
~q (x) -> ~p (x) than that of p (x) -> q (x).
With proof by contradiction would be applied when a negation of the therom statement ~p would
be way easier to prove than that of p using proof. An example of this would be that of saying
there is no largest even integer. Now using k+2. We can say that k + 2 = (2n) + 2 = 2(n+1.) Then
say that k+2 is even, however k+2 is indeed larger than that of just k. This would be a
contradiction because the statement clearly says that k is the largest even integer. This would lead
us back to our original claim proving it to be true.
In proof by contradiction, we assume that the statement to be proved is false. That is, we suppose
the negation of the statement to be proved to be true. Then, we show logically that our
supposition leads to a contradiction. Finally, we conclude that the statement to be proved is true.
This is because after a contradiction is reached, the supposition is false therefore the statement to
be proved is true.
The proof by contrapositive is based on the logical equivalence of a statement and its
contrapositive. To prove a statement by contraposition, we take the contrapositive of the
statement, prove the contrapositive by direct proof, and conclude that the original statement is
true. The underlying reasoning being since a conditional statement is logically equivalent to its
contrapositive, if the contrapositive is true then the statement is true.
For example, proof by contrapositive:
Proposition: For all integers n, if n2 is even, then n is even
Proof:
Suppose n is any odd integer. Of odd,
n = 2k + 1 for some integer k. By substitution and algebra,
n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1.
But 2k2 + 2k is an integer because products and sums of integers are integers.
So n2 = 2(an integer) + 1, and thus, of odd, n2 is odd
Since the contrapositive is true, we conclude that the initial proposition to be proved is true.
A direct proof involves the assumption that the hypothesis is true followed by work to enforce the
hypothesis. The following propositions can be direct, as stated before or indirect through
contrapositive or contradictive avenues to reinforce the initial hypothesis.
Contrapositive proofs tackle the hypothesis through negating the hypothesis, so p→q is −p→−q. If
the proof shows not p, then not q to be true than the original hypothesis must be true.
Contradiction also assumes p→q to be false. The hypothesis is true and the conclusion must be
false. Proving the conclusion to be false inadvertently proves the hypothesis to be true.
Let x be an integer. If x2−6x+5 is even, then x is odd
assuming x is even, the assumption that x2−6x+5 is odd.
even integers x=2a, odd integers x=2b+1 where a and b are both integers.
x2−6x+5=(2a)2−6(2a) +5
=4a2−12a+5
=2(2a2−6a+2) +1
which indicates the proposition to be x2−6x+5 odd.
(Proof) of Contradiction: One proposition P is true, assume not P is true, then find a contradiction
that shows not P is false, so P is true.
The Implication, P->Q, assume P and not Q is true, then finds a contradiction that shows that P->Q
is true or not Q->, not P is true.
Proof of Contradiction is proof that determines the truth of a statement by assuming that it is
false, then work to show how it is false until the results of the assumption are a contradiction.
(Webster Dictionary)
Proof of Contrapositive is a proposition or theorem formed by contradicting both the subject and
predicate or both the hypothesis and conclusion of a given proposition or theorem and
interchanging them (if not -b then not-a) is the contrapositive of (if a then b). (Webster Dictionary)
A proof by contradiction is when we are proving a statement where we are assuming the
hypothesis is true and the conclusion is false. For instance, we can say that 2–√ is irrational. For
contradiction we would assume that 2–√ is rational so we can say that 2–√=pq where p and q do
not = 0 and are integers with no common factors. We would start by squaring and multiplying by
q2 to get p2=2(q2) this means that p2or p is an even number. We can say that p=2k for some an
integer k. So now we can say that 4k2=2q2 which means that q2=2k2 which means that q and q2
are even and because they are both even that means they are both divisible by 2. This contradicts
what was said about p and q having no common factors. This means that we cannot have 2–√ as a
rational number which means it is rational. A proof by contrapositive is basically saying that if one
statement is true than its opposite or negation must also be true or its equivalent.
The difference between proof by contrapositive and contradiction can be a bit confusing, at least
it was for me at first. A proof by contradiction is used by assuming the hypothesis to be true and
the conclusion to be false. We then show that this causes and contradiction and therefore the
initial conclusion is true, and thus prove its legitimacy.
Proof by contrapositive starts the same as proof by contradiction, in that we assume the
conclusion to be false, but we then prove that the hypothesis is false. This works because of the
equivalence between `If A, then B` and `If not A, then not B`.
Example (Contrapositive):
Prove that for all integers, if 5x+3 is even, then x is an odd number. For a contrapositive proof we
will assume the hypothesis is false and prove that the conclusion is also false.
Suppose x is not odd.
If x is not odd then x is even.
If x is even then x can be rewritten as x=2a for some integer a.
Then we can say that 5x+3=5(2a) +3=10a+3=10a+2+1=2(5a+1) +1.
Since a is an integer then 5a+1 is an integer.
Therefore 5x+3=2b+1where b is an integer.
Consequently 5x+3 is odd, the definition of an odd integer being 2k+1 where k is an integer.
Therefore 5x+3 is even.
Proof by contradiction and proof by contrapositive are similar in a way that they both create a
statement to either prove a hypothesis to be true or false, but they differ in the way that the
statements are created. Proof by contrapositive begins with the negation of the conclusion and
proving that the negation of the hypothesis is true. Proof by contradiction, on the other hand,
takes the negation of the theorem to show that inconsistencies will arise, proving the original
theorem to be true. Below, I will provide proof by contrapositive.
Prove: For every integer n, if n2−2n+7 is even, then n is odd.
Proof: Assume that n is n is NOT odd resulting in n2−2n+7 NOT being even.
Since n is even, n=2k for some integer k.
Plugging 2k into n2−2n+7 gives (2k)2−2(2k) +7 = 4k2−4k+7
Factor out a 2 this results in 2(2k2−2k+3) +1 which is odd, meaning if n is even, n2−2n+7is odd.
Thus, by contrapositive, for every integer n, if n2−2n+7 is even, then n is odd.
References
An introduction to proof by contradiction. NRICH. (2021). Retrieved January 21, 2022, from
https://nrich.maths.org/4717
Indirect proof explained (contradiction vs contrapositive). Cal workshop. (2021, January 17).
Retrieved January 21, 2022, from https://calcworkshop.com/proofs/indirect-proof/
Libre texts. (2020, July 27). Indirect proofs. Mathematics Libre Texts. Retrieved January 21, 2022,
from
https://math.libretexts.org/Courses/Monroe_Community_College/MATH_220_Discrete_Math/3%3
A_Proof_Techniques/3.4%3A_Indirect_Proofs
