Why Presburger arithmetic is not categorical in any cardinality (the theory of natural number with ordering also)?

Question

May I ask why Presburger arithmetic is not categorical in any cardinality? And I was told that the theory $T<$ of natural number with ordering structure $(\mathbb{N} , 0 , S, <)$ is not categorical in any cardinality, e.g. the nonstandard part in $A$, a model of $T<$, are gained by replacing every points in $(\mathbb{N}, <)$ with a "$\mathbb{Z}$-chain" (which is like "$......, a, Sa , SSa$", because every "number" other than $0$ is a successor of some other "number") and the one in model $B$, another model of $T<$, are gained by replacing every points in $(\mathbb{Q}, <)$ with a $\mathbb{Z}$-chain, then $A$ and $B$ are not isomorphic. I think it may be because the $\mathbb{Z}$-chains in $A$ are dense but $B$'s are not. However, could this argument work for uncountable cardnalities as well?

Answer 1

The theory $Th(\mathbb{N},<)$ is easier to think about, so let's treat it first. The models of $Th(\mathbb{N},<)$ are exactly the linear orders of the form $\omega + \zeta\cdot L$ for some linear order $L$ (possibly $L=\emptyset$). Here $\omega$ is the ordertype of $\mathbb{N}$ and $\zeta$ is the ordertype of $\mathbb{Z}$.

The key fact is this: we have $$\omega+\zeta\cdot L_1\cong \omega+\zeta\cdot L_2\quad\iff\quad L_1\cong L_2.$$ The right-to-left direction is trivial; for the left-to-right direction, the point is that an isomorphism can't send two elements in different "$\zeta$-blocks" to elements of the same "$\zeta$-block." Note that this relies on the structure of $\zeta$: it is not true that e.g. $\omega+\eta\cdot L_1\cong \omega+\eta\cdot L_2\implies L_1\cong L_2$ (here $\eta$ is the ordertype of $\mathbb{Q}$).

This, together with the fact that $\vert\omega+\zeta\cdot L\vert=\vert L\vert$ if $L$ is infinite, means:

To show that $Th(\mathbb{N},<)$ is not categorical in an infinite cardinality $\kappa$, we just have to find non-isomorphic linear orders of cardinality $\kappa$.

One way to do this (motivated by the idea in your post) is to show that there is a dense linear order of size $\kappa$ and a non-dense linear order of size $\kappa$. The latter is provided by $\kappa$ itself; for the former, we can take e.g. $\eta\cdot\kappa$.

---

Now models of Presburger arithmetic, which I'll call "$\mathsf{Pres}$" ("$\mathsf{PA}$" already means something), are more than just linear orders. The above does however suggest an approach to proving non-categoricity in any cardinal: find some class of structures $\mathbb{X}$ with lots (that is, $>1$) of non-isomorphic instances of each infinite cardinality, and a way $X\mapsto M_X$ of turning structures in $\mathbb{X}$ into linear orders such that $$X\cong Y\iff M_X\cong M_Y.$$

Here's one way to do that:

Let $\mathbb{X}$ be the class of all infinite divisible monoids. Given a monoid $\mathcal{X}=(X,\star)\in\mathbb{X}$, let $M_\mathcal{X}$ be the monoid with underlying set $\mathbb{N}\sqcup X\times\mathbb{Z}$ and monoid operation $*$ given by:

• For $a,b\in\mathbb{N}$ we set $a*b=a+b$.

• For $(x_1,z_1)\in X\times\mathbb{Z}$ and $a\in\mathbb{N}$ we set $(x_1,z_1)*a=a*(x_1,z_1)=(x_1, z_1+a)$.

• For $(x_1,z_1),(x_2,z_2)\in X\times\mathbb{Z}$ we set $(x_1,z_1)*(x_2,z_2)=(x_1\star x_2, z_1+z_2)$.

It's easy to check that $\vert M_\mathcal{X}\vert=\vert\mathcal{X}\vert$, that $\mathcal{X}\cong\mathcal{Y}\iff M_\mathcal{X}\cong M_\mathcal{Y}$, and that $M_\mathcal{X}\models\mathsf{Pres}$. Now to prove non-categoricity of $\mathsf{Pres}$ in an infinite cardinal $\kappa$ we just need to show that there are at least two non-isomorphic monoids of cardinality $\kappa$. This is a good exercise.

---

Of course, for more complicated theories this sort of ad hoc argument gets increasingly tedious. Ultimately it's nice to have some powerful theorems to apply. For example:

Suppose $T$ is a countable theory which is categorical in some (equivalently by Morley, every) uncountable cardinal. Then if $M_1,M_2$ are countable models of $T$ we must have an elementary embedding of $M_1$ into $M_2$ or an elementary embedding of $M_2$ into $M_1$.

This reduces the task of proving non-categoricity in uncountable cardinals to an analysis of countable models, which is usually pretty easy. Proving non-categoricity in $\omega$ is then handled separately (usually via omitting types).

Ultimately, counting models of a given theory is surprisingly hard, and over the years lots of work has gone into this - the term "(neo)stability theory" is key here. But for reasonably-natural countable theories, establishing non-categoricity is usually pretty straightforward, especially with a few key theorems in hand.