5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are you asking for proofs of things that are commonly known in mathematics, or that would be commonly known by people who would send you that xkcd? (By the way, I found that xkcd funny, but in a oh-that-hurts kind of way.) $\endgroup$ – Brian Tung Dec 10 '15 at 23:36
  • 2
    $\begingroup$ You don't need contradiction to show that $x \in \mathbb{Q} \setminus \mathbb{Z}$ satisfies $x^2 \not\in \mathbb{N}$. This shows that the only natural numbers whose square roots are rational are the squares. $\endgroup$ – Eric Tressler Dec 10 '15 at 23:48
  • $\begingroup$ @BrianTung I guess I'm looking for proofs that are the MOST commonly known by people who have gone through college. Not only mathematicians. I guess this is a short list. That's why I'd like a reference if anyone has one. $\endgroup$ – amcalde Dec 11 '15 at 16:32
3
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ I appreciate the answer but this is really not what I'm looking for. Maybe I should just close the question. $\endgroup$ – amcalde Dec 11 '15 at 16:25
  • $\begingroup$ @amcalde I like the question. But it's not really well-defined the way you meant it. $\endgroup$ – 6005 Dec 11 '15 at 18:20
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Some proofs by contradiction are of the form $\neg \phi \Rightarrow (\psi \wedge \neg \psi)$. I'm not sure whether this can be converted directly into contrapositive form. $\endgroup$ – Ian Dec 11 '15 at 1:13
  • $\begingroup$ @Ian $\neg \phi \rightarrow (\psi \wedge \neg \psi) \equiv (\psi \wedge \neg \psi) \vee \neg \neg \phi \equiv (\psi \wedge \neg \psi) \vee \phi \equiv (\phi \vee \psi) \wedge (\phi \vee \neg \psi)$ $\endgroup$ – Stefan Mesken Dec 11 '15 at 1:22
  • $\begingroup$ Isn't this a little misleading? Of course proofs by contradiction can be converted into direct proofs in a Hilbert system where the axioms already have all the components to make proof by contradiction valid. However you prove something in a Hilbert system, if proof by contradiction is a valid rule, then you are basically relying on rules equivalent to proof by contradiction. $\endgroup$ – 6005 Dec 11 '15 at 2:16
  • $\begingroup$ If you want to make a distinction between whether or not a proof uses proof by contradiction, you will have to use as a base a logical system where proof by contradiction is not valid, so that you can then say which other theorems rely on it based on whether or not they follow from the base set of axioms, or whether they only follow from the base set of axioms + proof by contradiction. $\endgroup$ – 6005 Dec 11 '15 at 2:17
  • $\begingroup$ All of the subtlety is hidden in these three rules: $A \land \lnot A \vDash \bot$ (LNC), $\bot \vDash A$ (explosion), $A \lor \lnot A$ (LEM). $\endgroup$ – 6005 Dec 11 '15 at 2:19
1
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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