This is exercise 2.3.1 (2) from Tent/Ziegler, A Course in Model Theory.
Let $\mathcal F$ be the set of all functions $\mathbb N \to \mathbb N$. Show that $(\mathbb N, <, f)_{f\in \mathcal F}$ has no countable proper elementary extension.
My approach was to assume we have some proper elementary extension $\mathfrak A$ with $\mathbb N \subsetneq A$. Choose $a \in A \setminus \mathbb N$. As we have a first order sentences true in $\mathbb N$ stating that there is no maximal element, either $a$ is between two natural numbers $n,m$ with $m = n+1$, or comes before every natural number. In the first case let $\overline n, \overline m : \mathbb N \to \mathbb N$ the constant function giving $n$ and $m$. Then in $(\mathbb N, <, f)_{f\in \mathcal F}$ the sentence $\exists x \forall y ( \overline n(y) < x < \overline m(y) )$ is false, but in $\mathfrak A$ it is true. Hence this case could not arise. Similar if $a$ comes before every natural number, using $\overline 0 : \mathbb N \to \mathbb N$ I can give a sentence true in this extension, but not true in $\mathbb N$.
So, in consequence there would be no elementary extension at all. But this contradicts the Theorem stated on these slides (see slide number 7), that every infinite model has a proper elementary extension.
So what is wrong with my above reasoning? Why this contradiction?
Best Answer
There seems to be some confusion here. Let $\mathcal{M} = (\mathbb{N}, < f)_{f \in \mathcal{F}}$. We want to show that if $\mathcal{M} \prec \mathcal{N}$, then $|\mathcal{N}| > \aleph_0$ (by upward Löwenheim–Skolem/Ultrapower construction, we know such $\mathcal{N}$ exists). Any element in $a \in \mathcal{N} \backslash \mathcal{M}$ will be greater than any natural number (in above, you say that it must be less than any natural number or inbetween two of them).
Now, one has to show that $|\mathcal{N}| > \aleph_0$. Choose $a \in \mathcal{N} \backslash \mathcal{M}$. We know that $M \models \forall x \exists y f(x) = y$ for every $f \in \mathcal{F}$. Since $M \prec \mathcal{N}$, we know that for every $f \in \mathcal{F}$, $f(a) \in \mathcal{N}$. Now, it's your job to show that $|\mathcal{N}| > \aleph_0$.
(As a hint, you need to somehow incorporate the ordering.)