# Good ultrafilters and highly saturated models: a friendly explanation

Paul E. Lammert<EMAIL_ADDRESS>Department of Physics, Pennsylvania State
University, University Park, PA 16802

(Date: Dec. 6, 2015)

###### Abstract.

Highly saturated models are a fundamental part of the model-theoretic
machinery of nonstandard analysis. Of the two methods for producing them,
ultrapowers constructed with the aid of $\kappa^{+}$-good ultrafilters seems
by far the less popular. Motivated by the hypothesis that this is partly due
to the standard exposition being somewhat dense, a presentation is given which
is designed to be easier to digest.

##  1\. Should you read this?

The most difficult piece of the model-theoretic machinery underlying
nonstandard analysis (NSA) is certainly the construction of polysaturated
models (more generally, $\kappa$-saturated for $\kappa>\omega^{+}$). There are
two main approaches: the ultralimit method and the good ultrafilter method.
Stroyan and Luxemburg[5] and the recent volume[4] edited by Loeb and Wolff
contain detailed proofs using ultralimits. This method has the advantage that
at least the general idea seems clear enough. Lindstrøm’s lectures[3] is very
unusual in adopting the good ultrafilter method, which allows use of plain
ultrapower construction by relying on special properties of the ultrafilter.
This facilitates using ultrapowers to directly reason about nonstandard
universes; the ultralimit construction is too unwieldy for that. Lindstrøm
essentially copies the proof of Chang & Keisler[1] (itself a fleshing-out of
Kunen[2]) of the existence of $\kappa^{+}$-saturated ultraproducts, describing
it as “an interesting, but quite technical piece of infinitary combinatorics”.
To me, “opaque” seemed an apt description. The following attempt at
clarification is offered firstly to others who are not model theorists or set
theorists, but are interested in using nonstandard analysis (or model theory
more generally) in their home fields. In mathematical essence, it follows §6.1
of Chang & Keisler. The difference is primarily one of presentation.

Here is a brief description of the body of the paper, highlighting novel
elements. §2.1 and 2.2 very briefly recall ultraproducts and saturation.
Rather than just showing that the definition of good ultrafilter works, §2.3
follows some intution vaguely inspired by modal logic to deduce a condition on
an ultrafilter which endows an untraproduct with $\kappa$-saturation. The
condition is reformulated and abstracted into an order-theoretic definition of
good in §2.4 in §2.4 and used in the first main Thm. 2.3. That may seem to be
gratuitous generalization, but it has some naturality, and the domain side of
the abstract version is maintained through the second main Thm. 3.1,
clarifying a little what is involved, with no cost in complication. In §3, the
construction of a $\kappa^{+}$-good ultrafilter on $\kappa$ is given,
structured as a transfinite recursion with some complications. We add sets
step-by-step to a filter to produce an ultrafilter, simultaneously building in
goodness for a set of functions. (Which set is determined by the finished
ultrafilter!) The recursion also requires a supply of a certain auxiliary raw
material — partitions of $\kappa$ with special properties, which are simply
consumed, not built into the final product in any meaningful sense. The
construction of this supply, which is completely independent of everything
else, is segregated in §4.

##  2\. What’s good about a good ultrafilter?

######  Notation 2.1.

Ordinals are denoted by greek letters $\alpha,\ldots,\mu$, but $\kappa$ will
always be an infinite cardinal and $\lambda$ and $\mu$ usually limit ordinals.
As is commonly done, we identify infinite cardinal numbers with initial
ordinals. To avert potential confusion, ordinal comparisons are denoted by
curly symbols like ‘$\prec$’, cardinal comparisons by ‘$<$’, etc. The
successor cardinal to $\kappa$ is $\kappa^{+}$. ${\mathcal{P}_{\omega}}(X)$
consists of the finite, and $\overline{{\mathcal{P}_{\omega}}}(X)$ of the
cofinite, subsets of $X$. ${\mathcal{P}}_{*}(X)$ comprises the subsets with
the same cardinality as $X$ itself (large subsets). The cardinality of a set
$X$ is denoted $|X|$, and the underlying universe of an
${\mathcal{L}}$-structure ${\mathcal{B}}$ by $|{\mathcal{B}}|$.

###  2.1. Ultraproduct models

Let ${\mathcal{L}}$ be a formal language, $({\mathcal{A}}_{i}|{i\in I})$ a
family of ${\mathcal{L}}$-structures indexed by the nonempty set $I$, and
$\mathcal{U}$ an ultrafilter on $I$. These are the raw materials for the
mod-${\mathcal{U}}$ ultraproduct $\prod_{\mathcal{U}}{\mathcal{A}}_{i}$. With
$|{\mathcal{A}}_{i}|$ the underlying universe of ${\mathcal{A}}_{i}$, the
universe of the ultraproduct is the quotient of $\prod_{i\in
I}|{\mathcal{A}}_{i}|$ by the equivalence relation $\simeq_{\mathcal{U}}$,
defined by, $(a_{i})_{i\in I}\simeq_{\mathcal{U}}(b_{i})_{i\in I}$ iff
$\\{i\in I\,|\,a_{i}=b_{i}\\}\in{\mathcal{U}}$. The equivalence class of $a$
is denoted $[a]$. The interpretation of ${\mathcal{L}}$ in the ultraproduct is
defined by: $\prod_{\mathcal{U}}{\mathcal{A}}_{i}\models\phi$ iff $\\{i\in
I\,|\,{\mathcal{A}}_{i}\models\phi\\}\in{\mathcal{U}}$.

###  2.2. Saturation

A set of formulas $\Sigma(x)$ with one free variable is satisfiable in an
${\mathcal{L}}$-structure ${\mathcal{B}}$ if there is $b\in|{\mathcal{B}}|$
such that ${\mathcal{B}}\models\Sigma[b]$. It is finitely satisfiable if every
finite subset is satisfiable. Given a subset $X\subset|{\mathcal{B}}|$, the
enrichment of the language obtained by adding names for all the elements of
$X$ is denoted ${\mathcal{L}}(X)$, and the corresponding structure by
$({\mathcal{B}},a)_{a\in X}$ (‘$a$’ being interpreted by $a$!).
${\mathcal{B}}$ is $\kappa$-saturated if for any $X\subset|{\mathcal{B}}|$
with $|X|<\kappa$, then a set of formulas $\Sigma(x)\subset{\mathcal{L}}(X)$
with one free variable is satisfiable in $({\mathcal{B}},a)_{a\in X}$ as soon
as it is finitely satisfiable.

######  Remark 2.1.

The Robinson-Zakon constructions in NSA invlve a bit more than the generic
ultraproducts appearing here: an ultrapower is taken of the superstructure
$\cup_{n\prec\omega}V_{n}(\mathcal{X})$ over a set $\mathcal{X}$
[$V_{0}(\mathcal{X})\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\mathcal{X}$,
$V_{n+1}(\mathcal{X})\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=V_{n}(\mathcal{X})\cup\mathcal{P}(V_{n}(\mathcal{X}))$];
elements of unbounded superstructure rank are ejected; and the result is
embedded into the superstructure over ${{}^{*}}\\!{\mathcal{X}}$ via Mostowski
collapse. The middle step results in a slightly different notion of
saturation. Elements of bounded rank in the ultrapower are (identified, via
Mostowski collapse, with) the internal entities. In the previous description
we should add requirements that $X$ consist of internal entities and that for
some $n$, $\Sigma(x)$ is finitely satisfiable in $V_{n}$. The difference
essentially boils down to just making sure that the ranks are bounded. Keeping
that in mind, it is not difficult to specialize to the NSA setting.

###  2.3. Sufficient conditions on ${\mathcal{U}}$ for saturation

Suppose the ultrafilter ${\mathcal{U}}$ guarantees the condition (S): Whenever
$\Sigma(x)$ with $|\Sigma|<\kappa$ is finitely satisfiable in a
mod-${\mathcal{U}}$ ultraproduct $\prod_{\mathcal{U}}{\mathcal{A}}_{i}$, then
it is satisfiable. Then, any mod-${\mathcal{U}}$ ultraproduct interpreting a
language with $|{\mathcal{L}}|<\kappa$ is $\kappa$-saturated. This follows
because for $X$ a subset of the ultraproduct with $|X|<\kappa$,
${\mathcal{L}}(X)$ is another language with cardinality less than $\kappa$ and
condition S immediately delivers what is required. Thus, we are going to
deduce a property of ${\mathcal{U}}$ which guarantees condition S.

To that end, suppose $\Sigma(x)$ with $|\Sigma|<\kappa$ is finitely
satisfiable in $\prod_{\mathcal{U}}{\mathcal{A}}_{i}$. This can be phrased in
terms of a satisfiability function

$p:{\mathcal{P}_{\omega}}(\Sigma)\rightarrow{\mathcal{U}}::\Theta\mapsto\\{i\in
I\,|\,{\mathcal{A}}_{i}\models\exists x(\wedge\Theta)\\}.$ (2.1)

$p(\Theta)$ is the set of indices of models in which the finite set of
formulas $\Theta$ is satisfiable. A binary relation-style notation is also
convenient: ‘$i\,p\,\Theta$’ is synonymous with ‘$i\in p(\Theta)$’. Clearly,
$p$ satisfies the condition

$\Theta\subseteq\Theta^{\prime}\Rightarrow p(\Theta)\supseteq
p(\Theta^{\prime}),\;\text{ equivalently
}\;i\,p\,(\Theta\cup\Theta^{\prime})\Rightarrow i\,p\,\Theta\text{ \&
}i\,p\,\Theta^{\prime}.$ (Psb)

defining the notion of a possibility function (or binary relation).

With $p$ denoting the possibility relation associated with $\Sigma$ as above,
$\Sigma$ is satisfiable if there exists
$(\Phi_{i}\in{\mathcal{P}_{\omega}}(\Sigma))_{i\in I}$ actualizing $p$ in the
sense that

$\text{(a): }i\,p\,\Phi_{i},\text{ and }\text{(b): }\text{for all
}\theta\in\Sigma,\,\\{i\in I\,|\,\theta\in\Phi_{i}\\}\in{\mathcal{U}}.$

This is because, according to (a), $p$ certifies the existence of an element
$[(a_{i}\,|\,i\in I)]$ of the ultraproduct such that
${\mathcal{A}}_{i}\models\Phi_{i}[a_{i}]$. Clause (b) then shows that
$[(a_{i}\,|\,i\in I)]$ satisfies every formula in $\Sigma$. As linguistic
aspects of $\Sigma$ are untouched here, we might as well ask for criteria
guaranteeing that every possibility function on any set $X$, $|X|<\kappa$, has
an actualization.

Now, by basic properties of ultrafilters, clause (b) in the definition implies
that $\\{i\in I\,|\,\Theta\subseteq\Phi_{i}\\}\in{\mathcal{U}}$ for every
$\Theta\in{\mathcal{P}_{\omega}}(X)$. Thus, defining $p_{\Phi}$ by
$i\,p_{\Phi}\,\Theta$ iff
$\Theta\subseteq\Phi_{i}\in{\mathcal{P}_{\omega}}(X)$, $p_{\Phi}$ is a
possibility relation in its own right. It satisfies the possibility condition
(Psb), and the strenghtened form of clause (b) shows that
$p_{\Phi}:{\mathcal{P}_{\omega}}(X)\rightarrow{\mathcal{U}}$. Such a
possibility relation $q=p_{\Phi}$ has some special properties:

$q\text{ consistent: }\quad i\,q\,(\Theta\cup\Theta^{\prime})\Leftarrow
i\,q\,\Theta\text{ \& }i\,q\,\Theta^{\prime},$ (Con)

which is inverse to the implication in (Psb), and

$q\text{ locally finite: }\quad\text{ for all }i\in
I,\;\sup\\{|\Theta|\,|\,i\,q\,\Theta\\}<\infty.$ (Lfn)

(Con) is equivalent to the statement that
$q^{-1}i=\\{\Theta\in{\mathcal{P}_{\omega}}(X)\,|\,i\,q\,\Theta\\}$ is closed
under finite union. Thus, if $q$ satisfies (Psb,Con,Lfn), then $\bigcup
q^{-1}i$ is finite, hence itself a member of $q^{-1}i$, for all $i\in I$. And,
in that case $\bigcup q^{-1}i$ is an actualization of $q$. So, a locally
finite consistent possibility relation has an actualization.

Finally, suppose that $p^{\prime}\leq p$ [meaning $p^{\prime}(\Theta)\subseteq
p(\Theta)$ for $\Theta\in{\mathcal{P}_{\omega}}(X)$]. Then, an actualization
of $p^{\prime}$ is also an actualization of $p$ [only clause (a) sees $p$],
and $p^{\prime}$ is locally finite if $p$ is. Thus, if for every possibility
relation $p$, there were two others, $Tp\leq p$ locally finite, and $Mp\leq p$
consistent, then $MTp$ satisfies (Psb,Con,Lfn), hence has an actualization
which is also an actualization of $p$. Summing up, ${\mathcal{U}}$ guarantees
saturation if the operators $M$ and $T$ exist.

$T$, at least, is quickly dispatched.

######  Lemma 2.1.

If the ultrafilter ${\mathcal{U}}$ on $I$ is countably incomplete, then for
every possibility relation $p$, there is a locally finite possibility relation
$q\leq p$.

###### Proof.

That ${\mathcal{U}}$ is countably incomplete means that there exists
$\\{K_{m}\\}_{m\in{\mathbb{N}}}\subseteq{\mathcal{U}}$ such that
$I_{n}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\cap_{m\leq
n}K_{m}\downarrow\emptyset$. Defining
$N(i)=\min\\{n\in{\mathbb{N}}\,|\,i\notin I_{n}\\}$ for $i\in I$, note that

$\\{i\in I\,|\,n\leq N(i)\\}\in{\mathcal{U}}\text{ for all }n\in{\mathbb{N}}.$
(2.2)

Now, for $p:{\mathcal{P}_{\omega}}(X)\rightarrow{\mathcal{U}}$ a possibility
function, define $Tp$ by

$i\,(Tp)\,\Theta\text{ iff }i\,p\,\Theta\text{ \& }|\Theta|\leq N(i).$

(2.2) shows that $Tp$ is a possibility relation, and it is manifestly locally
finite. ∎

###  2.4. Goodness

If $X$ is an infinite set, then a map ${\mathcal{P}_{\omega}}(X)\rightarrow Y$
can equally well be viewed as a map
$\overline{{\mathcal{P}_{\omega}}}(X)\rightarrow Y$, simply by precomposing
with complementation. The correspondingly rephrased condition for an
$M$-operator for ${\mathcal{U}}$ is as follows. Given
$f:\overline{{\mathcal{P}_{\omega}}}(X)\rightarrow{\mathcal{U}}$ satisfying
$x\subseteq y\Rightarrow f(x)\subseteq f(y)$, there is
$(Mf:\overline{{\mathcal{P}_{\omega}}}(X)\rightarrow{\mathcal{U}})\leq f$
satisfying $Mf(x\cap y)=Mf(x)\cap Mf(y)$. Definition 2.1 below captures the
lattice-theoretic essence of this.

######  Notation 2.2.

$\mathsf{PoSet}$ denotes the category of posets with monotone maps, and
$\wedge\mathsf{SemiLatt}$, the subcategory of meet-semilattices with meet-
preserving (or “multiplicative”) maps. [A meet-semilattice is a poset with a
binary operation $\wedge$ such that $a\leq x$ & $a\leq y$ iff $a\leq x\wedge
y$.] “$f:Y\rightarrow Z\;\text{ in }{\mathsf{C}}$” indicates that $f$ is in
the set $\mathsf{C}(Y,Z)$ of $\mathsf{C}$ morphisms. A subset of
$\mathcal{P}(X)$ is a poset with $\subseteq$ in the role of $\leq$, and if
closed under intersection, is also a meet-semilattice with $\cap$ in the role
of $\wedge$.

######  Definition 2.1 (good).

Let $\mathcal{Y}$ and $\mathcal{X}$ be meet-semilattices. If, for
$f:\mathcal{X}\rightarrow\mathcal{Y}$ in $\mathsf{PoSet}$, there is
$g:\mathcal{X}\rightarrow\mathcal{Y}\text{ in }\wedge\mathsf{SemiLatt}$ with
$g\leq f$, then $\mathcal{Y}$ is $f$-good (or “good for $f$”). If
$\mathcal{Y}$ is good for every $f$ in
$\mathsf{PoSet}(\mathcal{X},\mathcal{Y})$, then $\mathcal{Y}$ is
$\mathcal{X}$-good. Finally, for $\kappa$ an infinite cardinal, $\mathcal{Y}$
is $\kappa$-good if it is $\overline{{\mathcal{P}_{\omega}}}(\beta)$-good for
all $\beta<\kappa$.

######  Lemma 2.2.

Suppose $\mathcal{Y}$ is $\mathcal{X}$-good and
${\mathcal{W}}\stackrel{{\scriptstyle
s}}{{\rightarrow}}\mathcal{X}\stackrel{{\scriptstyle
r}}{{\rightarrow}}{\mathcal{W}}$ in $\wedge\mathsf{SemiLatt}$, with $r\circ
s=id_{{\mathcal{W}}}$. Then, $\mathcal{Y}$ is ${\mathcal{W}}$-good.

###### Proof.

Given $f:{\mathcal{W}}\rightarrow\mathcal{Y}$ in $\mathsf{PoSet}$,
$\mathcal{X}$-goodness implies existence of
$g:\mathcal{X}\rightarrow\mathcal{Y}$ in $\wedge\mathsf{SemiLatt}$ with $g\leq
f\circ r$. Then, $g\circ s\leq f\circ r\circ s=f$ meets the requirement. ∎

######  Theorem 2.3.

If ${\mathcal{U}}$ is a a $\overline{{\mathcal{P}_{\omega}}}(\kappa)$-good
ultrafilter, then any mod-${\mathcal{U}}$ ultraproduct for a language of
cardinality less than $\kappa^{+}$ is $\kappa^{+}$-saturated.

###### Proof.

Combine the preceding with the discussion in §2.3. Lemma 2.2 is not really
needed, but is applicable with
${\mathcal{W}}=\overline{{\mathcal{P}_{\omega}}}(\beta)$,
$\mathcal{X}=\overline{{\mathcal{P}_{\omega}}}(\kappa)$,
$s(x)=x\cup(\kappa\setminus\beta)$ and $r(y)=y\cap\beta$. ∎

Before taking up the main agenda, we pick off and enjoy some low-hanging
fruit.

######  Theorem 2.4.

Any countably incomplete ultrafilter $\mathcal{U}$ is $\omega^{+}$-good.

###### Proof.

For
$f\in\mathsf{PoSet}(\overline{{\mathcal{P}_{\omega}}}(\omega),{\mathcal{U}})$,
$f{\mkern-6.0mu}\upharpoonright{\mkern-6.0mu}\mathcal{X}$ is multiplicative if
$\mathcal{X}\subseteq\overline{{\mathcal{P}_{\omega}}}(\omega)$ is totally
ordered, since for $\Theta,\Theta^{\prime}\in\mathcal{X}$,
$f(\min(\Theta,\Theta^{\prime}))=f(\Theta\cap\Theta^{\prime})\subseteq
f(\Theta)\cap f(\Theta^{\prime})$. Thus, if
$M^{*}\in\wedge\mathsf{SemiLatt}(\overline{{\mathcal{P}_{\omega}}}(\omega),\mathcal{X})$,
then $Mf\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=f\circ
M^{*}\in\wedge\mathsf{SemiLatt}(\overline{{\mathcal{P}_{\omega}}}(\omega),{\mathcal{U}})$.
Further, if $M^{*}\leq id$ ($M^{*}\Theta\subseteq\Theta$), then $Mf\leq f$.
These meet the requirements:

${\mathcal{X}}=\\{X_{n}\\}_{n\prec\omega}\text{ where }X_{n}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{m\prec\omega\,|\,n\preceq
m\\},\text{ and }{M^{*}}\Theta\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\bigcup\\{x\in\mathcal{X}\,|\,x\subseteq\Theta\\}.$

∎

##  3\. how to make a $\kappa^{+}$-good ultrafilter

######  Theorem 3.1.

If $\mathcal{X}$ is a meet-semilattice with $|\mathcal{X}|\leq\kappa$, then
there is an $\mathcal{X}$-good ultrafilter on $\kappa$.

§3.1 describes a transfinite recursion to construct the required ultrafilter.
Lemmata 3.4 and 3.5 show how to carry out successor steps with the aid of a
supply $\Pi$ of partitions of $\kappa$ so as to preserve usability of these
auxiliary resources. The proof of Thm. 3.1 is finished at the end of this
Section, but it depends on the existence of a suitable $\Pi$, the construction
of which is given §4.

###  3.1. A transfinite recursion

If $\mathcal{X}$ is a meet-semilattice with $|\mathcal{X}|=\kappa$, then
$|\mathsf{PoSet}(\mathcal{X},\mathcal{P}(\kappa))|\leq(2^{\kappa})^{\kappa}=2^{\kappa\cdot\kappa}=2^{\kappa}$.
So, fix length-$2^{\kappa}$ enumerations

$\mathcal{P}(\kappa)=\\{J_{\gamma}\\}_{\gamma\prec
2^{\kappa}},\quad\mathsf{PoSet}(\mathcal{X},\mathcal{P}(\kappa))=\\{f_{\delta}\\}_{\delta\prec
2^{\kappa}},$

and, starting from a countably-incomplete filter ${\mathcal{F}}_{0}$, carry
out a transfinite recursion of length $2^{\kappa}$ with the following steps.

  1. sucσ:

At a successor stage $\sigma=\gamma+1$, construct filter
${\mathcal{F}}_{\gamma+1}$ satisfying

     * •

${\mathcal{F}}_{\gamma+1}\supseteq{\mathcal{F}}_{\gamma}$,

     * •

${\mathcal{F}}_{\gamma+1}$ decides $J_{\gamma+1}$.

     * •

${\mathcal{F}}_{\gamma+1}$ is $f_{\delta}$-good, where $\delta$ is
$\prec$-least in
$\\{\delta\prec
2^{\kappa}\,|\,\mathop{\mathrm{ran}}f_{\delta}\subseteq{\mathcal{F}}_{\gamma}\text{
but }{\mathcal{F}}_{\gamma}\text{ not }f_{\delta}\text{-good}\\}$ (skip, if
that set is empty).

  2. limλ:

At a limit stage $\lambda$, take
${\mathcal{F}}_{\lambda}=\bigcup_{\gamma\prec\lambda}{\mathcal{F}}_{\gamma}$.

If step sucγ+1 is possible for every $\gamma\prec 2^{\kappa}$, then
${\mathcal{F}}^{*}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\cup\\{{\mathcal{F}}_{\gamma}\,|\,\gamma\prec
2^{\kappa}\\}$ is countably incomplete [it contains ${\mathcal{F}}_{0}$], and
is an ultrafilter [it decides every $J$ in $\mathcal{P}(\kappa)$].
$\kappa^{+}$-goodness is trickier, and involves the concept of cofinality.
[For $\mathcal{Y}$ a poset, $X\subseteq\mathcal{Y}$ is cofinal in
$\mathcal{Y}$ if, for all $y\in\mathcal{Y}$, there exists $x\in X$, $y\preceq
x$. The cofinality of $\mathcal{Y}$, denoted $\mathrm{cf}(\mathcal{Y})$, is
the least cardinal of sets cofinal in $\mathcal{Y}$.] Suppose
$f_{\delta}\in\mathsf{PoSet}(\mathcal{X},\mathcal{P}(\kappa))$ has range in
${\mathcal{F}}^{*}$. Since
$|\mathop{\mathrm{ran}}{f_{\delta}}|\leq\kappa<\mathrm{cf}(2^{\kappa})$ [the
second inequality by Prop. 3.2 below],
$\mathop{\mathrm{ran}}f_{\delta}\subset{\mathcal{F}}_{\gamma}$ for some
$\gamma<2^{\kappa}$. The growing filter is made $f_{\delta}$-good within
another $\delta$ steps of the recursion, which point is certainly reached
because $2^{\kappa}$ is a cardinal, so that $\gamma+\delta\prec 2^{\kappa}$.

######  Proposition 3.2.

If $\alpha$ is an infinite cardinal and $2\leq\lambda$, then
$\alpha<\mathrm{cf}(\lambda^{\alpha})$.

###### Proof.

We prove this using the following
Claim (König’s theorem): if $\mu$ is an infinite cardinal, then
$\mu<\mu^{\,\mathrm{cf}\,\mu}$.
Suppose the proposition is false, so
$\alpha\geq\mathrm{cf}\,\lambda^{\alpha}=\mathrm{cf}\,\mu$, with abbreviation
$\mu=\lambda^{\alpha}$. Then, using the Claim in the first inequality that
follows,

$\mu<\mu^{\mathrm{cf}\,\mu}\leq\mu^{\alpha}=\lambda^{\alpha\cdot\alpha}=\lambda^{\alpha}=\mu.$

As this is a blatant contradiction, the Proposition is proven, once the Claim
is secured. Let $Y$ be an unbounded subset of $\mu$, and suppose that an
enumeration $\\{g_{\gamma}\\}_{\gamma<\mu}$ of all functions $Y\rightarrow\mu$
exists. Diagonalize out of the enumeration as follows. Define
$A_{\delta}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{g_{\gamma}(\delta)\,|\,\gamma<\mu\\}$
for $\delta\in Y$. Since $|A_{\delta}|=\delta<\mu$, we can choose $f(\delta)$
from $\mu\setminus A_{\delta}\neq\emptyset$. Then, $f\neq g_{\gamma}$ for
every $\gamma$. For, by unboundedness of $Y$, $\gamma<\delta\in Y$ for some
$\delta$, implying that $f(\delta)\neq g_{\gamma}(\delta)$. ∎

###  3.2. Partitions of $\kappa$ as a resource

We begin with a simple order-theoretic observation.

######  Lemma 3.3.

Suppose $\mathcal{X}$ is a meet-semilattice and
$h:\mathcal{X}{\rightarrow}{\mathcal{Y}}$, where
${\mathcal{Y}}\subseteq\mathcal{P}(\kappa)$ is $\cup$-complete. Then, the
least $\mathsf{PoSet}$ morphism $\hat{h}$ satisfying $h\leq\hat{h}$ is

$\hat{h}:\mathcal{X}{\rightarrow}{\mathcal{Y}}\,::\,x\mapsto\bigcup\\{h(y)\,|\,y\leq
x\\}.$ (3.1)

If $h$ is disjoint, then $\hat{h}$ is also multiplicative.

###### Proof.

$\hat{h}$ is monotone, and clearly a monotone function as large as $h$ is as
large as $\hat{h}$, so the first assertion is immediate. If $h$ is disjoint,
given $\gamma\in\kappa$, there is at most one $w\in\mathcal{X}$ such that
$\gamma\in h(w)$. So, $\gamma\in\hat{h}(x\wedge y)$ iff (such $w$ exists and)
$w\leq x\wedge y$, iff $w\leq x$ and $w\leq y$, iff $\gamma\in\hat{h}(x)$ and
$\gamma\in\hat{h}(y)$. Thus $\hat{h}$ is multiplicative. ∎

This result is immediately suggestive. Given
$f:\mathcal{X}\rightarrow{{\mathcal{F}}}$ in $\mathsf{PoSet}$, we attempt to
get a multiplicative $g\leq f$ by cutting $f$ back to a disjoint map $h\leq f$
and then using the “hat map”(3.1). Chopping up the image of $f$ with a
partition is an obvious way of getting the disjoint $h$. That motivates the
next couple of definitions.

######  Definition 3.1 (partition, large, polycell, independent).

A partition $P$ is a set of disjoint subsets of $X$ (cells of $P$), which
cover $X$. $P$ is large if $|P|=|X|$. If $\Pi$ is a collection of partitions,
a polycell is the intersection $C_{1}\cap\cdots\cap C_{n}$ of a finite number
of cells from distinct partitions $P_{1},\ldots,P_{n}\in\Pi$. The set of
polycells of $\Pi$ is denoted $\mathrm{cell}^{*}(\Pi)$. $\Pi$ is independent
(or, “a set of independent partitions”) if
$\emptyset\not\in\mathrm{cell}^{*}(\Pi)$.

######  Definition 3.2 (consistent, polyconsistent).

If ${\mathcal{F}}$ is a filter on $Y$, then

$\mathrm{con}\,{\mathcal{F}}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{y\in
Y\,|\,x\cap y\neq\emptyset,\forall x\in{\mathcal{F}}\\}$ (3.2)

is the set of subsets of $Y$ consistent with ${\mathcal{F}}$. A subset of
(function into) $\mathcal{P}(Y)$ is called consistent with ${\mathcal{F}}$ if
it (its range) is a subset of $\mathrm{con}\,{\mathcal{F}}$. A collection
$\Pi$ of partitions is polyconsistent with ${\mathcal{F}}$ if
$\mathrm{cell}^{*}(\Pi)\subseteq\mathrm{con}\,{\mathcal{F}}$.

######  Remark 3.1.

The notion of consistency is central, as Lemmata 3.4, 3.5 will show. A few
points to note: $\mathrm{con}\,{\mathcal{F}}$ is closed under taking
supersets. ${\mathcal{F}}\cup A$ generates a filter iff the $\cap$-semilattice
generated by $A$ (finite intersections) is in $\mathrm{con}\,{\mathcal{F}}$.
Finally, $Y\setminus(\mathrm{con}\,{\mathcal{F}})$ is closed under union. For,
if $a\cap x=b\cap y=\emptyset$ for $x,y\in{\mathcal{F}}$, then $(a\cup
b)\cap(x\cap y)=(a\cap x\cap y)\cup(b\cap x\cap y)=\emptyset$.

######  Lemma 3.4.

Let $\Pi$ be a collection of large partitions of $\kappa$ polyconsistent with
the filter ${\mathcal{F}}\subset\mathcal{P}(\kappa)$,

$f:\mathcal{X}\rightarrow{\mathcal{F}}\,\,{\text{i}n}\,\,\mathsf{PoSet},$

and $P\in\Pi$. Then there exists a filter
${\mathcal{F}}^{\prime}=\mathrm{Flt}({\mathcal{F}}\cup\mathop{\mathrm{ran}}g)\supseteq{\mathcal{F}}$
and

$g:\mathcal{X}\rightarrow{\mathcal{F}}^{\prime}\,\,{\text{i}n}\,\wedge\mathsf{SemiLatt},\quad
g\leq f$

such that $\Pi^{\prime}=\Pi\setminus P$ is polyconsistent with
${\mathcal{F}}^{\prime}$.

###### Proof.

Since $|\mathcal{X}|\leq|P|=\kappa$, there is an injective map
$D:\mathcal{X}\rightarrow P$. Since
$\mathop{\mathrm{ran}}f\subseteq{\mathcal{F}}$ and
$P\subseteq\mathrm{con}\,{\mathcal{F}}$, the map

$h:\mathcal{X}\rightarrow\mathrm{con}\,{\mathcal{F}}\,::\,s\mapsto f(s)\cap
D(s)$

is disjoint. Therefore, the range of $g\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\hat{h}$
is an $\cap$-semilattice in $\mathrm{con}\,{\mathcal{F}}$, and
${\mathcal{F}}^{\prime}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\mathrm{Flt}({\mathcal{F}}\cup\mathop{\mathrm{ran}}g)=\\{g(s)\cap
A\,|\,s\in\mathcal{X},A\in{\mathcal{F}}\\}$. For
$C\in\mathrm{cell}^{*}(\Pi\setminus P)$ and $g(s)\cap
A\in{\mathcal{F}}^{\prime}$, $C\cap(g(s)\cap A)\supseteq C\cap h(s)\cap
A=[C\cap D(s)]\cap[f(s)\cap A]$. This is nonempty because $C\cap
D(s)\in\mathrm{cell}^{*}(\Pi)$, $f(s)\cap A\in{\mathcal{F}}$, and $\Pi$ is
polyconsistent with ${\mathcal{F}}$. ∎

######  Lemma 3.5.

Let $\Pi$ be a collection of large partitions of $\kappa$ polyconsistent with
the filter ${\mathcal{F}}\subset\mathcal{P}(\kappa)$, and $J\subseteq\kappa$.
Then, either

  1. (a)

$\Pi^{\prime}=\Pi$ is polyconsistent with
${\mathcal{F}}^{\prime}=\mathrm{Flt}({\mathcal{F}}\cup\\{J\\})$, or

  2. (b)

$\Pi^{\prime}\subseteq\Pi$ cofinite, is polyconsistent with
${\mathcal{F}}^{\prime}=\mathrm{Flt}({\mathcal{F}}\cup\\{\kappa\setminus
J\\})$.

###### Proof.

Assume (a) fails. Then, for a polycell $C$ of some finite
$\\{P_{1},\ldots,P_{n}\\}\subseteq\Pi$, $C\cap
J\not\in\mathrm{con}\,{\mathcal{F}}$. If (b) also fails with
$\Pi^{\prime}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\Pi\setminus\\{P_{1},\ldots,P_{n}\\}$,
there is similarly $C^{\prime}\in\mathrm{cell}^{*}(\Pi^{\prime})$ such that
$C^{\prime}\cap(\kappa\setminus J)\not\in\mathrm{con}\,{\mathcal{F}}$. But
then $C\cap C^{\prime}\subseteq(C\cap J)\cup(C^{\prime}\cap(\kappa\setminus
J))$ is not in $\mathrm{con}\,{\mathcal{F}}$ [see Rem. 3.1], contradicting
$\mathrm{cell}^{*}(\Pi)\subseteq\mathrm{con}\,{\mathcal{F}}$. ∎

###### Proof of Thm. 3.1.

Lemmata 3.4 and 3.5 show how the successor steps of the recursion described in
§3.1 are to be carried out with the aid of some partitions of $\kappa$. Given
$\Pi_{\gamma}$ satisfying usableγ: $|\Pi|=2^{\kappa}$ and
$\mathrm{cell}^{*}(\Pi_{\gamma})\subseteq\mathrm{con}\,{\mathcal{F}}_{\gamma}$,
as well as $f:\mathcal{X}\rightarrow{\mathcal{F}}_{\gamma}$ and
$J\in\mathcal{P}(\kappa)$, the transformations
$({\mathcal{F}},\Pi)\mapsto({\mathcal{F}}^{\prime},\Pi^{\prime})$ in the
Lemmata applied in sequence yield $\Pi_{\gamma+1}$ which is usableγ+1,
$f$-good, and decides $J$.

For limit stage limλ, $\lambda\prec 2^{\kappa}$,
${\mathcal{F}}_{\lambda}=\cup_{\gamma\prec\lambda}{\mathcal{F}}_{\gamma}$. Add
the rule $\Pi_{\lambda}=\cap_{\gamma\prec\lambda}\Pi_{\gamma}$, and assume
that ${\Pi_{\gamma}}$ is usableγ for all $\gamma\prec\lambda$. Since
$2^{\kappa}$ is a cardinal, $|\Pi_{\lambda}|=2^{\kappa}$. If
$A\in{\mathcal{F}}_{\lambda}$ and $C\in\mathrm{cell}^{*}(\Pi_{\lambda})$, then
$A\in{\mathcal{F}}_{\beta}$ for some $\beta\prec\lambda$ and
$C\in\mathrm{cell}^{*}(\Pi_{\beta})$, so $C\cap A\neq\emptyset$ by the
inductive hypothesis. So, $\Pi_{\lambda}$ is polyconsistent with
${\mathcal{F}}_{\lambda}$ and thus usableλ.

Finally, we need a countably incomplete filter ${\mathcal{F}}_{0}$ and a
usable0 $\Pi_{0}$ to start the recursion. For $n\prec\omega$, take
${K}_{n}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{\alpha\prec\kappa\,|\,\alpha=\lambda+m\text{
for a limit ordinal }\lambda,\text{ and }0\leq m\leq n\\}$ ($0$ is a limit
ordinal). Then, $K_{n}\downarrow\emptyset$, and with $\mu$ the common
cardinality of the $K_{n}$’s, $\mu\times\omega=\kappa$, so that $\mu=\kappa$.
Thus, $E=\\{K_{n}\\}_{n\prec\omega}$ satisfies the hypotheses of Prop. 4.3,
which delivers countably incomplete ${\mathcal{F}}_{0}=\mathrm{Flt}(E)$, as
well as $\Pi_{0}$. ∎

##  4\. building a stock of large independent partitions of $\kappa$

The goal of this section is Prop. 4.3, which was used in the proof of the main
theorem 3.1. A pair of clever lemmata are required.

######  Lemma 4.1.

There is a collection $\Pi^{\prime}$ of independent large partitions of
$\kappa$ with $|\Pi^{\prime}|=2^{\kappa}$.

###### Proof.

Define

$\Gamma=\\{(s,r)\,|\,s\in{\mathcal{P}_{\omega}}(\kappa),\,\,r:\,{s}\rightarrow\kappa\\}.$

Also, for each $J\subseteq\kappa$, the function

$f_{J}:\Gamma\rightarrow\kappa\,::\,(s,r)\mapsto r(s\cap J),$

and corresponding partition of $\Gamma$

${P}_{J}^{\Gamma}=\\{f_{J}^{-1}(\gamma)\,|\,\gamma\in\mathop{\mathrm{ran}}f_{J}\\}.$

We show that for distinct $J_{1},\ldots,J_{n}\in\mathcal{P}(\kappa)$, and
arbitrary $\gamma_{1},\ldots,\gamma_{n}\in\kappa$, there is a solution $\xi$
of the system

$f_{J_{i}}(\xi)=\gamma_{i},\quad 1\leq i\leq n.$ (4.1)

This immediately implies that
$\\{P_{J}^{\Gamma}\,|\,J\in\mathcal{P}(\kappa)\\}$ comprises $2^{\kappa}$ [by
(4.1 with $n=2$], independent [general $n$], large [$n=1$] partitions of
$\Gamma$.

To solve (4.1), note that for each pair $1\leq i<j\leq n$, there is $x_{ij}\in
J_{i}\Delta J_{j}$, so, with $t\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{x_{ij}\,|\,1\leq
i<j\leq n\\}$, the subsets $K_{i}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=t\cap
J_{i}$ are all distinct, for $1\leq i\leq n$. Then, $\xi=(t,r)$ does the trick
if $r(K_{i})=\gamma_{i}$.

Since $|\Gamma|={\kappa}$, there is a bijection
$\sigma:\kappa\rightarrow\Gamma$. Use it to pull the $P_{J}^{\Gamma}$’s back
to $\kappa$, obtaining partitions $P_{J}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\sigma^{-1}P_{J}^{\Gamma}$.

$\Pi^{\prime}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{P_{J}\,|\,J\in\mathcal{P}(\kappa)\\}$
(4.2)

is the promised collection. ∎

######  Lemma 4.2.

If $\beta\leq\kappa$ and $f:\beta\rightarrow{\mathcal{P}}_{*}(\kappa)$, then
there is a disjoint $h\leq f$.

###### Proof.

By the axiom of Choice, there is a bijection between $\kappa$ and
$\kappa\times\kappa$, inducing a (henceforth the) well-order on
$\kappa\times\kappa$. Let $I$ be the set of all injective functions from
initial segments of $\kappa\times\kappa$ to $\kappa$ that map $x\times\kappa$
into $f(x)$, ordered by extension ($g\leq g^{\prime}$ iff $g^{\prime}$ agrees
with $g$ on $\mathrm{dom}\,g$). We show that some $g^{*}\in I$ has
$\mathrm{dom}\,g^{*}=\kappa\times\kappa$. For if not, there is a least element
$(x,\xi)$ not in the domain of any function in $I$, and a $g$ defined on
everything preceding $(x,\xi)$. But then $g(x\times\kappa)\subseteq f(x)$ has
cardinality less than $\kappa$, so an extension of $g$ can be defined at
$(x,\xi)$. Contradiction. The sets $h(x)\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=g(x\times\kappa)\subseteq
f(x)$ have cardinality $\kappa$ and are disjoint, as required. ∎

######  Proposition 4.3.

Let $E\subseteq{\mathcal{P}}_{*}(\kappa)$ with $|E|\leq\kappa$ have the finite
intersection property. Then, there is a set $\Pi$ of partitions of $\kappa$
with $|\Pi|=2^{\kappa}$ and
$\mathrm{cell}^{*}(\Pi)\subseteq\mathrm{con}\,\mathrm{Flt}(E)$.

###### Proof.

$\hat{E}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\\{\cap
I\,|\,I\in{\mathcal{P}_{\omega}}(E)\\}\subseteq{\mathcal{P}}_{*}(\kappa)$ is a
filter base for ${\mathcal{F}}=\mathrm{Flt}(E)$. Since $|\hat{E}|\leq\kappa$,
Lemma 4.2 guarantees subsets $I_{e}\subseteq e\in\hat{E}$ such that
$\\{I_{e}\\}_{e\in\hat{E}}$ is disjoint, and $|I_{e}|=\kappa$ so that there
are bijections $\phi_{e}:I_{e}\rightarrow\kappa$. Using them, define a
surjection

$\phi:\kappa\rightarrow\kappa::\,x\mapsto\begin{cases}\phi_{e}(x),\quad\text{
if }x\in I_{e}\text{ for some }e\\\ 0,\quad\text{otherwise},\end{cases}$

bijective on each $I_{e}$. Now, pull back $\Pi^{\prime}$ from (4.2) via $\phi$
to obtain

${\Pi}=\\{\hat{P}_{J}\,|\,J\in\mathcal{P}(\kappa)\\},\quad\hat{P}_{J}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\phi^{-1}P_{J},$

with $|{\Pi}|=|\Pi^{\prime}|=2^{\kappa}$. Since $\Pi^{\prime}$ is independent,
$\phi\\!\upharpoonright\\!I_{e}$ is bijective, and pullback by $\phi$ commutes
with intersection, ${\Pi}\\!\upharpoonright\\!I_{e}$ is independent for each
$e$. Thus, since every member of ${\mathcal{F}}$ is a superset of some
$I_{e}$, $\mathrm{cell}^{*}(\Pi)\subseteq\mathrm{con}\,{\mathcal{F}}$. ∎

## References

  * [1] C. C. Chang and H. J. Keisler.  Model theory.  North-Holland Publishing Co., Amsterdam-New York-Oxford, second edition, 1977.  Studies in Logic and the Foundations of Mathematics, 73.
  * [2] Kenneth Kunen.  Ultrafilters and independent sets.  Trans. Amer. Math. Soc., 172:299–306, 1972.
  * [3] T. Lindstrøm.  In N. Cutland, editor, Nonstandard Analysis, pages 1–105. Cambridge University Press, Cambridge, New York, 1988.
  * [4] P. A. Loeb and M. P. A. Wolff, editors.  Kluwer Academic Publishers, Dordrecht, Boston, 2000.
  * [5] K. D. Stroyan and W. A. J. Luxemburg.  Introduction to the Theory of Infinitesimals.  Academic Press, New York, 1976.