completeness theorem in Enderton's book

154 Views Asked by At

I'm reading completeness theorem part(Section 2.5) in Enderton's Mathematical Introduction to Logic.

proving $\vDash_{\mathfrak{A}}\varphi^{*}[s]$ iff $\varphi\in\Delta$ for all formula, Enderton writes in the universal quantification part(139p)

($\varphi^{*}$ : replacing equality symbol to $E$ in $\varphi$ where $<t,u>\in E^{\mathfrak{A}}$ iff $u=t\in\Delta$. $\Delta$ is maximal consistent set containing $\Gamma$ originally consistent, and formulas the form of $\neg\forall x \varphi \rightarrow \neg\varphi_{c}^{x}$)

$\vDash_{\mathfrak{A}}\forall x \varphi^{*}[s] \Rightarrow \vDash_{\mathfrak{A}}\varphi^{*}[s(x|c)]$

$\Rightarrow\vDash_{\mathfrak{A}}({\varphi}_{c}^{x})^{*}[s]$

thus $\varphi_{c}^{x}\in\Delta$(by inductive hypothesis).

I don't understand why last step is justified by indutive hypothesis. I thought inductive hypothesis for this case is only $\vDash_{\mathfrak{A}}\varphi^{*}[s]$ iff $\varphi\in\Delta$.

1

There are 1 best solutions below

1
On BEST ANSWER

See page 138 :

The other claim, that

$\mathfrak A \vDash \varphi^\ast [s]$ iff $\varphi \in \Delta,$

we prove by induction on the number of places at which connective or quantifier symbols appear in $\varphi$.

Thus in the step above, the formula $(\varphi^x_c)^\ast$ has one connective or quantifier less than $\forall x \varphi^\ast$; we have only "removed" the outer $\forall$.