1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Direct proofs

  1. Nov 27, 2016 #1
    1. The problem statement, all variables and given/known data
    What is the first step in proving a proposition of the form ##\forall x (P(x) \implies Q(x))##

    2. Relevant equations


    3. The attempt at a solution
    So this isn't exactly a homework question, but I am just trying to figure things out. So say that we have a conjecture of the form ##\forall x (P(x) \implies Q(x))##. In my textbook, it says that to (formally) prove a proposition such as this, we first prove ##P(c) \implies Q(c)##, where c is an arbitrary element of the domain of discourse, and then by the inference rule of universal generalization, conclude that ##\forall x (P(x) \implies Q(x))##.

    However, I confused as to how to get to the second step. First we begin with ##\forall x (P(x) \implies Q(x))##. So to get to ##P(c) \implies Q(c)## don't we need to apply universal instantiation? And to apply universal instantiation, don't we first need to know that ##\forall x (P(x) \implies Q(x))## is true? Isn't that kind of circular?
     
  2. jcsd
  3. Nov 28, 2016 #2

    Mark44

    Staff: Mentor

    I don't see that a second step is needed. Since c is chosen arbitrarily, and ##P(c) \implies Q(c)##, you can conclude that ##P(x) \implies Q(x)## for any x in the domain you're considering.
     
  4. Nov 29, 2016 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The statement ##P(x) \implies Q(x)## might be a theorem of some kind. Then establishing ##P(c) \implies Q(c)## amounts to giving a proof of the theorem. That may be easy, or it might be very difficult.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Direct proofs
  1. Direct Proof (Replies: 1)

  2. Direct Sum Proof (Replies: 1)

  3. Simple Direct Proof (Replies: 3)

  4. Direct proofs help (Replies: 5)

Loading...