Proofs involving negations and conditionals

[jfierro]

0. Background

First and foremost, this is a proof-reading request. I'm going through Velleman's "How To Prove It" because I found that writing and understanding proofs is a prerequisite to serious study of mathematics that I did not meet. Unfortunately, the book is very light on answers to its exercises and there is no solution manual available for purchase. Also, I understand that the best (and only?) way of learning to write proofs is by getting feedback from actual human beings. For what it's worth, I have an engineering degree's curriculum worth of math.


1. Homework Statement

Exercise 3.2.2. This problem could be solved by using truth tables, but don't do it that way. Instead, use the methods for writing proofs discussed discussed so far in this chapter. (See Example 3.2.4.)

1. Suppose $P \rightarrow Q$ and $R \rightarrow \neg Q$ are both true. Prove that $P \rightarrow \neg R$ is true.
2. Suppose that $P$ is true. Prove that $Q \rightarrow \neg (Q \rightarrow \neg P)$.

Homework Equations

At this point Velleman has introduced sentential and quantificational logic. He has talked about a few techniques that can be used to tackle proofs involving conditionals and negations, including proof by contradiction and contrapositive, how one can use the givens of a problem to infer other givens via inference rules such as modus ponens and modus tollens, etc. For example, he says that to prove a statement of the form $P \rightarrow Q$, one can assume that P is true and then prove Q.

The Attempt at a Solution

The first one is rather simple:

• Suppose $P$ is true. Then, since $P \rightarrow Q$, it follows that $Q$ is true. By the contrapositive of $R \rightarrow \neg Q$, we know that $Q \rightarrow \neg R$. Therefore, $P \rightarrow \neg R$.

The second one I found at least 3 ways of proving, so I'm most interested in input on this one. Which one would be better? Are there other, better ways of proving it?

• (By assuming the antecedent is true and proving the consequent. Contrapositive.) Suppose $Q$ is true. Then $\neg (Q \rightarrow \neg P)$ is also true since it is equivalent to $Q \wedge P$ and we know $P$ is true. Therefore, if $Q$, then $\neg (Q \rightarrow \neg P)$.

• (By contrapositive.) We will prove $Q \rightarrow \neg (Q \rightarrow \neg P)$ by its contrapositive $(Q \rightarrow \neg P) \rightarrow \neg Q$. Suppose $Q \rightarrow \neg P$ is true. Since we know $P$ is true, it cannot be that $Q$ is true (again by contrapositive). Therefore, $(Q \rightarrow \neg P) \rightarrow \neg Q$.

• (By contradiction.) Assume $\neg (Q \rightarrow \neg (Q \rightarrow \neg P))$ is true. This is equivalent to saying that $Q \wedge (Q \rightarrow \neg P)$ is true. Thus, both $Q$ and $Q \rightarrow \neg P$ must be true. But since $Q \rightarrow \neg P$, we have $\neg P$, which is a contradiction. Therefore, it cannot be the case that $Q \rightarrow \neg (Q \rightarrow \neg P)$ is false.

Thanks.

 

[jbunniii]

All of your proofs look fine to me. For the second statement, I don't see any reason to prefer one of your three proofs over another. It's a matter of taste. I like the middle proof (contrapositive) slightly better because it doesn't require me to remember how to negate $A \to B$. But they're all valid and easy to understand. Nice job finding several proofs of the same statement - doing so can often provide additional insight into the problem.

 

[jfierro]

Thanks a lot. I realize the proofs are very basic so there wasn't much room for me to screw up. I just exercise 3.2.8 which was a bit more challenging and I'll post that in a new thread soon.