# Detecting incomparability in countable elementary submodel

This might be just an easy exercise in model theory but I can't seem to wrap my head around right now.

Let $\theta$ be large enough regular cardinal and $\kappa < \theta$. $(\kappa, \prec)$ is a partial order with no $\kappa$-chain such that $y\prec x, y'\prec x, y<y' \Rightarrow y\prec y'$ and $x\prec y \Rightarrow x<y$. Suppose $M$ is a countable elementary submodel of $H_\theta$ containing $\kappa$ and $(\kappa, \prec)$. Fix $n\in \omega$. Let $\langle F_\xi: \xi<\kappa\rangle \in M$ be a sequence of finite subsets of $\kappa$ of size $n$ ($\xi < \min F_\xi$ and $\max F_\xi < \min F_\eta, \forall \xi < \eta$). Let $F\in [\kappa \backslash M]^n$ such that $\forall x\in F \forall y\in M\cap \kappa \ \ x \not \prec y$. Show $\exists \xi \in M\cap \kappa$ such that for all $x\in F$ $y\in F_\xi$ x and y are $\prec$-incomparable.

My attempts so far: suppose not then by pigeon hole we have for some $x\in F$ $\Gamma=\{\xi \in M: \exists y\in F_\xi \wedge y\prec x\}$ is cofinal in $M\cap \kappa$. Also by assumption on $\prec$ $\{y: \exists \xi \in \Gamma y\in F_\xi \wedge y\prec x\}$ (i.e. the witnesses) form a chain. Now the problem is $M$ might not see this (its definition involves $x$). I feel there might be a trick to get around this. Thanks in advance.

More information: This occurs (without details given) in the proof of Proper Forcing Axiom implies failure of square of $\kappa$ ($\Box_\kappa$) for $\kappa>\omega_1$ regular in Todorcevic's A Note on Proper Forcing Axiom.

• Now that I have seen the paper you mention, you could have said that $\prec$ is a subordering of the order of $\kappa$. The author also says $\xi<F_\xi<\eta$ for $\xi<\eta<\kappa"$, although I don't know what he means. In any case, you should clarify more on this. – Camilo Arosemena-Serrato Dec 12 '15 at 0:23
• Sure. I think it means $\xi < \min F_\xi$ and $\max F_\xi < \min F_\eta, \forall \xi < \eta$. – Jing Zhang Dec 12 '15 at 1:43

We have $\langle F_\xi\mid \xi < \kappa \rangle$ which is the set of copies of $F$, and further, $\xi < F_\xi < \eta$.

If $\xi <\kappa$ and $G \in [\kappa]^n$are given, let $\phi(\xi, G)$ abbreviate the statement "$\exists x \in F_\xi\exists y \in G [x \prec y]$".

Now, suppose that there is no $\xi \in M \cap \kappa$ such that every element of $F_\xi$ and $F$ are incompatible. So $M \models \forall\xi< \kappa \exists G \in [\kappa]^n \forall \eta <\xi[\phi(\eta,G)]$". So in $M$, there is a sequence $\langle G_\xi \mid \xi< \kappa \rangle$ such that $G_\xi$ is a witness for $\xi$. Note that now, if $\xi <\eta$, then $\phi(\xi, G_\eta)$.

Let $F_\xi = \langle x^\xi_1, \ldots, x^\xi_n\rangle$ and $G_\xi = \langle y^\xi_1, \ldots, y^\xi_n\rangle$ be fixed enumerations of all the $F_\xi$ and $G_\xi$. From hereon the argument will be like in Baumgartner's partial order to specialise an Aronszajn tree.

Now, fix a uniform ultrafilter $U$ on $\kappa$. For every $\eta < \kappa$, and for every $\xi > \eta$, there is $(i,j) \in \{1,\ldots, n\}\times \{1,\ldots ,n\}$ such that $x^\eta_i \prec y^\xi_j$. Using the uniform ultrafilter $U$, get for each $\eta < \kappa$ a pair $p_\eta = (i,j)$ and $S_\eta \in U$ such that for every $\xi \in S_\eta$, $\eta < \xi$ and $x^\eta_i \prec y^\xi_j$.

There are only $n^2$ many possible pairs $(i,j)$, so let $T \subseteq\kappa$ have size $\kappa$ and $p = (i,j)$ be a pair such that for each $\eta \in T$, $p_\eta = p$.

Now, let $\eta< \xi \in T$ be distinct. Let $\zeta \in S_\eta \cap S_\xi$ be larger than both. Then $x^\eta_i \prec y^\zeta_j$ and $x^\xi_i \prec y^\zeta_j$. But then just unravelling what this means, it is clear that $x^\eta_i \prec x^\xi_i$. So in particular, $\langle x^\xi_i \mid \xi \in T\rangle$ is a chain of length $\kappa$, which is a contradiction.

In response to comment:

You're right. But under the assumption that for every $\xi \in F$ there are unboundedly many $\eta \in \kappa \cap M$ such that $\eta \prec \xi$ we are okay still, because then given any $\xi \in M$, we can find in $M$ an $n$-element set $G$ all of whose elements are larger than $\xi$ and every element of $F$ is comparable with some element of $G$.

Now, suppose that doesn't happen. Let $F'\subseteq F$ be the set of all $\xi$ such that there is a greatest $\delta_\xi \in \kappa\cap M$ such that $\delta_\xi \prec \xi$. Since $F\cap M = \emptyset$, you know that for every $\xi \in F'$, there must be many $\eta \in \kappa \cap M$ such that $\delta_\xi \prec \eta$. Let $|F \setminus F'| = m$ (and this cannot be $0$).

Let $\delta > \{\delta_\xi \mid \xi \in F'\}$ be in $\kappa\cap M$. Now use the same argument as the first case, since we have that for each $\zeta \geq \delta$ in $\kappa \cap M$ there is, in $M$, a set $G_\zeta$ of size $m$ such that for every $\eta \in [\delta, \zeta)$ there is $x \in F_\eta$ and $y \in G_\zeta$ such that $x \prec y$, so we can again use a uniform ultrafilter on $\kappa$ to finish.

• when you say $M \models\forall\xi< \kappa \exists G \in [\kappa]^n \forall \eta <\xi[\phi(\eta,G)]$, for any $\xi\in M\cap \kappa$, actually $H(\theta)\models \exists G \in [\kappa]^n \forall \eta \in \xi\cap M [\phi(\eta,G)]$ (F can still be incomparable with sets with index not in M) – Jing Zhang Dec 12 '15 at 5:49
• OK I see thanks. That's a nice argument! Sometimes I easily got confused in wacky countable structures :-(. – Jing Zhang Dec 12 '15 at 20:47