12
$\begingroup$

I am looking for some examples of when proof by contradiction is used in a problem with more than one case.

In all the elementary examples, there are only two options (eg rational/irrational, infinite/finite), so you assume the opposite, show it cannot be true and then conclude the result.

However, I remember from my undergraduate study situations where there were three or more options and proof by contradiction was used to eliminate one or more of these.

I do not remember any of these examples anymore, but I was wondering if I could have some examples of statements (ideally elementary, but more advanced works) that follow such a style in their proof. This would be good to have to show students I teach typical contexts in which this may arise.

Thank you

$\endgroup$
18
$\begingroup$

(1) Here is a $3$-case proof from Larry Cusick's webpages:

Theorem. There are no rational number solutions to the equation $x^3 + x + 1 = 0$.

Proof. (Proof by Contradiction.) Assume to the contrary there is a rational number $p/q$, in reduced form, with $p$ not equal to zero, that satisfies the equation. Then, we have $p^3/q^3 + p/q+ 1 = 0$. After multiplying each side of the equation by $q^3$, we get the equation

$$p^3 + p q^2 + q^3 = 0 \;.$$ There are three cases to consider.

(1) If $p$ and $q$ are both odd, then the left hand side of the above equation is odd. But zero is not odd, which leaves us with a contradiction.

(2) If $p$ is even and $q$ is odd, then the left hand side is odd, again a contradiction.

(3) If $p$ is odd and $q$ is even, we get the same contradiction.

The fourth case—$p$ even and $q$ even—is not possible because we assumed that $p/q$ is in reduced form. This completes the proof.


(2) Another $3$-case example may be found in Euclid's Elements, Book I, Prop.6, which uses the law of trichotomy for lines:

Proposition. If in a triangle two angles equal one another, then the sides opposite the equal angles also equal one another.

See David Joyce's webpage:

"If $AB$ does not equal $AC$, then one of them is greater." There are three cases: $AB < AC$, $AB = AC$, $AB > AC$.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Maybe you mean "q not equal to zero" (not "p not equal to zero")? $\endgroup$ – Daniel R. Collins May 10 at 6:34
  • 1
    $\begingroup$ @DanielR.Collins - I think that q=0 is invalid pretty much by definition because that wouldn't be a reduced rational number then. p=0 means that we're looking at non-0 solutions to the equation. Actually, I think that 0 should be looked separately as a fourth case too, although it's trivial to see that it's not a solution. $\endgroup$ – Vilx- May 10 at 10:57
  • 1
    $\begingroup$ zero is handled in case (2) $\endgroup$ – RiaD May 11 at 3:42

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.