Let $T$ be the complete first-order arithmetic, with signature $0, 1, + , \dot{}$. Show that the natural numbers form an exsitentially closed model of T.

I am having some trouble proving this directly, I tried contradiction: Consider a structure $\mathcal B \supseteq \mathbb N $ and an existential formula $\phi(\bar x)=\exists y $ $ \psi(\bar x,y) $ such that $\mathcal B \vDash \phi(\bar x) $ but $\mathbb N \nvDash \phi(\bar x) $. Equivalently $$ \mathbb N \vDash \forall y\neg \psi(\bar x,y)$$ Or in other words, there is a system of equations which has solution in $\mathcal B$ but not in $\mathbb N$. Then I fail to reach a contradiction. How is that not possible? The book I'm taking this from (Hodges) states this as a "freak" example. Is it trivial maybe? Thanks for any help. (Sorry if some of my syntax is not too acurate).


Hint: If there were no parameters $\bar{x}$, then $\phi$ would be a sentence and so it would be true in $\mathcal{B}$ iff it is true in $\mathbb{N}$. Can you find a way to get rid of the parameters so you just have a sentence?

A full solution is hidden below.

Every element $n\in \mathbb{N}$ can be represented by a closed term, by just adding together $n$ copies of $1$. So replace each parameter appearing in $\phi$ by a closed term representing the same natural number and you get an equivalent formula $\phi'$ which now has no parameters. This $\phi'$ is a sentence and thus if it is true in $\mathcal{B}$, it must also be true in $\mathbb{N}$.

  • $\begingroup$ By sentence do you mean closed formula? $\endgroup$ – I.Padilla Jun 24 '17 at 2:28
  • $\begingroup$ Yes, "sentence" and "closed formula" are synonyms. $\endgroup$ – Eric Wofsey Jun 24 '17 at 2:29

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.