Vacuous "If then" statements: Can you use direct proofs?

[HyperActive]

Hi,
I'm comfortable using a direct proof to prove $P → Q$ type statements when I have a $P$ that is either always true (e.g $x=x$) or can be true (e.g. $x > 3$).

But what about when $P$ is definitely false, (e.g. $x \neq x$), or definitely false in relation to an earlier statement (e.g. If we've already been given the fact that we're dealing with a group G, and $P$ is the statement "there does not exist an identity element in G")? Can you use direct proof then? By direct proof I mean proving the statement by assuming $P$ is true, then showing through legal logical inferences that $Q$ must be true as well.

I hope that's made sense. Thanks :)

 

[Stephen Tashi]

The logical principles that deal with quantifiers such as "for each " and "there exists" is more complicated than the logic that deals with unquantified statements. Dealing with the logic of quantifiers employs a variety of rules such as "universal generaiization" and "universal instantiation". You say you are familiar with the logic involved in showing $P \rightarrow Q$, but you mention a case involving the quantifier "there exists". The proof might not actually be as simple saying that an implication is vacuously true. Give a specific example of what you want to prove.

What's unclear to me is the "scope" of the quantifiers. For example, the case of

( for each x, P(x)) implies ( not ( for each y, Q(y)))

is different than the case

for each x, for each y ( P(x) implies (not Q(y)) )

 

[HyperActive]

Ok, I see. First of all, thank you for your response!
I understand that the proof might not just be as simple as saying it's vacuously true, but that's not necessarily how I'd like to prove these statements anyhow. Maybe I had better give some context for my question. In the math courses I've done, I've seen problems that go like this: "Assume P(x). Prove Q(x)." And I'd usually have a good strategy for proving whatever it is (although that strategy would be different in different cases, for instance as you say there'd be a difference depending on the quantifiers involved).

But now I'm faced with problems that go like this: "Prove that if P(x), then Q(x)". My question is basically this: Can I use the same proof strategy I would have used had the question been phrased in "Assume P(x). Prove Q(x)" format?

The only potential issue I can see with this is if P(x) is always false, because in both cases above P(x) is assumed to be true.

 

[Stephen Tashi]

Can I use the same proof strategy I would have used had the question been phrased in "Assume P(x). Prove Q(x)" format?

If you are doing work for the average math instruction, you can. I think only a person who focuses on formal logic would see the distinction you are making. There is one "rule" of logic called modus ponens which says "Given P implies Q and given P is true, conclude Q is true". There is a different "rule" which says "Assume P. Derive Q by various rules. Conclude that P implies Q". I think you are asking if the second rule is applicable when P is false.

I don't know the technical answer to that. We need a logician!. The way I stated the rule, you can apply it when P is false. But instead of stating the rule as "Assume P..." , should I have said "P is (definitely) true. Q is derivable, therefore P implies Q"?

 

[HyperActive]

There is a different "rule" which says "Assume P. Derive Q by various rules. Conclude that P implies Q". I think you are asking if the second rule is applicable when P is false.

Thank you! That's exactly what I'm asking, and that's a much clearer way to phrase it.
I guess we do need a logician...

 

[PeroK]

Thank you! That's exactly what I'm asking, and that's a much clearer way to phrase it.
I guess we do need a logician...

I think what you're asking is this, for example:

If we assume that $q \in \mathbb{Q}$ and $q^2 = 2$ can we show that directly that $q=0$

This is, of course, vacuously true, but finding a direct proof might be difficult.

Also, the last statement can be replaced with anything well-defined.

 

[HyperActive]

Yup, that's a good example.
You say that

finding a direct proof might be difficult.

Let's say we found one. Would such a proof be valid? Is direct proof (assuming a statement is true, deriving another statement, and concluding that the first statement implies the second) valid with a first statement like q^2 =2?

Thanks!

 

[Stephen Tashi]

The Wikipedia article on "List of Rules for Inference" http://en.wikipedia.org/wiki/List_of_rules_of_inference calls the rule ""Deduction theorem" and says, earlier in the article, that in "Discharge rules" $\varphi$ can be a "temporary assumption".

The "talk" page for the article http://en.wikipedia.org/wiki/Talk:List_of_rules_of_inference has the usual complex kind of discussions that arise when dealing with logic.

 

[Erland]

Let's say we found one [proof of q=0 from the assumptions q ∈ Q and q²=2]. Would such a proof be valid? Is direct proof (assuming a statement is true, deriving another statement, and concluding that the first statement implies the second) valid with a first statement like q^2 =2?

Thanks!

Such a proof is certainly valid if the derivation is valid. If you prove P → Q by assuming P and deriving Q from this, and all steps in this derivation are valid, then you have proved P → Q. It does not matter if P happens to be true or not. Of course, if P is false, then P → Q is automatically true, but this does not disqualify the previous proof, whose result then conforms with this.

 

[TeethWhitener]

You can actually go further than this with a neat little trick. Assume $P$. From this assumption derive $Q$. Then go back and assume $\neg P$ and from this assumption derive $Q$. In this case, instead of proving $P \rightarrow Q$, you've proven $Q$ unconditionally. Here's the reason:

In symbolic terms, you've proven that $(P \rightarrow Q) \wedge (\neg P \rightarrow Q)$ is true. Since $P$ is always either true or not true, one of the members of the conjunction will automatically be true (i.e., if $P$ is true, then $\neg P$ is false and therefore $\neg P \rightarrow Q$ must be true. On the other hand, if $\neg P$ is true, then $P \rightarrow Q$ must be true for analogous reasons). Since you've already proven that the conjunction is true, this can only hold if each side of the conjunction is true. But if, e.g., $P$ is true (and therefore $\neg P \rightarrow Q$ is true), then the only way for the other side of the conjunction, $P \rightarrow Q$, to be true is if $Q$ is true unconditionally.