Give an example of a structure of cardinality $\omega_2$ that has a substructure of $\omega$ but no substructure of $\omega_1$

Question

Give an example of a structure of cardinality $\omega_2$ that has a substructure of $\omega$ but no substructure of $\omega_1$

This is from Hodges' A Shorter Model Theory.

My idea is to take some set of cardinality $\omega_2$ as the domain, $\mathrm{dom}(A)$. Choose and fix a subset of $\mathrm{dom}(A)$ with cardinality $\omega$, call this $X$. I need to then choose an $n$-ary relation, $R^A$ carefully. The point is that I need to find something that breaks:

$R^A=R^B\cap A^n$

for every subset of cardinality $\omega_1$ but such that that holds for A subset of cardinality $\omega$. The ones I've tried (like everything in the set $X$ being related to each other, etc.) didn't work.

Any hints?

Answer 1

HINT: Using only relations won't work, since given a language with only relation symbols, and a structure to the language, every subset of the domain defines a substructure. So using functions is necessary here.

Let $\{f_\alpha\mid\alpha<\omega_2\}$ be a list of $\omega_2$ unary function symbols. For sake of concreteness we can take $A=\omega_2$. Find a way to interpret $f_\alpha$ so for every $n<\omega$, $f_\alpha(n)<\omega$; and if $\beta\geq\omega$, then $\{f_\alpha(\beta)\mid\alpha<\omega_2\}=\omega_2$ (you actually don't need equality there, requiring that $|\{f_\alpha(\beta)\mid\alpha<\omega_2\}|=\aleph_2$ is enough).

Answer 2

(Inspired by Asaf Karagila)

Let $A$ be a structure with $\mathrm{dom}(A)=\omega_2$. $C^A=\emptyset$, $R^A=\emptyset$ and $F^A=\{f_{\alpha}\colon \alpha<\omega_2\}$ where:

$$f_{\alpha}(\beta)=\begin{cases}\beta \text{ for } \beta<\omega\\ \alpha \text{ for } \beta\geq \omega\end{cases}$$

Then define $S$ to be a substructure of $A$ with $\mathrm{dom}(S)=\omega$, $C^A=\emptyset$, $R^A=\emptyset$ and $F^A=\{f_{\alpha}\colon \alpha<\omega\}$. Then trivially $F^S=F^A\mid \mathrm{dom}(A)$ and $S$ is a substructure of $A$.

However if $T$ is a substructure with $|T|=\omega_1$, then there is some $t\in T\setminus\omega$. Pick $\alpha\in A\setminus T$, then $f_{\alpha}(t)=\alpha\not\in T$.