# Cardinality preservation under elementary extensions

Is there a first order language $$L$$ and an $$L$$-structure $$M$$ with $$|M|<|L|$$ s.t. every proper elementary extension of $$M$$ has cardinality $$\ge |L|$$?

Yes. Here's a standard example: Consider the language $$L = \{<\}\cup \{f\mid f\colon \mathbb{N}\to \mathbb{N}\}$$, where $$<$$ is a binary relation symbol and for each function $$f\colon \mathbb{N}\to \mathbb{N}$$, $$f$$ is a unary function symbol. We have $$|L| = 2^{\aleph_0}$$.

We view $$\mathbb{N}$$ as an $$L$$-structure, where the symbols have their natural interpretations. Of course, $$|\mathbb{N}| = \aleph_0 < |L|$$.

Here are two exercises for you:

• If $$\mathbb{N}\preceq \mathcal{N}$$, then for any $$n\in \mathcal{N}\setminus \mathbb{N}$$, we have $$k < n$$ for all $$k\in \mathbb{N}$$.
• For $$f,g\colon \mathbb{N}\to \mathbb{N}$$, we say that $$f$$ and $$g$$ are almost disjoint if there exists some $$k\in \mathbb{N}$$ such that $$f(x)\neq g(x)$$ for all $$x\in \mathbb{N}$$ with $$k < x$$. There exists a family $$\mathcal{F}$$ of $$2^{\aleph_0}$$-many functions $$\mathbb{N}\to \mathbb{N}$$ which is pairwise almost disjoint.

Now suppose $$\mathbb{N}\preceq \mathcal{N}$$ is a proper elementary extension, and let $$n\in \mathcal{N}\setminus \mathbb{N}$$. For any pair of functions $$f,g\in \mathcal{F}$$, $$f$$ and $$g$$ are almost disjoint, so there exists $$k\in \mathbb{N}$$ such that $$f$$ and $$g$$ differ on all values greater than $$k$$. Then $$\mathcal{N}\models \forall x\, (k < x \rightarrow f(x)\neq g(x))$$. But $$k < n$$, so $$f(n)\neq g(n)$$. The same is true for any pair from $$\mathcal{F}$$, so since $$\mathcal{F}$$ has cardinality $$2^{\aleph_0}$$, the set of values $$\{f(n)\mid f\in \mathcal{F}\}\subseteq \mathcal{N}$$ has cardinality $$2^{\aleph_0}$$. Thus $$|\mathcal{N}|\geq |L|$$.

• brilliant, thank you – Lorenzo Oct 21 '20 at 13:06