On ADS (Part 4)

February 10, 2012 at 14:40 | Posted in Uncategorized | Leave a comment

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)


\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.

On ADS (Part 3)

February 9, 2012 at 11:40 | Posted in Uncategorized | Leave a comment

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.

On ADS (Part 2)

February 7, 2012 at 11:11 | Posted in Uncategorized | Leave a comment

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.


February 6, 2012 at 11:13 | Posted in Uncategorized | Leave a comment

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.

Blog at WordPress.com.
Entries and comments feeds.