# Using the Downward Lowenheim-Skolem-Tarski Theorem.

I've been reading about the models of Set Theory in Kunen's most recent Set Theory text, and working on exercises since this is my first time working with Model Theory. There is one exercise that I've been looking at for a while now, but I can't seem to wrap my brain around it.

$(ZFC^-)$ Let $\alpha > \omega_1$ be a limit ordinal. Prove that there is a countable, transitive $M$ and ordinals $\beta, \gamma \in M$ such that $M \equiv V_\alpha$ and $(\beta \approx \gamma)^M$ is false but $(\beta \approx \gamma)^{V_\alpha}$ is true.

The notation $\beta \approx \gamma$ means that $\beta$ and $\gamma$ have the same size, i.e., there is a bijection from $\beta$ to $\gamma$.

A hint is also provided: Use the Downward Lowenheim-Skolem-Tarski Theorem to get a countable $A$ with $\omega, \omega_1 \in A \preccurlyeq V_\alpha$. Then, let $M$ be the Mostowski collapse of $A$; let $\beta = \mbox{mos}(\omega) = \omega$ and $\gamma = \mbox{mos}(\omega_1)$. Then, $\gamma$ will be a countable ordinal that $M$ thinks" is true.

The text states the mentioned Theorem (in $ZFC^-$) as follows: Let $\mathfrak{B}$ be any structure for $\mathcal{L}$. Fix $\kappa$ such that max$(|\mathcal{L}|, \aleph_0) \leq \kappa \leq B$, and fix $S \subset B$ with $|S| \leq \kappa$. Then, there is an $\mathfrak{A} \preccurlyeq \mathfrak{B}$ such that $S \subset A$ and $|A| = \kappa$.

I'm not sure how we can have $\omega, \omega_1 \in A$, or what we would be able to use for $A$. Any help or explanations would be greatly appreciated.

What the Downward-Löwenheim-Skolem theorem tells you is that for the relation $R_\in=\{(a,b)\in V_\alpha\times V_\alpha:a\in b\}$ of $V_\alpha$ you can find some countable $A\subseteq V_\alpha$ such that the elements $\omega,\omega_1$ of the model $V_\alpha$ lie at $A$ and $(A,A^2\cap R_\in)\preceq(V_\alpha,R_\in)$, that is, $(A,\in)\preceq(V_\alpha,\in).$

To complete the rest of the exercise, that is, to show $(\operatorname {mos}(\omega)\simeq\operatorname {mos}(\omega_1))^M$ is false, simply show that if $\varphi(\bar x)$ is a $\Delta_0$-formula then $(\varphi(\bar a))^A$ if and only if $(\varphi(\operatorname {mos}(\bar a))^M$, and as the notion of being an ordinal and a bijection can be described with $\Delta_0$-formulas, you get the result.

• @josh As $M$ is transitive we have that $\beta,\gamma\subseteq M$, then as $M$ is countable this implies $\beta,\gamma<\omega_1$, but $\alpha>\omega_1$, and any bijection $f$ from $\beta$ onto $\gamma$ has rank less than $\omega_1$, so $f\in V_\alpha$. Oct 12, 2013 at 20:20
• Thanks for the explanation. There's one thing I'm a little confused about. From looking at the hint provided in the question, why would $V_\alpha$ think mos$(\omega_1)$ is countable, and $M$ think mos$(\omega_1)$ is uncountable?
– josh
Oct 12, 2013 at 20:27
• @josh Because in M there isn't a bijection between $mos(\omega_1)$ and $\omega$. Oct 12, 2013 at 20:46
• Since we are dealing with the $\in$ relation and $M$ is transitive, then wouldn't $\in$ be extensional on $M$, implying that mos would be the identity function on $M$, meaning mos$(\omega_1) = \omega_1$ on $M$?
– josh
Oct 13, 2013 at 3:21
• @josh And yes, $\in$ is extensional on $A$ since so is $\in$ on $V_\alpha$ and $(A,\in)\preceq(V_\alpha,\in)$ and Oct 13, 2013 at 14:25

The Downward Löwenheim–Skolem Theorem allows you to get a countable elementary substructure of a given structure in a countable language, say $(V_\alpha;\in)$, containing any given countably many elements. To do this, add countably many constant symbols to the language corresponding to the elements you want to make sure your substructure contains.

In this case, to get a countable elementary substructure $A \prec V_\alpha$ with $\omega,\omega_1 \in A$, you can apply the theorem to the expanded structure $(V_\alpha;\in,\omega,\omega_1)$.

EDIT: As Asaf pointed out, $\omega$ and $\omega_1$ are definable (in $V_\alpha$ as well as in $V$) so if $A \prec V_\alpha$ then we automatically get $\omega,\omega_1 \in A$. The argument that I described is only necessary if you want to obtain the result for an arbitrary pair of ordinals $\beta,\gamma < \alpha$.

• There is no need to add constants for $\omega$ and $\omega_1$. Both are definable. Oct 12, 2013 at 5:51
• @Asaf Oops, quite right. I will edit accordingly. Oct 12, 2013 at 23:01
• Again, not accurate. If $A$ is countable and transitive then $\omega_1\notin A$. But you always have some $x\in A$ such that $x=\omega_1^A$. Oct 12, 2013 at 23:14
• @Asaf In the notation of this answer (as well as the question) $A$ denotes the uncollapsed structure and $M$ is its transitive collapse. Oct 12, 2013 at 23:21