text:
\chapter{The Ketonen Order}\label{KetonenChapter}
\section{Introduction}
\subsection{Ketonen's order}
Central to \cref{MOChapter} was an argument that the Mitchell order is linear in
all known canonical inner models. In \cref{WCUASection}, we delved deeper into
the first half of this proof, extracting from it a general inner model principle
called the Ultrapower Axiom. It turns out that a closer look at the second half
of the proof also yields more information: it shows that the Ultrapower Axiom
implies not only the linearity of the Mitchell order, but also the linearity of
a much more general order on countably complete ultrafilters.

This order dates back to the early 1970s. A remarkable theorem of Ketonen
\cite{Ketonen} from this period states that if every regular cardinal \(\lambda
\geq \kappa\) carries a \(\kappa\)-complete uniform ultrafilter, then \(\kappa\)
is strongly compact. Ketonen\index{Ketonen} gave two proofs of this theorem. The
first is an induction. The second is not as well-known, but is of much greater
interest here. Ketonen introduced a wellfounded order on countably complete
weakly normal ultrafilters, and showed that certain minimal elements in this
order witness the strong compactness of \(\kappa\). (We give this proof in
\cref{KetonenThm} since generalizations of the proof form a key component of our
analysis of strong compactness and supercompactness under UA.)

Independently of Ketonen's work, and a rather long time after, we extracted from
the proof of the linearity of the Mitchell order under UA (\cref{UAMO}) a more
general version of Ketonen's order, which we now call the {\it Ketonen order}.
The Ketonen order is a wellfounded partial order on countably complete
ultrafilters concentrating on ordinals. The key realization, which distinguishes
our work from Ketonen's, is that the Ketonen order can be {\it linear.} In fact,
the totality of the Ketonen order is an immediate consequence of UA
(\cref{Totality}). In fact, the linearity of the Ketonen order is equivalent to
the Ultrapower Axiom. This equivalence is \cref{LinKetThm}, which is probably
the hardest theorem of this chapter. The Ketonen order will be our main tools in
the investigation of the structure of countably complete ultrafilters under UA.

\subsection{Outline of \cref{KetonenChapter}}
Let us outline the rest of \cref{KetonenChapter}.\\

\noindent {\sc\cref{PrelimsSection2}.} We introduce some more preliminary
definitions that will be used throughout the rest of this dissertation.
Especially important are limits of ultrafilters, which we introduce both in the
traditional ultrafilter theoretic sense and in a generalized setting in terms of
inverse images.\\

\noindent {\sc\cref{KetonenOrderSection}.} We introduce the main object of study of this
chapter, a fundamental tool in the theory of the Ultrapower Axiom: a wellfounded
partial order on countably complete ultrafilters called the Ketonen order. In
\cref{KOCharsSection}, we define the Ketonen order and give various alternate
characterizations. The most important characterization is given by
\cref{KOChars}, which shows that the Ketonen order can be reformulated in terms
of comparisons. This immediately leads to the observation that the Ketonen order
is linear under the Ultrapower Axiom. In \cref{BasicSection}, we establish the
basic order-theoretic properties of the Ketonen order: it is a preorder on the
class of countably complete ultrafilters concentrating on ordinals. Restricted
to tail uniform ultrafilters, it is a partial order. \cref{SpaceLemma} shows
that the Ketonen order is {\it graded} in the sense that if \(\alpha < \beta\),
then the tail uniform ultrafilters on \(\alpha\) all lie below those on
\(\beta\). In particular, the Ketonen order is setlike. We finally prove the
wellfoundedness of the Ketonen order (\cref{KOWellfounded}). The general proof
of the wellfoundedness of the Ketonen order is due to the author.\\

\noindent {\sc\cref{OtherOrderSection}.} We explore the relationship between the Ketonen
order and two well-known orders on ultrafilters. \cref{MOKetSection} shows that
the restriction of the Ketonen order to normal ultrafilters is precisely the
Mitchell order. In this sense the Ketonen order is a generalized Mitchell order.
In \cref{RKSection} we turn to perhaps the best-known order on ultrafilters: the
Rudin-Keisler order. We take this opportunity to set down some basic facts about
this order, sometimes with proofs. The Ketonen order is not isomorphism
invariant, so it cannot extend the Rudin-Keisler order. To explain these orders'
relationship better, we define an auxiliary order called the {\it revised
Rudin-Keisler order} which is contained in the intersection of the Rudin-Keisler
order and the Ketonen order. Moreover we introduce the concept of an {\it
incompressible ultrafilter}, an ultrafilter \(U\) whose generator \(\id_U\) is
as small as possible (see \cref{IncomPower}). An argument due to Solovay shows
that the strict Rudin-Keisler order and the revised Rudin-Keisler order coincide
on incompressible ultrafilters. Thus the Ketonen order extends the strict
Rudin-Keisler order on countably complete incompressible ultrafilters.\\

\noindent {\sc\cref{VariantSection}.} We study several variants of the Ketonen order. In
\cref{ExtendedKetonen}, we investigate the relationship between the Ketonen
order and notions from inner model theory. We introduce a model theoretic
generalization of the Ketonen order whose domain is the class of pointed models
of ZFC, structures \((M,\xi)\) where \(M\) is a transitive model of ZFC and
\(\xi\) is an ordinal of \(M\). This defines a  coarse analog of the Dodd-Jensen
order, the canonical prewellorder on mice. We give a generalized wellfoundedness
proof for this order (\cref{GenWellfounded}) that is closely related to the
proof of the wellfoundedness of the Dodd-Jensen order. We use this to prove an
often useful lemma that is a coarse analog of the Dodd-Jensen lemma:
\cref{MinDefEmb} shows that definable embeddings are pointwise minimal on the
ordinals.

In the next subsection, \cref{SOSection}, we introduce the {\it seed order}. In
early versions of this work, we mainly used the seed order where we now use the
Ketonen order. There is no substantive difference between these approaches since
under UA the two orders coincide. In ZFC, however, one cannot prove that the
seed order is transitive: indeed, we show by a silly argument that the
transitivity of the seed order implies the Ultrapower Axiom. We also introduce
an extension of the seed order to pointed ultrapowers. The next subsection
\cref{MInftySection} is spent relating this order to the structure of the direct
limit of all ultrapowers under UA.

The next two subsections are devoted to combinatorial generalizations of the
Ketonen order. One does not need to read them to understand the rest of this
dissertation. In  \cref{LipschitzSection}, we introduce a generalized version of
the Lipschitz order, and show that this order extends the Ketonen order on
countably complete ultrafilters. Therefore under UA, the two orders coincide,
which gives a strange analog of the linearity of the Lipschitz order in
determinacy theory. \cref{FilterSection} introduces a combinatorial
generalization of the Ketonen order to filters, which demonstrates a
relationship between the Ketonen order and the canonical order on stationary
sets due to Jech \cite{JechStationary}.\\

\noindent {\sc\cref{LinKetSection}.} This section contains \cref{LinKetThm}, the most
substantive result of the chapter:  the linearity of the Ketonen order is
equivalent to the Ultrapower Axiom. The fact that UA implies the linearity of
the Ketonen order is immediate. (The proof appears in \cref{KOCharsSection}.)
The converse, however, is subtle. Since we will mostly work under the assumption
of UA, this equivalence is itself not that important (although it does show that
all of our results can be proved from an a priori weaker premise). More
important is the proof, which identifies a canonical way to compare a pair of
ultrafilters assuming the linearity of the Ketonen order.

\section{Preliminary definitions}\label{PrelimsSection2}
\subsection{Tail uniform ultrafilters}\label{TailUniformSection}
A common notational issue we will encounter in this dissertation is that two
ultrafilters may differ only in the sense that they have different underlying
sets. The change-of-space relation, defined below, articulates our tendency to
identify such ultrafilters.
\begin{defn}\label{UltrafilterConcentration}
	Suppose \(U\) is an ultrafilter on \(X\) and \(C\) is a class. We say \(U\)
	{\it concentrates on \(C\)} if \(C\cap X\in U\). If \(C\) is a set and \(U\)
	concentrates on \(C\), the {\it projection of \(U\) on
	\(C\)}\index{Projection of an ultrafilter}\index{\(U\mid C\) (projection of
	an ultrafilter on a set)} is the ultrafilter \(U\mid C = \{A\subseteq C :
	A\cap X\in U\}\).\index{Ultrafilter!concentrating on a class}
\end{defn}

\begin{defn}\label{EmbeddingEquivalenceDef}
	The {\it change-of-space relation}\index{\(\KE\) (change-of-space relation)}
	is defined on ultrafilters \(U\) and \(W\) by setting \(U \KE W\) if \(U = W
	\mid X\) where \(X\) is the underlying set of \(U\).
\end{defn}

\begin{lma}\label{EmbeddingEquivalence}
	Suppose \(U\) and \(W\) are ultrafilters. Then the following are equivalent:
	\begin{enumerate}[(1)]
		\item \(U\KE W\).
		\item For some set \(S\in U\cap W\), \(U\cap P(S) = W\cap P(S)\).
		\item For all sets \(A\), \(\id_U \in j_U(A)\) if and only if \(\id_W\in
		j_W(A)\).
		\item There is a comparison \((k,h)\) of \((j_U,j_W)\) such that
		\(k(\id_U) = h(\id_W)\).\qed
	\end{enumerate}
\end{lma}
The change-of-space relation is therefore an equivalence relation on
ultrafilters.

The Ketonen order will be a partial order on the class of ultrafilters on
ordinals. On such general ultrafilters, however, the (nonstrict) Ketonen order
is only a preorder, due to the existence of \(\KE\)-equivalent ultrafilters (see
\cref{StrictvsNonStrict2}). Thus we sometimes restrict further to those
ultrafilters that are uniform in a slightly nonstandard sense:

\begin{defn}A filter \(F\) on an ordinal \(\delta\) is {\it tail uniform}\index{Tail uniform} if it contains \(\delta \setminus\alpha\) for every \(\alpha < \delta\).\end{defn}

For any ordinal \(\delta\), the {\it tail filter}\index{Tail filter} on
\(\delta\) is the filter generated by sets of the form \(\delta\setminus
\alpha\) for \(\alpha < \delta\). A filter is therefore tail uniform if it
extends the tail filter. Equivalently, \(F\) is tail uniform if every element of
\(F^+\) is cofinal in \(\alpha\).

For example, the principal ultrafilter on \(\alpha+1\) concentrated at
\(\alpha\) is uniform.

\begin{defn}\label{SpaceDef} If \(U\) is an ultrafilter that concentrates on
ordinals, then \(\delta_U\)\index{\(\delta_U\)} denotes the least ordinal
\(\delta\) on which \(U\) concentrates.
\end{defn}

\begin{lma} If \(U\) is an ultrafilter that concentrates on ordinals, then \(U\) is tail uniform if and only if \(\delta_U\) is the underlying set of \(U\).\qed\end{lma}

The key property of tail uniform ultrafilters, which is quite obvious, is that
they yield canonical representatives of \(\KE\) equivalence classes of
ultrafilters concentrating on ordinals.
\begin{lma}
	For any ultrafilter \(U\) that concentrates on ordinals, then \(U\mid
	\delta_U\) is the unique tail uniform ultrafilter \(W\) such that \(U \KE
	W\). In particular, if \(U\) and \(W\) are tail uniform ultrafilters such
	that \(U\KE W\), then \(U = W\).\qed
\end{lma}

There is an obvious but useful characterization of \(\delta_U\) in terms of
elementary embeddings:
\begin{lma}\label{SpaceChar}
If \(U\) is an ultrafilter that concentrates on ordinals, then \(\delta_U\) is
the least ordinal \(\delta\) such that \(\id_U < j_U(\delta)\).\qed
\end{lma}

\begin{defn}
The class of countably complete tail uniform ultrafilters\index{\(\Un\)
(countably complete tail uniform ultrafilters)} is denoted by \(\Un\).
\end{defn}

Let us just point out that tail uniformity and uniformity are not the same
concept, and moreover neither is a strengthening of the other. The simplest way
to separate these concepts is by considering the Fr\'echet and tail filters
themselves. For any set \(X\), let \(F_X\) denote the Fr\'echet filter on \(X\).
For any ordinal \(\alpha\), let \(T_\alpha\) denote the tail filter on
\(\alpha\).

\begin{lma}
Suppose \(\lambda\) is an ordinal.
\begin{itemize}
\item \(T_\lambda \subseteq F_\lambda\) if and only if \(\lambda\) is a
cardinal.
\item \(F_\lambda \subseteq T_\lambda\) if and only if \(|\lambda| =
\textnormal{cf}(\lambda)\).
\end{itemize}
Thus \(T_\lambda = F_\lambda\) if and only if \(\lambda\) is a regular cardinal.
If \(\lambda\) is a singular cardinal, \(T_\lambda\) is tail uniform but not
uniform. If \(\lambda\) is not a cardinal, then \(F_\lambda\) is uniform but not
tail uniform.\qed
\end{lma}

One can easily obtain ultrafilters that are counterexamples to the equivalence
of tail uniformity and true uniformity by combining the previous lemma with the
Ultrafilter Lemma.

\subsection{Limits of ultrafilters}\label{LimitSection}
The following definition comes from classical ultrafilter theory:
\begin{defn}\label{LimitDef}
Suppose \(W\) is an ultrafilter, \(I\) is a set in \(W\), and \(\langle U_i :
i\in I\rangle\) is a sequence of ultrafilters on a set \(X\). The {\it
\(W\)-limit of \(\langle U_i : i\in I\rangle\)}
\index{Limit}
\index{\(U\text{-}\lim\) (\(U\)-limit)} is the ultrafilter \[W\text{-}\lim_{i\in
I} U_i = \{A\subseteq X: \{i\in I : A\in U_i\}\in W\}\]
\end{defn}

It is often easier to think about limits in terms of elementary embeddings:
\begin{lma}\label{LimitInverse}
Suppose \(W\) is an ultrafilter, \(I\) is a set in \(W\), and \(\langle U_i :
i\in I\rangle\) is a sequence of ultrafilters on a fixed set \(X\). Then
\[W\text{-}\lim_{i\in I} U_i = j_W^{-1}[Z]\] where \(Z = [\langle U_i : i\in
I\rangle]_W\).
\begin{proof}
Suppose \(A\subseteq X\). Then
\begin{align*}
A\in W\text{-}\textstyle\lim_{i\in I} U_i &\iff  A\in U_i\text{ for \(W\)-almost all }i\in I\\
&\iff j_W(A)\in [\langle U_i : i\in I\rangle]_W\\
&\iff A\in j_W^{-1}[Z]
\end{align*}
where the middle equivalence follows from \L o\'s's Theorem.
\end{proof}
\end{lma}

Limits generalize the usual derived ultrafilter and pushforward constructions:
\begin{defn}\label{PrincipalDef}\index{Principal ultrafilter}\index{\(\pr {a} {X}\) (principal ultrafilter)}
	Suppose \(X\) is a set and \(a\in X\). The {\it principal ultrafilter on
	\(X\) concentrated at \(a\)} is the ultrafilter \(\pr a X = \{A\subseteq X :
	a\in A\}\).
\end{defn}

\begin{defn}\label{PushDef}\index{Pushforward}
	Suppose \(W\) is an ultrafilter, \(I\) is a set in \(W\), and \(f : I\to X\)
	is a function. Then the {\it pushforward} of \(W\) by \(f\) is the
	ultrafilter \(f_*(W) = \{A\subseteq X: f^{-1}[A]\in W\}\).
\end{defn}

The following lemmas relate the derived ultrafilter construction to inverse
images, limits, and pushforwards.

\begin{lma}\label{DerivedPrincipal}\index{Derived ultrafilter!as an inverse image}
	Suppose \(N\) and \(P\) are transitive models of \textnormal{ZFC}, \(X\) is
	a set in \(N\), \(i : N \to P\) is an elementary embedding, and \(a\in
	i(X)\). Then the \(N\)-ultrafilter on \(X\) derived from \(i\) using \(a\)
	is simply \(i^{-1}[\pr a {i(X)}]\).\qed
\end{lma}

\begin{lma}\label{PushDerived}\index{Derived ultrafilter!as a pushforward}
	Suppose \(W\) is an ultrafilter, \(I\) is a set in \(W\), and \(f : I\to X\)
	is a function. Then
	\[f_*(W) = W\text{-}\lim_{i\in I} \pr {f(i)} {X} = j_W^{-1}[\pr {[f]_W}
	{j_W(X)}]\] In other words, \(f_*(W)\) is the  ultrafilter on \(X\) derived
	from \(j_W\) using \([f]_W\).\qed
\end{lma}

These lemmas are trivial, but it turns out that many calculations are
significantly simpler when one treats limits and derived ultrafilters uniformly
as inverse images.

To be really pedantic, the reader might point out that for example in
\cref{PushDerived}, \(\pr {[f]_W} {j_W(X)}\) is not an \(M_W\)-ultrafilter but a
\(V\)-ultrafilter. Moreover if \(M_W\) is not wellfounded, then the statement
\([f]_W\in j_W(X)\) so \(\pr {[f]_W} {j_W(X)}\) is not well-defined. Of course,
\(\pr {[f]_W} {j_W(X)}\)  really denotes \((\pr {[f]_W} {j_W(X)})^{M_W}\). For
the reader's own sake, we will try to omit all these superscripts in our
notation for principal ultrafilters when they can be guessed from context. For
example, in \cref{PushDerived}, we would usually write: \[f_*(W) =
W\text{-}\lim_{i\in I} \pr {f(i)} {} = j_W^{-1}[\pr {[f]_W} {}]\]

The key to understanding derived ultrafilters is to consider the natural factor
embeddings associated to them. There is a generalization of the factor embedding
construction to the case of limits. In fact, this works somewhat more generally
for arbitrary inverse images of ultrafilters:

\begin{lma}\label{LimitFactor}\index{Factor embedding!associated to a limit}
Suppose \(N\) and \(P\) are transitive models of \textnormal{ZFC}, \(X\) is a
set in \(N\), \(i : N \to P\) is an elementary embedding, and \(D\) is a
\(P\)-ultrafilter on \(i(X)\). Let \(U = i^{-1}[D]\). There is a unique
elementary embedding \(k : M_U^N\to M^P_D\) such that \(k(\id_U) = \id_D\) and
\(k\circ j_U^N = j_D^P\circ i\).
\begin{proof}
For any function \(f\in N\) defined on a set in \(U\), set \[k([f]^N_U) =
[i(f)]^P_D\] It is immediate from this definiton that \(k(\id_U) = \id_D\) and
\(k\circ j_U^N = j_D^P\circ i\). We must show that \(k\) is well-defined and
elementary. This follows from the usual calculation:
\begin{align*}
M_U^N\vDash \varphi([f_1]^N_U,\dots,[f_n]^N_U)&\iff N\vDash \varphi(f_1(x),\dots,f_n(x))\text{ for \(U\)-almost all \(x\)}\\
&\iff P\vDash \varphi(i(f_1)(x),\dots,i(f_n)(x))\text{ for \(D\)-almost all \(x\)}\\
&\iff M_U^P\vDash \varphi([i(f_1)]_D^P,\dots,[i(f_n)]_D^P)\qedhere
\end{align*}
\end{proof}
\end{lma}
\section{The Ketonen order}\label{KetonenOrderSection}
\subsection{Characterizations of the Ketonen order}\label{KOCharsSection}
Let us begin our investigation of the Ketonen order with a purely combinatorial
definition.
\begin{defn}
	Suppose \(X\) is a set and \(A\) is a class. Then \(\mathscr B(X)\) denotes
	the set of countably complete ultrafilters on \(X\), and \(\mathscr
	B(X,A)\)\index{\(\mathscr B(X),\mathscr B(X,A)\) (countably complete
	ultrafilters on \(X\), concentrating on \(A\))} denotes the set of countably
	complete ultrafilters on \(X\) that concentrate on \(A\).
\end{defn}

\begin{defn}\label{KODef}
	Suppose \(\delta\) is an ordinal. The {\it Ketonen order}\index{Ketonen
	order} is defined on \(\mathscr B(\delta)\) as follows. For \(U,W\in
	\mathscr B(\delta)\):
	\begin{itemize}
		\item \(U\sE W\) if there is a set \(I\in W\) and a sequence \(\langle
		U_\alpha : \alpha \in I\rangle\in \prod_{\alpha\in I}\mathscr
		B(\delta,\alpha)\) such that \(U = W\text{-}\lim_{i\in I} U_\alpha\).
		\item \(U\E W\) if there is a set \(I\in W\) and a sequence \(\langle
		U_\alpha : \alpha \in I\rangle\in \prod_{\alpha\in I}\mathscr
		B(\delta,\alpha+1)\) such that \(U = W\text{-}\lim_{i\in I} U_\alpha\).
	\end{itemize}
\end{defn}
We refer to \(\sE\) and \(\E\) as the {\it strict} and {\it non-strict} Ketonen
orders.

Of course one could take \(I = \delta\setminus \{0\}\) in the first bullet-point
and \(I = \delta\) in the second, but the combinatorics are typically clearer if
one does not make this demand.

There is perhaps a potential ambiguity in our notation, since the order \(\sE\)
depends on the ordinal \(\delta\), which we suppress in our notation. This
dependence is always immaterial, however, since there are canonical embeddings
between the various Ketonen orders. These embeddings allow us to spin all these
orders together into one (\cref{GlobalKODef}).

Let us first explain the straightforward relationship between the strict and
nonstrict Ketonen orders.
\begin{prp}\label{StrictvsNonStrict}
	Suppose \(\delta\) is an ordinal and \(U,W\in \mathscr B(\delta)\). Then
	\(U\E W\) if and only if \(U \sE W\) or \(U = W\).
	\begin{proof}
		Let \(\langle U_\alpha : \alpha \in I\rangle\in \prod_{\alpha\in
		I}\mathscr B(\delta,\alpha+1)\) witness \(U\E W\). Let \[J = \{i\in I :
		U_\alpha\in \mathscr B(\delta,\alpha)\}\] If \(J\in W\), then \(\langle
		U_\alpha : \alpha \in J\rangle\in \prod_{\alpha\in J}\mathscr
		B(\delta,\alpha)\) witnesses \(U\sE W\).

		Assume therefore that \(J\notin W\). For all \(\alpha\in I\setminus J\),
		\(U_\alpha \in \mathscr B(\delta,\alpha+1)\setminus \mathscr
		B(\delta,\alpha)\). Note that \(\mathscr B(\delta,\alpha+1)\setminus
		\mathscr B(\delta,\alpha)\) contains only the principal ultrafilter
		\(\pr \alpha \delta\), and hence \(U_\alpha = \pr \alpha\delta\) for
		\(\alpha\in I\setminus J\). Thus
		\[U = W\text{-}\lim_{\alpha\in I}U_\alpha = W\text{-}\lim_{\alpha\in
		I\setminus J}\pr \alpha {} = W\] where the final equality follows easily
		from the definitions (or from \cref{PushDerived}).
	\end{proof}
\end{prp}

We therefore focus our attention on the strict Ketonen order \(\sE\) for now.
Before establishing its basic order-theoretic properties, let us give some
fairly obvious alternate characterizations of it. We think the characterization
\cref{KOChars} (2) is quite elegant in that it demonstrates a basic relationship
between the Ketonen order, the covering properties of ultrapowers, and
extensions of filter bases to countably complete ultrafilters, foreshadowing the
powerful interactions between strong compactness and the Ultrapower Axiom that
we will see in \cref{SCChapter1} and \cref{SCChapter2}. \cref{KOChars} (3) and
(4) are more useful, though, linking the Ketonen order and the Ultrapower Axiom
through the concept of a comparison (\cref{ComparisonDef}).
\begin{lma}\label{KOChars}
	Suppose \(\delta\) is an ordinal and \(U,W\in \mathscr B(\delta)\). The
	following are equivalent:
	\begin{enumerate}[(1)]
		\item \(U\sE W\).
		\item \(j_W[U]\) extends to an \(M_W\)-ultrafilter \(Z \in \mathscr
		B^{M_W}(j_W(\delta),\id_W)\).
		\item There is a comparison \((k,h) : (M_U,M_W)\to P\) of \((j_U,j_W)\)
		such that \(h\) is an internal ultrapower embedding of \(M_W\) and
		\(k(\id_U) < h(\id_W)\).
		\item There is a comparison \((k,h) : (M_U,M_W)\to P\) of \((j_U,j_W)\)
		such that \(h\) is close to \(M_W\) and \(k(\id_U) < h(\id_W)\).
	\end{enumerate}
\begin{proof}
	{\it (1) implies (2):} Fix \(I\in W\) and \(\langle U_\alpha : \alpha\in
	I\rangle\in \prod_{\alpha\in I}\mathscr B(\delta,\alpha)\) witnessing \(U\sE
	W\). Let \(Z = [\langle U_\alpha: \alpha\in I\rangle]_W\). By \L o\'s's
	Theorem, \(Z\in \mathscr B^{M_W}(j_W(\delta),\id_W)\), and by
	\cref{LimitInverse}, \(j_W^{-1}[Z] = W\text{-}\lim_{i\in I} U_i  = U\). This
	implies \(j_W[U]\subseteq Z\).

	{\it (2) implies (1):} Similar.

	{\it (2) implies (3):} Fix \(Z \in \mathscr B^{M_W}(j_W(\delta),\id_W)\)
	such that \(j_W[U]\subseteq Z\). Because of the basic structure of
	ultrafilters, the fact that \(j_W[U]\subseteq Z\) implies that \(j_W^{-1}[Z]
	= U\). Let \(h : M_W\to N\) be the ultrapower of \(M_W\) by \(Z\). Since
	\(Z\) concentrates on \(\id_W\), \(\id_Z < h(\id_W)\). By
	\cref{LimitFactor}, there is a unique elementary embedding \(k : M_U\to N\)
	such that \(k(\id_U) = \id_Z\) and \(k\circ j_U = h\circ j_W\). The former
	equation implies \(k(\id_U) < h(\id_W)\), while the latter equation says
	that \((k,h)\) is a comparison of \((j_U,j_W)\). Therefore (3) holds.

	{\it (3) implies (4):} Internal ultrapower embeddings are close.

	{\it (4) implies (2):} Let \(Z\) be the \(M_W\)-ultrafilter on
	\(j_W(\delta)\) derived from \(h\) using \(k(\id_U)\). Thus \(Z = h^{-1}[\pr
	{k(\id_U)} {}]\). (Here \(\pr {k(\id_U)} {}\) denotes the principal
	ultrafilter on \(k(j_U(\delta))\) concentrated at \(k(\id_U)\); see
	\cref{PrincipalDef} and the ensuing discussion.) Since \(h\) is close, \(Z\)
	belongs to \(M_W\), and since \(k(\id_U) < h(\id_W)\), \(Z\) concentrates on
	\(\id_W\). Thus \(Z\in \mathscr B^{M_W}(j_W(\delta),\id_W)\). Moreover,
	\[j_W^{-1}[Z] = j_W^{-1}[h^{-1}[\pr {k(\id_U)} {}]] =  j_U^{-1}[k^{-1}[\pr
	{k(\id_U)} {}]] = j_U^{-1}[\pr {\id_U} {}] = U\] In particular,
	\(j_W[U]\subseteq Z\), which shows (2).
\end{proof}
\end{lma}

Of course, there are identical characterizations for the nonstrict Ketonen order
as well:
\begin{lma}\label{NSKOChars}
	Suppose \(\delta\) is an ordinal and \(U,W\in \mathscr B(\delta)\). The
	following are equivalent:
	\begin{enumerate}[(1)]
		\item \(U\E W\).
		\item \(j_W[U]\) extends to an \(M_W\)-ultrafilter \(Z\in \mathscr
		B^{M_W}(j_W(\delta),\id_W+1)\).
		\item There is a comparison \((k,h) : (M_U,M_W)\to P\) of \((j_U,j_W)\)
		such that \(h\) is an internal ultrapower embedding of \(M_W\) and
		\(k(\id_U) \leq h(\id_W)\).
		\item There is a comparison \((k,h) : (M_U,M_W)\to P\) of \((j_U,j_W)\)
		such that \(h\) is close to \(M_W\) and \(k(\id_U) \leq h(\id_W)\).\qed
	\end{enumerate}
\end{lma}

\cref{KOChars} and \cref{NSKOChars} lead to the central linearity theorem for
the Ketonen order under UA:
\begin{thm}[UA]\label{Totality}\index{Ketonen order!linearity}
	Suppose \(\delta\) is an ordinal and \(U,W\in \mathscr B(\delta)\). Either
	\(U\sE W\) or \(W\E U\).
	\begin{proof}
		Let \((k,h) : (M_U,M_W)\to N\) be an internal ultrapower comparison of
		\((j_U,j_W)\). If \(k(\id_U) < h(\id_W)\), then \cref{KOChars} (3)
		implies \(U\sE W\). Otherwise, \(h(\id_W)\leq k(\id_U)\) and so \(W\E
		U\) by \cref{NSKOChars}.
	\end{proof}
\end{thm}

This linearity theorem is only interesting, of course, if we know that the
Ketonen order is ``well defined": if \(U \sE W\) and \(W\sE U\) held for all
\(U,W\in \mathscr B(\delta)\), it wouldn't be very useful. We now show that in
fact the Ketonen order is a wellfounded partial order.
\subsection{Basic properties of the Ketonen order}\label{BasicSection}
We state the main theorem of this section, which we will prove in pieces:
\begin{thm*}
	For any ordinal \(\delta\), \((\mathscr B(\delta),\sE)\) is a strict
	wellfounded partial order.
\end{thm*}

Thus we must show the following facts:
\begin{prp}\label{KOTransitive}
	For any ordinal \(\delta\), \(\sE\) is a transitive relation on \(\mathscr
	B(\delta)\).
\end{prp}

\begin{thm}\label{KOWellfounded}
	For any ordinal \(\delta\), \(\sE\) is a wellfounded relation on \(\mathscr
	B(\delta)\).
\end{thm}

Let us warm up to this by proving irreflexivity:
\begin{prp}\label{KOIrreflexive}
	For any ordinal \(\delta\), \(\sE\) is an irreflexive relation on \(\mathscr
	B(\delta)\).
	\begin{proof}
		Suppose towards a contradiction that \(U\in \mathscr B(\delta)\)
		satisfies \(U\sE U\). Fix \(I\in U\), and \(\langle U_\alpha : \alpha\in
		I\rangle\in \prod_{\alpha\in I}  \mathscr B(\delta,\alpha)\) such that
		\[U = U\text{-}\lim_{\alpha\in I}U_\alpha\] Define \(A\subseteq \delta\)
		by induction: put \(\alpha\in A\) if and only if \(A\cap\alpha\notin
		U_\alpha\). Then \begin{align*}A\in U&\iff \{\alpha \in I : A\in
		U_\alpha\}\in U\\
			&\iff \{\alpha\in I : A\cap \alpha\in U_\alpha\} \in U\\ &\iff
			\{\alpha\in I : \alpha\notin A\}\in U\\
			&\iff I\setminus A\in U\end{align*} Since \(I\in U\) and \(U\) is an
		ultrafilter, either \(A\) or \(I\setminus A\) must belong to \(U\). Thus
		both belong to \(U\), contradicting that \(U\) is closed under
		intersections.
	\end{proof}
\end{prp}

Notice that the proof does not use the wellfoundedness of \(U\). We now give two
proofs of the transitivity of the Ketonen order.
\begin{proof}[Proof of \cref{KOTransitive}] Suppose \(U\sE W \E Z\). We will
	show that \(U\sE Z\). Fix the following objects:
	\begin{itemize}
		\item A set \(I\in W\) and a sequence \(\langle U_\alpha : \alpha\in
		I\rangle\in \prod_{\alpha\in I}\mathscr B(\delta,\alpha)\) such that \(U
		= W\text{-}\lim_{\alpha\in I} U_\alpha\).
		\item A set \(J\in Z\) and a sequence \(\langle W_\beta : \beta\in
		J\rangle\in \prod_{\beta\in J}\mathscr B(\delta,\beta)\) such that \(W=
		Z\text{-}\lim_{\beta\in J} Z_\beta\).
	\end{itemize}

	Since \(I\in W = Z\text{-}\lim_{\beta\in J} W_\alpha\), the set \(J' =
	\{\beta\in J : I\in W_\beta\}\) belongs to \(Z\). For \(\beta\in J'\), we
	can define \(U'_\beta = W_\beta\text{-}\lim_{\alpha\in I} U_\alpha\). Thus:
	\begin{align*}
		U &= W\text{-}\lim_{\alpha\in I} U_\alpha\\
			&= (Z\text{-}\lim_{\beta\in J} W_\alpha)\text{-}\lim_{\alpha\in I} U_\alpha\\
			&= Z\text{-}\lim_{\beta\in J'} (W_\alpha\text{-}\lim_{\alpha\in I} U_\alpha)\\
			&= Z\text{-}\lim_{\beta\in J'}U_\alpha'
	\end{align*}

	Finally, if \(\beta\in J'\), then \(\{\alpha\in I : U_\alpha\in \mathscr
	B(\delta,\beta)\}\supseteq I\cap (\beta + 1)\in W_\beta\), so \[\langle
	U'_\beta : \beta\in J'\rangle\in \prod_{\beta\in J'} \mathscr
	B(\delta,\beta)\] Therefore \(\langle U'_\beta : \beta\in J'\rangle\)
	witnesses \(U\sE Z\).
\end{proof}

We are still just warming up, so let us give another proof of the transitivity
of the Ketonen order that is more diagrammatic:
\begin{proof}[Alternate Proof of \cref{KOTransitive}] Using \cref{KOChars}, fix
	the following objects:
	\begin{itemize}
		\item A comparison \((k_0,h_0): (M_U,M_W)\to N_0\) of \((j_U,j_W)\) such
		that \(h_0\) is an internal ultrapower embedding of \(M_W\) and
		\(k_0(\id_U) < h_0(\id_W)\).
		\item A comparison \((k_1,h_1) : (M_W,M_Z)\to N_1\) of \((j_W,j_Z)\)
		such that \(h_1\) is an internal ultrapower embedding of \(M_Z\) and
		\(k_1(\id_W)\leq h_1(\id_Z)\).
	\end{itemize}

	The rest of the proof is contained in \cref{KOTransitiveFig}.
	\begin{figure}
	\center
	\includegraphics[scale=.6]{KOTransitive.pdf}
	\caption{The transitivity of the Ketonen order}\label{KOTransitiveFig}
	\end{figure}
	Consider the embeddings \(h_0 : M_W\to N_0\) and \(k_1 : M_W\to N_1\). There
	is a very general construction that yields a comparison of \((h_0,k_1)\).
	Since \(h_0\) is amenable to \(M_W\), one can define \(k_1(h_0) : N_1\to
	k_1(N_0)\) by shifting the fragments of \(h_0\) using \(k_1\). The
	well-known identity \((k_1\restriction N_0)\circ h_0 = k_1(h_0)\circ k_1\)
	implies that \((k_1\restriction N_0,k_1(h_0)) : (N_0,N_1)\to k_1(N_0)\) is a
	comparison of \((h_0,k_1)\).

	It follows easily that \(((k_1\restriction N_0)\circ k_0,k_1(h_0)\circ
	h_1)\) is a comparison of \((j_U,j_Z)\). Easily \(k_1(h_0)\circ h_0\) is an
	internal ultrapower embedding of \(M_Z\). Finally \[(k_1\restriction
	N_0)\circ k_0(\id_U) < (k_1\restriction N_0)\circ h_0(\id_W) = k_1(h_0)
	\circ k_1(\id_W) \leq k_1(h_0)\circ h_1(\id_Z)\] Thus \(U\sE Z\) by
	\cref{KOChars}.
\end{proof}

We finally turn to wellfoundedness. We will give a combinatorial proof, but the
reader can consult \cref{ExtendedKetonen} for a diagrammatic approach in a more
general context. The proof proceeds by iterating the following {\it strong
transitivity lemma} for the Ketonen order, abstracted from the proof of
\cref{KOTransitive}:
\begin{lma}\label{StrongTrans}\index{Ketonen order!strong transitivity}
	Suppose \(\delta\) is an ordinal, \(U,W\in \mathscr B(\delta)\), and \(U\sE
	W\). Suppose \(Z\) is an ultrafilter, \(J\) is a set in \(Z\), and \(\{ W_x
	: x\in J\} \subseteq\mathscr B(\delta)\) is a sequence such that \[W =
	Z\text{-}\lim_{x\in J}W_x\] Then there is a set \(J'\subseteq J\) in \(Z\)
	and \(\{ U_x : x\in J'\}\subseteq \mathscr B(\delta)\) with \(U_x\sE W_x\)
	for all \(x\in J'\) such that
	\[U = Z\text{-}\lim_{x\in J'} U_x\]
	\begin{proof}[Sketch] Fix \(I\in W\) and \(\langle U_\alpha : \alpha\in
		I\rangle\in \prod_{\alpha\in I} \mathscr B(\delta,\alpha)\) such that
		\(U = W\text{-}\lim_{\alpha\in I} U_\alpha\). Let \(J' = \{x\in J : I\in
		W_x\}\). For \(x\in J'\), let \(U_x = W_x\text{-}\lim_{\alpha\in I}
		U_\alpha\). Then \(\langle U_\alpha : \alpha\in I\rangle\) witnesses
		that \(U_x\sE W_x\). Moreover the calculation in \cref{KOTransitive}
		shows that \(U = Z\text{-}\lim_{x\in J'} U_x\).
	\end{proof}
\end{lma}

This is more elegantly stated using elementary embeddings:
\begin{lma}
	Suppose \(\delta\) is an ordinal, \(U,W\in \mathscr B(\delta)\), and \(U\sE
	W\). Suppose \(j : V\to M\) is an elementary embedding and \(W_*\in
	j(\mathscr B(\delta))\) extends \(j[W]\). Then there is some \(U_*\in
	j(\mathscr B(\delta))\) extending \(j[U]\) such that \(M\vDash U_*\sE
	W_*\).\qed
\end{lma}

Recall now the notation \(U\mid C\) from \cref{UltrafilterConcentration},
denoting the projection of an ultrafilter \(U\) to a set \(C\) on which it
concentrates. We will need the following trivial lemma, which is also implicit
in the proof of \cref{KOTransitive}:
\begin{lma}\label{KetonenProjection}
	Suppose \(\epsilon\) and \(\delta\) are ordinals, \(U\in \mathscr
	B(\delta)\), and \(W\in \mathscr B(\delta,\epsilon)\). If \(U\E W\), then
	\(U\in \mathscr B(\delta,\epsilon)\) and \(U\mid \epsilon \E W\mid
	\epsilon\) in the Ketonen order on \(\mathscr B(\epsilon)\).
	\begin{proof}
		Fix \(I\in W\) and \(\langle U_\alpha : \alpha\in I\rangle\in \prod
		\mathscr B(\delta,\alpha)\) such that \(U = W\text{-}\lim_{\alpha\in I}
		U_\alpha\). Then since \(U = W\text{-}\lim_{\alpha\in I} U_\alpha =
		W\text{-}\lim_{\alpha\in I\cap \epsilon} U_\alpha\) is a limit of
		ultrafilters concentrating on \(\epsilon\), so \(U\) itself concentrates
		on \(\epsilon\). Moreover \(\langle U_\alpha\mid \epsilon : \alpha\in
		I\cap \epsilon\rangle\) witnesses that \(U\mid \epsilon \sE W\mid
		\epsilon\) in the Ketonen order on \(\mathscr B(\epsilon)\).
	\end{proof}
\end{lma}

As we prove \cref{KOWellfounded}, the reader may profit from the observation
that the proof consists of the combinatorial core of the proof of the
wellfoundedness of the Mitchell order on normal ultrafilters, stripped of all
applications of normality and \L o\'s's Theorem.
\begin{proof}[Proof of \cref{KOWellfounded}]\index{Ketonen order!wellfoundedness}
	Assume towards a contradiction that there is an ordinal \(\delta\) such that
	\(\sE\) is illfounded on \(\mathscr B(\delta)\). Fix the least such
	\(\delta\). Choose a sequence \(\{ U_n : n < \omega\}\subseteq  \mathscr
	B(\delta)\) that is \(\sE\)-descending:
	\[U_0\sgE U_1 \sgE U_2 \sgE\cdots\]

	For each positive number \(n\), we will define by recursion a set \(J_n\in
	U_0\) and a sequence of ultrafilters \(\langle U^n_\alpha : \alpha\in
	J_n\rangle\in \prod_{\alpha\in J_n} \mathscr B(\delta,\alpha)\) such that
	for all \(n < \omega\), the following hold:
	\begin{itemize}
		\item \(U_n = U\text{-}\lim_{\alpha\in J_n} U^n_\alpha\).
		\item If \(n > 1\), then \(J_n\subseteq J_{n-1}\) and for all
		\(\alpha\in J_{n}\), \(U^{n}_\alpha \sE U^{n-1}_\alpha\).
	\end{itemize}
	To start, fix \(J_1\in U_0\) and \(\langle U^1_\alpha : \alpha\in
	J_1\rangle\in \prod_{\alpha\in J_1} \mathscr B(\delta,\alpha)\) witnessing
	that \(U_1\sE U_0\); that is,
	\[U_1 = U_0\text{-}\lim_{\alpha\in J_1} U_\alpha^1\] Suppose \(n > 1\) and
	\(J_{n-1}\in U_0\) and \(\langle U^{n-1}_\alpha : \alpha\in
	J_{n-1}\rangle\in \prod_{\alpha\in J_{n-1}} \mathscr B(\delta,\alpha)\) have
	been defined so that \(U_{n-1} = U\text{-}\lim_{\alpha\in J_{n-1}}
	U^{n-1}_\alpha\). \cref{StrongTrans} (with \(U = U_{n}\), \(W = U_{n-1}\),
	and \(Z = U_0\)) yields \(J_{n}\subseteq J_{n-1}\) and \(\{U^{n}_\alpha :
	\alpha \in J_n\}\subseteq \mathscr B(\delta)\) such that the two bullet
	points above are satisfied. We must verify that \(\langle U^{n}_\alpha :
	\alpha\in J_n\rangle\in \prod_{\alpha\in J_n} \mathscr B(\delta,\alpha)\).
	But for any \(\alpha\in J^n\), \(U^n_\alpha \sE U^{n-1}_\alpha\in \mathscr
	B(\delta,\alpha)\), and therefore \(U^n_\alpha\in \mathscr
	B(\delta,\alpha)\) by \cref{KetonenProjection}, as desired. This completes
	the recursive definition.

	Now let \(J = \bigcap_{n < \omega} J_n\). For any \(\alpha\in J\), we have
	\[U^1_\alpha\sgE U^2_\alpha \sgE U^3_\alpha \sgE\cdots\] by the second
	bullet point above. Since \(U^n_\alpha\in \mathscr B(\delta,\alpha)\) for
	all \(n < \omega\), \cref{KetonenProjection} implies \[U^1_\alpha\mid \alpha
	\sgE U^2_\alpha\mid \alpha \sgE U^3_\alpha\mid \alpha\sgE \cdots \] Thus the
	restriction of \(\sE\) to \(\mathscr B(\alpha)\) is illfounded. This
	contradicts the minimality of \(\delta\).
\end{proof}
Observe that the proof of \cref{KOWellfounded} goes through in ZF + DC. The
structure of countably complete ultrafilters on ordinals is of great interest in
the context of the Axiom of Determinacy, and so the existence of a combinatorial
analog of the Mitchell order in that context raises a number of very interesting
structural questions that we will not pursue seriously in this dissertation.
\subsection{The global Ketonen order}
\cref{KetonenProjection} above suggests extending the Ketonen order to an order
on ultrafilters that is agnostic about the underlying sets of the ultrafilters
involved:
\begin{defn}\label{GlobalKODef}
	Suppose \(U\) and \(W\) are countably complete ultrafilters on ordinals. The
	(global) {\it Ketonen order}\index{Ketonen order!global} is defined as
	follows:
	\begin{itemize}
		\item \(U\sE W\) if \(U\mid \delta\sE W\mid \delta\).
		\item \(U\E W\) if \(U\mid \delta\E W\mid \delta\).
	\end{itemize}
	where \(\delta\) is any ordinal such that \(U\) and \(W\) both concentrate
	on \(\delta\).
\end{defn}

By \cref{KetonenProjection}, this definition does not conflict with our original
definition of the Ketonen order on \(\mathscr B(\delta)\). In fact, various
characterizations of the Ketonen order from \cref{KOChars} translate smoothly to
this context:

\begin{lma}\label{GlobalKOChars}
	Suppose \(\epsilon\) and \(\delta\) are ordinals, \(U\in \mathscr
	B(\epsilon)\), and \(W\in \mathscr B(\delta)\). Then the following are
	equivalent:
	\begin{enumerate}[(1)]
		\item \(U\sE W\).
		\item There exist \(I\in W\) and \(\langle U_\alpha : \alpha \in
		I\rangle\in \prod _{\alpha \in I}\mathscr B(\epsilon, \alpha)\) such
		that \(U = W\text{-}\lim_{\alpha\in I}U_\alpha\).
		\item \(j_W[U]\subseteq Z\) extends to an \(M_W\)-ultrafilter \(Z\in
		\mathscr B^{M_W}(j_W(\epsilon), \id_W)\).
		\item There is a comparison \((k,h) : (M_U,M_W)\to P\) of \((j_U,j_W)\)
		such that \(h\) is an internal ultrapower embedding of \(M_W\) and
		\(k(\id_U) < h(\id_W)\).
		\item There is a comparison \((k,h) : (M_U,M_W)\to P\) of \((j_U,j_W)\)
		such that \(h\) is close to \(M_W\) and \(k(\id_U) < h(\id_W)\).\qed
	\end{enumerate}
\end{lma}

We have the following simple relationship between the space of an ultrafilter
and its position in the Ketonen order:
\begin{lma}\label{SpaceLemma}
	Suppose \(U\) and \(W\) are countably complete ultrafilters on ordinals.
	\begin{itemize}
		\item If \(\delta_U < \delta_W\), then \(U\sE W\).
		\item If \(U\E W\), then \(\delta_U \leq \delta_W\).
	\end{itemize}
	\begin{proof}
		To see the first bullet point, note that for any \(\alpha\in
		[\delta_U,\delta_W)\), \(\alpha \geq \delta_U\) and hence \(U\)
		concentrates on \(\alpha\). Thus the constant sequence \(\langle U :
		\alpha \in [\delta_U,\delta_W)\rangle\) belongs to \(\prod _{\alpha \in
		[\delta_U,\delta_W)}\mathscr B(\epsilon, \alpha)\), and clearly \(U =
		W\text{-}\lim_{\alpha\in [\delta_U,\delta_W)}U\). By
		\cref{GlobalKOChars}, \(U\sE W\).

		The second bullet point is immediate from \cref{KetonenProjection}.
	\end{proof}
\end{lma}

The one issue with the global Ketonen order, which presents only notational
difficulties, is that in this generalized context, \(\E\) is no longer the
irreflexive part of \(\sE\). Instead we have the following fact, where \(\KE\)
is the change-of-space relation defined in \cref{EmbeddingEquivalenceDef}:

\begin{lma}\label{StrictvsNonStrict2}
	Suppose \(U\) and \(W\) are countably complete ultrafilters on ordinals.
	Then \(U\E W\) if and only if \(U\sE W\) or \(U \KE W\).\qed
\end{lma}

Since the \(\KE\)-relation convenient to restrict the global Ketonen order to
the class of tail uniform ultrafilters \(\Un\):
\begin{lma}\label{StrictvsNonStrictUn}
	Suppose \(U, W\in \Un\). Then \(U\E W\) if and only if \(U\sE W\) or \(U =
	W\).
\end{lma}

\begin{defn}
	For any ordinal \(\delta\), let \(\Un(\delta)\) denote the set of tail
	uniform ultrafilters \(U\) such that \(\delta_U\leq \delta\).
\end{defn}

\begin{lma}\label{KOUnGood}
	For all ordinals \(\delta\), the map \(\phi : \mathscr B(\delta)\to
	\Un(\delta)\) defined by \(\phi(U) = U\mid \delta_U\) is an isomorphism from
	\((\mathscr B(\delta), \sE, \E)\) to \((\Un(\delta),\sE, \E)\). Thus the
	Ketonen order is a set-like wellfounded partial order on \(\Un\).\qed
\end{lma}

The following easy lemma generalizes our work in this section, showing that not
only do the various Ketonen orders on \(\mathscr B(\delta)\) cohere, but in
fact, order-preserving maps between ordinals induce order-preserving maps on
their associated Ketonen orders:

\begin{lma}\label{Functorial}
	Suppose \(\epsilon\leq \delta\) are ordinals and \(f : \epsilon\to \delta\)
	is an increasing function. For any \(U,W\in \mathscr B(\epsilon)\), \(U\sE
	W\) in the Ketonen order on \(\mathscr B(\epsilon)\) if and only if
	\(f_*(U)\sE f_*(W)\) in the Ketonen order on \(\mathscr B(\delta)\).
	\begin{proof}[Sketch] Fix \(I\in W\) and \(\langle U_\alpha : \alpha \in
		I\rangle\in \prod_{\alpha\in I}\mathscr B(\epsilon,\alpha)\) such that
		\(U = W\text{-}\lim_{\alpha\in I} U_\alpha\). Let \(J = f[I]\), and for
		\(\alpha \in I\), let \(Z_{f(\alpha)}= f_*(W_\alpha)\). Thus \(J\in
		f_*(W)\). Moreover, for all \(\alpha\in I\), \(f(\alpha)\supseteq
		f[\alpha]\in Z_{f(\alpha)}\) since \(f\) is increasing, so
		\(Z_{f(\alpha)}\in \mathscr B(\delta,f(\alpha))\). Thus \(\langle
		Z_\beta:\beta\in J\rangle\in \prod_{\beta\in J}\mathscr
		B(\delta,\beta)\). Finally \[f_*(U) = W\text{-}\lim_{\alpha\in I}
		f_*(W_\alpha) = f_*(W)\text{-}\lim_{\beta\in f[I]} Z_\alpha\] It follows
		that \(f_*(U)\sE f_*(W)\). The other direction is similar.
	\end{proof}
\end{lma}
\section{Orders on ultrafilters}\label{OtherOrderSection}
In this section, we discuss some generalizations of the Ketonen order and
compare the Ketonen order with other well-known orders.

\subsection{The Mitchell order}\label{MOKetSection}
The Ketonen order can be seen as a combinatorial generalization of the Mitchell
order on normal ultrafilters. We will discuss the relationship between the
Ketonen order and the generalization of the Mitchell order to arbitrary
countably complete ultrafilters at length in \cref{GMOChapter}, but for now, we
satisfy ourselves by proving that the Ketonen and Mitchell orders coincide on
normal ultrafilters.
\begin{thm}\label{KetMO}
Suppose \(U\) and \(W\) are normal ultrafilters. Then \(U\mo W\) if and only if
\(U\sE W\).\index{Ketonen order!vs. the Mitchell order}
\begin{proof}
Suppose first that \(U\) and \(W\) are normal ultrafilters on distinct cardinals
\(\kappa\) and \(\lambda\). Clearly \(U\mo W\) if and only if \(\kappa <
\lambda\). Moreover by \cref{SpaceLemma}, \(U\sE W\) if and only if \(\kappa <
\lambda\). Thus \(U\mo W\) if and only if \(U\sE W\).

Assume instead that \(U\) and \(W\) lie on the same cardinal \(\kappa\). By
\cref{NormalChar}, \(U\) and \(W\) are \(\kappa\)-complete and \(\kappa  = \id_U
= \id_W\). The key fact we use is that since \(\textsc{crt}(j_W) = \kappa\),
\(j_W(A)\cap \kappa = A\) for all \(A\subseteq \kappa\).

Suppose first that \(U\mo W\). Then \(U\in M_W\). Working in \(M_W\), consider
the projection \(Z = U\mid j_W(\kappa)\in \mathscr B^{M_W}(j_W(\kappa),
\kappa)\). For any \(A\subseteq \kappa\), \(j_W(A)\cap \kappa = A\in U\), or in
other words, \(j_W(A)\in Z\). In other words, \(j_W[U]\subseteq Z\), so by
\cref{KOChars}, \(U\mo W\).

Conversely, suppose \(U\sE W\). Fix \(Z\in \mathscr B^{M_W}(j_W(\kappa),
\kappa)\) such that \(U = j_W^{-1}[Z]\). Suppose \(A\subseteq \kappa\). Then
\(A\in U\) if and only if \(j_W(A)\cap \kappa\in Z\) if and only if \(A\in Z\).
Therefore \(U = Z\mid \kappa\), so \(U\in M_W\). This implies \(U\mo W\).
\end{proof}
\end{thm}

Thus the wellfoundedness of the Mitchell order follows from the wellfoundedness
of the Ketonen order. Notice that this theorem gives another proof of the
linearity of the Mitchell order on normal ultrafilters under UA. Finally, the
proof has the following consequence:
\begin{cor}
	Suppose \(\kappa\) is a cardinal, \(U\in \mathscr B(\kappa)\), and \(W\) is
	a normal ultrafilter on \(\kappa\). Then \(U\sE W\) if and only if \(U\mo
	W\).\qed
\end{cor}
Thus the Ketonen predecessors of a normal ultrafilter \(W\) on \(\kappa\) are
precisely \(\mathscr B(\kappa)\cap M_W\). We will see various nontrivial
generalizations of this fact to more general types of ultrafilters than normal
ones.

\subsection{The Rudin-Keisler order}\label{RKSection}
In this section, we briefly recall the theory of the Rudin-Keisler order and
explain its relationship with the Ketonen order. We also introduce the notion of
an {\it incompressible ultrafilter}, which will be a useful technical tool.

The Rudin-Keisler order is defined in terms of pushforward ultrafilters
(\cref{PushDef}).

\begin{defn}
Suppose \(U\) and \(W\) are ultrafilters. The {\it Rudin-Keisler order} is
defined by setting \(U\RK W\) if there is a function \(f : I \to X\) such that
\(f_*(W) = U\) where \(I\in W\) and \(X\) is the underlying set of
\(U\).\index{Rudin-Keisler order}
\end{defn}

We could of course take \(I\) to be the underlying set of \(W\) above. The
Rudin-Keisler order is a (nonstrict) preorder on the class of ultrafilters. For
us, the most important characterization of the Rudin-Keisler order uses
elementary embeddings:
\begin{lma}\label{RKChar}
Suppose \(U\) and \(W\) are ultrafilters. Then \(U\RK W\) if and only if there
is an elementary embedding \(k : M_U\to M_W\) such that \(k\circ j_U = j_W\).
\begin{proof}
Let \(X\) be the underlying set of \(U\).

First assume \(U\RK W\). Fix \(I\in W\) and \(f : I\to X\) such that \(f_*(W) =
U\). Let \(a = [f]_W\), so by \cref{PushDerived}, \(U\) is the ultrafilter on
\(X\) derived from \(j_W\) using \(a\). Let \(k : M_U\to M_W\) be the factor
embedding, so \(k(\id_U) = a\) and \(k\circ j_U = j_W\). Then \(k\) witnesses
the conclusion of the lemma.

Conversely, assume there is an elementary embedding \(k : M_U\to M_W\) such that
 \(k\circ j_U = j_W\). Let \(b = k(\id_U)\). Then \(b\in j_W(X)\). On the one
 hand, \(U\) is equal to the ultrafilter on \(X\) derived from \(j_W\) using
 \(b\). (Explicitly: \(U = j_U^{-1}[\pr {\id_U} {}] = j_U^{-1}[k^{-1}[k(\pr
 {\id_U} {})]] = j_W^{-1}[\pr b {}]\).) Fix \(I\in W\) and \(f : I\to X\) such
 that \([f]_W = b\). Then by \cref{PushDerived}, \(f_*(W)\) is the ultrafilter
 on \(X\) derived from \(j_W\) using \(b\), or in other words \(f_*(W) = U\).
 Thus \(U\RK W\) as desired.
\end{proof}
\end{lma}

A second combinatorial formulation of the Rudin-Keisler order is in terms of
partitions which will become relevant when we study indecomposability
(especially in \cref{Silver}):
\begin{lma}\label{RKPartitionChar}
Suppose \(U\) and \(W\) are ultrafilters. Let \(X\) be the underlying set of
\(U\). Then \(U\RK W\) if and only if there is a sequence of pairwise disjoint
sets \(\langle Y_x : x\in X\rangle\) such that \(U = \textstyle\left\{A\subseteq
X: \bigcup_{x\in A} Y_x\in W\right\}\).\qed
\end{lma}
The following is the fundamental theorem of the Rudin-Keisler order:
\begin{thm}\label{RKThm}
Suppose \(U\) and \(W\) are ultrafilters. Then  \(U\cong W\) if and only if
\(U\RK W\) and \(W\RK U\).
\end{thm}
We sketch the proof even though we do not need it in what follows. This involves
a very interesting rigidity theorem for pushforwards:
\begin{lma}\label{PushRigid}
Suppose \(U\) is an ultrafilter on \(X\) and \(f : X\to X\) is a function. If
\(f_*(U) = U\) then \(f(x) = x\) for \(U\)-almost all \(x\in X\).
\begin{proof}
Assume \(f : X\to X\) is such that \(f(x)\neq x\) for all \(x\in X\). We will
show that \(f_*(U)\neq U\).

\begin{clm*} There is a partition \(X = A_0\cup A_1\cup A_2\) such that \(f[A_n] \subseteq X\setminus A_n\) for \(n = 0,1,2\). \end{clm*}
\begin{proof}[Sketch]Consider the directed graph \(G\) with vertices \(X\) and a directed edge from \(x\) to \(f(x)\) for each \(x\in X\). Our claim above amounts to the fact that \(G\) is 3-colorable. It suffices to show that each connected subgraph \(H\subseteq G\) is 3-colorable. Therefore suppose \(H\) is a connected subgraph of \(G\). The key point is that \(H\) contains at most one cycle (since \(G\) is a ``functional graph"), so one obtains an acyclic graph \(H'\) by removing an edge of \(H\) if necessary. Since \(H'\) is acyclic, \(H'\) is 2-colorable. By changing the color of at most one vertex in the coloring of \(H'\), one obtains a \(3\)-coloring of \(H\).\end{proof}
Since \(A_0\cup A_1\cup A_2 = X\in U\), either \(A_0,A_1,\) or \(A_2\) belongs
to \(U\). Assume without loss of generality that \(A_0\in U\). Then \(X\setminus
A_0\supseteq f[A_0] \in f_*(U)\), so \(X\setminus A_0\in f_*(U)\) as desired.
\end{proof}
\end{lma}

Let us reformulate this in terms of ultrapowers:
\begin{thm}\label{RKRigid}
	Suppose \(U\) is an ultrafilter and \(k : M_U\to M_U\) is an elementary
	embedding such that \(k\circ j_U = j_U\). Then \(k\) is the identity.
	\begin{proof}
		Let \(X\) be the underlying set of \(U\). Fix \(X\in U\) and a function
		\(f : X\to X\) such that \([f]_U = k(\id_U)\). Then by
		\cref{PushDerived}, \(f_*(U)\) is the ultrafilter on \(X\) derived from
		\(j_U\) using \(k(\id_U)\), which is easily seen to equal \(U\). (Yet
		another inverse image calculation: \(j_U^{-1}[\pr {k(\id_U)} {}] =
		(k\circ j_U)^{-1}[\pr {k(\id_U)} {}] = j_U^{-1}[k^{-1}[\pr {k(\id_U)}
		{}]] = j_U^{-1}[\pr {\id_U} {}] = U\).) Therefore by \cref{PushRigid},
		\(f\restriction I = \text{id}\) for some \(I\in U\). Thus \(k(\id_U) =
		[f]_U = \id_U\). It follows that \(k\restriction j_U[V]\cup \{\id_U\}\)
		is the identity, so \(k\restriction M_U\) is the identity since \(M_U =
		H^{M_U}(j_U[V]\cup \{\id_U\})\).
	\end{proof}
\end{thm}

\cref{PushRigid} immediately implies \cref{RKThm}:

\begin{proof}[Proof of \cref{RKThm}] Let \(X\) be the underlying set of \(U\)
and \(Y\) be the underlying set of \(W\). The trivial direction is to prove that
\(U\cong W\) implies \(U\RK W\) and \(W\RK U\). Fix \(I\in U\), \(J\in W\), and
a bijection \(f : I\to J\) such that for all \(A\subseteq I\), \(A\in U\) if and
only if \(f[A]\in W\). Viewing \(f\) as a function \(p : I\to Y\), we have \(W =
p_*(U)\). Viewing \(f^{-1}\) as a function \(p : J\to X\), we have \(U =
p_*(W)\). This implies implies \(W\RK U\) and \(U\RK W\).

Conversely assume \(U\RK W\) and \(W\RK U\). Fix \(I\in U\) and \(f : I\to Y\)
such that \(f_*(U) = W\). Fix \(J \in W\) and \(g: J\to X\) such that \(g_*(W)=
U\). We claim there is a set \(I'\subseteq I\) such that \(I'\in U\) and
\(g\circ f\restriction I'\) is the identity. To see this, note that \((g\circ
f)_*(U) = g_*(f_*(U)) = g_*(W) = U\). Therefore by \cref{PushRigid}, there is a
set \(I'\subseteq I\) such that \(I'\in U\) and \(g\circ f\) is the identity.
\end{proof}

\cref{RKThm} motivates the following definition:

\begin{defn}\index{Rudin-Keisler order!strict}
The {\it strict Rudin-Keisler order} is defined on ultrafilters \(U\) and \(W\)
by setting \(U\sRK W\) if \(U\RK W\) and \(W\not \cong U\).
\end{defn}

We now discuss the structure of the Rudin-Keisler order on countably complete
ultrafilters and its relationship to the Ketonen order. To facilitate this
discussion, we introduce a revised version of the Rudin-Keisler order. Recall
that a function \(f\) defined on a set of ordinals \(I\) is {\it regressive} if
\(f(\alpha) < \alpha\) for all \(\alpha\in I\).
\begin{defn}\label{rRKDef}\index{Rudin-Keisler order!revised}
Suppose \(U\) and \(W\) are ultrafilters on ordinals. Let \(X\) be the
underlying set of \(U\). The {\it revised Rudin-Keisler order} is defined by
setting \(U\rRK W\) if there is a set \(I\in W\) and a regressive function \(f :
I \to X\) such that \(f_*(W) = U\).
\end{defn}

\begin{lma}\label{rRKEmbedding}
If \(U\) and \(W\) are ultrafilters on ordinals, then \(U\rRK W\) if and only if
there is an elementary embedding \(k : M_U\to M_W\) such that \(k\circ j_U =
j_W\) and \(k(\id_U) < \id_W\).\qed
\end{lma}

\begin{cor}
The Ketonen order and the Rudin-Keisler order extend the revised Rudin-Keisler
order.\qed
\end{cor}

\begin{lma}\label{rRKLinear}
For any ultrafilter \(U\), the collection of tail uniform ultrafilters
isomorphic to \(U\) is linearly ordered by the revised Rudin-Keisler order.
\begin{proof}
Suppose \(W_0\cong U\cong W_1\) are tail uniform ultrafilters. Then \(W_0\rRK
W_1\) if and only if \(M_U\vDash \id_{W_0} < \id_{W_1}\).
\end{proof}
\end{lma}

We now introduce a concept that is very useful in the study of countably
complete ultrafilters. (The same concept was considered by Ketonen
\cite{Ketonen2}, who called them normalized ultrafilters.)

\begin{defn}
A tail uniform ultrafilter \(U\) on an ordinal \(\lambda\) is {\it
incompressible} if for any set \(I\in U\), no regressive function on \(I\) is
one-to-one.\index{Incompressible ultrafilter}
\end{defn}

\begin{lma}\label{IncomRK0}
Suppose \(U\) is tail uniform. The following are equivalent:
\begin{enumerate}[(1)]
\item \(U\) is incompressible.
\item If \(W \rRK U\), then \(W\sRK U\).\qed
\end{enumerate}
\end{lma}

\begin{lma}
A tail uniform ultrafilter \(U\) is incompressible if and only if it is the
\(\rRK\)-minimum element of \(C = \{U'\in \Un : U'\cong U\}\).
\begin{proof}
By \cref{IncomRK0}, \(U\) is an \(\rRK\)-minimal element of \(C\). Since
\(\rRK\) linearly orders \(C\) by \cref{rRKLinear}, \(U\) is the
\(\rRK\)-minimum element of \(C\).
\end{proof}
\end{lma}

\begin{cor}
An ultrafilter is isomorphic to at most one incompressible ultrafilter.\qed
\end{cor}

\begin{lma}\label{IncomPower}
Suppose \(U\) is tail uniform ultrafilter on \(\delta\). Then the following are
equivalent:
\begin{enumerate}[(1)]
\item \(U\) is incompressible.
\item \(\id_U\) is the least ordinal \(a\) of \(M_U\) such that \(M_U =
H^{M_U}(j_U[V]\cup \{a\})\).
\item \(\id_U\) is the largest ordinal \(a\) of \(M_U\) such that \(a\neq
j_U(f)(b)\) for any function \(f :\delta\to \delta\) and \(b < a\).\qed
\end{enumerate}
\end{lma}

If \(U\) is countably complete, then the collection of tail uniform ultrafilters
isomorphic to \(U\) is {\it wellordered} by \(\rRK\), and therefore it has a
minimum element. The following is the key existence theorem for incompressible
ultrafilters:
\begin{lma}
Any countably complete ultrafilter \(U\) is isomorphic to a unique
incompressible ultrafilter \(W\) which can be obtained in any of the following
ways:
\begin{itemize}
\item \(W\) is the \(\rRK\)-minimum element of the isomorphism class of \(U\).
\item \(W = f_*(U)\) where \(f : \delta_U\to\delta_U\) is the least one-to-one
function modulo \(U\).
\item \(W\) is the tail uniform ultrafilter derived from \(j_U\) using
\(\alpha\) where \(\alpha\) is the ordinal defined in either of the following
ways:
\begin{itemize}
\item \(\alpha\) is least such that \(M_U = H^{M_U}(j_U[V]\cup \{\alpha\})\).
\item \(\alpha\) is largest such that \(\alpha\neq j_U(f)(\beta)\) for any
\(\beta < \alpha\).\qed
\end{itemize}
\end{itemize}
\end{lma}

What makes incompressible ultrafilters useful is the following dual to
\cref{IncomRK0}:

\begin{prp}\label{IncomRK}
Suppose \(U\) is incompressible and \(W\) is an ultrafilter on an ordinal. If
\(U\sRK W\) then \(U\rRK W\).
\begin{proof}
Assume \(U\sRK W\). Fix \(k : M_U\to M_W\) such that \(k\circ j_U = j_W\). Since
\(U\not\cong W\), \(k\) is not an isomorphism. It follows that \(\id_W\notin
k[M_U]\): otherwise \(j_W[V]\cup\{\id_W\}\subseteq k[M_U]\) and so \(M_W =
H^{M_W}(j_W[V]\cup\{\id_W\})\subseteq k[M_U]\), and therefore \(k\) is
surjective and hence an isomorphism.

To show that \(U\rRK W\), it suffices by \cref{rRKEmbedding} to show that
\(k(\id_U) < \id_W\). Suppose not. Then \(\id_W\leq k(\id_U)\), and since
\(\id_W\notin k[M_U]\), in fact \(\id_W < k(\id_U)\). Since \(M_W =
H^{M_W}(j_W[V]\cup \{\id_W\})\) we can fix a function \(f :\delta_W\to
\delta_W\) such that \(j_W(f)(\id_W) = k(\id_U)\). Since \(\id_W < k(\id_U)\),
\[M_W\vDash \exists \xi < k(\id_U)\ j_W(f)(\xi) = k(\id_U)\] Since \(j_W(f) =
k(j_U(f))\), the elementarity of \(k: M_U\to M_W\) implies
\[M_U\vDash \exists \xi < \id_U\ j_U(f)(\xi) = \id_U\] This contradicts
\cref{IncomPower} (3), which in particular states that \(\id_U \neq
j_U(f)(\xi)\) for any \(\xi < \id_U\).
\end{proof}
\end{prp}

\begin{cor}\label{RKrRK}
The strict Rudin-Keisler order and the revised Rudin-Keisler order coincide on
incompressible ultrafilters.\qed
\end{cor}

\begin{cor}\label{RKKet}\index{Ketonen order!vs. the Rudin-Keisler order}
The Ketonen order extends the strict Rudin-Keisler order on countably complete
incompressible ultrafilters.\qed
\end{cor}

We remark that given \cref{RKKet}, one might guess that \({\rRK} = {\RK}\cap
{\sE}\), but it is not hard to construct a counterexample under weak large
cardinal assumptions.

\begin{cor}[Solovay]\label{RKWF}
The strict Rudin-Keisler order is wellfounded on countably complete
ultrafilters.\index{Rudin-Keisler order!Wellfoundedness}
\begin{proof}
Suppose towards a contradiction that \[U_0\sgRK U_1\sgRK U_2\sgRK\cdots\] is a
descending sequence of countably complete ultrafilters in the strict
Rudin-Keisler order. For each \(n\), let \(W_n\) be the unique incompressible
ultrafilter isomorphic to \(U_n\). Then \[W_0\sgRK W_1 \sgRK  W_2\sgRK\cdots\]
since the strict Rudin-Keisler order is isomorphism invariant. But by
\cref{RKKet}, the Ketonen order extends the strict Rudin-Keisler order on
countably complete incompressible ultrafilters, and therefore \[W_0\sgE W_1 \sgE
W_2 \sgE\cdots\] This contradicts the wellfoundedness of the Ketonen order
(\cref{KOUnGood}).
\end{proof}
\end{cor}
Note that this yields another proof of \cref{RKThm} in the case that \(U\) and
\(W\) are countably complete.

\section{Variants of the Ketonen order}\label{VariantSection}
\subsection{Minimality of internal embeddings}\label{ExtendedKetonen}
In this subsection, we study an extension of the Ketonen order that provides
some insight into arbitrary extender embeddings (as opposed to just ultrapower
embeddings). This order also clarifies the connection between the Ketonen order
and the mouse order from inner model theory (which is also known as the
Dodd-Jensen order). Using these ideas, we prove a lemma (\cref{MinDefEmb}) that
states that if \(N\) and \(M\) are transitive models and \(j : N\to M\) is an
elementary embedding that is definable over \(N\) from parameters, then
\(j(\alpha) \leq k(\alpha)\) for any other elementary embedding \(k : N \to M\).

\begin{defn}\index{Pointed model}
A {\it pointed model} is a structure \((M,\xi)\) such that \(M\) is a transitive
model of ZFC and \(\xi\in \text{Ord}^{M}\). If \(\mathcal M = (M,\xi)\) is a
pointed model, then \(\xi_{\mathcal M} = \xi\).
\end{defn}

We allow pointed models \((M,\xi)\) where \(M\) is a proper class. We abuse
notation by confusing a pointed model \(\mathcal M = (M,\xi)\) with its
underlying set \(M\). We therefore sometimes denote \(\xi\) by \(\xi_M\) instead
of \(\xi_\mathcal M\).

When we discuss elementary embeddings of pointed models, we never impose
elementarity in the language of a pointed model (i.e., with a distinguished
constant for \(\xi\)), only elementarity in the language of set theory.

\begin{defn}
Suppose \(N\) and \(M\) are transitive models of ZFC. An elementary embedding
\(j : N\to M\) is:
\begin{itemize}
\item an {\it extender embedding} if \(j\) is cofinal and \(M = H^M(j[M]\cup S)\) for some \(S\in M\).\index{Extender embedding}
\item an {\it internal extender embedding} if it is furthermore definable over
\(N\).
\end{itemize}
\end{defn}

\begin{defn}
Suppose \(M\) and \(N\) are pointed models.

The {\it Ketonen order on models}\index{Ketonen order!on models} is defined on
\(M\) and \(N\) by setting \(M\sE N\) if there are embeddings \((k,h) : (M,N)\to
P\) such that \(k(\xi_M) < h(\xi_N)\) and \(h\) is an internal extender
embedding of \(N\).

The {\it nonstrict Ketonen order} is defined on \(M\) and \(N\) by setting \(M\E
N\) if there are embeddings \((k,h) : (M,N)\to P\) such that \(k(\xi_M) \leq
h(\xi_N)\) and \(h\) is an internal extender embedding of \(N\).

{\it Ketonen equivalence} is defined on \(M\) and \(N\) by setting \(M\KE N\) if
\(M\E N\) and \(N\E M\).
\end{defn}

The transitivity for the Ketonen order on pointed models uses a trivial
``comparison lemma" that is provable in ZFC.

\begin{lma}\label{ZFCComparison}
Suppose \(M\), \(N_0\), and \(N_1\) are transitive models of \textnormal{ZFC}.
Suppose \(h: M\to N_0\) is an internal extender embedding and \(k : M\to N_1\)
is a cofinal elementary embedding. Then there is a comparison \((\ell, i) :
(N_0,N_1)\to P\) of \((h,k)\) such that \(i\) is an internal extender embedding
of \(N_1\).
\begin{proof}
Let \(\ell = k\restriction N_0\) and \(i = k(h)\). Then \(i\) is an internal
extender embedding and \(\ell\circ h = k\circ h = k(h)\circ k = i\circ k\), so
\((\ell,i)\) is a comparison of \((h,k)\).
\end{proof}
\end{lma}

\begin{lma}\label{PointedTransitive}
If \(M_0 \sE M_1\E M_2\), then \(M_0\sE M_2\).
\begin{proof}
Suppose \(M_0 \sE M_1\E M_2\). Let \((k_0,h_0) : (M_0,M_1)\to N_0\) witness
\(M_0\sE M_1\). Let \((k_1,h_1) : (M_1,M_2)\to N_1\) witness \(M_1\E M_2\).
Applying \cref{ZFCComparison}, let \[(\ell,i) : (N_0,N_1) \to P\] be a
comparison of \((h_0,k_1)\) such that \(i\) is an internal extender embedding of
\(N_1\). Let \(k = \ell \circ k_0\) and let \(h = i\circ h_1\). Then \((k,h) :
(M_0,M_2)\to P\) and \(h\) is an internal extender embedding of \(M_2\) since it
is the composition of the internal extender embeddings \(i\) and \(h_1\).
Finally, \[k(\xi_{M_0}) = \ell\circ k_0(\xi_{M_0}) < \ell\circ h_0(\xi_{M_1}) =
i\circ k_1(\xi_{M_1}) \leq i\circ h_1(\xi_{M_2}) = h(\xi_{M_2})\qedhere\]
\end{proof}
\end{lma}

We will prove the wellfoundedness of the Ketonen order on pointed models that
satisfy a very weak form of iterability.

\begin{defn}
A transitive model \(M\) of ZFC is {\it \(\omega\)-linearly iterable} if the
following holds. Suppose \[M = M_0\stackrel{h_0}{\longrightarrow}
M_1\stackrel{h_1}{\longrightarrow} M_2 \stackrel{h_2}{\longrightarrow}\cdots\]
is such that for all \(i < \omega\), \(h_i : M_i\to M_{i+1}\) is an internal
extender embedding, then its direct limit is wellfounded.
\end{defn}

The following is a well-known fact, versions of which are due to Gaifman, Kunen,
and Mitchell (see \cite{MitchellHandbook}):

\begin{lma}\label{Iterability}
Suppose \(M\) is a model of \textnormal{ZFC} such that \(\textnormal{Ord}^M\)
has uncountable cofinality. Then \(M\) is \(\omega\)-linearly iterable.
Similarly, any inner model is \(\omega\)-linearly iterable.\qed
\end{lma}

The proof of the wellfoundedness of the Ketonen order on pointed models is based
on the proof of the wellfoundedness of the Dodd-Jensen order.
\begin{thm}\label{GenWellfounded}
The Ketonen order is wellfounded on \(\omega\)-linearly iterable pointed
models.\index{Ketonen order!on models!wellfoundedness}
\begin{proof}
To simplify notation, we isolate the main step of the proof as a lemma:
\begin{lma}\label{WF1Step}
Suppose that \(M_0\sgE M_1\sgE M_2\sgE \cdots\) is a descending sequence of
pointed models. Then there is a descending sequence \(N_0\sgE  N_1\sgE N_2\sgE
\cdots\) of pointed models and an internal extender embedding \(h : M_0\to N_0\)
with \(\xi_{N_0} < h(\xi_{M_0})\).
\begin{proof}
The proof is illustrated by \cref{GenWFFig}.
\begin{figure}
	\center
	\includegraphics[scale=.75]{GenWF.pdf}
	\caption{The proof of \cref{WF1Step}}\label{GenWFFig}
\end{figure} Let \((h_i,k_i) : (M_i,M_{i+1})\to N_i\) witness \(M_i\sgE
M_{i+1}\). We endow \(N_i\) with the structure of a pointed model by letting
\(\xi_{N_i} = k_i(\xi_{M_{i+1}})\).

Setting \(h = h_0\), particular, \(h\) is an internal extender embedding and
\(\xi_{N_0} < h(\xi_{M_0})\). It remains to verify that \(N_0\sgE  N_1\sgE
N_2\sgE \cdots\). Fix \(i < \omega\). By \cref{ZFCComparison}, there is a
comparison \((h_i',k_i') : (N_i,N_{i+1})\to P_i\) of \((k_i,h_{i+1})\) such that
\(h_i'\) is an internal extender embedding of \(N_i\). As in
\cref{PointedTransitive}, \[h_i'(\xi_{N_i}) = h_i'(k_i(\xi_{M_{i+1}})) =
k_i'(h_{i+1}(\xi_{M_{i+1}})) > k_i'(k_{i+1}(\xi_{M_{i+1}})) =
k_i'(\xi_{N_{i+1}})\] and hence \(N_i\sgE N_{i+1}\).
\end{proof}
\end{lma}
Now suppose towards a contradiction that  \(M^0_0\sgE M^0_1\sgE M^0_2\sgE
\cdots\) is a descending sequence of \(\omega\)-linearly iterable pointed
models. By recursion, using the lemma, one obtains sequences \(M^i_0\sgE
M^i_1\sgE M^i_2\sgE \cdots\) and internal extender embeddings \(h^i : M^i_0 \to
M^{i+1}_0\) with \(\xi_{M^{i+1}_0} < h^i(\xi_{M^i_0})\) for all \(i < \omega\).
But then the iteration \[M^0_0\stackrel{h^0}{\longrightarrow}
M_0^1\stackrel{h^1}{\longrightarrow}M_0^2\stackrel{h^2}{\longrightarrow}\cdots\]
has an illfounded direct limit, which contradicts that \(M^0_0\) is
\(\omega\)-linearly iterable.
\end{proof}
\end{thm}

The wellfoundedness of the Ketonen order on pointed models has some useful
consequences. Of course, it provides an alternate proof of the wellfoundedness
of the Ketonen order:

\begin{proof}[Alternate Proof of \cref{KOWellfounded}] For \(U\in \Un\), let
\(\Phi(U) = (M_U,\id_U)\). Then for any \(U\in \Un\), \(\Phi(U)\) is an
\(\omega\)-linearly iterable pointed model. Moreover, if \(U\sE W\), then
\(\Phi(U)\sE \Phi(W)\) since internal ultrapower embeddings are internal
extender embeddings. Thus the Ketonen order is wellfounded on \(\Un\) since by
\cref{GenWellfounded}, the Ketonen order is wellfounded on \(\omega\)-linearly
iterable models.
\end{proof}

More interestingly, \cref{GenWellfounded} implies a coarse version of the
Dodd-Jensen Lemma (proved for example, \cite{Steel}):
\begin{thm}\label{MinDefEmb}\index{Minimality of definable embeddings}
Suppose \(M\) is an \(\omega\)-linearly iterable model. Suppose \(h,k : M\to N\)
are elementary embeddings and \(h\) is an internal extender embedding of \(M\).
Then for all \(\alpha\in \textnormal{Ord}^M\), \(h(\alpha) \leq k(\alpha)\).
\begin{proof}
Suppose towards a contradiction that \(k(\alpha) < h(\alpha)\). Then \((k,h) :
(M,M)\to N\) witnesses \((M,\alpha) \sE (M,\alpha)\), contradicting
\cref{GenWellfounded}.
\end{proof}
\end{thm}
The idea of generalizing arguments from inner model theory to prove results like
\cref{MinDefEmb} is due to Woodin \cite{Woodin}, who proved the similar theorem
that if \(M\) and \(N\) are models of ZFC and \(M\) is finitely generated, then
there is at most one close embedding from \(M\) to \(N\). Woodin's theorem
actually follows from the restriction of \cref{MinDefEmb} to ultrapower
embeddings.

By tracing through the proof of this theorem, one can prove the following fact,
which is really a theorem scheme:
\begin{thm}
Suppose \(M\) and \(N\) are inner models, \(h,k : M\to N\) are elementary
embeddings. If \(h\) is definable over \(M\), then \(h(\alpha) \leq k(\alpha)\)
for all ordinals \(\alpha\).\qed
\end{thm}
There are some metamathematical difficulties involving the linear iterability of
an inner model \(M\) by an \(\omega\)-sequence of definable embeddings: it is
not in general clear that this is first-order expressible in the language of set
theory with a predicate for \(M\). The iterability required for the proof of
\cref{MinDefEmb}, however, can be stated and proved. We omit the proof since we
have no applications of this more general theorem.

\subsection{The seed order}\label{SOSection}
We now define the seed order, a variant of the Ketonen order that uses fully
internal ultrapower comparisons.
\begin{defn}
Suppose \(U\) and \(W\) are countably complete ultrafilters on ordinals.
\index{Seed order}

The {\it seed order} is defined by setting \(U\swo W\) if there is an internal
ultrapower comparison \((k,h)\) of \((j_{U},j_{W})\) such that \(k(\id_{U}) <
h(\id_{W})\).

The {\it nonstrict seed order} is defined by setting \(U\wo W\) if there is an
internal ultrapower comparison \((k,h)\) of \((j_{U},j_{W})\) such that
\(k(\id_{U}) \leq h(\id_{W})\).

{\it Seed equivalence} is defined by setting \(U=_S W\) if there is an internal
ultrapower comparison \((k,h)\) of \((j_{U},j_{W})\) such that \(k(\id_{U}) =
h(\id_{W})\).
\end{defn}

\begin{lma}
If \(U\) and \(W\) are countably complete ultrafilters, then \(U =_S W\) if and
only if \(U \KE W\).\qed
\end{lma}

\begin{lma}
Suppose \(U_0\) and \(U_1\) are countably complete ultrafilters concentrating on
ordinals. Then \(U_0\wo U_1\) if and only if \(U_0 \swo U_1\) or \(U_0 =_S
U_1\).\qed
\end{lma}

By the characterization of the Ketonen order in terms of comparisons
(\cref{KOChars}) we have the following fact:
\begin{lma}
The Ketonen order extends the seed order.\qed
\end{lma}

It follows that the seed order is a strict wellfounded set-like relation.
(Transitivity is another story; see \cref{TransUA} below.)

\begin{cor}\label{SeedAntisymmetry}
Suppose \(U\) and \(W\) are countably complete ultrafilters on ordinals. Then
\(U =_S W\) if and only if \(U\wo W\) and \(W\wo U\).\qed
\end{cor}

\begin{prp}[UA]\label{SeedKet}
The seed order linearly orders \(\Un\).
\begin{proof}
By the definition of the Ultrapower Axiom, the nonstrict seed order is a total
relation on \(\Un\). By \cref{SeedAntisymmetry} and the fact that \(=_S\)
restricts to equality on \(\Un\), the seed order is antisymmetric on \(\Un\).
Thus the seed order linearly orders \(\Un\).
\end{proof}
\end{prp}

The seed order, unlike the Ketonen order, is not provably transitive in ZFC (for
mundane reasons):
\begin{prp}\label{TransUA}
The seed order is transitive if and only if the Ultrapower Axiom
holds.\index{Seed order!transitivity}
\end{prp}

The proof uses the following trivial variant of \cref{SpaceLemma}.

\begin{lma}\label{PrincipalOrder2}
Suppose \(\alpha\) is an ordinal and \(U\) is a countably complete ultrafilter
that concentrates on ordinals. Then \(U\) and the principal ultrafilter \(\pr
\alpha {}\) are comparable in the seed order:
\begin{itemize}
\item \(U \swo \pr \alpha {}\) if and only if \(\delta_U\leq \alpha\).
\item \(U \KE \pr \alpha {}\) if and only if \(\delta_U = \alpha + 1\).
\item \(U\slwo \pr \alpha {}\) if and only if \(\alpha +1 < \delta_U\).\qed
\end{itemize}
\end{lma}

\begin{proof}[Proof of \cref{TransUA}] Suppose \(j_0 : V\to M_0\) and \(j_1 :
V\to M_1\) are ultrapower embeddings. We will show they can be compared. For \(i
= 0,1\), fix ordinals \(\alpha_i\in M_i\) such that \(M_i = H^{M_i}(j_i[V]\cup
\{\alpha_i\})\) with the further property that letting \(U_i\) be the tail
uniform ultrafilter derived from \(j_i\) using \(\alpha_i\),  \(\delta_{U_0} <
\delta_{U_1}\).

By \cref{PrincipalOrder2}, \[U_0 \swo \pr {\delta_{U_0}} {}\wo U_1\] Thus if the
seed order is transitive, \(U_0 \wo U_1\). Since \(j_0 = j_{U_0}\) and \(j_1 =
j_{U_1}\) the fact that \(U_0 \swo U_1\) implies in particular that there is an
internal ultrapower comparison of \((j_0,j_1)\). This verifies the Ultrapower
Axiom for the pair \((j_0,j_1)\).
\end{proof}

We now consider the seed order on pointed models.

\begin{defn}\index{Pointed ultrapower}\index{Pointed ultrapower embedding}
A {\it pointed ultrapower} is a pointed model \(\mathcal M\) whose underlying
class \(M\) is an ultrapower of the universe \(V\). A {\it pointed ultrapower
embedding} is a pair \((j,\xi)\) where \(j\) is an ultrapower embedding and
\(\xi\) is an ordinal.
\end{defn}

There is a natural identification of countably complete ultrafilters with a
certain class of pointed ultrapower embeddings:
\begin{defn}\index{Pointed ultrapower embedding!representing an ultrafilter}
	Suppose \(U\) is a countably complete ultrafilter on an ordinal. Then the
	{\it pointed ultrapower embedding representing \(U\)} is \((j_U,\id_U)\). A
	pointed ultrapower embedding \((j,\xi)\) {\it represents an ultrafilter} if
	it is the pointed ultrapower embedding representing some ultrafilter.
\end{defn}

We apologize for bombarding the reader with definitions. The following
definitions extend the seed order and Ketonen order to pointed ultrapowers and
embeddings.

\begin{defn}
Suppose \(M\) and \(N\) are pointed ultrapowers.

The {\it seed order}\index{Seed order!on pointed ultrapowers} ({\it nonstrict
seed order}) is defined by setting \( M \swo  N\) (\( M \wo  N\)) if there is an
internal ultrapower comparison \((k,h) : ( M, N)\to P\) such that \(k(\xi_ M) <
h(\xi_{ N})\) (\(k(\xi_ M) \leq h(\xi_{ N})\)).

{\it Seed equivalence}\index{Seed order!seed equivalence}\index{\(=_S\) (seed
equivalence)} is defined by setting \( M \wo  N\) if there is an internal
ultrapower comparison \((k,h) : ( M, N)\to P\) such that \(k(\xi_ M) = h(\xi_{
N})\).
\end{defn}

\begin{defn}
Suppose \((i,\nu)\) and \((j,\xi)\) are pointed embeddings.

The {\it seed order} ({\it nonstrict seed order}) is defined by setting
\((i,\nu) \swo (j,\xi)\) (\((i,\nu) \wo (j,\xi)\)) if there is an internal
ultrapower comparison \((k,h)\) of \((i,j)\) such that \(k(\nu) < h(\xi)\)
(\(k(\nu) \leq h(\xi)\)).

{\it Seed equivalence} is defined on by setting \((i,\nu) =_S (j,\xi)\) if there
is an internal ultrapower comparison \((k,h)\) of \((i,j)\) such that \(k(\nu) =
h(\xi)\).

The {\it Ketonen order} ({\it nonstrict Ketonen order}) is defined on by setting
\((i,\nu) \sE (j,\xi)\) (\((i,\nu)  \E (j,\xi)\)) if there is a comparison
\((k,h)\) of \((i,j)\) such that \(h\) is an internal ultrapower embedding and
\(k(\nu) < h(\xi)\) (\(k(\nu) \leq h(\xi)\)).

{\it Ketonen equivalence}\index{Ketonen order!Ketonen
equivalence}\index{\(=_{\Bbbk}\) (Ketonen equivalence)} is defined by setting
\((i,\nu)=_{\Bbbk} (j,\xi)\) if \((i,\nu)\E(j,\xi)\) and \((j,\xi)\E (i,\nu)\).
\end{defn}

The following is in a sense the strongest consequence of UA for these orders:

\begin{prp}[UA]\label{GenTrichotomy}
Suppose \((i,\nu)\) and \((j,\xi)\)  are pointed ultrapower embeddings. Then
either \((i,\nu) \swo (j,\xi)\), \((i,\nu) =_S (j,\xi)\), or \((i,\nu) \slwo
(j,\xi)\).\qed
\end{prp}

\begin{defn}
If \((j,\xi)\) is a pointed ultrapower embedding, then \(M(j)\) denotes the
target model of \(j\) and \(M(j,\xi)\) denotes the pointed ultrapower
\((M(j),\xi)\).
\end{defn}

\begin{lma}[UA]\label{GenSE}\index{Ketonen order!vs. the seed order}\index{Seed order!vs. the Ketonen order}
Suppose  \((i,\nu)\) and \((j,\xi)\)  are pointed ultrapower embeddings. Then
the following are equivalent:
\begin{enumerate}[(1)]
\item \((i,\nu) \wo (j,\xi)\).
\item \((i,\nu)\E (j,\xi)\).
\item \(M(i,\nu) \wo M(j,\xi)\).
\item \(M(i,\nu) \E M(j,\xi)\).
\end{enumerate}
\begin{proof}
The implications from (1) to (2) to (3) to (4) are trivial, so to prove the
lemma, it suffices to show that (4) implies (1). Therefore assume \(M(i,\nu)\E
M(j,\xi)\). Assume (4) fails, towards a contradiction, so that by
\cref{GenTrichotomy}, \((j,\xi)\swo (i,\nu)\). Therefore \(M(j,\xi)\swo M
(i,\nu)\) and hence \(M(j,\xi)\sE M(i,\nu)\). By \cref{PointedTransitive},
\(M(i,\nu)\sE M(i,\nu)\), contradicting \cref{GenWellfounded}.
\end{proof}
\end{lma}

Unlike their restrictions to ultrafilters, the relations \(\KE\) and \(=_S\) are
far from trivial on pointed ultrapowers and embeddings. When one of the pointed
ultrapower embeddings involved represents an ultrafilter, \(=_S\) is closely
related to the Rudin-Frol\'ik order (\cref{RFChapter}):

\begin{lma}\label{RFSEquiv}\index{Seed order!seed equivalence!vs. the Rudin-Frol\'ik order}
Suppose \((i,\nu)\) and \((j,\xi)\) are pointed ultrapower embeddings such that
\((i,\nu)\) represents an ultrafilter. Then \((i,\nu) =_S (j,\xi)\) if and only
if there is an internal ultrapower embedding \(e : M(i)\to M(j)\) such that
\(e\circ i = j\) and \(e(\nu) = \xi\).
\begin{proof}
We prove the forwards direction, since the converse is trivial. Let \(M = M(i)\)
and \(N = M(j)\). Fix an internal ultrapower comparison \((k,h) : (M,N)\to P\)
of \((i,j)\) with \(k(\nu) = h(\xi)\).

We claim that \(k[M]\subseteq h[N]\). Since \(i\) represents an ultrafilter, \(M
= H^M(i[V]\cup \{\nu\}),\) and hence \(k[M] = H^P(k[i[V]\cup \{\nu\}])\). But
\(k(\nu) = h(\xi)\in h[N]\) and \(k[i[V]] = h[j[V]]\subseteq h[N]\). Thus
\(k[i[V]\cup \{\nu\}]\subseteq h[N]\), so that \(k[M] = H^P(k\circ i[V]\cup
\{k(\nu)\})\subseteq h[N]\), as claimed.

Let \(e = h^{-1}\circ k\). Then \(e : M\to N\) is an elementary embedding and
since \(e\circ i = h^{-1} \circ k \circ i = h^{-1} \circ h\circ j\), we have
\(e\circ i = j\). It follows that \(e\) is an ultrapower embedding of \(M\).
Since \(h \circ e = k\) and \(k\) is close to \(M\), \(e\) is an internal
ultrapower embedding of \(M\) by \cref{CloseLemma}. Finally, \(e(\nu) =
h^{-1}(k(\nu)) = h^{-1}(h(\xi)) = \xi\).
\end{proof}
\end{lma}

\begin{cor}[UA]\label{UniqueUltrapowerEmbedding}\index{Ultrapower!ultrapower embedding!uniqueness}
Suppose \(i : V\to M\) and \(j : V\to M\) are ultrapower embeddings with the
same target model. Then \(i = j\).
\begin{proof}
Fix \(\xi\) such that \(M = H^M(i[V]\cup \{\xi\})\). Since \(M(i,\xi) = (M,\xi)
= M(j,\xi)\), we must have \((i,\xi) =_S (j,\xi)\) by \cref{GenSE}. By
\cref{RFSEquiv}, it follows that there is an internal ultrapower embedding \(k:
M\to M\) such that \(k\circ i = j\) and \(k(\xi) = \xi\). Since \(k\) is
internal to \(M\), \(k\) is the identity, and therefore \(i = j\).
\end{proof}
\end{cor}

The structure of the equivalence relation \(=_S\) on pointed models under UA
seems quite interesting. For example, for all we know, if \(M =_S N\) then there
some \(H\) of which both \(M\) and \(N\) are ultrapowers such that \(M =_S H =_S
N\).

\subsection{The width of an embedding}
As a brief digression, we make some general remarks about the size of
ultrafilters necessary to realize compositions of ultrapower embeddings. It
turns out to be easier to work in a bit more generality, using a definition due
to Cummings \cite{CummingsHandbook}:

\begin{defn}\index{Width of an elementary embedding}
	Suppose \(M\) and \(N\) are transitive models of ZFC and \(j : M\to N\) is
	an extender embedding. The {\it width} of \(j\), denoted
	\(\textsc{width}(j)\), is the least \(M\)-ordinal \(\iota\) such that \(N =
	H^N(j[M]\cup \sup j[\iota])\).
\end{defn}
Note that an embedding is an extender embedding if and only if its width is
well-defined. For ultrapower embeddings, there is a simple relationship between
width and size. Recall from \cref{RelativizedLambda}, which generalizes the
notion of size (i.e., \(\lambda_U\)) to \(M\)-ultrafilters \(U\).

\begin{prp}
	If \(j : M\to N\) is the ultrapower embedding associated to an
	\(M\)-ultrafilter \(U\), then \(\textsc{width}(j) = \lambda_U+1\).\qed
\end{prp}

There are really two key facts about width, both of which are generalized by the
theory of generators (\cref{CompositionGenerators}). The first can be summarized
that narrow embeddings are continuous\index{Continuous embedding} at large
regular cardinals \(\lambda\) (i.e., \(j(\lambda) =\sup j[\lambda]\)):

\begin{lma}\label{NarrowContinuity}
	Suppose \(j: M\to N\) is an extender embedding and \(\lambda\) is an ordinal
	of \(M\)-cofinality at least \(\textsc{width}(j)\). Then \(j(\lambda) = \sup
	j[\lambda]\).
	\begin{proof}
		Suppose \(\alpha\in \text{Ord}^{N}\) and \(\alpha < j(\lambda)\). We
		will show \(\alpha \leq j(\gamma)\) for some \(\gamma < \lambda\). Since
		\(N = H^N(j[M]\cup \sup j[\lambda])\), we can find a function \(f\in M\)
		and an ordinal \(\nu < \lambda\) such that \(\alpha = j(f)(\xi)\) for
		some \(\xi < j(\nu)\). Since the \(M\)-cofinality of \(\lambda\) is
		above \(\nu\), \(f[\nu]\cap \lambda\) is bounded by some \(\gamma <
		\lambda\). Hence \(\alpha = j(f)(\xi) \leq \sup j(f)[j(\nu)]\cap
		j(\lambda) = j(\sup f[\nu]\cap \lambda) = j(\gamma)\), as desired.
	\end{proof}
\end{lma}

This has a useful consequence for ultrapower embeddings (which is essentially
equivalent):

\begin{lma}\label{MUFContinuity}\label{UFContinuity}
	Suppose \(M\) is a transitive model of \textnormal{ZFC} and \(U\) is an
	\(M\)-ultrafilter on a set \(X\in M\). Then for any ordinal \(\delta\) such
	that \(\text{cf}^M(\delta) > \lambda_U\), \(j_U^M\) is continuous at
	\(\delta\).\qed
\end{lma}

It is worth mentioning a related fact here:
\begin{lma}\label{UFCardinality}
	If \(U\) is an ultrafilter on \(X\), then for any cardinal \(\gamma\),
	\(|j_U(\gamma)| \leq \gamma^{|X|}\). Thus if \(\lambda\) is a strong limit
	cardinal above \(|X|\), \(j_U[\lambda]\subseteq \lambda\). If moreover
	\(\textnormal{cf}(\lambda) > |X|\), then \(j_U(\lambda) = \lambda\).\qed
\end{lma}

The second provides a computation of the width of a composition in terms of the
width of the factors:

\begin{lma}\label{WidthLemma}
	Suppose \(M\stackrel{i}{\longrightarrow}N\stackrel{j}{\longrightarrow}P\)
	are elementary embeddings. Then
	\[\textsc{width}(j\circ i) = \max \{\textsc{width}(i),\gamma\}\] where
	\(\gamma\) is the least ordinal such that \(\textsc{width}(j) \leq \sup
	i[\gamma]\).
	\begin{proof}
		Let \(\iota = \max \{\textsc{width}(i),\gamma\}\).

		We first show \(\textsc{width}(j\circ i) \leq \iota\). Since
		\(\textsc{width}(i) \leq \iota\), \(N = H^N(i[M]\cup \sup i[\iota])\).
		Since \(\textsc{width}(j) \leq \sup i[\iota]\), \(P = H^P(j[N]\cup \sup
		j[\sup i[\iota]]) = H^P(j[N]\cup \sup j\circ i[\iota])\). Putting these
		calculations together, \[P = H^P(j[i[M]\cup \sup i[\iota]]\cup \sup
		j\circ i[\iota]) = H^{P}(j\circ i[M]\cup \sup j\circ i[\iota])\] It
		follows that \(\textsc{width}(j\circ i) \leq \iota\).

		We now show \(\iota \leq \textsc{width}(j\circ i)\). First, we show
		\(\gamma \leq \textsc{width}(j\circ i)\). Fix \(\eta < \gamma\), and we
		will show \(\eta < \textsc{width}(j\circ i)\). This follows from the
		fact that \[H^P(j\circ i[M]\cup \sup j\circ i[\eta]) \subseteq
		H^P(j[N]\cup \sup j[\sup i[\eta]]) \subsetneq P\] The final inequality
		uses that \(\sup i[\eta] < \textsc{width}(j)\).

		We finish by showing \(\textsc{width}(i) \leq\textsc{width}(j\circ i)\).
		This uses the argument from \cref{IncomRK}. Suppose \(\eta <
		\textsc{width}(i)\) is an \(M\)-cardinal, and we will show  \(\eta <
		\textsc{width}(j\circ i)\). Fix \(a\in N\) such that \(a\notin
		H^N(i[M]\cup \sup i[\eta])\). Suppose towards a contradiction that
		\(j(a)\in H^P(j\circ i[M]\cup \sup j\circ i[\eta])\). Fix \(\xi < \eta\)
		and \(f\in M\) such that \(j(a) = j(i(f))(\alpha)\) for some \(\alpha
		\leq j(i(\xi))\). Then by the elementarity of \(j\), \(N\) satisfies
		that \(a = i(f)(\alpha)\) for some \(\alpha \leq i(\xi)\). This
		contradicts our assumption that \(a\notin H^N(i[M]\cup \sup i[\eta])\).
		Therefore \(j(a)\notin H^P(j\circ i[M]\cup \sup j\circ i[\eta])\), so
		\(\eta < \textsc{width}(j\circ i)\), as desired.
	\end{proof}
\end{lma}

\subsection{The direct limit of all ultrapowers}\label{MInftySection}
Under the Ultrapower Axiom, it is possible to take the direct limit of all
ultrapower embeddings. The properties of this structure, which is denoted
\(M_\infty\), turn out to be closely related both to the Ketonen order on
pointed ultrapowers and to the theory of supercompact cardinals.

To save ink, it is convenient to let \(\infty\) be a formal symbol such that (by
definition) every ordinal \(\lambda\) satisfies \(\lambda < \infty\).

\begin{defn}
	Suppose \(M\) is an ultrapower of the universe and \(\lambda\) is an
	ordinal. Then \(\nu(M,\lambda) = \sup i[\lambda]\) where \(i : V\to M\) is
	any ultrapower embedding.
\end{defn}

By \cref{MinDefEmb}, \(\nu(M,\lambda)\) does not depend on the choice of \(i\).
We also set \(\nu(M,\infty) = \infty\).

\begin{defn}
If \(\lambda\) is is a cardinal or \(\lambda = \infty\), then \(\mathcal
D_\lambda\) denotes the following category:
\begin{itemize}
	\item An inner model \(M\) is an object of \(\mathcal D_\lambda\) if there is an ultrapower embedding  \(i : V\to M\) with \(\textsc{width}(i) \leq \lambda\).\index{Ultrapower!category of}
	\item If \(M,N\in \mathcal D_\lambda\), an internal ultrapower embedding \(j
	: M\to N\) is a morphism of \(\mathcal D_\lambda\) if \(\textsc{width}(j)
	\leq \nu(M,\lambda)\).
\end{itemize}
\end{defn}

Thus \(\mathcal D_\infty\) is the category of all ultrapowers of the universe
equipped with their internal ultrapower embeddings.  As an immediate consequence
of \cref{UniqueUltrapowerEmbedding}, UA implies that \(\mathcal D_\lambda\) is a
full subcategory of \(\mathcal D_\infty\); that is, it contains all morphisms
between the objects it sees. It is not clear whether this is the case in ZFC
(and it is not even clear whether this subcategory is locally small in the
natural sense).\footnote{This raises an interesting question in the general
theory of elementary embeddings:
\begin{qst}[ZFC] Can two ultrapower embeddings of the universe have the same
	target model but different widths?
\end{qst}
The question has something to do with uniform ultrafilters on singular
cardinals.}

\begin{defn}
	A category \(\mathcal C\) is a {\it partial order} if every pair of objects
	\(a,b\in \mathcal C\) there is at most one morphism from \(a\) to \(b\) in
	\(\mathcal C\). A category \(\mathcal C\) is {\it directed} if for every
	pair of objects \(a,b\in \mathcal C\), there is a further object \(c\in
	\mathcal C\) admitting morphisms \(a\to c\) and \(b \to c\).
\end{defn}

We have the following equivalences:

\begin{lma}
The following are equivalent:
\begin{enumerate}[(1)]
\item The Ultrapower Axiom.
\item For all cardinals \(\lambda\), \(\mathcal D_\lambda\) is a directed
partial order.
\item \(\mathcal D_\infty\) is a directed partial order.
\end{enumerate}
\begin{proof}
 	{\it (1) implies (2):} The fact that \(\mathcal D_\lambda\) is a partial
 	order follows immediately from \cref{UniqueUltrapowerEmbedding}. The
 	directedness of \(\mathcal D_\lambda\) follows from an easy localization of
 	UA (\cref{UpperBoundBound}), which states that if \(U\) and \(W\) are
 	countably complete ultrafilters on a cardinal \(\gamma\), then there is a
 	countably complete ultrafilter \(Z\) on \(\gamma\) such that there are
 	internal ultrapower embeddings \(k : M_U\to M_Z\) and \(h : M_W\to M_Z\).

 	{\it (2) implies (3):} Immediate.

  	{\it (3) implies (1):} Immediate.
\end{proof}

\end{lma}

\begin{defn}[UA]\index{Direct limit of all ultrapowers}
If \(\lambda\) is a cardinal or \(\lambda = \infty\), let \[M_\lambda = \lim
\mathcal D_\lambda\] For all \(M\in \mathcal D_\lambda\), \[j_{M,\lambda} : M\to
M_\lambda\] denotes the direct limit embedding.
\end{defn}

The models \(M_\lambda\) are wellfounded by a standard application of the linear
iterability of the universe (\cref{Iterability}). We will see that \(M_\infty\)
need not be set-like. By convention we identify its set-like part with an inner
model.

The following lemma is the key to the analysis of the models \(M_\lambda\) for
\(\lambda\) a regular cardinal:

\begin{lma}[UA]\label{InftyAbs}
Suppose \(\lambda\) is a regular cardinal or \(\lambda = \infty\). For any
ultrapower embedding \(i :V\to N\) with \(i\in \mathcal D_\lambda\),
\(i(M_\lambda) = M_\lambda\) and \(i(j_{V,\lambda}) = j_{N,\lambda}\).
\begin{proof}
The key point is that since \(\lambda\) is regular and \(\textsc{width}(i) \leq
 \lambda\), \(i(\lambda)  = \sup i[\lambda] = \nu(N,\lambda)\). Thus
 \(i(\mathcal D_\lambda) = \mathcal D_{i(\lambda)}^N =\mathcal
 D_{\nu(N,\lambda)}^N\), which is equal to the cone above \(N\) in \(\mathcal
 D_\lambda\). Since \(\mathcal D_\lambda\) is a directed partial order, this
 cone is cofinal in \(\mathcal D_\lambda\), and thus its direct limit is equal
 to that of \(\mathcal D_\lambda\). In other words, \(i(M_\lambda) = \lim
 i(\mathcal D_\lambda) = \lim \mathcal D_\lambda = M_\lambda\), and similarly
 \(i(j_{V,\lambda}) = j_{N,\lambda}\).
\end{proof}
\end{lma}
In the case \(\lambda = \infty\) above, we are heavily abusing notation: when
\(M_\infty\) is not set-like (and so cannot be identified with a transitive
class), a more careful statement would involve isomorphism rather than equality.

We now further explore the set-likeness of \(M_\infty\).

\begin{defn}
	We say an ordinal \(\kappa\) {\it can be mapped arbitrarily high by
	ultrapower embeddings} if for all \(\alpha > \kappa\), there is an
	ultrapower embedding \(j : V\to M\) such that \(j(\kappa) > \alpha\). The
	{\it ultrapower threshold}\index{Ultrapower threshold} is the least ordinal
	\(\kappa\) that can be mapped arbitrarily high by ultrapower embeddings.
\end{defn}

The existence of the ultrapower threshold is a large cardinal principle closely
related to two recently popularized weakenings of strong compactness: the
strongly tall cardinals of Hamkins \cite{Hamkins} and the \(\omega_1\)-strongly
compact cardinals of Bagaria-Magidor \cite{MagidorBagaria}. Certainly a strongly
tall cardinal or an \(\omega_1\)-strongly compact cardinal is greater than or
equal to the ultrapower threshold. (By theorems of Gitik \cite{Gitik}, it is
consistent with ZFC that these inequalities are strict.) The ultrapower
threshold is in a sense a hybrid of these notions in the sense that it weakens
strong compactness in the Hamkins and Bagaria-Magidor directions simultaneously,
producing a super-weakening of strong compactness.

If it exists, the ultrapower threshold is a Beth fixed point, but by the
arguments of Bagaria-Magidor \cite{MagidorBagaria}, it cannot be proved to be
inaccessible in ZFC. The nonexistence of the ultrapower threshold has the
following structural consequence for ultrapower embeddings:

\begin{lma}\label{ArbHigh}
If the ultrapower threshold does not exist, then unboundedly many ordinals are
fixed by all ultrapower embeddings.
\begin{proof}
Fix an ordinal \(\xi\). Let \[T_\xi = \{j(\xi) : j\text{ is an ultrapower
embedding of }V\}\]  and let \(C\) be the class of ordinals fixed by all
ultrapower embeddings. Note that if \(\xi\) is an ordinal and \(i: V\to N\) is
an ultrapower embedding, \[i(T_\xi) = \{j(i(\xi)) : j\text{ is an ultrapower
embedding of }N\}\subseteq T_\xi\] This is because the composition of ultrapower
embeddings is an ultrapower embedding.

Since the ultrapower threshold does not exist, \(T_\xi\) is a set for all
ordinals \(\xi\). So assume \(T_\xi\) is a set, and we will show \(C\setminus
\xi\) is nonempty. Let \(\alpha = \sup(T_\xi)\). Obviously \(\alpha \geq \xi\).
Suppose \(i\) is an ultrapower embedding. Then \[i(\alpha) = \sup i(T_\xi) \leq
\sup(T_\xi) = \alpha\] Thus \(i(\alpha) = \alpha\). It follows that \(\alpha\in
C\setminus \xi\), as desired. Thus if \(T_\xi\) is a set, then there is an
ordinal above \(\xi\) fixed by all ultrapower embeddings. It follows that if
\(T_\xi\) is a set for all \(\xi\), then \(C\) is a proper class.
\end{proof}
\end{lma}

The embedding \(j_{V,\infty}\) actually encodes the class of common fixed points
of ultrapower embeddings by a standard argument:

\begin{lma}\label{FixClm} An ordinal belongs to the range of \(j_{V,\infty}\) if and only if it is fixed by all ultrapower embeddings.\end{lma}
\begin{proof}
	Suppose first that \(\beta\) is an ordinal in the range of \(j_{V,\infty}\).
	Fix an ordinal \(\alpha\) such that \(\beta = j_{V,\infty}(\alpha)\).
	Suppose \(i: V\to N\) is an ultrapower embedding. Then \(i(\beta) =
	i(j_{V,\infty}(\alpha)) = i(j_{V,\infty})(i(\alpha)) = j_{N,\infty}\circ
	i(\alpha) = j_{V,\infty}(\alpha) = \beta\). Thus \(\beta\) is fixed by all
	ultrapower embeddings.

	Conversely, suppose \(\beta\) is fixed by all ultrapower embeddings. Let
	\(\alpha\) be the least ordinal such that \(j_{V,\infty}(\alpha) \geq
	\beta\). Suppose towards a contradiction that \(j_{V,\infty}(\alpha) >
	\beta\). Then there is an ultrapower embedding \(i : V\to N\) and some
	ordinal \(\xi< i(\alpha) \) and \(j_{N,\infty}(\xi) \geq \beta\). But by the
	elementarity of \(i\), \(i(\alpha)\) is the least ordinal \(\alpha'\) such
	that \(i(j_{V,\infty})(\alpha') \geq i(\beta)\). Since \(i(\beta) = \beta\),
	this means that \(i(\alpha)\) is the least ordinal \(\alpha'\) such that
	\(j_{N,\infty}(\alpha')\geq \beta\). This contradicts the existence of \(\xi
	< i(\alpha)\) such that \(j_{N,\infty}(\xi) \geq \beta\).\end{proof}

\begin{thm}[UA]\label{MInftyDichotomy1}\index{Direct limit of all ultrapowers!set-likeness}
	Exactly one of the following holds:
	\begin{enumerate}[(1)]
		\item The ultrapower threshold exists.
		\item \(M_\infty\) is set-like.
	\end{enumerate}
\begin{proof}
Suppose (1) holds. For any ordinal \(\xi\), the images of \(\xi\) under
ultrapower embeddings are bounded above by \(j_{V,\infty}(\xi)\), and so \(\xi\)
is not the ultrapower threshold. Thus (2) fails.

Suppose (2) fails. By \cref{ArbHigh}, the class \(C\) of ordinals fixed by all
ultrapower embeddings is unbounded in the ordinals. By \cref{FixClm}, \(C =
j_{V,\infty}[\text{Ord}]\cap \text{Ord}\). The function
\(j_{V,\infty}\restriction \text{Ord}\) is therefore equal to the increasing
enumeration of \(C\). It follows that for every ordinal \(\alpha\),
\(j_{V,\infty}(\alpha)\) is an ordinal. In other words, \(M_\infty\) is
set-like. Thus (1) holds.
\end{proof}
\end{thm}

The analysis of supercompactness under UA has the following surprising
consequence (\cref{ThreshThm}): the ultrapower threshold is supercompact.
\begin{thm}[UA]\label{SetLikeSupercompact}
Exactly one of the following holds:
\begin{enumerate}[(1)]
\item \(M_\infty\) is set-like.
\item There is a supercompact cardinal.
\end{enumerate}
\begin{proof}[Proof given \cref{ThreshThm}] Suppose \(M_\infty\) is not
	set-like. By \cref{MInftyDichotomy1}, the ultrapower threshold exists. By
	\cref{ThreshThm}, the ultrapower threshold is supercompact.
\end{proof}
\end{thm}
In fact, if the ultrapower threshold \(\kappa\) is supercompact, then
\(j_{V,\infty}(\kappa)\) is isomorphic to \(\text{Ord}\) while
\(j_{V,\infty}\restriction V_\kappa = (j_{V,\infty})^{V_\kappa}\).

We now explain the connection between the models \(M_\lambda\) and the Ketonen
order on pointed ultrapower embeddings.
\begin{defn}\label{ERank}\index{Ketonen order!on pointed ultrapowers!rank (\(o_\lambda(M)\))}\index{\(o_\lambda(M)\) (rank in the Ketonen order on pointed ultrapowers)}
Let \(\mathcal P_\lambda\) denote the collection of pointed ultrapowers
\((M,\xi)\) such that \(M\in \mathcal D_\lambda\). For any \(M\in\mathcal
P_\lambda\), \(o_\lambda(M)\) denotes the rank of \(M\) in the Ketonen order
restricted to \(\mathcal P_\lambda\). (If \(\lambda = \infty\), this rank may
not exist.) If \(W\) is a countably complete ultrafilter then \(o_\lambda(W) =
o_\lambda(M_W,\id_W)\).
\end{defn}

The following theorem shows that the ordinals \(o_\lambda(M)\) are highly
structured under UA:

\begin{thm}[UA]\label{RankEmb}
Assume \(\lambda\) is regular or \(\lambda = \infty\). For any \(M\in \mathcal
P_\lambda\), \(o_\lambda(M) = j_{M,\lambda}(\xi_M)\).
\begin{proof}
Consider the partial function \(\Phi_\lambda : \mathcal P_\lambda\to
\text{Ord}\) defined by \[\Phi_\lambda(M) = j_{M,\lambda}(\xi_M)\] If \(\lambda
= \infty\), we leave \(\Phi_\lambda(M)\) undefined if \(j_{M,\lambda}(\xi_M)\)
is not in the set-like part of \(M_\infty\).

For \(M,N\in \mathcal P_\lambda\), \(M \sE N\) implies \(\Phi_\lambda(M)\sE
\Phi_\lambda(N)\) and \(M \KE N\) implies \(\Phi_\lambda(M) = \Phi_\lambda(N)\).
Moreover the image of \(\Phi_\lambda\) is the set-like initial segment of
\(\text{Ord}^{M_\lambda}\). Therefore \(\Phi_\lambda\) is equal to the rank
function of \((\mathcal P_\lambda,\sE)\). That is, for all \(M\in \mathcal
P_\lambda\), \(o_\lambda(M) = \Phi_\lambda(M) = j_{M,\lambda}(\xi_M)\).
\end{proof}
\end{thm}

Combining this with \cref{SetLikeSupercompact}, we obtain:
\begin{cor}
Exactly one of the following holds:
\begin{enumerate}[(1)]
\item There is a supercompact cardinal.
\item For any pointed ultrapower \(M\), \(o_\infty(M)\) exists.\qed
\end{enumerate}
\end{cor}
In conclusion, the Ketonen order, which is in a sense the simplest structure
associated with the Ultrapower Axiom, bears a deep relationship to
supercompactness under UA. This relationship is one of the topics of
\cref{SCChapter1} and \cref{SCChapter2}.
\subsection{The Lipschitz order}\label{LipschitzSection}
In this short subsection, we describe a generalization of the Ketonen order that
raises an interesting philosophical question. Throughout the section, we fix an
infinite ordinal \(\delta\).
\begin{defn}
Suppose \(f : P(\delta)\to P(\delta)\). Then \(f\) is:
\begin{itemize}
\item a {\it reduction} if for \(A\subseteq \delta\) and \(\alpha < \delta\),
\(f(A)\cap \alpha\) depends only on \(A\cap \alpha\).
\item a {\it contraction} if for \(A\subseteq\delta\) and \(\alpha < \delta\),
\(f(A)\cap (\alpha+1)\) depends only on \(A\cap \alpha\).
\end{itemize}
We say \(X\) {\it reduces} ({\it contracts}) to \(Y\) if there is a reduction
(contraction) \(f : P(\delta)\to P(\delta)\) such that \(f^{-1}[Y] = X\). In
this case we say \(f\) is a reduction (contraction) from \(X\) to \(Y\).
\end{defn}

These concepts can be formulated in terms of long games:
\begin{defn}\index{Lipschitz game}
In the {\it Lipschitz game of length \(\delta\)} associated to sets
\(X,Y\subseteq P(\delta)\), denoted \(G_\delta(X,Y)\), two players I and II
alternate playing 0s or 1s. I plays at limit stages. The play lasts for
\(\delta\cdot 2\) moves, so that I and II produce sequences
\(x_\text{I},x_\text{II}\in {}^\delta2\). Let \(A_\text{I} = \{\alpha < \delta :
x_\text{I}(\alpha) = 1\}\) and \(A_\text{II}  = \{\alpha < \delta :
x_\text{II}(\alpha) = 1\}\). Then II wins if \(A_\text{I}\in X\iff
A_\text{II}\in Y\).
\end{defn}

Player II has a winning strategy if and only if \(X\) reduces to \(Y\), and
Player I has a winning strategy if and only if \(Y\) contracts to
\(P(\delta)\setminus X\).

\begin{defn}\index{Lipschitz order}
The {\it Lipschitz order} is defined on \(X,Y\subseteq P(\delta)\) by setting
\(X\sLi Y\) if \(X\) and \(P(\delta)\setminus X\) contract to \(Y\). The {\it
nonstrict Lipschitz order} is defined on \(X,Y\subseteq P(\delta)\) by setting
\(X\Li Y\) if \(X\) reduces to \(Y\).
\end{defn}

This notation is perhaps misleading since it might suggest that \(X\sLi Y\) if
and only if \(X\Li Y\) and \(Y\not \Li X\). Under the Axiom of Determinacy, this
is true when \(X\) and \(Y\) are contained in \(P(\omega)\).

The Lipschitz order is transitive in the following strong sense:

\begin{lma}
The composition of a contraction and a reduction is a contraction. Therefore is
\(X\) contracts to \(Y\) and \(Y\) reduces to \(Z\), then \(X\) contracts to
\(Z\). In particular, if \(X \sLi Y \Li Z\) then \(X\sLi Z\).\qed
\end{lma}

A generalization of the proof of \cref{KOIrreflexive} shows that the Lipschitz
order is irreflexive:
\begin{lma}\label{LipschitzIrreflexive}
Suppose \(X\subseteq P(\delta)\). Then \(X\) does not contract to
\(P(\delta)\setminus X\).
\begin{proof}
It suffices to show that every contraction \(f : P(\delta)\to P(\delta)\) has a
fixed point \(A\): then \(A\in X\) if and only if \(f(A)\in X\) so \(f\) is not
a contraction from \(X\) to \(P(\delta)\setminus X\).

We define \(A\) by recursion. Suppose \(\alpha < \delta\) and we have defined
\(A\cap \alpha\). We then put \(\alpha\in A\) if and only if \(\alpha\in f(A\cap
\alpha)\). Then for any \(\alpha < \delta\), \begin{align*}\alpha\in A&\iff
\alpha\in f(A\cap \alpha)\\&\iff\alpha\in f(A)\end{align*} The final equivalence
follows from the fact that \(f\) is a contraction. Thus \(f(A) = A\), as
desired.
\end{proof}
\end{lma}

\begin{cor}
The Lipschitz order is a strict partial order.\qed
\end{cor}

By the proof of the Martin-Monk theorem (see \cite{VanWesep}) descending
sequences in the Lipschitz order give rise to pathological subsets of Cantor
space:
\begin{thm}[ZF + DC]\label{MartinMonk}
The following are equivalent:
\begin{enumerate}[(1)]
\item There is a flip set.
\item The Lipschitz order on \(P(\omega)\) is illfounded.
\item The Lipschitz order on \(P(\delta)\) is illfounded.
\end{enumerate}
\begin{proof}
To see (1) implies (2), suppose \(F\subseteq 2^\omega\) is a flip set. Define
\((E_n)_{n < \omega}\) by recursion, setting \(E_0 = F\) and \(E_{n+1} = \{s\in
2^\omega : 0s \in E_n\}\). It is easy to see that \(E_{n+1}\) and \(2^\omega
\setminus E_{n+1}\) both contract to \(E_n\), via the contractions \(s\mapsto
0s\) and \(s\mapsto1s\) respectively.

(2) trivially implies (3).

We finally show (3) implies (1). Fix \(X_0\sgLi X_1 \sgLi X_2\sgLi\cdots\) a
descending sequence of subsets of \(P(\delta)\). For \(n < \omega\), fix
contractions \(f_n^0\) from \(X_{n+1}\) to \(X_n\) and \(f_n^1\) from
\(X_{n+1}\) to \(P(\delta)\setminus X_n\). For each \(s\in 2^\omega\), we define
sets \(A_n^s\subseteq \delta\) such that \[A_n^s = f_n^{s(n)}(A_{n+1}^s)\]
Suppose \(A_n^s\cap\alpha\) has been defined for all \(n < \omega\). Then
\[A_n^s\cap (\alpha + 1) = f_n^{s(n)}(A_{n+1}^s\cap \alpha)\cap (\alpha + 1)\]
Since \(f_n^i\) is a contraction for all \(n < \omega\) and \(i \in \{0,1\}\),
\(A_n^s\) is well-defined and \(A_n^s = f^{s(n)}_n(A^s_{n+1})\).

Define \(F_n\subseteq 2^\omega\) by putting \(s\in F_n\) if and only if
\(A_n^s\in X_n\). Whether \(s\in F_n\) depends only on \(s\restriction
(\omega\setminus n)\). Moreover, if \(s\in F_{n+1}\) then \(s\in F_n\) if and
only if \(s(n) = 0\). It is easy to show by induction that if \(s\) and \(s'\)
agree on \(\omega\setminus n\) and \(\sum_{k < n} s(k) = \sum_{k < n} s'(k)\mod
2\), then \(s\in F_0\) if and only if \(s'\in F_0\). Similarly, if \(s\) and
\(s'\) agree on \(\omega\setminus n\) and \(\sum_{k < n} s(k) \neq \sum_{k < n}
s'(k)\mod 2\), then \(s\in F_0\) if and only if \(s'\notin F_0\). It follows
that \(F_0\) is a flip set.
\end{proof}
\end{thm}
Of course, (1), (2), and (3) are all provable in ZFC. In the choiceless context
of ZF + DC, however, there may be no flip sets (for example, if every subset of
Cantor space has the Baire property or is Lebesgue measurable). In this case,
\cref{MartinMonk} shows that the Lipschitz order is wellfounded not only on
subsets of Cantor space but also on subsets of \(P(\delta)\).\footnote{Under the
same hypotheses, one can show that the Lipschitz order on \({}^\delta S\) is
wellfounded for any set \(S\) after generalizing the definition of the Lipschitz
order in the natural way.} The proof also shows that the wellfounded part of the
Lipschitz order is equal to the collection of sets that do not lie above a flip
set.

We turn now to the relationship between the Lipschitz order and the Ketonen
order.

\begin{defn}\label{SetConcentration}
A set \(Z\subseteq P(\delta)\) {\it concentrates} on a set \(S\) if for all
\(A,B \subseteq \delta\) with \(A\cap S = B\cap S\), \(A\in Z\) if and only if
\(B\in Z\).
\end{defn}

Note that if \(Z\) is an ultrafilter that concentrates on a class \(S\) in the
sense of \cref{UltrafilterConcentration}, then \(Z\) concentrates on \(S\) is
the sense of \cref{SetConcentration}.

\begin{lma}\label{LipChar}
Suppose \(X\subseteq P(\delta)\) and \(W\) is an ultrafilter on \(\delta\). Then
the following are equivalent:
\begin{enumerate}[(1)]
\item \(X\sLi W\).
\item \(X\) contracts to \(W\).
\item For some \(Z\in M_W\) that concentrates on \(\id_W\), \(X = j_W^{-1}[Z]\).
\end{enumerate}
\begin{proof}
{\it (1) implies (2)}: Trivial.

{\it (2) implies (1)}: Assume \(X\) contracts to \(W\). Since \(W\) is an
ultrafilter, \(W\) reduces to \(P(\delta)\setminus W\). Since \(X\) contracts to
\(W\) and \(W\) reduces to \(P(\delta)\setminus W\), \(X\) contracts to
\(P(\delta)\setminus W\). Therefore \(X\sLi W\).

{\it (1) implies (3)}: Let \(f : P(\delta)\to P(\delta)\) be a contraction from
\(X\) to \(W\). For each \(\alpha\), let \(X_\alpha = \{A\subseteq \delta :
\alpha\in f(A)\}\). Since \(f\) is a contraction, \(X_\alpha\) concentrates on
\(\alpha\). Let \(Z = [\langle X_\alpha : \alpha < \delta\rangle]_W\). By \L
o\'s's Theorem, \(Z\) concentrates on \(\id_W\). Then
\begin{align*}
A\in X&\iff f(A)\in W\\
&\iff \{\alpha < \delta : A\in X_\alpha\}\in W\\
&\iff j_W(A)\in Z
\end{align*}
Thus \(j^{-1}_W[Z] = X\).

{\it (3) implies (1)}: Fix \(Z\in M_W\) concentrating on \(\id_W\) such that \(X
= j_W^{-1}[Z]\). Let \(\langle X_\alpha : \alpha \in I\rangle\) be such that \(Z
= [\langle X_\alpha : \alpha \in I\rangle]_W\) and \(X_\alpha\) concentrates on
\(\alpha\) for all \(\alpha\in I\). Define \(f : P(\delta)\to P(\delta)\) by
setting \(f(X) = \{\alpha \in I : X\in X_\alpha\}\). Then \(f\) is a contraction
since \(X_\alpha\) concentrates on \(\alpha\) for all \(\alpha\in I\). Moreover,
\begin{align*}
A\in X&\iff j_W(A)\in Z\\
&\iff \{\alpha < \delta : A\in X_\alpha\}\in W\\
&\iff f(X)\in W\qedhere
\end{align*}
\end{proof}
\end{lma}

Using \cref{KOChars}, this has the following corollary:

\begin{cor}\label{LipKet}\index{Ketonen order!vs. the Lipschitz order}
The Lipschitz order extends the Ketonen order on \(\mathscr B(\delta)\).\qed
\end{cor}

Under UA, it follows that the two orders coincide:

\begin{cor}[UA] The Lipschitz order and the Ketonen order coincide on \(\mathscr
B(\delta)\). In particular, the Lipschitz order linearly orders \(\mathscr
B(\delta)\).
\begin{proof}
Since \(\sLi\) is a strict partial order extending the total relation \(\sE\)
(\cref{Totality}), the two orders must be equal.
\end{proof}
\end{cor}

Another way to state this is as a determinacy consequence of UA:

\begin{cor}[UA]\index{Ultrapower Axiom!vs. long determinacy}
	For all ordinals \(\delta\), for any \(U,W\in \mathscr B(\delta)\), the game
	\(G_\delta(U,W)\) is determined.
\end{cor}

We conclude this section with a question that is perhaps of some philosophical
significance:
\begin{qst}\label{LipUA}
Assume that for any ordinal \(\delta\), for any \(U,W\in \mathscr B(\delta)\),
the game \(G_\delta(U,W)\) is determined. Does the Ultrapower Axiom hold?
\end{qst}
If this were true then the Ultrapower Axiom would be a long determinacy
principle. In \cref{LinKetSection}, we give partial positive answer.

\subsection{The Ketonen order on filters}\label{FilterSection}
We briefly discuss a generalization of the Ketonen order to a wellfounded
partial order on arbitrary countably complete filters that is suggested by the
proof of \cref{KOWellfounded}. This order will not appear elsewhere in this
dissertation, but it seems potentially quite interesting since it identifies a
connection between the Ketonen order and stationary reflection.

\begin{defn}
	Suppose \(F\) is a filter, \(I\in F\), and \(\langle G_i : i\in I\rangle\)
	is a sequence of filters on a fixed set \(Y\). The {\it \(F\)-limit of
	\(\langle G_i : i\in I\rangle\)} is the filter \[F\text{-}\lim_{i\in I} G_i
	= \{A\subseteq Y : \{i \in I : A\in G_i\}\in F\}\]
\end{defn}

\begin{defn}
	If \(F\) is a filter on  a set \(X\) and \(C\) is a class, then \(F\) {\it
	concentrates} on \(C\) if \(C\cap X\in F\).
\end{defn}

\begin{defn}
	Suppose \(X\) is a set and \(C\) is a class. Let \(\mathscr F(X)\) denote
	the set of countably complete filters on \(X\) and let \(\mathscr F(X,C)\)
	denote the set of filters on \(X\) that concentrate on \(C\).
\end{defn}
\begin{defn}\index{Ketonen order!on filters}
	Suppose \(\epsilon\) and \(\delta\) are ordinals, \(F\in\mathscr
	F(\epsilon)\), and \(G\in \mathscr F(\delta)\). The {\it Ketonen order on
	filters} is defined on by setting \(F\sE G\) if there is a set \(I\in G\)
	and a sequence \(\langle F_\alpha : \alpha \in I\rangle\in \prod_{\alpha\in
	I}\mathscr F(\epsilon,\alpha)\) such that \(F \subseteq
	G\text{-}\lim_{\alpha\in I} F_\alpha\).
\end{defn}
Under the Ultrapower Axiom, the restriction to ultrafilters of the Ketonen order
on filters coincides with the Ketonen order as it is defined in
\cref{KOCharsSection}. We do not know whether this is provable in ZFC.

Note that the proof of \cref{KOIrreflexive} breaks down when we consider filters
instead of ultrafilters. In fact, in a sense this simple proof cannot be
remedied, since irreflexivity fails if we allow filters that are countably
incomplete, and it is not clear how countable completeness could come in to the
argument of \cref{KOIrreflexive}.  It is somewhat surprising that one can in
fact prove the irreflexivity of the Ketonen order by instead using countable
completeness and the argument of \cref{KOWellfounded}:

\begin{thm}\label{FilterWellfounded}
	The Ketonen order on filters is wellfounded.
\end{thm}

We include the proof, which is closely analogous to that of
\cref{KOWellfounded}.
\begin{lma}\label{FilterResemblance}
	Suppose \(H\) is a filter and \(F\sE G\) are countably complete filters on
	ordinals \(\epsilon\) and \(\delta\). Suppose \(J\in H\) and \(\langle G_x :
	x \in J\rangle\) is a sequence of countably complete filters such that \(G
	\subseteq H\text{-}\lim_{x \in J} G_x\). Then there is a set \(J'\subseteq
	J\) in \(H\) and a sequence \(\langle F_x: x \in J'\rangle\) of countably
	complete filters such that \(F_x \sE G_x\) for all \(x\in K\) and \(F
	\subseteq H\text{-}\lim_{x \in K} F_x\).
	\begin{proof}
		Since \(F\sE G\), we can fix \(I\in G\) and countably complete filters
		\(\langle D_\alpha : \alpha\in I\rangle\in \prod_{\alpha\in I} \mathscr
		F(\epsilon,\alpha)\) such that \(F \subseteq G\text{-}\lim_{\alpha\in I}
		D_\alpha\).

		Let \(J' = \{b \in J : I\in G_x\}\). Since \(I\in G \subseteq
		H\text{-}\lim_{x\in J} G_x\), we have \(J'\in H\) by the definition of a
		limit. For each \(x\in J'\), let \[F_x = G_x\text{-}\lim_{\alpha\in I}
		D_\alpha\] Then \(F_x\in \mathscr B(\epsilon)\), and the sequence
		\(\langle D_\alpha : \alpha\in I\rangle\) witnesses \(F_b \sE G_b\).

		Finally,
		\begin{align*}
			F &\subseteq G\text{-}\lim_{\alpha\in I} D_\alpha\\
			&\subseteq (H\text{-}\lim_{x\in J} G_x)\text{-}\lim_{\alpha\in I} D_\alpha\\
			&= H\text{-}\lim_{x\in J'} (G_x\text{-}\lim_{\alpha\in I} D_\alpha)\\
			&= H\text{-}\lim_{x\in J'} F_x
		\end{align*}
		Thus \(F\subseteq H\text{-}\lim_{x\in K} F_x\), as desired.
	\end{proof}
\end{lma}

\begin{proof}[Proof of \cref{FilterWellfounded}] Suppose towards a contradiction
	that \(\delta\) is the least ordinal such that the Ketonen order is
	illfounded below a countably complete filter that concentrates on
	\(\delta\). Fix a descending sequence \(F_0\sgE F_1\sgE F_2\sgE\cdots\) such
	that \(F_0\) concentrates on \(\delta\).

	We will define sets of ordinals \(I_1\supseteq I_2\supseteq \cdots\) in
	\(F\) and sequences \(\langle F^{m}_\alpha : \alpha \in I_m\rangle\) of
	countably complete filters such that \[F_m \subseteq F\text{-}\lim_{\alpha
	\in I_m} F^{m}_\alpha\] for all \(1\leq m< \omega\). We will have:
	\begin{itemize}
		\item For all \(\alpha\in I_1\), \(F_\alpha^1\) concentrates on
		\(\alpha\).
		\item For all \(1\leq m< \omega\), for all \(\alpha \in I_{m+1}\),
		\(F^{m+1}_\alpha \sE F^{m}_\alpha\).
	\end{itemize}

	Since \(F_1\sE F\), there is a set of ordinals \(I_1\in F\) and a sequence
	\(\langle F^1_\alpha : \alpha\in I_1\rangle\) of countably complete
	ultrafilters such that \(F_1 \subseteq F\text{-}\lim_{\alpha \in I_1}
	F^1_\alpha\) and \(F^1_\alpha\) concentrates on \(\alpha\) for all
	\(\alpha\in I_1\).

	Suppose \(1\leq m < \omega\) and \(\langle F^{m}_\alpha : \alpha \in
	I_m\rangle\) has been defined. We now apply \cref{FilterResemblance} with
	\(H = F\), \(F = F_{m+1}\), and \(G =F_m\). This yields a set
	\(I_{m+1}\subseteq I_m\) in \(F\) and a sequence \(\langle F^{m+1}_\alpha :
	\alpha \in I_m\rangle\) of countably complete filters on \(\delta\) such
	that \(F^{m+1}_\alpha \sE F^{m}_\alpha\) for all \(\alpha\in I_{m+1}\) and
	\[F_{m+1} \subseteq F\text{-}\lim_{\alpha\in I_{m+1}}F^{m+1}_\alpha\]

	This completes the definition of the sets \(I_1\supseteq I_2\supseteq
	\cdots\) and sequences \(\langle F^{m}_\alpha : \alpha \in I_m\rangle\)  for
	\(1\leq m < \omega\).

	Now let \(I = \bigcap_{1\leq m < \omega} I_m\). Since \(F_0\) is countably
	complete, \(I\) is nonempty, so we can fix an ordinal \(\alpha\in I\). Then
	since \(\alpha\in I_m\) for all \(1\leq m < \omega\), \[F^1_\alpha \sgE
	F^2_\alpha \sgE F^3_\alpha \sgE\cdots\] Since \(F^1_\alpha\) concentrates on
	\(\alpha < \delta\), this contradicts the minimality of \(\delta\).
\end{proof}

Recall the following definition, due to Jech \cite{JechStationary}:
\begin{defn}
	Assume \(\delta\) is a regular cardinal. The {\it canonical order on
	stationary sets} is defined on stationary sets \(S,T\subseteq \delta\) by
	setting \(S < T\) if there is a closed unbounded set \(C\subseteq \delta\)
	such that \(S\cap \alpha\) is stationary in \(\alpha\) for all \(\alpha\in
	C\cap T\).
\end{defn}

\begin{defn}
	For any ordinal \(\alpha\), let \(\mathcal C_\alpha\) denote the filter of
	closed cofinal subsets of \(\alpha\).
\end{defn}

\begin{defn}
	Suppose \(F\) is a filter on a set \(X\) and \(S\) is a set such that \(F\)
	does not concentrate on the complement of \(S\). The {\it projection of
	\(F\) on \(S\)} is the filter defined by \[F\mid S = \{A\cap S : A\in F\}\]
\end{defn}

The following proposition connects the canonical order on stationary sets and
the Ketonen order on filters:
\begin{prp}\label{StationaryKetonen} Suppose \(\delta\) is a regular cardinal
and \(S\) and \(T\) are stationary subsets of \(\delta\). Then \(S < T\) implies
\(\mathcal C_\delta\mid S\sE \mathcal C_\delta\mid T\).
	\begin{proof}
		Fix a closed unbounded set \(C\subseteq \delta\) such that \(S\cap
		\alpha\) is stationary in \(\alpha\) for all \(\alpha\in C\cap T\). Note
		that \(C\cap T\in \mathcal C_\delta\mid T\), and for all \(\alpha\in
		C\cap T\), \(\mathcal C_\alpha\mid S\) is a countably complete filter
		concentrating on ordinals less than \(\alpha\).
		\begin{clm}
			\(C_\delta\mid S \subseteq (\mathcal C_\delta\mid
			T)\text{-}\lim_{\alpha\in C\cap T} \mathcal C_\alpha\mid S\).
		\end{clm}
		\begin{proof}
			Suppose \(A\in \mathcal C_\delta\mid S\). We will show that \(A\in
			(\mathcal C_\delta\mid T)\text{-}\lim_{\alpha\in C\cap T} \mathcal
			C_\alpha\mid S\). Fix \(E\in C_\delta\) such that \(S\cap E\subseteq
			A\). Let \(E'\) be the set of accumulation points of \(E\). Then for
			any \(\alpha\in E'\), \(S\cap (E\cap \alpha)\subseteq A\) and
			\(E\cap \alpha\in \mathcal C_\alpha\), so \(A\in \mathcal
			C_\alpha\mid S\). Thus \[E'\cap C\cap T\subseteq \{\alpha \in C\cap
			T : A\in \mathcal C_\alpha\mid S\}\] Since \(E'\cap C\in \mathcal
			C_\delta\), \(E'\cap C\cap T\in \mathcal C_\delta\mid T\), and
			therefore \(\{\alpha \in C\cap T : A\in \mathcal C_\alpha\mid S\}\in
			\mathcal C_\delta\mid T\). It follows that \(A\in (\mathcal
			C_\delta\mid T)\text{-}\lim_{\alpha\in C\cap T} \mathcal
			C_\alpha\mid S\), as desired.
		\end{proof}
		The claim implies \(C_\delta\mid S\sE \mathcal C_\delta\mid T\), as
		desired.
	\end{proof}
\end{prp}
As a corollary of \cref{FilterWellfounded} and \cref{StationaryKetonen}, we have
the following theorem of Jech:
\begin{cor}
	The canonical order on stationary sets is wellfounded.\qed
\end{cor}

\section{The linearity of the Ketonen order}\label{LinKetSection}
In this final section, we prove a converse to \cref{SeedKet}, which can also be
seen as a partial positive answer to \cref{LipUA}. We say that {\it the Ketonen
order is linear} if  for all ordinals \(\delta\), the Ketonen order on
\(\mathscr B(\delta)\) is a linear order. The Ketonen order is linear if and
only if its restriction to \(\Un\) is a linear order.

\begin{thm}\label{LinKetThm}\index{Ketonen order!linearity}
The Ketonen order is linear if and only if the Ultrapower Axiom holds.
\end{thm}
Given \cref{KOChars}, the linearity of the Ketonen order would appear to be a
much weaker assumption than UA: the linearity of the Ketonen order only
guarantees comparisons \((k,h): (M_U,M_W)\to N\) such that \(h\) is an internal
ultrapower embedding of \(M_W\), while UA asserts the existence of comparisons
with both \(k\) and \(h\) internal. How can one transform partially internal
comparisons into the fully internal comparisons required by UA?

To properly describe it, let us make some definitions:
\begin{defn}
Suppose \(M_0,\) \(M_1,\) and \(N\) are transitive models of ZFC and
\[(k_0,k_1): (M_0,M_1)\to N\] are elementary embeddings.
\begin{itemize}
\item \((k_0,k_1)\) is {\it \(0\)-internal} if \(k_0\) is definable over \(M_0\).\index{Comparison!\(0\)-internal, \(1\)-internal}
\item \((k_0,k_1)\) is {\it \(1\)-internal} if \(k_1\) is definable over
\(M_1\).
\item \((k_0,k_1)\) is {\it internal} if it is both \(0\)-internal and
\(1\)-internal.
\end{itemize}
\end{defn}
We indicated above that the difficulty in proving \cref{LinKetThm} is that it is
not clear how to transform the \(1\)-internal comparisons given by the linearity
of the Ketonen order into the internal comparisons required to witness UA. In
fact, it is simply impossible to do this in general, since as a consequence of
the proof of \cref{ZFCComparison}, \(1\)-internal comparisons can be proved to
exist in ZFC alone.
\begin{prp}
Any pair of ultrapower embeddings has a \(0\)-internal ultrapower comparison and
a \(1\)-internal ultrapower comparison.\qed
\end{prp}
Thus the true power of the linearity of the Ketonen order lies not in the mere
existence of \(1\)-internal comparisons \((k,h)\) but rather in the existence of
\((k,h)\) witnessing \(U\sE W\) (or \(W\E U\)); that is, with the additional
property \(k(\id_U) < h(\id_W)\).

\cref{LinKetThm} is an immediate consequence of our next theorem, which shows
how to explicitly define a comparison of a pair of ultrafilters:

\begin{thm}\label{Reciprocity1}
	Assume the Ketonen order is linear. Suppose \(\epsilon\) and \(\delta\) are
	ordinals. Suppose \(U\in \mathscr B(\epsilon)\) and \(W\in \mathscr
	B(\delta)\).
	\begin{itemize}
		\item Let \(W_*\) be the least element of \(j_U(\mathscr
		B(\delta),\sE)\) extending \(j_U[W]\).
		\item Let \(U_*\) be the least element of \(j_W(\mathscr
		B(\epsilon),\sE)\) extending \(j_W[U]\).
	\end{itemize}
	Then \((j_{W_*}^{M_U},j_{U_*}^{M_W})\) is a comparison of \((j_U,j_W)\).
\end{thm}

The definitions of \(W_*\) and \(U_*\) rely on the fact that \(j_U(\mathscr
B(\delta),\sE)\) and \(j_W(\mathscr B(\epsilon),\sE)\) are wellorders, not only
in \(M_U\) and \(M_W\) but also by absoluteness in the true universe \(V\).
This, however, is not the main use of the linearity of the Ketonen order in the
proof. Indeed, it is consistent that there is a pair of countably complete
ultrafilters \(U\) and \(W\) such that the minimum extensions \(W_*\) and
\(U_*\) are well-defined yet \((j_U,j_W)\) admits no comparison.\footnote{Take
\(U\) and \(W\) to be Mitchell incomparable normal ultrafilters. Apply
\cref{KetMO} and \cref{NormalGeneration} to see that \(j_U(W)\) and \(j_W(U)\)
are the {\it only} extensions of \(j_U[W]\) and \(j_W[U]\) in \(M_U\) and
\(M_W\) respectively.} Instead we will use the linearity of the Ketonen order to
compare \((j_{W_*}^{M_U}\circ j_U,j_{U_*}^{M_W}\circ j_W)\):
\begin{comment}
Ultrafilter sums are the natural construction for producing an ultrafilter whose
associated ultrapower embedding is a given two-step iterated ultrapower:

\begin{defn}
Suppose \(U\) is an ultrafilter on \(X\), \(I\) is a set in \(U\), and \(\langle
W_i : i \in I\rangle\) is a sequence of ultrafilters on \(Y\). The {\it
\(U\)-sum of  \(\langle W_i : i \in I\rangle\)} is the ultrafilter defined by
\[U\text{-}\sum_{i\in I}W_i = \{A\subseteq X\times Y : \{i\in I : A_i \in
W_i\}\in U\}\]
\end{defn}
In the definition above, if \(A\subseteq X\times Y\) and \(i\in X\), then \(A_i
= \{j\in Y : (i,j)\in A\}\).

There is an obvious connection between sums and limits: the projection of a sum
of ultrafilters onto its second coordinate is precisely equal to the limit of
those ultrafilters.

\begin{lma}\label{SumPower}
Suppose \(U\) is an ultrafilter, \(I\) is a set in \(U\), and \(\langle W_i : i
\in I\rangle\) is a sequence of ultrafilters on \(Y\). Let \(Z = [\langle W_i :
i \in I\rangle]_U\) and let \(D =U\text{-}\sum_{i\in I}W_i\). Then \(M_D =
M^{M_U}_Z\),  \(j_D = j_Z^{M_U}\circ j_U\), and \(\id_D =
(j_Z^{M_U}(\id_U),\id_Z)\).\qed
\end{lma}

\begin{defn}
Suppose \(U\) is a countably complete ultrafilter, \(I\) and \(J\) are sets in
\(U\), and \(\langle W_i : i\in I\rangle\) and \(\langle Z_i : i\in J\rangle\)
are sequences of countably complete ultrafilters on ordinals. The {\it Ketonen
order modulo \(U\)} is defined by setting \(\langle W_i : i\in I\rangle \sE
\langle Z_i : i\in J\rangle\) modulo \(U\) if \(W_i \sE Z_i\) for \(U\)-almost
all \(i\in I\cap J\).
\end{defn}

\begin{lma}
If \(U\) is a countably complete ultrafilter, then the Ketonen order modulo
\(U\) is wellfounded.
\begin{proof}
This is an immediate consequence of the wellfoundedness of the Ketonen order and
the countable completeness of \(U\).
\end{proof}
\end{lma}

The following is a combinatorial reformulation of \cref{Reciprocity1}.
\begin{lma}\label{LinComp}
Suppose \(\delta\) is an ordinal and the Ketonen order is linear on \(\mathscr
B(\delta)\). Suppose \(U,W\in \mathscr B(\delta)\).
\begin{itemize}
\item Let \(\langle W_\alpha : \alpha\in I\rangle\) be \(\sE\)-minimal modulo
\(U\) such that \(W= U\text{-}\lim_{\alpha\in I} W_\alpha\).
\item Let \(\langle U_\beta : \beta\in J\rangle\) be \(\sE\)-minimal modulo
\(W\) such that \(U= W\text{-}\lim_{\beta\in J} U_\beta\).
\end{itemize}
Then \[U\text{-}\sum_{\alpha\in I} W_\alpha \cong W\text{-}\sum_{\beta\in J}
U_\beta\] In fact, let \(f: \delta\times \delta\to \delta\times \delta\) be
defined by \(f(\alpha,\beta) = (\beta,\alpha)\). Then
\[f_*(U\text{-}\sum_{\alpha\in I} W_\alpha) \KE W\text{-}\sum_{\beta\in J}
U_\beta\]
\end{lma}

It is probably clear enough, but let us go ahead and explain why this implies
\cref{LinKetThm}:

\begin{proof}[Proof of \cref{LinKetThm}] Suppose \(i : V\to M\) and \(j : V\to
	N\) are ultrapower embeddings. We must show that \((i,j)\) has an internal
	ultrapower comparison.

	Fix countably complete ultrafilters \(U\) and \(W\) on ordinals such that
	\(i = j_U\) and \(j = j_W\). Let \(\langle W_\alpha : \alpha\in I\rangle\)
	be \(\sE\)-minimal modulo \(U\) such that \(W= U\text{-}\lim_{\alpha\in I}
	W_\alpha\). Let \(\langle U_\beta : \beta\in J\rangle\) be \(\sE\)-minimal
	modulo \(W\) such that \(U= W\text{-}\lim_{\beta\in J} U_\beta\). By
	\cref{SumComparison},
	\begin{equation}\label{Isomorphism}U\text{-}\sum_{\alpha\in I} W_\alpha \cong W\text{-}\sum_{\beta\in J} U_\alpha\end{equation}
	Let \(W_* = [\langle W_\alpha : \alpha\in I\rangle]_U\) and let \(U_*=[\langle U_\beta :\beta\in J\rangle]_W\). Then by \cref{Isomorphism} and \cref{SumPower},
	\begin{align*}
		M_{W_*}^{M_U} &= M_{U_*}^{M_W}\\
		j_{W_*}^{M_U}\circ j_U &= j_{U_*}^{M_W}\circ j_W
	\end{align*}
	Thus \((j_{W_*}^{M_U},j_{U_*}^{M_W})\) is an internal ultrapower comparison of \((j_U,j_W) = (i,j)\), as desired. This completes the proof.
\end{proof}

The strategy of the proof of \cref{LinComp} is roughly to show that neither \(U\text{-}\sum_{\alpha\in I} W_\alpha \sE W\text{-}\sum_{\beta\in J} U_\beta\) nor \(U\text{-}\sum_{\alpha\in I} W_\alpha \sgE W\text{-}\sum_{\beta\in J} U_\beta\) can hold. By the linearity of the Ketonen order, we must therefore have \(U\text{-}\sum_{\alpha\in I} W_\alpha = W\text{-}\sum_{\beta\in J} U_\beta\).

A minor technical issue with this strategy, which we will address later, is that the Ketonen order is only defined on ultrafilters on ordinals, so these ultrafilter sums cannot even be compared in the Ketonen order. Before we turn to this, we show the main sense in which these two sums bear no relation to one another in the strict Ketonen order. The following lemma makes precise the sense in which \(U\text{-}\sum_{\alpha\in I} W_\alpha \not\sgE W\text{-}\sum_{\beta\in J} U_\beta\) in the context of \cref{LinComp}:
\end{comment}
\begin{lma}\label{SumComparison}
Suppose \(\epsilon\) and \(\delta\) are ordinals. Suppose \(U\in \mathscr B(\epsilon)\) and \(W\in \mathscr B(\delta)\).
\begin{itemize}
\item Let \(W_*\) be an element of \(j_U(\mathscr B(\delta))\) extending \(j_U[W]\).
\item Let \(U_*\) be a minimal element of \(j_W(\mathscr B(\epsilon),\sE)\) extending \(j_W[U]\).
\end{itemize}
For any \(1\)-internal ultrapower comparison \[(k,h) : (M^{M_U}_{W_*},M^{M_W}_{U_*})\to P\] of \((j_{W_*}^{M_U}\circ j_U ,j_{U_*}^{M_W}\circ j_W)\), the following hold:
\begin{align}
	h(j_{U_*}^{M_W}(\id_W))&\leq k(\id_{W_*})\label{bs}\\
	h(\id_{U_*})&\leq k(j_{W_*}^{M_U}(\id_U))\label{as}
\end{align}
\begin{proof}

Let us direct the reader's attention to the key diagram, \cref{LinKetFig}.
\begin{figure}
	\center
	\includegraphics[scale=.6]{LinKet.pdf}
	\caption{The proof of \cref{SumComparison}.}\label{LinKetFig}
\end{figure}

We first prove \cref{bs}. By \cref{LimitFactor}, there is an elementary embedding \(e : M_W\to M_{W_*}^{M_U}\) such that \(e\circ j_W = j^{M_U}_{W_*}\circ j_U\) and \(e(\id_W) = \id_{W_*}\).
We now apply the minimality of internal embeddings (\cref{MinDefEmb}). Note that \(k\circ e\) and \(h\circ j^{M_W}_{U_*}\) are both elementary embeddings from \(M_W\) to \(P\), but \(h\circ j^{M_W}_{U_*}\) is an internal ultrapower embedding. Thus by \cref{MinDefEmb}, \(h(j^{M_W}_{U_*}(\alpha)) \leq k(e(\alpha))\) for all ordinals \(\alpha\). It follows in particular that \(h(j_{U_*}^{M_W}(\id_W))\leq k(e(\id_W)) = k(\id_{W_{*}})\), proving \cref{bs}.

We now prove \cref{as}. To reduce subscripts, we define: \[\alpha = j_{W_*}^{M_U}(\id_U)\] Let \(Z\) be the \(M_W\)-ultrafilter on \(j_W(\epsilon)\) derived from \(h\circ j_{U_*}^{M_W}\) using \(k(\alpha)\), so \[Z = (h\circ j^{M_W}_{U_*})^{-1}\left[\pr {k(\alpha)} {}\right]\] Since \(h\circ j_{U_*}^{M_W}\) is an internal ultrapower embedding of \(M_W\), \(Z\) is a countably complete ultrafilter of \(M_W\); in other words, \(Z\in j_W(\mathscr B(\epsilon))\). Moreover, it is not hard to compute that \(Z\) extends \(j_W[U]\), or equivalently \(j_W^{-1}[Z] = U\):
\begin{align}
j_W^{-1}[Z] &= j_W^{-1}[(h\circ j^{M_W}_{U_*})^{-1}[\pr {k(\alpha)} {}]]\nonumber\\
&= (h\circ j_{U_*}^{M_W}\circ j_W)^{-1}[\pr {k(\alpha)} {}]\nonumber\\
&= (k\circ j_{W_*}^{M_U}\circ j_U)^{-1}[\pr {k(\alpha)} {}]\nonumber\\
&= (j_{W_*}^{M_U}\circ j_U)^{-1}[k^{-1}[\pr {k(\alpha)} {}]]\nonumber\\
&= (j_{W_*}^{M_U}\circ j_U)^{-1}[\pr {\alpha} {}]   \nonumber  \\
&= j_U^{-1}[(j_{W_*}^{M_U})^{-1}[\pr {j_{W_*}^{M_U}(\id_U)} {}]]\nonumber\\
&= j_U^{-1}[\pr {\id_U} {}] = U\nonumber
\end{align}
Since \(U_*\) is a minimal element of \(j_W(\mathscr B(\epsilon),\sE)\) extending  \(j_W[U]\), \(M_W\) satisfies \(Z\not \sE U_*\).

Since \(Z\) is derived from \(h\circ j_{U_*}^{M_W}\) using \(k(\alpha)\), there is a factor embedding \(i : (M_{Z})^{M_W}\to P\) specified by the following properties:
\begin{align}i\circ j^{M_W}_{Z} &= h\circ j_{U_*}^{M_W}\label{Compy}\\
	i(\id_{Z}) &= k(\alpha)\label{Motion}\end{align}
Note that these properties define \(i\) over \(M_W\). Therefore by \cref{Compy}, \((i,h)\) is a \(1\)-internal ultrapower comparison of \((j_{Z}^{M_W},j_{U_*}^{M_W})\) in \(M_W\).
The fact that \(Z\not \sE U_*\) in \(M_W\) implies \[h(\id_{U_*})\leq i(\id_Z) = k(\alpha) = k(j_{W_*}^{M_U}(\id_U))\]
proving \cref{as}.
\end{proof}
\end{lma}

\cref{SumComparison} can be read as asserting that the natural ultrafilter representing the embedding \(j_{U_*}^{M_W}\circ j_W\) is not strictly above the one representing \(j_{W_*}^{M_U}\circ j_U\) in the Ketonen order. To make this precise, we need to define what these natural ultrafilters. This is related to the well-known notion of an ultrafilter sum:

\begin{defn}
	Suppose \(U\) is an ultrafilter on \(X\), \(I\) is a set in \(U\), and \(\langle W_i : i \in I\rangle\) is a sequence of ultrafilters on \(Y\). The {\it \(U\)-sum of  \(\langle W_i : i \in I\rangle\)} is the ultrafilter defined by
	\[U\text{-}\sum_{i\in I}W_i = \{A\subseteq X\times Y : \{i\in I : A_i \in W_i\}\in U\}\]
\end{defn}
In the definition above, if \(A\subseteq X\times Y\) and \(i\in X\), then \(A_i = \{j\in Y : (i,j)\in A\}\).

There is an obvious connection between sums and limits: the projection of a sum of ultrafilters onto its second coordinate is precisely equal to the limit of those ultrafilters.

\begin{lma}
	Suppose \(U\) is an ultrafilter, \(I\) is a set in \(U\), and \(\langle W_i : i \in I\rangle\) is a sequence of ultrafilters on \(Y\). Let \(Z = [\langle W_i : i \in I\rangle]_U\) and let \(D =U\text{-}\sum_{i\in I}W_i\). Then \(M_D = M^{M_U}_Z\),  \(j_D = j_Z^{M_U}\circ j_U\), and \(\id_D = (j_Z^{M_U}(\id_U),\id_Z)\).\qed
\end{lma}

Motivated this lemma, we introduce the following nonstandard notation.

\begin{defn}\index{Sum of ultrafilters}\index{\(U\text{-}\sum\) (\(U\)-sum)}
	Suppose \(U\) is an ultrafilter on \(X\), and \(W_*\) is an \(M_U\)-ultrafilter on \(j_U(Y)\). Then \(U\text{-}\sum W_*\) denotes the ultrafilter on \(X\times Y\) derived from \(j_{W_*}^{M_U}\circ j_U\) using \((j_{W_*}^{M_U}(\id_U),\id_{W_*})\).
\end{defn}

In this section we will only require sums of ultrafilters where \(W_*\in M_U\), but it is just more convenient not to choose a representative for \(W_*\).

\begin{lma}\label{SumPower}
	Suppose \(U\) is an ultrafilter and \(W_*\) is an \(M_U\)-ultrafilter on \(j_U(Y)\). Then  \(j_{U\text{-}\sum W_*} = j_{W_*}^{M_U}\circ j_U\), and \(\id_{U\text{-}\sum W_*} = (j_{W_*}^{M_U}(\id_U),\id_{W_*})\).\qed
\end{lma}

In the context of \cref{Reciprocity1}, we would like to use \cref{SumComparison} to conclude that the ultrafilters \(U\text{-}\sum W_*\) and \(W\text{-}\sum U_*\) are either equal or incomparable in the Ketonen order, and thus conclude by the linearity of the Ketonen order that \(U\text{-}\sum W_* = W\text{-}\sum U_*\). The only remaining problem is that \(U\text{-}\sum W_*\) and \(W\text{-}\sum U_*\) are not ultrafilters on ordinals. But obviously we can associate Ketonen orders to an arbitrary wellorder:

\begin{defn}\index{Ketonen order!associated to a wellorder}
	Suppose \((X,\prec)\) is a wellorder. The {\it Ketonen order associated to \((X,\prec)\)} is the order \((\mathscr B(X),\prec^{\Bbbk})\) defined on \(U,W\in \mathscr B(X)\) by setting \(U \prec^{\Bbbk} W\) if there exist \(I\in W\) and \(\langle U_x : x\in I\rangle\in \prod_{x\in I} \mathscr B(X,X_{\prec x})\) such that \(U = W\text{-}\lim_{x\in I} U_x\).
\end{defn}

If \((X,\prec)\) and \((X',\prec')\) are isomorphic wellorders, then the associated Ketonen orders are also isomorphic, so in particular all the characterizations of the Ketonen order generalize to arbitrary wellorders:

\begin{lma}\label{KOWOChar}
	Suppose \((X,\prec)\) is a wellorder and \(U,W\in \mathscr B(X)\). Then the following are equivalent:
	\begin{enumerate}[(1)]
		\item \(U\prec^\Bbbk W\).
		\item There is a \(1\)-internal ultrapower comparison \((k,h) : (M_U,M_W)\to N\) of \((j_U,j_W)\) such that \(k(\id_U)\prec^* h(\id_W)\) where \({\prec}^* =k(j_U(\prec)) = h(j_W(\prec))\).\qed
	\end{enumerate}
\end{lma}

It is convenient to introduce some notation for the statement of \cref{PreciseReciprocity}:

\begin{defn}\label{GodelDef}
	Let \(\text{flip} : \text{Ord}\times  \text{Ord} \to  \text{Ord}\times  \text{Ord}\) be defined by \(\text{flip}(\alpha,\beta) = (\beta,\alpha)\). Let \(\prec\) denote the G\"odel order on \(\text{Ord}\times \text{Ord}\).
\end{defn}

The only property of the G\"odel order that we need is that \((\alpha_0,\beta_0)\prec (\alpha_1,\beta_1)\) implies that either \(\alpha_0 < \alpha_1\) or \(\beta_0 < \beta_1\).

\begin{lma}\label{PreciseReciprocity}
	Suppose \(\epsilon\) and \(\delta\) are ordinals. Suppose \(U\in \mathscr B(\epsilon)\) and \(W\in \mathscr B(\delta)\). Assume the Ketonen order \((\mathscr B(\epsilon\times \delta),\prec^{\Bbbk})\) is linear.
	\begin{itemize}
		\item Let \(W_*\) be the least element of \(j_U(\mathscr B(\delta),\sE)\) extending \(j_U[W]\).
		\item Let \(U_*\) be the least element of \(j_W(\mathscr B(\epsilon),\sE)\) extending \(j_W[U]\).
	\end{itemize}
	Then \(U\text{-}\sum W_* = \textnormal{flip}_*(W\text{-}\sum U_*)\).
	\begin{proof}
		Assume towards a contradiction that \(U\text{-}\sum W_* \prec^{\Bbbk} \textnormal{flip}_*(W\text{-}\sum U_*)\).
		The following identities are easily verified using \cref{SumPower}:
		 \begin{align*}
		 	j_{U\text{-}\sum W_*} &= j_{W_*}^{M_U} \circ j_U & 	j_{\textnormal{flip}_*(W\text{-}\sum U_*)} &= j_{U_*}^{M_W} \circ j_W\\
		 	\id_{U\text{-}\sum W_*} &= (j_{W_*}^{M_U}(\id_U),\id_{W_*})& \id_{\textnormal{flip}_*(W\text{-}\sum U_*)} &= (\id_{U_*}, j_{U_*}^{M_W}(\id_W))
		 \end{align*}
		By  \cref{KOWOChar}, the assumption that \(U\text{-}\sum W_* \prec^{\Bbbk} \textnormal{flip}_*(W\text{-}\sum U_*)\) is equivalent to the existence of a \(1\)-internal comparison \[(k,h) : (M_{W_*}^{M_U},M_{U_*}^{M_W})\to N\] of \((j_{W_*}^{M_U} \circ j_U,  j_{U_*}^{M_W} \circ j_W)\) such that
		\[k(j_{W_*}^{M_U}(\id_U),\id_{W_*}) \prec h(\id_{U_*}, j_{U_*}^{M_W}(\id_W))\]
		Therefore either \(k(j_{W_*}^{M_U}(\id_U)) < h(\id_{U_*})\) or \(k(\id_{W_*}) < h(j_{U_*}^{M_W}(\id_W))\), contradicting \cref{SumComparison}.

		A symmetric argument shows that we cannot have \(\textnormal{flip}_*(W\text{-}\sum U_*) \prec^{\Bbbk} U\text{-}\sum W_*\) either. Thus by the linearity of \((\mathscr B(\epsilon\times\delta),\prec^\Bbbk)\), we must have \(U\text{-}\sum W_* = \textnormal{flip}_*(W\text{-}\sum U_*)\), which proves the theorem.
	\end{proof}
\end{lma}

As an immediate consequence, we can prove \cref{Reciprocity1}:
\begin{proof}[Proof of \cref{Reciprocity1}]
	Let \(\alpha\) be the ordertype of the G\"odel order on \(\epsilon\times \delta\). Since the Ketonen order is linear on \(\mathscr B(\alpha)\), the isomorphic order \((\mathscr B(\epsilon\times \delta),\prec^\Bbbk)\) is also linear. Thus we can apply \cref{PreciseReciprocity} to conclude that \(U\text{-}\sum W_* = \text{flip}_*(W\text{-}\sum U_*)\). In particular, \(U\text{-}\sum W_*\cong W\text{-}\sum U_*\), so applying \cref{SumPower},
	\[j_{W_*}^{M_U}\circ j_U = j_{U\text{-}\sum W_*} =j_{W\text{-}\sum U_*} = j_{U_*}^{M_W} \circ j_W\]
	Thus \((j_{W_*}^{M_U},j_{U_*}^{M_W})\) is a comparison of \((j_U,j_W)\), as desired.
\end{proof}

Let us make some comments on this theorem. It is not immediately obvious from the definition that the linearity of the Ketonen order on \(\mathscr B(\lambda)\) implies the linearity of the Ketonen order on \(\mathscr B(\delta)\) for all ordinals \(\delta < \lambda^+\).\footnote{Note that if \(\kappa\) is regular, then for any \(n < \omega\), the collection of subsets of \(\kappa^n\) of ordertype less than \(\kappa^n\) forms a  \(\kappa\)-complete ideal; this is closely related to the Milner-Rado Paradox. Therefore for example if \(\kappa\) is \(2^\kappa\)-strongly compact, there is a \(\kappa\)-complete ultrafilter on \(\kappa^n\) that does not concentrate on a set of ordertype less than \(\kappa^n\). (It suffices that \(\kappa\) is measurable.) This suggests it may be nontrivial to reduce the linearity of \((\mathscr B(\kappa^2),\sE)\) to that of \((\mathscr B(\kappa),\sE)\) by a direct combinatorial argument.}

\begin{defn}
	Suppose \(\lambda\) is a cardinal.
	\begin{itemize}
		\item \(\text{UA}_{<\lambda}\) is the assertion that any pair of ultrapower embeddings of width less than \(\lambda\) have an internal ultrapower comparison.
		\item \(\text{UA}_{\leq\lambda}\) is another way of writing \(\text{UA}_{<\lambda^+}\).
	\end{itemize}
\end{defn}

\begin{cor}
	Suppose \(\lambda\) is an infinite cardinal and the Ketonen order is linear on \(\mathscr B(\lambda)\). Then \(\textnormal{UA}_{\leq\lambda}\) holds. In particular, the Ketonen order is linear on \(\mathscr B(\delta)\) for all \(\delta < \lambda^+\).
	\begin{proof}
		Suppose \(U\) and \(W\) are ultrafilters on \(\lambda\). To see \(\textnormal{UA}_{\leq\lambda}\), it suffices to show that \((j_U,j_W)\) has a comparison. Since the Ketonen order \((\mathscr B(\lambda),\sE)\) is linear, so is \((\mathscr B(X),\prec^{\Bbbk})\) whenever \((X,\prec)\) is a wellorder of ordertype \(\lambda\).
		Since \(\lambda\) is an infinite cardinal, the G\"odel order on \(\lambda\times \lambda\) has ordertype \(\lambda\). Thus \((\mathscr B(\lambda\times\lambda),\prec^{\Bbbk})\) is linear, and so we can apply \cref{PreciseReciprocity} and the proof of \cref{Reciprocity1} to conclude that \((j_U,j_W)\) has a comparison.
	\end{proof}
\end{cor}

Surely with some extra work one can prove the following conjecture:
\begin{conj}
	If the Ketonen order is linear on countably complete incompressible ultrafilters, then the Ultrapower Axiom holds.
\end{conj}

\begin{comment}
\begin{defn}
	A {\it structure} is a pair \((X,R)\) where \(X\) is a set and \(R\) is a binary relation on \(X\). For any \(x\in X\), \(R_x = \{w\in X : w\mathrel{R} x\}\).
\end{defn}

\begin{defn}
	Suppose \((X,R)\) is a structure. The {\it Ketonen structure \((\mathscr B(X),\hat R)\)} is defined on \(U,W\in \mathscr B(X)\) by setting \(U\mathrel{\hat R} W\) if there exist \(I\in W\) and \(\langle U_x : x\in I\rangle\in \prod_{x\in I} \mathscr B(X,R_x)\) such that \(U = W\text{-}\lim_{x\in I} U_x\).
\end{defn}

This more general Ketonen order enjoys all the usual characterizations of the Ketonen order:
\begin{lma}
	Suppose \((X,R)\) is a structure and \(U,W\in \mathscr B(X)\). The following are equivalent:
	\begin{enumerate}[(1)]
		\item \(U\mathrel{\hat R} W\).
		\item \(j_W[U]\) extends to an element of \(\mathscr B^{M_W}(j_W(X), j_W(R)_{\id_W})\).
		\item There is a \(1\)-internal ultrapower comparison \((k,h) : (M_U,M_W)\to N\) of \((j_U,j_W)\) such that \(k(\id_U)\mathrel{R^*} h(\id_W)\) where \(R^* =k(j_U(R)) = h(j_W(R))\).\qed
	\end{enumerate}
\end{lma}

\begin{lma}
	Suppose \((X,R)\) and \((Y,S)\) are structures. If \(f : (X,R)\to (Y,S)\) is an injective homomorphism, then \(f_* : (\mathscr B(X),\hat R)\to( \mathscr B(Y),\hat S)\) is an injective homomorphism.\qed
\end{lma}

We can restate \cref{SumComparison} in terms of the Ketonen structure given by a certain the relation \(\prec\) on \(\delta\times \epsilon\) defined by \((\alpha_0,\beta_0)\prec (\alpha_1,\beta_1)\) if \(\alpha_0 < \alpha_1\) or \(\beta_0 < \beta_1\):
\begin{lma}
	Suppose \(\epsilon\) and \(\delta\) are ordinals. Suppose \(U\in \mathscr B(\epsilon)\) and \(W\in \mathscr B(\delta)\).
	\begin{itemize}
		\item Let \(W_*\) be an element of \(j_U(\mathscr B(\delta))\) extending \(j_U[W]\).
		\item Let \(U_*\) be a minimal element of \(j_W(\mathscr B(\delta),\sE)\) extending \(j_W[U]\).
	\end{itemize}
	 Let \(f : \delta\times\epsilon\to \epsilon\times \delta\) be the coordinate-switching function.
	 Then \(U\text{-}\sum W_*\not \mathrel{\hat \prec} f_*(W\text{-}\sum U_*)\).\qed
\end{lma}

\begin{thm}
	Suppose \(\epsilon\) and \(\delta\) are ordinals. Suppose \(U\in \mathscr B(\epsilon)\) and \(W\in \mathscr B(\delta)\). Assume the Ketonen order is linear on \(\mathscr B( \delta\cdot \epsilon)\).
		\begin{itemize}
		\item Let \(W_*\) be the least element of \(j_U(\mathscr B(\delta))\) extending \(j_U[W]\).
		\item Let \(U_*\) be the least element of \(j_W(\mathscr B(\delta),\sE)\) extending \(j_W[U]\).
	\end{itemize}
	Let \(f : \delta\times\epsilon\to \epsilon\times \delta\) be the coordinate-switching function. Then  \(U\text{-}\sum W_* = f_*(W\text{-}\sum U_*)\).
	\begin{proof}

	\end{proof}
\end{thm}

\begin{proof}[Proof of \cref{LinComp}]
Let \(\preceq_0\) defined by \((\alpha_0,\beta_0) \preceq_0 (\alpha_1,\beta_1)\) if \(\alpha_0 \leq \alpha_1\) and \(\beta_0 \leq \beta_1\). Let \(\preceq\) be any wellorder on \(\delta\times \delta\) of ordertype \(\delta\) extending the partial order \(\preceq_0\). For the remainder of the proof, let \(\sE,\E\) denote the Ketonen order on \(\mathscr B(\delta\times \delta)\) induced by \(\preceq\).

Let \(F = U\text{-}\sum_{\alpha\in I}W_\alpha\) and \(G = W\text{-}\sum_{\beta\in J}U_\beta\).

\begin{clm}
\(f_*(F) \not \sE G\).
\begin{proof}
This is precisely the content of \cref{SumComparison}. Suppose \((k,h): (M_F,M_G)\to P\) is a \(1\)-internal comparison of \((j_F,j_G)\). Then \cref{SumComparison} amounts to the assertion that \(h(\id_G) \preceq_0 k(\id_{f_*(F)})\), and hence  \(h(\id_G) \preceq k(\id_{f_*(F)})\), so \((k,h)\) does not witness \(f_*(F)\sE G\).
\end{proof}
\end{clm}
By a symmetric argument, we have:
\begin{clm}
\(G \not \sE f_*(F) \).\qed
\end{clm}

Thus by the linearity of the Ketonen order, \(f_*(F) = G\), as desired.
\end{proof}
\end{comment}
The proof of \cref{LinKetThm} that we have given here uses \L o\'s's Theorem, which makes significant use of the Axiom of Choice. With care, however, the combinatorial content of \cref{LinKetThm}, namely \cref{PreciseReciprocity}, can actually be established in ZF + DC alone. This makes the following question seem interesting:
\begin{qst}
Assume \(\textnormal{AD} + V= L(\mathbb R)\). Is the Ketonen order linear?
\end{qst}