Results 1 to 3 of 3

Math Help - Fol 6

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 6

    Enderton problem 4 in Section 2.5

    Let \Gamma = \{\neg \forall v_1 Pv_1, Pv_2, Pv_3, \ldots \}. Is \Gamma consistent? Is \Gamma satisfiable?

    The completeness theorem says that any consistent set of formulas is satisfiable. Therefore, we only need to show that \Gamma is consistent.

    Suppose to the contrary, towards a contradiction, \Gamma \vdash \bot. Then, we have both \Gamma \vdash \phi and \Gamma \vdash \neg \phi for any wff \phi. I am looking for a counterexample \phi, which is either \Gamma \vdash \phi or \Gamma \vdash \neg \phi, not both.

    Any help will be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Fol 6

    I think I solved it. Since \Gamma \vdash \neg Pv_2 (by axiom group 2 \neg \forall v_1Pv_1 \rightarrow \neg Pv_2 of Enderton's book and modus ponens) and \Gamma \vdash Pv_2 by assumption, which means \Gamma \vdash \bot, i.e., inconsistent.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Fol 6

    Quote Originally Posted by logics View Post
    Since \Gamma \vdash \neg Pv_2 (by axiom group 2 \neg \forall v_1Pv_1 \rightarrow \neg Pv_2 of Enderton's book and modus ponens)
    This is strange because \forall v_2\,(\neg \forall v_1\,Pv_1 \rightarrow \neg Pv_2) is not a tautology. It is equivalent to \forall v_2\,((\exists v_1\neg Pv_1)\to\neg Pv_2).

    I think \Gamma is satisfiable: consider P(x) to mean x>1 and s(v_i)=i on natural numbers.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum