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

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

3. ## Re: Fol 6

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