# Are there countable non-standard models of true arithmetic formulated in the uncountable "full (first-order) language of arithmetic"?

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})$$?

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

• This strategy can be improved to show that any nonstandard model of true full arithmetic has size at least $2^{\aleph_0}$. Find a family $\mathcal{F}$ of functions $\mathbb{N}\to\mathbb{N}$ of cardinality $2^{\aleph_0}$ such that any two functions in $\mathcal{F}$ agree on only finitely many natural numbers. Let $m\in M$ be a nonstandard element in a nonstandard model. Then for any $f\neq g$ in $\mathcal{F}$, there is some $N\in \mathbb{N}$ such that $\mathbb{N}\models \forall x (N < x \rightarrow f(x)\neq g(x))$, so $f(m)\neq g(m)$. So $|\{f(m)\mid f\in \mathcal{F}\}| = 2^{\aleph_0}$. Jun 8, 2020 at 14:37
• One way to find the continuum-sized family of "almost disjoint" functions is to put $\mathbb{N}$ in bijection with $\mathbb{Q}$ and pick, for each real number, a sequence of rationals converging to it. Jun 8, 2020 at 14:37