[Sh:430.1-4] An easy inequality

January 31, 2011 at 16:38 | Posted in Cardinal Arithmetic, cov vs. pp, [Sh:355], [Sh:430] | 1 Comment

What follows is not really part of the first section of [Sh:430], but it does pin down an important connection between cov and pp. The proposition is a special case of part of Shelah’s “cov vs. pp theorem”, Theorem 5.4 on page 87 of Cardinal Arithmetic. Note that there are no special assumptions on {\mu} here. Getting inequalities in the reverse direction (i.e., showing that covering numbers are less than pp numbers) is generally a more difficult proposition.

Let us recall that {{\rm cov}(\mu,\mu,\kappa^+, 2)} is the minimum cardinality of a set {\mathcal{P}\subseteq[\mu]^{<\mu}} such that for any {A\in [\mu]^\kappa} (equivalently {[\mu]^{\leq\kappa}}), there is a {B\in\mathcal{P}} such that {A\subseteq B}.

Proposition 1 If {\mu} is singular of cofinality {\kappa}, then

\displaystyle  {\rm pp}(\mu)\leq {\rm cov}(\mu,\mu,\kappa^+,2). \ \ \ \ \ (1)

Proof: Suppose by way of contradiction that

\displaystyle  \theta:={\rm cov}(\mu,\mu,\kappa^+,2)<{\rm pp}(\mu). \ \ \ \ \ (2)

By the definition of {\rm pp}, we can find a (not necessarily increasing) sequence of regular cardinals {\langle \mu_i:i<\kappa\rangle} and an ultrafilter {D} on {\kappa} such that

\displaystyle  \{i<\kappa:\mu_i\leq\tau\}\notin D\text{ for each }\tau<\mu, \ \ \ \ \ (3)


\displaystyle  \theta<\sigma:={\rm cf}\left(\prod_{i<\kappa}\mu_i, <_D\right). \ \ \ \ \ (4)

Let {\mathcal{P}\subseteq [\mu]^{<\mu}} be a family of cardinality {\theta} standing as witness to {{\rm cov}(\mu,\mu,\kappa^+,2)=\theta}, and let {\langle f_\alpha:\alpha<\sigma\rangle} be a {<_D}-increasing and cofinal sequence of functions in {\prod_{i<\kappa}\mu_i}. For each {\alpha<\sigma}, the range of {f_\alpha} is a subset of {\mu} of cardinality at most {\kappa}, and so we can find {A_\alpha\in \mathcal{P}} such that

\displaystyle  {\rm ran}(f_\alpha)\subseteq A_\alpha. \ \ \ \ \ (5)

Since {\sigma} is a regular cardinal greater than {\theta}, there is a single {A^*\in \mathcal{P}} such that

\displaystyle  |\{\alpha<\sigma: A_\alpha=A^*\}|=\sigma. \ \ \ \ \ (6)

Thus, (by passing to a subsequence of {\langle f_\alpha:\alpha<\sigma\rangle}) we may as well assume that the range of each {f_\alpha} is a subset of {A^*}.

But {|A^*|<\mu}, and so

\displaystyle  B:= \{i<\kappa:|A^*|<\mu_i\}\in D \ \ \ \ \ (7)

by our choice of {D}. Let us now define a function {g} by setting {g(i)=0} if {i\notin B}, and

\displaystyle  g(i)=\sup(A^*\cap\mu_i) \ \ \ \ \ (8)

whenever {i} is in {B}. Our assumptions imply that {g} is in {\prod_{i<\kappa}\mu_i}.

If {\alpha<\sigma}, then for each {i\in B} we have

\displaystyle  f_\alpha(i)\leq g(i) \ \ \ \ \ (9)

as {f_\alpha(i)\in A^*\cap\mu_i}.

It follows that {g} is a function in {\prod_{i<\kappa}\mu_i} such that{f_\alpha\leq_D g} for all {\alpha<\sigma}. This is absurd, given our choice of {\langle f_\alpha:\alpha<\sigma\rangle}, and the proof is complete. \Box

[Updated 2-7-11]

[Sh:430.1-3] Elementary Submodel Conventions

January 27, 2011 at 18:39 | Posted in Uncategorized | Leave a comment

We’re going to be working with elementary submodels a lot, so I wanted to pin down the assumptions we make and the notation we use.

In the current project, we are investing combinatorics relevant to a singular cardinal {\mu}, and {\chi} is a regular cardinal “much much larger” than {\mu}. The exact identity of {\chi} isn’t important. We also need to fix some well-ordering {<_\chi} of {H(\chi)}; we will build this into the structures we consider so that they all have definable Skolem functions.

In general, {\mathfrak{A}} denotes some expansion of {\langle H(\chi),\in, <_\chi\rangle} by at most countably many functions, constants, and relations. I won’t get too pedantic with this, but for example, in the current situation we want {\mathfrak{A}} to contain a name for {\mu}, so that we know {\mu} makes it into any elementary submodel of {\mathfrak{A}}. We won’t make this explicit in our notation.

I will use {{\rm Sk}_{\mathfrak{A}}(B)} (or just {{\rm Sk}(B)}) to denote the Skolem hull of {B} in the structure {\mathfrak{A}}.

I may update this post to reflect new things that I forgot to include…

[Sh:430.1-2] Framework for proof

January 26, 2011 at 18:46 | Posted in Cardinal Arithmetic, [Sh:430] | Leave a comment

Let us assume that {\mu} is a singular cardinal with {\rm{pp}(\mu)=\mu^+}. We will prove that there is a family {\mathcal{P}\subseteq [\mu]^{<\mu}} of cardinality {\mu^+} such that every member of {[\mu]^{\rm{cf}(\mu)}} is a subset of some member of {\mathcal{P}}.

Fix a sufficiently large regular cardinal {\chi}; we will be working with elementary submodels of the structure {\langle H(\chi),\in, <_\chi\rangle} where {<_\chi} is some appropriate well-ordering of {H(\chi)} used to give us definable Skolem functions.

Let {\mathfrak{M}=\langle M_\alpha:\alpha<\mu^+\rangle} be a {\mu^+}-approximating sequence, that is, {\mathfrak{M}} is a {\in}-increasing and continuous sequence of elementary submodels of {H(\chi)} such that for each {\alpha<\mu^+},

  • {\mu\in M_0},
  • {M_\alpha} has cardinality {\mu},
  • {M_\alpha\cap\mu^+} is an initial segment of {\mu^+} (so {\mu+1\subseteq M_\alpha\cap\mu^+}), and
  • {\langle M_\beta:\beta<\alpha\rangle\in M_{\alpha+1}}.

Let {M^*} denote {\bigcup_{\alpha<\mu^+} M_\alpha}. Then {M^*} is an elementary submodel of {H(\chi)} of cardinality {\mu^+} containing {\mu^+} as both an element and subset. Define

\displaystyle  \mathcal{P}=M^*\cap [\mu]^{<\mu}. \ \ \ \ \ (1)

Clearly {\mathcal{P}\subseteq [\mu]^{<\mu}} and {|\mathcal{P}|=\mu^+}, so we need only verify that for any {a\in [\mu]^{\rm{cf}(\mu)}}, there is a {b\in \mathcal{P}} with {a\subseteq b}.

In broad terms, this will be done via an “{I[\lambda]} argument” with {\lambda=\mu^+}, but we’ll fill in the details in further posts.

[Sh:430.1-1] What are we aiming for?

January 24, 2011 at 21:38 | Posted in Cardinal Arithmetic, [Sh:430] | Leave a comment

We focus our attention on the first section of [Sh:430]: “equivalence of two covering properties”. The first result states the following:

Theorem 1 If {\rm{pp}(\lambda)=\lambda^+}, {\lambda>\rm{cf}(\lambda)=\kappa>\aleph_0} then {\rm{cov}(\lambda,\lambda,\kappa^+,2)=\lambda^+}.

I am pretty sure that this isn’t what Shelah meant to write here — the assumption that {\lambda} has uncountable cofinality means that the result is a trivial consequence of a deeper theorem in Cardinal Arithmetic [Update: Perhaps not! See 2nd update below]. I think that the proof he gives works even for the countable cofinality case, and this gives us something of interest because {\lambda} could very well be a fixed point. So, here’s what I conjecture he meant to say (after changing notation and translating the “cov” statement into more standard form):

Theorem 2 Let {\mu} be a singular cardinal. Then {\rm{pp}(\mu)=\mu^+} if and only if there is a family {\mathcal{P}\subseteq [\mu]^{<\mu}} of cardinality {\mu^+} such that every member of {[\mu]^{\rm{cf}(\mu)}} is a subset of some element of {\mathcal{P}}.

We’ll work through his proof as best we can, and see if my conjecture is correct.

UPDATE 1: I don’t think the conjecture is correct. It looks to me like the proof was originally written for singular of countable cofinality, but a mistake was discovered and the statement was corrected but a lot of the old proof didn’t get revised properly. The annotated content was revised, but the abstract was not. Anyway, I’ll ask Saharon if I can’t figure out what’s going on.

UPDATE 2: I think the theorem doesn’t follow from the Cardinal Arithmetic stuff. The problem I run into is that when Shelah says informally that “cov = pp when the cardinal has uncountable cofinality”, there are lots of disclaimers hidden in the background. But this underscores why I think what I’m doing here is important — I want to pin down what exactly is known and what exactly is still open in this area.

Current Project: [Sh:430] Section 1

January 24, 2011 at 21:19 | Posted in Cardinal Arithmetic, [Sh:430] | Leave a comment

So, I’ve decided what I want to try to accomplish with this blog: I want to use it as a tool for developing a reasonable exposition of more advanced pcf material. I consider this an experiment, as I have no idea how effective this will be, and it is entirely possible that I decide the entire endeavour is silly.

My first project will be to develop a treatment of the first section of [Sh:430] “Further Cardinal Arithmetic”; my intermediate goal is to concentrate on resuts related to the “cov vs. pp” problem.

It is safe to say that most of what I will be doing is presenting results of Shelah; if something is unattributed then consider it a result of Shelah (although I tend to try and reformulate things to make them more understandable to myself).

SCH above a compact cardinal

January 20, 2011 at 20:41 | Posted in Uncategorized | 1 Comment
Tags: ,

This is really just an experiment to see if I can actually get latex2wp to work for me, but maybe it has mathematical interest as well. Anyway, it is well-known that Shelah’s pcf theory can be used to give a proof of Solovay’s result that the Singular Cardinals Hypothesis holds above a compact cardinal. What follows is a fairly short proof of a more general result; the argument consists of chaining together some ideas of Shelah taken from his Cardinal Arithmetic.
See “proof of 3.3 in Case gamma” and Remark 3.3B on pages 150-151 of his book.

Theorem 1 Suppose {\mu} is singular of countable cofinality and {\rm{pp}(\mu)>\mu^+}. Then there is no uniform countably complete ultrafilter on {\mu^+}.

Proof: We actually show more: we prove that there is no weakly {\mu^+}-saturated uniform countably complete filter on {\mu^+}. Said another way, if {F} is a uniform countably complete filter on {\mu^+} for {\mu} singular of countable cofinality and {\text{pp}(\mu)>\mu^+}, then we can find {\mu^+} disjoint {F}-positive subsets of {\mu^+}. In particular, {F} cannot be an ultrafilter.

To understand the proof, we don’t really need to know what {\text{pp}(\mu)>\mu^+} means. What we really need is one of the combinatorial consequences of this statement, namely that there is a family {\langle A_\alpha:\alpha<\mu^+\rangle} of countable subsets of {\mu} (not {\mu^+}!) such that for every {\beta<\alpha}, the collection {\langle A_\beta:\beta<\alpha\rangle} is essentially disjoint, in the sense that there is a function {F_\alpha} with domain {\alpha} such that

  • {F_\alpha(\beta)} is a finite subset of {A_\beta}, and
  • the collection {\langle A_\beta\setminus F_\alpha(\beta):\beta<\alpha\rangle} is pairwise disjoint.

Thus, for each {\alpha<\mu^+} the collection {\langle A_\beta:\beta<\alpha\rangle} can be “disjointified” by removing a finite subset from each {A_\beta}.

Note that since the {A_\alpha} are subsets of {\mu}, no {\mu^+}-sized subcollection of {\langle A_\alpha:\alpha<\mu^+\rangle} can be disjointified, as this would give us {\mu^+} disjoint subsets of {\mu}. One should think of {\langle A_\alpha:\alpha<\mu^+\rangle} as a failure of “compactness” at {\mu^+} which necessarily arises from the failure of the singular cardinals hypothesis at {\mu}.

Let us assume now that {\langle A_\alpha:\alpha<\mu^+\rangle} is as above, and {F} is a uniform countably complete filter on our cardinal {\mu^+}; we will show {\mu^+} contains {\mu^+} disjoint {F}-positive subsets. Let us also assume that we have fixed some way of enumerating each {A_\alpha}, so that expressions such as “the first 5 elements of {A_\alpha}” make sense.

Given {\beta<\mu^+} and {n<\omega}, define {X^\beta(n)} to be those {\alpha<\mu^+} greater than {\beta} for which {F_\alpha(\beta)} is contained in the first {n} elements of {A_\beta}. For each {\beta}, the sequence {\langle X^\beta(n):n<\omega\rangle} is increasing with union {(\beta,\mu^+)}. Since {F} is uniform and countably complete, it follows that there is an {n_\beta<\omega} such that {X^\beta(n_\beta)} is {F}-positive.

For each {\beta<\mu^+}, let {x_\beta} be the “{n_\beta+1}th element” of {A_\beta}. Then clearly the set

\displaystyle  Y_\beta:=\{\alpha<\mu^+:\beta<\alpha\text{ and }x_\beta\in A_\beta\setminus F_\alpha(\beta)\} \ \ \ \ \ (1)

is {F}-positive for each {\beta}, as includes {X^\beta(n_\beta)}.

We know {x_\beta<\mu} for each {\beta}, and so there exists an {x^*<\mu} such that

\displaystyle  |\{\beta<\mu^+:x_\beta=x^*\}|=\mu^+. \ \ \ \ \ (2)

Given {x^*}, we define

\displaystyle  Z:=\{\beta<\mu^+:x_\beta=x^*\}. \ \ \ \ \ (3)

We are now done, as given {\alpha<\beta} in {Z}, we see that {Y_\alpha\cap Y_\beta=\emptyset}, and therefore the collection {\{Y_\alpha:\alpha\in A\}} is a collection of {\mu^+} disjoint {F}-positive subsets of {\mu^+}. \Box

Corollary 2 If {\kappa<\mu} where {\kappa} is strongly compact and {\mu} is a singular cardinal of countable cofinality, then {\text{pp}(\mu)=\mu^+}.

Proof: The co-bounded filter on {\mu^+} is a uniform {\mu^+}-complete filter. Since {\kappa} is strongly compact, this filter can be extended to a {\kappa}-complete ultrafilter (necessarily uniform) on {\mu^+}. The conclusion now follows immediately from the theorem. \Box

Corollary 3 If {\kappa} is strongly compact, then the Singular Cardinals Hypothesis holds above {\kappa}.

Blog at WordPress.com.
Entries and comments feeds.