2
$\begingroup$

Given $\mathfrak{R} = (\mathbb{N},0,\operatorname{S},<,+,\cdot)$, Let $$\Sigma = \{ 0 < c, \operatorname{S}{0} < c, \operatorname{S}\operatorname{S}{0} < c, \ldots\}$$

By compactness theorem and Löwenheim–Skolem theorem, we claim that $ \Sigma\cup \operatorname{Th}{\mathfrak{R}}$ has a countable model($\operatorname{Th}{\mathfrak{R}}$ means the set of all theorems of $\mathfrak{R}$),which is: $$\mathfrak{M} = (|\mathfrak{M}|,0^{\mathfrak{M}},S^{\mathfrak{M}},<^{\mathfrak{M}},+^{\mathfrak{M}},\cdot^{\mathfrak{M}},c^{\mathfrak{M}})$$

Let $\mathfrak{M}_0 $ be the restriction of $\mathfrak{M} $to the original language:$$\mathfrak{M}_0 = (|\mathfrak{M}|,0^{\mathfrak{M}},S^{\mathfrak{M}},<^{\mathfrak{M}},+^{\mathfrak{M}},\cdot^{\mathfrak{M}})$$

I'm confused as to why they're elementarily equivalent. It seems to me there isn't a infinite number in $\mathfrak{R}$, but there's one in $\mathfrak{M}_0 $. Isn't the case that $\nvDash_{\mathfrak{R}} \exists{x} \forall{y}(y <x \to\operatorname{S}{y} < x)$ But $\vDash_{\mathfrak{M}_0} \exists{x} \forall{y}(y <x \to\operatorname{S}{y} < x)$?

$\endgroup$
4
$\begingroup$

Suppose $\phi$ is a formula on the original language.

If $R \vDash \phi$, then $\phi \in Th \mathfrak R$, and since $\mathfrak M \vDash Th \mathfrak R$, $\mathfrak M \vDash \phi$, and in particular, $\mathfrak M_0 \vDash \phi$
If $R \nvDash \phi$, then $\neg \phi \in Th \mathfrak R$, and since $\mathfrak M \vDash Th \mathfrak R$, $\mathfrak M \vDash \neg \phi$, and in particular, $\mathfrak M_0 \nvDash \phi$

You cannot express "is an infinite number" with the original language (nor with the added constant). Your sentence is actually false in $\mathfrak R$ because $x$ can be $0$. And even with the sentence $\phi : \exists x, x \neq 0 \land \forall y, (y < x \implies S y < x)$, this doesn't say "the model contains an infinite number", it says "there is a nonzero number that has no predecessor", which is false again in $\mathfrak M_0$, even though $c^\mathfrak M$ is "infinite".

Even better, you actually know that $\forall x, \exists y, x = y+y \lor x = y+y+1$ which says that every number is even or odd, (and that you can divide even numbers by 2), so the sentence "c is even or odd" is true in $\mathfrak M_0$, even though you don't know in which case $c$ is.

$\endgroup$
  • $\begingroup$ Congratulations on the 10K, welcome to the club! $\endgroup$ – Asaf Karagila Apr 26 '13 at 16:26
  • 3
    $\begingroup$ Additionally, if you could express "is an infinite number", you could also express "there is no infinite number". Now assume you add that to $\textrm{Th}\, \mathfrak{R}$. Every finite subset of $\Sigma$ would still be consistent with that extended theory, yet the whole of $\Sigma$ would not. Which, due to compactness, is of course impossible. $\endgroup$ – fgp Apr 26 '13 at 16:32
5
$\begingroup$

InGoldstern and Judah's The Incompleteness Phenomenon there is a discussion of what countable models of your axioms look like. They show they are $\Bbb {N + Q \times Z}$: a standard copy of $\Bbb N$ followed by a dense order of copies of the integers. It is still true that every element except $0$ has a predecessor, in fact that contributes to showing the upper pieces are like $\Bbb Z$

$\endgroup$
  • $\begingroup$ Thank you very much for your answer. Why $\mathbb{N}+\mathbb{Z}$ is not the model that satisfies the axioms in the question? $\endgroup$ – Metta World Peace Apr 27 '13 at 3:15
  • 1
    $\begingroup$ @MettaWorldPeace: It isn't simple. They define an equivalence relation ~ as $a \sim b$ if $b-a$ or $a-b$ is a standard natural. They show the classes are ordered and the order on the classes respects the order on the model. Then they show that as any element except $0$ has a predecessor, the classes are $\Bbb Z$ Finally, and this is where $\Bbb{N + Z}$ fails, any pair of elements (or increasing one of them by $1$) in different equivalence classes have an arithmetic mean. No element of $\Bbb {N+Z}$ satisfies that if $a \in \Bbb N$ and $b \in \Bbb Z$ $\endgroup$ – Ross Millikan Apr 27 '13 at 4:00
1
$\begingroup$

Your new model $\frak{M}$ can't just say that there's one infinite element. It has to make sure that that new infinite element satisfies all the normal things from $\frak{R}$. Your construction only guaranteed that $\frak{M}$ would have a $c$ realizing $\Sigma$, not that it would be the only new element in $\frak{M}$. In particular, this new element in $\frak{M}$ must have successors and predecessors as well (since it's not the $0$ element). So while $\not\vDash_{\frak{R}} \exists x \forall y (y < x \rightarrow Sy < x)$, neither does $\frak{M}$ since $c$ must also have predecessors.

$\endgroup$
1
$\begingroup$

Note that ${\frak M}_0$ does not satisfy the property that you mention. Compactness argument gives us that there is some $c$ that is larger than all the standard integers. But this $c$ has a successor as well.

Being "truly finite" is not expressible in a first-order formula, it's a schema.

$\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.