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!

Nested Quantifiers Help Please

  1. Feb 2, 2016 #1
    1. The problem statement, all variables and given/known data
    Problem #5,
    20160202_195936.jpg
    2. Relevant equations
    Professor's handout, to show that this false: Show that for some x∈X there is no way to choose y∈Y such that P(x,y) is true. That is showΓ(∃x∃yP(x,y)) whic is equivalent to ∃x∀y(ΓP(x,y))
    3. The attempt at a solution
    So far I have appilied this definition, but my professor hasn't given me an example to follow to solve this... Would I have to solve the second part?
    20160202_195944.jpg
     
    Last edited by a moderator: Feb 3, 2016
  2. jcsd
  3. Feb 2, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    that's not correct.
    The statement we want to show false is ##\forall x\exists y(y^2<x+1)##, which is equivalent to ##\neg\exists x\neg\Big(\exists y(y^2<x+1)\Big)##.

    The negation of that is ##\exists x\neg\Big(\exists y(y^2<x+1)\Big)##.

    Can you find such an ##x##?
     
  4. Feb 2, 2016 #3
    So if we make (y^2<x+1) true than the Γ will make it false, correct? Like if I plug in 1 for x and y.
     
  5. Feb 2, 2016 #4
    20160202_204418.jpg
    Would this be correct?
     
  6. Feb 2, 2016 #5

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No that is not correct. Your step from the first to second line is invalid. In symbolic logic, you should always write the formal justification for each step. If you apply that discipline you will in most cases realise without assistance when you make an invalid step.
    Go back to my previous post, look at the last logical proposition, and think about what value of ##x## would satisfy ##
    \neg\Big(\exists y(y^2<x+1)\Big)## where the domain is the real numbers. It's actually very easy.
     
  7. Feb 3, 2016 #6
    Okay, I already turned it in. So basically I just had to prove when (y^2<x+1) is false,correct? So if I set x to 2 and y to 2, I would get 4<3 therefore making the statement false. The thing that confuses me is the not symbol, so it I made the statement false it would be not false, so true?
     
  8. Feb 3, 2016 #7

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. What you have to do is find a value of ##x## such that, for all ##y##, ##y^2## is not less than ##x+1##, ie that ##y^2## is more than or equal to ##x+1##. You cannot choose a single ##y##. The result has to hold for all ##y##.
    Can you think of a number that all squares of real numbers are more than or equal to (but, by the way, not all squares of complex numbers)?
     
  9. Feb 3, 2016 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    It looks right to me.
    In your last step in post 2 you had ....~∃y(P(x,y)). That converts to ...∀y(~P(x,y)) to get the form in the OP.
    Which form is more readily proven is another matter.
     
  10. Feb 3, 2016 #9

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The first step is invalid. It selects specific values for ##x## and ##y##, which is only valid if those variables are universally quantified (using the Axiom Schema of Specification). They are existentially quantified.
     
    Last edited: Feb 3, 2016
  11. Feb 3, 2016 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Ok, I thought you were objecting to the last part.
    I suspect the erroneous statement was a typo for ∃x(~∃y( etc.
     
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: Nested Quantifiers Help Please
  1. Concentration problems (Replies: 2)

Loading...