2
$\begingroup$

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$
  • $\begingroup$ The vague part is where you write "an example where it doesn't work." What is "it" and what does "doesn't work" mean? $\endgroup$ – Matthew Leingang Jul 13 '17 at 9:05
  • $\begingroup$ Yes; suppose that you want to disprove the (false) claim that every natural number is even. (i.e. a multiple of $2$). It is enough to consider the number $3$: it is not a multiple of $2$ and thus we can safely conclude that: "not every (natural) number is even". $\endgroup$ – Mauro ALLEGRANZA Jul 13 '17 at 9:06
  • $\begingroup$ @MatthewLeingang I edited my question, hope it helps. $\endgroup$ – user401855 Jul 13 '17 at 9:08
  • $\begingroup$ I still think it's vague. Can you give an explicit example where you're struggling? $\endgroup$ – Henno Brandsma Jul 13 '17 at 9:20
3
$\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$
  • $\begingroup$ this got to the core of the issue. Thanks for the answer! $\endgroup$ – Neo M Hacker Feb 26 at 7:17
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$
1
$\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$
0
$\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$

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.