Nature of Proof by Contradiction

Question

This is from a maths competition which is still probably taking place, so I don't think I will be able to release any specific details about it yet.

Essentially, the question asked for a proof of $A\Rightarrow B$.

This was however difficult so I took the contrapositive of this ($\bar B\Rightarrow \bar A$) and proved the contrapositive by contradiction (by assuming $\bar B\Rightarrow A$).

This has raised two questions:

1) I showed that a contradiction arises for a specific case where all the points lie in a straight line. This is not the general case, so would this proof be sufficient for the contrapositive?

2) Is my overall approach valid?

Answer 1

So you did something like:

Prove: $\forall(x); A(x) \implies B(x)$ and you figured that is equvialent to

$\forall(x); \lnot B(x) \implies \lnot A(x)$. (that is correct). And to prove that you tried to do a proof by contradiction that

Assume $\forall(x); \lnot B(x) \implies A(x)$. (Wrong!)

And you showed a contradiction that $\exists(x): \lnot B(x) \land \lnot A(x)$. (Which is a valid contradiction to your assumption)

You did prove that $\forall(x); \lnot B(x) \implies A(x)$ is false.

But that does not prove that $\forall(x); \lnot B(x) \implies \lnot A(x)$.

.... consider the following FALSE proof.

Prove: If $n$ is composite, the $n$ is a perfect square. (This is obviously false. For example $n=6$ is a couterexample.)

Contrapositive If $n$ is not a perfect square then $n$ is prime. (That is the correct contrapositive. But it is still false.)

Assume not: Assume If $n$ is not a perfect square then $n$ is composite. (This is NOT the correct negation. "If $n$ is not a perfect square then $n$ is prime" is obviously false. And "If $n$ is not a perfect square then $n$ is composite" is also obviously false. A negation must be the exact opposite. This is not the exact oposite.)

(The proper negation would be "There is an $n$ that is not a perfect square but is composite". This will never lead to a contradiction because because it is TRUE.... Now back the faulty proof).

But here's a counter example: $n = 7$ is not a perfect square. So our assumption, If $n$ is not a perfect square then $n$ is composite, was false

So if $n$ is not a perfect square than $n$ is prime,

which is equivalent to: If $n$ is composite then it is a perfect square.

This fails because the negation of $\forall(x); \lnot B(x) \implies \lnot A(x)$ is NOT $\forall(x); \lnot B(x) \implies A(x)$. The negation is $\exists (x): \lnot B \land A(x)$.

ANd in our example the negation of: If $n$ is not a perfect square, then $n$ is prime; is not-- if $n$ is not a perfect square, then $n$ is prime. The negation is: there is an $n$ where $n$ is not a perfect square and $n$ is composite.

This will never lead to a contradiction as it is a true statement and the statement you were trying to prove is just wrong.

......

What you should do is something more like this.

Prove: If $n$ is a perfect square (other than $1$) it is composite.

Contrapositive: If $n$ is prime it is not a perfect square.

Assume not: Assume, there exists an $n$ that is prime and also a perfect square.

But that means $n = m^2 = m*m$ for some $m$. So $n$ has a factor that is neither equal to one nor to $n$ itself. That's a contradiction.

So if $n$ is prime it can not be a perfect square.

And, contrapositively, if $n$ is a perfect square (other than 1), it must be composite.

That is a valid proof.

=====

I don't know what you statement you were trying to prove but it seems to be something like.

If points K are GIMBLE then they are WOBBLE.

Lets suppose you have:

points: A,B,C are colinear, not GIMBLE and not WOBBLE

point D,E,F are GIMBLE and WOBBLE.

points H,I,J are not GIMBLE and WOBBLE.

And points K,L,M are GIMBLE but you don't know if they are WOBBLE or not.

Your proof went like this:

The proposition is GIMBLE $\implies$ WOBBLE. So far as we know that may be true or it may not be. It's true if $K,L,M$ are all WOBBLE but it isn't true if some of $K,L,M$ are not WOBBLE.

You figured the contrapositive: not WOBBLE $\implies$ not GIMBLE. That is the correct contrapositive. We don't know if it is true. If some of the $K,L,M$ aren't WOBBLE it isn't true. But if they are all WOBBLE it is true.

You assumed the opposite. not WOBBLE $\implies$ GIMBLE. That is NOT the opposite. If not WOBBLE $\implies$ not GIMBLE is true then then not WOBBLE $\implies$ GIMBLE if false. THat part is fine. But If not WOBBLE $\implies$ not GIMBLE is false then not WOBBLE $\implies$ GIMBLE may be true and may not be. THis is not the negation.

And we do know that not WOBBLE $\implies$ GIMBLE is false as poinst $A,B,C$ is a case where they are not WOBBLE and not GIMBLE. But that's not enough to show not WOBBLE always implies not GIMBLE.

THe actual negation of not WOBBLE $\implies$ not GIMBLE is: It's possible for there to be points that not WOBBLE and GIMBLE. This is also the same negation of the original GIMBLE $\implies$ WOBBLE.

To prove either $GIMBLE \implies WOBBLE$ or the equivalent not WOBBLE $\implies $ not GIMBLE by contradition is a matter of showing not WOBBLE and GIMBLE leads to a contradition.

Showing a specific case where neither occurs is not enough.

Answer 2

If you want to prove the contrapositive by contradiction, you have to handle a general/arbitrary case where both $A$ and $B'$ hold, not a specific case. Note that this is simply the same as if you were to prove the original statement $A \implies B$ by contradiction.