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.

Happy New Year

January 10, 2012 at 09:36 | Posted in Uncategorized | 3 Comments

Well, for you Terry Pratchett fans out there “I aten’t Dead”. I got surprised by some real world things over break so I spent my time handling those instead of thinking about pcf theory. Nothing serious, but it did require my attention.

Besides, don’t 90% of blog posts consist of people apologizing for not updating the blog?

But Happy New Year. I actually kept the project up for 1 year, and it should keep going.

Consequences of no inaccessible accumulation point

November 28, 2011 at 14:05 | Posted in Uncategorized | Leave a comment

This post is just an organizational one without any proofs. I wanted to list a few consequences of the following conjecture of Shelah:

  • If {\mathfrak{a}} is a progressive set of regular cardinals, then {{\rm pcf}(\mathfrak{a})} does not have a weakly inaccessible point of accumulation.

Equivalently, if {\mathfrak{a}} is a progressive set of regular cardinals, then {{\rm pcf}(\mathfrak{a})\cap\kappa} is bounded in {\kappa} for every weakly inaccessible {\kappa}.

In his paper [Sh:666], Shelah argues that this conjecture is “a significant dividing line between chaos and order”.


One answer is outlined in [Sh:666]: if the conjecture is true, then for any progressive set of regular cardinals {\mathfrak{a}} we have

\displaystyle  {\rm cf}\left(\prod\mathfrak{\rm pcf}(\mathfrak{a}), <\right)={\rm cf}\left(\prod\mathfrak{a}, <\right), \ \ \ \ \ (1)

while if the conjecture fails one can force a counterexample to the above statement.

The above is really just an outcropping of deeper results from the third section of Chapter VIII of The Book, where Shelah proves that a subset {\mathfrak{b}} of {{\rm pcf}(\mathfrak{a})} which does not have a weakly inaccessible accumulation point still has a nice pcf structure, even though it may be the case that {\mathfrak{b}} is not progressive. In particular, we have {{\rm pcf}(\mathfrak{b})\subseteq{\rm pcf}(\mathfrak{a})} for such a {\mathfrak{b}}. As a corollary, we see that if Shelah’s conjecture is true, then

\displaystyle  {\rm pcf}({\rm pcf}(\mathfrak{a}))={\rm pcf}(\mathfrak{a}) \ \ \ \ \ (2)

for any progressive set of regular cardinals {\mathfrak{a}}.

But Shelah’s Conjecture also has consequences for cardinal arithmetic as well: this is the content of the fourth section of [Sh:430]. I invite the adventurous reader to take a look at that particular piece of Shelah’s oeuvre, because at this point I have no idea what the theorems say. Well, that’s not quite true, as I have a vague idea of what they say, but they are couched in the language of nice filters originating in Chapter V of The Book, and that’s a language I’ve not yet tried to learn. In [Sh:666], he says that if the conjecture holds and {\aleph_\delta} is the {\omega_1}th fixed point (strong limit), then {{\rm pp}(\aleph_\delta)} is less than then {\omega_4}th fixed point. (But I don’t actually see this in [Sh:430] so it’s possible that something was retracted.).

PCF Hypotheses 2

November 28, 2011 at 12:17 | Posted in Uncategorized | Leave a comment

Almost all of the implications listed at the end of the last post follow immediately from the definitions involved. The one exception to this is the result that the Shelah Weak Hypothesis implies {|{\rm pcf}\mathfrak{a}|\leq|\mathfrak{a}|} for any progressive set of regular cardinals {\mathfrak{a}}. It isn’t a difficult result, but it uses “heavy machinery”: the Localization Theorem for pcf.

Suppose {\mathfrak{a}} is a progressive set of regular cardinals satisfying {|\mathfrak{a}|<|{\rm pcf}(\mathfrak{a})|}. Let {\mathfrak{b}} consist of the first {|\mathfrak{a}|^+} elements of {{\rm pcf}(\mathfrak{a})} greater than {|\mathfrak{a}|^+} (so {\mathfrak{b}} is progressive).

If we define

\displaystyle  \lambda:=\sup\{\kappa_\alpha:\alpha<|\mathfrak{a}|^+\} \ \ \ \ \ (1)

then clearly {\lambda} is a singular cardinal of cofinality {|\mathfrak{a}|^+}. Our goal is to obtain a violation of the Shelah Weak Hypothesis by proving

\displaystyle  |\{\mu<\lambda:\mu\text{ singular and }{\rm pp}(\mu)\geq\lambda\}|\geq |\mathfrak{a}|^+ \ \ \ \ \ (2)

We mentioned the localization theorem earlier; we will be content just to quote it without proof:

Theorem 1 (Localization Theorem) Suppose {\mathfrak{a}} is a progressive set of regular cardinals and {\mathfrak{b}\subseteq{\rm pcf}(\mathfrak{a})} does not have a weakly inaccessible point of accumulation. Then for any {\lambda\in{\rm pcf}(\mathfrak{b})} there is a set {\mathfrak{c}\subseteq\mathfrak{b}} of cardinality at most {|\mathfrak{a}|} such that {\lambda\in{\rm pcf}(\mathfrak{c})}.

The above is Theorem 3.4 on page 337 of The Book. Note that the theorem doesn’t require that {\mathfrak{b}} is progressive; it demands only that {\mathfrak{b}\cap\kappa} is bounded in {\kappa} for every weakly inaccessible cardinal {\kappa} (of course, this is overkill for the application we have in mind).

Given {\alpha<\lambda}, note

\displaystyle  \max{\rm pcf}(\mathfrak{b}\cap(\alpha,\lambda))\geq\lambda. \ \ \ \ \ (3)

(This follows immediately upon consideration of the cofinality of {\prod\mathfrak{b}/D} where {D} is any ultrafilter on {\mathfrak{b}} disjoint to the ideal of bounded subsets of {\mathfrak{b}}.)

By the Localization Theorem, it follows that for each {\alpha<\lambda} there is a {\beta} such that {\alpha<\beta<\lambda} and

\displaystyle  \max{\rm pcf}(\mathfrak{b}\cap (\alpha,\beta))\geq\lambda. \ \ \ \ \ (4)

It follows easily that we can find an increasing and continuous sequence {\langle\kappa_\alpha:\alpha<|\mathfrak{a}|^+\rangle} of cardinals such that

  • {\sup\{\kappa_\alpha:\alpha<|\mathfrak{a}|^+\}=\lambda}, and
  • {\max{\rm pcf}(\mathfrak{b}\cap (\kappa_\alpha,\kappa_{\alpha+1}))\geq\lambda} for each {\alpha}.

For {\alpha<|\mathfrak{a}|^+}, let us define

\displaystyle  \mathfrak{b}_\alpha=\mathfrak{b}\cap(\kappa_\alpha,\kappa_{\alpha+1}), \ \ \ \ \ (5)

and let {D_\alpha} be an ultrafilter on {\mathfrak{b}_\alpha} with

\displaystyle  \lambda\leq{\rm tcf}(\prod\mathfrak{b}_\alpha/D_\alpha). \ \ \ \ \ (6)

Now let {\mu_\alpha} be the least cardinal with

\displaystyle  \mathfrak{b}_\alpha\cap \mu_\alpha\notin D_\alpha, \ \ \ \ \ (7)

and an easy argument establishes that {\mu_\alpha} is a singular cardinal satisfying {{\rm pp}(\mu_\alpha)\geq\lambda}. Since {\min(\mathfrak{b}_\alpha)\leq\mu_\alpha\leq\sup(\mathfrak{b}_\alpha)}, it follows that the sequence {\langle \mu_\alpha:\alpha<|\mathfrak{a}|^+\rangle} is strictly increasing, and therefore we have what we need.

List of PCF Hypotheses

November 17, 2011 at 11:09 | Posted in Uncategorized | 2 Comments

This post represents a short detour. I want to take a look at the last section of the paper [Sh:420]: “Advances in Cardinal Arithmetic”. The published version of this paper is a bit hard to track down, but Shelah’s archive contains an approximation.

Anyway, the last section commences with a list of hypotheses:

  1. {{\rm pp}(\lambda)=\lambda^+} for every singular {\lambda}. (The “Shelah Strong Hypothesis” or (SSH).)
  2. If {\mathfrak{a}} is a progressive set of regular cardinals, then {|{\rm pcf}(\mathfrak{a})|\leq|\mathfrak{a}|}.
  3. If {\mathfrak{a}} is a progressive set of regular cardinals, then {{\rm pcf}(\mathfrak{a})} does not have a weakly inaccessible accumulation point.
  4. For every {\lambda}, {\{\mu<\lambda:\mu\text{ singular and }{\rm pp}(\mu)\geq\lambda\}} is countable. (The “Shelah Weak Hypothesis” or (SWH).)
  5. For every {\lambda}, {\{\mu<\lambda:\mu\text{ singular of countable cofinality and }{\rm pp}(\mu)\geq\lambda\}} is countable.
  6. For every {\lambda}, {\{\mu<\lambda:\mu\text{ singular of uncountable cofinality and }{\rm pp}_{\Gamma({\rm cf}\mu)}(\mu)\geq\lambda\}} is finite.

Are the above hypotheses true? Well, the first of these is the only one whose negation is known to be consistent (relative to large cardinals), so potentially any of the others could be a theorem of ZFC.

Edit: See James’s comment for news on (2).

How are they related? Shelah points out the following:

  • (1) implies (2) implies (3)
  • (1) implies (4) implies (5)
  • (1) implies (6)
  • (5) and (6) together imply (4)
  • (4) implies (2)

I think I’d like to take a few posts to map out the proofs of the above, and maybe comment on what I know about the strength of the various hypotheses.


November 15, 2011 at 15:16 | Posted in Uncategorized | Leave a comment

I wanted to use this post as an opportunity to write down some things that I think I know regarding the unresolved questions raised in my last post.

To set the stage, suppose {\aleph_0<\sigma\leq{\rm cf}(\mu)<\theta<\mu} with {\sigma} and {\theta} regular. Let us define the set {{\rm PP}_{\Gamma(\theta,\sigma)}(\mu)} to be of all cardinals {\kappa} such that

\displaystyle  \kappa={\rm tcf}\left(\prod\mathfrak{a}, <_I\right), \ \ \ \ \ (1)


  • {\mathfrak{a}} is a progressive set of regular cardinals cofinal in {\mu},
  • {|\mathfrak{a}|<\theta},
  • {I} is a {\sigma}-complete ideal on {\mathfrak{a}} containing the bounded subsets of {\mathfrak{a}}, and
  • {{\rm tcf}\left(\prod\mathfrak{a}, <_I\right)} exists,

so that

\displaystyle  {\rm pp}_{\Gamma(\theta,\sigma)}(\mu)=\sup{\rm PP}_{\Gamma(\theta,\sigma)}(\mu). \ \ \ \ \ (2)

We are interested in the following:

Suppose {{\rm pp}_{\Gamma(\theta,\sigma)}(\mu)} is a regular cardinal {\kappa}. Is {\kappa\in{\rm PP}_{\Gamma(\theta,\sigma)}(\mu)}?

If the answer to the above question is “NO” for some {\mu}, then I THINK I know the following:

  • There is a cardinal {\lambda} such that {\sigma\leq{\rm cf}(\lambda)<\theta\leq\lambda<\mu} and {\kappa\in{\rm PP}_{\Gamma(\theta,\sigma)}(\lambda)}.
  • There is a cofinal and progressive {\mathfrak{a}\subseteq\mu} with {{\rm pcf}_{\Gamma(\theta,\sigma)}(\mathfrak{a})} unbounded in {\kappa}.
  • There is cofinal and progressive {\mathfrak{b}\subseteq\mu\cap{\sf Reg}} of cardinality {\theta} for which {\prod\mathfrak{b}} modulo the ideal {[\mathfrak{b}]^{<\theta}} has true cofinality at least {\kappa}.

What I want to do over our Christmas break is to work out the details of the above and see if I REALLY know this. The idea is to keep mining pcf theory for more and more structure, with the hope of getting a contradiction eventually. I’ll post my work on the blog as it progresses.


November 14, 2011 at 17:09 | Posted in Uncategorized | Leave a comment

The quarter is ending here, so I should have a little more time for maintaining this blog. I mentioned before that I figured out how to fix the proof of Claim 3.5, which then gives a fairly transparent proof of the cov vs. pp theorem. I need to clarify this a little, because what I’ve got doesn’t recover the full result originally claimed by Shelah. Here’s what I can show:

Theorem 1 Suppose {\mu} is singular, and {\aleph_0<\sigma\leq{\rm cf}(\mu)<\theta<\mu} with {\sigma} and {\theta} regular. Then the following two statements are equivalent for a regular cardinal {\kappa}:

  1. {{\rm pp}_{\Gamma(\theta,\sigma)}(\mu)<\kappa}.
  2. {{\rm cov}(\mu,\mu,\theta,\sigma)<\kappa}.

This is enough to deduce Shelah’s cov vs. pp theorem (Theorem 5.4 of Chapter II in The Book), which states:

Theorem 2 If {\sigma} is a regular uncountable cardinal, and {\sigma<\theta\leq\kappa\leq\lambda}, then

\displaystyle  {\rm cov}(\lambda,\kappa,\theta,\sigma)+\lambda =\sup\{{\rm pp}_{\Gamma(\theta,\sigma)}(\mu): \kappa\leq\mu\leq\lambda\wedge \sigma\leq{\rm cf}(\mu)<\theta\}+\lambda \ \ \ \ \ (1)

Now the issue left unresolved concerns the attainment of suprema in one particular case: if {\mu} is singular and {{\rm pp}_{\Gamma(\theta,\sigma)}(\mu)} is a weakly inaccessible cardinal {\kappa}, must there exist a cofinal subset of {\mu\cap{\sf Reg}} of cardinal less than {\theta} and a {\sigma}-complete ideal {J} on {\mathfrak{a}} containing the bounded subsets of {\mathfrak{a}} such that

\displaystyle  \kappa={\rm tcf}\left(\prod\mathfrak{a}/J\right). \ \ \ \ \ (2)

Said another way, if {{\rm pp}_{\Gamma(\theta,\sigma)}(\mu)} is regular, then must the supremum in the definition of {{\rm pp}_{\Gamma(\theta,\sigma)}(\mu)} be attained?

PS: I’m still very sleep-deprived…it’s all part of being the father of young children.


October 20, 2011 at 12:32 | Posted in Uncategorized | Leave a comment

I’m still trying to figure out if the stuff I’ve gotten is new or not. I was certainly right about there being an error in the proof of Claim 3.5 on page 381 — Shelah points out in [Sh:513] “Pcf and infinite free subsets of an algebra” that the proof is incorrect, and only establishes something much weaker. But I have no idea if he’s rescued the result somewhere else in his collected works. I’ve emailed him; we’ll see what he says.

« Previous PageNext Page »

Create a free website or blog at WordPress.com.
Entries and comments feeds.