Wednesday, July 20, 2016

On a theorem of Gitik and Shelah II: Blanket Assumptions


\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{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{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

Assumptions for the next few posts are:


  • $\kappa$ weakly compact
  • $\mu>2^\kappa$ is singular of cofinality $\kappa$
  • $A\subseteq\mu$ is a set of regular cardinals
  • $A$ is unbounded in $\mu$ of cardinality $\kappa$
  • $J$ is a $\kappa$-complete ideal on $A$ extending the bounded ideal
  • $\lambda=\tcf(\prod A/ J)$
Since $J$ extends the bounded ideal, we may as well assume

  • $(2^\kappa)^+<\min(A)$ 
Of course this implies  $|A|<\min(A)$, and so without loss of generality $A$ is progressive.

Let $D$ be an ultrafilter on $A$ disjoint to $J$.  Then $\cf(\prod A/D)=\lambda$ and hence $\lambda\in \pcf(A)$.  Furthermore, if $B_\lambda[A]$ is a pcf generator for $\lambda$ then $B_\lambda[A]$ must be in $D$ and therefore unbounded in $A$.

It follows that $\tcf(\prod B_\lambda[A]/J)=\lambda$ as well, and so we may assume (by passing to $B_\lambda[A]$ if necessary) that

  • $\lambda=\max\pcf(A)$

Our assumption that $2^\kappa<\min(A)$ tells us that

(1)  $\pcf(\pcf(A))=\pcf(A)$, and

(2)  $|\pcf(A)|\leq 2^\kappa<\min(A)=\min(\pcf(A))$


and so $\pcf(A)$ has a transitive set of generators, that is, a sequence $\langle B_\theta:\theta\in\pcf(A)\rangle$ such that

  • $B_\theta\subseteq \pcf(A)$
  • $B_\theta$ is a generator for $\theta$ in $\pcf(\pcf(A))=\pcf(A)$, and
  • $\tau\in B_\theta\Longrightarrow B_\tau\subseteq B_\theta$.




Friday, July 01, 2016

On a theorem of Gitik and Shelah I

\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\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{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

We are going to be looking at Theorem 2.1 of [GiSh:1013]  "Applications of pcf for mild large cardinals to elementary embeddings" Annals of Pure and Applied Logic 164 (2013) 855--865:

Theorem (Gitik and Shelah)
Assume $\kappa$ is weakly compact and $\mu>2^\kappa$ is singular of cofinality $\kappa$. If $\lambda$ is a regular cardinal satisfying $\mu<\lambda<\pp^+_{\Gamma(\kappa)}(\mu)$, then there is an increasing sequence $\langle\lambda_i:i<\kappa\rangle$ of regular cardinals converging to $\mu$ such that $\lambda=\tcf(\prod_{i<\kappa}\lambda_i/J^{\bd}_\kappa)$.


In this post, we will simply unpack what the theorem says.


The assumption  $\mu<\lambda<\pp^+_{\Gamma(\kappa)}(\mu)$ means the following:

There is a set of regular cardinals $A\subseteq\mu$ and a $\kappa$-complete ideal $J$ on $A$ such that

  • $A$ is unbounded in $\mu$
  • $|A|=\kappa$
  • $J$ extends the ideal $J^{\bd}[A]$ of bounded subsets of $A$, and
  • $\lambda=\tcf(\prod A/ J)$.
Comments:

1. $A$ need not have order-type $\kappa$, and $J$ can potentially be much larger than the ideal of bounded subsets of $A$.

2. Recall a poset has true cofinality $\lambda$ if it has a totally ordered cofinal subset of cardinality $\lambda$.


So our assumptions tell us $\lambda$ can be represented as $\tcf(\prod A/ J)$ for a certain sort of $A$ and $J$.

The conclusion of the theorem is that in fact $\lambda$  has a very nice representation as a true cofinality:

There is a set of regular cardinals $D\subseteq \mu$ (in fact, $D$ will be a subset of $\pcf(A)\cap\mu$) such that

  • $D$ is unbounded in $\mu$ of order-type $\kappa$, and
  • $\lambda=\tcf(\prod D/ J^{\bd}[D])$


















Thursday, June 30, 2016

On Weak Compactness II [edited]


\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\DeclareMathOperator{\pcf}{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{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

Lingering a little on the material from the last post just for curiosity's sake:

Theorem 

The following are equivalent for an inaccessible cardinal $\kappa$:

1.  $\kappa$ is weakly compact.

2.  For every sequence of functions $\langle f_\alpha:\alpha<\kappa\rangle$ with $f_\alpha:\alpha\rightarrow\alpha$, there is an $f:\kappa\rightarrow\kappa$ such that for every $\alpha<\kappa$ there is a $\beta\geq\alpha$ with $f_\beta\restr\alpha= f\restr\alpha$.

3. For every sequence of sets $\langle A_\alpha:\alpha<\kappa\rangle$ with $A_\alpha\subseteq\alpha$, there is a set $A\subseteq\kappa$ such that for every $\alpha<\kappa$ there is a $\beta\geq\alpha$ with $A_\beta\cap\alpha = A\cap\alpha$.

4. For every $C$-sequence $\langle C_\alpha:\alpha<\kappa\rangle$ there is a closed unbounded $C\subseteq\kappa$ such that for all $\alpha<\kappa$ there is a $\beta\geq\alpha$ with $C_\beta\cap\alpha= C\cap\alpha$.


We'll work this out next time to make sure, but (1) implies (2) by Shelah's result used last time,  and (4) implies (1) by a result of Todorcevic  (Theorem 6.3.5 of his book "Walks on Ordinals and their Characteristics").


One thing to note is that subtle cardinals, weakly ineffable cardinals, and ineffable cardinals all are defined using something that looks like condition (3).  It might be worthwhile to see if the corresponding modifications of (2) and (4) give equivalent characterizations.

See  Cantor's Attic for more information.


--------------

Edit:  (2) follows from (3) immediately, as we just set $f_\alpha$ to be the characteristic function of $A_\alpha$, and then $f$ is the characteristic function of the $A$ we need.

(4) follows from (3) immediately, as it is easily seen that if we apply (3) to a $C$-sequence $\langle C_\alpha:\alpha<\kappa\rangle$ then the resulting $A$ must be closed.










On weak compactness


\(
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\tcf}{tcf}
\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}}
\newcommand{\restr}{\upharpoonright}
\DeclareMathOperator{\ch}{Ch}
\DeclareMathOperator{\PP}{pp}
\DeclareMathOperator{\Sk}{Sk}
\)

We're firing the blog up again after a long hiatus.  Our immediate plan is to give a simplified proof of one of the main results from [GiSh:1013]  (Gitik-Shelah:  Applications of pcf for mild large cardinals to elementary embeddings).

We start with a lemma on weakly compact cardinals. I haven't seen this exact formulation before but certainly there aren't any new ideas involved.

Theorem

The following two conditions are equivalent for an uncountable cardinal $\kappa$:

1.  $\kappa$ is weakly compact.

2. If $c:[\kappa]^2\rightarrow\sigma$ with $\sigma<\kappa$, there is a function $f:\kappa\rightarrow\sigma$ and a set $H\subseteq\kappa$ of cardinality $\kappa$ such that for each $\alpha<\kappa$ we have $c(\alpha,\beta)=f(\alpha)$ for all sufficiently large $\beta\in H$.

Proof:

(2) implies (1)

Suppose $c:[\kappa]^2\rightarrow \{0, 1\}$, and let $f$ and $H$ be as in (2).   Define a function $g:\kappa\rightarrow\kappa$ by letting $g(\alpha)$ equal the least $\gamma<\kappa$ such that
\begin{equation}
\beta\in H \wedge \gamma\leq\beta\Longrightarrow c(\alpha,\beta)= f(\alpha).
\end{equation}

Thin out $H$ to $H_0$ of cardinality $\kappa$ so that
\begin{equation}
\alpha<\beta\text{ in }H\Longrightarrow g(\alpha)\leq\beta.
\end{equation}

This means that for $\alpha<\beta$ in $H_0$, $c(\alpha,\beta)=f(\alpha)$.  Now choose $\epsilon\in\{0,1\}$ so that $\{\alpha\in H_0:f(\alpha)=\epsilon\}$ has cardinality $\kappa$.  This set is homogeneous for the coloring $c$, and we conclude that $\kappa$ is weakly compact.



(1) implies (2)

We use a result due to Shelah (Theorem 1 of  [Sh:94] "Weakly compact cardinals: a combinatorial proof") which states that an inaccessible cardinal $\kappa$ is weakly compact if and only if for every family of functions $f_\alpha:\alpha\rightarrow\alpha$ (for $\alpha<\kappa$) there is a function $f:\kappa\rightarrow\kappa$ such that
$$(*) \qquad\qquad (\forall\alpha<\kappa)(\exists\beta<\kappa)[\alpha\leq\beta\wedge f_\beta\upharpoonright\alpha= f\restr\alpha].$$

Suppose $c:[\kappa]^2\rightarrow\sigma$ for some $\sigma<\kappa$.

 For $\alpha<\sigma$ we let $f_\alpha:\alpha\rightarrow\alpha$ be identically 0 (these $\alpha$ will be irrelevant), and for $\sigma\leq\alpha<\kappa$ we define $f_\alpha:\alpha\rightarrow\alpha$ by

$$f_\alpha(\gamma)=c(\gamma,\alpha).$$

Now fix a function $f:\kappa\rightarrow\kappa$ as in Shelah's theorem. We define an increasing sequence $\langle \beta_\xi:\xi<\kappa\rangle$ by the following recursion:


First, we set $\beta_0 =\sigma$.

Given $\langle \beta_\zeta:\zeta<\xi\rangle$, we define

$$\alpha_\xi=\sup\{\beta_\zeta:\zeta<\xi\}+1$$

and then use (*) to choose $\beta_\xi$ such that

$$\alpha_\xi\leq\beta_\xi\text{ and }f_{\beta_\xi}\restr\alpha_\xi = f\restr\alpha_\xi.$$


The preceding generates an increasing sequence $\langle\beta_\xi:\xi<\kappa\rangle$, and we note our construction guarantees that $c(\alpha,\beta_\xi)=f(\alpha)$ whenever $\alpha\leq\beta_\zeta$ and $\zeta<\xi<\kappa$.



In particular, if $\alpha<\kappa$ then $c(\alpha,\beta_\xi)= f(\alpha)$ for all sufficiently large $\xi<\kappa$, and $H:=\{\beta_\xi:\xi<\kappa\}$ is as required.