Results 1 to 8 of 8
Like Tree2Thanks
  • 2 Post By emakarov

Math Help - First Order Logic: Prove that this equivalence is valid

  1. #1
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

    First Order Logic: Prove that this equivalence is valid

    "Consider the equivalence
    ∀x∃yφ(x, y) ↔ ∃y∀x φ(x, y)
    You can assume that φ has no free variables other than x and y.
    Show that one direction of this equivalence is valid (i.e. true in every structure/model). Prove this carefully."

    I have found out that the direction to the "left" is valid.
    So I am sure that this is valid: ∃y∀x φ(x, y) ∀x∃yφ(x, y)
    Now I have to prove it by showing that it's true in every structure/model.
    Can someone show me how this kind of proof is done?


    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: First Order Logic: Prove that this equivalence is valid

    It's important to understand the general idea: if one y make φ true for all x, then for every x there exists its own (in this case, that same) y that makes φ true.

    The proof depends on the definition of truth of a formula in a structure, which may vary slightly in different sources. Could you write the parts of the definition for formulas starting with ∀ and ∃?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

    Re: First Order Logic: Prove that this equivalence is valid

    First Order Logic: Prove that this equivalence is valid-logic-structure.jpg

    I am not sure if this is what you are thinking of (the two last lines in the image).
    The weird looking symbol is supposed to be structure/model.
    This is from the book "Logic and Structure" by Dirk van Dalen,
    the book that is used in my logic course.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: First Order Logic: Prove that this equivalence is valid

    The weird-looking symbol is the Fraktur letter A.

    My guess is that for every element a of the model carrier you consider a new constant \bar{a} and define the truth of formulas in the extended language where these constants are added.

    Suppose \mathfrak{A}\models\exists y\forall x\,\varphi(x, y). Then by (vii) there exists an b\in|\mathfrak{A}| such that \mathfrak{A}\models\forall x\,\varphi(x,\bar{b}). By (vi) this in turn means that for this particular b and for all a\in|\mathfrak{A}| we have \mathfrak{A}\models\varphi(\bar{a},\bar{b}). Again by (vii) for all a\in|\mathfrak{A}| we have \mathfrak{A}\models\exists y\,\varphi(\bar{a},y) and by (vi) \mathfrak{A}\models\forall x\exists y\,\varphi(x,y).

    It is important to understand why a similar argument cannot be used to show \mathfrak{A}\models\forall x\exists y\,\varphi(x,y)\to\exists y\forall x\,\varphi(x,y). By definition, \mathfrak{A}\models\forall x\exists y\,\varphi(x,y) means that for every a\in|\mathfrak{A}| there exists (its own) b\in|\mathfrak{A}| such that \mathfrak{A}\models\varphi(\bar{a},\bar{b}). However, we cannot swap meta-level (i.e., natural language) quantifiers to say that there exists a single b such that \mathfrak{A}\models\varphi(\bar{a},\bar{b}) for all a. Therefore, we cannot say \mathfrak{A}\models\forall x\,\varphi(x,\bar{b}): there is no such single b; each b exists only when a is given.
    Thanks from Zhai and jsndacruz
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,420
    Thanks
    1856

    Re: First Order Logic: Prove that this equivalence is valid

    You can't prove it for the very good reason that it is not true. For example, take \phi(x, y) be the statement [itex]x+ y= 0[itex]. Then the left side, that "for any x, there exist y such that x+ y= 0" is true: whatever x is take y= -x. But the right side say "there exist a y such that, for all x, x+ y= 0. But that is NOT true. For any given y, there exist an x such that x+ y= 0 but it is not true for all x.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

    Re: First Order Logic: Prove that this equivalence is valid

    Quote Originally Posted by HallsofIvy View Post
    You can't prove it for the very good reason that it is not true. For example, take \phi(x, y) be the statement [itex]x+ y= 0[itex]. Then the left side, that "for any x, there exist y such that x+ y= 0" is true: whatever x is take y= -x. But the right side say "there exist a y such that, for all x, x+ y= 0. But that is NOT true. For any given y, there exist an x such that x+ y= 0 but it is not true for all x.
    What is not true?
    This is not true: ∀x∃yφ(x, y) ↔ ∃y∀x φ(x, y)
    But this should be a valid statement (the one direction in the statement above):
    ∃y∀x φ(x, y) → ∀x∃yφ(x, y)
    That's what I figured out, and when it's true or valid, it can be proved
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: First Order Logic: Prove that this equivalence is valid

    Yes, ∃y∀x φ(x, y) → ∀x∃yφ(x, y) is valid, but ∀x∃yφ(x, y) → ∃y∀x φ(x, y) is not.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

    Re: First Order Logic: Prove that this equivalence is valid

    Quote Originally Posted by emakarov View Post
    Yes, ∃y∀x φ(x, y) → ∀x∃yφ(x, y) is valid, but ∀x∃yφ(x, y) → ∃y∀x φ(x, y) is not.
    Ye, it's actually a b-part of this problem and that is to find
    a counterexample for the direction that is not valid, which I have
    already completed.

    The proof you just wrote looks really familiar with something I had
    in the class, but what you wrote is far more understandable, and
    that's a good thing!
    Last edited by Zhai; May 9th 2012 at 02:26 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: August 21st 2011, 12:47 PM
  2. Equivalence with logic laws
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 12th 2010, 12:38 PM
  3. propositional logic equivalence proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 11th 2010, 01:20 AM
  4. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 10:03 AM
  5. Replies: 3
    Last Post: May 28th 2009, 11:11 AM

Search Tags


/mathhelpforum @mathhelpforum