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<mu^+\rangle of pairwise disjoint elements of [\lambda]^{<cf(\theta)} and note that there is some \xi<cf(\theta) 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)<f_{t^\eta_{\beta(0)}}(j). Let i(0)=\sup\{i_\eta : \eta<\xi\}<\theta since \xi<cf(\theta), so then for every j> i(0) and every \eta<\xi, we have Ch^A_M(j)<f_{t^\eta_{\beta(0)}}(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<cf(\theta)\leq \theta<\min (A). 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)}<t^{\eta_2}_{\beta(0)}). 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)}<t^{\eta_2}_{\beta(0)};
  3. For every j>i(1), we get that f_{t^{\eta_1}_{\beta(2)}}(j)<f_{t^{\eta_2}_{\beta(0)}}(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)<Ch^A_M(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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s