# Ultrafilter extensions of bounded graphs are elementary

Zalán Molnár  Eötvös Loránd University, Department of Logic, Budapest, Hungary
<EMAIL_ADDRESS>
Abstract. The main motivation of this paper is the study of first-order model
theoretic properties of structures having their roots in modal logic. We will
focus on the connections between ultrafilter extensions and ultrapowers. We
show that certain structures (called bounded graphs) are elementary
substructures of their ultrafilter extensions, moreover their modal logics
coincide.

keywords: ultrafilter extension, elementary substructures, bounded graphs.

##  1\. Overview

There are two different approaches that are called ultrafilter extensions of
structures (graphs) equipped with a single binary relation. The recently
introduced one has its origins in model theory [26] and was further
investigated in [27, 28, 22], while the other emerged from modal logics and
universal algebra and was first introduced in [9]. The connections between the
extensions were initially investigated in [29]. In this paper, we will focus
on the second type of extension that has become a fundamental construction for
understanding modal logics and their algebraic counterpart. Our motivation
stems from one of the central areas in model theory of modal logics – namely
its interconnection with first-order logic. This topic has been tackled from
various sides. Example of this include: correspondence theory, [6, 24],
definability [18, 15], bounded fragments of first-order logic [1], canonicity
[5, 19, 20, 14]. Some of these connections are guided by the “proportion”:

$\displaystyle\frac{\text{Modal
logic}}{\text{Bisimulation}}\approx\frac{\text{First-order logic
}}{\text{Partial isomorphism }}$

That is “bisimulations are to modal logic, what partial isomorphism is for
first-order logic”. This was put forward by de Rijke in [23] and was further
explicated through the investigation of bounded fragments. Later, in [30]
Venema improved de Rijke’s results by invoking the “proportion”:

$\displaystyle\frac{\text{Modal logic}}{\text{Ultrafilter
extension}}\approx\frac{\text{First-order logic }}{\text{Ultrapowers}}$

By introducing the construction called ultrafilter union, Venema justified the
phrase “taking an ultrafilter union of a set of models is the modal analogue
of taking ultraproducts in the model theory of first-order logic”.111We should
mention that all of the upcoming studies can be adapted to ultrafilter unions
and ultraproducts. From these constructions one easily obtains the modal
counterpart of the well-known Keisler-Shelah Theorem: Two (pointed) models are
modally equivalent if and only if they have bisimilar ultrafilter extensions
(cf. [2] Theorem 2.62).

Our primary focus will be on the second “proportion” by studying the two
constructions, and investigating how the resulted new structures can be
related to each other. From this approach, the following questions mainly
issued by [14, 7, 5, 8] are very natural:

  1. •

What can be said about the modal theory of the ultrapowers?

  2. •

What can we say about the first-order theory of the ultrafilter extensions?

  3. •

What kind of modal formulas are preserved under taking ultraflter extension?

  4. •

What kind of connections can we have between the ultrafilter extensions and
ultrapowers?

In general, it is not surprising that the ultrafilter extension, as opposed to
ultrapowers, may fail to preserve first-order formulas. As a result, the
literature mostly posed and partially answered the question; “What type of
first-order formulas are preserved under taking ultrafilter extensions?” [6,
8, 5, 18]. This turned out to be $\Pi_{1}^{1}$-hard, hence no such
characterization can exist [10]. Also, similar questions concerning the first
type of ultrafilter extension were addressed in [27] (cf. Problem 5.2, and
Theorem 5.3). Here we take the reverse approach, surprisingly untouched by the
literature and ask; “What type of structures are elementary equivalent to
their ultrafilter extension?”. Hence, instead of formulas, we concentrate on
structures, attempting to isolate classes for which ultrafilter extensions and
ultrapowers share structural features. Our main results are proved in Section
4. We show that for certain structures (called bounded graphs) their
ultrafilter extension has a characteristic similar to Łoś’s Lemma. As a result
of this, they are found to be elementary substructures to their ultrafilter
extension. Additionally, their modal logics coincide.

##  2\. Preliminary notions, background

#### Semantics

Here we recall all the necessary notions from the semantics of modal logics
and fix the notation. The reader who is more interested in this area is
referred to [12, 2, 3] and [11]. Throughout the paper we consider structures
$\mathfrak{F}=\langle W,R\rangle$ to be directed graphs for the first-order
language $\mathcal{L}_{R}$ with equality, containing a single binary relation
symbol $R$.

As opposed to the first-order relational language $\mathcal{L}_{R}$, the
standard propositional modal language $\mathcal{L}_{\diamondsuit}$ is the
extension of the propositional language by a single unary connective
$\diamondsuit$. A model for $\mathcal{L}_{\diamondsuit}$ is a pair
$\mathfrak{M}=\langle\mathfrak{F},V\rangle$, where $\mathfrak{F}$ is the
underlying structure and $V:\Phi\to\mathcal{P}(W)$ is a function, called
valuation. The relation $\mathfrak{M},w\Vdash\varphi$ reads as the truth of
$\varphi\in\mathsf{Form}(\mathcal{L}_{\diamondsuit})$ in the model
$\mathfrak{M}$ at $w\in W$, and is defined in the usual recursive manner. The
only non-obvious case is

  1. •

$\mathfrak{M},w\Vdash\diamondsuit\varphi\Leftrightarrow(\exists v\in W)Rwv$
and $\mathfrak{M},v\Vdash\varphi$.

Moreover, $\mathfrak{M}\Vdash\varphi$ denotes the fact that for all $w\in W$
we have $\mathfrak{M},w\Vdash\varphi$, and $\mathfrak{F}\Vdash\varphi$
abbreviates the statement that for all valuation $V$, the relation
$\mathfrak{M}\Vdash\varphi$ holds. Finally, the modal theory (or logic) of
$\mathfrak{F}$ is denoted by
$\Lambda(\mathfrak{F})=\\{\varphi\in\mathsf{Form}(\mathcal{L}_{\diamondsuit}):\mathfrak{F}\Vdash\varphi\\}$.
Since our motivation is to study the first-order structural and modal
properties both appearing at the level of frames, we confine ourselves into
this segment of the semantics.

#### Ultrafilter extension

Let $\mathfrak{F}=\langle W,R\rangle$ be a structure and $X\subseteq W$. We
define the following operations on $\mathcal{P}(W)$:

$\displaystyle R^{+}(X)$ $\displaystyle=\\{s\in W:\exists w(Rws\wedge w\in
X)\\}$ $\displaystyle R^{-}(X)$ $\displaystyle=\\{w\in W:\exists s(Rws\wedge
s\in X)\\}$ $\displaystyle R(X)$ $\displaystyle=R^{-}(X)\cup R^{+}(X)$
$\displaystyle l_{R}(X)$ $\displaystyle=\\{w\in W:\forall v(Rwv\to v\in X)\\}$

If $X=\\{w\\}$, we use the shorthand notation $R(w)$ instead of $R(\\{w\\})$
and similarly for the other operations. The ultrafilter (or canonical)
extension of $\mathfrak{F}$ is the structure
$\mathfrak{F}^{\mathfrak{ue}}=\langle\mathrm{Uf}(W),R^{\mathfrak{ue}}\rangle$,
where $\mathrm{Uf}(W)$ is the set of all ultrafilters over $W$ and the
relation $R^{\mathfrak{ue}}$ is defined as:

$R^{\mathfrak{ue}}uv\Leftrightarrow(\forall X\in v)(R^{-}(X)\in u)$

It is easy to see that the following equivalence holds between the ultrafilter
relation and the operations defined above:

$R^{\mathfrak{ue}}uv\Leftrightarrow\\{Y:l_{R}(Y)\in u\\}\subseteq
v\Leftrightarrow\\{R^{+}(X):X\in u\\}\subseteq v.$

By $\pi_{w}=\\{X\subseteq W:w\in X\\}$ we denote the principal ultrafilter
generated by $w$, and $\mathrm{Uf}^{*}(W)$ denotes the set of non-principal
ultrafilters. The function
$\eta:\mathfrak{F}\hookrightarrow\mathfrak{F}^{\mathfrak{ue}}$, where
$\eta(w)=\pi_{w}$ is an embedding, called the canonical embedding (of
$\mathfrak{F}$ into $\mathfrak{F}^{\mathfrak{ue}}$). For a model
$\mathfrak{M}=\langle\mathfrak{F},V\rangle$, its ultrafilter extension is
given by
$\mathfrak{M}^{\mathfrak{ue}}=\langle\mathfrak{F}^{\mathfrak{ue}},V^{\mathfrak{ue}}\rangle$,
where $V^{\mathfrak{ue}}(p)=\\{u\in\mathrm{Uf}(W):V(p)\in u\\}$. A well-known
fact is the equivalence (cf. Proposition 2.59 from [2]):

$\displaystyle\mathfrak{M}^{\mathfrak{ue}},u\Vdash\varphi\Leftrightarrow
V(\varphi)\in u,$ (1)

for all $u\in\mathrm{Uf}(W)$ and
$\varphi\in\mathsf{Form}(\mathcal{L}_{\diamondsuit})$, from which it follows
that $\Lambda(\mathfrak{F})\subseteq\Lambda(\mathfrak{F}^{\mathfrak{ue}})$.

#### Model theoretic notions

Using standard notation, for $\mathfrak{F}=\langle W,R\rangle$, and
$\mathfrak{F}^{\prime}=\langle W^{\prime},R^{\prime}\rangle$ by
$\mathfrak{F}\leq\mathfrak{F}^{\prime}$, we denote the fact that
$\mathfrak{F}$ is a substructure of $\mathfrak{F}^{\prime}$ and
$\mathfrak{F}\preceq\mathfrak{F}^{\prime}$ means that $\mathfrak{F}$ is an
elementary substructure of $\mathfrak{F}^{\prime}$. Elementary equivalence is
denoted by $\mathfrak{F}\equiv\mathfrak{F}^{\prime}$. We recall that a set
$\Gamma$ of first-order formulas in a language $\mathcal{L}$ with a free
variable $x$ is satisfied in the structure $\mathfrak{F}=\langle W,R\rangle$,
if there is a $w\in W$, such that $\mathfrak{F}\models\varphi(w)$, for each
$\varphi(x)\in\Gamma$. Then $\Gamma$ is finitely satisfiable if each finite
subset of $\Gamma$ is satisfied in $\mathfrak{F}$. For a cardinal $\kappa$,
the structure $\mathfrak{F}$ is $\kappa$-saturated if for each
$A\in[W]^{<\kappa}$ and set of formulas $\Gamma$ in the extended language
$\mathcal{L}\cup\\{c_{a}:a\in A\\}$ containing a free variable $x$, the set
$\Gamma$ is satisfied, whenever $\Gamma$ is finitely satisfied. A well-known
fact on saturation is the following theorem (cf. Theorem 6.1.8 in [11]):

######  Fact 2.1.

For any structure $\mathfrak{F}$ and cardinal $\kappa$ there exists a
$\kappa$-saturated ultrapower of $\mathfrak{F}$.

#### Ultrapower vs. ultrafilter extension

Our primary interest is in the potential connections between an ultraproduct
of $\mathfrak{F}$ and $\mathfrak{F}^{\mathfrak{ue}}$. According to Lemma 3.8
from [5], $\mathfrak{F}^{\mathfrak{ue}}$ is always a $p$-morphic image of a
suitably saturated ultrapower of $\mathfrak{F}$. Also it is proved in [8]
(Theorem 15.11) and later generalized in [17] (Theorem 4.2.5), that a first-
order formula is preserved under $p$-morphisms if and only if it is equivalent
to an essentially positive formula (for the definition: [17], Section 4).
Hence, essentially positive formulas are preserved under taking ultrafilter
extensions. Another important $\mathcal{L}_{R}$-fragment is the class of
$r(u)$-formulas introduced by [8] in Definition 15.17, where $u$ is a fixed
variable. This class enjoys the following “Łoś Lemma-like” characterization:
For any structure $\mathfrak{F}$, $r(u)$-formula
$\varphi(u,x_{0},\dots,x_{n})$ and $w_{0},\dots,w_{n}\in W$,
$v\in\mathrm{Uf}(W)$ we have,

$\displaystyle\mathfrak{F}^{\mathfrak{ue}}\models\varphi(v,\pi_{w_{0}},\dots,\pi_{w_{n}})\text{
iff }\\{s\in W:\mathfrak{F}\models\varphi(s,w_{0},\dots w_{n})\\}\in v.$ (2)

Hence the existential closure of an $r(u)$-formula is preserved by passing
from $\mathfrak{F}$ to $\mathfrak{F}^{\mathfrak{ue}}$.

The exact syntactic nature of formulas that are preserved under taking
ultrafilter extensions is proved to be $\Pi_{1}^{1}$-hard by [10]. As a
result, it is not surprising that elementarily equivalence is by far out of
reach, as the following textbook example shows.

######  Example 2.2.

Let $\mathfrak{N}=\langle\mathbb{N},<\rangle$, its ultrafilter extension can
be illustrated as:

$\mathfrak{N}^{\mathfrak{ue}}$$\pi_{0}$$\pi_{1}$$\pi_{2}$$\dots$cluster of
non-principal ultrafilters

where for any ultrafilter $u\in\mathrm{Uf}(\mathbb{N})$ and
$v\in\mathrm{Uf}^{*}(\mathbb{N})$ we have $u<^{\mathfrak{ue}}v$. Trivially
$\mathfrak{N}\models\forall x(x\not<x)$, but
$\mathfrak{N}^{\mathfrak{ue}}\models\exists x(x<x)$, hence
$\mathfrak{N}\not\equiv\mathfrak{N}^{\mathfrak{ue}}$.

Intuitively, the failure was due to the fact that each $n\in\mathbb{N}$ had
infinitely many $<$-successors. In order to characterize subclasses e.g. whose
elements are elementary equivalent to their ultrafilter extensions, it is
natural to impose conditions on the relation in question.

##  3\. General properties on degree

In what follows we are going to present some basic properties on the branching
of an ultrafilter extension.

######  Definition 3.1.

Let $\mathfrak{F}=\langle W,R\rangle$ be a structure. We introduce the
notation:

  1. •

$\deg^{+}(w)=|R^{+}(w)|$

  2. •

$\deg^{-}(w)=|R^{-}(w)|$

  3. •

$\deg(w)=\deg^{+}(w)+\deg^{-}(w)$

Also, $\mathfrak{F}$ is

  1. •

$\deg^{+}$-finite ($\deg^{-}$-finite, $\deg$-finite), if for all $w\in W$,
$\deg^{+}(w)<\omega$ (resp. $\deg(w),\deg^{-}(w)<\omega$).

  2. •

$\deg^{-}$-bounded ($\deg^{+}$-bounded, $\deg$-bounded), if there is some
$n\in\omega$, such that for all $w\in W$, $\deg^{+}(w)\leq n$ (resp.
$\deg(w),\deg^{-}(w)\leq n$).

Finally, $\mathfrak{F}$ is locally finite if $\mathfrak{F}$ is $\deg$-finite,
moreover $\mathfrak{F}$ is bounded if $\mathfrak{F}$ is $\deg$-bounded.

In basic modal logic, the term image finite is used for $\deg^{+}$-finite
structures that are of special importance, as they have the Hennessy-Milner
property. That is given image finite models $\mathfrak{M}$,
$\mathfrak{M}^{\prime}$, for every $w\in W$ and $w^{\prime}\in W^{\prime}$ we
have
$\\{\varphi\in\mathsf{Form}(\mathcal{L}_{\diamondsuit}):\mathfrak{M},w\Vdash\varphi\\}=\\{\varphi\in\mathsf{Form}(\mathcal{L}_{\diamondsuit}):\mathfrak{M}^{\prime},w^{\prime}\Vdash\varphi\\}$
if and only if the two states $w$ and $w^{\prime}$ are bisimilar (cf. [2]).
Our main results, however, will be concentrated on the bounded structures.

######  Definition 3.2.

Let $u_{0},\dots,u_{n}$ be different ultrafilters over $W$. We say that the
subsets $D_{u_{0}},\dots,D_{u_{n}}\subseteq W$ are distinguishing elements for
the ultrafilters $u_{0},\dots,u_{n}$, if $D_{u_{i}}\cap D_{u_{j}}=\emptyset$,
whenever $i\neq j\leq n$, and $D_{u_{i}}\in u_{j}$ iff $i=j$.

######  Proposition 3.3.

Fix any structure $\mathfrak{F}=\langle W,R\rangle$ and $u\in\mathrm{Uf}(W)$.
If $\\{w\in W:\deg^{+}(w)\leq n\\}\in u$, then $\deg^{+}(u)\leq n$.

###### Proof.

Let $X=\\{w\in W:\deg^{+}(w)\leq n\\}$. By way of contradiction, assume that
$\deg^{+}(u)>n$. For $i\leq n$ let $v_{i}\in\mathrm{Uf}(W)$ be different
ultrafilters, such that $R^{\mathfrak{ue}}uv_{i}$ and fix some distinguishing
elements $D_{v_{i}}\in v_{i}$. Then $\bigcap_{i\leq n}R^{-}(D_{v_{i}})\cap
X\in u$. Hence there is some $s\in X$ with $\deg^{+}(s)>n$, which is a
contradiction. ∎

#### Locally finite structures

Regarding the first constraint on the relation, we present some basic
connections between the ultrafilter extension and ultrapower of locally finite
structures in terms of generated substructures from the standpoint of modal
logic. A structure $\mathfrak{F}^{\prime}=\langle
W^{\prime},R^{\prime}\rangle$ is called a generated substructure of
$\mathfrak{F}=\langle W,R\rangle$ (notation:
$\mathfrak{F^{\prime}}\trianglelefteq\mathfrak{F}$), if
$\mathfrak{F}^{\prime}\leq\mathfrak{F}$ and moreover, for all $w^{\prime}\in
W^{\prime}$ and $v\in W$, $Rw^{\prime}v$ implies $v\in W^{\prime}$.

######  Proposition 3.4 (Theorem 2.5 in [13]).

$\mathfrak{F}\unlhd\mathfrak{F}^{\mathfrak{ue}}$ if and only if $\mathfrak{F}$
is $\deg^{+}$-finite.

###### Proof.

($\Leftarrow$) Suppose $R^{\mathfrak{ue}}\pi_{w}v$. As $\mathfrak{F}$ is
$\deg^{+}$-finite, there is some $n\in\omega$ such that
$R^{+}(w)=\\{w_{0},\dots,w_{n}\\}$. For any $X\in v$, since $w\in R^{-}(X)$,
there exists an $i\leq n$, such that $w_{i}\in X$. We claim that
$v=\pi_{w_{i}}$, for some $i\leq n$. Otherwise $W\setminus
R^{+}(w)=\bigcap_{i\leq n}(W\setminus\\{w_{i}\\})\in v$. However, for no
$w_{i}\in R^{+}(w)$ we have $w_{i}\in W\setminus R^{+}(w)$, which is a
contradiction.

($\Rightarrow$) Suppose that there is some $w\in W$, such that
$\deg^{+}(w)\geq\omega$. Consider a $v\in\mathrm{Uf}^{*}(W)$ with $R^{+}(w)\in
v$. It is enough to show that $R^{\mathfrak{ue}}\pi_{w}v$, as in this case
$\mathfrak{F}\not\trianglelefteq\mathfrak{F}^{\mathfrak{ue}}$. Pick any $X\in
v$, then $R^{+}(w)\cap X\in v$. Let $s\in R^{+}(w)\cap X$, then $Rws$ and
$w\in R^{-}(X)$, that is $R^{-}(X)\in\pi_{w}$. ∎

Now we have the following simple characterization via generated substructures.

######  Theorem 3.5.

Let $\mathfrak{F}=\langle W,R\rangle$ be a structure, $|I|\geq\aleph_{0}$ and
$D$ be an $\aleph_{1}$-incomplete ultrafilter over $I$. The following are
equivalent:

  1. (i)

$\mathfrak{F}$ is $\deg^{+}$-finite,

  2. (ii)

$\mathfrak{F}\unlhd\mathfrak{F}^{\mathfrak{ue}}$,

  3. (iii)

$\mathfrak{F}\unlhd\,^{I}\mathfrak{F}/D$.

###### Proof.

(i) $\Rightarrow$ (iii) Suppose that $\deg^{+}(w)<\aleph_{0}$ for all $w\in
W$. In order to avoid cumbersome notation let us denote
${}^{I}\mathfrak{F}/D=\langle W^{*},R^{*}\rangle$ and use $[c_{w}]_{D}\in
W^{*}$ to denote the diagonal element for $w\in W$. Assume, for the sake of
contradiction, that $\mathfrak{F}\not\trianglelefteq\,^{I}\mathfrak{F}/D$.
Hence, there is some $[c_{w}]_{D},[f]_{D}\in\,W^{*}$, such that
$[f]_{D}\neq[c_{v}]_{D}$ for all $v\in W$, but $R^{*}[c_{w}]_{D}[f]_{D}$. Then
$\\{i\in I:Rwf(i)\\}\in D$ and for all $v\in R^{+}(w)$ we have that $\\{i\in
I:v\neq f(i)\\}\in D$, as $[c_{v}]_{D}\neq[f]_{D}$. Since $R^{+}(w)$ is
finite, $\emptyset=\bigcap_{v\in R^{+}(w)}\\{i\in I:v\neq f(i)\\}\cap\\{i\in
I:Rwf(i)\\}\in D$, which is a contradiction.

(iii) $\Rightarrow$ (i) Let $\mathfrak{F}\unlhd\,^{I}\mathfrak{F}/D$ and again
assume, by way of contradiction, that $\deg^{+}(w)\geq\aleph_{0}$, for some
$w\in W$. Consider an enumeration of $R^{+}(w)=\\{v_{\alpha}:\alpha<\beta\\}$.
We construct an $[f]_{D}\in W^{*}$, such that $[f]_{D}\neq[c_{v}]_{D}$ for all
$v\in W$, but $R^{*}[c_{w}]_{D}[f]_{D}$. As $D$ is $\aleph_{1}$-incomplete,
there exists $\\{I_{n}:n\in\omega\\}\subseteq D$, such that $I_{0}=I$,
$I_{n}\supseteq I_{n+1}$, and $\bigcap_{n<\omega}I_{n}=\emptyset$. Hence, for
all $i\in I$ there is an $m(i)\in\omega$, such that $i\in I_{m(i)}$ and for
all $n>m(i)$, $i\not\in I_{n}$. We define $f\in\,^{I}W$ as follows: let
$f(i)=v_{m(i)}$, where $v_{m(i)}\in R^{+}(w)$. Then for each $v_{\alpha}\in
R^{+}(w)$, we have $[f]_{D}\neq[c_{v_{\alpha}}]_{D}$ because of the following
reason. Pick $v_{\alpha}\in R^{+}(w)$. If $\omega\leq\alpha<\beta$, then
$\\{i\in I:f(i)=v_{\alpha}\\}=\emptyset$ by definition of $f$. On the other
hand, for $\alpha<\omega$ we have two cases. If $v_{\alpha}\neq v_{m(i)}$ for
any $i\in I$, then again by definition of $f$ we obtain $\\{i\in
I:f(i)=v_{\alpha}\\}=\emptyset$. Otherwise $v_{\alpha}=v_{m(i)}$ for some
$i\in I$. Then $\\{i\in I:f(i)=v_{m(i)}\\}\subseteq I_{m(i)}\setminus
I_{m(i)+1}\not\in D$. However, we have $R^{*}[c_{w}]_{D}[f]_{D}$, as $\\{i\in
I:Rwf(i)\\}=I\in D$, contradicting to
$\mathfrak{F}\unlhd\,^{I}\mathfrak{F}_{/D}$.

The proof of (i) $\Leftrightarrow$ (ii) is Proposition 3.4. ∎

######  Remark 3.6.

We note that the proposition above admits an immediate dual characterization
on $\deg^{-}$ due to Theorem 2 from [29], according to which,

$(R^{-1})^{\mathfrak{ue}}=(R^{\mathfrak{ue}})^{-1}.$

However promising the locally finite structures are, their first-order model
theoretic connection to ultrafilter extensions is doomed to fail at a very
first level.222We are grateful to the referee for pointing out the next
example. Consider the structure
$\mathfrak{N}=\biguplus_{n\in\omega}\mathfrak{N}_{n}$, the disjoint union of
$\mathfrak{N}_{n}=\langle n,<\rangle$, for all $n\in\omega$:

$0$$0$$1$$0$$1$$2$$\vdots$

######  Proposition 3.7.

$\mathfrak{N}^{\mathfrak{ue}}$ has reflexive points, hence
$\mathfrak{N}\not\equiv\mathfrak{N}^{\mathfrak{ue}}$.

###### Proof.

Let $F$ be the family of choice functions of the form
$f:\omega\to\bigcup_{n\in\omega}\mathfrak{N}_{n}$, and let
$X_{f}=\mathfrak{N}\setminus\\{f(n):n\in\omega\\}$. Then the set
$u^{*}=\\{X_{f}:f\in F\\}$ has F.I.P., and any ultrafilter extending $u^{*}$
is reflexive. ∎

##  4\. Ultrafilter extension of bounded graphs

From now on, by $\mathfrak{F}=\langle W,R\rangle$ we will always understand a
bounded structure/graph. These structures were intensively studied in modal
logics under the title bounded alternatives [16, 4]. Our final goal is to
prove $\mathfrak{F}\preceq\mathfrak{F}^{\mathfrak{ue}}$, which will be
established via some ultrapower ${}^{I}\mathfrak{F}/D$ such that
$\mathfrak{F}\preceq\mathfrak{F}^{\mathfrak{ue}}$ and
$\mathfrak{F}^{\mathfrak{ue}}\preceq\,^{I}\mathfrak{F}/D$. Before doing so, we
motivate the class of bounded structures by the following warming up example.

######  Example 4.1.

Let $\mathfrak{F}=\langle\mathbb{N},S\rangle$, where the graph of $S$ is the
successor operator. There is an ultrapower ${}^{I}\mathfrak{F}/D$ of
$\mathfrak{F}$ such that
${}^{I}\mathfrak{F}/D\cong\mathfrak{F}^{\mathfrak{ue}}$.

###### Proof.

It is not hard to calculate from first principles that for each
$u\in\mathrm{Uf}^{*}(\mathbb{N})$ there is exactly one pair
$u^{-},u^{+}\in\mathrm{Uf}^{*}(\mathbb{N})$ such that
$u^{-}S^{\mathfrak{ue}}u$ and $uS^{\mathfrak{ue}}u^{+}$, hence
$S^{\mathfrak{ue}}$ remains injective. Also, one can show that
$S^{\mathfrak{ue}}$ remains cycle-free. By Pospíšil’s Theorem
$|\mathrm{Uf}(\mathbb{N})|=2^{2^{\aleph_{0}}}$ and the structure
$\mathfrak{F}^{\mathfrak{ue}}$ consists of $\langle\mathbb{N},S\rangle$ and a
disjoint union of $2^{2^{\aleph_{0}}}$-many copies of
$\langle\mathbb{Z},S\rangle$. Hence considering an index set $I$ of
cardinality ${2^{\aleph_{0}}}$ and a regular ultrafilter $D$ over $I$, by
standard results (cf. Proposition 4.3.7 of [11]), the ultrapower
${}^{I}\mathfrak{F}/D$ will be of cardinality $2^{2^{\aleph_{0}}}$, and so
consequently ${}^{I}\mathfrak{F}/D\cong\mathfrak{F}^{\mathfrak{ue}}$. ∎

#### “Łoś Lemma-like” properties

Let $\mathsf{K}$ be a class of structures. Starting from the equivalence of
(2), we say that a formula with one free variable $\varphi(x)$ in the language
$\mathcal{L}_{R}$ has the Łoś Lemma-like property within $\mathsf{K}$, if for
all $\mathfrak{F}\in\mathsf{K}$ we have,

$\displaystyle\mathfrak{F}^{\mathfrak{ue}}\models\varphi(u)\Leftrightarrow\\{w\in
W:\mathfrak{F}^{\mathfrak{ue}}\models\varphi(w)\\}\in u,$ (3)

for all $u\in\mathrm{Uf}(W)$. In what follows, we investigate basic Łoś Lemma-
like properties within the class of bounded structures.

The next proposition is a straightforward application of the de Bruijn-Erdős
Theorem, however it serves as a key observation in proving Theorem 4.9.
Although the usual formulation concerns undirected graphs, it can be adopted
to directed ones. If $\langle G,E\rangle$ is directed, then a $k$-coloring of
$G$ is a function $c:G\to\\{0,\dots,k-1\\}$ such that for all $x\neq y\in G$
if $\langle x,y\rangle\in E$, then $c(x)\neq c(y)$, i.e. reflexive loops do
not ruin the coloring. Also, it is easy to see by induction, that whenever a
finite directed graph $\langle G,E\rangle$ has $\deg(G)\leq k$, then it is
$k+1$ colorable.

######  Proposition 4.2.

Let $\mathfrak{F}=\langle W,R\rangle$ be a bounded graph. Then for all
$u\in\mathrm{Uf}(W)$ we have that $\mathfrak{F}^{\mathfrak{ue}}\models Ruu$
iff $\\{w\in W:\mathfrak{F}\models Rww\\}\in u$.

###### Proof.

($\Leftarrow$) Holds trivially for any ultrafilter extension.
($\Rightarrow$) Let $X=\\{w\in W:\mathfrak{F}\not\models Rww\\}$, and assume
that $X\in u$. As $\mathfrak{F}$ is bounded, there is some $m\in\omega$, such
that $\deg(w)\leq m$, for all $w\in W$. Hence, for all finite $H\subseteq X$,
the graph $\langle H,{R\upharpoonright H}\rangle$ is $m+1$-colorable.
Therefore, the graph $\langle X,{R\upharpoonright X}\rangle$ is
$m+1$-colorable too by the de Bruijn-Erdős Theorem. Such an $m+1$ coloring
gives an $m+1$ partition of $\bigcup_{i\leq m}C_{i}=X$, and say $C_{k}\in u$.
Then $R^{-}(C_{k})\cap C_{k}=\emptyset$, hence
$\mathfrak{F}^{\mathfrak{ue}}\not\models Ruu$. ∎

######  Proposition 4.3.

Let $\mathfrak{F}=\langle W,R\rangle$ be a bounded structure, then

$\deg^{+}(u)=n\text{ if and only if }\\{w\in W:\deg^{+}(w)=n\\}\in u.$

###### Proof.

($\Leftarrow$) Suppose that $X=\\{w\in W:\deg^{+}(w)=n\\}\in u$. Then by
Proposition 3.3 we have that $\deg^{+}(u)\leq n$. Assume, by way of
contradiction, that $\deg^{+}(u)=m$, for some $m<n$ and fix distinguishing
elements for $R^{+}(u)=\\{v_{0},\dots,v_{m}\\}$. Now, we have two cases.
Either,

$A=\\{w\in X:(\exists z_{w}\in R^{+}(w))(z_{w}\not\in\bigcup_{0\leq i\leq
m}D_{v_{i}})\\}\in u$

or

$B=\\{w\in X:|R^{+}(w)\cap D_{v_{i}}|>2\\}\in u$

for some $0\leq i\leq m$. In the first case, it is easy to see that the system

$v^{*}=\\{R^{+}(Y):Y\in u\\}\cup\\{\\{z_{w}\in W:w\in A\\}\\}$

has F.I.P., and any ultrafilter $v$ extending $v^{*}$ has the property $Ruv$,
and $v\neq v_{i}$, for all $0\leq i\leq m$. This contradicts the assumption
that $\deg^{+}(u)=m$. For the second case, we define the graph $H=\langle
B,E\rangle$, where

$\\{x,y\\}\in E\text{ if and only if }(\exists z\in D_{v_{i}})(Rxz\wedge
Ryz).$

As $\mathfrak{F}$ is bounded, there is some $m\in\omega$, such that
$\deg_{E}(w)\leq m$, for all $w\in H$. Hence, for all finite $G\subseteq B$,
the graph $\langle G,{E\upharpoonright G}\rangle$ is $m+1$-colorable.
Consequently $H$ is $m+1$ colorable, and there is some $C_{k}\in u$, as in
Proposition 4.2. Then for each $w,t\in C_{k}$ we must have $D_{v_{i}}\cap
R^{+}(w)\cap R^{+}(t)=\emptyset$. Hence, consider any partition $Z_{0}\uplus
Z_{1}=R^{+}(C_{k})\cap D_{v_{i}}$, where each $Z_{i}$ picks at least one
element from $R^{+}(w)\cap D_{v_{i}}$, for each $w\in C_{k}$.

$R^{+}(C_{k})\cap
D_{v_{i}}$$C_{k}$$\dots$$\dots$$Z_{1}$$Z_{1}$$Z_{1}$$Z_{0}$$Z_{0}$$Z_{1}$$Z_{0}$$Z_{1}$$Z_{1}$$Z_{1}$$Z_{1}$

Partition of $R^{+}(C_{k})\cap D_{v_{i}}$

Consequently, for $i\in\\{0,1\\}$ the system $z^{*}_{i}=\\{R[Y]:Y\in
u\\}\cup\\{Z_{i}\\}$ has F.I.P. Therefore each $z^{*}_{i}$ extends to some
ultrafilter $z_{i}$ with $R^{\mathfrak{ue}}uz_{i}$. As $Z_{0}\uplus Z_{1}$ is
a partition, we may assume that $Z_{0}\not\in v_{i}$. Hence $z_{0}\neq v_{i}$
and we obtain $\deg^{+}(u)>m$, which is a contradiction.
($\Rightarrow$) If $\deg^{+}(u)=n$, then by considering the distinguishing
elements for $R^{+}(u)=\\{v_{0},\dots,v_{n}\\}$ we obtain $\\{w\in
W:\deg^{+}(w)\geq n\\}\in u$. If $\\{w\in W:\deg^{+}(w)=n\\}\not\in u$, then
since $\mathfrak{F}$ is bounded, there is some $m>n$, for which $\\{w\in
W:\deg^{+}(w)=m\\}\in u$. Now we can just simply repeat the whole construction
above. ∎

######  Remark 4.4.

In modal logic, the so called graded modal language ($\mathsf{GML}$) is an
extension by $\diamondsuit_{k}$, for all $k\in\omega$ which has the
interpretation,

$\mathfrak{M},w\Vdash\diamondsuit_{k}\varphi\Leftrightarrow|\\{v\in
W:Rwv\text{ and }\mathfrak{M},v\Vdash\varphi\\}|\geq k.$

One could think that an equivalence like (1) would shrink the proofs above
into one single line. However, there is no appropriate notion of an
ultrafilter extension for $\mathsf{GML}$ in frame semantics (cf. [25]).
Moreover, the property “every element has branching $n$” is not expressible by
an existential closure of any $r(u)$ formula and is not preserved under
$p$-morphisms. Nonetheless, it is preserved under ultrafilter extensions.

######  Definition 4.5.

Let $\mathfrak{F}$ be a structure and $w\in W$. For a fixed $n\in\omega$ we
define the sets:

  1. •

$\langle w\rangle^{0}=\\{w\\}$,

  2. •

$\langle w\rangle^{i+1}=R(\langle w\rangle^{i})\cup\langle w\rangle^{i}$ for
$i\leq n$.

Then the $n$-Hull of $w$ is the structure $\langle\langle
w\rangle^{n},R\\!\upharpoonright{\langle w\rangle^{n}}\rangle$. Also, we
blurry the distinction between an $n$-Hull and its underlying set. We let
$\langle w\rangle^{\omega}=\bigcup_{n\in\omega}\langle w\rangle^{n}$, and call
an element $s$ an endpoint of $\langle w\rangle^{n}$, if $s\in\langle
w\rangle^{n}\setminus\langle w\rangle^{n-1}$.

#### Notation

Given $\langle w\rangle^{n}$, we let $\varphi_{\langle w\rangle^{n}}(x)$ be
the $\mathcal{L}_{R}$-formula describing all the possible connections between
the elements of $\langle w\rangle^{n}$ with respect to $w$. Such a formula
always exists, as $\mathfrak{F}$ is bounded. By $\langle
w\rangle^{n}\cong\langle v\rangle^{n}$, we abbreviate the fact that there is
an isomorphism $f:\langle w\rangle^{n}\to\langle v\rangle^{n}$, such that
$f(w)=v$. Cleary, $\langle w\rangle^{n}\cong\langle v\rangle^{n}$ if and only
if $\mathfrak{F}\models\varphi_{\langle w\rangle^{n}}(v)$.

Our next goal is to prove the following Łoś Lemma-like characterization within
the class of bounded structures: For every bounded structure $\mathfrak{F}$,
$n\in\omega$ and $u\in\mathrm{Uf}(W)$ we will show sthat $\\{w\in W:\langle
w\rangle^{n}\cong\langle u\rangle^{n}\\}\in u$. For this purpose, we are going
to use the following example to outline the main ideas.

######  Example 4.6.

Let $\mathfrak{F}=\langle W,R\rangle$ be a structure $u\in\mathrm{Uf}^{*}(W)$,
and consider its 1-Hull: $\langle
u\rangle^{1}=\langle\\{u,v_{0},v_{1},v_{2},v_{3}\\},R^{\mathfrak{ue}}\upharpoonright\langle
u\rangle^{1}\rangle$, where

$R^{\mathfrak{ue}}\upharpoonright\langle u\rangle^{1}=\\{\langle
u,v_{i}\rangle:i\in\\{0,1\\}\\}\cup\\{\langle
v_{i},u\rangle:i\in\\{2,3,4\\}\\}\cup\\{\langle v_{0},v_{2}\rangle\\}$

that is:

$u$$v_{0}$$v_{1}$$v_{3}$$v_{2}$$v_{4}$

Our aim is to show that $\\{w\in W:\langle u\rangle^{1}\cong\langle
w\rangle^{1}\\}\in u$.

###### Proof.

Step 1: Let $D_{u},D_{v_{0}},\dots,D_{v_{4}}$ be pairwise disjoint
distinguishing elements for $u,v_{0},\dots,v_{4}$ and consider
$U_{0}=D_{u}\cap\\{w\in W:\deg^{+}(w)=\deg^{+}(u),\deg^{-}(w)=\deg^{-}(u)\\}$.
By Proposition 4.3 we have $U_{0}\in u$. Define the set $U_{1}$ as:

$\displaystyle R^{-}(D_{v_{0}})\cap R^{-}(D_{v_{1}})\cap R^{+}(D_{v_{2}})\cap
R^{+}(D_{v_{3}})\cap R^{+}(D_{v_{4}})\cap U_{0}.$ (4)

Then $U_{1}\in u$. Now, for each $w\in U_{1}$ there is exactly one $s_{w,0}\in
R^{+}(w)$ for which $s_{w,0}\in D_{v_{0}}$, and exactly one $s_{w,1}\in
R^{+}(w)$ for which $s_{w,1}\in D_{v_{1}}$. Moreover, $s_{w,0}\neq s_{w,1}$.
This is due to $D_{v_{1}}\cap D_{v_{0}}=\emptyset$ and the construction of
$U_{1}$. The same is true for all the members in $R^{-}(w)$. Hence, for each
$w\in U_{1}$, we let $f_{w}:\langle u\rangle^{1}\to\langle w\rangle^{1}$ to be
the function defined as:

$\displaystyle f_{w}(u)$ $\displaystyle=w$ $\displaystyle f_{w}(v_{i})$
$\displaystyle=s_{w,i}$

We will show that $\\{w\in W:f_{w}:\langle u\rangle^{1}\cong\langle
w\rangle^{1}\\}\in u$.

Step 2: First, we claim that

$\displaystyle U_{2}=\\{w\in U_{1}:Rwf_{w}(v_{0})\wedge
Rf_{w}(v_{0})f_{w}(v_{2})\wedge Rf_{w}(v_{2})w\\}\in u.$ (5)

Suppose otherwise. Then we have:

$\displaystyle U^{*}=\\{w\in U_{1}:\big{(}Rf_{w}(v_{2})w\wedge
Rwf_{w}(v_{1})\big{)}\to\neg Rf_{w}(v_{0})f_{w}(v_{2})\\}\in u$ (6)

Next, we define the following sets:

$\displaystyle A$ $\displaystyle=R^{+}(U^{*})\cap D_{v_{0}}\in v_{0}$
$\displaystyle B$ $\displaystyle=R^{+}(A)\cap D_{v_{2}}\in v_{2}$
$\displaystyle C$ $\displaystyle=R^{+}(B)\cap U^{*}\in u$

Pick any $w\in C$. As $w\in R^{+}(B)$ and $w\in U^{*}$, we have that
$f_{w}(v_{2})\in D_{v_{2}}\cap R^{+}(A)$ with $Rf_{w}(v_{2})w$, and this is
the only such element. Since $f_{w}(v_{2})\in R^{+}(A)$, we have that
$Rtf_{w}(v_{2})$ for some $t\in R^{+}(U^{*})\cap D_{v_{0}}$. Observe that
$t\neq f_{w}(v_{0})$, otherwise $Rwf_{w}(v_{0})$ would contradict to $w\in
U^{*}$. Also $t\in R^{+}(U^{*})$ implies an existence of some $w^{\prime}\in
U^{*}$, such that $Rw^{\prime}t$. Since $t\in D_{v_{0}}$, we must have $w\neq
w^{\prime}$. Hence, let us define

$\displaystyle\nabla(x)=\\{y\in C:(\exists s\in B)(\exists t\in A)(Rsx\wedge
Rts\wedge Ryt)\\}$ (7)

and define the graph $\langle C,E\rangle$ such that:

$\displaystyle\\{x,y\\}\in E\iff y\in\nabla(x)\text{ or }x\in\nabla(y)$ (8)

  1. •

As the original structure $\mathfrak{F}$ is bounded, there is some
$m\in\omega$, such that for all finite subgraphs $H\leq C$, we have that
$\deg_{E}(H)\leq m$. Hence $\langle H,E\rangle$ is $m+1$ colorable, and so is
$\langle C,E\rangle$ by the de Bruijn-Erdős Theorem via some coloring
$c$.333In general, the exact value of $m\in\omega$ depends on $\nabla(X)$, and
on the original structure $\mathfrak{F}$ itself. Nevertheless, there is some
$m\in\omega$, such that for each $H\leq C$, $\deg_{E}(H)\leq m$, since
$\mathfrak{F}$ is bounded. This also applies to the corresponding part of
Theorem 4.9.

  2. •

This coloring gives an $m+1$ partition of $\bigcup_{\ell\leq m}M_{\ell}=C\in
u$. Let’s say $M_{k}\in u$. Then consider the sets;

$\displaystyle A^{\prime}$ $\displaystyle=R^{+}(M_{k})\cap D_{v_{0}}\in v_{0}$
$\displaystyle B^{\prime}$ $\displaystyle=R^{+}(A^{\prime})\cap D_{v_{2}}\in
v_{2}$ $\displaystyle C^{\prime}$ $\displaystyle=R^{+}(B^{\prime})\in u$

  1. Since $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$, for all $s\in C^{\prime}$ there is some $t\in M_{k}$ such that $sEt$. Hence $c(s)\neq c(t)=k$. However, $M_{k}\cap C^{\prime}=\emptyset$, as every member of $C^{\prime}$ has different color from $k$, which is a contradiction.

Step 3: Finally, we need to assure the existence of $V\subseteq U_{2}$, such
that $V\in u$, and no “extra” relations between the element are added. We can
single out these extra relations one by one. As an example, assume, for the
sake of contradiction, that

$\displaystyle V^{*}=\\{w\in U_{2}:Rwf_{w}(v_{0})\wedge Rwf_{w}(v_{1})\wedge
Rf_{w}(v_{0})f_{w}(v_{1})\\}\in u.$ (9)

That is, for all $w\in V^{*}$, the map $f_{w}:\langle u\rangle^{1}\to\langle
w\rangle^{1}$ is not an isomorphism, as $f_{w}(v_{i})=s_{i}$ and
$Rf_{w}(v_{0})f_{w}(v_{1})$, but not $R^{\mathfrak{ue}}v_{0}v_{1}$. Since not
$R^{\mathfrak{ue}}v_{0}v_{1}$, there is some $X\in v_{0}$ such that
$R^{+}(X)\not\in v_{1}$, hence

$\displaystyle A$ $\displaystyle=X\cap D_{v_{0}}\in v_{0}$ $\displaystyle B$
$\displaystyle=\big{(}W\setminus{R^{+}(X)}\big{)}\cap D_{v_{1}}\in v_{1}$

Then it is easy to see why $\emptyset=R^{-}(A)\cap R^{-}(B)\cap V^{*}\in u$.
Otherwise let $w$ be an element in the intersection. Since $w\in R^{-}(A)$,
there is some $s\in X$, such that $Rws$. As $s\in D_{v_{0}}$, by the
assumption on $w\in V^{*}$, we have that $s=f_{w}(v_{0})$. Similarly, we get
$f_{w}(v_{1})\in B$. However, $w\in V^{*}$ implies
$Rf_{w}(v_{0})f_{w}(v_{1})$, whereas $f_{w}(v_{0})\in X$ and
$f_{w}(v_{i})\in\big{(}W\setminus{R^{+}(X)}\big{)}$ implies $\neg
Rf_{w}(v_{0})f_{w}(v_{1})$. This gives a contradiction. By iterating this
process we obtain $\\{w\in U_{2}:f_{w}:\langle w\rangle^{1}\cong\langle
u\rangle^{1}\\}\in u$. But then $\\{w\in U_{2}:f_{w}:\langle
w\rangle^{1}\cong\langle u\rangle^{1}\\}\subseteq\\{w\in W:\langle
w\rangle^{1}\cong\langle u\rangle^{1}\\}\in u$. ∎

#### Notation.

Before turning to Theorem 4.9 let us introduce some useful concepts and
notation. For a fixed structure $\mathfrak{F}=\langle W,R\rangle$ and $s,t\in
W$, we say that there is a road from $s$ to $t$ if there are pairwise
different elements $w_{0},\dots,w_{n}$ such that $s=w_{0}$, $t=w_{n}$ and
$w_{0}R_{1}^{\circ}\dots R_{n}^{\circ}w_{n}$, where each
$R_{i}^{\circ}\in\\{R,R^{-1}\\}$. Then $R[s,t]$ abbreviates the existence of a
concrete road from $s$ to $t$. To avoid cumbersome notation, if we already
picked a road $R[s,t]$, by $R[t,s]$ we mean its “inverse”, i.e. the road with
$(R_{i}^{\circ})^{-1}$ in each step. When we say that there are
$s=w_{0},\dots,w_{n}=t\in W$ such that $R[s,t]$, we mean that the particular
road $R[s,t]$ was constructed from these elements. Finally, if there are roads
$R[w,t]$ and $R[t,s]$, then their “composition” from $w$ to $s$ along $R[w,t]$
and $R[t,s]$ is denoted by $R[w,t,s]$.

######  Definition 4.7.

Let $u,v\in\mathrm{Uf}(W)$ and suppose that there are $v_{0},\dots,v_{n}$ with
$u=v_{0}$ and $v=v_{n}$ such that
$u(R^{\mathfrak{ue}})_{1}^{\circ}\dots(R^{\mathfrak{ue}})^{\circ}_{n}v$ is a
road. The ultrafilter road of $R^{\mathfrak{ue}}[u,v]$ based on $X\in u$ is
the set $\Delta(X,R^{\mathfrak{ue}}[u,v])$ defined as:

$\displaystyle\Delta_{0}\big{(}X,R^{\mathfrak{ue}}[u,v]\big{)}$
$\displaystyle=X$
$\displaystyle\Delta_{i+1}\big{(}X,R^{\mathfrak{ue}}[u,v]\big{)}$
$\displaystyle=\begin{cases}R^{+}\Big{(}\Delta_{i}\big{(}X,R^{\mathfrak{ue}}[u,v]\big{)}\Big{)}\cap
D_{v_{i+1}}&\text{if }(R^{\mathfrak{ue}})^{\circ}_{i+1}=R^{\mathfrak{ue}}\\\
R^{-}\Big{(}\Delta_{i}\big{(}X,R^{\mathfrak{ue}}[u,v]\big{)}\Big{)}\cap
D_{v_{i+1}}&\text{if
}(R^{\mathfrak{ue}})^{\circ}_{i+1}=(R^{\mathfrak{ue}})^{-1}\vspace{.2cm}\end{cases}$

Finally let
$\Delta\big{(}X,R^{\mathfrak{ue}}[u,v]\big{)}:=\Delta_{n}\big{(}X,R^{\mathfrak{ue}}[u,v]\big{)}$.

######  Definition 4.8.

Let ${R}[w_{0},w_{n}]$ be a particular road along some $w_{0},\dots,w_{n}\in
W$ and $R^{\mathfrak{ue}}[v_{0},v_{m}]$ be another road along some
$v_{0},\dots,v_{m}\in\mathrm{Uf}(W)$. Then ${R}[w_{0},w_{n}]$ is ultrafilter
similar to ${R^{\mathfrak{ue}}}[v_{0},v_{m}]$ if $n=m$, moreover for each
$0\leq i\leq n$ the following holds:

  1. •

if $R^{\circ}_{i}=R$, then
$(R^{\mathfrak{ue}})_{i}^{\circ}=R^{\mathfrak{ue}}$,

  2. •

if $R_{i}^{\circ}=R^{-1}$, then
$(R^{\mathfrak{ue}})^{\circ}_{i}=(R^{\mathfrak{ue}})^{-1}$,

  3. •

$w_{i}\in D_{v_{i}}$.

Now we are ready to prove our key theorem.

######  Theorem 4.9.

Let $\mathfrak{F}$ be a bounded graph. Then for all $n\in\omega$ and
$u\in\mathrm{Uf}^{*}(W)$, we have:

$\\{w\in W:\langle w\rangle^{n}\cong\langle u\rangle^{n}\\}\in u.$

###### Proof.

Step 1: Pick any $u\in\mathrm{Uf}^{*}(W)$ and $n\in\omega$. Let
$u,v_{0},\dots,v_{k}\in\langle u\rangle^{n}$ be an enumeration with
distinguishing elements $D_{u},D_{v_{0}},\dots,D_{v_{k}}$. By Proposition 4.2,
we may assume that for each $i\leq k$ we have that $D_{v_{i}}\subseteq\\{w\in
W:\mathfrak{F}\models Rww\\}$, whenever $\mathfrak{F}^{\mathfrak{ue}}\models
Rv_{i}v_{i}$ and $D_{v_{i}}\subseteq\\{w\in W:\mathfrak{F}\not\models Rww\\}$
whenever $\mathfrak{F}^{\mathfrak{ue}}\not\models Rv_{i}v_{i}$. Suppose for
some $m<n$ we already know that there is some $U_{m}\subseteq D_{u}$, such
that $U_{m}\in u$ with the following property: For all $w\in U_{m}$

  1. (i)

there is an isomorphism $f_{w,m}:\langle u\rangle^{m}\to\langle w\rangle^{m}$,
such that $f_{w,m}(u)=w$,

  2. (ii)

$f_{w,m}(v_{i})\in D_{v_{i}}$.

As for the base case $m=0$, we have that $U_{0}\in u$, again by Proposition
4.2. In what follows, up to Step 4 we present a technique to obtain:

$\displaystyle U_{m+1}=\left\\{w\in U_{m}\
:\parbox[c]{216.81pt}{\centering$\exists f_{w,m+1}:\langle
w\rangle^{m+1}\cong\langle u\rangle^{m+1},f_{w,m}\subseteq f_{w,m+1},$\\\
$(\forall v\in\langle u\rangle^{m+1})f_{w,m+1}(v)\in D_{v}$
\@add@centering}\right\\}\in u.$ (10)

Let $e_{0},\dots,e_{r}$ be an enumeration of all the endpoints of $\langle
u\rangle^{m}$, and consider $e_{0}$.

$\langle u\rangle^{m}$$u$$\langle
u\rangle^{n}$$w$$w^{\prime}$$w^{\prime\prime}$

Illustration of the isomorphism $f_{w,m}:\langle u\rangle^{m}\to\langle
w\rangle^{m}$

We can assume that $U_{m}$ has the following additional property: For all
$w\in U_{m}$, $\deg^{+}(f_{w,m}(e_{0}))=\deg^{+}(e_{0})$ and
$\deg^{-}(f_{w,m}(e_{0}))=\deg^{-}(e_{0})$. Otherwise let’s say that
$X=\\{w\in U_{m}:\deg^{+}(f_{w,m}(e_{0}))=k\neq\deg^{+}(e_{0})\\}\in u$. Since
there is some road $R^{\mathfrak{ue}}[u,e_{0}]$ in $\langle u\rangle^{m}$,
consider its ultrafilter road
$\Delta\big{(}X,R^{\mathfrak{ue}}[u,e_{0}]\big{)}\in e_{0}$. Observe that if
$t\in\Delta\big{(}X,R^{\mathfrak{ue}}[u,e_{0}]\big{)}$, then
$t=f_{w,m}(e_{0})$ for some $w\in X$, by the assumption on $U_{m}$. Therefore
$\emptyset=\Delta\big{(}X,R^{\mathfrak{ue}}[u,e_{0}]\big{)}\cap\\{w\in
W:\deg^{+}(w)=\deg^{+}(e_{0})\\}\in e_{0}$ by Proposition 4.3. Let
$z_{0},\dots,z_{h}$ be an enumeration of
$R^{\mathfrak{ue}}(e_{0})\setminus\langle u\rangle^{m}$, then

$U^{\prime}_{m}=\bigcap_{\ell\leq
h}\Delta\big{(}D_{z_{\ell}},R^{\mathfrak{ue}}[z_{\ell},e_{0},u]\big{)}\cap
U_{m}\in u.$

Hence, for each $w\in U^{\prime}_{m}$ let $s_{w,z_{\ell}}$ denote the unique
element in $R(f_{w,m}(e_{0}))\setminus\langle w\rangle^{m}$, for which
$s_{w,z_{\ell}}\in D_{z_{\ell}}$, moreover $s_{w,z_{\ell}}$ and
$f_{w,m}(e_{0})$ are related by $R$ exactly as $e_{0}$ and $z_{\ell}$ are
related by $R^{\mathfrak{ue}}$. This fact is abbreviated by
$R^{\circ}f_{w,m}(e_{0})s_{w,z_{\ell}}$ and
$(R^{\mathfrak{ue}})^{\circ}e_{0}z_{\ell}$.

Step 2: Consider $z_{0}\in R^{\mathfrak{ue}}(e_{0})\setminus\langle
u\rangle^{m}$, the first item from the enumeration. Suppose that
$(R^{\mathfrak{ue}})^{\circ}z_{0}v_{i}$ for some $v_{i}\in\langle
u\rangle^{m}$. Then there are some $v_{0}=u,\dots,v_{p}=z_{0}$, such that
there is a road ${R^{\mathfrak{ue}}}[u,e_{0},z_{0}]$ in $\langle
u\rangle^{m}$. Also, there are some
$v^{\prime}_{0}=v_{i},\dots,v^{\prime}_{q}=u$, such that there is a road
${R^{\mathfrak{ue}}}[v_{i},u]$ in $\langle u\rangle^{m}$. We claim that,

$\displaystyle U_{z_{0}}^{v_{i}}=\left\\{w\in U^{\prime}_{m}\
:\parbox[c]{180.67499pt}{\centering$\Big{(}{R}[w,f_{w,m}(e_{0}),s_{w,z_{0}}]\wedge$
\\\ $\wedge s_{w,z_{0}}R^{\circ}f_{w,m}(v_{i})\wedge
R[f_{w,m}(v_{i}),w]\Big{)}$ \@add@centering}\right\\}\in u,$ (11)

where ${R}[w,f_{w,m}(e_{0}),s_{w,z_{0}}]$ is ultrafilter similar to
$R^{\mathfrak{ue}}[u,e,v_{0}]$ and $R[f_{w,m}(v_{i}),w]$ is ultrafilter
similar to ${R^{\mathfrak{ue}}}[v_{i},u]$. Otherwise, we have,

$\displaystyle U^{*}=\left\\{w\in U^{\prime}_{m}\
:\parbox[c]{216.81pt}{\centering$\Big{(}R[w,f_{w,m}(v_{i})]\wedge
R[w,f_{w,m}(e_{0}),s_{w,z_{0}}]\wedge$ \\\ $\wedge\neg
f_{w,m}(v_{i})R^{\circ}s\Big{)}$ \@add@centering}\right\\}\in u.$ (12)

We define the ultrafilter roads:

$\displaystyle A_{\ell}$
$\displaystyle=\Delta_{\ell}\big{(}U^{*},R^{\mathfrak{ue}}[u,e_{0},z_{0}]\big{)}\cap
D_{v_{\ell}}$ for $1\leq\ell\leq p$ $\displaystyle B$
$\displaystyle=R^{\circ}(A_{p})\cap D_{v_{i}}$ $\displaystyle C_{j}$
$\displaystyle=\Delta_{j}\big{(}B,R^{\mathfrak{ue}}[v_{i},u]\big{)}\cap U^{*}$
for $1\leq j\leq q$

Let us abbreviate $C=C_{q}$ and pick $w\in C$. By the assumption on
$U^{\prime}_{m}$, and hence on $U^{*}$, there is exactly one road
$R[w,f_{w,m}(v_{i})]$ ultrafilter similar to $R^{\mathfrak{ue}}[u,v_{i}]$.
Also $f_{w,m}(v_{i})\in B$. Then $R^{\circ}f_{w,m}(v_{i})s$, for some
$s\in\Delta\big{(}U^{*},R^{\mathfrak{ue}}[u,e_{0},z_{0}]\big{)}$. Then $s\neq
s_{w,z_{0}}$ by assumption and there is a $w^{\prime}\in U^{*}$ with a road
$R[w^{\prime},f_{w^{\prime},m}(e_{0}),s]$ being ultrafilter similar to
$R^{\mathfrak{ue}}[u,e_{0},v_{0}].$ Since $w^{\prime}\in U^{*}$, we get $w\neq
w^{\prime}$. Using the same argument of Step 2 from Example 4.6, let us
define;

$\displaystyle\nabla(x)=\left\\{y\in
C:\parbox[c]{252.94499pt}{\centering$\Big{(}\bigwedge_{1\leq\ell\leq p}\exists
s_{\ell}\in\Delta_{\ell}(U^{*},R^{\mathfrak{ue}}[u,e_{0},z_{0}])\Big{)}$\\\
$\Big{(}\bigwedge_{1\leq j\leq q}\exists
t_{j}\in\Delta_{j}(B,R^{\mathfrak{ue}}[v_{i},u])\Big{)}$\\\
$\Big{(}{R}[x,s_{p-1},s_{p}]\wedge t_{1}R^{\circ}s_{p}\wedge
R[y,t_{1}]\Big{)}$ \@add@centering}\right\\}$ (13)

where ${R}[x,s_{p-1},s_{p}]$ is composed by the elements $s_{\ell}$’s
($1\leq\ell\leq p$) and ultrafilter similar to
${R^{\mathfrak{ue}}}[u,e_{0},v_{0}]$ and ${R}[y,t_{0}]$ composed by the
$t_{j}$’s ($1\leq j\leq q$) and ultrafilter similar to
$R^{\mathfrak{ue}}[u,v_{i}]$. Define the graph $\langle C,E\rangle$ such that:

$\displaystyle\\{x,y\\}\in E\iff y\in\nabla(x)\text{ or }x\in\nabla(y).$ (14)

As $\mathfrak{F}$ is bounded, there is some $m\in\omega$ such that for all
finite subgraphs $H$ of $C$ we have that $\deg_{E}(H)\leq m$. Hence $\langle
H,E\upharpoonright H\rangle$ is $m+1$ colorable and so is $\langle C,E\rangle$
by the de Bruijn-Erdős Theorem. The coloring gives an $m+1$ partition of
$\bigcup_{\ell\leq m}M_{\ell}=C\in u$. Let’s say $M_{k}\in u$. Now consider
the sets:

$\displaystyle A^{\prime}_{\ell}$
$\displaystyle=\Delta_{\ell}\big{(}M_{k},R^{\mathfrak{ue}}[u,e_{0},z_{0}]\big{)}\cap
D_{v_{\ell}}$ for $1\leq\ell\leq p$ $\displaystyle B^{\prime}$
$\displaystyle=R^{\circ}(A_{p}^{\prime})\cap D_{v_{i}}$ $\displaystyle
C^{\prime}_{j}$
$\displaystyle=\Delta_{j}\big{(}B^{\prime},R^{\mathfrak{ue}}[v_{i},u]\big{)}\cap
U^{*}$ for $1\leq j\leq q$

As above, we use the abbreviation $C^{\prime}=C^{\prime}_{q}$. Since each
$A^{\prime}_{\ell}\subseteq A_{\ell}$ and $C^{\prime}_{j}\subseteq C_{j}$,
moreover $B^{\prime}\subseteq B$, for all $s\in C^{\prime}$ there is some
$t\in M_{k}$, such that $sEt$. Hence $c(s)\neq c(t)=k$. However, $M_{k}\cap
C^{\prime}=\emptyset$, as every member of $C^{\prime}$ has different color
from $k$. This is a contradiction, since $M_{k}\cap C^{\prime}\in u$ by
construction.

Step 3: If $v_{\ell_{1}},\dots,v_{\ell_{n}}$ is an enumeration of
$R^{\mathfrak{ue}}(z_{0})\cap\langle u\rangle^{m}$ and
$U_{z_{0}}^{v_{\ell_{i}}}$ has been already constructed, repeat Step 2 by
using $U_{v_{0}}^{v_{\ell_{i}}}$ as the initial set to obtain
$U_{v_{0}}^{v_{\ell_{i+1}}}\subseteq U_{v_{0}}^{v_{\ell_{i}}}$, with
$U_{v_{0}}^{v_{\ell_{i+1}}}\in u$. Finally, for each $w\in
U_{z_{0}}^{v_{\ell_{n}}}$ put $f^{\prime}_{w,m}:=f_{w,m}\cup\\{\langle
z_{0},s_{w,z_{0}}\rangle\\}$. Similarly to Step 3 of Example 4.6, we can
obtain $V_{z_{0}}\subseteq U_{z_{0}}^{v_{\ell_{n}}}$, such that
$f^{\prime}_{w,m}:\langle u\rangle^{m}\cup\\{z_{0}\\}\to\langle
w\rangle^{m}\cup\\{s_{w,z_{0}}\\}$ is an isomorphism for all $w\in V_{z_{0}}$.

Step 4: We can further iterate the process described in Step 3. Consider the
next element in $R^{\mathfrak{ue}}(e_{0})=\\{z_{0},\dots,z_{h}\\}$. From the
previously obtained set we get $V_{z_{1}}\subseteq V_{z_{0}}$, where
$V_{z_{1}}\in u$ and for all $w\in V_{z_{1}}$ the function
$f^{\prime}_{w,m}\cup\\{\langle z_{1},s_{w,z_{1}}\rangle\\}$ is an
isomorphism. Hence, after $h$-step we reach $V_{z_{h}}\in u$. Then we may
repeat all these construction with all the other endpoints $e_{1},\dots,e_{r}$
from $\langle u\rangle^{m}$ in order to obtain $U_{m+1}\in u$ and isomorphisms
$f_{w,m+1}:\langle u\rangle^{m+1}\to\langle w\rangle^{m+1}$, for each $w\in
U_{m+1}$. By construction it will always be the case that $f_{w,m+1}(v_{i})\in
D_{v_{i}}$.

Step 5: After constructing $U_{m+1}$, we can simply repeat Step 1 – Step 4 to
construct $U_{n}\in u$ by using $U_{m+i}$ as the initial set from which we
obtain $U_{m+i+1}$. Finally, we conclude that $\\{w\in W:\langle
w\rangle^{n}\cong\langle u\rangle^{n}\\}\in u$, as $U_{n}\subseteq\\{w\in
W:\langle w\rangle^{n}\cong\langle u\rangle^{n}\\}$ and $U_{n}\in u$. ∎

Now we derive some important consequences of Theorem 4.9 regarding modal and
first-order model theoretic properties. As a direct corollary we have the
following.

######  Theorem 4.10.

For any bounded graph $\mathfrak{F}$ and ultrapower ${}^{I}\mathfrak{F}/D$,
$\Lambda(\mathfrak{F})=\Lambda(\mathfrak{F}^{\mathfrak{ue}})=\Lambda(^{I}\mathfrak{F}/D)$.

###### Proof.

The $\Lambda(\mathfrak{F}^{\mathfrak{ue}})\subseteq\Lambda(\mathfrak{F})$ part
always holds as was mentioned earlier. For the other direction we refer to the
notion of modal depth and $n$-bisimulation from [2]. Let
$\mathfrak{F}^{\mathfrak{ue}}\not\Vdash\varphi$ and $\text{dp}(\varphi)=n$ be
the modal depth of $\varphi$. Then for some valuation $V$ over
$\mathrm{Uf}(W)$ and $u\in\mathrm{Uf}(W)$, we have that
$\langle\mathfrak{F}^{\mathfrak{ue}},V\rangle,u\not\Vdash\varphi$. By Theorem
4.9 there is some $w\in W$, such that $\langle w\rangle^{n}\cong\langle
u\rangle^{n}$. Now, let $U$ be a valuation over $\mathfrak{F}$, such that for
all $s\in\langle w\rangle^{n}$ and $v\in\langle u\rangle^{n}$ if $s\mapsto v$,
then

$s\in U(p)\Leftrightarrow v\in V(p).$

From the isomorphism of the two $n$-Hulls it is easy to construct an
$n$-bisimulation between $s$ and $v$. As a consequence of Proposition 2.31
from [2], we get that $\langle\mathfrak{F},U\rangle,s\not\Vdash\varphi$ and
hence $\Lambda(\mathfrak{F})=\Lambda(\mathfrak{F}^{\mathfrak{ue}})$.

Since $\Sigma_{1}^{1}$-formulas are preserved under ultraproducts (cf. [11]),
by the standard translation of modal formulas into the $\Pi_{1}^{1}$-fragment,
$\Lambda(^{I}\mathfrak{F}/D)\subseteq\Lambda(\mathfrak{F})$ holds for any
structure. For the other direction a similar $n$-bisimulation argument applies
with the aid of Łoś’s Lemma. ∎

The next lemma is needed to prove Theorem 4.12.

######  Lemma 4.11.

Let ${}^{I}\mathfrak{F}/D$ be an ultrapower of $\mathfrak{F}$ over an
$\aleph_{1}$-incomplete ultrafilter $D$. Then for each non-diagonal element
$[a]_{D}\in\,^{I}W/D$, there is an $X\subseteq\mathrm{Uf}(W)$ with
$|X|={{\aleph_{0}}}$, such that for each $u,v\in X$ it holds that $\langle
v\rangle^{\omega}\cong\langle[a]_{D}\rangle^{\omega}\cong\langle
u\rangle^{\omega}$ and $\langle u\rangle^{\omega}\cap\langle
v\rangle^{\omega}=\emptyset$.

###### Proof.

Fix some $[a]_{D}$. By Łoś’s Lemma for each $n\in\omega$ we get $A_{n}=\\{i\in
I:\mathfrak{F}\models\varphi_{\langle[a]_{D}\rangle^{n}}(a(i))\\}\in D$. Let
$A_{n}^{\partial}=\\{a(i):i\in A_{n}\\}$. Since $[a]_{D}$ is non-diagonal,
each $A_{n}^{\partial}$ is infinite. Therefore, we can consider an injective
choice function $f:\omega\to\bigcup_{n\in\omega}A_{n}^{\partial}$, that is
$f(n)\in A_{n}^{\partial}$ and for all $n\neq m$ we have $f(n)\neq f(m)$.
Hence $Y=\\{f(n):n\in\omega\\}$ is infinite and by Pospíšil’s Theorem there
are $2^{2^{\aleph_{0}}}$ ultrafilters over $Y.$ For each
$v^{*}\in\mathrm{Uf}(Y)$ fix one $v\in\mathrm{Uf}(W)$ extending $v^{*}$, i.e.
$v^{*}\subseteq v$. By Theorem 4.9 we obtain

$\mathfrak{F}^{\mathfrak{ue}}\models\varphi_{\langle[a]_{D}\rangle^{n}}(v)\text{
and }\mathfrak{F}^{\mathfrak{ue}}\models\varphi_{\langle v\rangle^{n}}(v),$

for all $n\in\omega$. Now, for such a fixed $v\in\mathrm{Uf}(W)$ consider the
set $p_{v}=\\{\varphi_{\langle v\rangle^{n}}(x):n\in\omega\\}$. Then it is
clear that ${}^{I}\mathfrak{F}/D\models p_{v}([a]_{D})$. It should be routine
to verify that in fact $\langle[a]_{D}\rangle^{\omega}\cong\langle
v\rangle^{\omega}$, using the assumption of $D$ being $\aleph_{1}$-incomplete,
however we give a short sketch.

Since $D$ is $\aleph_{1}$-incomplete there is a sequence $\langle
I^{\prime}_{n}:n\in\omega\rangle$ such that $I^{\prime}_{n}\supseteq
I^{\prime}_{n+1}$ with $I^{\prime}_{n}\in D$ and
$\bigcap_{n<\omega}I^{\prime}_{n}=\emptyset$. Consider the decreasing sequence

$\displaystyle I_{0}$ $\displaystyle=I^{\prime}_{0},$ $\displaystyle I_{n+1}$
$\displaystyle=I^{\prime}_{n}\cap A_{n}.$

Then, for all $i\in I$, there is an $m(i)$ such that $i\in I_{m(i)}\setminus
I_{m(i)+1}$. For each $n\in\omega$ we let $J_{n}=\\{i\in I:m(i)=n\\}$. Now,
since for all $j\in J_{n}$ the set $\langle a(j)\rangle^{n}$ is finite, say
has $n_{J}\in\omega$ elements, we can construct choice functions
$a_{1},\dots,a_{n_{J}-1}:J_{n}\to W$ such that for $j\in J_{n}$ the set
$A_{n,j}=\\{a(j),a_{1}(j),\dots,a_{n_{J}-1}(j)\\}$ has the property

$\exists f_{n,j}:\langle u\rangle^{n}\cong\langle A_{n,j},\ R\upharpoonright
A_{n,j}\rangle.$

Pick $z\in\langle v\rangle^{\omega}$, we define the corresponding choice
function $a_{z}:I\to W$ as follows:

$\displaystyle a_{z}(i)=\begin{cases}f_{m(i),i}(z)&\text{ if }z\in\langle
v\rangle^{m(i)}\\\ b&\text{ otherwise}\end{cases}$

where $b$ is arbitrary, but fixed. Then the map
$\eta:\langle[a]_{D}\rangle^{\omega}\to\langle u\rangle^{\omega}$ defined by
$\eta([a_{z}]_{D})=z$ is an isomorphism.

Since $|\mathrm{Uf}(Y)|=2^{2^{\aleph_{0}}}$, and for each
$v^{*}\in\mathrm{Uf}(Y)$ we have that $|\langle
v\rangle^{\omega}|\leq\aleph_{0}$, by a simple cardinality argument there must
be a subset $X\subseteq\mathrm{Uf}(W)$ satisfying the conditions of the
present lemma. ∎

We recall the basic model theoretic facts that if
$\mathfrak{A}\leq\mathfrak{B}$, and for each finite sequence
$a_{0},\dots,a_{n}\in A$ and $b\in B$ there is an automorphism
$\eta:\mathfrak{B}\to\mathfrak{B}$ fixing $\overline{a}$ and moving $b$ into
$A$ (i.e. $\eta(a_{i})=a_{i}$ and $\eta(b)\in A$), then
$\mathfrak{A}\preceq\mathfrak{B}$. Also, if $\mathfrak{A}\preceq\mathfrak{C}$,
$\mathfrak{A}\leq\mathfrak{B}$ and $\mathfrak{B}\preceq\mathfrak{C}$, then
$\mathfrak{A}\preceq\mathfrak{B}$.

######  Theorem 4.12.

For any bounded graph $\mathfrak{F}$, there exists an ultrapower
${}^{I}\mathfrak{F}/D$ such that
$\mathfrak{F}\preceq\mathfrak{F}^{\mathfrak{ue}}\preceq\,^{I}\mathfrak{F}/D$.

###### Proof.

Let $\mathfrak{F}=\langle W,R\rangle$ be any bounded graph with $\lambda=|W|$,
and set $\kappa=2^{2^{\lambda}}=|\mathrm{Uf}(W)|$. Let
${}^{I}\mathfrak{F}/D=\langle W^{*},R^{*}\rangle$ be any
$\kappa^{+}$-saturated ultrapower of $\mathfrak{F}$ over an
$\aleph_{1}$-incomplete ultrafilter $D$. We claim that
$\mathfrak{F}^{\mathfrak{ue}}\preceq\,^{I}\mathfrak{F}/D$. First, we show the
embedding $\mathfrak{F}^{\mathfrak{ue}}\leq\,^{I}\mathfrak{F}/D$. As a
consequence of Theorem 3.5 and its dual, for each $w\in W$ we have:

$\langle
w\rangle^{\omega}\cong\langle\pi_{w}\rangle^{\omega}\cong\langle[c_{w}]_{D}\rangle^{\omega}.$

Hence, we let $f_{0}:\mathfrak{F}^{\mathfrak{ue}}\to\,^{I}\mathfrak{F}/D$ to
be the partial isomorphism, where $f_{0}(\pi_{w})=[c_{w}]_{D}$. Consider an
enumeration $\\{u_{\gamma}\in\mathrm{Uf}^{*}(W):\gamma<\kappa\\}$. For
$\gamma<\kappa$ we construct a sequence of partial isomorphisms
$f_{\gamma}:\mathfrak{F}^{\mathfrak{ue}}\to\,^{I}\mathfrak{F}/D$, such that:

  1. a)

$f_{\alpha}\subseteq f_{\gamma}$, for $\alpha<\gamma$,

  2. b)

$\langle u_{\gamma}\rangle^{\omega}\subseteq\mathrm{dom}(f_{\gamma+1})$,

  3. c)

$|\mathrm{dom}(f_{\gamma})|\leq|\gamma|+\aleph_{0}$,

  4. d)

$\langle u_{\gamma}\rangle^{\omega}\cong\langle
f_{\gamma+1}(u_{\gamma})\rangle^{\omega}$,

  5. e)

$f_{\gamma}=\bigcup_{\alpha<\gamma}f_{\alpha}$ if $\gamma$ is limit.

Assume that, for some $\beta<\kappa$ we have already defined the map
$f_{\beta}$, so let us now define $f_{\beta+1}$. There are two cases: If
$u_{\beta}\in\mathrm{dom}(f_{\alpha})$ for some $\alpha<\beta$, then let
$f_{\beta+1}=f_{\beta}$. Otherwise,
$u_{\beta}\not\in\bigcup_{\alpha<\beta}\text{dom}(f_{\alpha})$. Observe that
in this situation no $u_{\alpha}\in\langle u_{\beta}\rangle^{\omega}$ is
mapped by any previously defined $f_{\alpha}$ to ${}^{I}\mathfrak{F}/D$.

Consider the set $X=\bigcup_{\alpha<\beta}\langle
f_{\alpha+1}(u_{\alpha})\rangle^{\omega}$. We define the type:

$p_{u_{\beta}}(x)=\\{\varphi_{\langle
u_{\beta}\rangle^{n}}(x):n\in\omega\\}\cup\\{x\neq c:c\in X\\}$

with parameters from $X$. Since $|X|<\kappa^{+}$, we have that
$|p_{u_{\beta}}|<\kappa^{+}$ and since ${}^{I}\mathfrak{F}/D$ is
$\kappa^{+}$-saturated, we can find an element $[a]_{D}\in\,W^{*}$, such that
${}^{I}\mathfrak{F}/D\models p_{u}([a]_{D})$. Using the same argument from
Lemma 4.11 we can conclude that $\langle[a]_{D}\rangle^{\omega}\cong\langle
u\rangle^{\omega}$ and $\langle[a]_{D}\rangle^{\omega}\cap X=\emptyset$. Let
us denote this isomorphism by $\eta$ and define $f_{\beta+1}$ as

$f_{\beta+1}=\bigcup_{\alpha\leq\beta}f_{\beta}\cup\\{\langle
u,\eta(u)\rangle:u\in\langle u_{\beta}\rangle^{\omega}\\}.$

It is easy to see that $f_{\beta+1}$ indeed satisfies the conditions a)-e).
Finally, we set $f=\bigcup_{\gamma<\kappa}f_{\gamma}$. It is almost trivial
that

  1. •

$\mathrm{dom}(f)=\mathrm{Uf}(W)$,

  2. •

$f$ is an embedding.

Now, we show that $\mathfrak{F}^{\mathfrak{ue}}\preceq\,^{I}\mathfrak{F}/D$.
Pick $f(u_{0}),\dots,f(u_{n})\in W^{*}$ and $[a]_{D}\in W^{*}$. By Lemma 4.11,
there will be $v_{0},\dots,v_{n+1}\in\mathrm{Uf}(W)$ such that for $i\leq n+1$
it holds that $\langle
f(v_{i})\rangle^{\omega}\cong\langle[a]_{D}\rangle^{\omega}$ and $\langle
f(v_{i})\rangle^{\omega}\cap\langle f(v_{\ell})\rangle^{\omega}=\emptyset$.
Hence, for at least one such $v_{i}$ we must have that $\langle
f(v_{i})\rangle^{\omega}\cap\langle f(v_{j})\rangle^{\omega}=\emptyset$, for
$i\neq j\leq n$. Then let $\eta$ be the automorphism that isomorphically
permutes each element of $\langle[a]_{D}\rangle^{\omega}$ into $\langle
f(v_{i})\rangle^{\omega}$ and fixes every other pointwise. Since $\langle
f(v_{i})\rangle^{\omega}\cong\langle[a]_{D}\rangle^{\omega}$, the resulting
permutation is an automorphism moving $[a]_{D}$ into
$f[\mathfrak{F}^{\mathfrak{ue}}]$. Hence, we obtain that
$\mathfrak{F}\preceq\mathfrak{F}^{\mathfrak{ue}}\preceq\,^{I}\mathfrak{F}/D$.
∎

##  5\. Discussion

Regarding the other type of ultrafilter extension, [28] wonders about theories
such that elementary equivalence of their models lifts to their ultrafilter
extensions. Here, we have an immediate corollary:

######  Corollary 5.1.

For any bounded graphs $\mathfrak{F}$ and $\mathfrak{G}$ if
$\mathfrak{F}\equiv\mathfrak{G}$, then
$\mathfrak{F}^{\mathfrak{ue}}\equiv\mathfrak{G}^{\mathfrak{ue}}$.

It is natural to ask what other type of infinite structures can be isolated
within the class

$\mathsf{F}=\\{\mathfrak{F}:\mathfrak{F}\equiv\mathfrak{F}^{\mathfrak{ue}}\\}$

besides bounded graphs.

We note that $\mathsf{F}$ is not an elementary class, since it is not closed
under ultraproducts. To see this, consider the structures
$\mathfrak{N}_{n}=\langle n,<\rangle$ with their standard orderings. Then for
any non-principal ultrafilter $D$ over $\omega$, we have that
$\prod_{n\in\omega}\mathfrak{N}_{n}/D\models\forall x(x\not<x)$, but
$\big{(}\prod_{n\in\omega}\mathfrak{N}_{n}/D\big{)}^{\mathfrak{ue}}\models\exists
x(x<x)$, similarly to Example 2.2. We wonder whether $\mathsf{F}$ is closed
under elementary equivalence, that is given $\mathfrak{F}\in\mathsf{F}$ and
$\mathfrak{F}\equiv\mathfrak{G}$ does it imply $\mathfrak{G}\in\mathsf{F}$?

### Acknowledgement

The author is grateful to Zalán Gyenis for all the pleasant conversations
about the topic. We thank the anonymous reviewers for their many insightful
comments that improved the paper substantially. Supported by the ÚNKP-20-3 New
National Excellence Program of the Ministry for Innovation and Technology from
the Source of the National Research, Development and Innovation Fund.

## References

  * [1] H. Andréka, J. van Benthem, I. Németi. (1998).  Modal languages and bounded fragments of predicate logic.  Journal of Philosophical Logic,  27, 217-274.
  * [2] P. Blackburn, M. de Rijke, Y. Venema (2001). Modal Logic. Cambirdge University Press.
  * [3] P. Blackburn, J. van Benthem, F. Wolter (2006). Handbook of Modal Logic. Studies in Logic and Practical Reasoning. Elsevier.
  * [4] F. Bellissima (1988). On the lattice of extensions of the modal logics $\mathsf{KAlt}_{n}$. Archive for Mathematical Logic, 27(2), 107–114.
  * [5] J. van Benthem (1979).  Canonical Modal Logics and Ultrafilter Extensions.  The Journal of Symbolic Logic, 44(1) 1-8.
  * [6] J. van Benthem (1984).  Correspondence Theory.  Handbook of Philisophical Logic Vol. II, 327-344.
  * [7] J. van Benthem (1984).  Modal Formulas are Either Elementary or not $\Sigma\Delta$-Elementary.  The Journal of Symbolic Logic, 41(2), 436-438.
  * [8] J. van Benthem (1985).  Modal Logic and Classical Logic. Bibliopolis.
  * [9] B. Jónsson, A. Tarski (1951). Boolean algebras with operators, Part I: American Journal of Mathematics 73(4) (1951), 891–939, Part II: ibid. 74(1) (1952), 127–162.
  * [10] B. D. ten Cate (2005).  Model theory for extended modal languages.  PhD. thesis, ILLC.
  * [11] C.C. Chang H.J. Keisler (1990). Model Theory. Elsevier.
  * [12] A. Chagrov, M. Zakharyaschev (1997).  Modal Logic.  Clarendon Press, Oxford.
  * [13] B. Farkas, A. Simon. How canonical extensions are canonical? Manuscript.
  * [14] K. Fine (1975).  Some Connections Between Elementary and Modal Logic.  Studies in Logic and the Foundations of Mathematics 82, 15-31.
  * [15] M. Hollenberg (1998). Characterizations of Negative Definability in Modal Logic. Studia Logica, 60(3), 357-386.
  * [16] M. Kracht (1999).  Tools and Techniques in Modal Logic Studies in Logic and the Foundations of Mathematics, Volume 142.
  * [17] R.I. Goldblatt, (1989).  Varieties of complex algebras  Annals of Pure and Applied Logic, 44, 173-242.
  * [18] R. I. Goldblatt, S.K. Thomason (1975).  Axiomatic classes in propositional modal logic.  Lecture Notes in Mathematics, Springer 163-173.
  * [19] R. Goldblatt, I. Hodkinson, Y. Venema (2003).  On canonical modal logics that are not elementarily determined.  Algebra Universalis 34, 551-607.
  * [20] R. Goldblatt, I. Hodkinson, Y. Venema (2004).  Erdős Graphs Resolve Fine’s Canonicity Problem.  Bulletin of Symbolic Logic 10(02), 186-208.
  * [21] D. Marker (2006). Model theory: an introduction. Springer Science & Business Media.
  * [22] N. L. Poliakov, D. I. Saveliev (2021). On ultrafilter extensions of first-order models and ultrafilter interpretations. Archive for Mathematical Logic 60. 625–681. Available at arXiv:1812.06248
  * [23] M. de Rijke, H. Sturm (2001).  Global definability in basic modal logic. in: H. Wansing (ed.),  Essays on Non-Classical Logic, World Scientific Publishers.
  * [24] H. Sahlqvist (1975).  Correspondence and completeness in the first and second-order semantics for modal logic. in: S. Kanger (ed.),  Proc. of the 3rd Scandinavial Logic Symposium,Uppsala 1973, North-Holland, 110-143.
  * [25] K. Sano, M. Ma (2010).  Goldblatt-Thomason-style Theorems for Graded Modal Language.  Advances in Modal Logic 7, 330-349.
  * [26] D. I. Saveliev (2011).  Ultrafilter extensions of models.  Logic and Its Applications, Lecture Notes in Computer Science, Springer 162–177.
  * [27] D. I. Saveliev (2012).  On Ultrafilter extensions of models. in: S.-D. Friedman et al. (ed.),  The Infinity Project Proc. CRM Documents 11, Barcelona,  599-616.
  * [28] D. I. Saveliev, S. Shelah (2019).  Ultrafilter extensions do not preserve elementary equivalence.  Mathematical Logic Quarterly, 65(4), 511-516.
  * [29] D. I. Saveliev (2020). On two types of ultrafilter extensions of binary relations. Available at arXiv:2001.02456
  * [30] Y. Venema. (2000). Ultrafilter unions: an exercise in modal definability. in: A Nepomuceno et alii (editors). Logic, Language and Information: Proceedings of the First Workshop on Logic and Language. Instituto de Lógica, Lenguaje y Información, Universidad de Sevilla, Sevilla, 303–310.