Can First Order Logic Express Cardinal Numbers

Question

More specifically, is it possible for two models $M$ and $N$ whose domains' sizes are $\aleph_2$ and $\aleph_3$ respectively to be elementarily equivalent (in first order language)?

What about infinitary logic?

Answer 1

For first-order logic, the answer is that cardinality is largely undetectable: the Lowenheim-Skolem theorems say that for any theory $T$ in a language $L$ which has an infinite model and any infinite cardinal $\kappa\ge\vert L\vert$, there is a model of $T$ of cardinality $\kappa$.

That said, there are some interesting nuances:

• The cardinality of the language is quite important. It is not necessarily true that if $\aleph_0\le\vert\mathcal{A}\vert<\kappa$ then there is a $\mathcal{B}$ of cardinality $\kappa$ with $\mathcal{A}\equiv\mathcal{B}$.

  • Specifically, think about an infinite binary tree, in a language rich enough to talk about levels of the tree, equipped with a predicate naming each path. You can show that the theory of this structure has no uncountable models of size $<2^{\aleph_0}$, so if the continuum hypothesis fails we get a "gap" in possible cardinalities. I believe there is also a ZFC-provable example, which I'll add once I remember it.

• When we look at two cardinals at once, things get very complicated indeed. Suppose we have a structure $\mathcal{A}$ with a unary predicate symbol $U$ such that $\vert\mathcal{A}\vert=\aleph_2$ and $\vert U^\mathcal{A}\vert=\aleph_1$. Must $\mathcal{A}$ have an elementary substructure $\mathcal{B}$ with $\vert\mathcal{B}\vert=\aleph_1$ and $\vert U^\mathcal{B}\vert=\aleph_0$? This also pushes us beyond the usual axioms of set theory.

---

For infinitary logic, things are a bit more finicky.

On the one hand, we do have a weak analogue of Lowenheim-Skolem: if $L$ is a countable language and $\varphi$ is a single $\mathcal{L}_{\omega_1,\omega}$-sentence in that language, then every model of $\varphi$ has a countable substructure also satisfying $\varphi$.

(Incidentally, a slightly weaker version of this - where we just demand some countable model of $\varphi$, not necessarily a substructure of the starting model - has a very silly proof via forcing: given $\mathcal{A}\models\varphi$ uncountable, note that a $Col(\omega,\vert\mathcal{A}\vert)$-generic extension of the universe satisfies "$\varphi$ has a countable model," which is $\Sigma^1_2$ and hence holds already by Shoenfield absoluteness.)

But beyond that things are quite complicated. Here are a couple examples:

• The full $\mathcal{L}_{\omega_1,\omega}$ theory of $\mathcal{R}=(\mathbb{R};0,1,+,\cdot)$ is fully categorical: its only model is $\mathcal{R}$ (up to isomorphism).

  • HINT: for each bounded set $A$ of rationals there is an $\mathcal{L}_{\omega_1,\omega}$-sentence $\gamma_A$ saying that $A$ has a least upper bound.

• The Hanf number of $\mathcal{L}_{\omega_1,\omega}$ - the smallest cardinal $\kappa$ such that if an $\mathcal{L}_{\omega_1,\omega}$-sentence has cardinality $\kappa$ then it has models of arbitrarily large cardinality - is huge: it's $\beth_{\omega_1}$.