Confusion about proof statement by implication

Question

I have a question regarding proving "if p is true then q is true".

One way, is to show p $\implies$ q is a true statement, so then if p is true, then q is true.

The other way is to prove it by contrapositive, which is to say $\neg$q $\implies$ $\neg$p is true. This can be shown from the truth table of $\neg$q $\implies$ $\neg$p and p $\implies$ q, which proves they are logically equivalent.

p	q	(p $\implies$ q)	($\neg$q $\implies$ $\neg$p)
F	F	T	T
F	T	T	T
T	F	F	F
T	T	T	T

However, if p is true there are more logically equivalent statements on restriction of the case p = T . For example, let's look at $\neg$(p $\implies$$\neg$q).

p	q	~(p $\implies$ ~q)
F	F	F
F	T	F
T	F	F
T	T	T

If you restrict $\neg$(p $\implies$ $\neg$q) truth table to the case that p=T (as we only aim to show if p=T then q = T) , it is equivalent to p $\implies$ q truth table when p=T.

So why can't we just say if we want to prove "if p is true then q is true", we first show (p $\implies$ $\neg$q) is false, which means $\neg$(p $\implies$ $\neg$q) is true. and now if p=T it's truth table is the same as p $\implies$ q, so it means q is true.

So can use this approach alongside direct proof (p -> q) and prove by contrapositive ($\neg$q $\implies$ $\neg$p) when you only need to show if p is true the q is true?

I really appreciate any help with this confusion. Thank you.

Answer 1

The problem with the approach of showing $\neg (p \to \neg q)$ as opposed to $\neg q \to \neg p$ is that you cannot always prove the former when the implication $p \to q$ is true, while you can always prove the latter.

Ultimately, a proof of the former requires that $p$ be true, which doesn’t always have to be the case. For example, if you want to prove

$\forall x \in \mathbb R. \exists y \in \mathbb R. (x \not =0 \to x= \frac {1}{y})$

you do not want to prove

$\forall x \in \mathbb R. \exists y \in \mathbb R. \neg (x \not =0 \to x \not = \frac {1}{y})$

since it is equivalent to

$\forall x \in \mathbb R. \exists y \in \mathbb R. (x \not =0 \land x= \frac {1}{y})$

which is clearly false.

Answer 2

You said that the goal is to prove $P \Rightarrow Q$. We can't use $\lnot (P \Rightarrow \lnot Q)$ to prove $P \Rightarrow Q$ since they are not equivalent.

A proof for the forward direction would be something like:

If ¬(P ⇒ ¬Q):
    If P
        If ¬Q:
            If P:
                ¬Q.
            P ⇒ ¬Q.
            ¬(P ⇒ ¬Q).
            ⊥.
        ¬¬Q.
        Q.
    P ⇒ Q.

Now, consider the backward direction:

If P ⇒ Q:
    If P ⇒ ¬Q:
        If P:
            Q.
            ¬Q.
            ⊥.
        ¬P.

We just get that if $P \Rightarrow Q$, then if $P \Rightarrow \lnot Q$, then $\lnot P$. Hence, such a proof would be invalid.

Answer 3

TL;DR: If you are careful about any implicit quantifiers, then a proof by this technique is valid. But it has very limited usefulness. (And now that I have re-read this other answer I see that this point was already made, but I’ve already taken the trouble to write the answer below.)

---

The problem is that in many cases (perhaps all “interesting” cases), you cannot actually be sure that $P$ is true.

Suppose $P$ is “$3$ is even” and $Q$ is “$2$ is even.” Then $P\implies Q$ is true. But so is $P \implies \lnot Q$. So you can’t prove $P\implies Q$ this way even though it’s true.

You also have to beware of quantifiers, especially implicit quantifiers. For example, suppose $P$ is “$n$ is even” and $Q$ is “$n$ is a multiple of $6$.” Then when we write $P\implies Q$, we really mean, “For all $n$, $n$ is even implies $n$ is a multiple of $6$.” This is false. And when we write $P\implies \lnot Q$, we really mean, “For all $n$, $n$ is even implies $n$ is not a multiple of $6$.” This also is false. For example, consider $n=6.$ But if you prove that this statement is false, you have not proved that $P\implies Q$.

To prove that $P\implies Q$ for every $n$, you would need to prove $\lnot(P\implies \lnot Q)$ for every $n.$ If you can do that, then in fact you will have proved $P\implies Q.$ But keep in mind that while $P\implies Q$ is equivalent to $(\lnot P) \lor Q,$ $\lnot(P\implies\lnot Q)$ is equivalent to $P\land Q,$ which is often harder to prove and never easier. This may explain why this technique is not taught.