Friday, March 01, 2019

On a result of Gitik and Shelah

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

Granted, the title of this post is not very illuminating, as there are several theorems due to Gitik and Shelah.  What I have in mind is the following result:

Theorem 1.5 of [GiSh:412]
If $\mu>\kappa$, then the set $\{\cov(\mu,\kappa,\theta,\omega_1):\theta<\kappa\}$ is finite.

The result is in [GiSh:412], and is described as a ``non-GCH version'' of the Hajnal-Shelah theorem stating the set $\{\mu^\theta:2^\theta<\mu\}$ is finite.  It is a lovely illustration of the power of Shelah's cov vs. pp Theorem, and it is the use of this theorem that requires the fourth parameter in cov to be uncountable.

The proof in [GiSh:412] is very short, but it doesn't quite work as written.  We'll take a look at their proof and show it works except in the case where $\kappa$ is singular of uncountable cofinality, and then give an argument reducing this case to the one where $\kappa$ is regular. 

Lemma
If $\mu>\kappa$ and $\kappa$ is not singular of uncountable cofinality, then the set $\{\cov(\mu,\kappa,\theta,\omega_1):\theta<\kappa\}$ is finite.

Proof:

Assume this fails.  By monotonicity properties of cov, we can find an increasing sequence $\langle\theta_n:n<\omega\rangle$ of cardinals such that

$$\cov(\mu,\kappa,\theta_n,\omega_1)<\cov(\mu,\kappa,\theta_{n+1},\omega_1)$$

for each $n<\omega$.  Without loss of generality, we may assume each of these covering numbers is greater than $\mu$.

Since we have $\omega_1$ appearing as the fourth component, we can apply the Cov vs. pp Theorem (Theorem 5.4 of Chapter II of Cardinal Arithmetic), which tells us that if $\cov(\mu,\kappa,\theta,\omega_1)>\mu$, then

$$\cov(\mu,\kappa,\theta,\omega_1)=\sup\{\pp_{\Gamma(\theta,\omega_1)}(\chi): \kappa\leq\chi\leq\mu \text{ and }\cf(\chi)<\theta\}$$

In particular, for each $n<\omega$ we have

$$\mu<\cov(\mu,\kappa,\theta_n,\omega_1)=\sup\{\pp_{\Gamma(\theta_n,\omega_1)}(\chi): \kappa\leq\chi\leq\mu \text{ and }\cf(\chi)<\theta_n\}.$$

Given $n$, let $\chi_n$ be the least cardinal satisfying

  • $\kappa\leq\chi_n\leq\mu$,
  • $\omega_1\leq\cf(\chi_n)\leq\theta_n$, and
  • $\pp_{\Gamma(\theta_n,\omega_1)}(\chi_n)>\mu$.
Notice that $\chi_n$ must exist as $\cov(\mu,\kappa,\theta_n,\omega_1)>\mu$, and furthermore $\kappa<\chi_n$, because we have assumed $\kappa$ is not singular of uncountable cofinality -- this is the point where we use that assumption.

Since the sequence $\langle \chi_n:n<\omega\rangle$ is non-increasing, we can drop a few terms and assume that it is constant, say with value $\chi^*$.  Thus, there is a single cardinal $\chi^*$ such that for each $n<\omega$, $\chi^*$ is the least cardinal  satisfying

  • $\kappa<\chi^*\leq\mu$,
  • $\omega_1\leq \cf\chi^*<\theta_n$, and
  • $\pp_{\Gamma(\theta_n,\omega_1)}(\chi^*)>\mu$.

Now suppose $\kappa<\chi<\chi^*$ and $\omega_1\leq\cf(\chi)<\theta_n$.   Since $\chi^*$ is the least cardinal with the enumerated properties, we know 

$$\pp_{\Gamma(\theta_n,\omega_1)}(\chi)\leq\mu.$$

But we can then conclude

(*) $\pp_{\Gamma(\theta_n,\omega_1)}(\chi)<\chi^*$,

as otherwise Inverse Monotonicity (see part (4) of the No Hole Conclusion 2.3 of Chapter II of Cardinal Arithmetic) forces us to conclude

$$\pp_{\Gamma(\theta_n,\omega_1)}(\chi^*)\leq\pp_{\Gamma(\theta_n,\omega_1)}(\chi),$$

which would contradict our choice of $\chi^*$.


Since we have (*) holding for all relevant $\chi<\chi^*$, we can now apply a generalization of one of the main results of [Sh:371].  The actual theorem we need is Lemma 1.2 of the published version of [Sh:410], which tells us that since (*) holds for all sufficiently large $\chi<\chi^*$, we have

(**) $\pp_{\Gamma(\theta_n,\omega_1)}(\chi^*)=\pp_{\Gamma((\cf \chi^*)^+,\omega_1)}(\chi^*).$

(There are some issues with the proof of Lemma 1.2 in [Sh:410] that I will deal with in a future post, but the result still holds.)

Thus, the sequence $\langle\pp_{\Gamma(\theta_n,\omega_1)}(\chi^*):n<\omega\rangle$ is actually constant with value some $\lambda^*$.  The following claim immediately yields a contradiction:

Claim:  For all $n<\omega$, $\cov(\mu,\kappa,\theta_n,\omega_1)=\lambda^*$.

Proof of claim:
Let $n<\omega$ be given. Recall that by the cov vs. pp Theorem, we know 
$$\cov(\mu,\kappa,\theta_n,\omega_1)=\sup\{\pp_{\Gamma(\theta_n,\omega_1)}(\chi): \kappa\leq\chi\leq\mu \text{ and }\cf(\chi)<\theta_n\}$$
so in particular $$\lambda^*\leq\cov(\mu,\kappa,\theta_n,\omega_1).$$

Let $\chi$ be one of the cardinals used in computing the supremum.  By our assumptions on $\kappa$, we know $\kappa\neq\chi$ so $\kappa<\chi$.   If $\chi<\chi^*$, then by (*) we know

$$\pp_{\Gamma(\theta_n,\omega_1)}(\chi)<\lambda^*$$

On the other hand, if $\chi^*<\chi$ then because $\chi<\mu<\pp_{\Gamma(\theta_n, \omega_1)}(\chi^*)$, we know

$$\pp_{\Gamma(\theta_n,\omega_1)}(\chi)\leq \pp_{\Gamma(\theta_n, \omega_1)}(\chi^*)=\lambda^*$$

by inverse monotonicity.

Thus, $\cov(\mu,\kappa,\theta_n,\omega_1)=\lambda^*$. $_\square$



Now where did we use the assumption that $\kappa$ is not a singular cardinal of uncountable cofinality?   It was used when we needed to know $\kappa<\chi^*$, so that we can conclude (*) holds for all sufficiently large $\chi<\chi^*$ of the right cofinality.

Now how do we deal with this last case?  Let us assume that $\kappa$ is singular of uncountable cofinality, and find the sequence $\langle \theta_n:n<\omega\rangle\rangle$.   For each $n<\omega$ there is a cardinal $\kappa_n<\kappa$ such that

$$\cov(\mu,\kappa,\theta_n, \omega_1)=\cov(\mu,\kappa^*,\theta_n,\omega_1)$$

for all $\kappa^*\geq\kappa_n$ (as the covering numbers are non-increasing as we increase $\kappa^*$ to $\kappa$).

Since $\kappa$ has uncountable cofinality, there is a single $\kappa^*<\kappa$ (which can be taken to be regular) such that

$$\cov(\mu,\kappa,\theta_n,\omega_1)=\cov(\mu,\kappa^*,\theta_n,\omega_1)\text{ for all }n<\omega.$$

Now we generate a contradiction as in the preceding case.  $_\square$



















Friday, December 21, 2018

Another Application

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\forces{\Vdash}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

Continuing the last post. we show that proper $\aleph_2$--c.c. notions of forcings have another nice property.  This result is motivated by a question of Chodounsky and Guzman (private communication)

Theorem
Suppose $P$ is a proper and $\omega_2$-c.c. notion of forcing, $p\in P$, and $\dot S$ is a $P$-name for a stationary subset of $\omega_1$.  For all sufficiently large regular $\chi$, there are stationarily many elementary submodels $N\in [H(\chi)]^{\aleph_0}$ for which there is $q\in P$ such that
(1) $q\leq p$,

(2)  $q$ is $(N, P)$-generic, and

(3) $q\forces N[\dot G]\cap\omega_1\in \dot S$.


Proof
Given $P$, $p$, and $\dot S$, we show how find such an $N$ and $q$. The usual arguments show that the set of such $N$ is stationary.

Let $\langle N_\alpha:\alpha<\omega_1\rangle$ be a continuous $\in$-chain of countable elementary submodels of $H(\chi)$ with $\{P, p, \dot S\}\in N_0$, and let $G$ be a generic subset of $P$ containing $p$.

Since $P$ is proper, $p$ forces the existence of a closed unbounded set of $\delta<\omega_1$ such that

$$N_\delta\cap\omega_1 = N_\delta[\dot G]\cap\omega_1,$$

and so

$$p\forces (\exists\delta<\omega_1)[\delta\in\dot S\text{ and }N_\delta\cap\omega_1=N_\delta[\dot G]\cap\omega_1].$$

Now choose $q\leq p$ deciding a particular value for $\delta$.  This $q$ is $(N_\delta, P)$-generic by the previous post, and has the required properties.


Another application of "The Argument"

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\forces{\Vdash}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)


Here, we show that semi-proper $\aleph_2$-cc notions of forcing are proper. I have no idea if this has been noted before, but the proof we give is another application of "The Argument''.

Lemma

Suppose $P$ is an $\omega_2$-c.c. notion of forcing, and let $N$ be a countable elementary submodel of $H(\chi)$ for some sufficiently large regular $\chi$ with $P\in N$.  Then the following are equivalent for a condition $q\in P$:

  1. $q$ is $(N, P)$-generic, and
  2. $q\forces N\cap\omega_1 = N[\dot G]\cap\omega_1$.


Proof.

One implication is trivial, so assume we are given a $q$ as in (2).  Given a regular cardinal $\kappa\in N$, we claim

$$q\forces \sup(N\cap\kappa)=\sup(N[\dot G]\cap\kappa).$$

This happens automatically for $\kappa=\aleph_0$, and our assumption tells us this holds for $\kappa=\aleph_1$, so we may assume $\kappa$ is at least $\aleph_2$.

If $\dot\tau\in N$ is a $P$-name for an ordinal below $\kappa$, we let


$$X(\dot\tau)=\{\alpha<\kappa:(\exists p\in P)[p\forces \dot\tau=\alpha]\}.$$

The set $X(\dot\tau)$ is a set definable in $N$, and it has cardinality at most $\aleph_1$ because $P$ has the $\aleph_2$-chain condition.  It follows that $\beta:=\sup(X(\dot\tau))$ is an ordinal in $N\cap\kappa$, and clearly any condition forces $\dot\tau$ to be at most $\beta$.  It follows that any condition in $P$ forces $N\cap\kappa$ to be cofinal in $N[\dot G]\cap\kappa$.

Putting this together with our assumption (2), we get what we need, and now finish by using "The Argument" to show that $q$ is $(N, P)$-generic. 

Let $G$ be a generic subset of $P$ containing $q$, and we show $N\cap On = N[G]\cap On$ in the extension $V[G]$.  Assume this fails, that is, assume $N\cap On$ is a proper subset of $N[G]\cap On$.  Let $\alpha$ be the least ordinal in $N[G]$ not in $N$, and let $\beta$ be the least ordinal in $N$ above $\alpha$ (note that $\beta$ exists, as the argument we used above shows that $N\cap On$ is cofinal in $N[G]\cap On$).    Just as in the previous posts, one shows that $\beta$ must be a regular cardinal, but then we get a contradiction as

$$\sup(N\cap\beta)\leq\alpha<\sup(N[G]\cap\beta).$$

It must then be the case that $N\cap On = N[G]\cap On$.  Since $G$ was any generic subset of $P$ containing $q$, we know

$$q\forces N\cap On = N[\dot G]\cap On,$$

and so $q$ is $(N, P)$-generic.


Wednesday, December 05, 2018

Section 2 of [Sh:410] Part V - The Final Piece

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

Clearly $N\cap\mu\subseteq N^+\cap\mu$ so assume by way of contradiction the containment is strict, and let

$\gamma(*)=\min(N^+\cap\mu\setminus N).$

If we set $A=N\cap (\omega_1,\mu]\cap\REG$, then our construction guarantees

$\ch_N\restr A= \ch_{N^+}\restr A$.  In particular, if $\mu$ is regular, then

$\sup(N^+\cap\mu)=\sup(N\cap\mu)$.  This also holds if $\mu$ is singular, as either $\cf(\mu)\leq\omega_1$ and $N\cap\mu$ is cofinal in $\mu$, or $\cf(\mu)\in A$ and we use the fact that $\sup(N^+\cap\cf(\mu))=\sup(N\cap\cf(\mu))$.

In either situation, it follows that  $N\cap\mu\setminus\gamma(*)\neq\emptyset$.

Let us define

$$\beta(*)=\min(N\cap\mu\setminus\gamma(*)).$$

Note that the interval $[\beta(*),\gamma(*))$ is (non-empty and) disjoint to $N$.  A simple argument by contradiction tells us that $\gamma(*)$ must be a regular cardinal, but this is impossible:

On the one hand, $\sup(N\cap\gamma(*))=\sup(N^+\cap\gamma(*))$ as $\gamma(*)\in A$, but on the other hand

$\sup(N\cap\gamma(*)\leq\beta(*)<\sup(N^+\cap\gamma(*))$

as $\beta(*)+1\in N^+\cap\gamma(*)$.

Thus, it must be the case that $N\cap\mu=N^+\cap\mu$, and so $X\subseteq N\cap\mu$ as required.

Section 2 of [Sh:410] Part IV - The Proof

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

Moving now to a proof of the theorem from our last post:

Let us assume are as in the same set-up as Part II of this series, that is, 

 $\mu\geq\aleph_\omega$ is a cardinal, and

$\lambda^*=\sup\{\pp(\epsilon):\omega_1<\epsilon\leq\mu\text{ and }\cf(\epsilon)=\aleph_0\}$

Let $\chi$ be a sufficiently large regular cardinal, and let $\langle M_\alpha:\alpha<\cf(\lambda^*)\rangle$ be a tower of elementary submodels of $\mathfrak{A}:=\langle H(\chi), \in, <^*\rangle$  built ``as usual'', and let 

$M^*:=\bigcup_{\alpha<\cf(\lambda^*)}M_\alpha.$

We claim that $\mathcal{P}:= M^*\cap [\mu]^{\aleph_0}$ enjoys the property demanded by the theorem.

To show this, let $X$ be a subset of $\mu$ of cardinality $\aleph_1$.  We are going to run what I like to call "THE argument", as it appears so often in these sorts of results.

We will build a sequence $\langle N_m:m<\omega\rangle$ of elementary submodels of $\mathfrak{A}$ so that the following conditions are satisfied:

  1. $X\subseteq \bigcup_{m<\omega}N_m$, 
  2. $|N_m|=\aleph_1$, and 
  3. every member of $[N_m]^{\aleph_0}$ is covered by a countable set from $M^*$, that is,
$$(\forall Y\in [N_m]^{\aleph_0})(\exists Z\in M^*\cap [M^*]^{\aleph_0})\bigl[ Y\subseteq Z\bigr].$$

This will establish the theorem, as we let $X_m = X\cap N_m$.  In this situation, a countable subset of $X_m$ is covered by a countable set from $M^*$. Without loss of generality this countable set is a subset of $\mu$, and therefore in $\mathcal{P}$.

Our construction will start by setting

$$N_0:=\Sk_{\mathfrak{A}}(\omega_1+1)$$.   Note that condition 3 is satisfied in this situation because $N_0$ is actually an element of $M^*$.


So suppose we are given $N_m$ satisfying conditions (2) and (3) above.  We define objects as follows:

  • $A_m:= N_m\cap (\omega_1,\mu]\cap\REG$
  • $N_m^+:=\Sk_{\mathfrak{A}}(N_m\cup X)$, and
  • $g_m = \ch_{N_m^+}\restr A_m$
We are now set up to apply Lemma 3 from Part I and Lemma 4 from Part II of this series.  Since $|A_m|=\aleph_1$, our assumptions tell us there is a set $\mathcal{B}$ such that 
  • $\mathcal{B}\subseteq M\cap [A_m]^{\aleph_0}$, and
  • $|\mathcal{B}|=\aleph_1$.
By Lemma 3, there is a function $f_m\in\prod A_m$ such that

  • $g_m<f_m$, and
  • $f_m\restr B\in M^*$ for every $B\in\mathcal{B}$.
We define  

$$N_{m+1} := \Sk_{\mathfrak{A}}(N_m\cup \{f_m(\theta):\theta\in A_m\}).$$

Lemma 4 tells us that Condition (3) is maintained for $N_{m+1}$, and the construction continues.

To finish, we define  

$$N=\bigcup_{m<\omega} N_m$$

and

$$N^+=\bigcup_{m<\omega} N_m^+$$.

Clearly $X\subseteq N^+\cap\mu$, so we finish if we know $N^+\cap \mu = N\cap\mu$.

This will follow by a standard argument, but I don't know that there is a crisp formulation of what we need in Shelah's writings.  We'll just show the equality in the next post.





Section 2 of [Sh:410] Part III - The Theorem

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

Our goal is to present a proof of the following theorem.

Theorem
Suppose $\mu\geq\aleph_\omega$ is a cardinal, and let
$$\lambda^*=\sup\{\pp(\epsilon):\omega_1<\epsilon\leq\mu\text{ and }\cf(\epsilon)=\aleph_0\}.$$

Then there is a set $\mathcal{P}\subseteq [\mu]^{\aleph_0}$ of cardinality $\lambda^*$ such that any $X\in[\mu]^{\aleph_1}$ can be written as a countable union of sets, each of whose countable subsets is covered by a set in $\mathcal{P}$, that is, given $X\subseteq \mu$ of cardinality $\aleph_1$, we can find sets $\langle X_n:n<\omega\rangle$ such that


  • $X=\bigcup_{n<\omega}X_n$, and
  • $(\forall Y\in [X_n]^{\aleph_0})(\exists Z\in \mathcal{P})\bigl[Y\subseteq Z\bigr]$.

The use of $\mu\geq\aleph_\omega$ is just to ensure that $\lambda^*$ is not defined as the supremum of the empty set.

This theorem is (a piece of) Claim 2.2 in Section 2 of [Sh:410].  The proof sketched by Shelah is dubious at a couple of points, and I don't think his full result goes through.  We are replacing his Observation 2.3 by the results in the previous two posts.


After we prove the theorem, we will look at some applications to combinatorial set theory.

Section 2 of [Sh:430] Part II - Even More Technical Lemmas

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

We deal with some more technical material regarding Skolem hulls.

Let $\mu\geq\aleph_\omega$ be a cardinal, and let 

$\lambda^*=\sup\{\pp(\epsilon):\omega_1<\epsilon\leq\mu\text{ and }\cf(\epsilon)=\aleph_0\}$

Let $\chi$ be a sufficiently large regular cardinal, and let $\langle M_\alpha:\alpha<\cf(\lambda^*)\rangle$ be a tower of elementary submodels of $\mathfrak{A}:=\langle H(\chi), \in, <^*\rangle$  built ``as usual'', and let 

$M^*:=\bigcup_{\alpha<\cf(\lambda^*)}M_\alpha.$

Lemma 4
Suppose we have a model $M\prec \mathfrak{A}$ of cardinality $\aleph_1$ such that 

$$(\forall Y\in [M]^{\aleph_0})(\exists Z\in M^*\cap [M^*]^{\aleph_0})\bigl[Y\subseteq Z\bigr].$$

Let $A= M\cap(\omega_1,\mu]\cap\REG$,  let $\mathcal{B}\subseteq M^*\cap[A]^{\aleph_0}$ be cofinal in $[A]^{\aleph_0}$ with $|\mathcal{B}|=\aleph_1$, and let $f$ be a function as in the conclusion of Lemma 3 of the previous post. Define a model $N$ by 

$$N:=\Sk_{\mathfrak{A}}(M\cup \{f(\theta):\theta\in A\}).$$

Then

$$(\forall Y\in [N]^{\aleph_0})( \exists Z\in M^*\cap [M^*]^{\aleph_0})\bigl[Y\subseteq Z\bigr].$$



Proof:

Given a countable $Y\subseteq N$, there are countable $p\subseteq M$ and $q\subseteq A$ such that

$$Y\subseteq\Sk_{\mathfrak{A}}(p\cup\{f(\theta):\theta\in q\}).$$

By our assumption, we may assume that $p$ and $q$ are both in $M^*$ (they are both covered by countable sets from $M^*$, and replacing them by larger sets just enlarges the Skolem hull.)  Moreover, we may assume $q\in \mathcal{B}$.

Given our choice of $f$ and $\lambda^*$, we know $\{f(\theta):\theta\in q\}$ is in $M^*$ by way of Lemma 3 of the preceding post.

If we choose $\alpha<\cf(\lambda^*)$ so that $p$, $q$, and $\{f(\theta):\theta\in q\}$ are all in $M_\alpha$, then the relevant Skolem hull can be computed in $M^*$ using $M_\alpha$, and so

$Y\subseteq Z:=\Sk_{\mathfrak{A}}(p\cup\{f(\theta):\theta\in q\})\in M^*\cap [M^*]^{\aleph_0}.$



Thursday, November 29, 2018

Section 2 of [Sh:410] Part I - Technical Lemmas

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

This post will lay down preliminary material for obtaining some results in [Sh:410] to be discussed in the next installment.

Let $\mu>\aleph_1$ be a cardinal, and let

$\lambda^*=\sup\{\pp(\epsilon):\omega_1<\epsilon\leq\mu\text{ and }\cf(\epsilon)=\aleph_0\}.$


Let $\chi$ be a sufficiently large regular cardinal, and let $M$ be an elementary submodel of $\langle H(\chi),\in,<^*\rangle$ of cardinality $\lambda^*$ containing everything relevant.

Note that $M$ will contain a family

$\bar{F}=\langle \bar{f}^A: A\subseteq (\omega_1,\mu]\cap\REG\text{ and }|A|=\aleph_0\rangle,$
where
$\bar{f}^A=\langle \bar{f}^{A,\lambda}:\lambda\in\pcf(A)\rangle,$
and
$\bar{f}^{A,\lambda}=\langle f^{A,\lambda}_\alpha:\alpha<\lambda\rangle$
is a minimally obedient (at cofinality $\omega_1$) universal sequence for $\lambda\in\pcf A$.  (See Section 5 of Abraham-Magidor.)  $_\square$

Lemma 1
Suppose $A$ satisfies
  • $A\subseteq (\aleph_1,\mu]\cap\REG$,
  • $A\in  M$, and
  • $|A|=\aleph_0$.
Then $f^{A,\lambda}_\alpha\in M$ for any $\lambda\in\pcf(A)$ and $\alpha<\lambda$.

Proof:  Given the preceding post, this follows easily from the definition of $\lambda^*$ as $\lambda^*+1\subseteq M$.  $_\square$

Lemma 2
Suppose $N$ is an $\omega_1$-presentable elementary submodel of $H(\chi)$, and let $A$ satisfy

  • $A\subseteq (\aleph_1,\mu]\cap\REG$,
  • $A\in N\cap M$, and
  • $|A|=\aleph_0$.
Then $\ch_N\restr A\in M$.

Proof.  This is an application of Corollary 5.9 in Abraham-Magidor.  Since $A\in N$, we know there are cardinals $\lambda_0>\lambda_1>\cdots>\lambda_n$ in $N\cap \pcf(A)$ such that
$$\ch_N\restr A = \sup\{f^{A,\lambda_0}_{\gamma_0},\dots,f^{A,\lambda_n}_{\gamma_n}\},$$
where $\gamma_n=\sup(N\cap\lambda_n)$.  Since $A\in M$, the previous lemma tells us $\ch_N\restr A\in M$.  $_\square$


Lemma 3
Suppose $A\subseteq (\aleph_1,\mu]\cap\REG$ is of cardinality $\aleph_1$, and $\mathcal{B}$ is a subset of  $M\cap[A]^{\aleph_0}$ of cardinality $\aleph_1$.  Give $g\in\prod A$ there is $f\in\prod A$ such that

  • $g<f$, and
  • $f\upharpoonright B\in M$ for every $B\in\mathcal{B}$.
(Note that we do not assume that $A$ is in $M$, only that the elements of $\mathcal{B}$ are.)
Proof.

Let $N$ be an $\omega_1$-presentable elementary submodel of $H(\chi)$ containing $A$, $\mathcal{B}$, and $g$.   Let $f=\ch_N\restr A$, so clearly $g<f$ as $A\subseteq N$.

Given $B\in\mathcal{B}$, we know $B\in N\cap M$ (as $\mathcal{B}\subseteq N$) and so the previous lemma applies giving us $f\restr B=\ch_N\restr B\in M$.  $_\square$







Wednesday, November 21, 2018

Section 2 of [Sh:410] Part 0: Two cardinals

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

This post pins down an easy observation, relevant to several results of Shelah:


Observation:

Suppose $\theta\leq\kappa<\mu$   Then following two cardinals are equal:

$\lambda_1:=\sup\{\pp_{<\theta}(\tau):\kappa<\tau\leq\mu\text{ and }\cf(\tau)<\theta\}$

$\lambda_2:=\sup\{\max\pcf(A):  A\subseteq (\kappa,\mu]\cap\REG \text{ and }|A|<\theta\}$.

Proof:

Suppose $\lambda<\lambda_1$, and choose a cardinal $\tau$ satisfying
  • $\kappa<\tau\leq\mu$,
  • $\cf(\tau)<\theta$, and
  • $\lambda<\pp_{<\theta}(\tau)$
This last statement means that we can find a set $A$ and an ultrafilter $U$ on $A$ such that

  • $A$ is cofinal in $\tau\cap\REG$,
  • $|A|<\theta$,
  • $U$ extends the cobounded filter on $A$,  and
  • $\lambda<\tcf(\prod A/ U)$
Replacing $A$ by $A\cap (\kappa,\mu]$ does not change the situation, as $A\cap\kappa+1$ is not in the ultrafilter $U$, and so $A$ and $U$ witness that $\lambda<\lambda_2$.


Now suppose $\lambda<\lambda_2$, and choose $A$ and $U$ such that
  • $A\subseteq (\kappa,\mu]\cap\REG$,
  • $|A|<\theta$,
  • $U$ an ultrafilter on $A$, and
  • $\lambda<\tcf(\prod A/U)$.
Let $\epsilon\leq\sup(A)$ be minimal with $A\cap\epsilon\in U$.  It is clear that $A$ is unbounded in $\epsilon$, and so $\epsilon$ is a singular cardinal of cofinality at most $|A|<\theta$.

The set $A\cap\epsilon$ and the ultrafilter $U$ restricted to $A\cap\epsilon$ witness that

$\lambda<\pp_{<\theta}(\epsilon)$

and this implies $\lambda<\lambda_1$.

Sunday, November 11, 2018

A note on rank and colorings

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{pcf}
\DeclareMathOperator{\cov}{cov}
\def\cf{\rm{cf}}
\DeclareMathOperator{\otp}{otp}
\def\REG{\sf {REG}}
\def\restr{\upharpoonright}
\def\bd{\rm{bd}}
\def\subs{\subseteq}
\def\cof{\rm{cof}}
\def\ran{\rm{ran}}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)


Given a function $f:\theta\rightarrow\lambda$ for cardinals $\theta$ and $\lambda$ with $\cf(\theta)$ uncountable, we let $||f||$ denote the Galvin-Hajnal rank of $f$ with respect to the unbounded filter on $\theta$.

Theorem
Suppose $\aleph_0<\theta<\lambda$ and there is a function $f:\theta\rightarrow\lambda$ such that $||f||\geq\lambda$.  Then there is a coloring $p:[\lambda]^{<\omega}\rightarrow\theta$ such that the range of $p\restr [A]^{<\omega}$ is unbounded in $\theta$ whenever $A\subseteq\lambda$ is of cardinality $\lambda$.

proof.

Let $\chi$ be a sufficiently large regular cardinal, and assume by way of contradiction that the conclusion fails.  Then we can an elementary submodel $M$ of $H(\chi)$ such that

  • $\theta$, $\lambda$, and $f$ are all in $M$,
  • $|M\cap\lambda|=\lambda$, but
  • $M\cap\theta$ is bounded in $\theta$.
Given such an $M$, we define $\delta=\sup(M\cap\theta)$.   Let us now agree to call a function $g:\theta\rightarrow\lambda$ bad if
  • $g\in M$, and
  • $g(\delta)<\otp(M\cap ||g||)$.
Notice that our function $f$ is bad, so there exists at least one bad function.

Claim: If $g$ is a bad function then there is another bad function $h$ such that $h\restr[\delta,\theta)<g\restr[\delta,\theta)$.

Notice that the claim gives us a contradiction: using $f$ as $g_0$, we can iterate the claim to produce a sequence of bad functions $\langle g_n:n<\omega\rangle$ so that $\langle g_n(\delta):n<\omega\rangle$ forms an infinite decreasing sequence of ordinals.

To prove the claim, we proceed as follows:

We know $g(\delta)<\otp(M\cap||g||)$, so choose $\beta\in M\cap ||g||$ such that
$$g(\delta)=\otp(M\cap\beta).$$

Since $\beta<||g||$, we can find $h:\theta\rightarrow\lambda$ such that $h<^* g$ and
$\beta\leq ||h||$.


Since $g$ and $\beta$ are in $M$, we may assume that $h$ is in $M$ as well, and therefore so is the ordinal
\begin{equation}
\gamma:=\sup\{i<\theta: g(i)\leq h(i)\}.
\end{equation}

Given our choice of $\delta$, it follows that $\gamma<\delta$, and so
\begin{equation}
h\restr [\delta,\theta)< g\restr [\delta,\theta).
\end{equation}

In particular,  $h(\theta)<g(\theta)$ and therefore
\begin{equation}
h(\theta)<g(\theta)=\otp(M\cap\beta)\leq\otp(M\cap ||h||),
\end{equation}
and so $h$ is indeed a bad function.




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.