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.

Thanks in advance.

  • $\begingroup$ Have you tried using the Tarski-Vaught criterion? $\endgroup$ Feb 13 '17 at 2:05
  • $\begingroup$ @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. $\endgroup$ Feb 13 '17 at 2:26
  • 2
    $\begingroup$ 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$. $\endgroup$ 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$.

  • $\begingroup$ 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$? $\endgroup$ Feb 13 '17 at 2:52
  • 1
    $\begingroup$ @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.) $\endgroup$ Feb 13 '17 at 2:53
  • $\begingroup$ @JacobErrington I've added a bit more detail, including the precise statement of Tarski-Vaught. $\endgroup$ Feb 13 '17 at 2:55
  • $\begingroup$ 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. $\endgroup$ Feb 13 '17 at 3:05
  • $\begingroup$ 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? $\endgroup$ 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.

  • 2
    $\begingroup$ +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$). $\endgroup$ Feb 13 '17 at 3:30
  • $\begingroup$ Oh, good point. $\endgroup$ Feb 13 '17 at 3:33
  • 1
    $\begingroup$ Enter Jonsson cardinals. $\endgroup$
    – Asaf Karagila
    Feb 13 '17 at 6:49

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.