\documentclass{amsart}
\usepackage{amsfonts,graphicx,amsthm,amssymb}
\usepackage[all]{xy}
\newcommand{\tbd}[1]{
\begin{center}\framebox{\parbox{100mm}{\begin{center}\parbox{96mm}{\texttt{#1}}\end{center}}}\end{center}}
\renewcommand{\topfraction}{.85}
\renewcommand{\bottomfraction}{.8}
\renewcommand{\textfraction}{.1}
\renewcommand{\floatpagefraction}{.86}
\renewcommand{\dbltopfraction}{.66}
\renewcommand{\dblfloatpagefraction}{.66}
\setcounter{topnumber}{9}
\setcounter{bottomnumber}{9}
\setcounter{totalnumber}{20}
\setcounter{dbltopnumber}{9}
\newcommand{\x}{\mathsf{x}}
\renewcommand{\o}{\mathrm{o}}
\newcommand{\inc}{\ensuremath{\mathsf{0=1}}}
\newcommand{\pr}[1]{\prod #1}
\pagestyle{plain}
\renewenvironment{proof}{\smallskip \noindent\textsl{Proof.}
}{\rule{0mm}{1mm}\hfill{\footnotesize\textsf{q.e.d.}}\\
\medskip}
\newcommand{\blubb}{}
\newenvironment{numberedproof}[1]{\smallskip
\noindent\textsl{Proof.}
\renewcommand{\blubb}{#1}}{\rule{0mm}{1mm}\hfill{\footnotesize\textsf{q.e.d.}
(\blubb)}\\
\medskip}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{prop}[defn]{Proposition}
\newtheorem{thm}[defn]{Theorem}
\newtheorem{lem}[defn]{Lemma}
\newtheorem{lemma}[defn]{Lemma}
\newtheorem{claim}[defn]{Claim}
\newtheorem{rmk}[defn]{Remark}
\newtheorem{sublem}[defn]{Sublemma}
\newtheorem{conj}[defn]{Conjecture}
\newtheorem{cor}[defn]{Corollary}
\newtheorem{quest}[defn]{Question}
\newtheorem{fact}[defn]{Fact}
\renewcommand{\labelenumi}{(\roman{enumi})}
\newcommand{\ZF}{{\mathsf{ZF}}}
\newcommand{\ZFC}{{\mathsf{ZFC}}}
\newcommand{\AD}{{\mathsf{AD}}}
\newlength{\gnarg}
\settowidth{\gnarg}{$\aleph_8$}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\bU}{\overline{U}}
\newcommand{\conc}{^\smallfrown}
\newcommand{\lex}{\mathrm{lex}}
\newcommand{\M}{\mathbf{M}}
\renewcommand{\a}{\aleph_0}
\newcommand{\A}{\aleph_1}
\renewcommand{\AA}{\aleph_2}
\newcommand{\AAA}{\aleph_3}
%\newcommand{\pattern}[3]{\framebox{%
%\framebox{\parbox{\gnarg}{$#1$}} \framebox{\parbox{\gnarg}{$#2$}}
%\framebox{\parbox{\gnarg}{$#3$}}}}
\newcommand{\lr}{\mathbf{L}(\mathbb{R})}
\newcommand{\pattern}[3]{\ensuremath{[\,#1\,/\,#2\,/\,#3\,]}}
\newcommand{\Prikry}{P\v{r}\'{\i}kr\'{y}{}}
\newcommand{\cf}{\mathrm{cf}}
%\newcommand{\comment}[1]{\parbox[t]{7cm}{#1}}
%%% Steve's new commands %%%
\newcommand{\ad}{\mathsf{AD}}
\newcommand{\zf}{\mathsf{ZF}}
\newcommand{\dc}{\mathsf{DC}}
\newcommand{\ww}{{\omega^\omega}}
\newcommand{\sca}{\mathrm{Scale}}
\newcommand{\red}{\mathrm{Red}}
\newcommand{\sep}{\mathrm{Sep}}
\newcommand{\bg}{\boldsymbol{\Gamma}}
\newcommand{\bd}{\boldsymbol{\Delta}}
\newcommand{\bdto}{(\Bdelta^2_1)^{\mathbf{L}(\mathbb{R})}}
\newcommand{\Bdelta}{\boldsymbol{\delta}}
\newcommand{\bs}{\boldsymbol{\Sigma}}
\newcommand{\bp}{\boldsymbol{\Pi}}
\newcommand{\bgd}{\breve{\boldsymbol{\Gamma}}}
\newcommand{\res}{{\restriction}}
\newcommand{\cof}{\mathrm{cf}}
\newcommand{\on}{\text{On}}
\newcommand{\lh}{\text{lh}}
\newcommand{\ran}{\text{ran}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\pwo}{\text{pwo}}
\newcommand{\dom}{\text{dom}}
\newcommand{\R}{{\omega^\omega}}
\renewcommand{\theta}{\vartheta}
\newcommand{\SCM}{\ZFC+\mathsf{SC{+}M}}
\newcommand{\SC}{\ZFC+\mathsf{SC}}
\newcommand{\MC}{\ZFC+\mathsf{MC}}
\newcommand{\TMC}{\ZFC+\mathsf{2MC}}
\newcommand{\WC}{\ZFC+\mathsf{WC}}
\newcommand{\brf}{\bar{f}}
\newcommand{\brg}{\bar{g}}
\newcommand{\brh}{\bar{h}}
\begin{document}
\title{Cofinality and measurability of the first three uncountable
cardinals}
\author{Arthur W. Apter, Stephen C. Jackson, Benedikt L\"owe}
\thanks{The first author's visits to Amsterdam and the third author's visit to New York were
partially supported by the DFG-NWO
Bilateral Grant (DFG \textsf{KO 1353/5-1}; NWO \textsf{62-630}).
In addition, the first author wishes to acknowledge
the support of various PSC-CUNY and CUNY
Collaborative Incentive grants. The third author would like to thank the
CUNY Graduate Center Mathematics Program for their hospitality and partial financial support during his stay in New York.}
\address[A.\ W.\ Apter]{Department of Mathematics, Baruch College, City
University of New York,
One Bernard Baruch Way, New York, NY 10010, United States of
America;
The CUNY Graduate Center, Mathematics, 365 Fifth Avenue,
New York, NY 10016, United States of America}
\email{awapter@alum.mit.edu}
\urladdr{http://faculty.baruch.cuny.edu/apter}
\address[S.\ C.\ Jackson]{Department of Mathematics, University of North
Texas, P.O.\ Box 311430,
Denton, TX 76203-1430, United States of America}
\email{jackson@unt.edu}
\urladdr{http://www.math.unt.edu/~sjackson}
\address[B.\ L\"owe]{Institute for Logic, Language
and Computation, Universiteit van Amsterdam,
Postbus~94242, 1090 GE Amsterdam, The Netherlands;
Department Mathematik, Universit\"at Hamburg, Bundesstrasse
55,
20146 Hamburg, Germany; Mathematisches Institut, Rheinische
Friedrich-Wil\-helms-Uni\-ver\-si\-t\"at Bonn, Endenicher Allee~60, 53115~Bonn, Germany}
\email{bloewe@science.uva.nl}
\urladdr{http://staff.science.uva.nl/~bloewe}
\date{May 4, 2009 (revised
March 22, 2010)}
%\date{\today}
\subjclass[2000]{Primary 03E02,
03E35, 03E55, 03E60; secondary
03E10, 03E15, 03E25}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\maketitle
\begin{abstract} This paper discusses models of set theory
without the Axiom of Choice. We investigate all possible patterns
of the cofinality function and the distribution of measurability
on the first three uncountable cardinals. The result relies
heavily on a strengthening of an unpublished result of Kechris:
we prove (under $\mathsf{AD}$) that there is a cardinal $\kappa$
such that the triple $(\kappa,\kappa^+,\kappa^{++})$ satisfies
the strong polarized partition property. \end{abstract}
%\tableofcontents
\section{Introduction}\label{sec:intro}
In $\ZFC$, small cardinals such as $\aleph_1$, $\aleph_2$, and
$\aleph_3$ cannot be measurable, as measurability implies strong
inaccessibility; they cannot be singular either, as successor
cardinals are always regular. So, in $\ZFC$, these three
cardinals are non-measurable regular cardinals. But both of the
mentioned results use the Axiom of Choice, and there are many
known situations in set theory where these small cardinals are
either singular or measurable: in the Feferman-L\'{e}vy model,
$\aleph_1$ has countable cofinality
(cf.\ \cite[Example 15.57]{Jech}),
in the model constructed independently by
Jech and Takeuti, $\aleph_1$
is measurable (cf.\ \cite[Theorem 21.16]{Jech}),
and in models of $\mathsf{AD}$, both $\aleph_1$
and $\aleph_2$ are measurable and $\cf(\aleph_3)=\aleph_2$
(cf.\ \cite[Theorem 28.2, Theorem 28.6, and Corollary 28.8]{Kanamori}).
Simple adaptations of the Feferman-L\'{e}vy
and Jech and Takeuti
arguments show that one can also make
$\aleph_2$ or $\aleph_3$ singular or measurable, but is it
possible to control these
properties simultaneously for the three cardinals $\aleph_1$,
$\aleph_2$ and $\aleph_3$?
In this paper, we investigate all possible patterns of
measurability and cofinality for the three mentioned cardinals.
Combinatorially, there are exactly 60 such patterns of which 13 are impossible for trivial
reasons (e.g., if $\aleph_1$ is singular, then $\aleph_2$ cannot have cofinality
$\aleph_1$). In this paper, we prove that the remaining 47 patterns are all
consistent relative to large cardinals.
Our 47 consistency results will be proved by reducing all cases to eight
base cases from which the other patterns can be obtained by standard
methods. Three of the base cases will be proved consistent
by techniques from forcing, and
five of them will require the existence of a model of $\AD$. In particular,
we will be using the existence of a polarized partition property under $\AD$
which generalizes an unpublished theorem of Kechris from the 1980s (cf.\ \cite[p.\
600]{ApterHenle}). This polarized partition property is of independent interest
and its proof will take up the larger part of this paper.
We begin by giving some basic definitions
and terminology
(\S\S\,\ref{subsec:def} and \ref{subsec:AD}).
We then present a proof of
(a slightly stronger version of) Kechris'
result (\S\,\ref{sec:kechris}) and generalize it to higher
exponents (\S\S\,\ref{sec:higherexponents} and \ref{sec:optimal}).
We then move towards our application of
the polarized partition property. We start by listing
some basic tools for
forcing in the $\ZF$ context, some of them using
both polarized and ordinary partition properties, in
\S\S\,\ref{sub:forcing} and \ref{sub:magidor}.
These tools will allow us to reduce the 47 consistent patterns to eight base
cases in \S\,\ref{sec:reducing}. In \S\S\,\ref{sec:2357} and
\ref{sec:PPP}, we prove the consistency of all base cases.
We use consequences of the polarized partition property
established in \S\,\ref{sec:optimal}
in our applications in \S\,\ref{sec:PPP}.
Finally, in \S\,\ref{sec:summary}, we summarize upper and
lower consistency strength bounds of all
60 patterns and discuss open questions.
Our notation is mostly standard. We will make frequent use of coding and
decoding maps on $\omega$ and $\ww$, especially in \S\,\ref{sec:ppp}.
We fix a recursive bijection $i \mapsto (i_0,i_1)$ from $\omega$ to $\omega^2$
and its inverse function $(i,j) \mapsto \langle i,j\rangle$ (and similarly, for $n$-tuples).
For $x\in\ww$, we define $(x)_i(j) := x(\langle i,j\rangle)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% PART I %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Polarized partition properties under determinacy} \label{sec:ppp}
\subsection{Definitions}\label{subsec:def}
Fix a strictly increasing triple $(\kappa_0,\kappa_1,\kappa_2)$ of
cardinals and an ordinal $\delta \leq\kappa_0$. We say a function
$f \colon 3\times\delta \to \on$ is a \textbf{block function} if
$\kappa_{i-1} < f(i,\alpha) < \kappa_i$ for $i\in 3$ (and
$\kappa_{-1} := 0$), and we say it is \textbf{increasing} if
$f(i,\alpha)0$ as usual. This defines the
projective-like
hierarchy. In this case, $\bs^\alpha_0$, $\bp^\alpha_1$, etc.\ have
the prewellordering
property. These classes will be particularly important for the
arguments of
\S\S
\ref{sec:kechris}--\ref{sec:optimal}.
If $\cof(\alpha)>\omega$, the Wadge pair $(\bg, \bgd)$
of rank $\alpha$ is non-selfdual.
By \cite{stcl}, exactly one of $\bg$, $\bgd$, say $\bgd$, has the
separation property, and this class is
closed under $\exists^\R$. If this pointclass is not also closed
under $\forall^\R$ we are in type II if
$\bg$ is not closed under $\vee$ and in type III if $\bg$ is closed under $\vee$.
We call $\bg$ in these cases the \textbf{Steel pointclass} at the
base of the hierarchy.
If $\bg$ is closed under real quantification
then we are in type IV (in this case the projective-like hierarchy
is built up by applying
quantifiers to $\bg \wedge \bgd$). This analysis of the
projective-like hierarchies does not
depend on the scale property, and assumes just $\ad$.
We now specialize to the Suslin cardinals and Suslin pointclasses.
We say the $\lambda$th Suslin cardinal $\kappa_\lambda$ is a limit
Suslin cardinal if
$\lambda$ is a limit ordinal, and otherwise a successor Suslin
cardinal
(so a successor Suslin cardinal may be a limit cardinal).
First we recall that \cite{Ste.Scales} shows that the Suslin
cardinals form a
closed set in $\lr$ (which as we mentioned
above has largest element $\bdto$).
More generally, Steel and Woodin have shown that
the Suslin cardinals are closed below $\Theta$ assuming $\ad^+$, and
closed below their supremum assuming just $\ad$. So we have:
\begin{prop}\label{prop:limit2} If $\lambda$ is a limit ordinal,
then $\kappa_\lambda$ is a limit of Suslin cardinals. \end{prop}
If $\kappa=\kappa_\lambda$ is a limit Suslin cardinal, then
$\bd := \bigcup_{\rho<\kappa} \mathbf{S}(\rho)$ is selfdual and closed
under
$\wedge$, $\exists^\R$, and so $\o(\bd) \in D$. As discussed above,
$\bd$
sits at the base of a projective-like hierarchy in one of four
possible types.
In \cite{Ste.Scales}, Steel identifies the pointclasses
$\mathbf{S}(\kappa)$ among the $\bs^1_\alpha$ and $\bp^1_\alpha$
and in fact determines the scaled L\'{e}vy classes
among the $\bs^1_\alpha$, $\bp^1_\alpha$ (assuming $\mathbf{V}{=}\lr$).
We recall some of the consequences in terms of the possible
hierarchy types. In all cases, $\kappa=\o(\bd)=\delta(\bd)$.
\begin{description}
\item[Type I] In this case $\cof(\kappa)=\cof(\lambda)=\omega$.
If we let, as above, $\bs^\alpha_0$ (where $\alpha=\o(\bd)=\kappa$)
be the collection of countable unions
of sets in $\bd$, then $\bs^\alpha_0$, $\bp^\alpha_1$, etc.\ have
the scale
property. $\kappa^+$ is a Suslin cardinal, and a
$\bp^\alpha_1$ scale on a $\bp^\alpha_1$-complete set
has norms of length $\kappa^+$. We have
$\mathbf{S}(\kappa)=\bs^\alpha_1$ and
$\mathbf{S}(\kappa^+)=\bs^\alpha_2$.
\item[Type II or III] In this case, let $\bg$ be the Steel class
defined above. So, $\bd=\bg \cap \bgd$, and $\bg$ is closed under
$\wedge$, $\forall^\R$. Then $\mathbf{S}(\kappa)=\exists^\R \bg$,
and
$\sca(\bg)$, $\sca(\mathbf{S}(\kappa))$ hold.
\item[Type IV] In this case, the pointclasses $\bg$, $\bgd$ of
Wadge degree $\kappa$
are closed under real quantification. Let $\bg$ be such that $\bgd$
has the separation property.
Then $\sca(\bg)$, and $\mathbf{S}(\kappa)= \bg$.
\end{description}
If $\kappa$ is a regular limit Suslin cardinal, then \cite[Theorem
2.1]{stcl}
shows that $\bg$ (as in the above hierarchy descriptions) is closed
under
$\vee$. Thus, we are in type III or IV. Finally, the analysis of
\cite[Theorem 4.3]{Ste.Scales} shows that a successor Suslin
cardinal is either a successor
cardinal or has cofinality $\omega$. Thus, a weakly inaccessible
Suslin cardinal $\kappa_\lambda$ must be a limit Suslin cardinal
(and so $\lambda=\kappa$).
Summarizing, our inaccessible Suslin cardinal $\kappa$ is a
limit of Suslin cardinals, and $\mathbf{S}(\kappa)$ has the scale
property. In fact, $\mathbf{S}(\kappa)=\exists^\ww \bg$, where
$\bg$ is a non-selfdual pointclass with $\o(\bg)=\kappa$, $\bg$ is
closed
under $\forall^\ww$, $\wedge$, $\vee$, and
$\sca(\bg)$. It is possible that $\bg=\mathbf{S}(\kappa)$ if we
are in the case of a Type IV hierarchy. We again note that these
results
can be obtained from just $\ad$ (cf.\ \cite{Ja.Hand}).
We fix a $\bg$-complete
set $P$ (which exists by Wadge's Lemma for all non-selfdual
pointclasses under $\ad$) and let $\{ \varphi_n\}_{n \in \omega}$
be a (regular) $\bg$-scale on $P$. An inspection of the standard
argument shows that we have the following boundedness condition
(as $\bg$ is a boldface pointclass with the prewellordering
property and closed under $\forall^\ww$ and finite unions): any
$\bd=\bg \cap \bgd$ subset $A$ of $P$ is bounded in the codes,
that is, $\sup \{ \varphi_x(x) \,;\, n \in \omega, x \in
A\}<\kappa$.
Our results from \S\S \ref{sec:higherexponents} and
\ref{sec:optimal} have to be understood in the context of proofs
of partition properties for $\delta(\bd)$ for highly closed
pointclasses. For instance, consider the following example theorem
as listed in \cite[Theorem 3.10]{Ja.Cabal}:
\begin{thm}\label{thm:example} Let $\bg$ be non-selfdual, closed
under $\forall^\R$ and finite unions, and with the
prewellordering property. Define $\bd := \bg\cap\bgd$. If
$\exists^\R\bd\subseteq\bd$, then $\delta(\bd)$ has the strong
partition property. \end{thm}
Note that if $\kappa$ is an inaccessible Suslin cardinal and
$\bg$ is the pointclass defined as above, then $\bg$ satisfies
all of the requirements of Theorem \ref{thm:example}, and
therefore $\delta(\bd) = \kappa$ has the strong partition
property. Our results are extensions of this observation.
The fact that $\kappa$ has the strong partition property immediately
implies that
the $\omega$-cofinal measure
$\mu:=\mathcal{C}^\omega_\kappa$ on $\kappa$ is a normal ultrafilter
(cf.\ %\cite[Theorem 28.10]{Kanamori}).
\cite[Theorem 2.1]{Kleinberg}).
Finally, we recall one more result, due to Martin (cf.\
\cite[Theorem~3.7]{ADProj})
in the $\ad$ theory of pointclasses which will be used frequently
later.
For the sake of completeness, we sketch the proof.
\begin{thm}[Martin] \label{martinunion}
Let $\bg$ be a non-selfdual pointclass closed under $\forall^\ww$,
$\wedge$, $\vee$,
and assume $\pwo(\bg)$. Let $\delta=\delta(\bd)$ (where $\bd=\bg
\cap \bgd$).
Then $\bd$ is closed under unions and intersections of length
$<\delta$.
\end{thm}
\begin{proof}
Assume the contrary, and let $\rho<\delta$ be least such that some
$\rho$ union, say $A=\bigcup_{\alpha<\rho} A_\alpha$, of sets in $\bd$ that is not in $\bd$.
Easily, $\rho$ is regular. We may assume the $A_\alpha$ are strictly
increasing.
Since $\rho<\delta$, there is a $\bd$-prewellordering of length
$\rho$. The coding lemma then shows that $A \in \bgd$
(since $\bgd$ is closed under $\exists^\ww$). By assumption,
$A \in \bgd-\bd$. Define a norm $\varphi$ of length $\rho$ on $A$ by
$\rho(x)=$ least $\alpha$ such that $x \in A_\alpha$.
To
see that $\varphi$ is a $\bgd$-norm, notice that the corresponding
norm relation $<^*$ can be written as $x <^* y \leftrightarrow
\exists \alpha < \rho\ (x \in A_\alpha \wedge y \notin A_\alpha)$,
a $\rho$-union of $\bd$ sets which is therefore in $\bgd$.
A similar computation works for $\leq^*$, showing
$\varphi$
is a $\bgd$-prewellordering on $A$.
This shows that $\bgd$ has the prewellordering property since $A$ is
$\bgd$-complete and so every $\bgd$ set is a $\rho$-union of $\bd$ sets.
This is a contradiction
since for pointclasses $\bg_0$ closed under $\wedge$, $\vee$ we have
the chain of implications
$\pwo(\bg_0) \Rightarrow \red(\bg_0) \Rightarrow \sep(\bgd_0)$ and
the separation
property cannot hold on both sides of a non-selfdual pointclass.
\end{proof}
\subsection{Kechris' Theorem}\label{sec:kechris}
In this section, we shall prove Kechris' theorem, announced in
the 1980s, but not published. The proofs of our extensions of
this theorem in \S\S \ref{sec:higherexponents} and
\ref{sec:optimal} build on this proof and will use definitions
from this section.
\begin{thm} \label{mta}\label{thm:kechris} Assume $\ad$ and
let $\kappa$ be a weakly inaccessible Suslin cardinal. Then for all
$\theta < \omega_1$ we have $(\kappa, \kappa^+,\kappa^{++})
\rightarrow (\kappa, \kappa^+,\kappa^{++}) ^\theta$.
\end{thm}
Throughout this section, $\kappa$ will be a weakly inaccessible
Suslin
cardinal (which exists by Proposition~\ref{prop:inaccs}). Note that by Fact~\ref{equiv} it doesn't matter whether
we are using the standard or the c.u.b.\ version of the partition
property, and we shall freely switch between them.
Partition property proofs under $\ad$ always follow the same lines
as developed by Tony Martin
(cf. \cite[Lemma 11.1]{ADProj} and \cite[Theorem 2.3.4]{Ja.Hand}):
to show $\kappa \rightarrow \kappa^\lambda$ we must find a
sufficiently good coding of the functions
$f \colon \lambda \to \kappa$. This involves identifying a L\'{e}vy
pointclass $\bg$
and a coding map $\varphi \colon \R \to \sP(\lambda \times \kappa)$
with certain
coding relations being in $\bd$. In this paper we shall use Martin's
method directly,
so the reader need not be familiar with these general results.
In our setting, $\bg$ is the (Steel) pointclass forming the lowest
level of the projective-like
hierarchy containing $\mathbf{S}(\kappa)$. We have seen in \S\ref{subsec:AD} that this
pointclass has the
required properties:
$\mathbf{S}(\kappa) = \exists^\R\bg$ has the scale property. The
pointclass $\bg$ (possibly $\bg = \mathbf{S}(\kappa)$) is scaled,
non-selfdual, closed under $\forall^\ww$ and finite intersections
and unions. We fixed a $\bg$-complete set $P$ and a regular
$\bg$-scale $\{ \varphi_n\}_{n \in \omega}$ on $P$ which allows
boundedness arguments. In the following, $P$ and $\varphi$ will be
used to code ordinals
less than $\kappa$. Since we also want to code higher ordinals, we
shall have to
come up with a means of coding for these (in \S\ref{subsec:coding}).
By $\mu$, we denote the
the $\omega$-cofinal measure on $\kappa$ (which is an ultrafilter by
Theorem \ref{thm:example}).
We shall show that $[\alpha\mapsto\alpha^+]_\mu = \kappa^+$
and that $\delta := [\alpha\mapsto\alpha^{++}]_\mu = \kappa^{++}$.
The first claim can be proved
directly (Lemma \ref{kappap}), after which we shall show the
following auxiliary theorem:
\begin{thm} \label{ce} $(\kappa, \kappa^+,\delta) \rightarrow
(\kappa,\kappa^+,\delta)^\theta$ for all $\theta < \omega_1$.
\end{thm}
It follows immediately from Theorem~\ref{ce} that $\delta
\rightarrow (\delta)^\theta$ for all $\theta < \omega_1$. In
particular, $\delta$ is regular. By showing that $\kappa^+ < \delta
\leq \kappa^{++}$
(Claim \ref{pp}), we establish that $\delta = \kappa^{++}$, thus
proving Theorem \ref{mta}.
\subsubsection{Countable unions of ${<}\alpha$-Suslin sets}
An ordinal $\alpha < \kappa$ is called
\textbf{$\vec\varphi$-strongly reliable} if for all $\beta <
\alpha$, we have $\sup \{ \varphi_n(x) \,;\, n \in \omega \wedge
\varphi_0(x) \leq \beta\} < \alpha$. Let $C \subseteq \kappa$ be
a c.u.b.\ set contained in the $\vec \varphi$-strongly reliable
ordinals. Without loss of generality, we may assume that $C$ is
contained in the Suslin cardinals. The relation $R(x,y)
\leftrightarrow x, y \in P \wedge \varphi_0(x) \leq \varphi_0(y)$
is in $\bg$, and so admits a $\bg$-scale $\vec \sigma$ (with
norms into $\kappa$). By boundedness, we may assume $C$ has the
property that for all $\alpha \in C$ and $\beta < \alpha$, if
$R(x,y)$ and $\varphi_0(x)\leq \varphi_0(y) \leq \beta$, then
$\sup_n \sigma_n(x,y) <\alpha$. Let $C_\omega$ denote the elements
of
$C$ of cofinality $\omega$.
As in \S\ref{subsec:AD}, for $\alpha \in C_\omega$, let
$\bs^\alpha_0$
denote the pointclass of countable unions of sets which are in
$\bigcup\{\mathbf{S}(\beta)\,;\,\beta < \alpha\}$. Thus,
$\sca(\bs^\alpha_0)$. Define $\bs^\alpha_n$, $\bp^\alpha_n$ from
$\bs^\alpha_0$ as usual. Then $\sca(\bp^\alpha_1)$, and
$\bs^\alpha_1$ is the pointclass of $\alpha$-Suslin sets. From
the Coding Lemma and the Kunen-Martin Theorem \ref{thm:KM} it
follows that $\alpha^+$ is the supremum of the lengths of the
$\bs^\alpha_1$ prewellorderings, and is the supremum of the
lengths of the $\bs^\alpha_1$ wellfounded relations. In
particular, $\alpha^+$ is regular.
The pointclass $\bs^\alpha_1$ behaves sufficiently similar to
$\bs^1_1$ to allow
proving the following result (by essentially the same argument as is
used in the
countable partition property of $\aleph_1$, cf.\ \cite[Theorem
11.2]{ADProj}):
\begin{thm}\label{thm:ppalpha}
For all $\theta < \omega_1$, we have $\alpha^+ \rightarrow
(\alpha^+)^\theta$.
\end{thm}
Applying %\cite[Theorem 28.10]{Kanamori}
\cite[Theorem 2.1]{Kleinberg}
again, we get that the
$\omega$-cofinal normal
measure $\mu_\alpha := \mathcal{C}^\omega_{\alpha^+}$ on $\alpha^+$
is an ultrafilter. We shall use this
measure in Lemma \ref{localpp} and its proof.
\medskip
As we shall need to do arguments about $\alpha$ uniformly, we check
in the next result that
the assignment of scales and universal sets is uniform:
\begin{lemma} \label{unif} There is a function $\alpha \mapsto
(A^\alpha, \vec \rho^\alpha)$ which assigns to each $\alpha \in
C_\omega$ a universal $\bs^\alpha_0$ set
$A^\alpha$ and a $\bs^\alpha_0$ scale $\vec \rho^\alpha=\{
\rho^\alpha_n\}_{n \in \omega}$ on $A^\alpha$ with norms into
$\alpha$. Furthermore, there is a function $\alpha \mapsto
(B^\alpha$, $V^\alpha)$ which assigns to such $\alpha$ a
universal $\bs^\alpha_1$ set $B^\alpha$ and a tree $V^\alpha$ on
$\omega \times \alpha$ with $B^\alpha=\mathrm{p}[V^\alpha]$.
Finally,
there is a function $\alpha \mapsto (Q^\alpha, \vec{\psi}^\alpha)$
which assigns to such $\alpha$ a universal $\bp^\alpha_1$ set and a
$\bp^\alpha_1$-scale $\vec{\psi}$ on $Q^\alpha$.
\end{lemma}
\begin{proof} For $\alpha \in C_\omega$ let
$R^\alpha= \{ \langle x,y\rangle \,;\, x, y \in P \wedge
\varphi_0(x) \leq \varphi_0(y)<\alpha\}$. From the definition of
$C$, $R^\alpha$ can be written as an $\alpha$ union of sets each
of which is ${<}\alpha$-Suslin. Thus, $R^\alpha \in \bs^\alpha_0$.
Since $R^\alpha$ is a prewellordering of length $\alpha$, it
cannot be ${<}\alpha$-Suslin. Define $A^\alpha=\{ \langle \tau,
z\rangle \,;\,
\exists n ( (\tau(z))_n \in R^\alpha)\}$, where we view every real
$\tau$
as a strategy for player II in an integer game in some standard manner, and
$\tau(z)$
is the result of applying $\tau$ to $z$. Clearly $A^\alpha \in
\bs^\alpha_0$. Moreover, since $R^\alpha$ has Wadge degree at
least $\alpha$, it follows easily that $A^\alpha$ is
$\bs^\alpha_0$-universal. We define, uniformly in $\alpha$, a tree
$U^\alpha$ with $A^\alpha=\mathrm{p}[U^\alpha]$. Define
$(s,(\alpha_0, \dots,\alpha_n)) \in U^\alpha$ if and only if
\begin{enumerate}
\item \label{p1} $\alpha_0 > \max \{ \alpha_1, \dots,
\alpha_m\}$, and $\alpha_0 <\alpha$.
\item $\alpha_1 \in \omega$
\item There is a $\langle \tau, z\rangle \in \ww$ extending $s$ such
that if
$(\tau(z))_{\alpha_1}=\langle x,y \rangle$, then
$\sigma_i(x,y)=\alpha_{i+2}$ for all $ i \leq n-2$ ($\vec \sigma$
is the scale on $R$ as above). \end{enumerate}
From the closure properties of $C$ it follows that
$A^\alpha=\mathrm{p}[U^\alpha]$. Let then $\{ \bar{\rho}^\alpha_n\}$
be the semi-scale derived from the Suslin representation $U^\alpha$,
and let $\{ \rho^\alpha_n\}$ be the corresponding scale.
Since each $\bar{\rho}^\alpha_n$ maps into $\alpha$,
so does $\rho^\alpha_n$, using property~(i) in the
definition of $U_\alpha$ [In passing from the semi-scale to the
scale
we can take $\rho^\alpha_n(w)= |(\bar{\rho}^\alpha_0(w),\dots,
\bar{\rho}^\alpha_n(w))|_\prec$,
where $\prec$ is lexicographic ordering on the set on $n+1$ tuples
satisfying (i).]
To see that $\vec \rho^\alpha$ is a
$\bs^\alpha_0$-scale, it is enough to show that the semi-scale
$\{ \bar {\rho}^\alpha_n\}$ is a $\bs^\alpha_0$ semi-scale, since
$\bs^\alpha_0$ is closed under $\wedge, \vee$.
However, each of
the norm relations $<^*_n$, $\leq^*_n$ corresponding to the norm
$\bar{\rho}^\alpha_n$ can be written a an $\alpha$ union of
${<}\alpha$-Suslin
sets. For example, for $<^*_0$ we have: $z <^*_0 w$ if and only if there is a
$\beta<\alpha$ such that
$(U^\alpha\res \beta)_{z} \text{ is ill-founded}$ and
$(U^\alpha \res \beta)_{w} \text{ is wellfounded}$. Since
$U^\alpha\res \beta$ and its complement are ${<}\alpha$-Suslin
(since $\alpha$ is a
limit of Suslin cardinals), the claim follows.
Define $B^\alpha$ by $B^\alpha(\langle \tau,z\rangle)$ if and only
if there is a $w$ such that for all $n$,
we have $R^\alpha (\tau(z,w,n))$. Since
$\bs^\alpha_1$ is closed under $\exists^\ww$ and countable unions
and intersections, $B^\alpha \in \bs^\alpha_1$. Since
$R^\alpha$ has Wadge degree at least $\alpha$, it is easy to check
that $B^\alpha$
is universal for $\bs^\alpha_1$.
The tree $U^\alpha$ projecting
to $A^\alpha$ easily gives a tree $V^\alpha$
projecting to $B^\alpha$
(as in the proof
that Suslin representations are closed under $\exists^\ww$ and
$\forall^\omega$). Finally, we can define $Q^\alpha$ by
$Q^\alpha(w)$ if and only if for all $z$, we have $A^\alpha(\langle w,z
\rangle)$,
and use periodicity to transfer the $\bs^\alpha_0$ scale on
$A^\alpha$ to a
$\bp^\alpha_1$ scale on $Q^\alpha$.
\end{proof}
\subsubsection{Coding of ordinals below $\kappa$, $\kappa^+$ and
$\delta$}\label{subsec:coding}
The coding of elements of $\kappa$ is completely standard:
A real $x$ will
code an ordinal below $\kappa$ if and only if $x \in P$. In this case, $x$
codes the ordinal $|x|=\varphi_0(x)$. We let $P_0=P$ be the set
of codes of ordinals below $\kappa$.
In order to code ordinals less than $\kappa^+$, we need a tree
$T^+$ on $\omega \times \kappa$ which we
shall use in our coding of the ordinals. For the definition of
$T^+$, we need a number of
auxiliary objects: $W$, $T_2$, and $U$.
Let $W=\{ w \in \ww\,;\,\forall n\ (w)_n \in P\}$. Define the
norm $\psi$ on $W$ by $\psi(w)=
\sup\{\varphi_0((w)_n)\,;\,n\in\omega\}$. It is easy to see that
$\psi$ is a $\bg$-norm on the set $W\in\bg$. If we define a tree
$T_2$ on $\omega \times \kappa$ by $(s, (\alpha_0, \dots,
\alpha_n)) \in T_2$ if and only if there is a $w$ extending $s$ such that
$$w \in W\mbox{ and for all $i \leq n$, we have }
(\varphi_{i_0}((w)_{i_1})=\alpha_i)\mbox{,}$$ then
$\mathrm{p}[T_2]=W$. For $\alpha \in C$ with
$\cof(\alpha)=\omega$ we also have that $\mathrm{p}[T_2 \res
\alpha]=W_\alpha := \{ w \in W\,;\,\psi(w) \leq \alpha\}$.
Furthermore, we define a tree $U$ on $(\omega)^4 \times \kappa
\times \kappa$
as follows (we recycle the notation here; $U$ has nothing to do
with the trees
$U^\alpha$ above). As a motivation, it is helpful to think of the
first two coordinates of
$U$ in the definition that follows as defining reals $x,y$ with $x
\in W$ and $y$ defining a $\bs^{\psi(x)}_1$ relation via the
universal set $B^{\psi(x)}$ from Lemma~\ref{unif}. Define
$(s,t,u,v,\vec \alpha, \vec \beta) \in U$ if and only if there are $x,y,z,w \in
\ww$ extending $s,t,u,v$ such that:
\begin{enumerate}
\item
$z$ codes the reals $z_0, z_1, \dots$, $w$ codes $w_0, w_1, \dots$,
and for each $i,n \in \omega$ the subsequence
$\gamma_j=\alpha_{\langle i,n,j\rangle}$ of the $\vec \alpha$
satisfies the following. View $y$ as coding a Lipschitz integer
strategy for player II, and set $r_i=\langle y(\langle z_i,
z_{i+1}\rangle), w_i \rangle$.
Let $b=(r_i)_n$. Then $(b, \vec \gamma)\in [T_{\vec \sigma}]$, where
$T_{\vec \sigma}$ is the tree of the scale $\vec \sigma$ on $R$.
\item
For each $i,n \in \omega$ we have (using the notation immediately
above) if $\delta_j=\beta_{\langle i,n,j\rangle}$ then $\delta_0\in
\omega$ and $(\langle (b)_1, x_{\delta_0} \rangle, \vec \delta' )
\in [T_{\vec \sigma}]$, where $\vec \delta'=(\delta_1, \delta_2,
\dots)$.
\end{enumerate}
Let us explain the idea behind the definition of $U$:
the objects $w$, $\vec \alpha$, $\vec \beta$ are
attempting to witness that the $z_0, z_1, \dots$ form a decreasing
sequence in the $\bs^{\psi(x)}_1$ relation coded by $y$, as in the
proof of the Kunen-Martin Theorem \ref{thm:KM}. The relation coded
by $y$ is the
set of $(c,d)$ such that there is a $w$ such that for all $n$, we have
$\langle y(\langle c,d\rangle),w\rangle_n =
(e,f) \in R^{\psi(x)}$ (where $R$ is as in the
proof of Lemma~\ref{unif}). The ordinals $\vec \beta$ witness that
the various $f$ reals satisfy $\varphi_0(f)<\varphi_0((x)_n)$ for
some $n$, and so $(e,f) \in R^{\psi(x)}$.
\begin{lemma} \label{tech}
Suppose that $x \in W$, $\psi(x) \in C$, and $y$ codes a wellfounded
relation $A$ in $\bs^{\psi(x)}_1$. Then $U_{x,y}$ is wellfounded.
Furthermore, $|U_{x,y} \res \psi(x)| \geq |A|$.
\end{lemma}
\begin{proof}
If $(z,w,\vec \alpha, \vec \beta) \in [U_{x,y}]$, then for each $i$,
$A(z_i, z_{i+1})$, where $A$ is the $\bs^{\psi(x)}_1$ relation coded
by $y$: $A(c,d)$ if and only if there is a $w$ such that for all $n$, we have
$\langle y(\langle c,d\rangle),w\rangle_n =
(e,f) \in R^{\psi(x)}$
The $\vec \beta$ witness
that the various $(e,f)$ are in $R^{\psi(x)}$. So, as in the
Kunen-Martin Theorem \ref{thm:KM}, this produces an infinite
decreasing chain
through $A$, a contradiction.
For any $c$, $d$ such that $A(c,d)$, we can find a $w$ such that for
all $n$, if $\langle y(\langle c,d\rangle),w\rangle_n =(e,f)$, then
$\sup_j
\sigma_j(e,f) < \psi(x)$ and $\sup_j \sigma_j(f, x_k)<\psi(x)$ for
any $k$ such that $\varphi_0(x_k)>\varphi_0(f)$. This follows from
the closure properties of $C$ and the fact that $\psi(x) \in C$. The
proof of the Kunen-Martin Theorem \ref{thm:KM} then shows that
$U_{x,y} \res
\psi(x)$ has rank at least $|A|$.
\end{proof}
We note that it is important for the following argument that for
$x,y$ as in the statement of Lemma~\ref{tech} that the entire tree
$U_{x,y}$ is wellfounded (not just $U_{x,y} \res \psi(x)$).
Finally, we can now define the tree $T^+$ on $(\omega)^2 \times
\kappa \times (\omega)^4 \times \kappa \times \kappa$ such that
$(a,b, \vec \gamma, s,t,u,v, \vec \alpha, \vec \beta) \in T^+$ if
and only if $(b, \vec \gamma) \in T_2$, $(s,t,u,v, \vec \alpha,
\vec \beta) \in U$, and there are $\sigma$, $r$, $x$, $y$
extending $a$, $b$, $s$, $t$, respectively, such that $\sigma(r)=\langle
x, y\rangle$. We may identify $T^+$ with a tree on $\omega \times
\kappa$ by identifying the last coordinates with a single
coordinate (i.e., taking a reasonable bijection between $\omega
\times \kappa \times (\omega)^4 \times \kappa \times \kappa$ and
$\kappa$). We furthermore fix a reasonable bijection between
$\kappa$ and $\kappa^{<\omega}$.
We assume (without loss of generality) that our c.u.b.\
set $C$ is closed under both of these bijections.
\medskip
\noindent\textbf{Coding ordinals below $\kappa^+$.} A code for an
ordinal below $\kappa^+$ will be a pair $(x, \sigma)$ where $x\in P$
and thus
codes an ordinal $|x| = \varphi_0(x)$ below $\kappa$, and
$\sigma\in\ww$ such that
$T^+_\sigma$
is wellfounded. Using our bijection between $\kappa$ and
$\kappa^{<\omega}$, we can ask for the
rank of an ordinal $\xi < \kappa$ in the tree $T^+_\sigma$; we write
$|T^+_\sigma(\xi)|$ for this.
Given a pair $(x,\sigma)$, we now consider the map
$f\colon\kappa\to\kappa$ defined by
$\alpha \mapsto |(T^+_\sigma\res \alpha)(|x|)|$. Using the
$\omega$-cofinal normal measure $\mu:=\mathcal{C}^\omega_\kappa$ on
$\kappa$, we now define
$|(x, \sigma)| := [f]_\mu$.
We let $P_1$ be the set of codes of ordinals below $\kappa^+$.
The
next lemma shows that this works.
\begin{lemma} \label{kappap} $\{ |(x, \sigma)|\,;\,(x,\sigma) \in
P_1\} = \kappa^+$. Also, $\kappa^+= [\alpha \mapsto
\alpha^+]_\mu$. \end{lemma}
\begin{proof} Suppose $(x, \sigma) \in P_1$, and let
$f=f_{x,\sigma}$ be given by $f(\alpha)=|T^+_\sigma \res \alpha
(|x|)|$ for all $\alpha >|x|$. If $g \colon \kappa \to \kappa$ is
such that $\forall^*_\mu \alpha\ g(\alpha)
f(\psi(x))$.
Player~I cannot have a winning strategy $\sigma$, for suppose
$\sigma$ were winning for player~I. Note that $\{ (r)_0\,;\, r
\in \sigma[\ww \times \ww] \} \subseteq P_0$. By boundedness, let
$\alpha_0 \in C$ be such that $\alpha_0> \sup \{ |(r)_0|\,;\,r
\in \sigma[\ww \times \ww] \}$. Fix a real $x_0 \in P_0$ with
$|x_0|=\alpha_0$. Note then that $\{ r_1\,;\,r \in \sigma[ \{
(x,y) \,;\, (x)_0=x_0\} \subseteq P_0$. By boundedness, fix
$\alpha_1>\alpha_0$ in $C$ with $\alpha_1>\sup \{ |(r)_1| \,;\, r
\in \sigma[ \{ (x,y) \,;\, (x)_0=x_0\}$. Continuing, we define
$\alpha_i$, and $x_i$ for all $i$. Let $x \in \ww$ be the real
with $(x)_i=x_i$ for all $i$. Let $\alpha=\sup_i \alpha_i$.
Clearly, $\alpha \in C$. By the coding lemma, there is a
$\bs^{\alpha}_1$ wellfounded relation, say coded by the real $y$,
of length greater than $f(\alpha)$. If player~II plays $x$ and
$y$, then player~II defeats $\sigma$, a contradiction.
Let now $\sigma$ be a winning strategy for player~II in $G_f$.
First note that $T^+_\sigma$ is wellfounded. For a branch $(r,\vec
\gamma, x,y,z,w,\vec \alpha, \vec \beta) \in [T^+_\sigma]$ would
give $r \in W$ (witnessed by $\vec \gamma)$ and so $x \in W$ and
$\psi(x) \geq \psi(r)$ as $\sigma(r)=\langle x,y \rangle$ and
$\sigma$ is winning for player~II. Also, $y$ codes a
$\bs^{\psi(x)}_1$ wellfounded relation $A_y$ of rank at least
$f(\psi(x))$. $z$ would however give a decreasing chain in $A_y$,
a contradiction. Next note that there is a c.u.b.\ $D \subseteq
\kappa$ such for all $\alpha \in D$ and $r \in W$ with $\psi(r)=
\alpha$, if $\sigma(r)=\langle x,y\rangle$, then
$\psi(x)=\psi(r)$. This follows by a boundedness argument similar
to the above. We may assume $D \subseteq C$. For $\alpha \in D$
with $\cof(\alpha)=\omega$, let $r \in W$ with $\psi(r)=\alpha$.
If $\sigma(r)=\langle x,y\rangle$, then $w \in W$ and
$\psi(x)=\psi(r)=\alpha$. Thus, $y$ codes a $\bs^\alpha_1$
wellfounded relation $A_y$ of rank at least $f(\alpha)$. From
Lemma~\ref{tech} it follows that $|T^+_\sigma\res \alpha| >
f(\alpha)$. So, $[f]_\mu \leq [\alpha \mapsto |T^+_\sigma \res
\alpha|]_\mu$. It follows that for some $x \in P$ that
$[f]_\mu=|(x,\sigma)|$.
So, $[\alpha \mapsto \alpha^+]_\mu \leq \{ |(x,
\sigma)|\,;\,(x,\sigma) \in
P_1\} \leq \kappa^+$.
\end{proof}
\bigskip
\noindent\textbf{Coding ordinals below $\delta$.} We use a variation
$T^{++}$ of the
tree $T^+$ above. The tree $T^{++}$ will be defined exactly as $T^+$
except we use a
tree $U'$ in place of $U$. In order to define $U'$, we need an
auxiliary tree $V_2$. In Lemma
\ref{lem:V}, we shall construct a tree $V$ which is then refined to
$V_2$ in Lemma
\ref{lem:V2}.
First, recall from Lemma~\ref{unif} that there is
a function $\alpha \mapsto (Q^\alpha, \vec \psi^\alpha)$, for
$\alpha \in C_\omega$, where $Q^\alpha$ is a
universal $\bp^\alpha_1$ set, and $\vec \psi^\alpha$ is a (regular)
$\bp^\alpha_1$-scale on $Q^\alpha$. Note that the norms
$\psi^\alpha_n$ map into $\alpha^+$, since $\alpha^+$ is the
supremum of the lengths of the $\bs^\alpha_1$ wellfounded relations.
We need the following technical lemma.
\begin{lem} \label{lem:cfunction}
There is a continuous function $c \colon \ww \times \ww \to \ww$
such that for all
$x \in W$, $\beta \geq \psi(x)$, and $y \in \ww$ we have
that $c(x,y) \in Q^\beta$
if and only if there is no $z$ such that for all $n$, we have $B^{\psi(x)}(\langle y, \langle z_n,
z_{n+1}\rangle \rangle)$.
Here, $B^{\psi(x)}$ and $Q^\beta$ are as in Lemma~\ref{unif}.
\end{lem}
\begin{proof}
Let $E(x,y)$ if and only if there is no $z$ such that for all $i$, we have
$B^{\psi(x)}(\langle y, \langle z_i, z_{i+1}\rangle\rangle)$. Then:
\begin{equation*}
\begin{split}
E(x,y) & \leftrightarrow \neg \exists z\ \forall i\ \exists w\ \forall n\
R^{\psi(x)}(y( \langle z_i, z_{i+1} \rangle,
w,n)) \\ &
\leftrightarrow \neg \exists u\ \forall m\ R^{\psi(x)}(y(\langle
(u_0)_{m_0}, (u_0)_{m_0+1} \rangle, (u_1)_{m_0}, m_1))
\\ &
\leftrightarrow \neg \exists \langle u,v \rangle \ \forall m\
( R(a,b) \wedge R(b, x_{v(m)})),
\end{split}
\end{equation*}
\noindent
where
\begin{equation*}
\begin{split}
a& = a(y,u,m)=(y(\langle
(u_0)_{m_0}, (u_0)_{m_0+1} \rangle, (u_1)_{m_0}, m_1))_0, \\
b &= b(y,u,m)=(y(\langle
(u_0)_{m_0}, (u_0)_{m_0+1} \rangle, (u_1)_{m_0}, m_1))_1.
\end{split}
\end{equation*}
\noindent
We use here the fact that (for all $j$) $R(a,b) \wedge R(b,x_j)$
holds if and only if $R^{\psi(x)}(a,b)
\wedge R^{\psi(x)}(b,x_j)$ if and only if $R^\beta(a,b) \wedge R^\beta(b,x_j)$.
We therefore have
\begin{equation*}
\begin{split}
E(x,y) & \leftrightarrow
\neg \exists t=\langle u,v \rangle \ \forall m\
( R^\beta(a,b) \wedge R^\beta(b, x_{v(m)})) \\
& \leftrightarrow \neg \exists t\ \forall m\
R^\beta(c_0(x,y)(c_1(x,y), t,m)) \\
& \leftrightarrow Q^\beta(c(x,y))
\end{split}
\end{equation*}
\noindent
where $c(x,y)=\langle c_0(x,y),c_1(x,y)\rangle$ and $c_0$, $c_1$ are
continuous functions such that
$c_0(x,y)$ is a strategy for player II satisfying
$c_0(x,y)(c_1(x,y), t,m)= \langle
a(y,u,\frac{m}{2}),b(y,u,\frac{m}{2}) \rangle$ if $m$ is even and
$c_0(x,y)(c_1(x,y), t,m)= \langle b(y,u,\frac{m-1}{2}), x_{v(m)}
\rangle$ if $m$ is odd.
We may take $c_1(x,y)=\langle x,y\rangle$, and then easily get a
continuous $c_0$
satisfying this equation.
\end{proof}
\begin{lemma}\label{lem:V}
There is a tree $V$ on $\omega \times \omega \times \kappa \times
\kappa$ such that $(x, y) \in \mathrm{p}[V]$ if and only if $x \in W$ and $y$
codes a
$\bs^{\psi(x)}_1$ wellfounded relation. Furthermore, if $x \in W$,
$\psi(x) \in C$, and $y$ codes a wellfounded $\bs^{\psi(x)}_1$
relation, then there is a $\beta < \psi(x)^+$ such that $V_{x,y}
\res \beta$ is illfounded. In fact, for any $\alpha \in C$ with
$\cof(\alpha)=\omega$, and any $A \in \bs^\alpha_1$ consisting of
pairs $(x,y)$ such that $x \in W$, $\psi(x) \leq \alpha$, and $y$
codes a wellfounded $\bs^{\psi(x)}_1$ relation, there is a
$\beta<\alpha^+$ such that $A \subseteq \mathrm{p}[V \res \beta]$.
\end{lemma}
\begin{proof}
Define $(s,t, \vec \alpha, \vec \beta)\in V$ if and only if
\begin{enumerate}
\item
$\beta_0 \in C$ and $\beta_0 > \max \{ \vec \alpha, \vec \beta\}$.
\item
$(s, \vec \alpha) \in T_2$.
\item
There are $x$, $y$ extending $s$, $t$ such that
$\beta_i=\psi^{\beta_0}_i(c(x,y))$ for $1 \leq i < \lh)s)$,
where $\{ \psi^{\beta_0}_i\}$ is the scale on $Q^{\beta_0}$ from
Lemma~\ref{unif}
and $c$ is the continuous function of Lemma~\ref{lem:cfunction}.
\end{enumerate}
It is clear that $V$ has the
desired properties from Lemma~\ref{lem:cfunction}.
For the last property claimed, we use the fact
that $\{ \psi^\alpha_i\}$ is a $\bp^\alpha_1$-scale, and so every
$\bs^\alpha_1$ subset of $Q^\alpha$ is bounded in these norms.
\end{proof}
The next lemma is a small variation of the previous one, allowing
$y$ to code countably many wellfounded relations instead of just
one.
\begin{lemma}\label{lem:V2}
There is a tree $V_2$ on $\omega \times \omega \times \kappa \times
\kappa$ such that $(x, y) \in \mathrm{p}[V]$ if and only if $x \in W$ and for
all $n$,
$(y)_n$ codes a $\bs^{\psi(x)}_1$ wellfounded relation. Furthermore,
for each $\alpha \in C$ with $\cof(\alpha)=\omega$ there
is a c.u.b.\ $D \subseteq
\alpha^+$ such that for all $\gamma \in D$, all $x \in W$ with $\psi(x) \leq \alpha$, and
all $y$ such that for
all $n$,
$| U_{x,(y)_n}\res \alpha|<\gamma$, we have that $(V_2)_{x,y} \res \gamma$ is illfounded.
\end{lemma}
\begin{proof} The tree $V_2$ is constructed as $V$ except that in
(iii) we
require that $\beta_{i}=\psi^{\beta_0}_{i_0}(c(x,(y)_{i_1}))$.
Given $\alpha \in C$ with $\cof(\alpha)=\omega$, define $D
\subseteq \alpha^+$ as follows. For $\beta <\alpha^+$, let
$B_{\alpha,\beta}= \{(x,y) \,;\, x \in W \wedge \psi(x)\leq \alpha
\wedge \forall n\ |U_{x,(y)_n}\res \alpha| \leq \beta \}$.\footnote{Using the set
$B^*_{\alpha,\beta}= \{(x,y) \,;\, x \in W \wedge \psi(x)\leq \alpha
\wedge \forall n\ (y)_n$ codes a $\bs^\alpha_1$ wellfounded relation of length
$\leq \beta\}$ might seem more natural, but it is not clear that this definies a $\bs^\alpha_1$
set.\label{footnoteb*}}
Since $\bd^\alpha_1$ is
closed under ${<}\alpha^+$ unions and intersections (by Theorem~\ref{martinunion}),
it follows that $B_{\alpha,\beta} \in
\bd^\alpha_1$. Let $g(\alpha,\beta)= \sup \{
\psi^\alpha_n(c(x,y)) \,;\, (x,y) \in B_{\alpha,\beta} \}<
\alpha^+$ by boundedness, as in Lemma~\ref{lem:V}. Let $D$ be the c.u.b.\ sets of points
below $\alpha^+$ which are closed under $g$. \end{proof}
We define $(s,t,u, \vec \alpha, \vec \beta, v, a,b, \vec \gamma,
\vec \delta) \in U'$ if and only if there are $x, \tau, w, y, z, w$ extending
$s,t,u,v,a,b$, respectively, such that
\begin{enumerate} \item $(s, u, \vec \alpha, \vec \beta) \in V_2$
\item $\tau(w)=y$
\item $(s, v, a,b,\vec \gamma, \vec \delta) \in U$. Here $U$ is as
in Lemma~\ref{tech}.
\end{enumerate}
We now define the tree $T^{++}$ on $\omega^2 \times \kappa \times
\omega^3 \times \kappa^2 \times \omega^3 \times \kappa^2$ consisting
of tuples
$(c,d, \vec \eta,s,t,u, \vec \alpha, \vec \beta, v, a,b,
\vec \gamma, \vec \delta)$ such that
there are $\sigma, r, x,
\tau$ extending $c,d,s,t$ such that:
\begin{enumerate}
\item
$\sigma(r)=\langle x, \tau \rangle$
\item $(d, \vec \eta) \in T_2$.
\item $(s,t,u, \vec \alpha, \vec \beta, v, a,b, \vec \gamma,
\vec \delta) \in U'$. \end{enumerate}
Let us explain the definition of $T^{++}$:
The first coordinate of the tree $T^{++}$ produces a
strategy $\sigma$. We intend for $\sigma$ to be a strategy such
that when player~I plays $r \in W$, then $\sigma(r)=\langle x,
\tau\rangle$ where $x \in W$ and $\psi(x) \geq \psi(r)$. The object
$\tau$
is also a strategy which we intend to do the following. If player~I
plays a $w$ such that for all $n$, $(w)_n$ codes a
$\bs^{\psi(x)}_1$ wellfounded relation (so $w$ codes the ordinal
$\sup_n \{ |U_{x,(w)_n}\res \psi(x)| \}$),
then $\tau(w)=y$ codes a wellfounded
relation in $\bs^{\psi(x)}_1$. Finally, $T^{++}$ attempts to produce
an infinite decreasing chain in the relation coded by $y$, as in
the Kunen-Martin Theorem \ref{thm:KM}.
For the following result, remember that $\mu_\alpha$ is the
$\omega$-cofinal measure
on $\alpha^+$ which exists by Theorem \ref{thm:ppalpha}.
\begin{lemma} \label{localpp}
For all $\alpha \in C_\omega$ we have
$j_{\mu_\alpha}(\alpha^+)=\alpha^{++}$.
\end{lemma}
\begin{proof}
The proof follows by a Kunen tree argument, as in the proof for the
odd projective ordinals. It is also a special case of the argument
given below. Briefly, define the tree $K$ on $\omega^2 \times
\alpha^+ \times \omega^3 \times \alpha^2$ by: $(s,t, \vec \alpha, u,
v,w, \vec \beta, \vec \gamma) \in K$ if and only if there are $\tau$, $w$, and
$y$
extending $s,t,u$ such that $\tau(w)=y$, $(t, \vec \alpha) \in
\bar{V}$, and $(t,u,v,w, \vec \beta, \vec \gamma) \in U$. Here
$\bar{V}$ is a tree such that $\mathrm{p}[\bar{V}]$ is the set of
$w$ such
that for all $n$, $(w)_n$ codes a $\bs^\alpha_1$ wellfounded
relation, and there is a c.u.b.\ $D \subseteq \alpha^+$ such that
for all $\beta \in D$ there is a $w \in \mathrm{p}[\bar{V} \res \beta]$ such
that for all $n$, $(w)_n$ has rank $|(w)_n| < \beta$ and $\sup_n
|(w)_n|=\beta$ \footnote{Take any $x \in W$ with $\psi(x)=\alpha$
and use the section $\bar{V}=(V_2)_x$. Note that there is a c.u.b.\
$E \subseteq \alpha^+$ such that for $\beta \in E$ and any
$\gamma<\beta$, there is a $w$ such that $|U_{x,w}\res \alpha| <\beta$.
So the distinction of footnote~\ref{footnoteb*} is irrelevant here. \label{footnotecofinal}}
If $F \colon \alpha^+ \to \alpha^+$, consider the game where
player~I
plays out $w$, player~II plays out $y$, and player~II wins
if and only if whenever for all $n$, $(w)_n$ codes a $\bs^\alpha_1$
wellfounded relation, then $y$ codes a $\bs^{\alpha}_1$ wellfounded relation
of length $> f(|w|)$, where $|w|$ is the supremum of the lengths of
the relations coded by the $(w)_n$. By boundedness, player~II has
a winning strategy $\sigma$ for the game. For any $\beta \in D$
with $\cof(\beta)=\omega$ we have $f(\beta)< |\bar{V}_\sigma \res
\beta|$. This shows $[f]_{\mu_\alpha} < \alpha^+$, and so
$j_{\mu_\alpha}(\alpha^+) \leq \alpha^{++}$. The lower bound
follows from the embedding argument given earlier
(the second paragraph of the proof of Lemma~\ref{kappap}).
\end{proof}
\begin{claim} \label{pp}
$[\alpha \mapsto \alpha^{++}]_\mu \leq \kappa^{++}$.
\end{claim}
\begin{proof}
Fix $f \colon \kappa \to \kappa$ such that for all $\alpha$,
$f(\alpha)< \alpha^{++}$. Consider the game $G_f$ defined as follows:
$$\begin{array}{rccccccc}
\mbox{Player~I} & r(0) & & r(1) & & r(2) & &...\\
\mbox{Player~II} & & x(0) & & x(1) & & x(2) & ...\\
& & \tau(0) & & \tau(1) & & \tau(2) & ...
\end{array}$$
If there is a least $i$ such that $(r)_i$ or $(x)_i$ is
not in $P_0$, then player~I wins if and only if $(r)_i \in P_0$. Suppose then
that
$r, x \in W$, that is, for all $n$, $(r)_n \in P_0 \wedge (x)_n
\in P_0$. Let $\alpha=\psi(x) =\sup_n \varphi_0((x)_n)$. Then
player~II wins
provided $\tau$ is a strategy with the following
properties. There is a $g \colon \alpha^+ \to \alpha^+$ such that
if for all $n$, $(w)_n$ codes a $\bs^\alpha_1$
wellfounded relation, then $\tau(w)$ codes a $\bs^\alpha_1$
wellfounded relation of length $> g(\sup_n |U_{x,(w)_n}\res \alpha|)$, and also
$[g]_{\mu_\alpha} \geq f(\alpha)$.
The usual boundedness argument and Lemma~\ref{localpp} (and its
proof) show that player~I cannot have a winning strategy for $G_f$.
Let
$\sigma$ be a winning strategy for player~II in $G_f$. Inspecting
the definition of $T^{++}$ shows that $T^{++}_\sigma$ is
wellfounded.
There is a c.u.b.\ $C_2 \subseteq C$ such that if player~I plays $r
\in
W$ with $\psi(r)=\alpha \in C_2$, then $\sigma(r)=\langle x, \tau
\rangle$ where $x \in W$ and $\psi(x)=\alpha$. Let $\alpha \in
C_2$ with $\cof(\alpha)=\omega$. Fix $r \in W$ with
$\psi(x)=\alpha$, and let $\sigma(r)= \langle x, \tau \rangle$.
Then by Lemma~\ref{lem:V2} and the comment in footnote~\ref{footnotecofinal}
there is a c.u.b.\ $D \subseteq \alpha^+$ such that for
$\beta \in D$ with $\cof(\beta)=\omega$, there is a $w$ such that
for all $n$, $|U_{x,(w)_n}\res \alpha|<\beta$ and we also have
$\sup_n|U_{x,(w)_n}\res \alpha|=\beta$ and
$(V_2)_{x,w} \res \beta$ is
illfounded. Also, for such $\beta$ and $w$, $\tau(w)=y$ codes a
$\bs^\alpha_1$ wellfounded relation of length $>g(\beta)$, where
$[g]_{\mu_\alpha} >f(\alpha)$. It follows that for such $\alpha$
that $[\beta \mapsto T^{++}_\sigma \res \beta]_{\mu_\alpha}
>f(\alpha)$.
From the normality of the measures $\mu_\alpha$ it follows that
if $[f']_\mu < [f]_\mu$, then there is a function $h$ such that
$h(\alpha)<\alpha^+$ and $f'(\alpha)=[\beta \mapsto T^{++}_\sigma
\res
\beta (h(\alpha))|$ for almost all $\alpha$. This shows that
$[f]_\mu$ is a wellordering of $[\alpha \mapsto
\alpha^+]_\mu=\kappa^+$. So, $[f]_\mu < \kappa^{++}$. So, $[\alpha
\mapsto \alpha^{++}]_\mu \leq \kappa^{++}$.
\end{proof}
Let $\delta=[\alpha \mapsto \alpha^{++}]_\mu$. We have shown
$\delta \leq \kappa^{++}$. The lower bound will follow from the
fact that $\delta$ is regular, which follows from the partition
property $\delta \rightarrow (\delta)^\theta$ for $\theta <
\omega_1$ which follows from the polarized partition property we
show below.
\medskip
We are finally in the position to code ordinals below $\delta$. Such a code
is a triple of the form $(x, \sigma_1,
\sigma_2)$, where $x \in P_0$, $T^+_{\sigma_1}$ is wellfounded, and
$T^{++}_{\sigma_2}$ is wellfounded. Let $P_2$ be the set of codes
for
ordinals below $\delta$.
Since $(x, \sigma_1) \in P_1$, it determines a function $h$ with
$h(\alpha) < \alpha^+$ almost everywhere. The triple then codes the
ordinal $[f]_\mu$ where $f(\alpha)=[\beta \mapsto |T^{++}_{\sigma_2}
\res \beta (h(\alpha)| ]_{\mu_\alpha}$.
\begin{lem}Every ordinal below $\delta$ is coded by a triple
in $P_2$.\end{lem}
\begin{proof}
Clear from the proof of Claim~\ref{pp}.\end{proof}
\subsubsection{Proof of Theorem \ref{ce}}
Let
$\sP$ be a partition of the block functions from $3\times \omega
\cdot
\theta$ to $(\kappa,\kappa^+,\delta)$. Fix a bijection $\pi
\colon \omega \cdot \theta\to \omega $. Let $\prec_\pi$ be the
corresponding wellordering of $\omega$.An ordinal $j < \omega \cdot
\theta$
can be identified with a pair $j=(i,n)$ where $i < \theta$ and $n
<\omega$,
using lexicographic ordering on the pairs. We shall frequently pass
back and forth
from this identification.
Consider the following game $G$, where player~I plays out a real
$\langle
x,y,z\rangle$, and player~II plays out the real $\langle x',y',z'
\rangle$. If there is an $j<\omega \cdot \theta$ such that
$(x)_{\pi(j)} \notin P_0$ or
$(x')_{\pi(j)} \notin P_0$, then player~I wins if and only if for the least
such $j$
we have that $(x)_{\pi(j)} \in P_0$. Suppose then that for all $j<
\omega \cdot \theta$,
$(x)_{\pi(j)}$ and $(x')_{\pi(j)}$ are in $P_0$. In this case, $x$
and $x'$ each
determine a function from $\omega \cdot \theta$ to $\kappa$, viz.\
$\bar{F}_x (j) := |(x)_{\pi(j)}|$
and $\bar{F}_{x'}:=|(x')_{\pi(j)}|$, respectively.
So, together they produce a function $F=F_{x,x'} \colon \theta \to
\kappa$ given by
$F(i)= \sup_{n} \max\{ \bar{F}_x(i,n), \bar{F}_{x'}(i,n) \}$.
Suppose next that there is an $\alpha<\kappa$ such that one of the
following holds.
\begin{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}
\item There is a $j< \omega \cdot \theta$ such that either
$T^+_{(y)_{\pi(j)}}
\res \alpha$ or $T^+_{(y')_{\pi(j)}}\res \alpha$ is
illfounded.
\item There is a $\beta < \alpha^+$ and a $j < \omega \cdot
\theta$ such that either $T^{++}_{(z)_{\pi(j)}} \res \beta$
or $T^{++}_{(z')_{\pi(j)}} \res \beta $ is
illfounded.
\end{enumerate}
Let $\alpha<\kappa$ be least such that (a) or (b) above holds.
If (a) holds, let $j$ be least such that (a) holds for $\alpha$ and
this $j$.
In this case, player I wins provided $T^+_{(y)_{\pi(j)}}$ is
wellfounded.
If (a) does not hold at $\alpha$, but (b) does, let $(\beta,j)$ be
lexicographically least
such that (b) holds. Player I wins in this case provided
$T^{++}_{(z)_{\pi(j)}} \res \beta$ is wellfounded.
Suppose finally that neither (a) nor (b) hold for all
$\alpha<\kappa$.
Then each of $y$, $y'$ determine a block function from $(\omega
\cdot \theta) \times \kappa$
to $\kappa$. Namely, for $\alpha \in C$ and $j<\omega \cdot \theta$,
let $\bar{g}_y(
=|T^+_{(y)_{\pi(j)}} \res \alpha|$. Likewise, $y'$ determines the
block function
$\bar{g}_{y'}$. Together, they determine the block function ${g}
\colon \theta \times \kappa \to \kappa$ by
${g}(\alpha,i)=\sup_n \max\{ \bar{g}_y(\alpha, j),
\bar{g}_{y'}(\alpha,j)\}$,
where $j=(i,n)$. Finally, $g$ determines a function $G =G_{y,y'}
\colon \theta \to \kappa^+$
by $G(i)= [\alpha \mapsto g(\alpha,i)]_\mu$.
In a similar fashion, each of $z$, $z'$ determine block functions
$\bar{h}_z$, $\bar{h}_{z'}$.
For $\alpha \in C$, $\beta<\alpha^+$, and $j<\omega \cdot \theta$,
let
$\bar{h}_z(\alpha,\beta,j)=| T^{++}_{(z)_{\pi(j)}} \res \beta|$.
Similarly define
$\bar{h}_{z'}$. Together they determine a block function $h$
defined by:
for $\alpha \in C$, $\beta<\alpha^+$, and $i<\theta$, let
$h(\alpha,\beta,i)=
\sup_n \max\{ \bar{h}_z(\alpha,\beta,j),
\bar{h}_{z'}(\alpha,\beta,j)\}$,
where $j=(i,n)$. Finally, $h$ determines a function $H
=H_{z,z'}\colon \theta \to \delta$
given by $H(i)=[\alpha \mapsto [\beta \mapsto
h(\alpha,\beta,i)]_{\mu_\alpha}]_\mu$.
Finally in this case we say Player~II wins the run of the game if and only if
$\sP(F,G,H)=1$.
Suppose without loss of generality that Player~II has a winning
strategy $\tau$ (the case where player~I has a winning strategy is
slightly easier). We define first a c.u.b.\ set $C_0 \subseteq
\kappa$. For each $\eta<\kappa$ and $j < \omega \cdot \theta$,
let $$A_{\eta,j}=\{ (x,y,z) \,;\, \forall j' \leq j \ (
(x)_{\pi(j')}
\in P_0 \wedge \varphi_0((x)_{\pi(j')}) \leq \eta\}.$$ Clearly
$A_{\eta,j}
\in \bd$ (recall $\bg$ is the Steel pointclass of Wadge rank
$\kappa$).
Since $\tau$ is winning for Player~II, if $(x,y,z) \in
A_{\eta,j}$,
and $\tau(x,y,z)=(x',y',z')$, then for all $j'
\leq j$, we have $((x')_{\pi(j')} \in P_0)$ and by boundedness
$$\rho_0(\eta,j) :=
\sup \{ \varphi_0((x')_{\pi(j')}) \,;\, (x',y',z') \in
\tau[A_{\eta,j}]
\wedge j' \leq j \}<\kappa.$$ Let $C_0 \subseteq C$ be
c.u.b.\ and closed under $\rho_0$.
We next define a c.u.b.\ $C_1 \subseteq \kappa^+$. For $\alpha \in
C_0$ with $\cof(\alpha)=\omega$, $\eta < \alpha^+$, and $j <
\omega \cdot \theta$, let
\begin{equation*}
\begin{split}
A_{\alpha, \eta,j}=&\{ (x,y,z) \,;\,
\forall j\ ( (x)_{\pi(j)} \in P_0 \wedge \varphi_0((x)_{\pi(j)}) <
\alpha)
\\ & \wedge
\forall \alpha' < \alpha\ \forall \beta \ <(\alpha')^+\ \forall j\
(T^+_{(y)_{\pi(j)}} \res \alpha \text{ and }
T^{++}_{(z)_{\pi(j)}} \res \beta \text{ are wellfounded})
\\&
\wedge \forall j' \leq j \ ( |T^+_{(y)_{\pi(j')}} \res \alpha |
\leq \eta ) \}.
\end{split}
\end{equation*}
\noindent Since $\tau$ is winning for player~II, if $(x,y,z) \in
A_{\alpha, \eta, j}$ and $\tau(x,y,z)=(x',y',z')$ then $x' \in W$
and $\varphi_0((x')_{\pi(j)})<\alpha$ for all $j$. Furthermore,
since
$A_{\alpha,\eta, j} \in \bd^\alpha_1$, we have by boundedness
that $$\rho_1(\alpha,\eta,j) := \sup \{ |T^+_{(y')_{\pi(j')}} \res
\alpha | \,;\, j' \leq j \, \wedge (x',y',z') \in
\tau[A_{\alpha,\eta,j}] \} < \alpha^+.$$
Construct (uniformly in $\alpha$) sets $D^\alpha \subseteq \alpha^+$ which are c.u.b.\ and closed
under $(\eta,j)\mapsto \rho_1(\alpha, \eta ,j)$.
Let $E_1 \subseteq \kappa^+$ be the set
of $[f]_\mu$ such that $\forall^*_\mu \alpha\ f(\alpha) \in
D^\alpha$. Let $F_1 \subseteq \kappa^+$ be the set of limit points
of
ordinals of the form $[\alpha \mapsto |T^+_x \res \alpha| ]_\mu$
where
$T^+_x$ is wellfounded. $F_1$ is c.u.b.\ in $\kappa^+$ from
Lemma~\ref{kappap}. Clearly $E_1$ is also c.u.b.\ in $\kappa^+$. Let
$C_1=E_1 \cap F_1$.
Finally, we define a c.u.b.\ $C_2 \subseteq \delta$. For $\alpha
\in C_0$ with $\cof(\alpha)=\omega$, $\beta, \eta < \alpha^+$, and
$j < \omega \cdot \theta$, let
\begin{equation*}
\begin{split}
A_{\alpha, \beta,\eta, j}=& \{ (x,y,z) \,;\, \forall j\ (
(x)_{\pi(j)}
\in P_0 \wedge \varphi_0((x)_{\pi(j)}) < \alpha)
\\ & \wedge
\forall \alpha' < \alpha\ \forall \beta \ <(\alpha')^+\ \forall j\
(T^+_{(y)_{\pi(j)}} \res \alpha \text{ and }
T^{++}_{(z)_{\pi(j)}} \res \beta \text{ are wellfounded})
\\ &
\wedge \forall j \
|T^+_{(y)_{\pi(j)}} \res \alpha| < \beta \wedge
\forall (\beta',j') \leq_\lex (\beta,j) \ (
|T^{++}_{(z)_{\pi(j)}} \res \beta | \leq \eta ) \}.
\end{split}
\end{equation*}
We have $A_{\alpha, \beta, \eta, j} \in \bd^\alpha_1$.
Since $\tau$ is winning for Player~II, for each $(x,y,z) \in
A_{\alpha, \beta, \eta,j}$, if $\tau(x,y,x)= (x',y',z')$ then
$\forall (\beta',j') \leq_\lex (\beta,j)\
T^{++}_{(z')_{\pi(j')}}\res \beta$ is wellfounded. By
boundedness, $$\rho_2(\alpha,\beta,\eta,j) := \sup \{ |
T^{++}_{(z')_{\pi(j')}} \res \beta| \,;\, (x',y',z') \in
\tau[A_{\alpha,\beta,\eta,j}] \wedge j' \leq j \} <
\alpha^+.$$
Let $E^\alpha$ be a c.u.b.\ subset of $\alpha^+$ closed
under $\rho_2$. Let $E^\alpha_2 \subseteq \alpha^{++}$ be the
c.u.b.\ set of all
$[f]_{\mu_\alpha}$ where $\ran(f) \subseteq E^\alpha$. Let $E_2
\subseteq \delta$ be the c.u.b.\ set of all
$[g]_\mu$ where $g(\alpha) \in E^\alpha_2$ for
$\alpha<\kappa$. $E_2$ is c.u.b.\ in $\delta$ from from the
definition of $\delta$. Let $F_2$ be the c.u.b.\ subset of $\delta$
consisting of limits of points of the form $[\alpha \mapsto [ \beta
\mapsto |T^{++}_x \res \beta| ]_{\mu_\alpha} ]_\mu$ where $T^{++}_x$
is
wellfounded. From Claim~\ref{pp}, $F_2$ is c.u.b.\ in $\delta$. Let
$C_2=E_2 \cap F_2$.
Let $C'_0$ be the set of limit points of $C_0$, and likewise for
$C'_1$, $C'_2$. To finish, we show the following.
\begin{claim}\label{cl:claim}
$(C'_0, C'_1, C'_2)$ is homogeneous for $\sP$.
\end{claim}
\begin{numberedproof}{Claim \ref{cl:claim}}
Suppose $(F,G,H)$ is a block function from $3\times \theta$
into $(C'_0,C'_1,C'_2)$ of the correct type (since
$\theta$ is countable, this just means that $F$, $G$, $H$ are
increasing,
discontinuous, and have range in points of cofinality $\omega$).
Let $\bar{F} \colon \omega \cdot \theta \to \kappa$ be increasing
and
induce $F$, that is, $F(i)= \sup_{j < \omega \cdot (i+1)}
\bar{F}(j)$ for all $i <\theta$. Let $x \in \ww$ be such that for
all
$j < \omega \cdot \theta$, $(x)_{\pi(j)} \in P_0$ and
$\varphi_0((x)_{\pi(j)})= \bar{F}(j)$.
Let $\bar{G} \colon \omega \cdot \theta \to \kappa^+$ be increasing
and induce
$G$, that is $G(i)=\sup_{j < \omega \cdot (i+1)} \bar{G}(j)$ for all
$i < \theta$. We may assume $\bar{G}$ has range in $C_1$.
Since $C_1 \subseteq F_1$, for each $j < \omega \cdot \theta$ we may
get a
$y_j \in \ww$ (using countable choice) such that $T^+_{y_j}$ is
wellfounded and
$\bar{G}(j)=[\alpha \mapsto |T^+_{y_j} \res \alpha| ]_\mu$. Let $y
\in \ww$
be such that for all $j<\omega \cdot \theta$ we have
$(y)_{\pi(j)}=y_j$.
Let $\bar{H} \colon \omega \cdot \theta \to \delta$ be increasing
and induce
$H$. We may assume $H$ has range in $C_2$.
Since $C_2 \subseteq F_2$, for each $j<\omega \cdot \theta$ there is
a $z_j \in \ww$
such that $T^{++}_{z_j}$ is wellfounded and
$\bar{H}(j)=[\alpha \mapsto [\beta \mapsto |T^{++}_{z_j} \res \beta|
]_{\mu_\alpha}]_\mu$.
Let $z \in \ww$ be such that for all $j<\omega \cdot \theta$ we have
$(z)_{\pi(j)}=z_j$.
Let $(x',y',z')=\tau(x,y,z)$. Recall we identify
$\omega \cdot \theta$ with lexicographic order on pairs
$(i,n)$ where $i < \theta$ and $n \in \omega$. Since $x \in W$ and
$\tau$ is winning for Player~II, it follows that $x' \in W$ as
well. Let $\bar{F}_{x'} \colon \omega \cdot \theta \to \kappa$ be
the function determined by $x'$, that is,
$\bar{F}_{x'}(j)= |(x')_{\pi(j)}|$. Since $\ran(\bar{F}_x) \subseteq
C_0$, it
follows from the definition of $C_0$ that $\bar{F}_{x'}(i,n) <
\bar{F}_x(i,n+1)
<\bar{F}(i)$ for all $i < \theta$. So, for
each $i< \theta$ we have $\sup_n \max \{ \bar{F}_{x}(i,n),
\bar{F}_{x'}(i,n) \}
= F(i)$. Thus the function $F_{x,x'}$ jointly produced by $x$ and
$x'$ is equal to $F$.
Consider next $y$ and $y'$. For all $j < \omega \cdot \theta$ we
have that
$T^{+}_{(y)_{\pi(j)}}$ and $T^{++}_{(z)_{\pi(j)}}$ are wellfounded.
Let $\alpha_0= \sup_{i < \theta} F(i)=\sup_{j< \omega \cdot \theta}
\bar{F}(j)$.
Let $\bar{g}_y$ be the block function determined by $y$. That is,
for $\alpha \in C_0$ and $j < \omega \cdot \theta$,
$\bar{g}_y(\alpha,j)= | T^{+}_{(y)_{\pi(j)}} \res \alpha|$. For
$\mu$
almost all $\alpha$ the function
$\bar{g}_y^\alpha(j)=\bar{g}_y(\alpha,j)$
is increasing. Let $g_y^\alpha$ be the function induced by
$\bar{g}_y^\alpha$, that is,
$g_y^\alpha(i)= \sup_n \bar{g}_y^\alpha(j)$
where $j=(i,n)$. For $\mu$ almost all $\alpha$, $g_y^\alpha$ has
range in the limit points
of $D^\alpha$ (as defined above in the construction of $C_1$). Say
$M_1 \subseteq C_0$
is this measure one set.
Consider any $\alpha \in M_1$ with $\alpha > \alpha_0$. Then for any
$j < \omega \cdot \theta$
we have that $(x,y,z) \in A_{\alpha,\eta,j}$ where $\eta=
\bar{g}_y^\alpha(j)
< g_y^\alpha(i)$ (where again $j=(i,n)$). It follows from the
definition of $D^\alpha$
that $| T^{+}_{(y')_{\pi(j)}} \res \alpha| \alpha_0$
($\alpha_0$ as above). Fix a c.u.b.\ $C \subseteq \alpha^+$ as with
the two properties
specified immediately above.
Let $\beta \in C$ with $\cof(\beta)=\omega$ and
$\beta > \sup g_y^\alpha(j)$. For such $\beta$, if $j < \omega \cdot
\theta$
and $\eta= h_z^\alpha(\beta,j)$, then from the definition of
$A_{\alpha,\beta,\eta,j}$
we see that $(x,y,z) \in A_{\alpha,\beta,\eta,j}$. From the
definition of $E_2^\alpha$
it follows that $h_{z'}^\alpha(\beta,j) < \sup h_z^\alpha(\beta,j')$
where $j=(i,n)$, and the supremum ranges over $j'=(i,n')$. It
follows that the function $\bar{H}_{z'}$
induces the function $H$, that is, $H=H_{z,z'}$.
Since $\tau$ is winning for Player~II, we have that
$\sP(F,G,H)=1$ and we are done.
\end{numberedproof}
\noindent We have proved the claim, and this finishes the proof of
Theorem~\ref{ce} (and thus the proof of Theorem \ref{mta}).
\subsection{A polarized partition property with higher exponents}
\label{sec:higherexponents}
We now improve Theorem~\ref{mta} from countable exponents to
arbitrary exponents $\theta < \kappa$.
The setup is the same as in the proof of Theorem~\ref{mta}: we have
the (Steel) pointclass $\bg\subseteq\mathbf{S}(\kappa)$ forming the
lowest level of the projective-like
hierarchy containing $\mathbf{S}(\kappa)$
which is scaled,
non-selfdual, closed under $\forall^\ww$ and finite intersections
and unions, and let $\bd = \bg\cap \bgd$.
\begin{thm} \label{mtb}\label{thm:submain} Assume $\ad$. Let
$\kappa$ be a weakly inaccessible Suslin cardinal. Then for all
$\theta
< \kappa$ we have $(\kappa,\kappa^+,\kappa^{++}) \rightarrow
(\kappa,\kappa^+,\kappa^{++})^\theta$. \end{thm}
\begin{proof} We fix $\theta<\kappa$, and fix a prewellordering
${\preceq} \in \bd$ of length $\omega \cdot \theta$. We shall
use the coding lemma to code functions from $\omega \cdot
\theta$ to $\kappa$. We again identify the ordinals below
$\omega \cdot \theta $ with the pairs $(i,n)$ ordered
lexicographically, where $i<\theta$ and $n < \omega$. We shall
also use the trees $T^+$ and $T^{++}$ from the proof of
Theorem~\ref{mta}.
Fix a pointclass $\bg_0\subseteq\bd$
which is non-selfdual, is closed
under $\exists^\ww$, has the prewellordering property, and contains
the
prewellordering $\preceq$. Fix a $\bg_0$-universal set $U$. Without
loss of generality we may assume $\dom(\preceq)=\ww$. Let $|a|$
denote the rank of $a \in \ww$ in $\preceq$.
For $x \in \ww$, we say
$x$ codes a function at $j < \omega \cdot \theta $ provided
\begin{enumerate}
\item
$\forall a \ (|a|=j \rightarrow \exists b\ U(x,a,b))$
\item
$\forall a, a', b, b'\ (U(x,a,b) \wedge U(x,a',b') \wedge |a|=|a'|=j
\rightarrow (b,b' \in P_0 \wedge \varphi_0(b)=\varphi_0(b'))$
\end{enumerate}
\noindent We say $x$ codes a function from $\omega \cdot \theta$
to $\kappa$ (or just say $x$ codes a function) if $x$ codes a
function at $j$ for all $j< \omega \cdot \theta $.
Recall that if $S$ is a tree, we write $S(\gamma)$ to denote the
subtree of $S$
consisting of points in $S$ below $\gamma$ (we are identifying
ordinals with finite tuples here for convenience).
Fix now a partition $\sP$ of the block functions from
$3\times\theta$
to $(\kappa, \kappa^+, \kappa^{++})$. Consider the
game $G$ where player~I plays out the real $\langle
x,y,u,z,v,w\rangle$
and player~II plays out the real $\langle x',y',u',z',v',w'
\rangle$. Suppose first that there is a least $j<\omega \cdot
\theta+$ such that $x$ or $x'$ does not code a function at
$j$. In this case, player~II wins if and only if $x$ does not code a
function at $j$. Suppose next that both $x$ and $x'$ code
functions. If there is a least $j$ such that $y$ or $y'$ does not
code a function at $j$, player~II again wins if and only if $y$ does not
code a function at $j$. Likewise, if all of $x,y,x',y'$ code
functions and there is a least $j$ such that $z$ or $z'$ doesn't
code a function at $j$, player~II wins if and only if $z$ doesn't code a
function at $j$.
Suppose next that $x,y,z,x',y',z'$ all code functions from $\omega
\cdot \theta $ to $\kappa$. We let $\brf_x, \brf_y$, etc.\ denote
these functions. Let $\alpha \in C_\omega$ be the least ordinal, if
it
exists, such that one of the following holds.
\begin{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}
\item There is a $j< \omega \cdot \theta$ such that either $T^+_u
\res \alpha (\brf_y(j))$ or $T^+_{u'}\res \alpha (\brf_{y'}(j))$ is
illfounded.
\item There is a $j< \omega \cdot \theta$ such that either $T^+_v
\res \alpha (\brf_z(j))$ or $T^+_{v'}\res \alpha (\brf_{z'}(j))$ is
illfounded.
\item There is a $\beta < \alpha^+$ and a $j < \omega \cdot
\theta$ such that either $T^{++}_w \res \beta (|T^+_v \res \alpha
(\brf_z(j))|)$ or
$T^{++}_{w'} \res \beta (|T^+_{v'} \res \alpha (\brf_{z'}(j))|)$
is illfounded.
\end{enumerate}
Suppose first such an $\alpha$ exists. If (a) holds, let $j$ be
least such that either $T^+_u \res \alpha (\brf_y(j))$ or
$T^+_{u'}\res
\alpha (\brf_{y'}(j))$ is illfounded. Player~II then wins if and only if
$T^+_u
\res \alpha (\brf_y(j))$ is illfounded. If (a) does not hold, but
(b) holds, then let $j$ be least such that either $T^+_v \res
\alpha (\brf_z(j))$ or $T^+_{v'}\res \alpha (\brf_{z'}(j))$ is
illfounded. Player~II then wins if and only if $T^+_v \res \alpha (\brf_z(j))$
is
illfounded. If (a) and (b) do not holds but (c) holds, then let
$(\beta,j)$ be the lexicographically least pair witnessing (c).
Player~II then wins if and only if $T^{++}_w \res \beta (T^+_v \res \alpha
(\brf_z(j)))$ is illfounded.
Finally, if no such $\alpha$ exists, then let $F=F_{x,x'}$
be the function jointly produced by $\brf_x$ and $\brf_{x'}$. That
is,
$\bar F(i)=\sup_n \max \{ \brf_x(i,n), \brf_{x'}(i,n)\}$ for all $i
<\theta$.
Let $\brg_{y,u}$ be the block function defined as follows.
For $\alpha \in C_\omega$ and $j<\omega \cdot \theta$, let
$\brg_{y,u}(\alpha,j)=| T^+_{u} \res \alpha (f_y(j))|$. Likewise
define $\brg_{y',u'}$ using $y'$ and $u'$. Let $\bar{G}_{y,u}$ be
the function
from $\omega \cdot \theta$ to $\kappa^+$ represented by
$\brg_{y,u}$. That is,
$\bar{G}_{y,u}(j)=[\alpha \mapsto \brg_{y,u}(\alpha,j)]_\mu$.
Likewise define
$\bar{G}_{y',u'}$. Finally, let $G=G_{y,u,y',u'} \colon \theta \to
\kappa^+$
be the function they jointly produce:
$G(i)= \sup_n \max\{ \bar{G}_{y,u}(i,n), \bar{G}_{y',u'}(i,n) \}$.
Let $\brh_{z,v,w}$ be the block function defined as follows.
For $\alpha \in C_\omega$, $\beta < \alpha^+$, and $j<\omega \cdot
\theta$,
let $\brh_{z,v,w}(\alpha,\beta,j)=|T^+_w
\res \beta (|T^+_v \res \alpha (\brf_z(j))|)$. Notice we may write
this as
$\brh_{z,v,w}(\alpha,\beta,j)=|T^+_w \res \beta
(\brg_{z,v}(\alpha,j))|$.
Similarly define
$\brh_{z',v',w'}$ using $z'$, $v'$, $w'$. Let $\bar{H}_{z,v,w}
\colon
\omega \cdot \theta \to \kappa^{++}$ be the function represented by
$\brh_{z,v,w}$. That is,
$\bar{H}_{z,v,w}(j)= [ \alpha \mapsto [\beta \mapsto
\brh_{z,v,w}(\alpha,\beta,j)]_{\mu_\alpha}]_\mu$.
Let $H=H_{z,v,w,z',v',w'} \colon \theta \to \kappa^{++}$
be the function they jointly produce:
$H(i)= \sup_n \max\{ \bar{H}_{z,v,w}(i,n), \bar{H}_{z',v',w'}(i,n)
\}$.
Player~II then wins the run of the game $G$ provided $\sP(F,G,H)=1$.
Suppose without loss of generality that player~II has a winning
strategy $\tau$ for $G$. We define c.u.b.\ sets $C'_0$, $C'_1$,
$C'_2$ in $\kappa$, $\kappa^+$, $\kappa^{++}$ respectively which
are homogeneous for $\sP$. The argument is similar to that of
Theorem~\ref{mta}, so we shall concentrate on the differences.
We first define $C_0$ ($C'_0$ will be the set of limit points of
$C_0$). For each $\eta<\kappa$ and $j < \omega \cdot \theta$,
Let
$$A_{\eta,j}=\{ c=\langle x,y,u,z,v,w\rangle \,;\, \forall j'
\leq j\ ( x \text{ codes a function at } j' \wedge f_x(j') \leq
\eta)
\}.$$
Clearly $A_{\eta,i} \in \bd$. Since $\tau$ is winning for
player~II, if $c \in A_{\eta,i}$, and $\tau(c)=\langle
x',y',u',z',v',w'\rangle$, then for all $j' \leq j$, $f_{x'}$ codes
a function at $j'$. By boundedness,
$$\rho(\eta,j) := \sup \{
f_{x'}(j') \,;\, \langle x',y',u',z',v'\rangle
\in \tau[A_{\eta,j}]
\wedge j' \leq j \}<\kappa.$$
Let $C_0 \subseteq C$ be c.u.b.\ and
closed under $f$.
We next define $C_1$. For $\eta<\kappa$, $\eta \in C_0$, with
$\cof(\eta)>\theta$ (for convenience), $\alpha \in C_\omega$,
$\alpha>\eta$, $j< \omega \cdot \theta$, and $\delta < \alpha^+$,
let
\begin{equation*}
\begin{split}
A_{\eta,\alpha,j,\delta} = & \{ c = \langle x,y,u,z,v \rangle \,;\,
x,y,z \text{ code functions } \wedge (\forall j\ \brf_x(j),
\brf_y(j),\brf_z(j) \leq \eta) \\ & \wedge \forall (\alpha',j')
\leq_{\lex}
(\alpha,j)\ |T^+_u \res \alpha' (\brf_y(j')| \leq \delta
\\ &
\wedge
\forall \alpha' < \alpha\ \forall \beta' < (\alpha')^+\ \forall j'<
\omega \cdot \theta\\ & \qquad T^{++}_w\res \beta' ( |T^+_v \res
\alpha' ( \brf_z(j'))|) \text{ is wellfounded} \}.
\end{split}
\end{equation*}
Let $c'=\langle x',y',u',z',v',w' \rangle =\tau(c)$, where
$c=\langle x,y,u,z,v,w \rangle \in A_{\eta,\alpha,j,\delta}$. From
the second and third conjuncts in the above definition it follows
that the least $\alpha'$ such that (a), (b), or (c) holds for $c$,
$c'$ is at
least $\alpha$. Furthermore, the second conjunct gives that (a) does
not hold at $\alpha$ for all $j' \leq j$. It follows that $T^+_{u'}
\res \alpha' (f_{y'}(j'))$ is wellfounded for all $(\alpha',j')
\leq_{\lex} (\alpha,j)$. For $\eta$, $\alpha$, $j$, $\delta$ as
above, define
\begin{equation*}
\begin{split}
\rho_1(\eta,\alpha,j,\delta)= \sup \{ T^+_{u'} \res \alpha
(f_{y'}(j'))
\,;\, j' \leq j \wedge c'=\langle x',y',u',z',v' \rangle \in
\tau[A_{\eta,\alpha,j,\delta}] \}.
\end{split}
\end{equation*}
\begin{claim} \label{claimba}
$\rho_1(\eta,\alpha,j,\delta)<\alpha^+$.
\end{claim}
\begin{proof}
We define a $\bs^\alpha_1$ wellfounded relation of length at least
$\rho_1(\eta,\alpha,j,\delta)$. Since
$\bs^\alpha_1=\mathbf{S}(\alpha)$, it
then follows that $\rho_1(\eta,\alpha,j,\delta)<\alpha^+$. In
defining
this relation we again for convenience think of the elements of
$T^+$
as ordinals rather than tuples of ordinals. Define a relation $S$ by
letting
\begin{equation*}
\begin{split}
(b,& u,s) S (b',u',s') \leftrightarrow b=b' \wedge u=u' \wedge
\exists c \in A_{\eta, \alpha, j, \delta}\ \exists y\ \exists j'
\leq j\ \exists a\ \\ & [\tau(c)_1=y \wedge \tau(c)_2=u \wedge
|a|=j' \wedge U(y,a,b) \wedge (b \in P_0 \wedge \varphi_0(b) \leq
\eta) \wedge s,s' \in P_0 \\ & \wedge \varphi_0(s),
\varphi_0(s')<\alpha \wedge (\varphi_0(s) <_{T^+_u \res \alpha}
\varphi_0(s') <_{T^+_u \res \alpha} \varphi_0(b)) ]
\end{split}
\end{equation*}
\noindent
where $<_{T^+_u \res \alpha}$ refers to the Kleene-Brouwer
ordering on the tree $T^+_u \res \alpha$. From the above remarks we
have that $S$ is wellfounded.
From the coding lemma, $T^+ \res \alpha$ is $\bs^\alpha_1$ in the
codes
(relative to $P_0 \res \alpha$). Also, $A_{\eta,\alpha,j,\delta} \in
\bd^\alpha_1$ using the closure of $\bd^\alpha_1$ under
${<}\alpha^+$
unions and intersections (for the last conjunct in the definition of
$A_{\eta,\alpha,j,\delta}$ note that if
wellfounded $|T^{++}_w \res \beta' (|T^+_v \res
\alpha'(\brf_z(j'))|)|$
must have rank less that $(\alpha')^+ <\alpha$).
Since also $\eta < \alpha$, it follows that $S \in \bs^\alpha_1$,
and we are done.
\end{proof}
We let $C_1^\alpha$ be the set of ordinals below $\alpha^+$ closed
under the $\rho_1$ function. Let $C_1 \subseteq \kappa^+$ be the set
of $[G]_\mu$ where $G(\alpha) \in C^\alpha_1$ for $\mu$ almost all
$\alpha$.
The definition of $C_2$ is similar to that of $C_1$. For
$\eta<\kappa$, $\eta \in C_0$, with $\cof(\eta)>\theta$, $\alpha
\in C_\omega$, $\alpha>\eta$, $j< \omega \cdot \theta$, and $\beta,
\delta < \alpha^+$, let
\begin{equation*}
\begin{split}
A_{\eta,\alpha,j,\beta, \delta}=& \{ c= \langle x,y,u,z,v,w \rangle
\,;\, x,y,z \text{ code functions } \wedge (\forall j\ \brf_x(j),
\brf_y(j),\brf_z(j) \leq \eta)
\\ & \wedge \forall \alpha' \leq \alpha\ \forall j' < \omega \cdot
\theta\
|T^+_u \res \alpha' (\brf_y(j')| \leq \delta
\\ & \wedge \forall \alpha' \leq \alpha\ \forall j' < \omega \cdot
\theta\
|T^+_v \res \alpha' (\brf_z(j')| \leq \delta
\\ & \wedge
\forall \alpha' < \alpha\ \forall \beta' < (\alpha')^+\ \forall j'<
\omega \cdot \theta \\ & \qquad T^{++}_w\res \beta' ( |T^+_v \res
\alpha' ( \brf_z(j'))|) \text{ is wellfounded } \\ & \wedge \forall
(\beta',j') \leq_{\lex} (\beta, j)\ |T^{++}_w \res \beta' (| T^+_v
\res
\alpha (\brf_z(j'))|)| \leq \delta \}.
\end{split}
\end{equation*}
It again follows that $A_{\eta,\alpha,j,\beta, \delta} \in
\bd^\alpha_1$. Suppose $c' \langle x',y',u',z',v',w' \rangle
=\tau(c)$
where $c=\langle x,y,u,z,v,w
\rangle \in A_{\eta,\alpha,j,\beta, \delta}$.
Since $x,y,z$ all define
functions taking values below $\eta$, and since $\eta \in C_0$ it
follows that $x',y',z'$ also all code functions below $\eta$ (for
$y'$, $z'$ we use also that $\cof (\eta)>\theta$ so that
$\sup(\brf_y)$, $\sup(\brf_z)$ are also below $\eta$). From the
second,
third, and fourth conjuncts in the definition of
$A_{\eta,\alpha,j,\beta, \delta}$ and the fact that $\tau$ is
winning for player~II it follows that the least $\alpha'$ such
that (a), (b), or (c) holds at $\alpha'$ is $\geq \alpha$. Also,
from the second conjunct it follows that (a) cannot hold at
$\alpha$. From the third conjunct it follows that (b) cannot hold
at $\alpha$. From the last conjunct it then follows that for all
$\beta' < \alpha^+$ and $j'$ with $(\beta', j') \leq_{\lex}
(\beta,j)$ that $T^{++}_{w'} \res \beta' (|T^+_{v'} \res \alpha
(\brf_{z'}(j'))| )$ is wellfounded.
For $\eta$, $\alpha$, $\beta$, $j$, $\delta$ as in the
definition of
$A_{\eta,\alpha,j,\beta, \delta}$ define
\begin{equation*}
\begin{split}
\rho_2(\eta,\alpha,\beta, j, \delta)& = \sup \{ |T^{++}_{w'} \res
\beta'
(|T^+_{v'} \res \alpha (\brf_{z'}(j'))| )| \,;\, (\beta',j')
\leq_{\lex}
(\beta,j)
\\ & \wedge c'=\langle x',y',u',z',v' \rangle \in
\tau[A_{\eta,\alpha,\beta, j,\delta}]
\}.
\end{split}
\end{equation*}
\noindent Analogous to Claim~\ref{claimba} we have:
\begin{claim} \label{claimbb}
$\rho_2(\eta,\alpha.\beta. j,\delta)<\alpha^+$.
\end{claim}
\begin{proof}
The proof follows from a computation as in Claim~\ref{claimba},
using the fact that $|\beta|= \alpha$, so $T^{++}\res \beta$ is
isomorphic to a tree on $\alpha$.
\end{proof}
For $\alpha \in C_\omega$, let now $C^\alpha_2$ be the c.u.b.\
subset of
$\alpha^+$ consisting of points closed under the $\rho_2$ function.
Let $D^\alpha \subseteq \alpha^{++}$ be the c.u.b.\ set of ordinals
of the form $[h]_{\mu \alpha}$ where $\ran(h) \subseteq D^\alpha_2$.
Finally, let $C_2 \subseteq \kappa^{++}$ the the c.u.b.\ set of
ordinals of the form $[H]_\mu$ where $H(\alpha) \in D^\alpha$ for
$\mu$ almost all
$\alpha$.
We now show that the c.u.b.\ sets $C'_0$, $C'_1$, $C'_2$ are
homogenous
for the given partition $\sP$. Fix a block function $(F,G,H)$ from
$3\times \theta$ to $(C'_0, C'_1, C'_2)$ of the correct type.
Let $\bar{F}$, $\bar{G}$, $\bar{H}$ from $3\times \omega\cdot
\theta$ to $(\kappa, \kappa^+,
\kappa^{++})$ be increasing and induce $(F,G,H)$.
From the coding lemma, let $x$ be such that $x$ codes a function at
$j$
for all $j < \omega \cdot \theta$ and such that $\brf_x=\bar{F}$.
Since $\kappa^+$ is regular by Theorem~\ref{mta}, $\sup(G)<
\kappa^+$. Let $u$ be such that $T^+_u$ is wellfounded and $[ \alpha
\mapsto |T^+_u\res \alpha|]_\mu > \sup(G)$. Let $\tilde {g} \colon
\omega \cdot \theta \to \kappa$ be defined as follows. For $j <
\omega \cdot \theta$, let $\bar{g}(j)$ be the ordinal less than
$\kappa$ such that $\forall^*_\mu \alpha\ [\alpha \mapsto |T_u\res
\alpha (\bar{g}(j))|]_\mu =\bar{G}(j)$. This is well-defined by the
normality of $\mu$ and the definition of $u$. Let $y$ be such
that $y$ codes the function $\tilde {g}$ (i.e., for all $j<\omega
\cdot \theta$, $y$ codes a function at $j$, and the value coded
at $j$ is $\tilde{g}(j)$).
Since $\kappa^{++}$ is also regular by Theorem~\ref{mta},
$\sup(H) <\kappa^{++}$. From the previous section there is a real
$w$ such that $T^{++}_w$ is wellfounded and such that $[\alpha
\mapsto
[\beta \mapsto |T^{++}_w\res \beta]_{\mu_\alpha}]_\mu > \sup(H)$.
Define a function $\ell \colon \omega \cdot \theta \to \kappa^+$
as follows. For $j < \omega \cdot \theta$, let $\ell(j)<\kappa^+$
be the ordinal represented by $\alpha \mapsto \ell(j,\alpha)$
with respect to $\mu$, where for almost all $\alpha \in C_\omega$ we
have: $$H(j)= [\alpha \mapsto [\beta \mapsto |T^{++}_w \res \beta (
\ell(j,\alpha))|]_{\mu_\alpha}]_\mu.$$ This is well-defined from
the definition of $w$ and the fact that each $\mu_\alpha$ is
normal. Let $z$, $v$ be the reals corresponding to $\ell$ just as
$y$, $u$ correspond to $\bar{g}$. So, $z$ codes a function
$\brf_z$ from $\omega \cdot \theta$ to $\kappa$, and $T^+_v$ is
wellfounded.
Consider the run of the game where player~I plays $c=\langle
x,y,u,z,v,w\rangle$, and player~II responds with
$c'=\tau(c)=\langle x',y',u',z',v',w'\rangle$. Let $\eta$ be the
least point in $C_0$ greater than
$\max\{ \sup(f_x), \sup(f_y), \sup(f_z)\}$ which
has cofinality greater than $\theta$. Since $\brf_x=\bar{F}$ has
range in $C_0$, it follows that $x'$ also codes a function
$\brf_{x'} \colon \omega \cdot \theta \to \kappa$, and the first
function they jointly produce, namely, $$F_{x.x'}(i)=\sup_n \max\{
\brf_x(i,n), \brf_{x'}(i,n)\}$$ is equal to $F$.
Consider now $\alpha > \eta$ in $C_\omega$. For such $\alpha$ and
any $j=(i,n)
<\omega \cdot \theta$, let $\delta= |T^+_u \res \alpha
(\brf_y(j)|<\alpha^+$. An easy argument shows, as in the proof of
the
last section, that there is a $\mu$ measure one set of $\alpha$
such that the map $j \mapsto |T^+_u \res \alpha
(\brf_y(j)|$ is increasing, and we may assume $\alpha$ is in this
set.
By definition we have $c \in A_{\eta,
\alpha, j, \delta}$. Thus, $c' \in
\tau[A_{\eta, \alpha,j, \delta}]$. Hence $T^+_{u'}\res \alpha
(\brf_{y'}(j))$ is wellfounded and $|T^+_{u'}\res \alpha
(\brf_{y'}(j))|
\leq \rho_1(\eta, \alpha, j, \delta)$.
\begin{claim}
For $\mu$ almost all $\alpha$ and all $i <\theta$,
$\sup_n \bar{g}_{y,u}(i,n) \in C^\alpha_1$.
\end{claim}
\begin{proof}
We have $\ran(G) \subseteq
C'_1$. If
for almost all $\alpha$ there is an $i<\theta$ for which this
fails, them by the $\kappa$-completeness of $\mu$ we could fix a
$i$ which witnessed the failure for almost all $\alpha$.
Now, $G(i)=\sup_n \bar{G}(i,n)$ is represented with respect to $\mu$
by the function $\alpha \mapsto \sup_n \bar{g}_{y,u}(\alpha,(i,n))$.
So, for $\mu$ almost all $\alpha$, $\sup_n
\bar{g}_{y,uu}(\alpha,(i,n)) \in (C^\alpha_1)'$.
\end{proof}
It follows that
$\rho_1(\eta,\alpha, j, \delta)< \sup_n
\bar{g}_{y,u}(\alpha,(i,n))=g_{y,u}(\alpha,i)$, where $j=(i,
m)$ for some $m$. Thus, for $\mu$ almost all $\alpha$ we have that
for all
$i<\theta$ that $$\sup_n \max\{ \bar{g}_{y,u}(\alpha,(i,n)),
\bar{g}_{y',u'}(\alpha,(i,n))\}={g}_{y,u}(\alpha,i).$$
It follows that
the second function $G_{y,u,y',u'}$ the players jointly produce is
equal to $G$.
By a similar argument, the third function $H_{z,v,w,z',v',w'}$
they jointly produce is
equal to $H$. Here we consider $\alpha > \eta$ and $\beta <
\alpha^+$ such that $\beta > \sup_j \brg_{y,u}(\alpha,j)$, and
$\beta > \sup_j \brg_{z,v}(\alpha,j)$.
For such $\alpha$, $\beta$ we have that $c \in A_{\eta,
\alpha,j, \beta, \delta}$ where $\delta=
\brh_{z,v,w}(\alpha,\beta,j)$.
We assume here that $\alpha$ is in the $\mu$ measure one set
such that the function $(\beta,j) \mapsto
\brh_{z,v,w}(\alpha,\beta,j)$
is order-preserving when restricted to a c.u.b.\ $C \subseteq
\alpha^+$
(as in the proof of the previous section).
An easy argument as above shows that we may
assume that for $\mu$ almost all $\alpha$, and for $\mu_\alpha$
almost all $\beta$, and all $i <\theta$ that
$\sup_n \brh_{z,v,w}(\alpha,\beta,(i.n))\in C^\alpha_2$.
Thus, $\forall^*_\mu \alpha\ \forall^*_{\mu_\alpha} \beta\
\forall i < \theta\ ( \sup_n \brh_{z',v',w'}(\alpha,\beta,(i,n))=
\sup_n \brh_{z,v,w}(\alpha,.\beta,(i,n)))$.
It follows that $H_{z,v,w,z',v',w'}=H$.
Since $\tau$ is winning for Player~II it follows that
$\sP(F,G,H)=1$, and we are done.
\end{proof}
\subsection{The strong polarized partition property}\label{sec:optimal}
In this section, we now prove the optimal result,
consequences of which will be used
in the applications in \S\ref{sec:PPP}.
\begin{thm}\label{thm:main} Assume $\AD$. Let $\kappa$ be a weakly
inaccessible Suslin cardinal. Then
$(\kappa,\kappa^+,\kappa^{++}) \rightarrow
(\kappa,\kappa^+,\kappa^{++})^{\kappa}$. \end{thm}
The proof of Theorem \ref{thm:main} is again similar to that of
the previous results, and we again use the trees $T^+$ and $T^{++}$
from
before. Let $\sP$ denote the given partition of the block
functions of the correct type from $(\kappa,\kappa,\kappa)$ to
$(\kappa, \kappa^+,\kappa^{++})$.
We now code functions from $\kappa$ to $\kappa$ using the uniform
coding lemma (cf. \linebreak \cite{KKMW}).
% Add exact reference to theorem number in KKMW
Let $U \subseteq \ww \times \ww$ be
universal for
the syntactic class $\bs_1(Q)$ where $Q$ is a binary predicate
symbol. Recall $A \in \bs_1(Q)$ if $A(x) \leftrightarrow A'(x_0,x)
\leftrightarrow \exists y\ (B(x,y) \wedge \forall n\
Q((y)_n))$ where $B \in \bs^1_1$. So, we may define the universal
set $U$ by:
$U_z(x,y)
\leftrightarrow \exists w\ (S(z,\langle x,y \rangle, w) \wedge
\forall n\ Q((w)_n))$, where $S$ is universal for $\bs^1_1$.
Recall $P$ is our $\bg$-complete set, and $\{ \varphi_m\}$ a
$\bg$-scale on $P$ (with norms onto $\kappa$). Let $P_\alpha=\{ x
\in P
\,;\, |x|=\alpha\}$ be the set of codes for $\alpha < \kappa$.
Also, $R$ is the prewellordering on $P$ given by $\varphi_0$, so $R
\in
\bg$. For $\alpha < \kappa$, recall also $R_\alpha = \{ (x,y) \in R
\,;\,
\varphi_0(y)<\alpha\}$ is the restriction of $R$ to reals of norm
less than $\alpha$. Let $R'_\alpha$ be the restriction of $R$ to
reals of norm $\leq \alpha$.
Let $\{ \rho_n\}$ be a $\bg$-scale on $R$, and let $\rho_\alpha$
(or $\rho'_\alpha$) denote its restriction to $R_\alpha$ (or
$R'_\alpha$). For any $\alpha <\kappa$, $\rho_\alpha$ is a
$\bd$-scale on $R_\alpha$ (similarly for $\rho'_\alpha$).
Uniformly in $\alpha$, the scale $\rho'_\alpha$ induces a scale on
$U(R'_\alpha)$. This gives, uniformly in $\alpha,$ a
uniformizing relation
$\bU(R'_\alpha)\in\bd$ (uniformizing on the last coordinate) of
$U(R'_\alpha)$. In fact, $\bU(R'_\alpha)$ is in the projective
hierarchy containing
$R'_\alpha$.
For $\alpha < \kappa$, let $\alpha'<\kappa$
be the least reliable ordinal $\geq \alpha$ (with respect to the
scale $\{ \varphi_n\}$ on $P$). We let $G \colon
\kappa^\omega \to \ww$ be the Lipschitz continuous generic coding
function from the Kechris-Woodin theory of generic codes for
uncountable ordinals (cf.\ \cite{KW:generic} for the theory of
generic codes).
This means $G$ has the following properties.
For all $s \in \kappa^\omega$, $G(s) \in
P$. Also, for all $\alpha <\kappa$, and any $s \in
(\alpha')^\omega$ enumerating an honest set $S \subseteq
\alpha'$, $|G(\alpha \conc s)|=\alpha$. Here (and throughout this
section)
$|z|$ denotes $\varphi_0(z)$.
For $\alpha < \kappa$, we say that comeager many $x \in P_\alpha$
have property $B$ (where $B \subseteq \ww$), written $\forall^* x
\in P_\alpha\ B(x)$, if player~II has a winning strategy in the game
where players I and II play $s_i \in (\alpha')^{<\omega}$ and
player~II wins the run if and only if $G(\alpha \conc s_0 \conc s_1\conc
\cdots) \in B$. If $B$ is Suslin and co-Suslin, then this
game is Suslin and co-Suslin as well, and hence
determined (cf.\ \cite[Theorem~2.5]{KKMW}).
We also write $\forall^* s \in (\alpha')^\omega$
to denote that player~II has a winning strategy in the game where
players I and II play $s_i \in (\alpha')^{<\omega}$ to produce $s=s_0 \conc
s_1 \conc
s_2 \cdots$.
We code functions from $\kappa$ to $\kappa$ using the uniform coding
lemma
as follows.
For any $f \colon \kappa \to \kappa$
there is a real $x$ such that for all $\alpha <\kappa$, the set
$U_x(R_\alpha)$ codes $f \res \alpha$. That is,
$U_x(R_\alpha)(a,b)$ if and only if $\varphi_0(a) < \alpha$, $b \in P$, and
$\varphi_0(b)=f(\varphi_0(a))$. We say $x$ \textbf{codes a
function} at $\alpha$ if $U_x(R'_\alpha)$ satisfies:
\begin{enumerate}
\item For all $a$, $|a|=\alpha$ implies that there is some $b$ with
$U_x(R'_\alpha)(a,b)$.
\item For all $a$, $a'$, $b$, and $b'$, we have that
$(U_x(R'_\alpha)(a,b) \wedge
U_z(R'_\alpha)(a',b') \wedge |a|=|a'|=\alpha \rightarrow
|b|=|b'|)$ holds.
\end{enumerate}
We code functions from $\kappa$ to $\kappa^+$ as follows. Given $y
\in \ww $, and given $\delta <\alpha \in C_0$, we say $y$ is good
at $(\delta,\alpha)$ if for comeager many $a \in P_\delta$, there
is a (unique) $b$ such that $\bU_y(R'_\delta)(a,b)$, and for this
$b$ we have that $T^+_b \res \alpha$ is wellfounded. We let
$g_y(\delta,\alpha)$ be
the least ordinal ${<}\alpha^+$ such that for comeager many $a \in
P_\delta$, and $b$ as above, $|T^+_b \res \alpha|\leq
g_y(\delta,\alpha)$. This is welldefined using the fact that
$\cof(\alpha^+)>\omega$ and the additivity of category.
We say $y$ is good at $\alpha \in C_\omega$ if $y$ is good at
$(\delta,\alpha)$ for all $\delta < \alpha$. If $y$ is good at
$\alpha$ for $\mu$ almost all $\alpha \in C_\omega$, then $y$ codes
the
function $G_y \colon \kappa \to \kappa^+$ defined by
$G_y(\delta)=[\alpha \mapsto g_y(\delta, \alpha)]_\mu$.
We code functions from $\kappa$ to $\kappa^{++}$ as follows. Given
$z \in \ww$, $\delta < \alpha \in C_\omega$ and $\beta <\alpha^+$,
we
say $z$ is good at $(\delta, \alpha,\beta)$ if for for comeager
many $a \in P_\delta$, if $\bU_z(R'_\delta)(a,b)$, then $T^{++}_b
\res
\beta$ is wellfounded. We let $h_z(\delta,\alpha,\beta)$ be the
least ordinal $< \alpha^+$ such that for comeager many $a \in
P_\delta$, and $b$ as above, $|T^{++}_b \res \beta| \leq
h_z(\delta,\alpha,\beta)$. We say $z$ is good at $(\alpha,\beta)$
if for all $\delta < \alpha$ we have that $z$ is good at
$(\delta,\alpha,\beta)$. We say $z$ is good at $\alpha$ if for all
$\delta<\alpha$ and all $\beta<\alpha^+$, $z$ is good at
$(\delta,\alpha,\beta)$. If for $\mu$ almost all $\alpha \in
C_\omega$
and $\mu_\alpha$ almost all $\beta < \alpha^+$ we have that $z$ is
good at $(\alpha,\beta)$, then $z$ codes the function $H_z \colon
\kappa \to \kappa^{++}$ given by $$ H_z(\delta)=[\alpha \mapsto
[\beta \mapsto g_z(\delta,\alpha,\beta)]_{\mu_\alpha}]_\mu.$$
Consider the game $G$ where player~I plays out reals $(x,y,z)$
and player~II plays out $(x',y',z')$. Let $\alpha < \kappa$ be
the least ordinal, if one exists, such that one of the following
holds.
\begin{enumerate} \renewcommand{\labelenumi}{(\arabic{enumi})}
\item \label{con1} For
some $\delta < \alpha$ we have that $y$ or $y'$ is not good
$(\delta,\alpha)$.
\item\label{con2} For some $\delta < \alpha$
and $\beta <\alpha^+$ we have that $z$ or $z'$ is not good at
$(\delta,\alpha,\beta)$.
\item \label{con3} $x$ or $x'$ does not code an ordinal at
$\alpha$. \end{enumerate}
Suppose first that an $\alpha <\kappa$ satisfying (\ref{con1}),
(\ref{con2}), or (\ref{con3}) exists, and let $\alpha$ be the
least such. First we check to see if case (\ref{con1}) holds at
$\alpha$. If so, then player~II wins the run if and only if for the least
$\delta$ as in (\ref{con1}) we have that $y$ is not good at
$(\delta,\alpha)$. Suppose next that case (\ref{con1}) does not
hold at $\alpha$. Then we check case to see if case (\ref{con2})
holds at $\alpha$. If so, and if $(\beta,\delta)$ is the
lexicographically least pair as in (\ref{con2}), then player~II
wins the run if and only if $z$ is not good at $(\delta,\alpha,\beta)$.
Suppose next that (\ref{con1}) and (\ref{con2}) do not hold at~$\alpha$, but case~(\ref{con3}) holds. Player~II then wins
provided $x$ does not code an ordinal at~$\alpha$.
Finally, suppose that there is no $\alpha<\kappa$ satisfying
(\ref{con1}), (\ref{con2}), or (\ref{con3}). So, $x$, $x'$, both
code functions $f_x$, $f_{x'}$ from $\kappa$ to $\kappa$. Let $F
\colon \kappa \to \kappa$ be defined from $f_x$ and $f_{x'}$ as
usual, that is, $F(\beta)= \sup_{j< \omega \cdot (\beta+1)} \max\{
f_x(j), f_{x'}(j)\}$. Similarly, $y$ and $y'$ code functions
$G_y$, $G_{y'}$ from $\kappa$ to $\kappa^+$. These determine the
function $G \colon \kappa \to \kappa^+$ in the usual way.
Likewise, $z$ and $z'$ determine $H_z$, $H_{z'} \colon \kappa \to
\kappa^{++}$ which then determine $H \colon \kappa \to
\kappa^{++}$.
Player~II then wins the run of the game if and only if $\sP(F,G,H)=1$.
Suppose without loss of generality that player~II has a winning
strategy $\tau$ for the game, and we define homogeneous sets $C_0
\subseteq \kappa$, $C_1 \subseteq \kappa^+$, and $C_2 \subseteq
\kappa^{++}$.
For $\eta_1, \eta_2<\kappa$, let $A(\eta_1,\eta_2)$ be the set of
$(x,y,z)$ satisfying the following:
\begin{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}
\item $y$ is good at $\alpha$ for all $\alpha \leq \eta_1$.
\item $z$ is good at $\alpha$ for all $\alpha \leq \eta_1$.
\item $x$ codes a function at all $\alpha \leq \eta_1$ and
$f_x(\alpha) \leq \eta_2$.
\end{enumerate}
A straightforward computation using the closure of $\bd$ under
quantifiers shows that $A(\eta_1,\eta_2) \in \bd$. From the
definition of $G$, if $(x,y,z) \in A(\eta_1,\eta_2)$ and
$(x',y',z')=\tau(x,y,z)$, then $x'$ codes a function at all
$\alpha \leq \eta_1$. By boundedness (since $\bg$ is closed under
$\wedge$, $\vee$), it follows that
$$\rho_0(\eta_1,\eta_2) :=
\sup \{ f_{x'}(\alpha)\,;\, \alpha \leq \eta_1 \wedge (x',y',z')
\in \tau [A(\eta_1,\eta_2)]\} < \kappa.$$ Let $C_0 \subseteq \kappa$
be a
c.u.b.\ subset closed under $\rho_0$.
For $\alpha \in C_\omega$, $\delta < \alpha$, and $\eta <\alpha^+$,
Let
$A(\delta, \alpha, \eta)$ be the set of $(x,y,z)$ satisfying:
\begin{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}
\item $y$ and $z$ good at all $\alpha' < \alpha$, and for all
$\alpha'<\alpha$ $x$ codes a function at $\alpha'$ with
$f_{x}(\alpha') <\alpha$.
\item For all $\delta' \leq \delta$, $y$ is good at
$(\delta',\alpha)$ and $g_y(\delta',\alpha) \leq \eta$.
\end{enumerate}
\begin{lem} \label{catcl}
For $\delta < \alpha \in C_\omega$, if $X(x,y) \in \bs^\alpha_1$,
then $X'(x) \leftrightarrow \forall^* s \in (\delta')^\omega\
X(G(s),y)$ is also in $\bs^\alpha_1$.
\end{lem}
\begin{proof}
Write $X(x,y) \leftrightarrow \exists z\ Y(x,y,z)$ where $Y \in
\bp^\alpha_0$.
Fix a non-selfdual pointclass $\bg_0$ closed
under $\exists^\ww$, $\wedge$, $\vee$ contained within
${<}\alpha$-Suslin
and which has prewellorderings of length at least
$\delta'$ (the least reliable $\geq \delta$). Using the coding
lemma, we code strategies on $\delta'$ by reals.
We then have:
\begin{equation*}
\begin{split}
z \in X' & \leftrightarrow
\exists w [ w \text{ codes a strategy $\tau_w \colon (\delta'^{<
\omega})^\omega \to
(\delta'^{< \omega})^\omega \times \ww \times \ww$ }
\\ & \wedge \forall (s,y,z) \text{ a run according to $\tau_w$, }
Y(G(s),y,z) ]
\end{split}
\end{equation*}
Saying $w$ codes a strategy is projective over $\bg_0$,
as is coding a run according to $\tau_w$. Since $Y \in
\bp^\alpha_0$, it follows that $X'$ is $\bs^\alpha_1$.
\end{proof}
\begin{claim} \label{cld} $A(\delta,\alpha,\eta) \in
\bd^\alpha_1$. \end{claim}
\begin{proof}
The set $B=\{ w
\,;\, |T^+_w \res \alpha| \leq \eta\}$ is in $\bd^\alpha_1$.
Since $\bd^\alpha_1$ is closed under ${<}\alpha^+$
unions and intersections (Theorem~\ref{martinunion}),
it is enough to show that
$A'=A'(\delta,\alpha,\eta)$ is $\bd^\alpha_1$, where $$z \in A'
\leftrightarrow
\forall^* a \in P_\delta\ \exists b\ (\bU_z(R'_\delta)(a,b)
\wedge |T^+_b \res \alpha| \leq \delta).$$ It is enough, by a
symmetrical argument,
to show that $A' \in \bs^\alpha_1$.
This follows immediately from Lemma \ref{catcl}.
\end{proof}
If $y \in A(\delta,\alpha,\eta)$ and $y'=\tau(y)$, then $y'$ is
good at $(\delta,\alpha)$. This follows from the winning
conditions for player~II in the game $G$, specifically the fact
that case~(\ref{con1}) is considered at stage $\alpha$ first.
\begin{claim} \label{clb} $\sup \{ g_{y'}(\alpha,\delta) \,;\,
y' \in \tau[A(\delta,\alpha.\eta)]\} < \alpha^+$.
\end{claim}
\begin{numberedproof}{Claim \ref{clb}}The supremum in question has
length bounded by the length of the
following ordering:
\begin{equation*}
\begin{split} y_1 \prec y_2 & \leftrightarrow
(y_1, y_2 \in \tau[A(\delta, \alpha,\eta)]) \wedge \exists s_0 \in
(\delta')^{< \omega}\ \forall^* s_1 \in (\delta')^\omega\ \forall^*
s_2 \in (\delta')^\omega
\\ & \exists b_1, b_2\ (\bU_{y_1}(R'_\delta)(G(s),b_1) \wedge
(\bU_{y_2}(R'_\delta)(G(s_0 \conc s),b_2) \wedge |T^+_{b_1}\res
\alpha| < |T^+_{b_2}\res \alpha|))
\end{split}
\end{equation*}
It follows from Lemma~\ref{catcl}
that ${\preceq} \in \bs^\alpha_1$ provided we show
that there is a $\bs^\alpha_1$ relation $S(b_1,b_2)$ which when
restricted to pairs such that $T^+_{b_1} \res \alpha$ and
$T^+_{b_2} \res \alpha$ are wellfounded correctly
computes the relation $|T^+_{b_1}\res \alpha| \leq |T^+_{b_2}\res
\alpha|$. To see this, let $\bg_n$ be a sequence of non-selfdual
pointclasses closed under $\exists^\ww$, $\wedge$, $\vee$ of
Wadge ranks cofinal in $\alpha$. Let $U_n$ be universal sets for
$\bg_n$. Let $\psi_n$ be a $\bg_n$ prewellordering of length
$\alpha_n$ where $\sup_n \alpha_n=\alpha$. Each real $z$ codes
the relation $R_z \subseteq \alpha \times \alpha$ given by
$R_z=\bigcup_n R_z^n$ where $R_z^n$ is the relation on $\alpha_n$
defined by $(\alpha,\beta) \in R_z^n$ if and only if there are $u$ and $v$ such
that
$\psi_n(u)=\alpha$, $\psi_n(v)=\beta$, and $U_n((z)_n,u,v)$.
From the coding lemma, every relation on $\alpha$ is coded in
this manner by some $z$. We can then say that
$S(b_1,b_2)$ holds if and only if there is a $z$ such that $R_z$ is an
order-preserving map from $T^+_{b_1}\res \alpha$ to
$T^+_{b_1}\res \alpha$. Using the closure of $\bd^\alpha_1$ under
${<}\alpha$ unions and intersections (Theorem~\ref{martinunion}), it
is straightforward to
verify that $S \in \bs^\alpha_1$.
\end{numberedproof}
Let now
$$\rho_1(\delta,\alpha,\eta)= \sup \{ g_{y'}(\alpha,\delta)
\,;\, y' \in \tau[A(\delta,\alpha.\eta)]\}.$$
Let $C'_1(\alpha)$
be the c.u.b.\ subset of $\alpha^+$ of points closed under $\rho_1$.
Let $C'_1=[\alpha \mapsto C'_1(\alpha)]_\mu$, so $C'_1$ is a
c.u.b.\ subset of $\kappa^+$. Let $C''_1$ be a c.u.b.\ subset of
$\kappa^+$ so that between any two elements
$\rho_1=[f]_\mu<[g]_\mu=\rho_2$ of $C''_1$, there is a $b \in \ww$
such that $T^+_b$ is wellfounded and $\forall^*_\mu \alpha\
f(\alpha)< |T^+_b \res \alpha| \sup_{\delta <
\alpha} \{ \bar{g}'(\delta,\alpha)\}$, and for all $\beta'<\beta$
and $\delta <\alpha$, $h_z(\delta,\alpha,\beta') <\beta$. This set
of pairs $A$ has measure one set with respect the iterated measure,
that is, $\forall^*_\mu \alpha\ \forall^*_{\mu_\alpha} \beta\
(\alpha,\beta) \in A$. For $(\alpha,\beta) \in A$, $z$ is in the set
$A(\delta ,\alpha,\beta, \bar{h}'(\delta,\alpha,\beta))$ for all
$\delta < \alpha$. Since $\bar{h}$ has its range in the
$C'_2(\alpha)$, $h_{z'}(\delta,\alpha,\beta)<
\bar{h}(\delta+1,\alpha,\beta)$. Thus, for all $\delta < \omega
\cdot \kappa$, $\bar{H}_z(\delta)$ and $\bar{H}_{z'}(\delta)$ are
both less than $\bar{H}(\delta+1)$. It follows that the function
jointly produced by $z$ and $z'$ is equal to $H$.
Since $\tau$ is winning for player~II, it follows that
$\sP(F,G,H)=1$, and we are done.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% PART II %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Application to choiceless set theory}
As mentioned in \S\,\ref{sec:intro}, our main application and the motivation for
proving Theorem \ref{thm:main} is the determination of the consistent patterns of cofinality and measurabilty for the
first three uncountable cardinals.
We shall use the labels $\mathbf{M}$ and $\aleph_n$, standing for ``measurable'' and ``non-measurable and
cofinality $\aleph_n$'', respectively, and write $$\pattern{\mathsf{x}_1}{\mathsf{x}_2}{\mathsf{x}_3}$$ for the
statement ``$\aleph_1$ has property $\mathsf{x}_1$, $\aleph_2$
has property $\mathsf{x}_2$, and $\aleph_3$ has property
$\mathsf{x}_3$''.
There are exactly 60 ($=3\times 4\times 5$) such
patterns: $\aleph_1$ can be measurable, regular non-measurable,
or singular (3 possibilities); $\aleph_2$ can be measurable,
regular non-measurable, or have cofinality $\aleph_1$ or
$\aleph_0$ (4 possibilities); and $\aleph_3$ can be measurable,
regular non-measurable, or have cofinality $\aleph_2$,
$\aleph_1$, or $\aleph_0$ (5 possibilities).
A pattern
$\pattern{\x_1}{\x_2}{\x_3}$ is called \textbf{trivially
inconsistent} if there are $0\leq k*\omega_1$.
Then the following hold:
\begin{enumerate}
%\item $(\kappa_1,\kappa_2)\to(\kappa_1,\kappa_2)^{\kappa_0}$,
\item $\kappa_i \to (\kappa_i)^{< \kappa_0}$ for $i = 1, 2$
(so $\kappa_i \to (\kappa_i)^{< \omega_1}$ for $i = 1, 2$),
\item $(\kappa_1,\kappa_2)\to(\kappa_1,\kappa_2)^{<\kappa_0}$, and
%\item $\kappa_2 \to (\kappa_2)^{< \kappa_0}$
%(so $\kappa_2 \to (\kappa_2)^{< \omega_1}$), and
\item $\kappa_0 \to (\kappa_0)^{< \omega_1}$.
%For $\gamma = \kappa_0$, $\gamma = \kappa_1$, and
%$\gamma = \kappa_2$, $\gamma \to (\gamma)^{< \omega_1}$.
\end{enumerate}
\end{lem}
\begin{proof}
Since
$(\kappa_0,\kappa_1,\kappa_2)\to(\kappa_0,\kappa_1,\kappa_2)^{\kappa_0}$
and $\kappa_0 > \omega_1$, it is trivially true that
$\kappa_i \to (\kappa_i)^{\kappa_0}$ for $i = 1, 2$,
$(\kappa_1,\kappa_2)\to(\kappa_1,\kappa_2)^{\kappa_0}$,
and $\kappa_0 \to (\kappa_0)^{\omega_1}$.
Claims (i)--(iii) now
follow from \cite[Proposition 4.10]{AHJ}. \end{proof}
%follows by the
%standard methods developed by Kleinberg for the standard
%partition relations \cite[Lemmas 1.3 and 1.4]{Kleinberg} that
%easily transfer to the polarized case (as mentioned in \cite[Facts
%4.3 through 4.7]{AHJ}):
%$(\kappa_1,\kappa_2)\to(\kappa_1,\kappa_2)^{\kappa_0}$ implies
%$(\kappa_1,\kappa_2)\to(\kappa_1,\kappa_2)^{\omega_1+\omega_1}$,
%from which we get
%$(\kappa_1,\kappa_2)\to(\kappa_1,\kappa_2)^{\omega_1}_{2^{\omega_1}}$,
%the partition relation for partitions into $2^{\aleph_1}$ many
%sets. From this, we get
%$(\kappa_1,\kappa_2)\to(\kappa_1,\kappa_2)^{<\omega_1}$ by
%coding. \end{proof}
\begin{thm} If there is a model of $\ad$, then there is a model of
Base Case \#1 (i.e., \pattern{\M}{\M}{\M}) and
Base Case \#4 (i.e., \pattern{\M}{\M}{\A}).\label{thm:basecases1and4}
\end{thm}
\begin{proof} Using Theorem \ref{thm:main}, we start with
a limit cardinal $\kappa$ such that
$(\kappa,\kappa^+,\kappa^{++}) \to
(\kappa,\kappa^+,\kappa^{++})^{\kappa}.$
By Lemma \ref{lem:consequencesstrong},
for $\gamma = \kappa$, $\gamma = \kappa^+$, or
$\gamma = \kappa^{++}$,
$\gamma \to (\gamma)^{<\omega_1}$.
From this, it easily follows that
$\gamma \to (\gamma)^{\omega + \omega}$,
so by \cite[Theorem 2.1]{Kleinberg},
$\kappa$, $\kappa^+$, and $\kappa^{++}$ are all measurable.
This yields a model of Base Case \#1
(cf.\ \cite[Theorem 2]{ApterHenle}).
By Lemma \ref{lem:consequencesstrong}, we know that
$\kappa^{++} \to (\kappa^{++})^{< \kappa}$.
Therefore, by forcing with
Magidor-like forcing $\cP_{\kappa,\kappa^{++}}$, we obtain a
model in which $\cf(\kappa^{++}) = \kappa$ and
no new bounded subsets of $\kappa^{++}$ are added.
%the polarized partition relation $(\kappa,\kappa^+)\to
%(\kappa,\kappa^+)^{\kappa}$ still holds (by the initial segment
%preservation from Lemma \ref{lem:initial}).
In particular, $\kappa$ and $\kappa^+$ remain
measurable after this forcing.
Now we can collapse
$\kappa$ symmetrically to become $\aleph_1$ and apply Theorem
\ref{thm:collapse} to obtain our
model for Base Case \#4. \end{proof}
We explicitly note that the full power of
Theorem \ref{thm:main} was not used in
establishing Theorem \ref{thm:basecases1and4}.
For Base Case \#1, all that is required are
cardinals $\kappa$, $\kappa^+$, and $\kappa^{++}$
such that each of $\kappa$, $\kappa^+$, and $\kappa^{++}$
is measurable and $\kappa$ is a limit cardinal
(which is a fairly weak consequence of Theorem \ref{thm:main} and actually follows from Theorem \ref{thm:kechris}).
For Base Case \#4, we only use the existence of
cardinals $\kappa$, $\kappa^+$, and $\kappa^{++}$ such that
both $\kappa$ and $\kappa^+$ are measurable and
$\kappa^{++}$ satisfies the Ramsey-type partition relation
$\kappa^{++} \to (\kappa^{++})^{< \kappa}$
(another consequence of Theorem \ref{thm:main}; in this case, the weaker Theorems
\ref{thm:kechris} and \ref{thm:submain} are---as far as we know---not
enough to establish these assumptions).
The partition relation ensures that
forcing with $\cP_{\kappa,\kappa^{++}}$ changes the
cofinality of $\kappa^{++}$ to $\kappa$ without
adding any bounded subsets to $\kappa^{++}$.
Without the partition relation, it does not seem possible
to be able to show that the forcing $\cP_{\kappa,\kappa^{++}}$
satisfies the aforementioned properties.
%\begin{thm}[Apter-Henle 1986] If there is a model of $\ad$,
%then there is a model of
%Base Case \#1 (i.e., \pattern{\M}{\M}{\M}).\label{thm:apterhenle}
%\end{thm}
%
%\begin{proof} Cf.\ \cite[Theorem 2]{ApterHenle}.
%The authors used (a slightly weaker version of)
%Kechris' Theorem \ref{thm:kechris}, listed as ``personal
%communication'' without a proof in \cite{ApterHenle}. \end{proof}
\begin{thm} If there is a model of $\AD$, then there is a model of
Base Case \#6 (i.e., \pattern{\M}{\A}{\M}).\label{thm:basecase6}
\end{thm}
\begin{proof} Again, from Theorem \ref{thm:main}, we start
with a limit cardinal $\kappa$ such that
$(\kappa,\kappa^+,\kappa^{++}) \to
(\kappa,\kappa^+,\kappa^{++})^{\kappa}$, and get with Lemma
\ref{lem:consequencesstrong} the
Ramsey-type polarized partition property
$(\kappa^+,\kappa^{++})\to(\kappa^+,\kappa^{++})^{<\kappa}$
and the ordinary partition relation
$\kappa^+ \to (\kappa^+)^{< \kappa}$.
Because $\kappa^+ \to (\kappa^+)^{< \kappa}$,
after forcing with Magidor-like forcing $\cP_{\kappa,\kappa^{+}}$,
the measurability of $\kappa$ is preserved (as the
forcing does not add bounded subsets of $\kappa^+$),
and $\cf(\kappa^+) = \kappa$.
Furthermore, since
$(\kappa^+,\kappa^{++})\to(\kappa^+,\kappa^{++})^{<\kappa}$,
by the countable final segment preservation
from Lemma \ref{lem:AHJ.Prop.6.4mod},
$\kappa^{++} \to (\kappa^{++})^{<\omega_1}$ remains
true. Hence, $\kappa^{++}$ stays measurable.
Now, we can collapse $\kappa$
symmetrically to become $\aleph_1$ and apply
Theorem \ref{thm:collapse} to obtain our result. \end{proof}
As is the case with Theorem \ref{thm:basecases1and4},
the full power of Theorem \ref{thm:main} is not
required in order to establish Theorem \ref{thm:basecase6}.
For Base Case \#6, we are using the existence of cardinals
$\kappa$, $\kappa^+$, and $\kappa^{++}$ such that
$\kappa$ is measurable,
$\kappa^+ \to (\kappa^+)^{< \kappa}$,
and the pair
$(\kappa^+, \kappa^{++})$ satisfies the Ramsey-type
polarized partition property
$(\kappa^+,\kappa^{++})\to(\kappa^+,\kappa^{++})^{<\kappa}$.
The partition relation $\kappa^+ \to (\kappa^+)^{< \kappa}$
allows us to deduce that forcing with $\cP_{\kappa,\kappa^{+}}$
changes the cofinality of $\kappa^+$ to $\kappa$ without
adding any bounded subsets to $\kappa^+$
(thereby preserving the measurability of $\kappa$).
The polarized partition property ensures that forcing with
$\cP_{\kappa,\kappa^{+}}$ preserves the ordinary partition relation
$\kappa^{++} \to (\kappa^{++})^{< \omega_1}$, which we then
use to infer that $\kappa^{++}$ remains a measurable cardinal.
Without the ordinary partition
relation and something along the
lines of the polarized partition relation,
it does not seem possible
to be able to show that the forcing $\cP_{\kappa,\kappa^{+}}$
satisfies the aforementioned properties.
For Base Case \#8, we rely on the methods of
\cite{AHJ}.
\begin{thm} If $\mathbf{L}(\mathbb{R})\models\mathsf{AD}$,
then there is a model of Base Case
\#8 (i.e., \pattern{\M}{\A}{\A}).\label{thm:basecase8}
\end{thm}
\begin{proof}
Suppose $V$ is a model of
$\mathbf{V}=\mathbf{L}(\mathbb{R})$ and $\mathsf{AD}$.
We use the model $N$ constructed and investigated
in \cite[\S 8]{AHJ} (in particular, \cite[Theorem 8.1]{AHJ}) and
applied in \cite[Theorem 11.1]{AHJ}.
In this model, which is a symmetric submodel
of a forcing extension of $V$,
$\aleph_2$ and $\aleph_3$ have cofinality $\aleph_1$.
Further, by \cite[Proposition 6.2 and Lemma 8.2]{AHJ},
$N$ and $V$ have the same bounded subsets of $\aleph_1$.
Thus, since
$V \models$``$\aleph_1$ is measurable'', $N \models$``$\aleph_1$
is measurable'' as well.
This means that $N$ is as desired. \end{proof}
\begin{figure}
{\small \begin{tabular}{rr|lcc}
&&& upper bound & lower bound\\[1mm]
\hline
\textbf{Base Case \#1:}& 1&\pattern{\M}{\M}{\M} & $\ZF+\AD$ & $\WC$
\\
\textbf{Base Case \#2:}& 2&\pattern{\M}{\M}{\AAA} & $\SCM$ & $\WC$
\\
\textbf{Base Case \#3:}& 3&\pattern{\M}{\M}{\AA} & $\ZF+\AD$ &
$\WC$ \\
\textbf{Base Case \#4:}& 4&\pattern{\M}{\M}{\A} & $\ZF+\AD$ & $\WC$
\\
(\#1)& 5&\pattern{\M}{\M}{\a} & $\ZF+\AD$ & $\WC$ \\
\textbf{Base Case \#5a:}& 6&\pattern{\M}{\AA}{\M} & $\TMC$ & $\TMC$
\\
\textbf{Base Case \#5b:}& 7&\pattern{\M}{\AA}{\AAA} & $\MC$ &
$\MC$\\
\textbf{Base Case \#5c:}& 8&\pattern{\M}{\AA}{\AA} & $\MC$ &
$\MC$\\
\textbf{Base Case \#5d:}& 9&\pattern{\M}{\AA}{\A} & $\MC$ & $\MC$
\\
(\#5a)&10&\pattern{\M}{\AA}{\a} & $\MC$ & $\MC$ \\
\textbf{Base Case \#6:}& 11&\pattern{\M}{\A}{\M} & $\ZF+\AD$ &
$\WC$ \\
\textbf{Base Case \#7:}&12&\pattern{\M}{\A}{\AAA} & $\SC$ & $\WC$\\
&13&\pattern{\M}{\A}{\AA} &\inc & \inc \\
\textbf{Base Case \#8:}& 14&\pattern{\M}{\A}{\A} & $\ZF+\AD$ &
$\WC$ \\
(\#6)&15&\pattern{\M}{\A}{\a} & $\ZF+\AD$ & $\WC$ \\
(\#1)&16&\pattern{\M}{\a}{\M} & $\ZF+\AD$ & $\WC$ \\
(\#2)&17&\pattern{\M}{\a}{\AAA} & $\SCM$ & $\WC$ \\
&18&\pattern{\M}{\a}{\AA} & \inc& \inc \\
(\#4)&19&\pattern{\M}{\a}{\A} & $\ZF+\AD$ & $\WC$ \\
(\#1,\#3)&20&\pattern{\M}{\a}{\a} & $\ZF+\AD$ & $\WC$ \\
(\#1)&21&\pattern{\A}{\M}{\M} & $\ZF+\AD$ & $\WC$ \\
(\#2)&22&\pattern{\A}{\M}{\AAA} & $\MC$ & $\MC$ \\
(\#3)&23&\pattern{\A}{\M}{\AA} & $\ZF+\AD$ & $\WC$ \\
(\#4)&24&\pattern{\A}{\M}{\A} & $\ZF+\AD$ & $\WC$ \\
(\#1)&25&\pattern{\A}{\M}{\a} & $\ZF+\AD$ & $\WC$ \\
(\#5a)&26&\pattern{\A}{\AA}{\M} & $\MC$ & $\MC$ \\
(\#5b)&27&\pattern{\A}{\AA}{\AAA} & $\ZFC$ & $\ZFC$\\
(\#5c)&28&\pattern{\A}{\AA}{\AA} & $\ZFC$ & $\ZFC$\\
(\#5d)&29&\pattern{\A}{\AA}{\A} & $\ZFC$ & $\ZFC$ \\
(\#5a)&30&\pattern{\A}{\AA}{\a} & $\ZFC$ & $\ZFC$
\end{tabular}}
\caption{Lower and upper bounds for the consistency strength of
patterns 1 to 30.}
\label{fig:1to30}
\end{figure}
\section{Summary, Lower Bounds \& Open Questions}\label{sec:summary}
Figures \ref{fig:1to30} and \ref{fig:31to60} list all of the
sixty patterns of measurability and cofinality
for the first three uncountable cardinals. In the first column,
we list ``\textbf{Base Case \#$n$}'' if a pattern
is one of our base cases. We list numbers in parentheses
to indicate in which of the diagrams
of \S\,\ref{sec:reducing} the pattern shows
up (if at all: of course, the 13 inconsistent patterns
do not show up in the diagrams).
For the purpose of listing the upper and lower consistency
strength bounds of our patterns, we define the following theories:
$\SCM$ stands for $\ZFC$ together with the statement
``There are $\kappa < \lambda$ where $\kappa$ is supercompact
and $\lambda$ is measurable''; $\SC$ stands for $\ZFC$
together with the statement
``There is a supercompact cardinal'';
$\MC$ stands for $\ZFC$ together with the statement
``There is a measurable cardinal''; $\TMC$ stands for
$\ZFC$ together with the statement ``There are two measurable cardinals'';
$\WC$ stands for $\ZFC$ together with the statement
``There is a Woodin cardinal''.
\subsection*{Upper bounds.} Most of the upper bounds come directly
from our consistency proofs in Theorems
%\ref{thm:apterhenle},
\ref{thm:woodin}, \ref{thm:ad},
\ref{thm:basecases1and4}, \ref{thm:leavingagap}, \ref{thm:basecase6},
\ref{thm:basecase7}, and \ref{thm:basecase8}
(corresponding to the eight base cases)
and the reduction diagrams as listed in \S\,\ref{sec:reducing}.
In a few cases, the upper bound for the consistency strength obtained
by our reduction diagrams is patently not optimal.
In our table, we have given the optimal bounds and briefly list
these exceptional cases in the following: patterns 22
and 26 can be obtained from a measurable cardinal
by symmetrically collapsing it to the
desired cardinal. Patterns 27, 28, 29, 30, 47, 48, and 50
all share the feature that $\aleph_2$ is regular but
non-measurable and do not involve any measurable cardinals;
consequently, the methods of Theorem \ref{thm:leavingagap} allow
us to obtain them from $\ZFC$. Patterns 32 and 37 only involve
one singular cardinal, and can thus be obtained
from $\ZFC$ by symmetrically collapsing
a strong limit of the desired cofinality. Finally,
pattern 46 is another
application of the methods of
Theorem \ref{thm:leavingagap} that only requires one measurable cardinal.
\subsection*{Lower bounds.}
For the purpose of calculating lower bounds,
we shall define ``$\kappa$ is measurable''
by ``there is a normal $\kappa$-complete ultrafilter on $\kappa$''.
Usually, ``normal'' is not required;
in $\mathsf{ZF}+\mathsf{DC}$, it is possible to
construct a normal ultrafilter from
a $\kappa$-complete one (cf.\ \cite[Theorem 10.20]{Jech}),
i.e., our stronger definition is equivalent to the usual definition.
There are a number of trivial lower bounds:
any pattern involving a measurable or two measurables necessarily has $\MC$ or $\TMC$ as a lower bound
(by the standard $\mathbf{L}[U]$ argument).
For other lower bounds, our main tool is the following theorem:
\begin{thm}[Schindler / Jensen-Steel] Suppose $\delta < \delta^+$ are
singular. Then there is an inner model with a Woodin
cardinal.
\label{thm:schindler}
\end{thm}
\begin{proof} \cite[Theorem 1]{Schindler} proved this claim under the additional
assumption that there is some $\Omega > \delta^+$ that is inaccessible and measurable in
$\mathbf{HOD}$. Schindler needed this assumption to build the core model. In the meantime,
Jensen and Steel have eliminated this assumption from the construction of the core model
(cf.\ \cite{JS2,JS1}).\end{proof}
Theorem \ref{thm:schindler} allows us to deal immediately with those patterns that have two consecutive singular cardinals
(patterns 14, 15, 19, 20, 34, 35, 39, 40, 56, 57, and 60) and get a lower bound of a Woodin cardinal. Patterns that involve $\kappa$ and $\kappa^+$ such that either both are measurable or one of them is measurable and the other is singular
have to be transformed into those that have
two consecutive singulars by P\v{r}\'{\i}kr\'{y} forcing via
Theorem \ref{thm:prikry}. This argument uses
our slightly non-standard definition of
measurable cardinal (guaranteeing the existence of a normal ultrafilter).
This allows us to transform patterns
1, 2, 3, 4, 5, 11, 12, 16, 17, 21, 23, 24, 25, 31, 36, 41, 42, 43,
and 45 into a pattern with two consecutive singulars and thus
apply Theorem \ref{thm:schindler} to get a lower bound of a Woodin cardinal.
Without the additional normality assumption, we do not know
how to derive more strength than a measurable out of,
say, $\pattern{\a}{\M}{\AAA}$.
\begin{figure}
{\small \begin{tabular}{rr|lcc}
&&& upper bound & lower bound\\[1mm]
\hline
\rule{1mm}{0mm}(\#6)&31&\pattern{\A}{\A}{\M} & $\ZF+\AD$ & $\WC$\\
(\#7)& 32&\pattern{\A}{\A}{\AAA} & $\ZFC$ & $\ZFC$ \\
& 33&\pattern{\A}{\A}{\AA} & \inc& \inc\\
(\#8)& 34&\pattern{\A}{\A}{\A} & $\ZF+\AD$ & $\WC$\\
(\#6)& 35&\pattern{\A}{\A}{\a} & $\ZF+\AD$ & $\WC$\\
(\#1)& 36&\pattern{\A}{\a}{\M} & $\ZF+\AD$ & $\WC$\\
(\#2)& 37&\pattern{\A}{\a}{\AAA} & $\ZFC$ & $\ZFC$ \\
& 38&\pattern{\A}{\a}{\AA} & \inc& \inc\\
(\#4)& 39&\pattern{\A}{\a}{\A} & $\ZF+\AD$ & $\WC$\\
(\#1,\#3)&40&\pattern{\A}{\a}{\a} & $\ZF+\AD$ & $\WC$\\
(\#1)&41&\pattern{\a}{\M}{\M} & $\ZF+\AD$ & $\WC$\\
(\#2)&42&\pattern{\a}{\M}{\AAA} & $\SCM$ & $\WC$\\
(\#3)&43&\pattern{\a}{\M}{\AA} & $\ZF+\AD$ & $\WC$\\
&44&\pattern{\a}{\M}{\A} &\inc & \inc\\
(\#1,\#4)&45&\pattern{\a}{\M}{\a} & $\ZF+\AD$ & $\WC$\\
(\#5a)&46&\pattern{\a}{\AA}{\M} & $\MC$ & $\MC$\\
(\#5b)&47&\pattern{\a}{\AA}{\AAA} & $\ZFC$ & $\ZFC$\\
(\#5c)&48&\pattern{\a}{\AA}{\AA} & $\ZFC$ & $\ZFC$\\
&49&\pattern{\a}{\AA}{\A} & \inc& \inc\\
(\#5a,\#5d)&50&\pattern{\a}{\AA}{\a} & $\ZFC$ & $\ZFC$\\
&51&\pattern{\a}{\A}{\M} & \inc& \inc\\
&52&\pattern{\a}{\A}{\AAA} & \inc& \inc\\
&53&\pattern{\a}{\A}{\AA} & \inc& \inc\\
&54&\pattern{\a}{\A}{\A} & \inc& \inc\\
&55&\pattern{\a}{\A}{\a} & \inc & \inc\\
(\#1,\#6)&56&\pattern{\a}{\a}{\M} & $\ZF+\AD$ & $\WC$\\
(\#2,\#7)&57&\pattern{\a}{\a}{\AAA} & $\SC$ & $\WC$\\
&58&\pattern{\a}{\a}{\AA} & \inc& \inc\\
&59&\pattern{\a}{\a}{\A} & \inc& \inc\\
(\#1,\#3,\#4,\#6,\#8)&60&\pattern{\a}{\a}{\a} & $\ZF+\AD$ & $\WC$
\end{tabular}}
\caption{Lower and upper bounds for the consistency strength of patterns 31 to 60.}
\label{fig:31to60}
\end{figure}
\subsection*{Open Questions}
We end the paper by listing some
remaining open questions. Six of the eight base cases
can be obtained from a model of $\ZF+\AD$,
but Base Case \#2 appears to need
(assumptions on the order of)
$\SCM$ and Base Case \#7
appears to need
(assumptions on the order of)
$\SC$.\footnote{As the proof of
\cite[Theorem 1]{ApterHenle} shows,
slightly weaker supercompactness hypotheses
(which are still well beyond the consistency
strength of $\AD$) actually suffice to
establish Base Case \#2 and Base Case \#7.}
\begin{quest}
Is it possible to force Base Case \#2
and Base Case \#7 from $\ZF+\AD$ (thus reducing the
consistency strength upper bound)?
\end{quest}
The two mentioned patterns are among 30
(out of our 60) patterns for which the upper bound
and the lower bound in consistency strength do not
coincide.
\begin{quest} Can we determine the precise consistency strength
in the cases where upper and lower bounds do not coincide?
\end{quest}
There are other large cardinal properties that
can be exhibited by small cardinals, such as
``$\kappa$ is $\kappa^+$-supercompact''
(under $\AD$, $\aleph_1$ exhibits this property
(cf.\ \cite{DPH})). Let us add another label for this
property to our patterns,
resulting in $4\times 5\times 6 = 120$ patterns.
\begin{quest}
Which of the 120 patterns involving cofinalities
$\aleph_0$, $\aleph_1$, $\aleph_2$, $\aleph_3$, measurability
and $\kappa^+$-supercompactness are consistent?\label{q:supercompact}
\end{quest}
Note that a 1975 result of Martin (cf.\ \cite[\S\,2]{DPH} for details) about the $\kappa^+$-supercompactness of
$\kappa$ under the assumption that both $\kappa$ and $\kappa^+$ carry a normal measure produces some nontrivial
restrictions for Question \ref{q:supercompact}.
\medskip
Now, after considering all
measurability and cofinality
patterns for the cardinals $\aleph_1$, $\aleph_2$,
and $\aleph_3$, one could ask what happens
if the same question is posed
for the first four uncountable cardinals.
There are $3\times 4\times 5\times 6 = 360$ such
patterns for the first
four uncountable cardinals.
\begin{quest}
Which of the 360 measurability and cofinality
patterns for the first four uncountable cardinals are consistent?
\label{q:four}
\end{quest}
Of course, a complete answer to Question \ref{q:four} would require
(among other things) a solution of one of the
big open questions of the field of large cardinals
without the Axiom of Choice, viz.\ whether it is consistent to have
four consecutive measurable cardinals. As a consequence,
we do not expect an answer to Question \ref{q:four} very
soon.
Slightly less ambitious would be to ask the same question
not for four consecutive cardinals, but for a
different selection of three consecutive cardinals,
e.g., the cardinals $\aleph_2$, $\aleph_3$, and $\aleph_4$.
Here we would have $4\times 5\times 6 = 120$ patterns.
\begin{quest}
Which of the 120 measurability and cofinality
patterns for the cardinals $\aleph_2$, $\aleph_3$, and $\aleph_4$
are consistent?
\label{q:aleph234}
\end{quest}
However, most of the methods used in this paper
to handle the case of the first three uncountable cardinals
will not work in this setting.
The main reason is that most of the proofs require symmetrically collapsing
some large cardinal to be $\aleph_1$. This collapse is
canonically well-orderable, and thus at our disposal in the
choice-free situation. The collapse of a cardinal to be $\aleph_2$,
however, is not canonically well-orderable; consequently, the obvious
analogues of our proofs will not work in the setting of
Question \ref{q:aleph234}.
At this point, it might be useful to mention that some of
the patterns have alternative consistency proofs
that are more likely to transfer to the situation
of $\aleph_2$, $\aleph_3$, and $\aleph_4$. We would like to give
one example: if there is a
strongly compact cardinal $\kappa$,
it is possible to obtain the pattern
\pattern{\A}{\a}{\A} by using strongly
compact \Prikry\ forcing. Obviously, this proof is not optimal
in terms of consistency strength (as we can get it from $\ZF+\AD$
via Theorem \ref{thm:basecases1and4}). However, this proof lifts to give
a consistency proof of the pattern
``$\aleph_2$ is regular but not measurable,
$\aleph_3$ has cofinality $\aleph_0$,
and $\aleph_4$ has cofinality
$\aleph_2$''.\footnote{A sketch of the proof
is as follows. Let $\kappa < \lambda$ be
such that in our ground model ${\mathbf{V}}$,
$\kappa$ is strongly compact and
$\lambda$ is the least singular strong limit
cardinal of cofinality $\aleph_2$ greater
than $\kappa$. Force over ${\mathbf{V}}$ with
$P_1 \times P_2$, where $P_1 =
\mathrm{Col}(\aleph_2, {<}\kappa)$ and
$P_2$ is strongly compact \Prikry\
forcing based on $\kappa$ and $\lambda$
as defined in the proof of \cite[Theorem 1]{ApHe91}.
Let $G = G_1 \times G_2$ be the resulting generic,
with $r = \langle r_n~;~ n < \omega \rangle$ the
generic sequence through $P_\kappa(\lambda)$
generated by $G_2$.
For $\delta \in (\kappa, \lambda)$ a cardinal, define
$r {\upharpoonright} \delta =
\langle r_n \cap \delta~;~ n < \omega \rangle$.
Consider the symmetric model
$N :=
\mathrm{HD}_\mathbf{V}(
\{G_1{\upharpoonright}\delta\,;\,\delta\in(\aleph_2,\kappa)$
and $\delta$ is a cardinal$\}
\cup
\{r{\upharpoonright}\delta\,;\,\delta\in(\kappa,\lambda)$
and $\delta$ is a cardinal$\})$.
The arguments found in the proofs of \cite[Theorem 1]{ApHe91}
and Theorems \ref{thm:cohen} and \ref{thm:leavingagap}
of this paper then show that $N$ is as desired.
Note that if $P_1$ is redefined as
$\mathrm{Col}(\aleph_1, {<}\kappa)$,
$\lambda$ is redefined as the least singular
strong limit cardinal of cofinality
$\aleph_1$ greater than $\kappa$,
$P_2$ remains strongly compact
\Prikry\ forcing based on $\kappa$
and $\lambda$, and $N$ is redefined as
$N :=
\mathrm{HD}_\mathbf{V}(
\{G_1{\upharpoonright}\delta\,;\,\delta\in(\aleph_1,\kappa)$
and $\delta$ is a cardinal$\}
\cup
\{r{\upharpoonright}\delta\,;\,\delta\in(\kappa,\lambda)$
and $\delta$ is a cardinal$\})$, then $N$ is a
model of the pattern \pattern{\A}{\a}{\A}.}
\bibliographystyle{alpha}
\bibliography{aleph123}
\end{document}
*