So what does it mean when we say ${k_\beta}$ “almost works”? We’ll start with a lemma:

Lemma 1 For a fixed ${\nu\in^{<\omega}\mu}$, the set ${\{\alpha<\beta:\nu=\eta_\alpha\upharpoonright k_\beta(\alpha)+1\}}$ contains at most one element from each set ${A_{n+1}^\beta\setminus A^\beta_n}$, and hence is at most countable.

Proof: Suppose by way of contradiction what ${\alpha}$ and ${\gamma}$ are distinct members of ${A^\beta_{n+1}\setminus A^\beta_n}$ for which

$\displaystyle \nu=\eta_\alpha\upharpoonright (k_\beta(\alpha)+1)=\eta_\gamma\upharpoonright (k_\beta(\gamma)+1). \ \ \ \ \ (1)$

Then

$\displaystyle f^\beta_{n+1}(\alpha)=\eta_\alpha(k_\beta(\alpha))=\nu(k_\beta(\alpha))=\nu(k_\beta(\gamma))=\eta_\gamma(k_\beta(\gamma))=f^\beta_{n+1}(\gamma), \ \ \ \ \ (2)$

and this contradicts the fact that ${f^\beta_{n+1}}$ is a transversal for ${\{x_\epsilon:\epsilon\in A^\beta_{n+1}\}}$. $\Box$

Now given ${\alpha<\beta}$, we are going to define ${E(\alpha)}$ to be those ${\gamma<\beta}$ for which ${k_\beta}$ has failed to work, that is,

$\displaystyle E(\alpha)=\{\gamma<\beta:\max\{k_\beta(\alpha),k_\beta(\gamma)\}<\Delta(\alpha,\gamma)\}. \ \ \ \ \ (3)$

Lemma 2 The set ${E(\alpha)}$ is at most countable.

Proof: If not, find ${k^*<\omega}$ for which the set ${B:=\{\gamma\in E(\alpha):k_\beta(\gamma)=k^*\}}$ is uncountable, and set

$\displaystyle \nu=\eta_\alpha\upharpoonright k^*+1. \ \ \ \ \ (4)$

Then for each ${\gamma\in B}$, we have

$\displaystyle \eta_\gamma\upharpoonright k_\beta(\gamma)+1=\eta_\alpha\upharpoonright k^*+1=\nu, \ \ \ \ \ (5)$

which contradicts the preceding lemma. $\Box$

So for a given ${\alpha<\beta}$, the function ${k_\beta}$ will “disjointify” ${A_\alpha}$ from all but countably many ${A_\gamma}$ with ${\gamma<\beta}$: the function ${k_\beta}$ “almost works”.

Notice that ${\gamma\in E(\alpha)}$ if and only if ${\alpha\in E(\gamma)}$, so that we can define a graph ${\Gamma}$ on ${\beta}$ by connecting ${\alpha}$ and ${\gamma}$ if and only if ${\gamma\in E(\alpha)}$. By the preceding lemma, every vertex of the graph has at most countably many edges coming out of it. An easy argument tells us that the connected components of our graph ${\Gamma}$ are at most countable as well.

Now if ${\alpha}$ and ${\gamma}$ are members of different connected components of ${\Gamma}$ then ${k_\beta}$ will disjointify ${A_\alpha}$ and ${A_\gamma}$. But each connected component of ${\Gamma}$ can be disjointified easily (by induction) as it is at most countable.

Thus, it is straightforward now to “correct” ${k_\beta}$ to a function ${h_\beta}$ which will work everywhere.

Continuing the construction, let us assume that ${\mu}$ is singular of countable cofinality and ${{\rm cov}(\mu,\mu,\aleph_1,2)>\mu^+}$. For each ${\beta<\mu^+}$, let ${\langle A^\beta_n:n<\omega\rangle}$ be a sequence of sets such that

• ${A^\beta_0=\emptyset}$,
• ${\beta=\bigcup_{n<\omega}A^\beta_n}$,
• ${|A^\beta_n|<\mu}$ for all ${n<\omega}$, and
• ${A^\beta_n\subseteq A^\beta_{n+1}}$.

By induction on ${\alpha<\mu^+}$ we choose sets ${x_\alpha\in[\mu]^{\aleph_0}}$ such that for no ${\beta<\mu^+}$ and ${n<\omega}$ is ${x_\alpha}$ a subset of ${\bigcup\{x_\gamma:\gamma\in A^\beta_n\cap\alpha\}}$.

Notice that each set of the form ${\bigcup\{x_\gamma:\gamma\in A^\beta_n\cap\alpha\}}$ is of cardinality less than ${\mu}$, and there are ${\mu^+}$ sets of this form. Our assumption that ${{\rm cov}(\mu,\mu,\aleph_1,2)}$ is greater than ${\mu^+}$ tells us that a suitable ${x_\alpha}$ can always be found.

Let ${\eta_\alpha:\omega\rightarrow x_\alpha}$ be a bijection, and let ${A_\alpha:=\{\eta_\alpha\upharpoonright\ell:\ell<\omega\}}$. We will show that the collection ${\{A_\alpha:\alpha<\mu^+\}}$ will witness ${{\rm ADS}_\mu}$.

What this amounts to is that for each ${\beta<\mu^+}$, we need a function ${h_\beta:\beta\rightarrow\omega}$ so that

$\displaystyle \Delta(\alpha,\gamma)\leq\max\{h_\beta(\alpha),h_\beta(\gamma)\} \ \ \ \ \ (1)$

for all ${\alpha,\gamma<\beta}$, where

$\displaystyle \Delta(\alpha,\gamma)=\text{ least }\ell\text{ such that }\eta_\alpha(\ell)\neq\eta_\gamma(\ell). \ \ \ \ \ (2)$

Lemma 1 For each ${n<\omega}$, the family ${\{x_\alpha:\alpha\in A^\beta_n\}}$ has a transversal (i.e., a one-to-one choice function) ${f^\beta_n}$.

Proof: We define ${f^\beta_n\upharpoonright (A^\beta_n\cap\alpha)}$ by induction on ${\alpha}$. This is trivial for ${\alpha=0}$ and ${\alpha}$ limit. If ${\alpha=\gamma+1}$, then ${x_\gamma}$ is not a subset of ${\bigcup\{x_\epsilon:\epsilon\in A^\beta_n\cap\gamma\}}$ so ${f^\beta_n(\gamma)}$ can be defined easily. $\Box$

Armed with the preceding lemma, we define a function ${k_\beta:\beta\rightarrow\omega}$ as follows:

Given ${\alpha<\beta}$, we know ${\alpha\in A^\beta_{n+1}\setminus A^\beta_n}$ for some unique ${n<\omega}$. We define ${k_\beta(\alpha)}$ to be the unique ${k<\omega}$ such that ${f^\beta_n(\alpha)\eta_\alpha(k)}$.

In English, ${k_\beta(\alpha)}$ answers the question “when does ${\eta_\alpha}$ enumerate the value of ${f^\beta_n(\alpha)}$?”.

Our goal is to show that the function ${k_\beta}$ almost works, and then show how to modify ${k_\beta}$ to a function ${h_\beta}$ that actually does the job.

So our project is to present a proof of the following result of Shelah:

Theorem 1 Suppose ${\mu}$ is singular and ${{\rm cf}\mu=\aleph_0}$. If ${{\rm cov}(\mu,\mu,\aleph_1, 2)>\mu^+}$, then ${{\rm ADS}_\mu}$ holds.

We first prove a lemma that is intended to make our task a bit easier:

Lemma 2 Suppose ${\mu}$ is a singular cardinal of countable cofinality, and suppose ${A}$ and ${\langle A_\alpha:\alpha<\mu^+\rangle}$ are such that

• ${|A|=\mu}$,
• each ${A_\alpha}$ is a countable subset of ${A}$, and
• for each ${\beta<\mu^+}$, there are finite sets ${B^\beta_\alpha\subseteq A_\alpha}$ such that ${\{A_\alpha\setminus B^\beta_\alpha:\alpha<\mu^+\}}$ is pairwise disjoint.

Then ${{\rm ADS}_\mu}$ holds.

Proof: This is not completely trivial because ${{\rm ADS}_\mu}$ requires sets that are unbounded in ${\mu}$, but it is still an elementary argument. Let ${\pi:A\rightarrow\mu}$ be a bijection, and for each ${\alpha<\mu^+}$ let ${C_\alpha=\pi[A_\alpha]}$. Given ${\beta<\mu^+}$, if we let ${D^\beta_\alpha=\pi[B^\beta_\alpha]}$, then it is certainly the case that

$\displaystyle \{C_\alpha\setminus D^\beta_\alpha:\alpha<\beta\}\text{ is pairwise disjoint.} \ \ \ \ \ (1)$

Now we are almost to ${{\rm ADS}_\mu}$; all we are missing is that the ${C_\alpha}$ need to be unbounded in ${\mu}$. This probably won’t be true in general, but there is an ${\alpha^*<\mu^+}$ so that ${C_\alpha}$ is unbounded in ${\mu}$ whenever ${\alpha^*<\alpha<\mu}$. To see why, suppose this fails. Then we can find ${\theta<\mu}$ so that ${I:=\{\alpha<\mu^+: C_\alpha\subseteq\theta\}}$ is unbounded in ${\mu^+}$.

Now choose ${\beta<\mu^+}$ so that ${|I\cap\beta|=\theta^+}$. Now the collection ${\{C_\alpha\setminus D^\beta_\alpha:\alpha\in I\cap\beta\}}$ gives us a collection of ${\theta^+}$ disjoint subsets of ${\theta}$, and clearly this is absurd.

Thus, if we throw away the first ${\alpha^*}$ sets from our family, the remainder will witness ${{\rm ADS}_\mu}$. $\Box$

I guess the moral of the above is that in the case of singular ${\mu}$, we can safely drop the requirement that each ${A_\alpha}$ is unbounded in ${\mu}$ because this will be true from some point on anyway.

Returning now to the proof of the theorem, our plan is to proceed as follows:

We will define a certain family ${\langle x_\alpha:\alpha<\mu^+\rangle}$ of distinct countable subsets of ${\mu}$. We then set ${\eta_\alpha:\omega\rightarrow x_\alpha}$ to be some bijection, and define

$\displaystyle A_\alpha:=\{\eta_\alpha\upharpoonright\ell:\ell<\omega\}. \ \ \ \ \ (2)$

Since the sets ${x_\alpha}$ are distinct, the collection ${\{A_\alpha:\alpha<\mu^+\}}$ will form an almost disjoint collection of countable subsets of ${A:=^{<\omega}\mu}$, and our aim is to show that this collection satisfies the demands of the preceding lemma. Of course, this proof will depend on choosing the sets ${x_\alpha}$ quite carefully.

So, I think I’ve finished my “busy period”, and I have a little time to write. What I want to do today is post about the topic of my second lecture at this years Czech Winter School. The very first post I made on this blog dealt with an argument of Shelah that can be used to prove Solovay’s theorem that the Singular Cardinals Hypothesis holds above a strongly compact cardinal. The argument used a consequence of ${{\rm pp}(\mu)>\mu^+}$ as a “black box”; I want to take a look at the interior of this black box today.

Definition 1 Let ${\mu}$ a cardinal. We say that ${{\rm ADS}_\mu}$ holds if there is a sequence ${\langle A_\alpha:\alpha<\mu^+\rangle}$ such that each ${A_\alpha}$ is unbounded in ${\mu}$, and for each ${\beta<\mu^+}$, the collection ${\{A_\alpha:\alpha<\beta\}}$ is essentially disjoint, in the sense that there is a function ${F_\beta:\beta\rightarrow\mu}$ such that the collection ${\{A_\alpha\setminus F_\beta(\alpha):\alpha<\beta\}}$ is disjoint.

Some things to note:

• ${{\rm ADS_\mu}}$ always holds if ${\mu}$ is regular (any “almost disjoint” family of size ${\mu^+}$ has the required property).
• If ${\mu}$ is singular and ${{\rm ADS}_\mu}$ holds, then we may assume each ${A_\alpha}$ is of order-type ${{\rm cf}(\mu)}$.
• ${{\rm ADS_\mu}}$ for ${\mu}$ singular implies that that there is no countably complete uniform ultrafilter on ${\mu^+}$ — this is the content of the very first post I made on this blog.
• ${{\rm ADS_\mu}}$ follows from the existence of a better scale (and hence it follows from each of weak square and ${{\rm pp}(\mu)>\mu^+}$). The details of this are in my Handbook of Set Theory article.

What I want to do here is derive ${{\rm ADS_\mu}}$ from the assumption that ${\mu}$ is a singular cardinal of countable cofinality satisfying ${{\rm cov}(\mu,\mu,\aleph_1, 2)>\mu^+}$. Remember this means that for any family ${\mathcal{F}\subseteq[\mu]^{<\mu}}$ of cardinality ${\mu^+}$, there is a countable ${A\subseteq\mu}$ not covered by any member of ${\mathcal{F}}$. I’ll just state the theorem, and spread the proof out over the next couple of days in some more blog posts.

Theorem 2 (Shelah) Suppose ${\mu}$ is singular and ${{\rm cf}\mu=\aleph_0}$. If ${{\rm cov}(\mu,\mu,\aleph_1, 2)>\mu^+}$, then ${{\rm ADS}_\mu}$ holds.