Recall that the theory of $\mathfrak{A},$ written as $Th\, \mathfrak{A},$ is the set of all sentences true in $\mathfrak{A}.$

In Enderton's A Mathematical Introduction to Logic, page $152,$ the author provided the following example.

Example: Consider the structure $$\mathfrak{R} = (\mathbb{N};0,S,<,+,\cdot).$$ We claim that there is a countable language $\mathfrak{R}_0,$ elementarily equivalent to $\mathfrak{R}$ (so that $\mathfrak{R}_0$ and $\mathfrak{R}$ satisfy exactly the same sentences) but not isomorphic to $\mathfrak{R}.$

Proof: We will construct $\mathfrak{R}_0$ by using the compactness theorem. Expand the language by adding a new constant symbol $c.$ Let $$\Sigma=\{0<c,S0<c,SS0<c,...\}.$$ We claim that $\Sigma\cup Th \,\mathfrak{R}$ has a model. For consider a finite subset. That finite subset is true in $$\mathfrak{R}_k=\{\mathbb{N};0,S,<,+,\cdot,k\}$$ where $k=c^{\mathfrak{R}_k}$ for some large $k.$ So by the compactness theorem $\Sigma\cup Th\, \mathfrak{R}$ has a model.

By the Lowenheim-Skolem Theorem, $\Sigma\cup Th\,\mathfrak{R}$ has a coutable model $$\mathfrak{M} = (|\mathfrak{M}|; 0^{\mathfrak{M}},S^{\mathfrak{M}}, <^{\mathfrak{M}}, +^{\mathfrak{M}}, \cdot^{\mathfrak{M}}, c^{\mathfrak{M}}).$$ Let $\mathfrak{R}_0$ be the restriction of $\mathfrak{M}$ to the original language: $$\mathfrak{R}_0 = (|\mathfrak{M}|;0^{\mathfrak{M}},S^{\mathfrak{M}},<^{\mathfrak{M}},+^{\mathfrak{M}},\cdot^{\mathfrak{M}}).$$ Since $\mathfrak{R}_0$ is a model of $Th\, \mathfrak{R},$ we have $\mathfrak{R}_0\equiv \mathfrak{R}.$ We leave it to the reader to verify that $\mathfrak{R}_0$ is not isomorphic to $\mathfrak{R}.$

I have two questions regarding the proof above.


$(1):$ Given a finite subset of $\Sigma\cup Th\, \mathfrak{R},$ why is it true in $$\mathfrak{R}_k=\{\mathbb{N};0,S,<,+,\cdot,k\}?$$ $(2):$ How to show that $\mathfrak{R}_0$ is not isomorphic to $\mathfrak{R}?$

  • $\begingroup$ For large enough $k$, $k> S...S0$ for all $S...S0$ appearing in the finite fragment in question. As for the isomorphism, they don't satisfy the same infinitary sentences; if you want a proof not using those, simply note that a morphism sends $0$to $0$, $S0$ to $S0$ and so on, so that $c$ is not in the image of said morphism $\endgroup$ – Max Mar 2 '18 at 12:33
  • $\begingroup$ @Max: I get your first sentence on why the finite subset in question is true. But I do not quite get your second part. Perhaps you can write an answer? $\endgroup$ – Idonknow Mar 2 '18 at 12:49
  • 3
    $\begingroup$ Here's an outline: Suppose there is an isomorphism $f$. Then $c = f(SS....S0)$ for [the interpretation of] some term $SS....SS0$. But the non-standard structure satisfies $SS...SS0<c$ and ($x<y$ implies $x<> y$) $\endgroup$ – Ned Mar 2 '18 at 14:12

(1) as explained in the comments, for a finite segment of this theory, there are only finitely many axioms of the form $c> S...S0$. Calling "$k$th axiom" the axiom $c> S...S0$ with $k$ $S$'s, taking a large enough $k$, bigger than all $j$'s such that the $j$th axiom appears in the finite segment, you can interpret $c$ as $k+1$, and then your structure will be a model of the given finite segment.

(2) Let $f : \mathfrak{R} \to \mathfrak{R}_0$ be any morphism. Then by definition, $f(S...S0) = S...S0$ (simple induction). But $\mathfrak{R}$ has an underlying set composed only of the $S...S0$'s for finitely many $S$'s. In particular, since $x<y \implies x\neq y$, for all $n\in \mathbb{N}$, $f(n) < c$ and so $f(n) \neq c$: $c$ is not in the image and so $f$ is not surjective, hence not an isomorphism

  • $\begingroup$ Sorry I misread your notations, let me edit $\endgroup$ – Max Mar 3 '18 at 13:32
  • $\begingroup$ Since $\mathfrak{R}_0$ is a restriction of $\mathfrak{M}$ to the original language, why is $c$ still in $\mathfrak{R}_0?$ Because in its universe, I do not see $c^{\mathfrak{M}}.$ $\endgroup$ – Idonknow Mar 3 '18 at 13:45
  • $\begingroup$ It does not matter that the language doesn't know $c$ exists anymore, the element $c^{\mathfrak{M}}$ is a fixed element $|\mathfrak{M}| = |\mathfrak{R}_0|$ $\endgroup$ – Max Mar 3 '18 at 15:28
  • $\begingroup$ I just used $c$ as an abbreviation, I should have written $c^{\mathfrak{M}}$ instead $\endgroup$ – Max Mar 3 '18 at 15: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.