# Proof by Contradiction

1. Aug 24, 2016

### Devil Moo

Proof by contradiction starts by supposing a statement, and then shows the contradiction.

1. The problem statement, all variables and given/known data

Now, there is a statement $A$.
Suppose $A$ is false.
So $A$ is true.

My question:
There are two statements $A$ and $B$.
Suppose $A$ is true.
Further suppose $B$ is false.
Can I conclude that "if $A$ is true, then $B$ is false."

Moreover, how do I distinguish between "Proof by Contradiction" and "Proof by Exhaustion"?

2. Aug 24, 2016

### andrewkirk

No. But you can conclude that if A is true then B is true.
Proof by exhaustion does not necessarily involve any contradictions. Here's the definition from wiki:

Last edited: Aug 24, 2016
3. Aug 24, 2016

### Staff: Mentor

Here's an example of a proof by exhaustion.
Assume that n is a positive integer. Then n(n + 1)(n + 2) is divisible by 3.

Case 1: n = 3k, for some integer k
Then n(n + 1)(n + 2) = 3k(3k + 1)(3k + 2), which clearly has a factor of 3, and so is divisible by 3

Case 2: n = 3k + 1, for some integer k
Then n(n + 1)(n + 2) = (3k + 1)(3k + 2)(3k + 3) = (3k + 1)(3k + 2)3(k + 1), which has a factor of 3, so is divisible by 3.

Case 3: n = 3k + 2, for some integer 8
Then n(n + 1)(n + 2) = (3k + 2)(3k + 3)(3k + 4) = (3k + 2)3(k + 1)(3k + 4), also has a factor of 3, so is divisible by 3.

There are no other possible cases. Any integer n falls into one of three equivalence classes: $n \equiv 0 (\mod 3)$, or $n \equiv 1 (\mod 3)$, or $n \equiv 2 (\mod 3)$. IOW, when an integer n is divided by 3, the remainder will be 0, 1, or 2. The three cases above are based on this fact.

4. Aug 24, 2016

### Staff: Mentor

Reopened...

Last edited: Aug 24, 2016