Recall that a coloring $c:G\rightarrow\kappa$ of an (undirected) graph $(G,E)$ is said to be chromatic if $c(v_1)\neq c(v_2)$ whenever $\{v_1,v_2\}\in E$. Then, the chromatic number of a graph $(G,E)$ is the least cardinal $\kappa$ for which there exists a chromatic coloring $c:G\rightarrow\kappa$.
Motivated by a paper I found yesterday in the arXiv, this post will be dedicated to exemplifying incompactness properties of the chromatic number measure. More specifically, we shall give a construction of Shelah, of a graph of size $\lambda$ such that all of its subgraphs of size $<\lambda$ are countably chromatic, while the graph itself is not.

Before stating and proving Shelah’s theorem, we mention a somewhat simpler (yet, canonical) test-case. To every cardinal $\lambda$, one associates the Erdos-Hajnal graph $EH(\lambda)=({}^\lambda\omega,\bot)$, where $f\bot g$ stands for the set $\{ \alpha<\lambda\mid f(\alpha)=g(\alpha)\}$ being bounded in $\lambda$. Here is a list of fairly simple observations:

• if $\lambda$ is a regular cardinal, then any subgraph of $EH(\lambda)$ of size $<\lambda$ is countably chromatic;
• the chromatic number of $EH(\aleph_0)$ equals $2^{\aleph_0}$;
• the chromatic number of $EH(\aleph_1)$ is bigger than $\aleph_1$;
• if $(G,E)$ is a graph of size $\lambda$ such that every subgraph of size $<\lambda$ is countably chromatic, then the chromatic number of $EH(\lambda)$ is $\ge$ the chromatic number of $(G,E)$. This shows that $EH(\lambda)$ is a canonical witness to incompactness of this sort, whenever exists.
• why did I write “whenever exists” in the previous item? well, for instance, if $\lambda$ is a measurable cardinal, then every function $f:\lambda\rightarrow\omega$ is fixed on a measure one set, and hence $EH(\text{measurable})$ is countably chromatic!

Now, on to the theorem.

Theorem (Shelah, 2012).  Suppose that $\lambda$ is a regular cardinal $>\aleph_1$.
If $E^{\lambda}_\omega$ admits a non-reflecting stationary subset, and $\mu^{\aleph_0}\le\lambda$ for all $\mu<\lambda$, then there exists a graph $(G,E)$ of size $\lambda$ such that any of its subgraphs of size $<\lambda$ is countably chromatic, while $(G,E)$ is not countably chromatic.
In particular, the above assumptions entails that $EH(\lambda)$ is not countably chromatic.
Proof. Fix a regressive surjection $f:\lambda\rightarrow\lambda$ such that the preimage of every singleton is cofinal in $\lambda$. Denote $F_\delta:=\{\gamma<\lambda\mid f(\gamma)=\delta\}$.  Let $S\subseteq E^{\lambda}_\omega$ be a non-reflecting stationary subset, and put $T:=f^{-1}[S]$.
As the underlying set of our graph, we take: $$G:=\{ (\alpha,\beta)\in \lambda\times T\mid  \alpha<f(\beta)\}.$$

Next, we fix a club guessing sequence  $\langle C_\delta\mid\delta\in S\rangle$. For all $\delta\in S$, let $\{ \delta_n\mid n<\omega\}$ denote the increasing enumeration of $C_\delta$. Let $\Gamma_\delta$ denote the collection of all sequences $\langle \beta_n\mid n<\omega\rangle$ that satisfies for all $n<\omega$:

• $(\beta_{2n},\beta_{2n+1})\in G$;
• $\delta_n<\beta_{2n}<\beta_{2n+1}<\delta_{n+1}$.

As $|\delta|^{\aleph_0}\le\lambda=|F_\delta|$, we may fix a surjection $g_\delta:F_\delta\rightarrow\Gamma_\delta$.
Finally, the set of edges of the constructed graph will be:
$$E:=\left\{\{(\beta_{2m},\beta_{2m+1}),(\delta_0,\gamma)\}\mid m<\omega, \delta\in S, \gamma\in F_\delta, g_\delta(\gamma)=\langle\beta_n\mid n<\omega\rangle\right\}.$$

Subclaim. $(G,E)$ is not countably chromatic.
Proof. Suppose not, as witnessed by some coloring $c:G\rightarrow\omega$. For each $\tau<\lambda$, let $u_\tau:=\{ c(\alpha,\beta)\mid (\alpha,\beta)\in G, \alpha\ge\tau\}$. Then $\{ u_\tau\mid \tau<\lambda\}$ is a descending chain, and since $\text{cf}(\lambda)>\omega$, the chain must stabilize at some $\tau^*<\lambda$. Denote $u^*:=u_{\tau^*}$.
Consider the club$$D:=\{ \delta<\lambda\mid \forall\tau<\delta\forall n\in u^*\exists(\alpha,\beta)\in G\text{ with }\tau<\alpha<\beta<\delta\text{ s.t. }c(\alpha,\beta)=n\}.$$
Pick $\delta\in S$ such that $C_\delta\subseteq D\setminus\tau^*$.
It follows that we may find a sequence $\langle \beta_n\mid n<\omega\rangle$ such that for all $n<\omega$:

• $(\beta_{2n},\beta_{2n+1})\in G$;
• $\delta_n<\beta_{2n}<\beta_{2n+1}<\delta_{n+1}$;
• if $n\in u^*$, then $c(\beta_{2n},\beta_{2n+1})=n$.

Pick $\gamma\in F_\delta$ such that $g_\delta(\gamma)=\langle \beta_n\mid n<\omega\rangle$. Then for all $n<\omega$, we have $\{(\beta_{2n},\beta_{2n+1}),(\delta_0,\gamma)\}\in E$, and hence $c(\delta_0,\gamma)\neq c(\beta_{2n},\beta_{2n+1})$. In particular, $$c(\delta_0,\gamma)\in\omega\setminus u^*.$$
On the other hand, $\tau^*\le\delta_0<\gamma$, and so $c(\delta_0,\gamma)\in u_{\tau^*}=u^*$. This is a contradiction. $\blacksquare$

Write $G=\bigcup_{i<\lambda}G_i$, where $G_i:=\{ (\alpha,\beta)\in G \mid f(\beta)<i\}$.

Note. if $i\not\in S$, then $G_{i+1}=G_i$.
Proof. If $(\alpha,\beta)\in G_{i+1}$, then $\beta\in T$ and $f(\beta)<i+1$. As $f(\beta)\in S$, while $i\not\in S$, we infer that $f(\beta)<i$, and so $(\alpha,\beta)\in G_i$. $\blacksquare$

Main subclaim. Suppose that $u$ is an infinite subset of $\omega$.
Then, for every $i\le j<\lambda$ with $i\not\in S$, and a chromatic coloring $c:G_i\rightarrow\omega$, there exists a chromatic coloring $c’:G_j\rightarrow\omega$ such that $c’\restriction G_i=c$, and $c’[G_j\setminus G_i]\subseteq u$.
Proof. Given $u\in[\omega]^\omega$, let $\{ u_n\mid  n<\omega\}$ be some partition of $u$ into mutually-disjoint infinite sets. We now prove the claim by induction on $j<\lambda$.

$\blacktriangleright$ The case $j=0$ is trivial. $\blacktriangleleft$

$\blacktriangleright$ If $j$ is a limit non-zero ordinal, let us pick a club $e$ in $j$ such that $\min(e)=i$. As $S$ is non-reflecting, we may moreover assume that  $e\cap S=\emptyset$.
Now, build an ascending chain of chromatic colorings $\{ c_k:G_k\rightarrow\omega\mid k\in e\}$ by induction on $k\in e$:

• for $k=\min(e)$, let $c_k:=c$;
• for $k\in\text{nacc}(e)$, let $i’:=\sup(e\cap k)$, and $j’:=k$. Then $i’<j’<j$, and $i’\not\in S$, so by the induction hypothesis, we may pick a chromatic coloring $c_k:G_k\rightarrow\omega$ that extends $c_{i’}$, and such that $c_k[G_k\setminus G_{i'}]\subseteq u$.
• for $k\in\text{acc}(e)$, let $c_k:=\bigcup_{i’<k}c_{i’}$. Then $c_k$ is chromatic as the limit of chromatic colorings.

Finally, put $c’:=\bigcup_{k<j}c_k$. Then $c’$ has all the desired properties. $\blacktriangleleft$

$\blacktriangleright$ If $j$ is a successor ordinal, and $j-1\not\in S$, then $G_j=G_{j-1}$, and so we may appeal to the induction hypothesis for $j-1$. $\blacktriangleleft$

$\blacktriangleright$ If $j$ is a successor ordinal, and $j-1\in S$, let us denote $\delta:=j-1$. Since $i\le\delta$ and $i\not\in S$, we get that $i<\delta$, so let us fix a large enough $n^*<\omega$ so that $\delta_{n^*}\ge i$.
Let

• $j(n):=\delta_{(n^*+n)}+1$ for all $n<\omega$;
• $i(0):=i$, and $i({n+1}):=j(n)$ for all $n<\omega$.

Note that for all $n<\omega$, we have $i\le i(n)<j(n)<j$ and $i(n)\not\in S$.
So it follows from the induction hypothesis, that there exists an increasing chain of chromatic colorings  $\{ c_n:G_{j(n)}\rightarrow\omega\mid n<\omega\}$ that extends $c$, and such that $c_{n}[G_{j(n)}\setminus G_{i(n)}]\subseteq u_{n}$, for all $n<\omega$. Note that $\text{dom}(\bigcup_{n<\omega}c_n)=G_\delta$.
Finally, let $c’:G_j\rightarrow \omega$ be some coloring that satisfies:

• $c’\restriction G_\delta=\bigcup_{n<\omega}c_n$;
• for every $\gamma\in F_\delta$, if $g_\delta(\gamma)=\langle \beta_n\mid n<\omega\rangle$, then $$c’(\delta_0,\gamma)\in u_0\setminus\{ c(\beta_{2m},\beta_{2m+1})\mid m<n^*\}.$$

We need to verify that $c’$ is chromatic.
For this, fix $x,y\in G_j$ such that $\{x,y\}\in E$, and let us verify that $c’(x)\neq c’(y)$.
Of course, we may assume that $\{ x,y\}\setminus G_\delta\not=\emptyset$, because otherwise $\{ x,y\}\subseteq\text{dom}(c_n)$ for some $n<\omega$.

Next, by the definition of $E$, there exists $\delta^*\in S$, $m<\omega$, and $\gamma<\lambda$ such that:

• $f(\gamma)=\delta^*$;
•  $g_{\delta^*}(\gamma)=\langle\beta_n\mid n<\omega\rangle$;
• $\{ x,y\}=\{ (\beta_{2m},\beta_{2m+1}) , (\delta^*_0,\gamma) \}$.

As $(\beta_{2m},\beta_{2m+1})\in G_j$, we know that $f(\beta_{2m+1})\le\delta$. In addition, $f(\beta_{2m+1})\neq\delta$, because otherwise $j=\delta+1=f(\beta_{2m+1})+1\le\beta_{2m+1}<\delta^*_{m+1}<\delta^*=f(\gamma)$, contradicting the fact that $(\delta^*_0,\gamma)\in G_j$.

So $f(\beta_{2m+1})<\delta$, that is $(\beta_{2m},\beta_{2m+1})\in G_\delta$, and since $\{x,y\}\setminus G_\delta\neq\emptyset$, we conclude that $f(\gamma)=\delta$, and $(\delta^*_0,\gamma)=(\delta_0,\gamma)$.

Now, if $m<n^*$, then by the very choice of $c’$, we have $$c’(\delta_0,\gamma)\in u_0\setminus \{c(\beta_{2m},\beta_{2m+1})\}.$$

If $m\ge n^*$, then $n:=m-n^*$ is a natural number, and so $$\delta_m<\beta_{2m}<\beta_{2m+1}<\delta_{m+1}$$ entails
$$i(n+1)=j(n)=\delta_m+1\le\beta_{2m}<\beta_{2m+1}<\delta_{m+1}<j(n+1).$$
Since $(\beta_{2m},\beta_{2m+1})\in G$, we get that $i(n+1)\le \beta_{2m}<f(\beta_{2m+1})$. Since $f$ is regressive, we get that $f(\beta_{2m+1})<\beta_{2m+1}<j(n+1)$. Altogether, $$(\beta_{2m},\beta_{2m+1})\in G_{j(n+1)}\setminus G_{i(n+1)},$$ and hence $$c’(\beta_{2m},\beta_{2m+1})\in u_{n+1}.$$
In particular, $$c’(\beta_{2m},\beta_{2m+1})\not\in u_0.$$This concludes the last case. $\blacktriangleleft$
This completes the proof of the main submclaim. $\blacksquare$

It follows from the main subclaim that for every $i<\lambda$, the subgraph $(G_i,E\restriction [G_i]^2)$ is countably chromatic. As $\lambda$ is regular, this in particular entails that every subgraph of $(G,E)$ of size $<\lambda$ is countably chromatic. $\blacksquare$

Corollary. If $\lambda$ is a strong limit singular cardinal, and $EH(\lambda^+)$ is countably chromatic, then $0^\sharp$ exists.
Proof. The covering lemma implies $\lambda^{\aleph_0}\le\lambda^+$ and $\square_\lambda$ for every strong limit singular cardinal $\lambda$. $\square_\lambda$ implies that every stationary subset of $\lambda^+$ admits a non-reflecting stationary subset. $\blacksquare$

We conclude this post by providing proofs to several easy facts (some of which were mentioned in the introduction).

Fact. if $\lambda$ is a regular cardinal, then any subgraph of $EH(\lambda)$ of size $<\lambda$ is countably chromatic.
Proof. Suppose that $\lambda$ is a regular cardinal, and $\mathcal F$ is a family of less than $\lambda$ many functions from $\lambda$ to $\omega$. For $f,g\in\mathcal F$ such that $f\bot g$, denote $$\Delta(f,g):=\min\{ \gamma<\lambda\mid \text{dom}(f\cap g)\subseteq\gamma\}.$$ Let $\gamma:=\sup\{ \Delta(f,g)\mid f,g\in\mathcal F, f\bot g\}$. As $|\mathcal F|<\text{cf}(\lambda)$, we get that $\gamma<\lambda$. Define $c:\mathcal F\rightarrow\omega$ by letting $c(f):=f(\gamma)$ for all $f\in\mathcal F$. Now, if $f,g\in\mathcal F$ and $f\bot g$, then $f(\gamma)\neq g(\gamma)$ for all $\gamma\ge\Delta(f,g)$ and hence $c$ is a chromatic coloring. $\blacksquare$

Fact. If $(G,E)$ is a graph  of size $\lambda$ such that every subgraph of size $<\lambda$ is countably chromatic, then the chromatic number of $EH(\lambda)$ is $\ge$ the chromatic number of $(G,E)$.
Proof. Without loss of generality, $G=\lambda$. For every $\gamma<\lambda$, let $c_\gamma:\gamma\rightarrow\omega\setminus\{0\}$ exemplify that $(\gamma,E\cap[\gamma]^2)$ is countably chromatic.
Next, for all $\alpha<\lambda$, define $f_\alpha\in{}^\lambda\omega$ by letting for all $\gamma<\lambda$:$$f_\alpha(\gamma):=\begin{cases}0,&\gamma<\alpha\\g_{\gamma+1}(\alpha),&\text{otherwise}\end{cases}.$$Note that if $\{\alpha,\beta\}\in E$, then $f_\alpha\bot f_\beta$ (indeed, $\Delta(f_\alpha,f_\beta)\le\min\{\alpha,\beta\}$). So, $\alpha\mapsto f_\alpha$ is a graph homomorphism, and the chromatic number of $EH(\lambda)$ is $\ge$ the one of $(G,E)$. $\blacksquare$

Corollary. The chromatic number of $EH(\aleph_1)$ is at least $\aleph_1$. $\blacksquare$

Fact. The chromatic number of $EH(\aleph_0)$ equals $2^{\aleph_0}$.
Proof. Clearly, the chromatic number of $EH(\aleph_0)$ is $\le2^{\aleph_0}$. Next, fix an injection $\psi:[\omega]^{<\omega}\rightarrow\omega$. For every $X\subseteq\omega$, let $f_X:\omega\rightarrow\omega$ be the function defined by $f_X(n):=\psi(X\cap n)$, for all $n<\omega$. Notice that if $X,Y$ are distinct infinite subsets of $\omega$, then $f_X\bot f_Y$. It follows that any chromatic coloring of $EH(\omega)$ must be injective over $\{ f_X\mid X\in[\omega]^\omega\}$, and hence the chromatic number of $EH(\omega)$ equals $2^{\aleph_0}$. $\blacksquare$

Fact. Suppose that $\mathbb T:=\langle T,\le\rangle$ is an $\aleph_1$-tree. Let $G(\mathbb T)$ denote the comparability graph of $\mathbb T$. If $G(\mathbb T)$ is countably chromatic, then $T$ is a special Aronszajn tree.
Proof. Recall that $G(\mathbb T)=(T,E)$, where $E=\{ \{x,y\}\in[T]^2\mid x\le y\text{ or }y\le x\}$. Now, if $C\subseteq T$ is a chain, then any chromatic coloring of $G(\mathbb T)$ must be injective over $C$. In particular, if $G(\mathbb T)$ is countably chromatic, then $\mathbb T$ is Aronszajn. Moreover, if $c:T\rightarrow\omega$ is a chromatic coloring, then it is easy to construct an order-preserving function $o:T\rightarrow\mathbb Q$. Simply define $o$ for all $x\in T$ by induction on $c(x)$, while insuring that $o[c^{-1}\{n\}]$ is finite for all $n<\omega$. $\blacksquare$

Trivia. Todorcevic proved that after Levy collapsing a supercompact to $\omega_2$, the following statement holds in the extension. If $\langle T,\le\rangle$ is a tree for which $G(T,\le)$ is not countably chromatic, then some subtree $T’\in[T]^{\aleph_1}$ already has the property that $G(T’,\le)$ is not countably chromatic.

Given an infinite cardinal $\lambda$, Shelah defines an ideal $I[\lambda]$ as follows.

Definition (Shelah, implicit in here). A set $S$ is in $I[\lambda]$ iff $S\subseteq\lambda$ and there exists a collection $\{ \mathcal D_\alpha\mid\alpha<\lambda\}\subseteq\mathcal [\mathcal P(\lambda)]^{<\lambda}$, and some club $E\subseteq\lambda$, so that for every $\delta\in S\cap E$, there exists a cofinal subset $A_\delta\subseteq\delta$ such that:

• $\text{otp}(A_\delta)<\delta$ (in particular, $\delta$ is singular);
• for every $\gamma<\delta$, there exists some $\alpha<\delta$ such that $A_\delta\cap\gamma\in\mathcal D_\alpha$.

In other words, $\bigcup_{\alpha<\delta}\mathcal D_\alpha$ contains all the initial segments of some small cofinal subset, $A_\delta$, of $\delta$.

Easy observations. 1) $E^\lambda_\omega\in I[\lambda]$;
2) if $\mu^{<\kappa}<\lambda$ for all $\mu<\lambda$, then $E^\lambda_\kappa\in I[\lambda]$;
3) if $S\subseteq\lambda$ is nonstationary, then $S\in I[\lambda]$;
4) if $\square_\lambda$ holds, then $I[\lambda^+]=\mathcal P(\lambda^+)$. (the definition of $\square_\lambda$ may be found in here.)
Proof hints. 1) Let $\mathcal D_\alpha:=[\alpha]^{<\omega}$ for all $\alpha<\lambda$.
2) Let $\mathcal D_\alpha:=[\alpha]^{<\kappa}$ for all $\alpha<\lambda$.
3) Take a club $E$ which is disjoint from $S$.
4) If $\langle C_\alpha\mid\alpha<\lambda^+\rangle$ is a $\square_\lambda$-sequence, then simply let $\mathcal D_\alpha:=\{\text{acc}(C_\alpha)\}\cup[C_\alpha]^{<\omega}$ for all $\alpha<\lambda^+$, and restrict your attention to $E:=\text{acc}(\lambda^+)$. $\square$

So, $I[\lambda^+]$ is rather trivial in the presence of $\square_\lambda$. On the other hand, it is a very sophisticated result of Mitchell, that $I[\lambda^+]$ may behave as the other extreme:

Theorem (Mitchell, 2009). Starting with a cardinal $\kappa$ which is $\kappa^+$-Mahlo, in some forcing extension, $I[\aleph_2]$ has the property that $S\cap E^{\aleph_2}_{\aleph_1}$ is nonstationary for every $S\in I[\aleph_2]$. $\square$

In other words, $I[\kappa^{++}]$ restricted to cofinality $\kappa^+$ may coincide with nonstationary ideal $NS^{\kappa^{++}}_{\kappa^+}$. Next, let us ask what about $I[\kappa^{++}]$ restricted to cofinality $\kappa$? it turns out that we are back on track here, and this follows from the trivial fact that $\kappa^{++}$ is a successor of a regular cardinal, together with the following less-trivial proposition:

Proposition (Shelah, 1991). $E^{\lambda^+}_{<\lambda}\in I[\lambda^+]$ for every regular cardinal $\lambda$.
Proof. Of course, we may assume that $\lambda>\aleph_0$. For every ordinal $\alpha<\lambda^+$, fix an injection $d_\alpha:\alpha\rightarrow\lambda$. Notice that for every $\alpha<\delta<\lambda^+$:

• $\forall i<\lambda\exists j\in[i,\lambda)$ such that $d_\delta^{-1}[i]\cap\alpha\subseteq d_\alpha^{-1}[j]$;
• $\forall i<\lambda\exists j\in[i,\lambda)$ such that $d_\delta^{-1}[j]\cap\alpha\supseteq d_\alpha^{-1}[i]$.

It follows that for all $\alpha<\delta<\lambda^+$, the following set is a club in $\lambda$: $$C_\alpha^\delta:=\{ i<\lambda\mid d_\delta^{-1}[i]\cap\alpha=d_\alpha^{-1}[i]\}.$$

Next, for all $\alpha<\lambda^+$, let $$\mathcal D_\alpha:=\{ d_\alpha^{-1}[i]\cap\gamma\mid \gamma\le\alpha,i<\lambda\}.$$ Clearly, $\{ \mathcal D_\alpha\mid \alpha<\lambda^+\}\subseteq[\mathcal P(\lambda^+)]^{\le\lambda}$. We now fix an arbitrary limit ordinal $\delta\in E^{\lambda^+}_{<\lambda}$, and show that $\bigcup_{\alpha<\delta}\mathcal D_\alpha$ contains all the initial segments of some small cofinal subset of $\delta$.
Let $u$ be a cofinal subset of $\delta$ of minimal order-type. In particular, $|u|<\lambda$, and hence $C:=\bigcap_{\alpha\in u}C^\delta_\alpha$ is a club in $\lambda$. Put $i:=\min(C\setminus\sup(d_\delta[u])+1)$, and $A_\delta:=d^{-1}_\delta[i]$. Then:

• $A_\delta\subseteq\delta$;
• $u\subseteq A_\delta$, and hence $\sup(A_\delta)=\delta$;
• $|A_\delta|=|i|$, and hence $|A_\delta|<\lambda$;
• for every $\alpha\in u$, as $i\in C^\delta_\alpha$, we have $ A_\delta\cap\alpha=d_\delta^{-1}[i]\cap\alpha=d_\alpha^{-1}[i]$;
• for every $\gamma<\delta$, letting $\alpha:=\min(u\setminus\gamma)$, we get that $$A_\delta\cap\gamma=A_\delta\cap\alpha\cap\gamma=d_\alpha^{-1}[i]\cap\gamma\in \mathcal D_\alpha.$$

This completes the proof. $\square$

We now arrive to the main result of today’s post:

Theorem (Shelah, 1993). If $\kappa$ is a regular cardinal, and $\kappa^+<\lambda$, then $I[\lambda]$ contains a stationary subset of $E^\lambda_\kappa$.
Proof. We already know that $E^\lambda_\omega\in I[\lambda]$. We also know that $E^\lambda_\kappa\in I[\lambda]$ in the case $\lambda=\kappa^{++}$. Thus, we shall assume that $\aleph_0<\kappa<\kappa^{++}<\lambda$.
In an earlier post, we proved that $E^{\aleph_3}_{\aleph_1}$ carries a club guessing sequence, and since here $\kappa$ is regular and uncountable, the same argument shows that $E^{\kappa^{++}}_\kappa$ carries a club-guessing sequence. Thus, let us fix such a club-guessing sequence $\overrightarrow C=\langle C_\beta\mid \beta\in E^{\kappa^{++}}_\kappa\rangle$. Next, fix a large enough regular cardinal $\theta$, and let $\overrightarrow M=\langle M_\alpha\mid \alpha<\lambda\rangle$ be an increasing sequence of elementary submodels of $(\mathcal H_\theta,\in)$ such that for all $\alpha<\lambda$:

• $|M_\alpha|<\lambda$;
• $\kappa^{++}+\alpha+1\subseteq M_{\alpha+1}$;
• $\overrightarrow C,\lambda\in M_\alpha$.

We shall now make a somewhat naive move, and simply let $\mathcal D_\alpha:=M_\alpha\cap\mathcal P(\lambda)$ for all $\alpha<\lambda$. Since $\mathcal D_\alpha\in[\mathcal P(\lambda)]^{<\lambda}$ for all $\alpha<\lambda$, the following set $S$ is obviously in $I[\lambda]$,$$S:=\{ \delta\in E^\lambda_\kappa\mid \exists A_\delta\subseteq\delta(\text{otp}(A_\delta)<\delta=\sup(A_\delta),\forall\gamma<\delta\exists\alpha<\delta[A_\delta\cap\gamma\in\mathcal D_\alpha])\}.$$

On the other hand, the next statement is not entirely obvious.

Subclaim. $S$ is stationary.
Proof. Given a club $D\subseteq\lambda$, we shall seek some $\delta\in S\cap D$. Wlog, $\min(D)>\kappa$.
Let $\overrightarrow N:=\langle N_i\mid i<\kappa^{++}\rangle$ be a sequence of of elementary submodels of $(\mathcal H_\theta,\in)$ such that for all $i<\kappa^{++}$:

• $|N_i|=\kappa^{++}$, with $\kappa^{++}\subseteq N_{i}$;
• $\langle N_j\mid j\le i\rangle\in N_{i+1}$;
• $\overrightarrow M, \overrightarrow C,D,\lambda\in N_i$;
• $N_i=\bigcup_{j<i}N_j$ whenever $i$ is a limit ordinal.

For all $i<\kappa^{++}$, as $D,\lambda\in N_i$ and $\sup(D)=\lambda$, we get by elementarity that $\sup(N_i\cap D)=\sup(N_i\cap\lambda)$. Recalling that $D$ is closed, we infer that $\sup(N_i\cap\lambda)\in D$ for all $i<\kappa^{++}$. Thus, it make sense to define a function $f:\kappa^{++}\rightarrow D$ by letting: $$f(i):=\sup(N_i\cap\lambda),\quad(i<\kappa^{++}.)$$
By the second and fourth defining properties of $\overrightarrow N$, we get that $f$ is increasing and continuous, and that $f\restriction\tau\in N_{\tau+1}$ for all $\tau<\kappa^{++}$. Put $\epsilon:=\sup(f[\kappa^{++}])$. Since $\kappa^{++}+\epsilon+1\subset M_{\epsilon+1}$, we get (by elementarity) the existence of some strictly-increasing and cofinal function $g:\kappa^{++}\rightarrow\epsilon$ that lies in $M_{\epsilon+1}$.
Since $f$ and $g$ are both continuous and cofinal in $\epsilon$, a standard back-and-fourth argument yields the existence of a club $c\subseteq\kappa^{++}$ for which $f\restriction c=g\restriction c$. Since $\overrightarrow C$ is a club guessing sequence, we may find some $\beta\in E^{\kappa^{++}}_\kappa$ such that $C_\beta\subseteq c$. Put $\delta:=f(\beta)$ and $A_\delta:=f[c_\beta]$. Then $\delta\in D\cap E^\lambda_\kappa$, and $A_\delta$ is a cofinal subset of $\delta$ of order-type $\kappa<\min(D)\le\delta$. Thus, we are left with showing that $A_\delta\cap\gamma\in\bigcup_{\alpha<\delta}\mathcal D_\alpha$ for all $\gamma\in A_\delta$.
Fix $\gamma\in A_\delta$, and let $\tau:=f^{-1}(\gamma)$. Then:

• $\tau+1<\beta$;
• $A_\delta\cap\gamma=g[c_\beta\cap\tau]$, and the latter belongs to $M_{\epsilon+1}$, since $g,\overrightarrow C,\beta,\tau\in M_{\epsilon+1}$ ;
• $A_\delta\cap\gamma=(f\restriction\tau)[c_\beta]$, and the latter belongs to $N_{\tau+1}$ since $f\restriction\tau,\overrightarrow C,\beta\in N_{\tau+1}$.

Denote $A:=A_\delta\cap\gamma$. Then $A\in M_{\epsilon+1}$, and $A,\overrightarrow M\in N_{\tau+1}$. Consequently: $$N_{\tau+1}\models \exists\alpha<\lambda(A\in M_\alpha).$$ It follows that there exists some $\alpha<\sup(N_{\tau+1}\cap\lambda)=f(\tau+1)<f(\beta)=\delta$ such that $A\in M_\alpha$. In particular, $A_\delta\cap\gamma\in\bigcup_{\alpha<\delta}\mathcal D_\alpha$. $\square$

So, $S$ is an example of a stationary subset of $E^\lambda_\kappa$ that belongs to $I[\lambda]$. $\square$

1. Notice that in the above proof, we could have replaced $\kappa^{++}$ with any regular cardinal $\mu<\lambda$ for which $E^\mu_\kappa$ carries a club-guessing sequence. In particular, the above proof shows:

Theorem (Shelah). If $\kappa<\kappa^+<\mu<\lambda$ are all regular cardinals, then there exists a subset $S\subseteq E^\lambda_\kappa$ such that:

• $S\in I[\lambda]$, and $S$ reflects in the following sense:
• $\{\delta\in E^\lambda_\mu\mid S\cap\delta\text{ is stationary}\}$ is stationary in $\lambda$. $\square$

2. The proof may be adapted to show that if $\kappa<\kappa^+<\lambda$ are regular, then there exists a sequence $\langle C_\delta\mid \delta\in E^\lambda_\kappa\rangle$, and an enumeration $\{ \mathcal D_\alpha\mid\alpha<\lambda\}\subseteq[\mathcal P(\lambda)]^{<\lambda}$, such that for every club $D\subseteq\lambda$, there exists $\delta\in\text{acc}(D)$ with:

• $\text{otp}(C_\delta)=\text{cf}(\delta)=\kappa$;
• $C_\delta$ is a club subset of of $D\cap\delta$;
• for every $\gamma<\delta$, there exists $\alpha<\delta$ such that $C_\delta\cap\gamma\in\mathcal D_\alpha$.

Yesterday, I attended a talk at the Quantum Foundations seminar at the beautiful Perimeter Institute for Theoretical Physics (Waterloo, Ontario).
The (somewhat provocative) title of the talk was “Is Classical Set Theory Compatible with Quantum Experiments?”, and the speaker was Radu Ionicioiu. Here are the links to the slides and videotape.

To make a long story short, the speaker addresses the Sakurai’s Bell inequality that can be thought of yielding a decomposition of a certain set $S(a_x,b_y)$ into two parts $S(a_x,b_y,c_+)$ and $S(a_x,b_y,c_{-})$, each of which being unknown/non-understood/non-definite, while each of these sets can be described as the set of all elements of the original set obeying a certain property. Thus:

“Recalling that ZFC‘s axiom of separation asserts that if $S$ is a set, and $\mathcal P$ is a property, then $\{ x\in S\mid \mathcal P(x)\text{ holds}\}$ is a set, we conclude that the results of the Sakurai-Bell experiment are incompatible with classical set theory (or incompatible with even more foundational logical rules, such as the law of excluded middle that implies that the union of the two sets would resurrect $S(a_x,b_y)$).”

Now, here are briefly my thoughts on this argument:

• The axiom of separation does not apply to arbitrary properties $\mathcal P(x)$. It only applies to formulas $\mathcal P(x)$ in the language of set theory! (Recall the paradox of the heap.)
• The discussed set (that admits an unclear decomposition) is finite – one of the participants of the seminar mentioned that it contains around 20k many elements. Partitioning a 20k-sized-set got nothing to do with ZFC!
• The superadditivity idea on slide 43 is a consequence of a confusion between undefined sets and the empty set. (some sets are undefined, some undefined objects are simply not sets, and in any case, undefined object is not necessarily the empty set).
• On slide 48, the speaker suggests that just as that the elimination of the fifth postulate from Euclidean geometry give rise to fertile (“non-Euclidean”) theories, the elimination of the separation scheme from ZFC could give rise to valuable theories. While this may sounds plausible, one should take into account that the fifth postulate is a restrictive axiom (hence, removing it, gives more freedom), while the separation axiom is responsible for the “existence” of sets (hence, removing it, kills many arguably-reasonable sets). To be even more picky, the axiom of separation anyway follows from the axiom of replacement, provided that an empty set exists.
• Nine years ago, I attended a talk by Guy Gildor, on his master thesis concerning a development of Set Theory within Fuzzy Logic. His work is perfectly rigorous, and may be found more convenient as foundations for quantum physics. I wonder if anyone ever considered that..?

Joint work with Stevo Todorcevic.

Extended Abstract: Consider the coloring statement $\lambda^+\nrightarrow[\lambda^+;\lambda^+]^2_{\lambda^+}$ for a given regular cardinal $\lambda$:

• In 1990, Shelah proved the above for $\lambda>2^{\aleph_0}$;
• In 1991, Shelah proved the above for $\lambda>\aleph_1$;
• In 1996, Shelah proved the above for $\lambda=\aleph_1$;
• In 2006, Moore proved the above for $\lambda=\aleph_0$.

In this paper, we provide a uniform proof of the fact that $\lambda^+\nrightarrow[\lambda^+;\lambda^+]^2_{\lambda^+}$ holds for every regular cardinal $\lambda$.

Downloads:

In Todorcevic’s class last week, he proved all the results of Chapter 8 from his Walks on Ordinals book, up to (and including) Theorem 8.1.11. The upshots are as follows:

• Every regular infinite cardinal $\theta$ admits a naturally defined function $osc:[\mathcal P(\theta)]^2\rightarrow\omega$;
• there exists, again natural, notion of unbounded subfamily of $\mathcal P(\theta)$, and if $\mathcal X$ is an unbounded subfamily of $\mathcal P(\theta)$, then $osc“[\mathcal X]^2=\omega$;
• if $\theta=cf(\theta)>\omega$ carries a non-trivial $C$-sequence (i.e., a sequence $\langle C_\alpha\mid\alpha<\theta\rangle$ such that $C_\alpha$ is a club in $\alpha$ for all limit $\alpha<\theta$, and such that for every club $D\subseteq\theta$, there exists an accumulation point $\alpha$ of $D$ such that $D\cap\alpha\nsubseteq C_\beta$ for all $\beta<\theta$), then, roughly speaking, there is a way to convert cofinal sets $A\subseteq\theta$ into sets $A’$ for which $\langle C_\alpha\mid \alpha\in A’\rangle$ forms an unbounded subfamily of $\mathcal P(\theta)$;
• building on the previous item, one can prove that every regular uncountable cardinal $\theta$ that carries a non-trivial $C$-sequence, admits a function $o:[\theta]^2\rightarrow\omega$ with the property that $o“[A]^2=\omega$ for every cofinal $A\subseteq\theta$.

I asked the lecturer whether a rectangular version of the above theorems is known. He started by saying that (in general) there is a huge difference between rectangular properties and square properties, and then provided the following:

• if $\mathcal X,\mathcal Y$ are unbounded subfamilies of $\mathcal P(\theta)$, then $osc[\mathcal X\times \mathcal Y]$ is co-finite;
• it is unknown whether there is an analogous way to convert cofinal subsets $A,B$ of $\theta$ to cofinal $A’,B’$ in way that will yield a function $o:[\theta]^2\rightarrow\omega$ with the property that $o“[A\circledast B]^2=\omega$ for every cofinal $A,B\subseteq\theta$.

Naturally, after proving that every successor of a singular cardinal admits a function that transforms rectangles into squares, I’ve been periodically looking for a mathematical evidence for this well-agreed “huge” difference between the two forms. Of course, there is this meta-evidence that it took two decades between Todorcevic’s theorem that $\omega_1\nrightarrow[\omega_1]^2_{\omega_1}$ holds in ZFC, to Moore’s theorem that $\omega_1\nrightarrow[\omega_1;\omega_1]^2_{\omega_1}$ holds in ZFC, yet, it was only today that I finally found what I was looking for.

In a plenary lecture at the Logic Colloquium 2008, Lajos Soukup mentions a concept (and results) that allows to contrast the rectangular version with the square version, as follows.

Theorem 1 (Erdos-Hajnal, 1978). If $f$ witnesses $\omega_1\nrightarrow[\omega_1;\omega_1]^2_{\kappa}$, then to any coloring $d:[\omega]^2\rightarrow\kappa$, there exists a strictly-increasing function $\psi:\omega\rightarrow\omega_1$ such that $$f(\psi(n),\psi(m))=d(n,m),\quad\text{ for all }n<m<\omega.$$

(so $f$ is universal for countable colorings $d:[\omega]^2\rightarrow\kappa$)

Theorem 2 (Shelah, 1975). CH entails the existence of a coloring $f$ that witnesses $\omega_1\nrightarrow[\omega_1]^2_\omega$, while $f\restriction[B]^2$ is not injective for every subset $B\subseteq\omega_1$ of size $>2$.

(so $f$ does not even embed injections of the form $d:[3]^2\rightarrow 3$)

Now, this is a huge difference indeed.

Before turning to the proofs, let us introduce the notion of a rainbow set. Given a coloring $f:[\lambda]^2\rightarrow\kappa$, we say that $X\subseteq\lambda$ is $f$-rainbow if $f\restriction[X]^2$ is injective. Then:

• Trivially, every coloring $f:[\lambda]^2\rightarrow\kappa$ with $\lambda\ge 2$ admits an  $f$-rainbow set of size $2$.
• Theorem 2 asserts that CH entails the existence of a coloring witnessing $\omega_1\nrightarrow[\omega_1]^2_{\omega}$ that does not admit a rainbow set of size $3$. Moreover, Shelah proved that $\diamondsuit(E^{\lambda^+}_\lambda)$ entails the existence of a coloring witnessing $\lambda^+\nrightarrow[\lambda^+]^2_{\lambda^+}$ that does not admit a rainbow set of size $3$. According to Hajnal, it is unknown whether these hypotheses are necessary.
• By Theorem 1, every coloring witnessing $\omega_1\nrightarrow[\omega_1;\omega_1]^2_{\omega}$ admits an infinite rainbow set. Hajnal proved that the same conclusion holds for coloring witnessing $\omega_1\nrightarrow[\omega_1,\omega_1]^2_{\omega}$.
• In his paper, Soukup points out that CH entails a coloring witnessing $\omega_1\nrightarrow[\omega;\omega_1]^2_{\omega_1}$ that does not admit an uncountable rainbow set. We noticed that any function witnessing $\omega_1\nrightarrow[\omega_1]^2_{\omega_1}$ does not admit an uncountable rainbow set. Either of the results shows that Theorem 1 cannot be improved to get universality for uncountable colorings.

Proof of Theorem 1. Suppose that $f$ witnesses $\omega_1\nrightarrow[\omega_1;\omega_1]^2_{\kappa}$ (or just $\omega_1\nrightarrow[\text{stat}(\omega_1);\text{stat}(\omega_1)]^2_\kappa$).

Subclaim. For every sequence $\langle S_n\mid n<\omega\rangle$ of stationary subsets of $\omega_1$, and every function $g:\omega\rightarrow\kappa$, there exists a sequence $\langle T_n\mid n<\omega\rangle$ such that:

• $T_0\subseteq S_0$ is a singleton;
• $T_n\subseteq S_n$ is stationary whenever $0<n<\omega$;
• $f[T_0\circledast T_n]=\{g(n)\}$ whenever $0<n<\omega$;
• $\max(T_0)<\min(T_n)$ whenever $0<n<\omega$.

Proof of subclaim. Suppose not, as witnessed by $\langle S_n\mid n<\omega\rangle$, and $g$. Then, for every $\alpha\in S_0$, there exists some positive $n<\omega$ such that $f[\{\alpha\}\circledast T_n]\neq\{g(n)\}$ for every stationary $T_n\subseteq S_n$. It follows that there exists some positive $m<\omega$, and a stationary $T\subseteq S_0$ such that $f[\{\alpha\}\circledast T_m]\neq\{g(m)\}$ for every $\alpha\in T$, and every stationary $T_m\subseteq S_m$. Pick clubs $\langle C_\alpha\mid \alpha<\omega_1\rangle$ such that $C_\alpha$ is disjoint from $\{ \beta\in S_m\mid f(\alpha,\beta)=g(m)\}$ for all $\alpha\in T$. Let $C=\Delta_{\alpha<\omega_1}C_\alpha$ be the diagonal intersection, and $T_m:=C\cap S_m$. Then for every $(\alpha,\beta)\in T\circledast T_m$, we get that $\beta\in C_\alpha$, and hence $f(\alpha,\beta)\neq g(m)$, contradicting the fact that $f[T\circledast T_m]=\kappa$. $\square$

Now, suppose that we are given $d:[\omega]^2\rightarrow\kappa$. For all $i<\omega$, let $g_i:\omega\rightarrow\kappa$ be a function satisfying $g_i(n)=d(i,n)$ whenever $i<n<\omega$. By a recursive application of the preceding subclaim, we may then find a matrix $\langle S_{i,n}\mid i<\omega,n<\omega\rangle$ such that:

• $S_{0,n}=\omega_1$ for all $n<\omega$;
• $S_{i+1,i}\subseteq S_{i,i}$ is a singleton for all $i<\omega$;
• $S_{i+1,i+n}\subseteq S_{i,i+n}$ is stationary whenever $i<\omega$ and $0<n<\omega$;
• $f[S_{i+1,i}\circledast S_{i+1,i+n}]=\{g_i(n)\}$, whenever $i<\omega$ and $0<n<\omega$;
• $\max(S_{i+1,i})<\min(S_{i+1,i+n})$, whenever $i<\omega$ and $0<n<\omega$.

Let $\psi:\omega\rightarrow\omega_1$ be the function satisfying $S_{i+1,i}=\{\psi(i)\}$ for all $i<\omega$. Then, $\psi$ is strictly increasing, and for every $i<n<\omega$, we have $\psi(i)\in S_{i+1,i}$ and $\psi(n)\in S_{i+1,n}$, and hence $$f(\psi(i),\psi(n))=g_i(n)=d(i,n). \square$$

Proof of Theorem 2. For all distinct $\eta,\rho\in{}^\omega2$, let $$\Delta(\eta,\rho):=\min\{ n<\omega\mid \eta(n)\neq\rho(n)\}.$$ Let $h:\omega\rightarrow\omega$ be a surjection such that $h^{-1}\{n\}$ is infinite for all $n<\omega$, and then define $f:[{}^\omega2]^2\rightarrow\omega$ by letting for all distinct $\eta,\rho\in{}^\omega2$: $$f(\eta,\rho):=h(\Delta(\eta,\rho)).$$

It is clear that for every $B\subseteq{}^\omega2$ of size $>2$, the function $f\restriction[B]^2$ is not injective, hence, our main goal is to find an uncountable $X\subseteq{}^\omega2$ for which $f\restriction[X]^2$ witnesses $\omega_1\nrightarrow[\omega_1]^2_{\omega}$.

Here goes. By CH, let $\{ A_i \mid i<\omega_1\}$ be some enumeration of $[{}^\omega2]^{\aleph_0}$. We now define a family $\{ \eta_i\mid i<\omega_1\}\subseteq{}^\omega2$ by recursion on $i<\omega_1$.
For the base case, we let $\eta_0$ be an arbitrary element of ${}^\omega2$.
Now, suppose that $i<\omega_1$ is nonzero, and that $\{ \eta_j\mid j<i\}$ has already been defined. Let

• $\{ A_k^{i}\mid k<\omega\}$ be some enumeration of $\{ A_j \mid j<i\}$, and
• $\{ \eta_k^{i}\mid k<\omega\}$ be some enumeration of $\{ \eta_j \mid j<i\}$.

$\eta_i$ will be defined as the limit of an increasing chain $\{ \rho_{i,k}\mid k<\omega\}\subseteq{}^{<\omega}2$ which will be set by recursion on $k<\omega$. Of course, we commence with letting $\rho_{i,0}:=\emptyset$.
Next, if $k<\omega$ and $\rho_{i,k}$ has been defined, we consider two cases:

1. $\rho_{i,k}\subseteq\sigma$ for some $\sigma\in A_{h(k)}^i$. In this case, we fix such $\sigma$ and find a large enough $l<\omega$ such that $|\rho_{i,k}|<l$ and $h(l)=|\{ t<k\mid h(t)=h(k)\}|$. We then let $$\rho_{i,k+1}:=(\sigma\restriction l){}^\frown\langle 1-\sigma(l)\rangle{}^\frown\langle 1-\eta^i_k(l+1)\rangle.$$
2. otherwise. In this case, we let $l:=|\rho_{i,k}|$, and put: $$\rho_{i,k+1}:=\rho_{i,k}{}^\frown\langle 1-\eta^i_k(l)\rangle.$$

Let $\eta_i:=\bigcup_{k<\omega}\rho_{i,k}$. Then, $\eta_i\in{}^\omega2$ and for all $k<\omega$, $\rho_{i,k+1}\subseteq\eta_i$, while $\rho_{i,k+1}\not\subseteq\eta^i_k$. In particular, $\eta_i\not\in\{\eta_j \mid j<i\}$. It follows that $X:=\{ \eta_i\mid i<\omega_1\}$ is uncountable.

Subclaim. $f\restriction[X]^2$ witnesses $\omega_1\nrightarrow[\omega_1]^2_{\omega}$.
Proof. Suppose that $A\subseteq X$ is uncountable, and $n<\omega$. We shall prove that $n\in f“[A]^2$. Fix a countable elementary submodel $M\prec H_{\omega_2}$ with $A\in M$. Let $j<\omega_1$ be such that $A_j=A\cap M$. Since $A$ is uncountable, pick a large enough $i\in(j,\omega_1)$ such that $\eta_i\in A\setminus M$. Let $m<\omega$ be such that $A_j=A^i_m$. Let $K:=\{ k<\omega\mid h(k)=m\}$. Let $k$ be the $n_{th}$ element of $K$. Then:

• $h(k)=m$;
• $|\{ t<k\mid h(t)=h(k)\}|=n$;
• $A^i_{h(k)}=A\cap M$.

As $\rho_{i,k}\in{}^{<\omega}2\subseteq M$ and $A\in M$, we get that $B:=\{ \sigma\in A\mid \rho_{i,k}\subseteq \sigma\}$ is in $M$. Since $\eta_i$ witnesses that $B$ is non-empty, we infer the existence of some $\sigma\in A\cap M$ such that $\rho_{i,k}\subseteq\sigma$. So, $\rho_{i,k+1}$ has been defined according to case 1, and there exists some $\sigma\in A\cap M$ and $l<\omega$ such that

• $h(l)=|\{ t<k\mid h(t)=h(k)\}|=n$, and
• $\eta_i\restriction(l+1)=(\sigma\restriction l){}^\frown\langle 1-\sigma(l)\rangle$.

It follows that $\Delta(\sigma,\eta_i)=l$, and hence $f(\sigma,\eta_i)=h(l)=n$. $\square$ $\square$

Proof of Soukup’s theorem. Recall the original construction of Erdos-Hajnal-Milner from CH of a function witnessing $\omega_1\nrightarrow[\omega;\omega_1]^2_{\omega_1}$. Let $\{ A_\gamma\mid \gamma<\omega_1\}$ be some enumeration of $[\omega_1]^{\aleph_0}$. For all infinite $\beta<\omega_1$ do the following:

• fix a surjection $\psi_\beta:\omega\rightarrow\beta$ such that $\psi_\beta^{-1}\{\gamma\}$ is infinite for all $\gamma<\beta$;
• pick an injection $\phi_\beta:\omega\rightarrow\omega_1$ such that $\phi_\beta(i)\in A_{\psi_\beta(i)}$ for all $i<\omega$. This can be done recursively, where at step $i<\omega$, we utilize the fact that $$|\phi_\beta[i]|=|i|<\aleph_0=|A_{\psi_\beta(i)}|.$$
• for all $\gamma<\beta$, denote $A_{\gamma,\beta}:=\{ \phi_\beta(i)\mid \psi_\beta(i)=\gamma\}$. Then $A_{\gamma,\beta}$ is an infinite subset of $A_\gamma$, and $\gamma_1<\gamma_2<\beta$ implies $A_{\gamma_1,\beta}\cap A_{\gamma_2,\beta}=\emptyset$.
• for all $\gamma<\beta$, fix a surjection $g_{\gamma,\beta}:A_{\gamma,\beta}\rightarrow\beta$.

Finally, pick a function $f:[\omega_1]^2\rightarrow\omega_1$ such that for all $\alpha<\beta<\omega_1$:

$$f(\alpha,\beta)=\begin{cases}
0,&\alpha\not\in\bigcup_{\gamma<\beta}A_{\gamma,\beta}\\
g_{\gamma,\beta}(\alpha),&\alpha\in A_{\gamma,\beta}
\end{cases}.$$

Subclaim. $f$ witnesses $\omega_1\nrightarrow[\omega;\omega_1]^2_{\omega_1}$.
Proof. Suppose that $Y$ is an infinite countable subset of $\omega_1$, $Z$ is an uncountable subset of $\omega_1$, and $\delta<\omega_1$. We shall show that $\delta\in f[Y\circledast Z]$.

Fix $\gamma<\omega_1$ such that $A_\gamma=Y$. Pick a large enough $\beta\in Z$ such that $\beta>\max\{\gamma,\delta,\sup(Y)\}$.

Since $\delta<\beta$ and $g_{\gamma,\beta}:A_{\gamma,\beta}\rightarrow\beta$ is surjective, we may now pick $\alpha\in A_{\gamma,\beta}$
such that $g_{\gamma,\beta}(\alpha)=\delta$. Then $\alpha\in A_{\gamma,\beta}\subseteq Y\cap\beta$ and $$f(\alpha,\beta)=g_{\gamma,\beta}(\alpha)=\delta. \square$$

It now follows from the upcoming observation that the function just constructed does not admit an uncountable rainbow set. $\square$

Observation. If $f$ witnesses $\kappa\nrightarrow[\kappa]^2_\theta$, then $f$ does not admit a rainbow set of size $\min\{\kappa,\theta^+\}$.
Proof. Given a set $X$ of size $\kappa$, decompose $X$ as $X_0\uplus X_1$, such that $X_i$ is of size $\kappa$, for all $i<2$. Then $f“[X_0]^2=\theta$ and $f“[X_1]^2=\theta$. In particular $f\restriction [X_0\cup X_1]^2$ is not injective. Given a set $X$ of size $\theta^+$, it is trivial that $f\restriction[X]^2:[X]^2\rightarrow\theta$ is not injective. $\square$

I gave a special session talk at the ASL 2012 North American Annual Meeting (Madison, March 31–April 3, 2012).

Talk Title: The extent of the failure of Ramsey’s theorem at successor cardinals.

Extended abstract: Ramsey’s theorem asserts that for every coloring $c:[\omega]^2\rightarrow2$, there exists an infinite subset $H\subseteq\omega$ such that $c\restriction [H]^2$ is constant. At the early 1930′s, Sierpinski showed that a generalization of Ramsey’s theorem must fail for successor cardinals, and ever since the extent of this failure was studied extensively by many set-theorists, including, Erdos, Eisworth, Hajnal, Moore, Shelah, and Todorcevic.

In this talk, we shall show that Shelah’s notion of strong coloring $\text{Pr}_0(\lambda^+,\lambda^+,\lambda^+,\omega)$ coincides with the most basic concept considered already by Erdos and his collaborators: $\lambda^+\not\rightarrow[\lambda^+]^2_{\lambda^+}$. More specifically, we shall discuss the following ZFC result.
Theorem. The following are equivalent for every uncountable cardinal $\lambda$:
(1) There exists a coloring $c:[\lambda^+]^2\rightarrow\lambda^+$ such that for every
(-) color $\gamma<\lambda^+$, and every
(-) subset $A\subseteq\lambda^+$ of size $\lambda^+$,
there exist $\alpha,\beta\in A$  with $\alpha<\beta$ such that $$c(\alpha,\beta)=\gamma.$$
(2) There exists a coloring $c:[\lambda^+]^2\rightarrow\lambda^+$ such that for every
(-) coloring $g:n\times n\rightarrow\lambda^+$ (here $n$ is a positive integer), and every
(-) family $\mathcal A\subseteq[\lambda^+]^n$ of size of $\lambda^+$ of mutually disjoint sets,
there exist $a,b\in\mathcal A$ with $\max(a)<\min(b)$ such that $$c(a_i,b_j)=g(i,j)\text{ for all }i,j<n.$$

(here, $a_i$ denotes the $i_{th}$-element of $a$, and $b_j$ denotes the $j_{th}$-element of $b$.)

Downloads:

While traveling downtown today, I came across a sign near a local church, with a quotation of Saint-Exupéry:

“Pure logic is the ruin of the spirit”? So sad.

Last night, I went to see a live show by Jane’s Addiction, in downtown Toronto. Here’s a video snippet from that show which I could found on YouTube:

The playlist was excellent, but there was one song which I was missing – “Had a dad”, so I compensate the loss, by including it here..:

After my previous post on Mekler’s characterization of c.c.c. notions of forcing, Sam, Mike and myself discussed the value of it . We noticed that a prevalent verification of the c.c.c. goes like this: given an uncountable set of conditions, apply the $\Delta$-system lemma, thin out the outcome some more (typically, a few iterations are needed) and then find two conditions in the thinned-out set which are already compatible. This successful method usually ends up showing more than the c.c.c. –  it shows that the poset has the Knaster property (i.e., every uncountable set of conditions, contains an uncountable subset of pairwise compatible conditions). However, if the notion of forcing does not have the Knaster property, then this method is unlikely to do the job. A-ha! So, that’s perhaps the value of Mekler’s verification method – to establish c.c.c. for posets which are not better than that. We decided to test this conjecture.
Todorcevic was around during our conversation, so we asked him for an example of a poset which is c.c.c., but does not have the Kanster property (of course, a Souslin tree is such an example, but Souslin trees are c.c.c. by definition, and we wanted to examine the verification method). He provided the following hint.

Example. Suppose that $\mathfrak b=\omega_1$, and let $\overrightarrow f=\langle f_\alpha\mid\alpha<\omega_1\rangle$ witness that. That is:

1. $f_\alpha\in{}^\omega\omega$ is an increasing function for all $\alpha<\omega_1$;
2. $\{ n<\omega\mid f_\alpha(n)\ge f_\beta(n)\}$ is finite, whenever $\alpha<\beta<\omega_1$;
3. for every $g\in{}^\omega\omega$, there exists some $\alpha<\omega_1$ such that $\{ n<\omega\mid g(n)<f_\beta(n)\}$ is infinite, whenever $\alpha<\beta<\omega_1$.

Let $\alpha\unlhd\beta$ iff $\{ n<\omega\mid f_\alpha(n)>f_\beta(n)\}$ is empty. Now, let $\mathbb P$ be the collection of all finite antichains of the poset $\langle\omega_1,\unlhd\rangle$, ordered by inclusion.

So, I tried to use the Mekler method to verify that $\mathbb P$ is c.c.c., without much of success. (What about you? can you suggest such a proof?)
Eventually, I did find a proof, and this finding lead me to yet another characterization:

(Ridiculously trivial) Observtion. Suppose that $\mathbb P$ is a given notion of forcing. Then the following are equivalent:

1. $\mathbb P$ is c.c.c.;
2. for every large enough regular cardinal $\kappa$, there exists an elementary submodel $\mathcal N\prec(\mathcal H(\kappa),\in)$ with $\mathbb P\in\mathcal N$, that enjoys the following feature. For every uncountable $A\subseteq\mathbb P$ in $\mathcal N$, there exists $q\in A\setminus\mathcal N$, and $r\in A\cap\mathcal N$ which are compatible.

A second look at Mekler’s proof of the Devlin-Shelah theorem makes it clear that the latter characterization may be utilized to establish the c.c.c. of the Devlin-Shelah notion of forcing. So, we did not lose anything. Yet, the above (ridiculously trivial) characterization is the key to the proof that I came up with of the following.

Proposition. $\mathbb P$ is c.c.c.
Proof. Let $\mathcal N$ be an arbitrary elementary submodel of $(\mathcal H(\kappa),\in)$ for a large enough $\kappa$, such that $\overrightarrow f,\mathbb P\in\mathcal N$. Suppose that we are given an uncountable subset $A\subseteq\mathbb P$ in $\mathcal N$. Fix an arbitrary $q\in A\setminus\mathcal N$, and let us find some $r\in A\cap\mathcal N$ which is compatible with $q$.

Before we begin, we introduce some notation.

1. For all $\alpha<\beta$, denote $$\Delta(\alpha,\beta):=\min\{ m<\omega\mid m\le n<\omega\rightarrow(f_\alpha(n)\le f_\beta(n))\};$$
2. For all $\alpha<\beta$, denote $$\Gamma(\alpha,\beta):=\min\{ m<\omega\mid m\le n<\omega\rightarrow(f_\alpha(n)< f_\beta(n))\};$$
3. For all $p\in\mathbb P$, and $m<\omega$, let $h_p^m:|p|\rightarrow{}^m\omega$ be the function satisfying $h_p^m(i)=f_\alpha\restriction m$ for the unique $\alpha\in p$ such that $|p\cap\alpha|=i$.

Here we go. Let $\rho=q\cap\mathcal N$. Then $\rho$ is a finite subset of $\mathcal N$, and hence in $\mathcal N$. Let $$S:=\{ \nu<\omega_1\mid \exists p\in A(p\cap\nu=\rho)\}.$$ Since $S\in\mathcal N$, and $\mathcal N\cap\omega_1\in S$ (as witnessed by $q$), we infer that $S$ is stationary. In particular, we may fix some $\nu\in S$ above $\max(q)$. Pick $p\in A\setminus\mathcal N$ such that $p\cap\nu=\rho$. Since $p\not\in\mathcal N$, we get that $p\neq\rho$ and $p\neq q$, so let $$m:=\max\{\Gamma(\alpha,\gamma)\mid \alpha<\gamma, \alpha\in q, \gamma\in p\}.$$

Put $h:=h^{m+1}_p$. Then $h\in\mathcal N$, and $p$ is a member of the following set (which lies in $\mathcal N$, as well): $$A(h,\rho):=\{ r\in A\mid h^{m+1}_r=h\ \& \exists\alpha<\omega_1(r\cap\alpha=\rho)\}.$$ In particular, we may pick some $r\in A(h,\rho)\cap\mathcal N$.
As $h^{m+1}_r=h^{m+1}_p$, we get that $|r|=|p|$, so let $\pi:r\rightarrow p$ be the order-preserving isomorphism. Then $\pi\restriction\rho$ is the identity map, and $f_\beta\restriction(m+1)=f_{\pi(\beta)}\restriction(m+1)$ for all $\beta\in r$.

We claim that $r$ and $q$ are compatible. Namely, that $\Delta(\beta,\alpha)>0$ for all $\beta<\alpha$ in $r\cup q$. Suppose that $\beta<\alpha$ are in $r\cup q$. For $\beta,\alpha\in r$ or $\beta,\alpha\in q$, it is immediate that $\Delta(\beta,\alpha)>0$, so suppose that $\beta\in r\setminus q$ and $\alpha\in q\setminus r$. As $r\cap q=\rho$, we get that $\beta<\alpha$. Let $\gamma:=\pi(\beta)$. By $f_\beta\restriction(m+1)=f_\gamma\restriction(m+1)$ and $\Gamma(\alpha,\gamma)\le m$, we get that $f_\alpha(m)< f_\gamma(m)=f_\beta(m)$, and hence $\Delta(\beta,\alpha)>m\ge 0$. $\square$

Note that essentially the same proof as above shows that $\mathbb P$ is productively c.c.c., and also that this works to any uncountable sequence of reals $\overrightarrow f$. So, what’s the role of $\mathfrak b=\aleph_1$? It is here to insure the following.

Proposition. $\mathbb P$ does not have the Knaster property.
Proof. Suppose that $A$ is an uncountable subset of $\mathbb P$. We shall find two conditions in $A$ which are incompatible. For this, we may already assume that $A$ forms a $\Delta$-system with a root $\rho$. In particular, $p\mapsto\min(p\setminus\rho)$ is an injection, and $B=\{ \min(p\setminus\rho)\mid p\in A\}$ is an uncountable subset of $\omega_1$. If we can find $\alpha<\beta$ in $B$ for which $\Delta(\alpha,\beta)=0$, then for the corresponding conditions $p,q\in A$ (i.e., $\alpha=\min(p\setminus\rho), \beta=\min(q\setminus\rho))$, we get that $p\cup q$ is not an antichain in the poset $\langle \omega_1,\unlhd\rangle$, and hence, $p$ and $q$ are incompatible.

Here we go. Fix a large enough regular cardinal $\kappa$, and then a countable elementary submodel $\mathcal N\preceq(H(\kappa),\in)$ with $B,\overrightarrow f\in\mathcal N$. Let $\delta:=\min(B\setminus\mathcal N)$. Evidently, $B\setminus(\delta+1)=\bigcup_{n<\omega}\{\beta\in B\setminus(\delta+1)\mid \Delta(\delta,\beta)=n\}$, so let us fix some $n<\omega$ such that $B_n:=\{\beta\in B\setminus(\delta+1)\mid \Delta(\delta,\beta)=n\}$ is uncountable. By the choice of $\overrightarrow f$ (more specifically, by item (3) there), we get that the set $$M:=\{ m<\omega\mid \sup\{ f_\beta(m)\mid \beta\in B_n\}=\omega\}$$ is non-empty (in fact, infinite), so consider its minimal element, $m:=\min(M)$.
For $t\in{}^m\omega$, denote $B^t_n:=\{ \beta\in B_n\mid t\subseteq f_\beta\}$. By minimality of $m$, the set $\{ t\in{}^m\omega\mid B^t_n\neq\emptyset\}$ is finite, so  we can easily find some $t\in{}^m\omega$ such that $$\sup\{ f_\beta(m)\mid \beta\in B^t_n\}=\omega.$$ Since $\{ \beta\in B\mid t\subseteq f_\beta\}$ is a non-empty set that lies in $\mathcal N$, let us fix some $\alpha\in\mathcal N\cap B$ such that $t\subseteq f_\alpha$. Put $k:=\Delta(\alpha,\delta)$, and then pick $\beta\in B^t_n$ such that $f_\beta(m)>f_\alpha(k+n)$. Of course, $\alpha<\delta<\beta$.
We claim that $\Delta(\alpha,\beta)=0$. This is best seen by dividing into three cases:

• if $i<m$, then $f_\alpha(i)=t(i)=f_\beta(i)$;
• if $m\le i\le k+n$, then $f_\alpha(i)\le f_\alpha(k+n)<f_\beta(m)\le f_\beta(i)$ (recall that the elements of $\overrightarrow f$ are increasing functions!);
•  if $k+n<i<\omega$, then $\Delta(\alpha,\delta)=k<i$ and $f_\alpha(i)\le f_\delta(i)$, as well as $\Delta(\delta,\beta)=n<i$ and $f_\delta(i)\le f_\beta(i)$. Altogether, $f_\alpha(i)\le f_\beta(i)$. $\square$

We conclude this post with an awkward proof of the following.

Fact. $\text{MA}_{\aleph_1}$ entails $\mathfrak b>\omega_1$.
Proof. Suppose not. Then $\text{MA}_{\aleph_1}$ is consistent together with the existence of a poset $\mathbb P=\langle P,\preceq\rangle$ of size $\aleph_1$ which is productively $c.c.c.$, but not Knaster. Define a poset $\mathbb Q=\langle Q,\le\rangle$, by $Q:={}^{<\omega}P$, and $q_1\le q_2$ (i.e., $q_2$ extends $q_1$) iff $\text{dom}(q_1)\subseteq \text{dom}(q_2)$, and $q_1(i)\preceq q_2(i)$ for all $i\in\text{dom}(q_1)$. Since $\mathbb P$ is productively $c.c.c$, $\mathbb Q$ is $c.c.c.$. Also, it a trivial fact that for any $p\in P$, and $q\in Q$, $q{}^\frown p\in Q$. So, $D_p:=\{ q\in Q\mid p\in\text{rng}(q)\}$ is dense in $\mathbb Q$, for all $p\in P$.
Finally, by $\text{MA}_{\aleph_1}$, let $G\subseteq Q$ be a directed set that meets any of the sets from the sequence $\langle D_p\mid p\in \mathbb P\rangle$. Denote $P_i:=\{ q(i)\mid q\in G\}$ for all $i<\omega$. Then $P=\bigcup_{i<\omega}P_i$. Since $G$ is $\le$-directed, $P_i$ is $\preceq$-directed for all $i<\omega$. It follows that for every uncountable $A\subseteq P$, there exists some $i<\omega$ such that $A\cap P_i$ is an uncountable subset of $A$ whose elements are pairwise compatible. That is, $\mathbb P$ has the Knaster property, contradicting the very choice of $\mathbb P$. $\square$