Fix the standard language of arithmetic as, for example, $L_A ≔ ⟨0,1,+,×,<⟩$. Define the full (first-order) language of arithmetic, notation $L_\text{full}$, as the first-order language with the following signature. For each natural number $n$:
-
$n$ is a constant symbol,
-
for each function $f : ℕ^{n+1} → ℕ$: $f$ is a function symbol of arity $n+1$,
-
for each relation $P ⊆ ℕ^{n+1}$: $P$ is a relation symbol of arity $n+1$.
The standard model of $L_A$ is the usual one. The standard model of $L_\text{full}$ has domain $ℕ$ and each symbol interpreted as itself. Let $\text{Tr}(L_A)$ and $\text{Tr}(L_\text{full})$ be the respective theories corresponding to these models.
Using compactness we have non-standard models of both $\text{Tr}(L_A)$ and $\text{Tr}(L_\text{full})$. The downwards Löwenheim-Skolem theorem then gives us a countable non-standard model of $\text{Tr}(L_A)$, but we cannot do the same to $\text{Tr}(L_\text{full})$ since the signature of $L_\text{full}$ is uncountable.
So my question is: are there non-standard countable models of $\text{Tr}(L_\text{full})$?
Best Answer
No, there are not. For instance, there exists a sequence of $\omega_1$ functions $f_\alpha:\mathbb{N}\to\mathbb{N}$ (for $\alpha<\omega_1$) such that if $\alpha<\beta$ then $f_\alpha(n)<f_\beta(n)$ for all sufficiently large $n$. (Proof sketch: given any countable set of functions, you can build a function that is eventually larger than each of them by a diagonal argument. So you can construct a sequence of length $\omega_1$ by transfinite recursion, choosing each new term of the sequence to be eventually larger than the previous ones.)
Now let $M$ be a nonstandard model of $\text{Tr}(L_\text{full})$ and let $n\in M$ be any nonstandard element. Then the sequence $(f_\alpha(n))$ must be strictly increasing, so this gives $\aleph_1$ different elements of $M$. Thus $M$ must be uncountable.
Here's another argument that is perhaps more elementary and gives a stronger result (thanks to Alex Kruckman for suggesting a variant of this in the comments). For each real number $r>0$, consider the function $f_r:\mathbb{N}\to\mathbb{N}$ defined by $f_r(n)=\lfloor rn\rfloor$. Note that the ratio $f_r(n)/n$ approaches $r$ as $n\to\infty$. It follows that if $n$ is a nonstandard element of a model, the elements $f_r(n)$ must all be distinct, since we can recover $r$ as the Dedekind cut in $\mathbb{Q}$ defined by comparing multiples of $n$ and multiples of $f_r(n)$. So, the model must have at least $2^{\aleph_0}$ elements.
Finally, let me discuss a generalization. As your question really only involves $\mathbb{N}$ as a set, it is natural to ask the same question with $\mathbb{N}$ replaced by any infinite set $X$: what is the smallest possible cardinality of a nonstandard model of the theory of $X$ with respect to its full language (I will call this the "full theory of $X$")? Note first that any countable ultrapower of $X$ will be a nonstandard model of the full theory of $X$ of cardinality $|X|^{\aleph_0}$. (In general, this bound is better than the bound $2^{|X|}$ given by Löwenheim-Skolem, and in many cases is equal to just $|X|$!)
However, this bound is not sharp in general. For instance, suppose $\kappa$ is a measurable cardinal and let $\lambda>\kappa$ be strong limit cardinal of cofinality $\omega$ (actually, all we need from "strong limit" is that $\theta^{\kappa}\leq\lambda$ for all $\theta<\lambda$). Let $U$ be a countably complete ultrafilter on $\kappa$ and let $M$ be the ultrapower of $\lambda$ with respect to $U$. Since $\lambda>\kappa$, $M$ is a nonstandard model of the full theory of $\lambda$. However, since $\lambda$ has cofinality $\omega$ and $U$ is countably complete, every element of $M$ is represented by a bounded function $\kappa\to\lambda$. The number of such functions is $\lambda\cdot\sup_{\theta<\lambda}\theta^\kappa=\lambda$, so $|M|=\lambda$. In particular, $|M|<\lambda^{\aleph_0}$ since $\lambda$ has cofinality $\omega$.