Would anyone mind explaining me how proof by contradiction works? I have a very vague understanding of it so I always avoid using it when it comes to discrete math. From what I've seen its something that is extremely useful when it comes to proofs.
From what I understand proof by contradiction is the following. Given an example I have to prove it to be true. I take the complete opposite from it and prove it to be false(?), from then on I can assume that the original example is true(?). If anyone would mind correcting my understanding, please do. Also, what would be a good step-by-step guide I can have in my mind when using it?
$\endgroup$6 Answers
$\begingroup$As Sherlock Holmes said, "When you have eliminated the impossible, whatever remains, however improbable, must be the truth".
If you can prove that not-$P$ is impossible, then you conclude that $P$ must be true.
$\endgroup$ 4 $\begingroup$Your understanding is fine, but it is good to really understand this proof.
A typical proof of contradiction looks like this:
- I want to prove the statement $P$.
- I assume that $\neg P$ , the negation of $P$, is correct (note, this is not "the complete opposite" in the typical sense. For example, it $P$ is "All humans are white", then $\neg P$ is not "no human is white", but rather "Not all humans are white", or in other words, "some humans are not white."
- Using the fact that $\neg P$ is true, and all other tricks up my sleeve, I prove that a contradiction is true (for example, I prove that $1<0$ or something similar).
- I then conclude that $P$ is true.
A typical example of a proof by contradiction is the proof that there are infinitely many primes:
- I want to prove $P=\text{there are infinitely many primes}$.
- I assume that $P$ is not true, so the statement $\neg P=\text{there are not infinitely many primes}$ is true.
Now, I use all my tricks. In this case, they are: 1. If there are not infinitely many primes, then there must be finitely many primes. Therefore, I can enumerate all primes, and they are $p_1,p_2,\dots, p_n$. Now, because there are finitely many primes, I can calculate the product $$M=p_1\cdot p_2\cdots p_n+1$$ Now, I can easily prove that $M$ is not divisible by any prime (as they are finite by assumption). This means that $M$ is a prime number. However, $M$ is greater than any other prime, so $M$ is not in the set $S=\{p_1,\dots, p_n\}$. But $S$ is a set of all primes, and $M$ is a prime which is not in the set of all primes. This is a contradiction.
- Therefore, My original statement is true.
I personally think the best analogy for this is sudoku. Let's say you get down to a point where the only options for a spot are a $3$ and a $1$. You can't decide which to use, so you just go for the three. A few turns later, you end up with $2$ twos in the same row, so you know you must have made a mistake somewhere, but the only time you did something you were unsure of it when you put a $3$ in the original spot. Thus, there is no way that original spot had a $3$ in it, so it must have a one in it.
Likewise, let's say you are trying to prove a statement. There are two possibilities: it is true, or it is false. If you decide to "guess" that it is false, and later on end up at something totally impossible, then you know that somewhere along the line you must have messed up. But the only time you did something you were uncertain of is when you assumed the statement was false. Thus, the statement couldn't possibly be false, so it must be true.
Let's run through a simple example. I want to prove that there is no largest natural number. Well there are two possibilities, either that statement is true, or it is false. Well let's see what happens if I "guess" it to be false. Well, if the statement is false, then that means that there is some largest natural number, let's call it $N$. But now, I claim that that is absurd because $N+1$ is always greater than $N$, so somewhere along the line I must have made a mistake. Well, the only step I was uncertain about was assuming that there was a largest natural number, so that must be the bad step, and therefore there cannot possibly be a largest natural number.
$\endgroup$ $\begingroup$A proof by contradiction is this: you have statements $P$ and $Q$, and you would like to know that $P\Rightarrow Q$ (note here that you are assuming the truth of $P$). So instead of showing that $P\Rightarrow Q$ directly, the contradiction is that we show we cannot have both of the statements $P$ and $\neg Q$ hold at the same time (in notation $P\wedge\neg Q$ is false). Since we are assuming $P$ is a true statement, the thing that fails must be $\neg Q$, which means $Q$ must hold.
$\endgroup$ 3 $\begingroup$In propositional logic, suppose you want to prove $P$ is true. Assume to the contrary that $\neg P$ is true. If you are then able to derive a contradiction of the form $Q\land \neg Q$ or $Q\iff \neg Q$, then you can conclude, as required, that $P$ is true.
In predicate logic, suppose you want to prove that $\forall a: P(a)$. Assume to the contrary that $\neg P(x)$ is true, where $x$ is the only free variable introduced in this statement. If you are then able to derive a contradiction of the form $Q\land \neg Q$ or $Q\iff \neg Q$, then you can conclude, as required, that $\forall a: P(a)$.
Similarly for multiple variables. Suppose you want to prove that $\forall a: \forall b: P(a,b)$. Assume to the contrary that $\neg P(x,y)$ is true, where $x$ and $y$ are the only free variables introduced in this statement. If you are then able to derive a contradiction of the form $Q\land \neg Q$ or $Q\iff \neg Q$, then you can conclude, as required, that $\forall a: \forall b: P(a,b)$.
Disclaimer: This may not be how it is done in many logic textbooks. Some instructors will say I am leaving out steps, but I really think this is how most mathematicians think about it. Show the extra steps if you must.
$\endgroup$ 7 $\begingroup$Proof by contradiction is simple: If $\;\neg A, \Sigma \vdash \bot\;$ then $\;\Sigma \vdash A\;$.
- we add the negation of what-is-to-be-shown to our premises
- we demonstrate that doing this leads to nonsense (that is, a contradiction).
- we conclude the premises entail what-is-to-be-shown.
