1
$\begingroup$

I'm trying to solve the exercise 2.3.1 of Chang-Keisler book "Model Theory".

If $\phi(x_1, \cdots, x_n)$ is a complete formula in a theory $T$ with respect to $x_1,\cdots, x_n$, then $\exists x_n \phi (x_1, \cdots, x_{n-1}, x_n)$ is a complete formula in $T$ with respect to $x_1, \cdots, x_{n-1}$.

By a complete formula, we mean that for all formula $\psi(x_1,\cdots, x_n)$, we have exactly one between $T \vdash \phi \rightarrow \psi$ and $T \vdash \phi \rightarrow \neg \psi$.

I have no idea how to approach this problem. Help?

$\endgroup$
2
$\begingroup$

Let $\psi(x_1,\ldots,x_{n-1})$ be a formula. $\psi$ is trivially also a formula in $x_1,\ldots,x_n$ with no dependence on $x_n$, which I will also denote by $\psi$. Let $\tilde{\phi}(x_1,\ldots,x_{n-1})=\exists x_n \phi(x_1,\ldots,x_n)$.

Then we have either $T\vdash\phi \to \psi$ or $T\vdash \phi \to \lnot \psi$ since $\phi$ is complete. Suppose we have $T\vdash \phi \to\psi$, then assuming $\exists x_n \phi(x_1,\ldots,x_n)$, we have $\psi(x_1,\ldots,x_{n-1},x_n)$, which is equivalent to $\psi(x_1,\ldots,x_{n-1})$, since $\psi$ doesn't depend on $x_n$. Thus given $T\vdash \phi \to \psi$, we have $T\vdash \tilde{\phi}\to \psi$.

Symmetrically, if we have $T\vdash \phi\to\lnot\psi$, we know $T\vdash \tilde{\phi}\to \lnot\psi$. Thus either $T\vdash \tilde{\phi}\to \psi$ or $T\vdash \tilde{\phi}\to \lnot \psi$. Therefore $\tilde{\phi}$ is complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.