# Thread: Fol 6

1. ## 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.

2. ## 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.

3. ## Re: Fol 6

Originally Posted by logics
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.