Results 1 to 3 of 3

Thread: Fol 6

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 6

    Enderton problem 4 in Section 2.5

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

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

    Suppose to the contrary, towards a contradiction, $\displaystyle \Gamma \vdash \bot$. Then, we have both $\displaystyle \Gamma \vdash \phi$ and $\displaystyle \Gamma \vdash \neg \phi$ for any wff $\displaystyle \phi$. I am looking for a counterexample $\displaystyle \phi$, which is either $\displaystyle \Gamma \vdash \phi$ or $\displaystyle \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 $\displaystyle \Gamma \vdash \neg Pv_2$ (by axiom group 2 $\displaystyle \neg \forall v_1Pv_1 \rightarrow \neg Pv_2$ of Enderton's book and modus ponens) and $\displaystyle \Gamma \vdash Pv_2$ by assumption, which means $\displaystyle \Gamma \vdash \bot$, i.e., inconsistent.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Fol 6

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

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


/mathhelpforum @mathhelpforum