On Two Concepts of Ultrafilter Extensions of First-Order Models and Their Generalizations

Abstract

There exist two known concepts of ultrafilter extensions of first-order models, both in a certain sense canonical. One of them [1] comes from modal logic and universal algebra, and in fact goes back to [2]. Another one [3, 4] comes from model theory and algebra of ultrafilters, with ultrafilter extensions of semigroups [5] as its main precursor. By a classical fact, the space of ultrafilters over a discrete space is its largest compactification. The main result of [3, 4], which confirms a canonicity of this extension, generalizes this fact to discrete spaces endowed with a first-order structure. An analogous result for the former type of ultrafilter extensions was obtained in [6].

Here we offer a uniform approach to both types of extensions. It is based on the idea to extend the extension procedure itself. We propose a generalization of the standard concept of first-order models in which functional and relational symbols are interpreted rather by ultrafilters over sets of functions and relations than by functions and relations themselves. We provide two specific operations which turn generalized models into ordinary ones, and establish necessary and sufficient conditions under which the latter are the two canonical ultrafilter extensions of some models.

The second author was supported by Grant 16-01-00615 of the Russian Foundation for Basic Research.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1. Fix a first-order language and consider an arbitrary model

$$ \mathfrak A=(X,F,\ldots ,R,\ldots ) $$

with the universe X, operations $F,\ldots \,$, and relations $R,\ldots$ . Let us define an abstract ultrafilter extension of $\mathfrak A$ as a model $\mathfrak A'$ (in the same language) of form

$$ \mathfrak A'=(\beta X,F',\ldots ,R',\ldots ) $$

where $\beta X$ is the set of ultrafilters over X (one lets $X\subseteq \beta X$ by identifying each $x\in X$ with the principal ultrafilter given by x), and operations $F',\ldots$ and relations $R',\ldots$ on $\beta X$ extend $F,\ldots$ and $R,\ldots$ resp. There are essentially two known ways to extend relations by ultrafilters, and one to extend maps. Partial cases of these extensions were discovered by various authors in different time and different areas, typically, without a knowledge of parallel studies in adjacent areas.

Recall that $\beta X$ carries a natural topology generated by basic open sets

$$ \widetilde{A}=\{\mathfrak u\in \beta X:A\in \mathfrak u\} $$

for all $A\subseteq X$. Easily, the sets are also closed, so the space $\beta X$ is zero-dimensional. In fact, $\beta X$ is compact, Hausdorff, extremally disconnected (the closure of any open set is open), and the largest compactification of the discrete space X. This means that X is dense in $\beta X$ and every (trivially continuous) map h of X into any compact Hausdorff space Y uniquely extends to a continuous map $\widetilde{h}$ of $\beta X$ into Y:

The largest compactification of Tychonoff spaces was discovered independently by Čech [7] and Stone [8]; then Wallman [9] did the same for $T_1$ spaces (by using ultrafilters on lattices of closed sets); see [5, 10, 11] for more information.

The ultrafilter extensions of unary maps F and relations R are exactly $\widetilde{F}$ and $\widetilde{R}$ (for $F:X\rightarrow X$ let $Y=\beta X$); thus in the unary case the procedure gives classical objects known in 30s. As for mappings and relations of greater arities, several instances of their ultrafilter extensions were discovered only in 60s.

Studying ultraproducts, Kochen [12] and Frayne et al. [13] considered a “multiplication” of ultrafilters, which actually is the ultrafilter extension of the n-ary operation of taking n-tuples. They shown that the successive iteration of ultrapowers by ultrafilters $\mathfrak u_1,\ldots ,\mathfrak u_n$ is isomorphic to a single ultrapower by their “product”. This has leaded to the general construction of iterated ultrapowers, invented by Gaifman and elaborated by Kunen, which has become common in model theory and set theory (see [14, 15]).

Ultrafilter extensions of semigroups appeared in 60s as subspaces of function spaces; the first explicit construction of the ultrafilter extension of a group is due to Ellis [16]. In 70s Galvin and Glazer applied them to give an easy proof of what now known as Hindman’s Finite Sums Theorem; the key idea was to use idempotent ultrafilters. The method was developed then by Blass, van Douwen, Hindman, Protasov, Strauss, and many others, and gave numerous Ramsey-theoretic applications in number theory, algebra, topological dynamics, and ergodic theory. The book [5] is a comprehensive treatise of this area, with an historical information. This technique was applied also for obtaining analogous results for certain non-associative algebras (see [17, 18]).

Ultrafilter extensions of arbitrary n-ary maps have been introduced independently by Goranko [1] and Saveliev [3, 4]. For $F:X_1\times \ldots \times X_n\rightarrow Y$, the extended map $\widetilde{F}:\beta X_1\times \ldots \times \beta X_n\rightarrow \beta Y$ is defined by letting

$$\begin{aligned}\begin{gathered} \widetilde{F}(\mathfrak u_1,\ldots ,\mathfrak u_n)= \\ \bigl \{A\subseteq Y: \{x_1\in X_1: \ldots \{x_n\in X_n: F(x_1,\ldots ,x_n)\in A \}\in \mathfrak u_n \ldots \}\in \mathfrak u_1 \bigr \}. \end{gathered}\end{aligned}$$

One can simplify this cumbersome notation by introducing ultrafilter quantifiers: let $(\forall ^{\,\mathfrak u}x)\,\varphi (x,\ldots )$ means $\{x:\varphi (x,\ldots )\}\in \mathfrak u$. In fact, this is a second-order quantifier: $(\forall ^{\,\mathfrak u}x)$ is equivalent to $(\forall A\in \mathfrak u)(\exists x\in A)$, and also (since $\mathfrak u$ is ultra) to $(\exists A\in \mathfrak u)(\forall x\in A)$. Such quantifiers are self-dual, i.e. $\forall ^{\,\mathfrak u}$ and $\exists ^{\,\mathfrak u}$ coincide, and generally do not commute with each other, i.e. $(\forall ^{\,\mathfrak u}x)(\forall ^{\,\mathfrak v}y)$ and $(\forall ^{\,\mathfrak v}y)(\forall ^{\,\mathfrak u}x)$ are not equivalent. Then the definition above is rewritten as follows:

$$\begin{aligned} \widetilde{F}(\mathfrak u_1,\ldots ,\mathfrak u_n)= \bigl \{A\subseteq Y: (\forall ^{\,\mathfrak u_1}x_1) \ldots (\forall ^{\,\mathfrak u_n}x_n)\; F(x_1,\ldots ,x_n)\in A \bigr \}. \end{aligned}$$

The map $\widetilde{F}$ can be also described as the composition of the ultrafilter extension of taking n-tuples, which maps $\beta X_1\times \ldots \times \beta X_n$ into $\beta (X_1\times \ldots \times X_n)$, and the continuous extension of F considered as a unary map, which maps $\beta (X_1\times \ldots \times X_n)$ into $\beta Y$.

One type of ultrafilter extensions of relations goes back to a seminal paper by Jónsson and Tarski [2] where they have been appeared implicitly, in terms of representations of Boolean algebras with operators. For binary relations, their representation theory was rediscovered in modal logic by Lemmon [19] who credited much of this work to Scott, see footnote 6 on p. 204 (see also [20]). Goldblatt and Thomason [21] used this to characterize modal definability (where Sect. 2 was entirely due to Goldblatt); the term “ultrafilter extension” has been introduced probably in the subsequent work by van Benthem [22] (for modal definability see also [23, 24]). Later Goldblatt [25] generalized the extension to n-ary relations.

Let us give an equivalent formulation: for $R\subseteq X_1\times \ldots \times X_n$, the extended relation $R^*\subseteq \beta X_1\times \ldots \times \beta X_n$ is defined by letting

$$\begin{aligned}\begin{gathered} R^*(\mathfrak u_1,\ldots ,\mathfrak u_n) \;\;\text {iff}\;\; \\ (\forall A_1\in \mathfrak u_1) \ldots (\forall A_n\in \mathfrak u_n) (\exists x_1\in A_1) \ldots (\exists x_n\in A_n)\; R(x_1,\ldots ,x_n). \end{gathered}\end{aligned}$$

Another type of ultrafilter extensions of n-ary relations has been recently discovered in [3, 4]:

$$\begin{aligned}\begin{gathered} \widetilde{R}(\mathfrak u_1,\ldots ,\mathfrak u_n) \;\;\text {iff}\;\; \\ \bigl \{x_1\in X_1: \ldots \{x_n\in X_n: R(x_1,\ldots ,x_n) \}\in \mathfrak u_n \ldots \bigr \}\in \mathfrak u_1, \end{gathered}\end{aligned}$$

or rewritting this via ultrafilter quantifiers,

$$\begin{aligned} \widetilde{R}(\mathfrak u_1,\ldots ,\mathfrak u_n) \;\;\text {iff}\;\; (\forall ^{\,\mathfrak u_1}x_1) \ldots (\forall ^{\,\mathfrak u_n}x_n)\; R(x_1,\ldots ,x_n). \end{aligned}$$

Or else, by decoding ultrafilter quantifiers, this can be rewritten by

$$\begin{aligned}\begin{gathered} \widetilde{R}(\mathfrak u_1,\ldots ,\mathfrak u_n) \;\;\text {iff}\;\; \\ (\forall A_1\in \mathfrak u_1) (\exists x_1\in A_1) \ldots (\forall A_n\in \mathfrak u_n) (\exists x_n\in A_n)\; R(x_1,\ldots ,x_n), \end{gathered}\end{aligned}$$

whence it is clear that $\widetilde{R}\subseteq R^*$. For unary R both extensions coincide with the basic open set given by R. If R is functional then $R^*$ (but not $\widetilde{R}$) coincides with the above-defined extension of R as a map. An easy instance of $\,\widetilde{\;}\;$-extensions (where R are linear orders) is studied in [26].

A systematic comparative study of both extensions (for binary R) is undertaken in [6]. In particular, there is shown that the ${}^*\,$- and the $\,\widetilde{\;}\;$-extensions have a dual character w.r.t. relation-algebraic operations: the former commutes with composition and inversion but not Boolean operations except for union, while the latter commutes with all Boolean operations but neither composition nor inversion. Also [6] contains topological characterizations of $\widetilde{R}$ and $R^*$ in terms of appropriate closure operations and in terms of Vietoris-type topologies (regarding R as multi-valued maps).

Ultrafilter extensions of arbitrary first-order models were considered for the first time independently in [1] with ${}^*\,$-extensions of relations, and in [3] with their $\,\widetilde{\;}\;$-extensions. We shall denote them by $\mathfrak A^*$ and $\widetilde{\,\mathfrak A\,}$ resp. Thus for a model $\mathfrak A=(X,F,\ldots ,R,\ldots )$ we let

$$\begin{aligned} \mathfrak A^*=(\beta X,\widetilde{F},\ldots ,R^*,\ldots ) \;\;\text { and }\;\; \widetilde{\,\mathfrak A\,}=(\beta X,\widetilde{F},\ldots ,\widetilde{R},\ldots ). \end{aligned}$$

The following is the main result of [1]:

FormalPara Theorem 1

If h is a homomorphism between models $\mathfrak A$ and $\mathfrak B$, then the continuous extension $\widetilde{h}$ is a homomorphism between $\mathfrak A^*$ and $\mathfrak B^*$:

A full analog of Theorem 1 for the $\,\widetilde{\;}\;$-extensions has been appeared in [3] (called the First Extension Theorem in [4]):

FormalPara Theorem 2

If h is a homomorphism between models $\mathfrak A$ and $\mathfrak B$, then the continuous extension $\widetilde{h}$ is a homomorphism between $\widetilde{\,\mathfrak A\,}$ and $\widetilde{\,\mathfrak B\,}$:

Moreover, both theorems remain true for embeddings and some other model-theoretic interrelations (see [1, 3, 4]).

Theorem 2 is actually is a partial case of a much stronger result of [3] (called the Second Extension Theorem in [4]). To formulate this, we need the following concepts (introduced in [3]).

Let $X_1,\ldots ,X_n,Y$ be topological spaces, and let $A_1\subseteq X_1,\ldots ,A_{n-1}\subseteq X_{n-1}$. An n-ary function $F:X_1\times \ldots \times X_n\rightarrow Y$ is right continuous w.r.t. $A_1,\ldots ,A_{n-1}$ iff for each i, $1\leqslant i\leqslant n$, and every $a_1\in A_1,\ldots ,a_{i-1}\in A_{i-1}$ and $x_{i+1}\in X_{i+1},\ldots ,x_n\in X_n$, the map

$$ x\mapsto F(a_1,\ldots ,a_{i-1},x,x_{i+1},\ldots ,x_n) $$

of $X_i$ into Y is continuous. An n-ary relation $R\subseteq X_1\times \ldots \times X_n$ is right open (right closed, etc.) w.r.t. $A_1,\ldots ,A_{n-1}$ iff for each i, $1\leqslant i\leqslant n$, and every $a_1\in A_1,\ldots ,a_{i-1}\in A_{i-1}$ and $x_{i+1}\in X_{i+1},\ldots ,x_n\in X_n$, the set

$$ \bigl \{x\in X_i: R(a_1,\ldots ,a_{i-1},x,x_{i+1},\ldots ,x_n) \bigr \} $$

is open (closed, etc.) in $X_i$.

Theorem 3 [3, 4] characterizes topological properties of $\,\widetilde{\;}\;$-extensions, it is a base of Theorem 4 (the Second Extension Theorem of [4]).

FormalPara Theorem 3

Let $\mathfrak A$ be a model. In the extension $\widetilde{\,\mathfrak A\,}$, all operations are right continuous and all relations right clopen w.r.t. the universe of $\mathfrak A$.

FormalPara Theorem 4

Let $\mathfrak A$ and $\mathfrak C$ be two models, h a homomorphism of $\mathfrak A$ into $\mathfrak C$, and let $\mathfrak C$ carry a compact Hausdorff topology in which all operations are right continuous and all relations are right closed w.r.t. the image of the universe of $\mathfrak A$ under h. Then $\widetilde{\,h\,}$ is a homomorphism of $\widetilde{\,\mathfrak A\,}$ into $\mathfrak C$:

Theorem 2 (for homomorphisms) easily follows: take $\widetilde{\,\mathfrak B}\,$ as $\mathfrak C$. The meaning of Theorem 4 is that it generalizes the classical Čech–Stone result to the case when the underlying discrete space X carries an arbitrary first-order structure.

A natural question is whether ${}^*\,$-extensions also canonical in a similar sense. The answer is positive; two following theorems are counterparts of Theorems 3 and 4 resp. (essentially both have been proved in [6]).

FormalPara Theorem 5

Let $\mathfrak A$ be a model. In the extension $\mathfrak A^*$, all relations are closed (and all operations are right continuous w.r.t. the universe of $\mathfrak A$).

FormalPara Theorem 6

Let $\mathfrak A$ and $\mathfrak C$ be two models, h a homomorphism of $\mathfrak A$ into $\mathfrak C$, and let $\mathfrak C$ carry a compact Hausdorff topology in which all operations are right continuous w.r.t. the image of the universe of $\mathfrak A$ under h, and all relations are closed. Then $\widetilde{\,h\,}$ is a homomorphism of $\mathfrak A^*$ into $\mathfrak C$.

Similarly, Theorem 1 (for homomorphisms) follows from Theorem 6. The latter also generalizes the Čech–Stone result for discrete spaces to discrete models but with a narrow class of target models $\mathfrak C$: having relations rather closed than right closed in Theorem 4.

2. The immediate purpose of this section is to provide a uniform approach to both types of extensions. This approach will lead us to certain structures, called here generalized models, which generalize ultrafilter extensions of each of the two types.

First we shall show that the ${}^*\,$-extension can be described in terms of the basic (cl)open sets and the continuous extension of maps. For this, let us consider the continuous extension of the continuous extension operation itself. To make notation easier, denote by ${\mathop {\mathrm {ext}}\nolimits }$ the operation of continuous extension of maps; i.e. ${\mathop {\mathrm {ext}}\nolimits } (f)$ is another notation for $\widetilde{f}$:

$$ {\mathop {\mathrm {ext}}\nolimits } (f)=\widetilde{f}. $$

So if we consider maps of X into Y, then ${\mathop {\mathrm {ext}}\nolimits }$ is a map of $Y^X$ into $C(\beta X,\beta Y)$. Since $C(\beta X,\beta Y)$ with the standard (i.e. pointwise convergence) topology is a compact Hausdorff space, ${\mathop {\mathrm {ext}}\nolimits }$ continuously extends to the map $\widetilde{\mathop {\mathrm {ext}}\nolimits }$ of $\beta (Y^X)$ into this space:

The extended map $\widetilde{\mathop {\mathrm {ext}}\nolimits }$ is surjective and non-injective.

FormalPara Lemma 1

Let  $R\subseteq Y^X$. Then $\widetilde{\mathop {\mathrm {ext}}\nolimits }$ maps the closure of R in the space $\beta (Y^X)$ onto the closure of R in the space $C(\beta X,\beta Y)$:

$$ \bigl \{\widetilde{\mathop {\mathrm {ext}}\nolimits } (\mathfrak f): \mathfrak f\in {\mathop {\mathrm {cl\,}}\nolimits } _{\beta (Y^X)}R\bigr \}= {\mathop {\mathrm {cl\,}}\nolimits } _{C(\beta X,\beta Y)}R. $$

For our purpose, let $X=n$. Then $\beta X=n$ and $C(\beta X,\beta Y)$ is $(\beta Y)^n$, which can be identified with $\beta Y\times \ldots \times \beta Y$ (n times). Now the required description of the ${}^*\,$-extension follows from Theorem 5:

FormalPara Theorem 7

Let $R\subseteq X\times \ldots \times X$. Then $R^*\subseteq \beta X\times \ldots \times \beta X$ is (identified with) the image of ${\mathop {\mathrm {cl\,}}\nolimits } _{\beta (X^n)}R$ under $\widetilde{\mathop {\mathrm {ext}}\nolimits }$.

Using ultrafilters over maps leads to the following concept. Given a language, we define a generalized (or ultrafilter) interpretation (the term is ad hoc) as a map $\imath$ that takes each n-ary functional symbol F to an ultrafilter over the set of n-ary operations on X, and each n-ary predicate symbol R to an ultrafilter over the set of n-ary relations on X; let also v be an ultrafilter valuation of variables, i.e. a valuation which takes each variable x to an ultrafilter over a given set X:

$$\begin{aligned} v(x)\in \beta X, \quad \imath (F)\in \beta (X^{X\times \ldots \times X}), \quad \imath (R)\in \beta \,\mathcal {P}(X\times \ldots \times X). \end{aligned}$$

The set $(\beta X,\imath (F),\ldots ,\imath (R),\ldots )$ is a generalized model. Now we are going to define the satisfiability relation in generalized models, which will be denoted by the symbol .

First, given an interpretation $\imath$ of non-logical symbols, we expand any valuation v of variables to the map $v_\imath$ defined on all terms as follows. Let ${\mathop {\mathrm {app}}\nolimits } :X_1\times \ldots \times X_n\times Y^{X_1\times \ldots \times X_n}\rightarrow Y$ be the application operation:

$$ {\mathop {\mathrm {app}}\nolimits } (a_1,\ldots ,a_n,f)=f(a_1,\ldots ,a_n). $$

Extend it to the map $\widetilde{\mathop {\mathrm {app}}\nolimits } : \beta X_1\times \ldots \times \beta X_n\times \beta (Y^{X_1\times \ldots \times X_n})\rightarrow \beta Y$ right continuous w.r.t. the principal ultrafilters, in the usual way:

Let $v_\imath$ coincide with v on variables, and if $v_\imath$ has been already defined on terms $t_1,\ldots ,t_n$, we let

$$ v_\imath (F(t_1,\ldots ,t_n))= \widetilde{\mathop {\mathrm {app}}\nolimits } (v_\imath (t_1),\ldots ,v_\imath (t_n),\imath (F)). $$

Further, given a generalized model $\mathfrak A=(\beta X,\imath (F),\ldots ,\imath (R),\ldots )$, define the satisfiability in $\mathfrak A$ as follows. Let $\mathrm {in\,}\subseteq X_1\times \ldots \times X_n\times \mathcal {P}(X_1\times \ldots \times X_n)$ be the membership predicate:

$$ \mathrm {in\,}(a_1,\ldots ,a_n,R)\;\;\text {iff}\;\;(a_1,\ldots ,a_n)\in R. $$

Extend it to the relation $\widetilde{\mathrm {in\,}}\subseteq \beta X_1\times \ldots \times \beta X_n\times \beta \,\mathcal {P}(X_1\times \ldots \times X_n)$ right clopen w.r.t. principal ultrafilters. Let

If $R(t_1,\ldots ,t_n)$ is an atomic formula in which R is not the equality predicate, we let

(Equivalently, we could define the satisfiability of atomic formulas by identifying predicates with their characteristic functions and using the satisfiability of equalities of the resulting terms.) Finally, if $\varphi (t_1,\ldots ,t_n)$ is obtained by negation, conjunction, or quantification from formulas for which  has been already defined, we define in the standard way.

When needed, we shall use variants of notation commonly used for ordinary models and satisfiability, for the generalized ones. E.g. for a generalized model $\mathfrak {A}$ with the universe $\beta X$, a formula $\varphi (x_1,\ldots ,x_n)$, and elements $\mathfrak u_1,\ldots ,\mathfrak u_n$ of $\beta X$, the notation means that $\varphi$ is satisfied in $\mathfrak A$ under a valuation taking the variables $x_1,\ldots ,x_n$ to the ultrafilters $\mathfrak u_1,\ldots ,\mathfrak u_n$.

Generalized models actually generalize not all ordinary models but those that are ultrafilter extensions of some models. It is worth also pointing out that whenever a generalized interpretation is principal, i.e. all non-logical symbols are interpreted by principal ultrafilters, we naturally identify it with the obvious ordinary interpretation with the same universe $\beta X$; however, not every ordinary interpretation with the universe $\beta X$ is of this form. Precise relationships between generalized models, ordinary models, and ultrafilter extensions will be described in Theorems 9 and 10.

An ultrafilter valuation v is principal iff it takes any variable to a principal ultrafilter.

FormalPara Lemma 2

Let two generalized models  $\mathfrak {A}=(\beta X,\imath (F),\ldots ,\imath (R),\ldots )$ and $\mathfrak {B}=(\beta X,\jmath (F),\ldots ,\jmath (R),\ldots )$ have the same universe $\beta X$. If for all functional symbols F, predicate symbols R, variables $x_1,\ldots ,x_n$, and principal valuations v,

$$\begin{aligned} \widetilde{ {\mathop {\mathrm {app}}\nolimits } }(v(x_1),\ldots ,v(x_n),\imath (F))&= \widetilde{ {\mathop {\mathrm {app}}\nolimits } }(v(x_1),\ldots ,v(x_n),\jmath (F)), \\ \widetilde{\mathrm {in\,}}(v(x_1),\ldots ,v(x_n),\imath (R)) \;\,&\text {iff}\;\;\, \widetilde{\mathrm {in\,}}(v(x_1),\ldots ,v(x_n),\jmath (R)), \end{aligned}$$

then for all formulas $\varphi$, terms $t_1,\ldots ,t_n$, and valuations v,

FormalPara Corollary 1

Let  $\mathfrak {A}=(\beta X,\imath (F),\ldots ,\imath (R),\ldots )$ be a generalized model and $\mathfrak {B}=(\beta X,\jmath (F),\ldots ,\jmath (R),\ldots )$ the generalized model having the same universe $\beta X$ and such that $\jmath$ coincides with $\imath$ on functional symbols and for each predicate symbol R, $\jmath (R)$ is the principal ultrafilter given by

$$ \bigl \{ (a_1,\ldots ,a_n)\in X^n: \widetilde{\mathrm {in\,}}(a_1,\ldots , a_n,\imath (R)) \bigr \}. $$

Then for all valuations v, formulas $\varphi$, and terms $t_1,\ldots ,t_n$,

Let us say that an ultrafilter $\mathfrak f$ over functions is pseudo-principal iff $\widetilde{\mathop {\mathrm {app}}\nolimits }$ takes any tuple consisting of principal ultrafilters together with $\mathfrak f$ to a principal ultrafilter, i.e. for $\mathfrak f\in \beta (Y^{X_1\times \ldots \times X_n})$,

$$\begin{aligned} a_1\in X_1,\ldots ,a_n\in X_n \;\;\text {implies}\;\; \widetilde{\mathop {\mathrm {app}}\nolimits } (a_1,\ldots ,a_n,\mathfrak f)\in Y. \end{aligned}$$

Every principal $\mathfrak f$ is pseudo-principal, and there exist pseudo-principal ultrafilters that are not principal as well as ultrafilters that are not pseudo-principal. A generalized interpretation $\imath$ is pseudo-principal on functional symbols iff $\imath (F)$ is a pseudo-principal ultrafilter for each functional symbol F (and then, for each term t).

FormalPara Corollary 2

Let $\mathfrak {A}=(\beta X,\imath (F),\ldots ,\imath (R),\ldots )$ be a generalized model with $\imath$ pseudo-principal on functional symbols. Let $\mathfrak {B}=(\beta X,\jmath (F),\ldots ,\jmath (R),\ldots )$ be the generalized model having the same universe $\beta X$ and such that $\jmath$ coincides with $\imath$ on predicate symbols and for each functional symbol F, $\jmath (F)$ is the principal ultrafilter given by $f:X^n\rightarrow X$ defined by letting

$$ f(a_1,\ldots ,a_n)=\widetilde{ {\mathop {\mathrm {app}}\nolimits } }(a_1,\ldots ,a_n,\imath (F)). $$

Then for all valuations v, formulas $\varphi$, and terms $t_1,\ldots ,t_n$,

It follows that for any generalized model $\mathfrak {A}$ whose interpretation is pseudo-principal on functional symbols, by replacing its relations as in Corollary 1 and its operations as in Corollary 2, one obtains an ordinary model $\mathfrak {B}$ with the same universe such that for all formulas $\varphi$ and elements $\mathfrak u_1,\ldots ,\mathfrak u_n$ of the universe, iff .

We do not formulate this fact as a separate theorem since we shall be able to establish stronger facts soon. In Theorem 8, we shall establish that for any generalized model $\mathfrak A$, not only one with a pseudo-principal interpretation, one can construct a certain ordinary model $e(\mathfrak A)$ satisfying the same formulas; and then, in Theorem 9, that whenever $\mathfrak A$ has a pseudo-principal interpretation, $e(\mathfrak A)$ is nothing but the $\widetilde{\;\;}$-extension of some model. In fact, in the latter case, $e(\mathfrak A)$ coincides with $\mathfrak B$ from the previous paragraph.

Now we provide two operations, e and E, which turn generalized models into certain ordinary models that generalize ${}^*\,$- and $\,\widetilde{\;}\;$-extensions. Both operations are surjective and non-injective.

Define a map e on ultrafilters over functions to functions over ultrafilters,

$$\begin{aligned} e:\beta (Y^{X_1\times \ldots \times X_n})\rightarrow \beta Y^{\beta X_1\times \ldots \times \beta X_n}, \end{aligned}$$

by induction on n. For $n=1$, let e coincide with $\widetilde{\mathop {\mathrm {ext}}\nolimits }$. Assume that e has been already defined for n. First we identify $Y^{X_1\times X_2\times \ldots \times X_{n+1}}$ with $(Y^{X_2\times \ldots \times X_{n+1}})^{X_1}$ (by the so-called evaluation map, or carrying). Under this identification, each $\mathfrak f\in \beta (Y^{X_1\times X_2\times \ldots \times X_{n+1}})$ corresponds to a certain $\mathfrak f'\in \beta ((Y^{X_2\times \ldots \times X_{n+1}})^{X_1}).$ Now we define $e(\mathfrak f)$ by letting

$$ e(\mathfrak f)(\mathfrak u_1,\mathfrak u_2,\ldots ,\mathfrak u_{n+1})= e(e(\mathfrak f')(\mathfrak u_1))(\mathfrak u_2,\ldots ,\mathfrak u_{n+1}) $$

(since e has been already defined on $\mathfrak f'$ and $e(\mathfrak f')(\mathfrak u_1)$ by induction hypothesis).

Alternatively, we can define e as follows. Expand the domain of ${\mathop {\mathrm {ext}}\nolimits }$ by letting

$$ {\mathop {\mathrm {ext}}\nolimits } (f)=\widetilde{f}$$

for n-ary functions f with any n, not only unary ones. Thus, if we consider functions of $X_1\times \ldots \times X_n$ into Y, then ${\mathop {\mathrm {ext}}\nolimits }$ maps $Y^{X_1\times \ldots \times X_n}$ into $RC_{X_1,\ldots ,X_{n-1}}(\beta X_1\times \ldots \times \beta X_n,\beta Y)$, the set of all functions of $\beta X_1\times \ldots \times \beta X_n$ into $\beta Y$ that are right continuous w.r.t. $X_1,\ldots ,X_{n-1}$. It can be shown that the latter set forms a closed subspace in the compact Hausdorff space $\beta Y^{\beta X_1\times \ldots \times \beta X_n}$ of all functions of $\beta X_1\times \ldots \times \beta X_n$ into $\beta Y$ with the standard (i.e. pointwise convergence) topology, and hence, is compact Hausdorff too. Therefore, ${\mathop {\mathrm {ext}}\nolimits }$ continuously extends to the map $\widetilde{\mathop {\mathrm {ext}}\nolimits }$ of $\beta (Y^{X_1\times \ldots \times X_n})$ into it:

Now we can identify e with $\widetilde{\mathop {\mathrm {ext}}\nolimits }$ in this expanded meaning.

By identifying relations with their characteristic functions, we can also let that e takes ultrafilters over relations to relations over ultrafilters:

$$\begin{aligned} e:\beta \,\mathcal {P}(X_1\times \ldots \times X_n)\rightarrow \mathcal {P}(\beta X_1\times \ldots \times \beta X_n). \end{aligned}$$

In fact, e and $\widetilde{\mathop {\mathrm {app}}\nolimits }$ (or ) are expressed via each other:

FormalPara Lemma 3

For all  $\mathfrak f\in \beta (Y^{X_1\times \ldots \times X_n})$, $\mathfrak r\in \beta \,\mathcal {P}(X_1\times \ldots \times X_n)$, and  $\mathfrak u_1\in \beta X_1,\ldots ,\mathfrak u_n\in \beta X_n$,

In other words,

$$\begin{aligned} e(\mathfrak f)&= \bigl \{ (\mathfrak u_1,\ldots ,\mathfrak u_n,\mathfrak v)\in \beta X_1\times \ldots \times \beta X_n\times \beta Y: \widetilde{ {\mathop {\mathrm {app}}\nolimits } }(\mathfrak u_1,\ldots ,\mathfrak u_n,\mathfrak f)=\mathfrak v \bigr \}, \\ e(\mathfrak r)&= \bigl \{ (\mathfrak u_1,\ldots ,\mathfrak u_n)\in \beta X_1\times \ldots \times \beta X_n: \widetilde{\mathrm {in\,}}(\mathfrak u_1,\ldots ,\mathfrak u_n,\mathfrak r) \bigr \}. \end{aligned}$$

FormalPara Corollary 3

For all generalized models $\mathfrak A=(\beta X,\imath (F),\ldots ,\imath (R),\ldots )$ and valuations v,

For a generalized model $\mathfrak B=(\beta X,\mathfrak f,\ldots ,\mathfrak r,\ldots )$, let

$$ e(\mathfrak B)= (\beta X,e(\mathfrak f),\ldots ,e(\mathfrak r),\ldots ). $$

Note that $e(\mathfrak B)$ is an ordinary model.

FormalPara Theorem 8

If $\mathfrak A$ is a generalized model, then for all formulas $\varphi$ and elements $\mathfrak u_1,\ldots ,\mathfrak u_n$ of the universe of $\mathfrak A$,

Define a map E, with the same domain and range that the map e has, as follows: E and e coincide on $\beta (Y^{X_1\times \ldots \times X_n})$, and if $\mathfrak r\in \beta \,\mathcal {P}(X_1\times \ldots \times X_n)$ then

$$\begin{aligned} E(\mathfrak r)= \bigl \{ \widetilde{\mathop {\mathrm {ext}}\nolimits } (\mathfrak q): \mathfrak q\in \widetilde{\mathop {\mathrm {ext}}\nolimits } (\mathfrak r) \bigr \}. \end{aligned}$$

Here $\widetilde{\mathop {\mathrm {ext}}\nolimits } (\mathfrak r)$ is a clopen subset of $\beta (X_1\times \ldots \times X_n)$, if $\mathfrak q\in \widetilde{\mathop {\mathrm {ext}}\nolimits } (\mathfrak r)$ then $\widetilde{\mathop {\mathrm {ext}}\nolimits } (\mathfrak q)$ is identified with an element of the space $\beta X_1\times \ldots \times \beta X_n$ (as in Theorem 7), and the resulting $E(\mathfrak r)$ is closed in the space.

FormalPara Lemma 4

Let  $\mathfrak r\in \beta \,\mathcal {P}(X_1\times \ldots \times X_n)$. Then

$$\begin{aligned} e(\mathfrak r)=\widetilde{R} \;\;\text {and}\;\; E(\mathfrak r)=R^* \end{aligned}$$

for $R= e(\mathfrak r)\cap (X_1\times \ldots \times X_n)= E(\mathfrak r)\cap (X_1\times \ldots \times X_n)= \bigcap _{S\in \mathfrak {r}}\bigcup S.$

One may write up this R more explicitly:

$$\begin{aligned} R&= \bigl \{ (a_1,\ldots ,a_n)\in X_1\times \ldots \times X_n: (\forall S\in \mathfrak {r})\, (\exists Q\in S)\; Q(a_1,\ldots ,a_n) \bigr \}. \end{aligned}$$

For a generalized model $\mathfrak B=(\beta X,\mathfrak f,\ldots ,\mathfrak r,\ldots )$, let

$$\begin{aligned} E(\mathfrak B)= (\beta X,E(\mathfrak f),\ldots ,E(\mathfrak r),\ldots ). \end{aligned}$$

Then $E(\mathfrak B)$, like $e(\mathfrak B)$, is an ordinary model.

By Lemma 4, relations of the model $e(\mathfrak B)$ are $\widetilde{\;\;\,}$-extensions of some relations on X, while relations of the model $E(\mathfrak B)$ are ${}^*\,$-extensions of the same relations. Whether the whole models $e(\mathfrak B)$ and $E(\mathfrak B)$ are ultrafilter extensions of some models depends only on the (generalized) interpretation of functional symbols in $\mathfrak B$:

FormalPara Theorem 9

Let  $\mathfrak B$ be a generalized model with the universe $\beta X$. The following are equivalent:

• (i) $e(\mathfrak B)=\widetilde{\,\mathfrak A\,}$ for a model $\mathfrak A$ with the universe X,

• (ii) $E(\mathfrak B)=\mathfrak A^*$ for a model $\mathfrak A$ with the universe X,

• (iii) The interpretation in $\mathfrak B$ is pseudo-principal on functional symbols.

Moreover, the model $\mathfrak A$ in (i) and (ii) is the same.

Finally, we point out that the fact whether an ordinary model with the universe $\beta X$ is of form $e(\mathfrak B)$, and whether it is of form $E(\mathfrak B)$, for some generalized model $\mathfrak B$ (clearly, with the same universe $\beta X$) depends only on its topological properties:

FormalPara Theorem 10

Let  $\mathfrak A$ be a model with the universe $\beta X$. Then:

• (i) $\mathfrak A=e(\mathfrak B)$ for a generalized model $\mathfrak B$ iff in $\mathfrak A$ all operations are right continuous and all relations right clopen w.r.t. X,

• (ii) $\mathfrak A=E(\mathfrak B)$ for a generalized model $\mathfrak B$ iff in $\mathfrak A$ all operations are right continuous w.r.t. X and all relations closed.

Since by Theorem 9, e and E applied to generalized models with pseudo-principal interpretations give the $\widetilde{\;\;}$- and ${}^*$-extensions of ordinary models, Theorem 10 can be considered as a generalization of Theorems 3 and 5.

In conclusion, let us mention that various characterizations of both types of ultrafilter extensions lead to a spectrum of similar extensions as proposed at the end of [6]; so natural tasks are to study all of the spectrum as well as to isolate special features of the two canonical extensions among others.