I have a vague question about proof by contradiction. The main goal of proofs by contradiction is to show that if some statement was true, then we would end up by a logical contradiction. My question would: in order to achieve the logical contradiction, would it be enough to just show a counter-example? That is we suppose the false statement, and then just give an example where the statement gives an illogical/absurd result. Would that be correct?
$\endgroup$ 44 Answers
$\begingroup$No that's not enought (if i understood what you mean). Think about it this way:
You want to prove A => B and you want to do it by contradiction. That means you suppose B is false even with the hypothesis A. Giving a counterexample to this means giving an example of A => B, and this doesn't prove A=>B in general.
For example: I try to prove that every odd number is prime (which is false); By contradiction suppose n is odd but not prime. I can find a counterexample to this (3 is odd and prime) but this doesn't give me the thesis (in fact 9 is odd but not prime)
$\endgroup$ 1 $\begingroup$What you're describing sounds more to me like a proof by counterexample than a proof by contradiction. For instance, in Mauro's proof that the statement "every natural number is even," he didn't need to assume for the sake of contradiction that not every number is even. He just pointed to the number 3.
Some so-called proofs by contradiction are proofs by contrapositive instead. To prove $A\implies B$, some writers will assume $A$ and $\neg B$, then derive $\neg A$, and say $A$ and $\neg A$ is a contradiction. But what they have actually done is proven $\neg B \implies \neg A$, which is the contrapositive of $A\implies B$.
A real proof by contradiction will arrive at some kind of internal contradiction. A very good example is the proof that $\sqrt{2}$ is irrational. You assume it is rational, then write it in lowest terms as $\frac{a}{b}$. From $a^2 = 2b^2$, you derive that both $a$ and $b$ are divisible by $2$, so $\frac{a}{b}$ can't be in lowest terms after all. So you see, the contradiction doesn't have to do with the statement in the theorem, so much as something that would follow from that statement being false.
$\endgroup$ $\begingroup$It depends on the proposition you wish to prove or disprove. If suppose you are asked to prove that for all integers $n$, $a^n + b^n = c^n$ has no integral solutions, then a counter-example might disprove this statement as it is clearly false if $n=2$(but true for all $n >2$)
But as Henno pointed out already, finding a counter-example and establishing a contradiction are not the same, counter-examples are very useful tool to disprove a more general result, in the same token, they are not easy to find, and also, it doesn't make sense to find counter-examples when asked to prove some interesting properties of numbers, like proving that $\sqrt {n}$ is irrational if $n$ is not a perfect square by looking for counterexamples, that's a NO NO.
But in proof by contradiction, you assume the given statement is false, then see what conditions are satisfied if that statement is false,then careful argument might lead you to an absurdity for which you can be sure that that your original assumption that the proposition is false must be wrong, hence the proposition must(Using the Law of excluded middle) be true
The proof for the irrationality of $\sqrt {2}$ is a good example.
$\endgroup$ $\begingroup$You seem to be confusing "proof by contradiction" with "proof by (counter)example".
e.g. the statement "not every natural number is even" can be proved by giving an example of a number like $3$ that can be shown not to be even.
This $3$ is also a counterexample to the statement "all natural numbers are even".
A proof by contradiction is a proof of a statement by assuming there is a counterexample and then deriving a contradiction from that supposed counterexample , a classical case being the proof that $\sqrt{2}$ is irrational.
$\endgroup$
