Thursday, June 30, 2016

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

\beta\in H \wedge \gamma\leq\beta\Longrightarrow c(\alpha,\beta)= f(\alpha).

Thin out $H$ to $H_0$ of cardinality $\kappa$ so that

\alpha<\beta\text{ in }H\Longrightarrow g(\alpha)\leq\beta.

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.

Joel David Hamkins said...
This comment has been removed by the author.
Joel David Hamkins said...

See also this MathOverflow post for a discussion of several other characterizations of weak compactness: mathoverflow.net/a/237508/1946.

Todd Eisworth said...

Thanks, Joel!