How do proofs guarantee the structure of the statement?

Question

In my math class, we are learning about direct proofs. Our lecturer tells us that you can prove an implication, by assuming the antecedent and then showing that the consequent must be true as well. But I am confused about two things. Namely

1. Where does this "rule" come from?
2. Why is it appropriate to deduce this relationship from this simple "checking"?

For (2), suppose that there is a true statement $P\implies Q$. A direct proof assumes $P$ and then shows $Q$ as well. But why does this infer specifically implication, rather than, $P \land Q$, since the only situation that was checked is shared by both those statements i.e. $P$ true and $Q$ true?

Answer 1

It's called the Deduction Theorem which is a theorem (or more properly, a "metatheorem", a theorem about theorems) from mathematical logic.

It establishes that if you have a formal proof of the implication $P\to Q$, then you can modify it to obtain a formal proof of $Q$ that starts from the additional assumption of $P$; and conversely, that if from the additional assumption of $P$ you can construct a formal proof of $Q$, then this proof can be used to construct a formal proof of $P\to Q$.

Thus, proving $P\to Q$ is equivalent to proving $Q$ from the additional assumption of $P$.

Answer 2

Regarding the relation between the implication $P \implies Q$ and the conjunction $P \wedge Q$ that you bring up at the end of your post, what you are observing is that $$(P \wedge Q) \implies (P \implies Q) $$ which you can verify easily using a truth table.

However, the other direction does not hold: $$(P \implies Q) \, \, \, \not{\!\!\!\!\!\!\implies} (P \wedge Q) $$ which you can also verify using a truth table: in the case that $P$ is false, the implication $P \implies Q$ is automatically true --- this is the Famous Case of Vacuous Truth. But the conjunction $P \wedge Q$ is false.

Answer 3

This proof technique is called a conditional proof: You assume $P$, derive derive $Q$, and then point to that 'subproof' and say: Aha! so we have $P \to Q$.

OK, so you have 2 questions. If we assume $P$ and derive $Q$, why can we conclude with $P \to Q$ ... and why can we not conclude $P \land Q$?

Let's do them one at a time.

Why can we conclude $P \to Q$?

Intuitively/conceptually/inoformally this makes sense because the conditional proof shpows that if you assume $P$, then you can derive $Q$, or in short: If $P$ then $Q$ ... which we symbolize as $P \to Q$

More formally, what is going on here is this. Suppose you are in the middle of a proof and you have a set of statements $\Gamma$. These statments are iether statements you started out with as premises, and/or statements that you have derived up to this point. Now, suppose you make an assumption $P$, and show that you can derive $Q$. Of course, in the derivation of $Q$, you probably used $P$, but you could also have used statements from $\Gamma$ that you already had. So, what you really showed is that $Q$ is a logical consequence of the set of statements $\Gamma \cup P$. SO what that means is that it is impossible for all of the statements in $\Gamma \cup P$ to be true, while $Q$ is false. OK, so now let's assume that all statements in $\Gamma$ are true. That means that it is impossible for $P$ to be true and $Q$ to be false. But since that is the only way for $P \to Q$ to be false, it must be the case that $P \to Q$ is true. In other words, if all statements in $\Gamma$ are true, then $P \to Q$ must be true as well. And of course that is what you obtain thanks to the conditional proof: you started with $\Gamma$, but you can now add $P \to Q$.

OK, and now: why can we not conclude $P \land Q$?

Again, first informally: The conditional proof method assumes $P$. But that of course is not the same as saying that $P$ is in fact the case. Or maybe better put: if you are in the middle of a proof and have proven a bunch statements $\Gamma$, the assumption or $P$ is not seeing that $P$ is true, but rather it asks: "OK, so what would happen if $P$ were to be true in addition to all this?". But that is different from saying that we have $P$ just because we got to $\Gamma$. And while $Q$ would be true if $P$ were to be true, that is also not the same as saying that we can conclude that $Q$we have shown $Q$ to be true, period.

A little more technically, let's demonstrate why concluding $P \land Q$ is a mistake. Well, consider this. Suppose we have the following statements:

$D \to L$, e.g. "If I am a dog, I have 4 legs" $L \to \neg H$, e.g. "If I have 4 legs, I am not a human"

From this, we should be able to conclude $D \to \neg H$ ("if I am a dog, I am not a human") .. and we do this through a conditional proof: Let's assume that I I would be a dog: $D$. OK, then we can combine that with $D \to L$ to get $L$: I have 4 legs. And then we can combine that with $L \to \neg H$ to get $\neg H$: I am not a human. So using the rule, we indeed get: $D \to \neg H$: "If I am a dog, then I am a human". All makes sense, right?

OK, but what if we were to be able to conclude $D \land C$? Then suddenly we have conclude that I am a dog, and that I am not human!! That should be wrong

And to do this really technically: Does $D \land \neg H$ follows from $D \to L$ and $L \to \neg H$? No, because when $D$ and $L$ are false, but $H$ is true, then $D \to L$ and $L \to \neg H$ are both true, but $D \land \neg H$ is false.

Answer 4

The assertion

If it is raining then the streets are wet.

is true

but

It is raining and the streets are wet.

may or not be. What's the weather right now?

Answer 5

Arturo has already given the formal answer for why this method of proof is correct. Let me offer an informal explanation for why.

It helps to first consider the truth table of $P\to Q$: \begin{array}{c|c|c} P & Q & P\rightarrow Q \\ \hline F & F & 1 \\ F & T & 1 \\ T & F & 0 \\ T & T & 1 \end{array} Now consider the implication

If the Euler-Mascheroni constant $\gamma$ is rational, then $\gamma+1$ is rational.

(It does not matter if you don't understand the definition of $\gamma$. For our purposes, it just a real number, approximately equal to $0.577$.)

The implication would be false in the situation that $\gamma$ is rational, and $\gamma+1$ is irrational. Otherwise, it would be true. Now, even the top mathematicians can't work out whether $\gamma$ is rational or not. Nevertheless, I claim that we can prove that the implication holds.

First, suppose that $\gamma$ is irrational. Then, $P=F$, and so $P\to Q$ holds, regardless of whether $\gamma+1$ is rational or not – that is, regardless of whether $Q$ is true or false.

Second, suppose that $\gamma$ is rational. Then, we can write $\gamma$ as $p/q$, where $p$ and $q$ are integers and $q\neq0$. Hence, $$\gamma+1=\frac{p}{q}+1=\frac{p}{q}+\frac{q}{q}=\frac{p+q}{q} \, ,$$ and so $\gamma+1$ must also be rational.

Thus, regardless of whether $\gamma$ is rational or irrational, we know that the implication is true.

Now notice that in our proof, we could have ignored the possibility that $\gamma$ is irrational. The reason is that this corresponds to the case $P=F$, and looking at the truth table, the implication $P\to Q$ always holds in this situation, regardless of what $Q$ is.

More generally, to prove $P\to Q$, we could try to verify it in two different cases: (i) in the situation that $P$ is false, and (ii) in the situation that $P$ is true. However, since $P\to Q$ must hold in case (i), we can shorten our proofs by solely focusing on case (ii). That is, we suppose that $P$ is true.

Answer 6

But why does this infer specifically implication, rather than, P∧Q, since the only situation that was checked is shared by both those statements i.e. P true and Q true?

Nowhere in the proof did we check/show that P is actually true: we merely assumed it.

Neither we did check/verify that Q is actually true: we derived Q under the assumption of P, in other words, our proof was merely that P implies Q, not that Q is true.

You can also think of it like this: we have proved that if P is not false, then Q must be true. After all, if P is actually false, then our statement $(P{\implies}Q)$ is not making any claim about Q's truth!

Yet another way to think of it is this: we have proved that either P is false, or Q is true.

Indeed, all three boldfaced statements are logically equivalent to one another. (To fully convince yourself of this, just compare their truth tables.)