Results 1 to 3 of 3

Math Help - Not logical consequence (First-order logic)

  1. #1
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39

    Not logical consequence (First-order logic)

    Hello,
    the problem is to show that P isn't logical consequence of Q:
     P = ( \forall x) ( \exists y)r(x,y)
     Q = ( \exists y) ( \forall x)r(x,y)

    r stands for relation.

    Maybe some kind of proof by contradiction would work, but I couldn't make one.

    Any help is appreciated. Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Greg98 View Post
    Hello,
    the problem is to show that P isn't logical consequence of Q:
     P = ( \forall x) ( \exists y)r(x,y)
     Q = ( \exists y) ( \forall x)r(x,y)

    r stands for relation.

    Maybe some kind of proof by contradiction would work, but I couldn't make one.

    Any help is appreciated. Thanks in advance!
    I think you are mistaken: Q\Rightarrow P is valid. Maybe you want to prove that P\Rightarrow Q is not valid, i.e. that Q is not a consequence of P?
    If so I would suggest coming up with a countermodel, i.e. a model in which P is true but Q is not (take, for example, the natural numbers as domain and r(x,y) := x<y).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Edit: too late.

    In fact, P is the logical consequence of Q. Indeed, assume Q and take a y0 that works for all x, i.e., a y0 such that for all x we have r(x, y0). To prove "for all x there exists a y such that r(x, y)", fix an arbitrary x and let y = y0.

    It is Q that is not the logical consequence of P. This can be shown by making a counter-model. For example, the domain is the set of people and r(x,y) means "y is x's mother".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. First order logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 10th 2011, 07:10 AM
  2. First order Logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 16th 2011, 04:41 AM
  3. First order Logic!
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: January 3rd 2011, 10:55 AM
  4. Replies: 2
    Last Post: June 10th 2010, 02:38 PM
  5. Replies: 3
    Last Post: January 21st 2010, 07:45 AM

Search Tags


/mathhelpforum @mathhelpforum