For the Sake of Argument

Question

So someone sent me this xkcd as a reply to something I said online:

https://xkcd.com/1432/

I frankly felt assaulted by the pop culture monster. Perhaps as a mathematician this is not uncommon.

My question is, in math we often prove things by contradiction. For example perhaps the best known way to prove that $\sqrt{2} \notin \Bbb{Q}$. This proof is, what I consider to be, well known. In that many people may have seen it in high school.

My question is: are there other well known examples of proofs via contradiction (so far) that are commonly known? I guess, sort of as a rebuttal to the idea that only liars assume things for the sake of arguing about them.

If you consider this question too broad, I could use a reference for such results or a nice book about them, etc.

Answer 1

The first question is, what do you mean you MUST prove things by contradiction? The only thing you can possibly mean, is that there are things which can be proved without proof-by-contradiction, i.e. without some of the very rules of logic that we usually take for granted. What exactly do we mean by this?

In classical logic, it is a theorem that proof by contradiction holds: for any statement $P$, if $\lnot P$ implies $Q$ and $\lnot Q$, then $P$. This theorem relies on three facts:

1. The law of the excluded middle (LEM): for any $P$, either $P$ or $\lnot P$.

2. The law of non-contradiction (LNC): for any $P$, if $P$ and $\lnot P$ then $\bot$. (This symbol can means the statement that is always false, read as just "false".)

3. The principle of explosion (PE): for any $P$, if $\bot$ then $P$.

The proof of the theorem, then, goes like this: Assume that $\lnot P$ implies $Q$ and not $Q$. By LEM, either $P$ or $\lnot P$. In the former case, $P$ and we are done. In the latter case, because $\lnot P$, by our assumption, $Q$ and $\lnot Q$. Therefore by LNC, $\bot$, and by PE, $P$. So we are done in this case as well.

---

So, what can you get done without proof by contradiction? Well, as the above theorem shows, you can get anything done as long as you accept LEM, LNC, and PE. But what if you reject these? A prominent alternative to classical logic is intuitionist logic, which rejects LEM. In intuitionistic thinking, you are not allowed to prove something by showing the opposite cannot be true. In particular, if you show that $P$ results in a contradiction, that means that $\lnot P$, because that's what $\lnot P$ means. But if you show that $\lnot P$ results in a contradiction, you have only shown that $\lnot \lnot P$--you haven't given a direct proof of $P$.

So, this has been a bit roundabout, but to answer your question, what are some things that you "need" proof by contradiction to prove? Here are some examples (I wish I had more), in the sense that intuitionist logic is not enough to prove them:

• There exists a function which is not continuous.

• There exists an incomputable function.

In fact (!), proving $\sqrt{2}$ is irrational does NOT require proof by contradiction, as you have claimed; you can do it by finding the continued fraction of $\sqrt{2}$.

---

See also:

• How can some statements be consistent with intuitionistic logic but not classical logic, when intuitionistic logic proves not not LEM?

Answer 2

If by a proof we mean a formal deduction in a Hilbert System that obeys classical propositional logic, then we never have to proof anything by contradiction. The reason for this is, that in such a system

1. $\phi \rightarrow \psi$
2. $\neg \psi \rightarrow \neg \phi$

are provably equivalent and thus any proof for $\neg \psi \rightarrow \neg \phi$ may be extended to a proof for $\phi \rightarrow \psi$ and vice versa.

Most mathematicians rarely (never) think about proofs in a formal way, but they agree (intuitively) on a common logical calculus which allows the above equivalence. However, this is not true of all mathematicians and there are alternative logical systems (e.g. intuitionistic logic) where 1. and 2. may not be provably equivalent. Thus, if your definition of a proof differs from mine in a substantial way, you would have to provide us with your logical system and notion of proof, before we could try to answer your question.

Answer 3

I think that the main problem with contradiction proofs is that they belong to a binary world where thing are radically true or radically false. This works great for our form of mathematics, but in a real world where things are sort of always mixed-up doesn't work that well.

I think that's why didn't really catch up with other lines of thought from the common sense. I guess that whatever example you will present at that stage it will appear as another "for the sake of argument".