0
$\begingroup$

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<c, S0<c, SS0<c,\ldots \}$. 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.

$\endgroup$
1
$\begingroup$

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."

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

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.