In constructive mathematics we make a distinction between "proof of negation" and "proof by contradiction". You can read a great account of the difference in this blog post of Andrej Bauer.
- Proof of negation is proving $\neg p$ by assuming $p$ and arguing an absurdity.
- Proof by contradiction is proving $p$ by assuming $\neg p$ and arguing an absurdity.
I am writing an introduction to proof book which puts Fitch style natural deduction introduction and elimination rules front and center. My definition of negation is $\neg p \equiv (p \implies \bot)$ where $\bot$ stands for an absurdity. The introduction rule for negation is thus the proof pattern we would call "proof of negation" above.
I am looking for a big list of elementary arguments which are actually proof by contradiction rather than proof of negation. I need these for the section of my textbook which covers the "proof by contradiction" strategy. It is exceedingly difficult to find elementary situations where proof by contradiction is actually an appropriate strategy.
Here is one example of each strategy:
Proof of negation
$6$ is not odd.
Assume that $6$ is odd. Then there is an integer $k$ with $6=2k+1$. Solving for $k$ yields $k=2.5$ which is not an integer. This is a contradiction. Thus $6$ is not odd.
Proof by contradiction
I steal an example from Neil Strickland: Some non-zero digit occurs infinitely often in the decimal expansion of $\pi$.
Proof: Assume to the contrary that every non-zero digit appears finitely many times in the decimal expansion of $\pi$. Then $\pi$ would be a rational number. However $\pi$ is known to be irrational. Contradiction.
In this argument we obtain a contradiction by assuming the negation of what we are trying to prove. Note that it does not actually produce an explicit example of a non-zero digit which occurs infinitely often (if it did the proof would be constructive).
UPDATE: I made the following table for my book. Perhaps it will inspire some more ideas. All of the current answers (I think) showcase the consequence of proving an existentially quantified statement by contradiction: that you cannot actually show me how to produce a witness. It would be interesting to see examples of proofs by contradiction which showcase the other sacrifices.
|Type of statement||The sacrifice we make using proof by contradiction|
|$p \vee q$||I know that either $p$ or $q$ is true, but I cannot tell you which one.|
|$p \wedge q$||I don't have a direct argument for $p$ and $q$ independently.|
|$\neg p$||There is no sacrifice. $\neg p$ is equivalent to $\neg (\neg (\neg p))$ in intuitionist logic as well. A bit weird to do though.|
|$p \implies q$||If you hand me an argument that $p$ is true, I do not actually have a way to use that data to argue $q$. All I can do is tell you that there should be such an argument.|
|$\exists x \in U: A(x)$||While I know that some $x_1 \in U$ makes $A(x_1)$ true, I do not know how to actually show you one.|
|$\forall x \in U: A(x)$||If you hand me a particular $x_1 \in U$ I don't have a direct argument that $A(x_1)$ is true. I can only show you that assuming it is not true leads to contradiction. In other words, whatever type of statement $A(x_1)$ is, I will pay the associated price for that statement.|