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

| cite | improve this answer | |
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Alex Kruckman Jun 8 at 14:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Alex Kruckman Jun 8 at 14:37

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.