# Coloring With Scales!

So the point of this post is to work through one of Shelah’s results that (roughly speaking) allows us to create a complicated coloring if we have a scale in hand. We begin with a few definitions.

Def: Let $\lambda, \kappa, \theta$ be cardinals with $\kappa+\theta<\lambda$. We say that $\mathrm{Pr}_1(\lambda, \kappa,\theta)$ holds if there is a coloring $[\lambda]^2\to\kappa$ of the pairs of $\lambda$ in $\kappa$-many colors such that:

Given a sequence $\langle t_\alpha : \alpha<\lambda\rangle$ of pairwise disjoint elements of $[\lambda]^{<\theta}$, and an ordinal $\zeta<\lambda$, there are $\alpha<\beta$ such that for every $\gamma\in t_\alpha$ and $\delta\in t_\beta$, we have $c(\{\gamma,\delta\})=\zeta$.

We can think of $\mathrm{Pr}_1(\lambda, \kappa,\theta)$ as a strong form of the assertion that $\lambda\not\to[\lambda]^2_\kappa$. For example, if we let $\mu$ be a singular cardinal, then $\mathrm{Pr}_1(\mu^+, \mu^+,2)$ says that there is a coloring $c:[\mu^+]^2\to \mu^+$ such that: Given any set $H\in[\mu^+]^{\mu^+}$ and any ordinal $\zeta<\mu$, there are $\alpha,\beta\in H$ such that $c(\{\alpha,\beta\})=\zeta$. In other words, this family of coloring principles assert that Ramsey’s theorem fails miserably, and in particular $\mathrm{Pr}_1(\mu^+, \mu^+,2)$ tells us that $\mu^+$ fails to be Jónsson in an incredibly spectacular way.

What I want to do in this post is work through a result of Shelah’s which allows us to produce witnesses to $\mathrm{Pr}_1(\mu^+, cf(\mu),cf(\mu))$ for any singular cardinal $\mu$ by using a scale to color pairs of $\mu^+$. First recall what a scale is.

Def: Let $\mu$ be singular. We say that the pair $(A,\vec f)$ is a scale on $\mu$ if:

1. $A$ is a set of regular cardinals cofinal in $\mu$;
2. $|A|<\min(A)$;
3. $\vec f=\langle f_\alpha : \alpha<\mu^+\rangle$ is strictly increasing and cofinal in $\prod A/J^{bd}[A]$ where $J^{bd}[A]$ is the ideal of bounded subsets of $A$.

A theorem of Shelah’s tells us that scales exist. Scales allow us to show that some of the combinatorial information on $\mu^+$ can be pulled down to $\mu$ or even $cf(\mu)$. In particular, scales are extremely useful for elementary submodel arguments because they allow us to smuggle information about $\mu^+$ into our submodel without needing all of $\mu$ or even $\mu^+$ present. This will be made apparent in the proof of the following (which can be found on page 67 of Cardinal Arithmetic):

Lemma 4.1B: (Shelah) Let $(A,\vec f)$ be a scale on $\mu$. Then, letting $\kappa=\min\{ |A\setminus a|: a\in A\}$ the principle $\mathrm{Pr}_1(\mu^+, \kappa,cf(|A|))$ holds. In particular, $\mathrm{Pr}_1(\mu^+, cf(\mu), cf(\mu))$ always holds.

The coloring used in the proof of the above lemma basically takes two ordinals $\alpha<\beta$ to the first point past which $f_\alpha$ and $f_\beta$ diverge completely. Much in the same way that coloring using Skolem functions is a useful technique, it’s nice to have this coloring lying around since scales always exist.

Proof: We begin by fixing a scale $(A,\vec f)$ as in the hypotheses, and let $\lambda=\mu^+$. Let $|A|=\theta$, and index $A=\{\mu_i : i<\theta\}$ so we may think of a function $f\in \prod A$ as a function in $\prod_{i<\theta}\alpha_i$. Now partition $A$ into $\kappa$-many pieces by way of $h: A\to \kappa$ such that $h^{-1}[\{\zeta\}]$ is unbounded in $\mu$ for each $\zeta<\kappa$. For ease of notation, let $A_\zeta=h^{-1}[\{\zeta\}]$. Now we define two colorings, $d,c$ on pairs of $\lambda$ as follows:

Let $d: [\lambda]^2\to\mu$ be defined by $d(\{\alpha,\beta\})=\sup\{i<\theta : f_\alpha(i)\geq f_\beta(i)\}$ for $\alpha<\beta$.

Let $c:[\lambda]^2\to\mu$ be defined by $c(\{\alpha,\beta\})=h(\mu_{d(\{\alpha,\beta\})})$. So $d$ takes a pair to the first point where their corresponding functions diverge, and $c$ takes the associated cardinal in $A$ to which piece of the partition that cardinal lies in. We claim that $c$ witnesses $\mathrm{Pr}_1(\lambda, \kappa,cf(\theta))$. With that said, fix a sequence $\langle t_\alpha : \alpha of pairwise disjoint elements of $[\lambda]^{ and note that there is some $\xi such that, for $\lambda$-many $\alpha<\lambda$, we have $t_\alpha=\{ t_\alpha^\eta : \eta<\xi\}$. So, we may as well assume that each $t_\alpha$ has this property by thinning out the collection we were originally handed, and reindexing. Further, let $\zeta<\kappa$ be a given color.

We want to show that there are $\alpha<\beta<\lambda$ such that for each $\eta_1,\eta_2<\xi$ we have $c(\{t_\alpha^{\eta_1},t_\beta^{\eta_2}\})=\zeta$. There are going to be a lot of indices to keep track of, but keeping the goal in mind (no matter how horrible it looks) will help. Our main tool for proving that this coloring is appropriate will be elementary submodels, so let $\xi$ be regular, and large enough with $M\prec \mathfrak{A}=(H(\theta),\in,<_\theta)$ such that:

1. $\{\lambda, \zeta, \langle t_\alpha : \alpha<\lambda\rangle, \vec f\}\subseteq M$;
2.  $\zeta\cup A\subseteq M$;
3. $|M|<\mu$.

It won’t quite be apparent why we’re utilizing this machinery until a little bit later. Now since the collection $\langle t_\alpha : \alpha<\lambda\rangle$ is disjoint, we can assume that $t_\alpha^\eta\geq\alpha$ for each $\alpha<\lambda$ by reindexing the sets $t_\alpha$, and perhaps chopping off initial segments. Next let $A'=\{\mu_i\in A : \sup (M\cap \mu_i)<\mu_i\}$ and define the characteristic function of $M$ with respect to $A$ by $Ch^A_M(i)=\sup (M\cap \mu_i)$ for every $\mu_i\in A'$ and $0$ everywhere else. Since $|M\cap \lambda|<\mu$, it follows that $Ch^A_M$ is non-zero almost everywhere (mod bounded) and so is in $\prod A/J^{bd}[A]$. Next since $\vec f$ is cofinal in $\prod A/J^{bd}[A]$, there is some $\beta(0)<\lambda$ such that:

1. $Ch^A_M <_{J^{bd}[A]}f_{\beta(0)}$;
2. $\beta(0)>\sup (M\cap \lambda)$.

So not only does $f_{\beta(0)}(i)$ get above $\sup (M\cap \mu_i)$ almost everywhere, we have that $\beta(0)> \sup (M\cap \lambda)$. This will allow us to take an appropriate Skolem Hull of $M$ and know that these things still happen. Next, since $t^\eta_{\beta(0)}\geq\beta(0)$, we can fix for each $\eta<\xi$ an index $i_eta$ such that: For every $j\geq i_\eta$, we have that $Ch^A_M(j). Let $i(0)=\sup\{i_\eta : \eta<\xi\}<\theta$ since $\xi, so then for every $j> i(0)$ and every $\eta<\xi$, we have $Ch^A_M(j). This give us a pair of canonical witnesses to the fact that $M\cap\lambda$ is thin, and gives us one of the indices we will use to witness the desired coloring property. So our next goal is to find our second (smaller) witness, which we will want $M$ to see enough of.

For each $\alpha<\lambda$, define a function $f_\alpha^*\in\prod \mu_i$ by:

$f_\alpha^*(i)=\min\{ f_{t^\eta_\alpha}(i) : \eta<\xi\}$.

Note that since $t^\eta_\alpha\geq\alpha$, we have that $f_\alpha\leq_{J^{bd}[A]} f^*_\alpha$. So above each $f_\alpha$, we have $\xi$-many functions $f_{t^\eta_\alpha}$ above it, and we are letting $f_\alpha^*(i)$ be the closest approximation to $f_\alpha$ we can get by way of these ladders of functions. Next let $A^*=\{\mu_i\in A : \sup\{f_\alpha^*(i): \alpha<\lambda\}=\mu_i\}$, which we claim is $J^bd[A]$-equivalent to $A$. Otherwise, suppose that $A\setminus A^*\notin J^{bd}[A]$, and define a function $g\in \prod A$ by $g(i)= \sup\{f_\alpha^*(i): \alpha<\lambda\}$ if $\mu_i\in A\setminus A^*$ and $0$ otherwise. As before, we can find some $\alpha<\lambda$ such that $0<_{J^{bd}[A]}g<_{J^{bd}[A]} f_\alpha\ \leq_{J^{bd}[A]} f^*_\alpha$ which is absurd. Now we pick an index $i(1)<\xi$ such that:

1. $i(1)\in A_\zeta\cap A^*$;
2. $i(1)>i(0)$;
3. $A\setminus \mu_{i(1)}\subseteq A'$;
4. $i(1)>|M|$.

We now make our first approximation to our desired companion to $\beta(0)$. We let $\beta(1)$ be such that

$\tau:= f^*_{\beta(1)} (i(1))>\sup\{f_{t^\eta_{\beta(0)}}(i(1)) : \eta<\xi\}$

We note that such a choice is possible, as $a(1)\in A^*$ implies that $\sup\{f_\alpha^*(i(1)):\alpha<\lambda\}=\mu_{i(1)}$ whereas $\sup\{f_{t^\eta_{\beta(0)}}(i(1)) : \eta<\xi\}<\mu_{i(1)}$ since $\xi. Really, we only wanted to find an index such that we can get above each $f_{t^\eta_{\beta(0)}}(i(1))$, and the important thing here is $\tau$. With that said, let $N=Sk^{\mathfrak{A}}(M\cup\{\tau\})$, and note that we have $\mathfrak{A}\models (\exists \alpha<\lambda)(f_\alpha^*(i(1))=\tau)$. So by elementarity we have

$N\models (\exists \alpha<\lambda)(f_\alpha^*(i(1))=\tau)$ by our requirements on $M$, and the fact that $\tau\in N$. So let $\beta(2)\in N\cap\lambda$ be such that $f_{\beta(2)}^*((i(1))=\tau$. Thus:

$\eta_1,\eta_2<\xi\implies f_{t^{\eta_1}_{\beta(0)}}(i(1))<\tau=f^*_{\beta(2)}(i(1))\leq f_{t^{\eta_2}_{\beta(2)}}(i(1))$.

We claim that $\beta(0)$ and $\beta(2)$ are as desired. That is, we need to show that $\beta(2)<\beta(0)$ and for every pair $\eta_1,\eta_2$, we have $c(\{t^{\eta_1}_{\beta(2)},t^{\eta_2}_{\beta(0)}\})=\zeta$ (so also that $t^{\eta_1}_{\beta(2)}). So if we can show that $\sup \{i<\theta : f_{t^{\eta_1}_{\beta(2)}}(i)\geq f_{t^{\eta_2}_{\beta(0)}}(i)\}=i(1)$, then we are done since $i(1)\in A_\zeta$. But by the above inequality, we only have to show the following three things:

1. $\beta(2)<\beta(0)$;
2. For every pair $\eta_1,\eta_2$, we have $t^{\eta_1}_{\beta(2)};
3. For every $j>i(1)$, we get that $f_{t^{\eta_1}_{\beta(2)}}(j).

By a lemma due to Baumgartner,  we have that (by our choice of $i(1)$, for every regular $\sigma \in M$, if $\sigma>\mu_{i(1)}$, then

$\sup (M\cap \sigma)=\sup(N\cap\sigma)$.

Now since $\lambda>\mu_{i(1)}$, it follows since $\beta(0)>\sup (M\cap \lambda)$, that $\beta(0)>\sup(N\cap\lambda)$ as well. But since $\beta(2)\in N\cap\lambda$, we have that $\beta(0)>\beta(2)$, and similarly $t^{\eta_1}_{\beta(2)}<\beta(0)\leq t^{\eta_2}_{\beta(0)}$ for each $\eta_1,\eta_2<\xi$ since each $t^{\eta_1}_{\beta(2)}$ is definable from parameters in $N$. Now that we’ve shown 1. and 2. above, we only need to show 3.

Now for every $j\geq i(1)$, and $\eta_1,\eta_2<\xi$ we have that $f_{t^{\eta_1}_{\beta(2)}}(j)\in N$ since it’s definable from parameters, and hence $f_{t^{\eta_1}_{\beta(2)}}(j). On the other hand, our choice of $\beta(0)$ tells us that $Ch^A_m(j) < f_{t^{\eta_2}_{\beta(0)}}(j)$, and so the result follows.