Intereting Posts

First four terms of the power series of $f(z) = \frac{z}{e^z-1}$?
Supremum of absolute value of the Fourier transform equals $1$, and it is attained exactly at $0$
Residue Calculation
Find the diameter of the new sphere assuming that the volume of a sphere is proportional to the cube of its diameter
How do I prove this sum is not an integer
Correct way to calculate numeric derivative in discrete time?
Let the function $f: \to \mathbb R$ be Lipschitz. Show that $f$ maps a set of measure zero onto a set of measure zero
Why is $\frac{d^n}{dx^n}(y(x))$ the notation for the $n$th derivative of $y(x)$, instead of $\frac{d^n}{d^nx}(y(x))$?
How to prove that $ 6ab=(a+b)(a+b+c)$ for triangle
Generalized rotation matrix in N dimensional space around N-2 unit vector
$(R^{\oplus A})^{\oplus B} \approx R^{\oplus (A\times B)}$?
Proving that $\lim_{n\rightarrow \infty} \frac{n^k}{2^n}=0$
Prove that $\int_0^\pi\frac{\cos x \cos 4x}{(2-\cos x)^2}dx=\frac{\pi}{9} (2160 – 1247\sqrt{3})$
A secant inequality for convex functions
Number we know all prime numbers less than

What is the difference between a “proof by contradiction” and “proving the contrapositive”? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proves by contradiction, and the other proves the contrapositive, the proofs look almost exactly the same.

For example, say I want to prove: $P \implies Q$

When I want to prove by contradiction, I would say assume this is not true.

Assume $Q$ is not true, and $P$ is true. Blabla, but this implies $P$ is not true, which is a contradiction.

When I want to prove the contrapositive, I say. Assume $Q$ is not true. Blabla, this implies $P$ is not true.

- Number of combinations with repetitions (Constrained)
- How many ways are there to position two black rooks and two white rooks on an 8X8 chessboard
- Free resources to start learning Discrete Mathematics
- Prove by induction the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges).
- Permutation isomorphic subgroups of $S_n$ are conjugate
- Ideal Coin Value Choices

The only difference in the proof is that I assume $P$ is true in the beginning, when I want to prove by contradiction. But this feels almost redundant, as in the end I always get that this is not true. The only other way that I could get a contradiction is by proving that $Q$ is true. But this would be the exact same things as a direct proof.

Can somebody enlighten me a little bit here ? For example: Are there proofs that can be proven by contradiction but not proven by proving the contrapositve?

- Prove that there's no fractions that can't be written in lowest term with Well Ordering Principle
- True, false, or meaningless?
- Understanding an Easy Relative Consistency Proof
- What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?
- Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$?
- combinatorics circular arrangement problem
- Formal System and Formal Logical System
- What is the difference between necessary and sufficient conditions?
- Axiom Systems and Formal Systems
- Proving $(A\cup B)\cap(B\cup C)\cap(C\cup A)=(A\cap B)\cup (A\cap C)\cup (B\cap C)$?

There is a useful rule of thumb, when you have a proof by contradiction, to see whether it is “really” a proof by contrapositive.

In a proof of by contrapositive, you prove $P \to Q$ by assuming $\lnot Q$ and reasoning until you obtain $\lnot P$.

In a “genuine” proof by contradiction, you assume *both* $P$ and $\lnot Q$, and deduce some other contradiction $R \land \lnot R$.

So, at then end of your proof, ask yourself: Is the “contradiction” just that I have deduced $\lnot P$, when the implication was $P \to Q$? Did I never use $P$ as an assumption? If both answers are “yes” then your proof is a proof by contraposition, and you can rephrase it in that way.

For example, here is a proof by “contradiction”:

Proposition: Assume $A \subseteq B$. If $x \not \in B$ then $x \not \in A$.

Proof. We proceed by contradiction. Assume $x \not \in B$ and $x \in A$. Then, since $A \subseteq B$, we have $x \in B$. This is a contradiction, so the proof is complete.

That proof can be directly rephrased into a proof by contrapositive:

Proposition: Assume $A \subseteq B$. If $x \not \in B$ then $x \not \in A$.

Proof. We proceed by contraposition. Assume $x \in A$. Then, since $A \subseteq B$, we have $x \in B$. This is what we wanted to prove, so the proof is complete.

Proof by contradiction can be applied to a much broader class of statements than proof by contraposition, which only works for implications. But there are proofs of implications by contradiction that cannot be directly rephrased into proofs by contraposition.

Proposition: If $x$ is a multiple of $6$ then $x$ is a multiple of $2$.

Proof. We proceed by contradiction. Let $x$ be a number that is a multiple of $6$ but not a multiple of $2$. Then $x = 6y$ for some $y$. We can rewrite this equation as $1\cdot x = 2\cdot (3y)$. Because the right hand side is a multiple of $2$, so is the left hand side. Then, because $2$ is prime, and $1\cdot x $ is a multiple of $2$, either $x$ is a multiple of $2$ or $1$ is a multiple of $2$. Since we have assumed that $x$ is not a multiple of $2$, we see that $1$ must be a multiple of $2$. But that is impossible: we know $1$ is not a multiple of $2$. So we have a contradiction: $1$ is a multiple of $2$ and $1$ is not a multiple of $2$. The proof is complete.

Of course that proposition can be proved directly as well: the point is just that the proof given is genuinely a proof by contradiction, rather than a proof by contraposition. The key benefit of proof by contradiction is that you can stop when you find *any* contradiction, not only a contradiction directly involving the hypotheses.

To prove $P \rightarrow Q$, you can do the following:

- Prove directly, that is assume $P$ and show $Q$;
- Prove by contradiction, that is assume $P$ and $\lnot Q$ and derive a contradiction; or
- Prove the contrapositive, that is assume $\lnot Q$ and show $\lnot P$.

Sometimes the contradiction one arrives at in $(2)$ is merely contradicting the assumed premise $P$, and hence, as you note, is essentially a proof by contrapositive $(3)$. However, note that $(3)$ allows us to assume *only* $\lnot Q$; if we can then derive $\lnot P$, we have a *clean* proof by contrapositive.

However, in $(2)$, the aim is to derive a *contradiction*: the contradiction might *not* be arriving at $\lnot P$, if one has assumed ($P$ *and* $\lnot Q$). Arriving at *any contradiction* counts in a proof by contradiction: say we assume $P$ *and* $\lnot Q$ and derive, say, $Q$. Since $Q \land \lnot Q$ is a contradiction (can never be true), we are forced then to conclude *it cannot be that both* $(P \land \lnot Q)$.

But note that $\lnot (P \land \lnot Q) \equiv \lnot P \lor Q\equiv P\rightarrow Q.$

So a proof by contradiction usually looks something like this ($R$ is often $Q$, or $\lnot P$ or any other contradiction):

- $P \land \lnot Q$ Premise
- $P$
- $\lnot Q$
- $\vdots$
- $R$
- $\vdots$
- $\lnot R$
- $\lnot R \land R$ Contradiction

$\therefore \lnot (P \land \lnot Q) \equiv P \rightarrow Q$

It’s not the same.

If $P$ and $Q$ are statements about instances that (a priori independently) are true for some instances and false for others then proving $P\Rightarrow Q$ is the same as proving the contrapositive $\neg Q\ \Rightarrow \neg P$. Both mean the same thing: The set of instances for which $P$ is true is contained in the set of instances where $Q$ is true.

Proving a statement $A$ by contradiction is something else: You add $\neg A$ to your list of axioms, and using the rules of logic arrive at a contradiction, e.g., at $1=0$. Then you say: My axiom system was fine before adding $\neg A$. Since this addition has spoiled it, in reality $A$ has to be true.

An example: You want to prove the statement $$A:\quad {\rm “The\ number}\ \sqrt{2}\ {\rm is\ irrational.”}$$

Then you add $\sqrt{2}={p\over q}$ to your list of axioms about rational numbers and arrive at a contradiction.

[Note: The post by amWhy is pretty much what I like to say, but still prefer to put my response as a separate answer, hoping some readers might find it more useful]

First, let me restrict my response only to conditional statements of the form $P\rightarrow $Q.

With this, let’s understand two important equivalences as listed below.

$P\rightarrow Q \equiv \lnot Q\rightarrow \lnot P$ …(I)

$P\rightarrow Q \equiv \lnot (\lnot (P\rightarrow Q)) \equiv \lnot (P \land \lnot Q) \equiv (P \land \lnot Q) \rightarrow C$ where C is contradiction …(II)

**For proof by contraposition**, we use equivalence (I) where we start by assuming $\lnot Q$ and show, by use of calculations and a priori knowledge about other theorems, etc., that $\lnot P$ is true.

**For proof by contradiction**, we use equivalence (II) where we start by assuming $P$ and $\lnot Q$ and show this leads to some kind of contradiction. The contradiction can be with $P$, or $Q$, or with altogether new statement $R$.

However, as long as there is some contradiction, it essentially proves the original statement. **In this regard, also note that, when the contradiction is with either P or Q (i.e. any of the initial assumptions), the proof by contradiction often looks very similar to proof by contraposition, especially for the ones who are not clear about the differences in (I) and (II).**

**Example 1**: If n is an odd integer, then 5n-3 is an even integer. You may prove this either by contradicting P or by Q.

**Example 2**:If f(x)=(2x+3)/(x+2) , then for every real x, f(x) ≠ 2. You may find a contradiction in an altogether new statement say $R$ := “3=4”

One difference is that proof by contrapositive only applies to propositions of the form $A \to B$ (“if-then propositions”). However not every proposition is a “if-then proposition”, for example, consider the proposition, `exist x real for all p,q integer, x != p/q`

, there is no $\to$ inside that proposition, so it is not feasible to prove it by contrapositive.

Proof by contrapositive is based on this rule:

$(\neg B \to \neg A) \to (A \to B)$

Proof by contradiction could be based on this rule:

$(\neg A \to (B \land\neg B)) \to A $

In both case you first prove the left hand side, then by applying modus ponens you get the right hand side.

Surprisingly, **no one has mentioned quantifiers.**

To quote a comment from Bernard on a duplicate of this question:

Take the assertion: ‘When Mr So and So is happy, he sings. The contrapositive asserts that ‘Mr So and So does not sing so he’s not happy’. The negation asserts that ‘There are days when Mr So and So is happy, yet he does not sing’.

I converted this example into logical notation *with quantifiers,* which makes the difference between negation and contrapositive more obvious.

**Original statement:** Any day when Mr. So-and-so is happy is a day when he sings. $$\forall d \in D_{ays}: (H_{appy}(M_r) \rightarrow S_{ings}(M_r))$$

**Contrapositive:** Any day when Mr. So-and-so does not sing is a day when he is not happy. $$\forall d \in D_{ays}: (\neg S_{ings}(M_r) \rightarrow \neg H_{appy}(M_r))$$

**Negation:** There are some days (at least one day) when Mr. So-and-so is happy, but does not sing. $$\exists d \in D_{ays}: (H_{appy}(M_r) \land \neg S_{ings}(M_r))$$

This doesn’t directly address the different types of *proofs* based on these concepts (addressed in several answers already), but it may assist an understanding of that.

To prove by contrapositive, in the above example, you would start with the expression (proposition) “not singing” and *directly* derive “not happy” (perhaps by algebraic rearrangement).

To prove by contradiction, on the other hand, you would *assume* the *negation,* and then derive from there until you had proven two contradictory facts.

- Prove that $\cos (A + B)\cos (A – B) = {\cos ^2}A – {\sin ^2}B$
- A scalar product in the space of oriented volumes?
- Two styles of semantics for a first-order language: what's to choose?
- A number-theory question on the deficiency function $2x – \sigma(x)$
- Is the formula $(\text{ker }A)^\perp=\text{im }A^T$ necessarily true?
- What is Modern Mathematics? Is this an exact concept with a clear meaning?
- The identity cannot be a commutator in a Banach algebra?
- Prove that $\Big|\frac{f(z)-f(w)}{f(z)-\overline{f(w)}}\Big|\le \Big|\frac{z-w}{z-\overline w}\Big|$
- Property of critical point when the Hessian is degenerate
- Presentation of the fundamental group of a manifold minus some points
- Probability of picking all elements in a set
- Definition of a nowhere dense set
- Does the Laplace transform biject?
- Triangle forming probability for area
- Integral $\int_0^\pi \theta^2 \ln^2\big(2\cos\frac{\theta}{2}\big)d \theta$.