# Proving that $\mathfrak{A}$ and $\mathfrak{N}$ are elementarily equivalent

This is an exercise problem in the textbook A Friendly Introduction to Mathematical Logic. The question is as follows:

Let $$\mathfrak{N}$$ be the usual structure of the language of number theory $$\mathcal{L}_{NT}$$. Let $$\Sigma$$ be the theory of $$\mathfrak{N}$$. Let $$\mathcal{L}$$ be a language given by $$\mathcal{L}=\mathcal{L}_{NT} \cup \{ c \}$$. Let $$\Theta=\Sigma\cup \{ 0. Let $$\mathfrak{A}'$$ be a model of $$\Theta$$. Now we define $$\mathfrak{A}=\mathfrak{A}'\upharpoonright_{\mathcal{L}_{NT}}$$. Prove that $$\mathfrak{A}$$ is elementarily equivalent to $$\mathfrak{N}$$.

My attempt:

In order to prove that $$\mathfrak{A}$$ is elementarily equivalent to $$\mathfrak{N}$$, we need to prove that theory of $$\mathfrak{A}$$ is $$\Sigma$$. Let's take $$\phi\in \Sigma$$. Then $$\phi\in\Theta$$. Thus, $$\Theta \vdash \phi$$ and by Soundness theorem, $$\Theta\models\phi$$. Since $$\mathfrak{A}'$$ is a model of $$\Theta$$, we have that $$\mathfrak{A}'\models\phi$$. Thus $$\mathfrak{A}\models \phi$$ as $$\phi$$ is a $$\mathcal{L}_{NT}$$ formula. Thus, $$\Sigma$$ is a subset of theory of $$\mathfrak{N}$$.

I am having trouble proving the other direction however. If I take a $$\phi$$ such that $$\mathfrak{A}\models\phi$$. Then I can say that $$\mathfrak{A}'\models \phi$$. But I am not really sure how to proceed after this.

Any hints will be appreciated.

HINT: $$\Sigma$$ is already "as big as possible" - if $$\mathfrak{A}'\models\varphi$$ for some $$\varphi\not\in\Sigma$$, there will be a "clash."

In more detail, suppose $$\mathfrak{A}'\models\varphi$$ but $$\mathfrak{N}\not\models\varphi$$. Can you think of a sentence related to $$\varphi$$ which $$\mathfrak{N}$$ does satisfy instead?

Its negation, $$\neg\varphi$$. Remember that by definition of the satisfaction relation we have $$\mathfrak{S}\not\models\eta\quad\iff\quad\mathfrak{S}\models\neg\eta$$ for every structure $$\mathfrak{S}$$ and every sentence $$\eta$$.

Now why would that be a problem?

If $$\mathfrak{N}\models\neg\varphi$$ then $$\neg\varphi\in\Sigma$$ so $$\mathfrak{A}'\models\neg\varphi$$. But this contradicts the assumption that $$\mathfrak{A}'\models\varphi$$.

Basically, what's going on here is that the theory of a structure is always a maximal consistent theory (with respect to the structure's language, that is), so there's no "room for improvement."

• "The theory of a structure is always a maximal consistent theory" is the takeaway here. – ashK Mar 17 at 12:10