1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ brilliant, thank you $\endgroup$ – Lorenzo Oct 21 '20 at 13:06

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.