So, we are requested to prove the existence a structure $\mathfrak{A}$ - first order logic - that has the same theory as the usual natural numbers and, moreover, there exists an element $\infty\in|\mathfrak{A}|$ such that it is "larger" than any other $x\in|\mathfrak{A}|$.

More specifically, let us consider a language $L$ with the only non-logical symbol being a binary predicate symbol $<$, a unary function symbol $S$ and a constant symbol $0$ and also let $\mathfrak{N}$ be the following structure: $$\mathfrak{N}=\langle\mathbb{N};<^{\mathfrak{N}},S^{\mathfrak{N}},0^{\mathfrak{N}}\rangle$$ where $\mathbb{N}=\{0,1,2,\dots\}$, $<^{\mathfrak{N}}$ is the usual ordinance relation in the natural numbers, $S^{\mathfrak{N}}$ is the usual successor function and $0^{\mathfrak{N}}$ is the usual zero. Now, let us also consider the set of sentences: $$\mathrm{Th}\mathfrak{N}=\{\phi|\phi\text{ is a sentence and }{\mathfrak{N}}\models\phi\}$$ So, what we want now, is to show that there exists a structure $L$ in that language, let $\mathfrak{A}$: $$\mathfrak{A}=\langle|\mathfrak{A}|;<^{\mathfrak{A}},S^{\mathfrak{A}},0^{\mathfrak{A}}\rangle$$ what has the property that there exists an element, let us note it with $\infty$, $\infty\in|\mathfrak{A}$ such that, for every $x\in\mathfrak{A}\setminus\{\infty\}$ we have that: $$x<^{\mathfrak{A}}\infty$$ To prove this, we will use the Compactness Theorem (CT), as follows.

Let, for our own convenience note with $\mathbf{n}$ the terms: $$\mathbf{n}:\underbrace{SS\dots S}_{n\text{ times}}0$$ for every $n=1,2,\dots$.

Let $\phi_n(x)$ be the following types: $$\phi_n(x):\mathbf{n}<x$$ for every $n=1,2,\dots$.

Now, let also: $$T=\mathrm{Th}\mathfrak{N}\cup\{\phi_n(x):n=1,2,\dots\}$$ If $T'\subseteq T$ and $T'$ is finite, then there exists a $k\in\mathbb{N}$ such that: $$T'\subseteq\mathrm{Th}\mathfrak{N}\cup\{\phi_n(x):n=1,2,\dots,k\}=\Sigma$$ For $\Sigma$, there exists a structure, $\mathfrak{N}$ itself, and a function $s:V\to|\mathfrak{N}|$ such that: $$\mathfrak{N}\models \Sigma[s]$$ Indeed, if $s(x)=\mathbf{n+1}$, then it is clear that, using the definition of $\mathrm{Th}\mathfrak{N}$ and the interpretation of $<^{\mathfrak{N}}$ and $S^{\mathfrak{N}}$.

So, we have also have that - since $T'\subseteq\Sigma$: $$\mathfrak{N}\models T'[s]$$ and, as a result, since $T'$ was arbitrary, we have that $T$ is finitely satisfiable. Hence, from CT, we have that $T$ is also satisfiable, which means that there exists a structure $\mathfrak{A}$ and a function $s:V\to|\mathfrak{A}|$ such that: $$\mathfrak{A}\models T[s]$$ Let us note with $\infty$ the element: $$\infty:=s(x)\in|\mathfrak{A}|$$ It is clear that, since $T$ is satisfiable, we have that: $$x<^{\mathfrak{A}}\infty$$ for every $x\in|\mathfrak{A}|\setminus\{\infty\}$ and also that $$\mathrm{Th}\mathfrak{A}=\mathrm{Th}\mathfrak{N}$$ since, from the definition of $\mathfrak{A}$ we have that $\mathrm{Th}\mathfrak{N}\subseteq\mathrm{Th}\mathfrak{A}$ and, if $\phi$ was a sentence such that $\phi\in\mathrm{Th}\mathfrak{A}\setminus\mathrm{Th}\mathfrak{N}$ then, we would have that $\neg\phi\in\mathrm{Th}\mathfrak{N}\subseteq\mathrm{Th}\mathfrak{A}$ which is a contradiction.

So, we have proved the requested.

However, let us consider the following sentence: $$\phi:\exists x\forall y(y<x)$$ It is clear that this is not true in $\mathbb{N}$, so $\phi\not\in\mathrm{Th}\mathfrak{N}$, but it is true in $\mathfrak{A}$, so $\phi\in\mathrm{Th}\mathfrak{A}=\mathrm{Th}\mathfrak{N}$.

Where's the mistake in all this?

I've thought of $<^{\mathfrak{A}}$ not being interpreted as a strict ordinance, but his is not the case, since the ordinance axioms can be described from sentences and they are modeled by $\mathfrak{N}$, so, by $\mathfrak{A}$, as well. Moreover, I cannot find any fault in the proof of the existence of $\mathfrak{A}$ using CT, however, I'm sure there should exist a mistake in all this.

  • $\begingroup$ If you use the compactness theorem then your sentence $\phi$ will not be true in the new model, either. $\endgroup$ – Mikhail Katz Jan 25 '18 at 11:38
  • $\begingroup$ Yeap, I know, but from Tarski's defintion, we have that $\phi$ is true iff there exist $d\in|\mathfrak{A}|$ such that $\forall y(y<d)$ which is true if we choose $d=\infty$, as defined in structure $\mathfrak{A}$. That's why I'm confused. $\endgroup$ – Βασίλης Μάρκος Jan 25 '18 at 11:40
  • 2
    $\begingroup$ But $d=\infty$ will only be bigger than all the elements in the original structure, not all the elements of the new structure. You might want to take a look at Skolem's model to get a clearer picture of what is going on. $\endgroup$ – Mikhail Katz Jan 25 '18 at 12:00
  • $\begingroup$ Hmmm... So, since $\phi$ is not satisfied by $\mathfrak{A}$ we have that $$\forall x\exists y(\neg(y<x))$$, so there exists an element $y_{\infty}$ such that $\neg(y_{\infty}<\infty)$. So, from orinance axioms, we have that $$y_{\infty}=\infty\lor \infty<y_{\infty}$$. But, if $y_{\infty}=\infty$, then we come back to our initial case, so we should have that $\infty<y_{\infty}$. By induction we can find a sequence $y_\infty(n)$ such that $$\infty<y_\infty(1)<\dots<y_\infty(k)<y_\infty(k+1)<\dots$$ which implies that $|\mathfrak{A}|$ contains infinitely many "infinte" elements, right? $\endgroup$ – Βασίλης Μάρκος Jan 25 '18 at 12:18
  • $\begingroup$ Certainly. You might want to look up the structure of countable nonstandard models; see e.g. wiki. $\endgroup$ – Mikhail Katz Jan 25 '18 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.