I’ll be doing a lot of traveling over the next two weeks; I’ll pick up with things when I’m back from Barcelona.
This post is a bit of a detour, but I wanted to point out that Conclusion 3.2A is really just Claim 3.2 grafted onto a nice characterization of . Shelah implicitly uses this characterization in his proof of Conclusion 3.2A, but I can’t find a formulation of it anywhere in The Book.
Theorem 1 Let be a singular cardinal. Then the following three cardinals are equal:
Notice that in 2 and 3, the suprema involved can only decrease as increases, and this tells us a couple of things. First, the cardinals in 2 and 3 are easily seen to be equal, as without loss of generality , hence the collection of relevant sets is exactly the same in each case, and we finish using the equality
for progressive .
Second, we know that as approaches , the suprema involve eventually stabilize and hence the minimum value is actually attained by some . What the theorem shows is that this stable value is exactly . Notice as well that although is computed using sets cofinal in , we do not assume this for the involved in 2 and 3.
We turn now to the proof:
Proof: We have already noted that 2 and 3 are equal for easy reasons. The fact that 1 is less than or equal to 2 is also trivial from the definition of :
Suppose . Then there is a progressive , a cardinal , and an ultrafilter on such that
- is disjoint to the bounded ideal on ,
- , and
Given , we know as , hence
for each and the desired inequality follows immediately.
What about the other inequality? This is exactly Lemma 1 from our June 17, 2011 post, which was written with this application in mind.
So we fix can fix large enough so that
- is progressive,
- , and
where for the last statement we use the result of the previous posting.
We will get what we need by comparing the last two bullet points:
Suppose . This means that we there is an ultrafilter and a set of cardinality such that
- , and
Clearly we may assume that has cardinality exactly , and the second bullet implies
as well, where we view as an ultrafilter on . Chaining things together, we have
So for our choice of , we have
This post is an immediate continuation of the previous one, so all notation etc. carries over from there. I noticed last night that Conclusion 3.2A is really two separate results which have been smashed together. The main part actually looks like it holds without the assumption that is not a fixed point, so I’m going to work in a slightly more general context today. If things work out, I’ll formulate “the real theorem” underlying things.
Lemma 1 Let be a singular cardinal of cofinality . Then there is a such that
Proof: First, note that if we restrict ourselves to with , then any relevant to computing the left-hand side of the above equation is necessarily progressive, and hence the cofinality of will just be . Thus, we need only prove that there is a in the interval for which
Suppose this is not the case, so for any there is a of cardinality with . The following proposition takes this hypothesis and moves us closer to a contradiction:
Proposition 2 Under the above assumptions, for every there is a such that
- is a progressive subset of ,
- , and
- is a bounded subset of .
Proof: Without loss of generality, we assume and so we can find (progressive) of cardinality such that . If is bounded below then we are done, so assume is unbounded.
Let be an ultrafilter on such that
The above equation, taken together with the fact that is unbounded in of cardinality , tells us (by way of the definition of ) that cannot be disjoint to the bounded subsets of , i.e,. that there is a such that
Now this has all of the required properties.
Armed with the above proposition, we can construct sequences and such that
- is a strictly increasing sequence of cardinals cofinal in
- (hence is progressive)
- for each .
Let , and consider the ideal on generated by and the bounded subsets of . It is easy to show that must be a proper ideal on : if not, then there would be a such that
but this is impossible as
by our construction of . If is an ultrafilter on disjoint to , then
and we have a contradiction of (6).
Recall from the last post that I’ve committed myself to providing a proof of the following:
We’ve already discussed what the notation means, so I’m going to plunge right in. I’ll probably split this up into a few posts; the result is true, but the proof given in The Book has the unfortunate property that at a key moment, the reader is given an incorrect reference as explanation, and it might take me a post or two to fill in the necessary details.
Proof: We’ll start with the easy stuff and prove first the inequality
whenever is such that is progressive.
Let be given (such exist because — see posts of June 15), and define
By Claim 3.2 (June 15, 2011), we know
To establish our inequality, we must show
This is actually quite easy. Let us define an ideal on by
Set , and note
- (as ), and
- (as contains the set ).
Thus, to finish this part of the proof we need only check
but this follows easily from (5).
I’ll end this post here, and pick up with establishing the other inequality (and the “” part) tomorrow.
In this post, we want to look at the next result in The Book: Conclusion 3.2A on page 378. What I will do is state this exactly as it appears in the book, and then reformulate it in conjunction with providing some commentary. I’ll attempt to prove it in a future post.
Theorem 1 (Conclusion 3.2A page 378) If , a limit ordinal, then:
- for large enough,
- if then for large enough
I’m going to concentrate on the first part of the above; here’s my attempt at reformulating it.
refers to the minimum cardinality of a family with the property that for any of cardinality , the collection
is cofinal in .
This definition is robust under small modifications: it is also the minimum cardinality of a family with the property that for any of cardinality at most and any , there is a finite set such that
In other words,
and we are back with the sorts of cardinals we’ve been considering of late.
There is something else implicit in this theorem that I want to bring out: it shows us that if is a singular cardinal that isn’t a fixed point, then can be calculated just by looking at structure
In this situation is the minimum cardinality of a family of functions in with the property that for some , for any of cardinality the family
is cofinal in . Roughly speaking, if is singular and not a fixed point, then is the minimum cardinality of a family of functions in which can cover all products of size drawn from some fixed tail of . That seems like it is worth knowing…
This is a silly post, but looking ahead to Conclusion 3.2A reminded me of one of the frustrations I had when first trying to read The Book. One of the major themes of pcf theory is that it tells us quite a lot about cardinal arithmetic at singular cardinals that are not fixed points of the function. The problem is that this is equivalent to lots of other conditions, and very often Shelah will use a different formulation of this property in the statement of a theorem, so it isn’t clear right away that what he’s really talking about is a cardinal that isn’t a fixed point. This little proposition is just an elementary exercise in set theory, but it’s useful to keep in mind when reading The Book. (And let’s hope I haven’t flubbed it since I’m typing from home while babysitting…)
Proposition 1 Let be a singular cardinal. Then the following are equivalent:
- is not a fixed point, i.e., .
- where is a limit ordinal .
- There is a such that is progressive.
Proof: Suppose , and fix such that . Since is a limit cardinal, we know , so choose such that
Now fix such that
It is clear that must be a limit (as is), and the fact that
is completely trivial. For the last bit, we know
and we are done with proving that (1) implies (2)
Now assume (2) holds, set , and define
and we have (3).
Moving on to the last implication, let us suppose and is progressive, i.e., . But then as well, and hence
Thus, we have
Last time, we left off with the statement of the following theorem:
Theorem 1 Suppose is a progressive set of regular cardinals, and
The above is just Claim 3.2 on page 377 of The Book with the notation changed a little. Today I want to give a proof of this theorem. If you’ve already read through our June 10th post, then today will be simple because it’s essentially the same proof.
Proof: Start by letting be -cofinal in for any of cardinality , and suppose . We will show that , thereby establishing the “” part of the theorem.
Assume by way of contradiction that . Let and witness that is in , i.e.,
- is a -complete ideal on ,
- has true cofinality ,
- , and
Since , there is a function such that
Given , we define
Then (4) tells us
A couple of things now come to our rescue: since and is -complete, there must be an such that is not in , and this tells us
This is absurd, of course, for was an upper bound of in . Thus, and the “” part of the theorem has been established.
For the other direction, we once again mirror our June 10th post. Given , let and be the associated ideal and generating set. Basic pcf theory tells us
and we let serve to witness this.
Clearly , so we will be done if we can show is -cofinal in for every of cardinality .
Suppose this is not the case. Then we can find a set of cardinality and a function such that the restriction of to cannot be covered by fewer than functions in .
Let us now define a collection of subsets of by putting into if and only if there is a family of cardinality such that
It’s easy to check that is an ideal, and for trivial reasons. Our choice of guarantees that is a -complete proper ideal as well.
Now let be minimal with , and define
The ideal is essentially restricted to ; it is easy to see that is a proper (by choice of ) -complete (as is) ideal on . Clearly as well, since this set is in .
The minimality of ensures
which immediately implies
Thus, the functions witness
Putting all of the above together, we see
by way of our ideal .
Our goal now is to reach a contradiction exactly as in the June 10th post by demonstrating that , and .
Part of this is trivial, as was selected so that . For the other part, we know that given our choice of , there is an such that
Having set the mood with our last post, we now return to “The Book” and examine “covering all small products”. I want to use this post to try out some terminology to see if it’s possible to make the material a little more palatable.
Definition 1 Let be a set of regular cardinals, let be a regular cardinal, and let . Given a set , we say that is -cofinal in if for any function , there is a family of fewer than elements of such that
In the last post, we characterized the minimum cardinality of a -cofinal subset of in the case where is progressive and . Today, I want to consider a related question:
What is the minimum cardinality of a family such that is -cofinal in for every of cardinality ?
Let us agree to denote the above cardinal by (again, don’t blame me for the notation!).
Ok, so why on earth would I want to consider such a cardinal? Well, we’re going to see that this is actually quite relevant for cardinal arithmetic — we will show that such cardinals are intimately tied up with Shelah’s covering numbers. Our first task, though, will be to characterize such cardinals in terms of pcf theory. The characterization will require a little terminology.
Definition 2 Suppose is a progressive set of regular cardinals, and let and be cardinals such that
We define the set to consist of all (regular) cardinals for which there is an ideal on such that
- is -complete,
- has true cofinality , and
- there is a such that and .
Notice that the above is very close to the definition of ; the difference is that the last clause further restricts the acceptable ideals to those which also “reduce” to something of the form where .
We’ll end this post with the statement of a theorem; we’ll prove the theorem in the next post.
Theorem 3 Suppose is a progressive set of regular cardinals, and
This post should be considered a warmup. To start, I want to recall one of the standard results of pcf theory, namely that if is a progressive set of regular cardinal, then
where the ordering on is given by
which means that there is a -increasing -sequence of functions in cofinal in . In other words, (3) means that has cofinality , AND every subset of of cardinality less than has an upper bound in .
The characterization we give involves the following notion:
Definition 1 Let be a regular cardinal, and suppose is a set of regular cardinals. We say that a family is -cofinal in if for every , there is a family of size less than such that , i.e., such that
for all . The -cofinality of is defined to be the minimum cardinality of a -cofinal subset of . We will denote this cardinal by .
So now we come to the promised characterization:
Theorem 2 If is a progressive set of regular cardinals, and is a regular cardinal with , then
and assume by way of contradiction that . Given this, (15) implies that is bounded modulo in , so there is a with
We have assumed, however, that is -cofinal in , so we can fix and with
Given , define
By our choice of , we have
Since is -complete and , there is a with . But this is a contradiction as was an upper bound for in . Thus, and the inequality “” has been established.
For the other direction, we are going to need a little pcf theory. In general, for each we have an associated ideal and generator , and
This entails the existence of a sequence of functions witnessing the true cofinality of the partial order, and we let denote the collection .
Let us define
Clearly . We claim that is -cofinal in .
Suppose this is not the case. Then there is a function that cannot be covered by fewer than functions from . We define an collection of subsets of by putting into if and only if there is a family of cardinality such that
It is easy to check that is a -complete ideal on , and this ideal is proper because of our choice of .
Let be minimal with , and define
Thus, the functions show us
We begin to close in on a contradiction. We know that is a proper ideal on and therefore (we’ll drop the “”) from now on) is not in ; we will finish the proof by demonstrating that in fact MUST be in .
Given the definition of , we know there is an for which
Said another way,
where the last inclusion is from (15).
But since , we know
as well, by the very definition of .
Thus, is the union of two sets in , hence an element of . Contradiction.