# Showing that an increasing sequence of L-structures is closed unbounded

I was given the following statement to show as an exercise, but I'm at a loss on how to proceed.

Let $\kappa$ be an uncountable regular cardinal, and $L$ be a countable language. Suppose $(M_\alpha : \alpha < \kappa)$ is an increasing and continuous (i.e. $M_\gamma = \bigcup_{\alpha < \gamma} M_\alpha$ for limit ordinals $\gamma$) sequence of $L$-structures, and let $M = \bigcup_{\alpha < \kappa} M_\alpha$. Show that $S = \{ \alpha \in \kappa : M_\alpha \prec M \}$ is a closed unbounded (club) set.

Here's what I have so far for the closure proof.

Take $A \subseteq S$ and let $\gamma = \lim A$. We want to show that $\gamma \in S$. Since $\kappa$ is regular, we know that $\gamma < \kappa$, so we just need to see that $M_\gamma \prec M$. To do so, we will check the Tarski-Vaught criterion. Take an arbitrary $L$-formula $\phi$ and suppose that there exists $a \in M$ such that $M \models \phi(a)$. Now we need to find $b \in M_\gamma$ such that $M_\gamma \models \phi(b)$. Note that $a \in M = \bigcup_{\alpha < \kappa} M_\alpha$ implies that $a \in M_\alpha$ for some $\alpha$. We now need to show that $\alpha \in A$ to satisfy the Tarski-Vaught criterion.

It's not clear to me how $\alpha$ can possibly be in $A$ in general though.

For unboundedness, I'm not sure at all how to begin.

• Have you tried using the Tarski-Vaught criterion? Feb 13 '17 at 2:05
• @EricWofsey I've amended my proof to show what I came up with for the Tarski-Vaught test. I hadn't included it originally because it seems to lead to a dead end. Feb 13 '17 at 2:26
• You've forgotten a necessary hypothesis that $|M_\alpha|<\kappa$ for all $\alpha$. For example, consider the structure $M = \kappa\times \{0,1\}$, together with the binary relation $E = \{((\alpha,0),(\alpha,1)\mid \alpha\in \kappa\}$. Let $M_\alpha$ be the substructure on $\kappa\times \{0\}\cup \alpha\times \{1\}$. Then $M = \bigcup_{\alpha<\kappa} M_\alpha$, but no $M_\alpha$ is an elementary substructure of $M$. Feb 13 '17 at 3:28

EDIT: Alex Kruckman pointed out a missing hypothesis in your problem. However, note that that hypothesis is not needed for what I've written below (the "closed" part of club)! Regardless of the sizes of the $M_\alpha$s, the set of indices of elementary substructures will always be closed (though it may be empty).

You want to show that $M_\gamma\prec M$. To do this, we'll use Tarski-Vaught, which states:

Suppose $N\subseteq M$ and for each formula $\varphi(x)$ with parameters in $N$, if $M\models \exists x\varphi(x)$ then for some $n\in N$ we have $M\models\varphi(n)$. Then $N\preccurlyeq M$.

So suppose $\varphi$ were such a formula. The formula $\varphi$ uses finitely many parameters from $M_\gamma$ and $\gamma$ is a limit element of $S$, so we may find some $\beta<\gamma$, $\beta\in S$ such that each parameter in $\varphi$ is in $M_\beta$.

Now since $M_\beta\prec M$, there is some $b\in M_\beta$ such that $M\models\varphi(b)$. But $M_\beta\subseteq M_\gamma$, so $b\in M_\gamma$.

• All we have as an assumption is that $M \models \phi$; how can you say that $\phi$ uses finitely many parameters from $M_\gamma$? Couldn't $\phi$ also have parameters from outside $M_\gamma$? Feb 13 '17 at 2:52
• @JacobErrington Tarski-Vaught only refers to formulas with parameters from the smaller model. (See the wiki page for a concise statement which makes this clear.) Feb 13 '17 at 2:53
• @JacobErrington I've added a bit more detail, including the precise statement of Tarski-Vaught. Feb 13 '17 at 2:55
• Ah I see! The formulation of Tarski-Vaught from my notes didn't really make it clear that the parameters are coming from the submodel. Feb 13 '17 at 3:05
• There's still something I don't understand though. The assumption $M \models \exists x : \phi (x)$ has the existential ranging over $M$, unless "with parameters in $N$" means that in fact that existential is ranging over $N$. But then, in that case, isn't $M \models \exists x \in N: \phi(x)$ always true? Feb 13 '17 at 3:09

Noah's answer has discussed how to prove closedness. For unboundedness, you're going to want to imitate the proof of (downward) Lowenheim-Skolem: you just need to show that for an unbounded set of $\alpha$, $M_\alpha$ is closed under a set of Skolem functions for $M$. Here you'll need to use the fact that the language is countable (so you have only countably many Skolem functions) and the fact that $\kappa$ is regular and uncountable, and you will need to assume that $|M_\alpha|<\kappa$ for all $\alpha$ as pointed out by Alex Kruckman's comments.

• +1. I think you actually need that $\kappa$ is regular, not just that is has uncountable cofinality, since given a structure $M_\alpha$ of size $\lambda$, you have to make sure another structure in the chain contains all the $\lambda$-many outputs of Skolem functions applied to tuples from $M_\alpha$. And this requires $\kappa$ to have cofinality greater than $\lambda$ (plus the omitted hypothesis that all the structures in the chain have size $<\kappa$). Feb 13 '17 at 3:30
• Oh, good point. Feb 13 '17 at 3:33
• Enter Jonsson cardinals. Feb 13 '17 at 6:49