0
$\begingroup$

I have seen it said on Mathematics Stack Exchange that proofs by contrapositive are generally preferred over proofs by contradiction (for instance here and here). In other words, it is bad style to prove an implication $P\to Q$ by assuming $P\land\neg Q$, and then giving a direct proof of $\neg Q\to\neg P$ without using the assumption $P$, and then deriving the contradiction $P\land\neg P$. There are many reasons why this might be considered bad style, but to me the most significant one is the following:

  • If in a proof by contradiction you establish a number of intermediate results $A_1,A_2,\dots,A_n$, then those results are not guaranteed to be valid outside of the contradictory framework you are working in—they are being used to construct a logical house of cards that will eventually topple. However, if you give a direct proof of $\neg Q\to\neg P$, then any intermediate results you establish along the way are valid. By phrasing the proof by contrapositive as a proof by contradiction, you are at risk of misleading the reader.

However, let's actually consider an example. The proof given below seems typical of what you might find in an introductory analysis book. Pay attention to the bolded sentence below:

Theorem: If a sequence of real numbers is increasing and bounded above, then its supremum is its limit.

Proof: Let $(a_n)_{n\in\mathbb N}$ be a sequence of real numbers, and let $\{a_n\}$ be the set of terms in $(a_n)_{n\in\mathbb N}$. By the least-upper-bound property of the real numbers, $l=\sup\{a_n\}$ exists in $\mathbb R$. Now, for every $\pmb{\varepsilon>0}$ there is an $\pmb{N>0}$ such that $\pmb{a_N>l-\varepsilon}$, as otherwise $\pmb{l-\varepsilon}$ would be an upper bound of $\pmb{\{a_n\}}$, which contradicts the definition of $\pmb{l}$. Since $(a_n)_{n\in\mathbb N}$ is increasing, if $n>N$, then $c\ge a_n\ge a_N>c-\varepsilon$, and so $|c-a_n|<\varepsilon$. Hence, by the definition of the limit of a sequence, $a_n\to\sup\{a_n\}$ as $n\to\infty$.

The claim being made in the bolded sentence above is $$ (\forall\varepsilon > 0)(\exists N>0)(a_N>l-\varepsilon) \, . $$ And the way this claim is proven is by showing that $$ \neg(\forall\varepsilon > 0)(\exists N>0)(a_N>l-\varepsilon)\to(\text{$l-\varepsilon$ is an upper bound of $\{a_n\}$})\land(l=\sup\{a_n\}) \, , $$ which is a contradiction. But notice that we just as well could have proven the claim by directly proving that $$ \neg(\forall\varepsilon > 0)(\exists N>0)(a_N>l-\varepsilon)\to(\text{$l-\varepsilon$ is an upper bound of $\{a_n\}$}) $$ and so by considering the contrapositive of this claim, we see that $$ (\text{$l-\varepsilon$ is not an upper bound of $\{a_n\}$})\to(\forall\varepsilon > 0)(\exists N>0)(a_N>l-\varepsilon) \, . $$ Since $l=\sup\{a_n\}$, we know that the premise of the above statement is true, and so the conclusion follows.

In this example, does it really matter that the proof by contrapositive above is phrased as a proof by contradiction? And if not, why are the objections to proof by contradiction raised above not relevant here? When is it important to care about whether a proof is by contrapositive, or proof by contradiction?

$\endgroup$
4
  • $\begingroup$ The first linked post does not consider "taste" (bad or good) but the fact that a direct proof can give "more information" than an indirect one. $\endgroup$ Oct 14 at 13:12
  • 1
    $\begingroup$ The Indirect Proof assume $\lnot Q$, derive a contradiction whatever and then conclude with the negation of $\lnot Q$ that in turn - using Double Negation - produces the sought conclusion $Q$. By Conditional Proof we have: $P \to Q$. $\endgroup$ Oct 14 at 13:14
  • $\begingroup$ $\lnot Q \to \lnot P$ is equivalent to $P \to Q$ , but again using Excluded Middle (that is equivalent to Double Negation) $\endgroup$ Oct 14 at 13:15
  • 4
    $\begingroup$ Isn't this question off-topic as being opinion-based ? $\endgroup$
    – user974557
    Oct 14 at 13:27
1
$\begingroup$

There is no real difference.

  • Let's say we want to prove $A \to B$ by contradiction. Then we assume $\neg (A \to B)$, which is equivalent to $A \land \neg B$, and try to reach a contradiction.

  • Let's say we want to prove it by contrapostion. Then we want to show $\neg B \to \neg A$. To show this, we assume $\neg B$ and try to show $\neg A$, which means we additionally assume $A$ and try to reach a contradiction.

In both cases we have $A$ and $\neg B$ as assumptions and we are trying to reach a contradiction.

Even in weaker logics, both principles are equivalently strong.


Here are two ways to approach the question that has been brought up in the comments.

  • By using the equivalence $X \to Y \iff \neg X \lor Y$ and the DeMorgan laws, we see $$ \neg B \to \neg A \iff \neg (\neg B) \lor \neg A \iff \neg (\neg B \land A) $$ i.e. $\neg B \to \neg A$ is true if and only if $\neg (\neg B \land A)$ is true, which means showing that $\neg B \land A$ is false.

  • The second approach goes via natural deduction to make explicit the proof steps that were described in the case of contraposition: $$ \dfrac{ \dfrac{ \dfrac{\neg B, A \vdash \bot }{\neg B \vdash A \to \bot} }{\neg B \vdash \neg A} }{\vdash \neg B \to \neg A} $$ So we simply use the implication introduction rule twice, and uses the fact that $\neg A = A \to \bot$.

$\endgroup$
6
  • 2
    $\begingroup$ Which means we additionally assume $A$? No. Where did you get that notion? $\endgroup$ Oct 14 at 20:47
  • 3
    $\begingroup$ @TedShifrin I fail to see the mistake you are trying to point to. $\neg (A \land \neg B)$ is equivalent to $A \to B$. So proving $A \to B$ is the same as deriving a contradiction under the assumption $A \land \neg B$. $\endgroup$
    – Lereau
    Oct 14 at 21:04
  • 4
    $\begingroup$ It’s your discussion of the contrapositive that is flawed. $\endgroup$ Oct 14 at 21:05
  • 4
    $\begingroup$ It is TedShifrin's comment that is flawed. Lereau's claim that the proof-by-contrapositive rule and the proof-by-contradiction rule, appropriately formalized, are equivalent even over intuitionistic logic, is actually completely correct. $\endgroup$
    – user21820
    Oct 15 at 17:54
  • 3
    $\begingroup$ I am not saying these are not equivalent. I am saying that it is not proper form among working mathematicians to prove the contrapositive $\lnot B\implies\lnot A$ by assuming $A$ as well. This is a proof by contradiction of the contrapositive. Of course it's all "logically equivalent." But perhaps my 45 years as a mathematician should earn me an F in formal logic. $\endgroup$ Oct 15 at 18:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.