Thursday, June 13, 2013

Around Observation 5.5

$\DeclareMathOperator{\pp}{pp} \def\pcf{\rm{pcf}} \DeclareMathOperator{\cov}{cov} \def\cf{\rm{cf}} \def\REG{\sf {REG}} \def\restr{\upharpoonright} \def\bd{\rm{bd}} \def\subs{\subseteq} \def\cof{\rm{cof}} \def\ran{\rm{ran}} \DeclareMathOperator{\PP}{pp} \DeclareMathOperator{\Sk}{Sk}$

I apologize for the lack of context for this post, but I'm just trying to get some ideas down.

Proposition: Assume $\cf(\lambda)<\theta=\cf(\theta)<\lambda$.    Then

$(1)\quad\quad \pp(\lambda)=\pp_\theta(\lambda)\Longrightarrow\cov(\pp(\lambda),\lambda,\theta^+,\theta)=\pp(\lambda).$

Proof:   We know $\lambda<\pp(\lambda)$ so $\lambda<\cov(\pp(\lambda),\lambda,\theta^+,\theta)$. Thus, by the cov vs. pp theorem (Theorem 5.4 on page 87 of The Book) it suffices to prove the following:

If $\lambda\leq\mu\leq\pp(\lambda)$ and $\cf(\mu)=\theta$, then $\pp_{\Gamma(\theta)}(\mu)\leq\pp(\lambda)$.

Clearly for such a $\mu$ we have $\pp_{\Gamma(\theta)}(\mu)\leq\pp(\mu)$, so we must show

$(2)\quad\quad \lambda\leq\mu\leq\pp(\lambda)\wedge\cf(\mu)=\theta\Longrightarrow\pp(\mu)\leq\pp(\lambda)$

But  we know the following:

• $\pp(\mu)=\pp_\theta(\mu)$ by definition.
• $\pp(\lambda)=\pp_\theta(\lambda)$ by assumption, and
• $\pp_\theta(\mu)\leq\pp_\theta(\lambda)$ by "inverse monotonicity" of $\pp_\theta$  (Conclusion 2.3(2) on page 57 of The Book)
Putting all these together gives us what we need.   Q.E.D.

As far as I know, it is still unknown if the hypothesis of the preceding proposition can fail.  We do know the following:

• If $\lambda$ is a strong limit and $\cf(\lambda)\leq\theta=\cf(\theta)<\lambda$, then $\pp(\lambda)=\pp_\theta(\lambda)$.
• Actually, instead of assuming $\lambda$ is a strong limit, it suffices to assume that $\pp_\theta(\mu)<\lambda$ for all sufficiently large $\mu<\lambda$ with $\cf(\mu)\leq\theta$.  This is part of Corollary 1.6 on page 321.
• We could also assume $\pp(\lambda)<\lambda^{+(\cf(\lambda))^+}$ and obtain the same conclusion.
What is the point?  In the first place, the argument given above allows us to deduce Observation 5.5 on page 404.  In the second place...well, I'll write the next piece out tomorrow.

Wednesday, June 12, 2013

Final Inequality Finale

$\DeclareMathOperator{\pp}{pp} \def\pcf{\rm{pcf}} \DeclareMathOperator{\cov}{cov} \def\cf{\rm{cf}} \def\REG{\sf {REG}} \def\restr{\upharpoonright} \def\bd{\rm{bd}} \def\subs{\subseteq} \def\cof{\rm{cof}} \def\ran{\rm{ran}} \DeclareMathOperator{\PP}{pp} \DeclareMathOperator{\Sk}{Sk}$

Continuing our last post, we need to prove that $X$ is a subset of $M\cap\lambda$.  Let

$N:=N_{\sup(I)}.$

Note that $X\subseteq N\cap\lambda$, so it suffices to prove the following:

$N\cap\lambda\subseteq M.$

Suppose by way of contradiction that this fails,  and define

$(1)\quad\quad \gamma(*)=\min(N\cap\lambda\setminus M).$

Since $\mu+1\subseteq M$, we know

$(2)\quad\quad\mu<\gamma(*)<\lambda.$

Next, define
$(3)\quad\quad\beta(*)=\min(M\cap N\setminus\gamma(*)).$

Claim 1: $\beta(*)<\lambda$

Proof:  Clearly $\lambda$ and $\cf(\lambda)$ are elements of $M\cap N$.  Since $\cf(\lambda)<\mu$, we know $\cf(\lambda)+1\subseteq M$.  Since $\cf(\lambda)<\theta$  and $N\cap\theta$ is an initial segment of $\theta$, it follows that $\cf(\lambda)+1\subseteq N$ as well.  From this we deduce that $M\cap N$ contains a cofinal subset of $\lambda$, and hence $\beta(*)<\lambda$.   Q.E.D.

Putting things together, we have

$(4)\quad\quad\mu<\gamma(*)<\beta(*)<\lambda,$

and by definition of $\beta(*)$,

$(5)\quad\quad M\cap N\cap [\gamma(*),\beta(*))=\emptyset.$

We now analyze what sort of ordinal $\beta(*)$ might be.  In the first place, $\beta(*)$ must be a limit ordinal,  because otherwise its predecessor would violate (5).

Claim 2: $\beta(*)$ is a regular cardinal

Proof:  Suppose not, and let $\kappa(*)=\cf(\beta(*))$.  Since $\kappa(*)\in M\cap N$, it must be the case that

$(6)\quad\quad \kappa(*)<\gamma(*)<\beta(*).$

Let $f\in M\cap N$ be a strictly increasing map from $\kappa(*)$ onto a cofinal subset of $\beta(*)$, and let $\gamma<\kappa(*)$ be the least ordinal with  $\gamma(*)<f(\gamma)$.

We know $\gamma\in N$ (it is definable once we have $\gamma(*)$ available) but $\gamma$ cannot be an element of $M$ as otherwise we contradict (5).  This means that $\kappa(*)$ must be larger than $\mu$ as $N\cap\mu\subseteq M$.

Certainly $\kappa(*)$ is regular, so $\kappa(*)$ is a regular cardinal in $N\cap (\mu,\lambda)$.  Given our definition of $N$, we can find $i\in I$ such that $f$, $\gamma$, and $\kappa(*)$ are all in $N_i$.

Let $\mathfrak{a}=N_i\cap\lambda\cap\REG$.  We chose $\alpha_i$ and $\mu_i$ so that

$\kappa\in\mathfrak{a}\setminus\mu_i+1\Longrightarrow \sup(N_i\cap\kappa)<f_{\alpha_i}(\kappa).$

Since $i\in I$, it follows that $\mu_i\leq\mu$ and therefore

$(7)\quad\quad \gamma\leq\sup(N_i\cap\kappa(*))<f_{\alpha_i}(\kappa(*))<\kappa(*).$

Let $\delta(*)=f(f_{\alpha_i}(\kappa(*))$.  Since $f$ is strictly increasing, we know

$(8)\quad\quad \gamma(*)\leq f(\gamma)<\delta(*)<\beta(*).$

The ordinal $\delta(*)$ is in $N$ because everything needed to define it is available in $N_{i+1}$. However, since $i\in I$ it follows that the ordinal $\alpha_i$ is in $B$ and hence $f_{\alpha_i}\in M$.  Since $f$ and $\kappa(*)$ are also in $M$, we find $\delta(*)\in M$ as well.  But now we have contradicted (5).  Q.E.D.

Claim 3: $\beta(*)$ cannot be a regular cardinal

Proof:  This is almost the same argument as above.   Fix $i\in I$ with $\gamma(*)\in N_i$.  Then arguing as above we find

$(9)\quad\quad \gamma<\sup(N_i\cap\beta(*))<f_{\alpha_i}(\beta(*))<\beta(*)$

and   $f_{\alpha_i}(\beta(*))$ contradicts (5). Q.E.D.

Clearly Claim 2 and Claim 3 provide the needed contradiction and we have established what we need.

Final Inequality 2

$\DeclareMathOperator{\pp}{pp} \def\pcf{\rm{pcf}} \DeclareMathOperator{\cov}{cov} \def\cf{\rm{cf}} \def\REG{\sf {REG}} \def\restr{\upharpoonright} \def\bd{\rm{bd}} \def\subs{\subseteq} \def\cof{\rm{cof}} \def\ran{\rm{ran}} \DeclareMathOperator{\PP}{pp} \DeclareMathOperator{\Sk}{Sk}$

Picking up right where we left off, suppose $X\in [\lambda]^{<\theta}$.  We will find an acceptable model $M$ with $X\subseteq M\cap\lambda$.

Start by fixing a continuous increasing $\in$-chain  $\langle N_i:i<\theta\rangle$  of elementary submodels of $\mathfrak{A}$ satisfying:

• $\langle N_j:j\leq i\rangle\in N_{i+1}$,
• $|N_i|<\theta$
• $N_i\cap\theta$ is an initial segment of $\theta$
• $\{X,p\}\in N_0$

This is certainly possible as $\theta$ is a regular cardinal.   Note that our requirement that $N_i\cap\theta$ is an initial segment of $\theta$ has a lot of power:  for example, it implies that $X\subseteq N_0$, and that $N_j\subseteq N_i$ whenever $j<i<\theta$.

Given $i<\theta$, let us consider $\mathfrak{a}:= N_i\cap\lambda\cap\REG$.  We know the following facts:
• $|\mathfrak{a}|=|N_i|<\theta$, and
• $\mathfrak{a}$ is cofinal in $\lambda$ (as $\cf(\lambda)<\theta$).
This means that $\prod\mathfrak{a}$ is "covered" by our family $\mathcal{F}$:  if $g\in\prod\mathfrak{a}$ then there is an $f\in\mathcal{F}$ and $\mu<\lambda$ such that $g(\kappa)<f(\kappa)$ whenever $\kappa\in\mathfrak{a}\cap (\mu,\lambda)$.

We apply the observation in the previous paragraph to the characteristic function of $N_i$ on $\mathfrak{a}$. This gives us an ordinals $\alpha_i<\lambda(1)$ and $\mu_i<\lambda$ such that
$$\kappa\in\mathfrak{a}\cap (\mu_i,\lambda)\Longrightarrow \sup(N_i\cap \kappa)<f_{\alpha_i}(\kappa).$$
Moreover, we can choose $\alpha_i$ and $\mu_i$ in $N_{i+1}$, as the above argument can be done in the model $N_{i+1}$.  This is important, because it guarantees that the function $i\mapsto\alpha_i$ is one-to-one.

Since $\cf(\lambda)<\theta=\cf(\theta)<\lambda$, there is a $\mu<\lambda$ such that
$$|\{i<\theta:\mu_i\leq\mu\}|=\theta.$$
Fix such a $\mu$ (without loss of generality greater than $\cf(\lambda)$), and define
$$I^*:=\{i<\theta:\mu_i\leq\mu\}$$.

Now look at the set $A^*=\{\alpha_i:i\in I^*\}$.   This set is in $[\lambda(1)]^\theta$ because we made sure that the function $i\mapsto\alpha_i$ is one-to-one.  By the definition of $\mathcal{P}$, there is a set $B^*\in\mathcal{P}$ such that $A^*\cap B^*$ is infinite.

Let $\alpha$ be the supremum of the first $\omega$ elements of $A^*\cap B^*$, and find $I\subseteq I^*$
of order-type $\omega$ so that

• $\{\alpha_i:i\in I\}$ is strictly increasing,
• each $\alpha_i$ is in $A^*\cap B^*$, and
• $\sup\{\alpha_i:i\in I\}=\alpha$
Now let $B=B^*\cap \alpha$, and define

$M=\Sk_\mathfrak{A}(B\cup p\cup\mu+1)$

Clearly $M$ is an acceptable model, so we need to prove that $X\subseteq M$.

To be continued...

Tuesday, June 11, 2013

Final Inequality 1

$\DeclareMathOperator{\pp}{pp} \def\pcf{\rm{pcf}} \DeclareMathOperator{\cov}{cov} \def\cf{\rm{cf}} \def\REG{\sf {REG}} \def\restr{\upharpoonright} \def\bd{\rm{bd}} \def\subs{\subseteq} \def\cof{\rm{cof}} \def\ran{\rm{ran}} \DeclareMathOperator{\PP}{pp} \DeclareMathOperator{\Sk}{Sk}$

Recall
• $\cf(\lambda)<\theta=\cf(\theta)<\lambda$,
• $\lambda(1):=\cf_{<\theta}(\prod(\lambda\cap\REG), <_{J^\bd_\lambda})$, and
• $\lambda(2)$ is the minimum cardinality of a family $\mathcal{P}\subseteq[\lambda(1)]^{<\lambda}$ such that for any $B\in[\lambda(1)]^\theta$ there is an $A\in\mathcal{P}$ with $A\cap B$ infinite.

We wish to prove $\cov(\lambda,\lambda,\theta,2)\leq\lambda(2)$.  This requires us to produce a family
$\mathcal{P}^*\subseteq[\lambda]^{<\lambda}$ such that
• $|\mathcal{P}^*|\leq\lambda(2)$, and
• for any $B\in [\lambda]^{<\theta}$ there is an $A\in\mathcal{P}^*$ with $B\subseteq A$.
We start by fixing a family $\mathcal{F}\subseteq \prod(\lambda\cap\REG)$ witnessing the definition of $\lambda(1)$, say $\mathcal{F}=\{f_\alpha:\alpha<\lambda(1)\},$ and let $\mathcal{P}\subseteq[\lambda]^{<\lambda}$ be as in the definition of $\lambda(2)$.

To find $\mathcal{P}^*$, let us assume $\chi$ is a regular cardinal much larger than any of the cardinals considered above, and let (as usual) $\mathfrak{A}$ denote the structure $\langle H(\chi),\in, <_\chi)$,where $<_\chi$ is some well-ordering of $H(\chi)$.  We will use $\Sk_\mathfrak{A}(B)$ to denote the Skolem hull of $B$ in the structure $\mathfrak{A}$.

Let us say that an elementary submodel $M$ of $\mathfrak{A}$ is acceptable if
$M=\Sk_{\mathfrak{A}}(B\cup p\cup\mu+1)$
where
• $B$ is an initial segment of some member of $\mathcal{P}$,
• $p=\{\theta,\lambda,\lambda(1),\lambda(2), \mathcal{F}, \mathcal{P},...\}$, and
• $\mu<\lambda$
(We have been sloppy with $p$.  The intent is that $p$ encodes the parameters associated with the preceding discussion.)

If $M$ is an acceptable model, then $|M|<\lambda$.  Also note that there are at most $\lambda(2)=|\mathcal{P}|$ acceptable models.

We define $\mathcal{P}^*\subseteq[\lambda]^{<\lambda}$ to be all sets of the form $M\cap\lambda$ where $M$ is an acceptable model.

It remains to show that $\mathcal{P}^*$ has the required covering property.  We will do this in the next couple of posts.

Wednesday, June 05, 2013

Continuing

$\DeclareMathOperator{\pp}{pp} \def\pcf{\rm{pcf}} \DeclareMathOperator{\cov}{cov} \def\cf{\rm{cf}} \def\REG{\sf {REG}} \def\restr{\upharpoonright} \def\bd{\rm{bd}} \def\subs{\subseteq} \def\cof{\rm{cof}} \def\ran{\rm{ran}} \DeclareMathOperator{\PP}{pp}$

Continuing our series of posts, let us recall

1. $\cf(\lambda)<\theta=\cf(\theta)<\lambda$,
2. $\lambda(1):=\cf_{<\theta}(\prod(\lambda\cap\REG), <_{J^\bd_\lambda})$, and
3. $\lambda(2)$ is the minimum cardinality of a family $\mathcal{P}\subseteq[\lambda(1)]^{<\lambda}$ such that for any $B\in[\lambda(1)]^\theta$ there is an $A\in\mathcal{P}$ with $A\cap B$ infinite.
I still owe you a proof that
$$\cov(\lambda,\lambda,\theta,2)\leq\lambda(2)\leq\cov(\lambda(1),\lambda,\theta^+,\theta).$$

The first of these inequalities requires a bit of machinery, so I'll save that for later and instead give the trivial proof of the second one and then make some comments on the relationship between $\lambda(1)$ and $\lambda(2)$.

Proposition: $\lambda(2)\leq\cov(\lambda(1),\lambda,\theta^+,\theta)$.

Let $\mathcal{P}\subseteq [\lambda(1)]^{<\lambda}$ have the property that any $B\in [\lambda(1)]^{\theta}$ is covered by a union of fewer than $\theta$ sets from $\mathcal{P}$.  Given such a $B$, it follows immediately that there is an $A\in \mathcal{P}$ for which $A\cap B$ is infinite.

Moving on to something a little more interesting, what can we say about the relationship between $\lambda(1)$ and $\lambda(2)$?

What I would like to prove here is that if $\lambda(1)$ is strictly less than $\lambda(2)$, then there must be a cardinal of cofinality $\theta$ in the interval $(\lambda,\lambda(1)]$.  Said another way, we show
$$\lambda(1)<\lambda^{+\theta}\Longrightarrow \lambda(1)=\lambda(2).$$

There's a cheap proof of this that is easy only by way of quoting  Shelah's cov vs. pp theorem (Theorem 5.4 on page 87 of Cardinal Arithmetic).  This proof works by noting that
$$\lambda(1)<\lambda(2)\Longrightarrow \lambda(1)<\cov(\lambda(1),\lambda,\theta^+,\theta),$$
and by the cov vs. pp theorem, this latter cardinal is equal to

$\lambda(1)+\sup\{\pp_{\Gamma(\theta^+,\theta)}(\lambda^*):\lambda\leq\lambda^*\leq\lambda(1)\wedge\cf(\lambda^*)=\theta\}.$

Since we know $\lambda(1)<\cov(\lambda(1),\lambda,\theta^+,\theta)$, we conclude there must be a singular cardinal of cofinality $\theta$ in the interval $[\lambda,\lambda(1)]$. Since $\cf(\lambda)<\theta$, the only way this can happen is if
$$\lambda^{+\theta}\leq\lambda(1).$$

The other proof I have in mind is also easy, and it doesn't require any fancy pcf theory:

For a cardinal $\kappa$, let $P(\kappa)$ be the statement that there is a family $\mathcal{P}\subseteq[\kappa]^<\lambda$ of size $\kappa$ with the property that for any $B\in [\kappa]^\theta$, there is an $A\in\mathcal{P}$ with $A\cap B$ infinite.

Clearly $P(\lambda)$ holds by way of "initial segments" as $\cf(\lambda)<\theta$, and an easy induction shows that $P(\kappa)$ holds if $\lambda\leq\kappa<\lambda^{+\theta}$.  Thus, if $P(\lambda(1))$ fails it must be the case that $\lambda^{+\theta}\leq\lambda(1)$.

Why should we care about the above?  My interest here lies in the question of whether or not the cardinals $\lambda(1)$ and $\cov(\lambda,\lambda,\theta^+,2)$ are actually equal.  What we've shown above is that if they are not, then there's a sizable gap between $\lambda$ and $\cov(\lambda,\lambda,\theta, 2)$.

Cutting down the case where $\lambda$ has size cofinality $\omega$, the above shows:
$$\cf_{\aleph_0}(\prod(\lambda\cap\REG), <_{J^\bd_\lambda})<\cov(\lambda,\lambda,\aleph_1, 2)\Longrightarrow \lambda^{+\omega_1}\leq\cov(\lambda,\lambda,\aleph_1, 2).$$