- 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:
- 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\}$;
- 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$
Pingback: Dushnik-Miller for regular cardinals (part 1) | Assaf Rinot
Pingback: Dushnik-Miller for singular cardinals (part 1) | Assaf Rinot
Pingback: Toronto Set Theory Seminar « Set Theory Talks
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.
That’s right. In the previous proof, I was working against the usual nonstationary ideal, but then ended up with an unjustified inequality: $||f_trestriction R||_Rle ||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).. ;).
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!
Thank you very much for your comments! I appreciate it.
1) it’s an informal description of the upcoming well-stated theorem.
2–5) corrected.
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 $iin S$.
3) In “End of the proof the of subclaim”, “the” and “of” are reversed.
Corrected. Thanks!
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.
Never mind, I think it’s in the proof of the subclaim, which I haven’t absorbed yet.
This is to insure that $emptysetin T_alpha$ for all $alpha$.
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}$.
Good idea!
Now you can remove the sentence about extending the definition of $c$.
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$.
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).
It would be pretty tedious to write the whole proof in detail so I think I will outline it in a few comments.
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_1right|_{R_1} geq left|hright|_{R_2}$.
This guarantees that $I$ is closed under subsets.
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.)
Ari, Vert looks fine in Firefox 10 (though somewhat too close together)
For a complete list of commands available in MathJax see http://www.mathjax.org/docs/1.1/tex.html#supported-latex-commands
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|hright|_{R_2}$.
This guarantees that $I$ is closed under the union of two sets where one is stationary and the other is not.
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_xiright|_{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_xiright|_{R_xi}.
]
This guarantees that $I$ is closed under the union of fewer than $kappa$ pairwise disjoint stationary sets.
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_xiright|_{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.
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_xiright|_{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_xiright|_{R_xi}.
]
This guarantees that $I$ is closed under the diagonal union of pairwise disjoint stationary sets indexed by $kappa$.
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.
Pingback: » Toronto Set Theory Seminar Set Theory Talks