# Dushnik-Miller for singular cardinals (part 2)

• In the first post on this subject, we provided a proof of $\lambda\rightarrow(\lambda,\omega+1)^2$ for every regular uncountable cardinal $\lambda$.
• In the second post, we provided a proof of $\lambda\rightarrow(\lambda,\omega)^2$ for every singular cardinal $\lambda$, and showed that $\lambda\rightarrow(\lambda,\omega+1)^2$ fails for every cardinal of countable cofinality.
• In this post, we shall be dealing with the missing case, proving Shelah’s theorem that $\lambda\rightarrow(\lambda,\omega+1)^2$ holds for every singular cardinal $\lambda$ of uncountable cofinality, whose arithmetic configuration is somewhat relaxed.

Theorem (Shelah, 2009). Suppose that $\lambda$ is a singular cardinal of uncountable cofinality. If $2^{\text{cf}(\lambda)}<\lambda$, then $\lambda\rightarrow(\lambda,\omega+1)^2$.

Proof. Let $c:[\lambda]^2\rightarrow\{0,1\}$ be a given coloring for which $c“[B]^2≠\{1\}$ for all subsets $B\subseteq\lambda$ of order-type $\omega+1$. We shall prove that $c“[A]^2=\{0\}$ for some subset $A\subseteq \lambda$ of type $\lambda$.

Denote $\kappa:=\text{cf}(\lambda)$. Fix a strictly increasing sequence of regular cardinals $\langle \lambda_i\mid i<\kappa\rangle$ convergning to $\lambda$, such that $\lambda_0>2^{\kappa}$ and $\lambda_i\ge\Sigma_{j<i}\lambda_j^{++}$ for all $i<\kappa$. Let $\{ X_i\mid i<\kappa\}$ be a collection of mutually disjoint subsets of $\lambda$ such that $|X_i|=\lambda_i^{++}$ for all $i<\kappa$, and $\sup(X_i)<\min(X_j)$ for all $i<j<\kappa$. Indeed, we shall also assume that $c“[X_i]^2=\{0\}$ for all $i<\kappa$.

The first ranking funtion. For every $i<\kappa$, denote $X^i:=\bigcup_{j<i}X_j$. Then, for every $i<\kappa$ and $\alpha\in X_i$, let $$T_\alpha:=\left\{ t\in \mathcal P(X^i) \mid c“[t\cup\{\alpha\}]^2\subseteq\{1\}\right\}.$$

Notice that if $B\in T_\alpha$ is an infinite set, then $\text{otp}(B\cup\{\alpha\})=\omega+1$, with $c“[B\cup\{\alpha\}]^2=\{1\}$. As we are assuming that the latter fails for $c$, we infer that all elements of $T_\alpha$ are finite, and that the poset $(T_\alpha,\supseteq)$ is well-founded. It follows that any element $t$ of $T_\alpha$ admits a rank, which we shall denote by $rk_\alpha(t)$. Note that $\emptyset$ is in $T_\alpha$ and that it admits the maximal possible rank, which is some ordinal $<\lambda_i^+$ (because $|T_\alpha|\le|X^i|^{<\omega}\le\lambda_i$).

Given $i<\kappa, t\in [X^i]^{<\omega}$ and $\rho<\lambda_i^+$, let $$X_i(t,\rho)=\{\alpha\in X_i\mid t\in T_\alpha\ \&\ rk_\alpha(t)=\rho\}.$$
Next, for all $i<\kappa$, let $$Y_i:=X_i\setminus\bigcup\{ X_i(t,\rho)\mid t\in [X^i]^{<\omega}, \rho<\lambda_i^{+}, |X_i(t,\rho)|\le\lambda_i^{+}\}.$$

Then $|X_i\setminus Y_i|\le\lambda_i^{+}$. In particular, for every $\alpha\in Y_i$ and $t\in T_\alpha$, we have $$|X_i(t,rk_\alpha(t))\cap Y_i|=\lambda_i^{++}.$$

The second ranking funtion. Given a stationary subset $S\subseteq\kappa$, consider the poset  $\mathbb P_S:=\langle \prod_{i\in S}\lambda_i^+, <_S\rangle$, where $f<_S g$ iff $\{ i\in S\mid f(i)\ge g(i)\}$ is nonstationary. As the countable union of nonstationary sets is nonstationary,  the poset $\mathbb P_S$ is well-founded, and in particular, each of its elements $f$ admits a rank, which we shall denote by $||f||_S$.

The hybrid ranking funtion. Given a stationary subset $S\subseteq\kappa$ , a choice function $f\in\prod_{i\in S}Y_i$ and a shared node $t\in\bigcap_{i\in S}T_{f(i)}$ (e.g., $t=\emptyset$), we derive the function $f_t\in\prod_{i\in S}\lambda_i^+$ by letting $f_t(i):=rk_{f(i)}(t)$ for all $i\in S$. We then consider the rank $||f_t||_S$.

Let $$\rho:=\min\left\{ ||f_t||_S\mid S\subseteq\kappa\text{ stationary }, f\in\prod_{i\in S}Y_i, t\in\bigcap_{i\in S}T_{f(i)}\right\},$$ and then fix a triplet $(S,f,t)$, for which $\rho=||f_t||_S$.
For all $i\in S$, let $$Z_i:=X_i(t,f_t(i))\cap Y_i.$$ As $f(i)\in Y_i$ and $f_t(i)=rk_{f(i)}(t)$, we infer that $|Z_i|=\lambda_i^{++}$.
For all $\alpha<\lambda$, let $$S_\alpha:=\left\{ i\in S\mid c“[\{\alpha\}\cup Z_i]^2=\{0\}\right\}.$$

Consider the ideal $$I:=\{R\subseteq S\mid R\text{ is nonstationary, or it is stationary and }||f_t\restriction R||_R>||f_t||_S\},$$ and let $F$ denote its dual filter.

Subclaim. $F$ is a normal filter over $S$.
Proof. See Ari B.’s comments below for the idea of the proof) $\square$

Subclaim. For every $\alpha\in \bigcup_{j\in S}Z_j$, we have $S_\alpha\in F$.
Proof.  Suppose not, and let us fix $j\in S, \alpha\in Z_j$, for which $S_\alpha\not\in F$.
Put $R:=S\setminus(S_\alpha\cup j+1)$. Then $R$ is stationary and $||f_t\restriction R||_R\le ||f_t||_S$. We proceed as follows:

• For every $i\in R$, as $i\not\in S_\alpha$, let us pick some $g(i)\in Z_i$ such that $c(\alpha,g(i))=1$;
• Since $\alpha\in Z_j\subseteq X_j(t,f_t(j))$, we get that $t\in T_\alpha$, and hence $c“[t\cup\{\alpha\}]^2=\{1\}$;
• Likewise, for all $i\in R$, since $g(i)\in Z_i$, we get that $t\in T_{g(i)}$ and hence $c“[t\cup\{g(i)\}]^2=\{1\}$.

Altogether, we see that $c“[t\cup\{\alpha\}\cup\{g(i)\}]^2=\{1\}$ for all $i\in R$. In particular, $t\cup\{\alpha\}\in\bigcap_{i\in R}T_{g(i)}$, and we may consider the function $g_{t\cup\{\alpha\}}$.
For all $i\in R$, as $Z_i\subseteq X_i(t,f_t(i))$ and $g(i)\in Z_i$, we have $rk_{g(i)}(t)=rk_{f(i)}(t)$. As $rk_{g(i)}(t)>rk_{g(i)}(t\cup\{\alpha\})$, we infer that $g_{t\cup\{\alpha\}}(i)<f_{t}(i)$ for all $i\in R$. So $||g_{t\cup\{\alpha\}}||_R<||f_t\restriction R||_R\le ||f_t||_S=\rho$, contradicting the minimality of $\rho$. End of the proof of the subclaim.

Now is time to invoke the arithmetic hypothesis! More specifically, for all $i\in S$, as $2^\kappa<\lambda_i^{++}$, let us fix some $R^i\in F$ such that $\{\alpha\in Z_i\mid S_\alpha=R^i\}$ has size $\lambda_i^{++}$.

Put $R:=\{ j\in S\mid j\in\bigcap_{i\in S\cap j}R^i\}$.  Then $R\in F$, and it makes sense to consider the set $$A:=\bigcup_{i\in R}\left\{ \alpha\in Z_i\mid S_\alpha=R^i\right\}.$$ So $|A|=\lambda$, and we are left with verifying that $c“[A]^2=\{0\}$. Thus, let us fix $\alpha<\beta$ in $A$.
Let $i\le j$ be elements of $R$ such that $\alpha\in Z_i$ and $\beta\in Z_j$. We consider two cases:

1. If $i=j$, then $\alpha,\beta$ are elements of $Z_i\subseteq Y_i\subseteq X_i$, so simply recall that $c“[X_i]^2=\{0\}$;
2. Suppose that $i<j$. Since $j\in R$, we get that $j \in R^i$. Since $\alpha\in A$, we get that $R^i=S_\alpha$. So $j\in S_\alpha$ and $c“[\{\alpha\}\cup Z_j]^2=\{0\}$. But $\beta\in Z_j$, and hence $c(\alpha,\beta)=0$.

This completes the proof of the theorem. $\square$

This entry was posted in and tagged , , . Bookmark the permalink.

### 27 Responses to Dushnik-Miller for singular cardinals (part 2)

1. Ari B. says:

Hey, it’s not the same as when I printed it out on Tuesday. I think you added the ideal I. That wasn’t there before.

0 likes

• saf says:

That’s right. In the previous proof, I was working against the usual nonstationary ideal, but then ended up with an unjustified inequality: $||f_t\restriction R||_R\le ||f_t||_S$. Indeed, the role of the ideal I here is to justify this inequality.

If you can’t beat them – join them (to an ideal).. ;).

1 likes

2. Ari B. says:

A few minor corrections:
1) In the introductory sentence, I’m not sure what it means for the arithmetic configuration to be “relaxed”.
2) In the second paragraph of the proof, the strictly increasing sequence of regular cardinals needs to be cofinal in $\lambda$. (It is clear that this is the intention but it isn’t stated.)
3) I found a few places where the superscript 2 is missing in $c”[\dots]^2$: Once in the definition of the first ranking function, and three times in the proof of the subclaim.
4) In a few places the subscript $i$ is missing from $\lambda^{++}_i$: Once in the displayed equation just before the second ranking function, once just before the definition of $S_\alpha$, and once just before the definition of $R$.
5) In the definition of the second ranking function, the word “whereas” should be just “where”, and the letters $f$ and $g$ should be interchanged somewhere.
That’s all for now, though I haven’t quite got to the end!

0 likes

• saf says:

1) it’s an informal description of the upcoming well-stated theorem.
2–5) corrected.

0 likes

3. Ari B. says:

1) The word “stationary” is missing in the definition of the ideal $I$.
2) In the second sentence after the end of the proof of the subclaim, the condition $i<\kappa$ should be $i \in S$. You cannot refer to $Z_i$ otherwise, as it was defined only when $i\in S$.
3) In “End of the proof the of subclaim”, “the” and “of” are reversed.

0 likes

• saf says:

Corrected. Thanks!

0 likes

4. Ari B. says:

In the first paragraph of the proof, you say “For simplicity, we extend the definition of $c$ …”. I don’t see where this extension is ever used.

0 likes

• Ari B. says:

Never mind, I think it’s in the proof of the subclaim, which I haven’t absorbed yet.

0 likes

• saf says:

This is to insure that $\emptyset\in T_\alpha$ for all $\alpha$.

0 likes

• Ari B. says:

Interesting. I’m not sure it actually accomplishes that goal. Is $(\alpha,\alpha) \in [\{\alpha\}]^2$? It would probably be less ambiguous if you replace the $=\{1\}$ in the definition of $T_\alpha$ with $\subseteq \{1\}$.

0 likes

• saf says:

Good idea!

0 likes

• Ari B. says:

Now you can remove the sentence about extending the definition of $c$.

0 likes

5. Ari B. says:

1) In the second and third bulleted lines of the proof of the subclaim, the 1 at the end of each line should be $\{1\}$.
2) After defining the ideal $I$, it should be stated that $I$ is a normal ideal. This is necessary when you later use the diagonal intersection to claim that $R \in F$. You did mention in the seminar on Friday that the ideal is normal, but it’s not written here.
3) It may not hurt to be explicit about the fact that $I$ and $F$ are ideal and filter on $S$, not on $\kappa$.

0 likes

• saf says:

Done. Thanks!

p.s.
Would you be interested in providing a proof for the normality of $F$? you can post your proof in here (as a comment).

0 likes

• Ari B. says:

It would be pretty tedious to write the whole proof in detail so I think I will outline it in a few comments.

0 likes

• Ari B. says:

1) Let $R_1 \subseteq R_2$ both be stationary subsets of $\kappa$. If $g, h \in \prod_{i \in R_2} \lambda^+_i$ are such that $g <_{R_2} h$, then $g \restriction R_1 <_{R_1} h \restriction R_1$.

By induction on $\left\| h \right\|_{R_2}$, it follows that for every $h \in \prod_{i \in R_2} \lambda^+_i$, $\left\|h \restriction R_1\right\|_{R_1} \geq \left\|h\right\|_{R_2}$.

This guarantees that $I$ is closed under subsets.

0 likes

• Ari B. says:

I don’t know why the codes \| and \Vert aren’t giving the proper double-bar norm symbol like they do in LaTeX.

(using Google Chrome the $\|$ symbol appears fine, but with Firefox it doesn’t.)

0 likes

• Ari B. says:

2) Let $R_1 \subseteq R_2$ be stationary subsets of $\kappa$ such that $R_2 \setminus R_1$ is nonstationary. If $g, h \in \prod_{i \in R_2} \lambda^+_i$ then
$g <_{R_2} h \text{ if and only if } g \restriction R_1 <_{R_1} h \restriction R_1.$
By induction on $\left\| h \right\|_{R_2}$, it follows that for every $h \in \prod_{i \in R_2} \lambda^+_i$, $\left\|h \restriction R_1 \right\|_{R_1} = \left\|h\right\|_{R_2}$.

This guarantees that $I$ is closed under the union of two sets where one is stationary and the other is not.

0 likes

• Ari B. says:

3) Fix a cardinal $\theta < \kappa$ and pairwise disjoint stationary sets $\left\{ R_\xi : \xi < \theta \right\}$, and let $R = \bigcup_{\xi < \theta} R_\xi$.

If $\left\{ g_\xi : \xi < \theta \right\}$ and $\left\{ h_\xi : \xi < \theta \right\}$ are such that for all $\xi < \theta$ we have $g_\xi, h_\xi \in \prod_{i \in R_\xi} \lambda ^+_i$ and $g_\xi <_{R_\xi} h_\xi$, then $\bigcup_{\xi < \theta} g_\xi <_R \bigcup_{\xi < \theta} h_\xi$.

By induction on $\inf_{\xi<\theta} \left\|h_\xi\right\|_{R_\xi}$, it follows that for any $\left\{ h_\xi : \xi < \theta \right\}$ such that $h_\xi \in \prod_{i \in R_\xi} \lambda ^+_i$ for each $\xi<\theta$, we have
$\left\| \bigcup_{\xi<\theta} h_\xi \right\|_R = \inf_{\xi<\theta} \left\|h_\xi\right\|_{R_\xi}.$
This guarantees that $I$ is closed under the union of fewer than $\kappa$ pairwise disjoint stationary sets.

0 likes

• Ari B. says:

4) Given any collection of fewer than $\kappa$ (not necessarily pairwise disjoint) sets in $I$, the collection can be made pairwise disjoint without changing the values of $\left\|h_\xi\right\|_{R_\xi}$, using the fact that the nonstationary ideal is $\kappa$-complete and the result from part (2). Then part (3) gives that $I$ is $\kappa$-complete.

0 likes

• Ari B. says:

5) Fix pairwise disjoint stationary sets $\left < R_\xi : \xi \lt \kappa \right \gt$, and let $R = \bigtriangledown_{\xi < \kappa} R_\xi$.

If $\left \lt g_\xi : \xi \lt \kappa \right \gt$ and $\left \lt h_\xi : \xi \lt \kappa \right \gt$ are such that for all $\xi < \kappa$ we have $g_\xi, h_\xi \in \prod_{i \in R_\xi} \lambda ^+_i$ and $g_\xi <_{R_\xi} h_\xi$, then $\bigtriangledown_{\xi < \kappa} g_\xi <_R \bigtriangledown_{\xi < \kappa} h_\xi$.

By induction on $\inf_{\xi < \kappa} \left\|h_\xi\right\|_{R_\xi}$, it follows that for any $\left \lt h_\xi : \xi < \kappa \right \gt$ such that $h_\xi \in \prod_{i \in R_\xi} \lambda ^+_i$ for each $\xi<\kappa$, we have
$\left\| \bigtriangledown_{\xi<\kappa} h_\xi \right\|_R = \inf_{\xi<\kappa} \left\|h_\xi\right\|_{R_\xi}.$
This guarantees that $I$ is closed under the diagonal union of pairwise disjoint stationary sets indexed by $\kappa$.

0 likes

• Ari B. says:

6) Similar to part (4), if we have any collection of $\kappa$ (not necessarily pairwise disjoint) sets in $I$, the collection can be made pairwise disjoint without changing its diagonal union using the result from part (2), and then part (5) gives that the diagonal union is in $I$. This completes the result that $I$ is a normal ideal. Therefore its dual filter $F$ is a normal filter.

0 likes