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

I Implication problem

Tags:
  1. Sep 13, 2018 #1
    I just saw this proof.... And, I don't understand why this is true. How am I supposed to think about problems like this one?

    Edit:
    Here's another one:
    The only steps here I understand are 1 to 5. I don't know why 6 and 7 are true.
     
  2. jcsd
  3. Sep 13, 2018 #2

    Delta²

    User Avatar
    Homework Helper
    Gold Member

    We know that an implication A→B is true when A and B are both true. So apply this for A= q B=r (have proved that q and r are true from steps 1-5), and then for A=p, B=q→r
     
  4. Sep 13, 2018 #3

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Line 2 makes an assumption, and thereby opens what is called a conditional proof (CP). The conditional proof is closed by discharging the assumption that made it, at a later line. We'll come to what that means shortly.

    Conditional proofs can be nested within each other. Above there are two CPs, one commencing at 2 and ending at 7, the other commencing at 3 and ending at 6. The last line of a CP closes the proof by asserting A->B, where A was the assumption that opened the proof and B is the statement immediately before the closing line. Closing the proof 'discharges' the assumption A, which means that A is no longer assumed but, in its place, we have A->B, which is valid everywhere from there on within the next enclosing CP.
    All interim results deduced inside a CP are invalid outside it, except for the closing statement.

    So line 6 closes the inner CP giving the result (3)->(5)
    Then line 7 closes the outer CP giving the result (2)->(6)

    The first example is actually written in a confusing manner. A better way to write it is:
    (1) Given: b
    (2) Suppose: a
    (3) b (from 1)
    (4) By implication with (3) and (1), a→b
    Written that way, we see that a CP is opened at (2) and closed at (4) with the statement (2)->(3).

    It's possible to loosen the rules for closing CPs so that the antecedent of the closing statement (the statement after the arrow ->) can be any statement that is in scope at that point. That is the approach that was taken in the first example. But that requires explicitly laying out the scoping rules, which may be more complex than you want to get.
     
  5. Sep 16, 2018 at 7:48 AM #4
    I am still having issues understanding this, so we may have to go deeper.

    For instance, in the first proof, we know b is true, and we are assuming a is true as well. Why does this imply a→b? Why not b→a?
     
  6. Sep 16, 2018 at 9:55 AM #5

    FactChecker

    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    These are sort of degenerate implications. In the first example, once you know that b is always true, anything will imply b. Remember that a -> b is equivalent to "b or not a". Since b is given, "b or not a" is always true no matter what a is. So a->b is always true no matter what a is. The second example is more complicated but similar.
     
    Last edited: Sep 16, 2018 at 5:54 PM
  7. Sep 16, 2018 at 12:23 PM #6

    verty

    User Avatar
    Homework Helper

    Does this make sense?

    Given ##p \lor q##:
    Suppose ##\lnot p##.
    ##q##
    ##\lnot p \to q##
     
  8. Sep 16, 2018 at 4:21 PM #7

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It is the first and not the second because that's how the inference rule for conditional proofs works. We open a proof at line n with statement P, and close it at statement m>n with the statement P->Q, where Q is the statement on line m-1 (or, more generally, any statement made between lines 1 and m-1 inclusive, excluding statements that were made on lines interior to conditional proofs that were closed before line m+1. All lines of a CP are 'interior to' the CP, except its last line).

    It's not clear whether your uncertainty is about how the inference rule was applied in this particular case, or in why the inference rule is written that way.
     
  9. Sep 17, 2018 at 2:14 AM #8

    Stephen Tashi

    User Avatar
    Science Advisor

    The notation you are using distinguishes between being "given" a statement and "assuming" a statement. In many contexts of writing about mathematics, we don't make such a distinction. For example, if we are working a trigonometry word problem where certain information is "given", we might also say the information is "assumed".

    The material you are studying deals with reliable patterns of reasoning. In the particular pattern:
    Given B:
    Assume A:
    Conclude: A implies B

    We do not conclude A is true. We could conclude B is true because it is "given". That is the distinction being made between "given" and "assume".

    As other have noted, this pattern of reasoning is valid, but not very prominent in writing typical mathematical proofs. On a page of a mathematics text, certain definitions and theorems have been established on previous pages. It would be rare for an author to bother saying that some hypothesis on the page implies the results established on previous pages.


    The more common pattern is:
    Assume A
    Prove B (by some method)
    Conclude: A implies B

    In this pattern, we cannot conclude that A is true and we cannot conclude that B is true. We only conclude the implication is true.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted