Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 1, 2014 #1
    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 :)
     
  2. jcsd
  3. Dec 1, 2014 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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 [itex] P \rightarrow Q [/itex], 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)) )
     
  4. Dec 1, 2014 #3
    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.
     
  5. Dec 1, 2014 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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"?
     
  6. Dec 2, 2014 #5
    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...
     
  7. Dec 2, 2014 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  8. Dec 2, 2014 #7
    Yup, that's a good example.
    You say that

    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!
     
  9. Dec 2, 2014 #8

    Stephen Tashi

    User Avatar
    Science Advisor

  10. Dec 6, 2014 #9

    Erland

    User Avatar
    Science Advisor

    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.
     
  11. Dec 6, 2014 #10

    TeethWhitener

    User Avatar
    Science Advisor
    Gold Member

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

    In symbolic terms, you've proven that [itex](P \rightarrow Q) \wedge (\neg P \rightarrow Q)[/itex] is true. Since [itex]P[/itex] is always either true or not true, one of the members of the conjunction will automatically be true (i.e., if [itex]P[/itex] is true, then [itex]\neg P[/itex] is false and therefore [itex]\neg P \rightarrow Q[/itex] must be true. On the other hand, if [itex]\neg P[/itex] is true, then [itex]P \rightarrow Q[/itex] 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., [itex]P[/itex] is true (and therefore [itex]\neg P \rightarrow Q[/itex] is true), then the only way for the other side of the conjunction, [itex]P \rightarrow Q [/itex], to be true is if [itex]Q[/itex] is true unconditionally.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Vacuous "If then" statements: Can you use direct proofs?
  1. Statement Proof. (Replies: 16)

  2. Vacuous quantification (Replies: 3)

  3. Direct proofs help (Replies: 1)

Loading...