# An introduction to continuous model theory

Bradd Hart  Department of Mathematics and Statistics, McMaster University,
1280 Main St., Hamilton ON, Canada L8S 4K1<EMAIL_ADDRESS>http://ms.mcmaster.ca/ bradd/

###### Abstract.

We present an introduction to modern continuous model theory with an emphasis
on its interactions with topics covered in this volume such as
$\mathrm{C}^{*}$-algebras and von Neumann algebras. The role of ultraproducts
is highlighted and expositions of definable sets, imaginaries, quantifier
elimination and separable categoricity are included.

###### Key words and phrases:

Continuous model theory, metric structures, Urysohn sphere,
$\mathrm{C}^{*}$-algebras

###### 2020 Mathematics Subject Classification:

03C66, 03C98, 46L05

The author was supported by the NSERC.

##  1\. Introduction

It is not a new idea to have more truth values than just true and false. For
example, Łukasiewicz and Tarski suggested a real-valued logic in the 1930’s
[38]. The modern understanding of continuous model theory has other
antecedents as well. Chang and Keisler wrote a book [15] in which they
consider a logic with truth values in arbitrary compact Hausdorff spaces. This
logic had many quantifiers and did not catch on; see Ben Yaacov [5] for
further commentary. Henson introduced positive bounded logic in [30], mostly
in the service of the model theory of normed vector spaces with additional
structure. Ben Yaacov introduced the very general setting of cats (short for
compact abstract theories) in [6] in order to capture expansions of first
order logic that would allow the seamless use of hyperimaginaries as
introduced in [31]; this line of research built on earlier work around
Robinson theories by Hrushovski, Pillay and others. In particular, it was
realized that Hausdorff cats interpreted a metric. Ben Yaacov, Berenstein,
Henson and Usvyatsov then introduced a logic for metric structures which is
the subject of this paper. This logic is first presented in [12], which
strangely was published after the de facto standard [10].

The history of the ultraproduct is very interesting and more colourful than
most model theorists are aware. A short history is contained in [41]. The
thumbnail sketch is that an ultraproduct-like construction in the operator
algebra context was introduced by Kaplansky and Wright in the early 1950’s.
Sakai also used an ultraproduct in the early 1960’s, again in the service of
operator algebras. McDuff’s systematic use of ultraproducts in her paper [39]
highlighted how important the construction had become in the operator algebra
world. In parallel, the seminal introduction of the ultraproduct in model
theory by Łoś [37] and its use by Robinson in the development of non-standard
analysis were key early moments in model theory. It does not seem that anyone
at that time saw anything more than a formal connection between the two uses
of ultraproducts. Keisler [34] provides a brief history on the model theory
side in which he gives the nod for a precursor to the ultraproduct to Skolem
and interestingly to Hewitt [33], who was working on rings of continuous
functions. Although there was prior work done by Krivine, Stern and others,
the first systematic connection between the analytic ultraproduct construction
and model theory, particularly for Banach spaces, was the work of Henson [30],
in which he also introduces his positive bounded logic. A general exposition
of this logic appears with Iovino in [32].

The ultraproduct plays a slightly different role in the development of
continuous model theory than it does in classical logic. While the connection
between the ultraproduct construction and the compactness theorem is the same
for both logics, it is the exploratory nature of the ultraproduct which is
different, by which we mean that there are classes of structures appearing in
analysis where an ultraproduct is used but without a formal language being
present. The fact that mathematicians are using ultraproducts in certain
settings "in the wild" often leads one to examine whether the class can in
fact be presented in a model theoretic framework. Examples relevant to this
volume where this has been done successfully include Banach spaces,
$\mathrm{C}^{*}$-algebras, tracial von Neumann algebras, and W∗-probability
spaces.

As we will see in Example 3.8, every classical elementary class can be seen as
a continuous elementary class. Continuous logic, however, is a _proper_
extension of classical first order logic. While there are a number of ways to
see this, here is one suggestion based on a Borel complexity argument due to
Farah, Toms and Törnquist. In [21], they show that the isomorphism relation on
the class of separable $\mathrm{C}^{*}$-algebras is turbulent and not Borel-
reducible to any class of countable classical structures (see their article
for the relevant definitions). Of course, the isomorphism relation for every
class of countable classical structures is Borel-reducible to itself, so the
isomorphism relation for the class of separable $\mathrm{C}^{*}$-algebras is
not equivalent to any class of countable classical structures. As we will see
in this article, the class of $\mathrm{C}^{*}$-algebras is an elementary class
(Example 5.18) and by this complexity argument, this class is not equivalent
to any classical elementary class.

We now give a brief outline of the paper. After a quick reminder of the basics
of ultrafilters in Section 2, we introduce the syntax and semantics of
continuous logic in Sections 3 and 4. Basic continuous model theory is then
developed in Section 5, where a generalized notion of formula is introduced.
As was indicated above, ultraproducts play a crucial role in continuous model
theory and the ultraproduct of metric structures is introduced in Section 6.
Section 7 introduces the notion of type in continuous model theory and the
type space is used to give another characterization of general formulas. A
critical section is Section 8, where definable sets are discussed and
contrasted with the notion of definable set from classical logic. Section 9
highlights the formulation of quantifier elimination in continuous logic and
gives several examples. In Section 10, imaginary elements in the continuous
setting are considered and the conceptual completeness theorem is stated in
this context. We end the article with a discussion of omitting types in
Section 11 and separable categoricity in Section 12.

Inevitably, there are topics that we left out. In particular, we do not
include a discussion of a proof system for continuous logic. This topic is
covered in [11] and is important for the topic of decidability in continuous
logic (see, for example, Section 3 of Goldbring’s paper in this volume).
Another topic not discussed here is stability theory in continuous logic; one
can find the basics of this theory in [10] and [12].

I’d like to thank Isaac Goldbring for our many discussions regarding this
article and for his patience as an editor.

##  2\. Preliminaries on ultrafilters and ultraproducts

Ultrafilters and ultraproducts will play an important role in continuous model
theory. We cover the requisite facts in this section.

######  Definition 2.1.

Suppose that $X$ is a set and $F\subset P(X)$, where $P(X)$ is the power set
of $X$.

  1. (1)

$F$ is a (proper) _filter_ on $X$ if:

    1. (a)

$\emptyset\not\in F$,

    2. (b)

$A,B\in F$ implies $A\cap B\in F$, and

    3. (c)

$A\subset B\subset X$ and $A\in F$ implies $B\in F$.

  2. (2)

$F$ is an _ultrafilter_ on $X$ if it is a filter on $X$ and, for every
$A\subset X$, either $A\in F$ or $X\setminus A\in F$ (but not both).

The following is an important characterization of ultrafilters. Note that we
are assuming the axiom of choice throughout this paper.

######  Exercise 2.2.

Suppose $F\subset P(X)$.

  1. (1)

$F$ is an ultrafilter on $X$ if and only if $F$ is a maximal (under inclusion)
filter on $X$.

  2. (2)

$F$ is contained in an ultrafilter on $X$ if and only if $F$ has the finite
intersection property, that is, for any finitely many $A_{1},\ldots,A_{n}\in
F$, $\bigcap_{i=1}^{n}A_{i}\neq\emptyset$.

######  Example 2.3.

  1. (1)

If $X$ is any infinite set and $F$ is the collection of co-finite subsets of
$X$, then $F$ is a filter on $X$, called the _Fréchet filter_ on $X$. Note
that the Fréchet filter is not an ultrafilter.

  2. (2)

If $X$ is any set, $a\in X$ is any element, and $F$ is the collection of
subsets of $X$ which contain $a$, then $F$ is an ultrafilter on $X$, called
the _principal ultrafilter on $X$ generated by $a$_.

######  Exercise 2.4.

If $X$ is an infinite set, then an ultrafilter on $X$ is non-principal if and
only if it contains the Fréchet filter on $X$. Consequently, non-principal
ultrafilters on $X$ exist.

The notion of an ultralimit will be important throughout this paper.

######  Exercise 2.5.

Suppose that $(r_{i}:i\in I)$ is a sequence of real numbers and
${\mathcal{U}}$ is an ultrafilter on $I$. Further suppose that there is a real
number $B$ such that $\\{i\in I:|r_{i}|<B\\}\in{\mathcal{U}}$. Prove that
there is a unique real number $r$ satisfying, for every $\epsilon>0$, that
$\\{i\in I:|r_{i}-r|<\epsilon\\}\in{\mathcal{U}}$.

######  Definition 2.6.

In the context of the previous exercise, we say that $r$ is the _ultralimit of
$(r_{i}:i\in I)$ along ${\mathcal{U}}$_, written $r=\lim_{\mathcal{U}}r_{i}$.

We now introduce the notion of the metric ultraproduct for bounded metric
spaces. Suppose that $(X_{i},d_{i})$ is an $I$-indexed family of metric spaces
that is _uniformly bounded_ , that is, there is some $B>0$ such that the
diameter of each $X_{i}$ is bounded by $B$ (meaning for all $i\in I$ and
$a,b\in X_{i}$, $d_{i}(a,b)\leq B$). Fix an ultrafilter ${\mathcal{U}}$ on
$I$. Set $X=\prod_{i\in I}X_{i}$ and define, for $\bar{a},\bar{b}\in X$,
$d(\bar{a},\bar{b})=\lim_{\mathcal{U}}d(a_{i},b_{i})$. It is easy to see that
$d$ is a pseudometric on $X$. We define the _ultraproduct of the family
$(X_{i},d_{i})$ with respect to ${\mathcal{U}}$_, denoted
$\prod_{\mathcal{U}}X_{i}$, to be the metric space obtained from $X$ by
quotienting by the pseudometric $d$. For $\bar{x}\in X$, we let
$[\bar{x}]_{\mathcal{U}}$ denote the equivalence class of $\bar{x}$ in the
quotient. If $X_{i}$ is some fixed $X$ for all $i\in I$, we write
$X^{\mathcal{U}}$ for the ultraproduct and call it the _ultrapower_ of $X$
with respect to ${\mathcal{U}}$. There is a natural isometric embedding of $X$
into $X^{\mathcal{U}}$, called the _diagonal embedding_ , which sends $x\in X$
to the equivalence class of the constant sequence $(x:i\in I)$.

######  Exercise 2.7.

  1. (1)

Suppose that $(X_{i}:i\in I)$ is a collection of _complete_ , uniformly
bounded metric spaces and ${\mathcal{U}}$ is an ultrafilter on $I$. Prove that
$\prod_{\mathcal{U}}X_{i}$ is complete.

  2. (2)

Suppose that $(X_{n}:n\in{\mathbf{N}})$ is a collection of uniformly bounded
metric spaces (which are not necessarily assumed to be complete) and
${\mathcal{U}}$ is a non-principal ultrafilter on ${\mathbf{N}}$. Prove that
$\prod_{\mathcal{U}}X_{n}$ is complete.

######  Exercise 2.8.

Suppose that $X$ is a compact bounded metric space. Show that for any index
set $I$ and ultrafilter ${\mathcal{U}}$ on $I$, the diagonal embedding of $X$
into $X^{\mathcal{U}}$ is surjective (and thus an isometry of metric spaces).

Throughout this article, we will be dealing with various metric spaces
equipped with additional structure. We highlight here a key point that will
come up when we have to deal with such additional structure. To keep things
simple, suppose we have a complete, bounded metric space $(X,d)$ and, in
addition, we have a unary function $f$ on $X$. We can naturally define the
product $X^{\mathbf{N}}$ with the $\sup$-metric and view $f$ as being defined
co-ordinatewise on $X^{\mathbf{N}}$. We ask: what constraints must there be on
$f$ if we wish to form an ultrapower of $(X,d,f)$ as a quotient of the product
structure? Notice in the classical case, there are no restrictions (one can
always form the discrete ultrapower). We claim that it is necessary and
sufficient that $f$ be uniformly continuous. Sufficiency is straightforward
and is left as an exercise to the reader. To verify necessity, suppose that
there is $\epsilon>0$ such that, for every $n\in{\mathbf{N}}$ (see the
footnote111We will adopt the convention that when $n\in{\mathbf{N}}$ is being
treated as a number and not an index then $n\neq 0$. This will avoid issues
with division by 0. on the use of ${\mathbf{N}}$ in this article), one can
find $a_{n},b_{n}\in X$ such that $d(a_{n},b_{n})<1/n$ and yet
$d(f(a_{n}),f(b_{n}))\geq\epsilon$. Set $\bar{a}=(a_{n}:n\in{\mathbf{N}})$ and
$\bar{b}=(b_{n}:n\in{\mathbf{N}})$. If ${\mathcal{U}}$ is a non-principal
ultrafilter on ${\mathbf{N}}$, then $\lim_{\mathcal{U}}d(a_{n},b_{n})=0$ and
so $[\bar{a}]_{\mathcal{U}}=[\bar{b}]_{\mathcal{U}}$ as elements of the
ultrapower $X^{\mathcal{U}}$. However,
$\lim_{\mathcal{U}}d(f(a_{n}),f(b_{n}))\geq\epsilon$ and so
$[f(\bar{a})]_{\mathcal{U}}\not=[f(\bar{b})]_{\mathcal{U}}$, where
$f(\bar{a})=(f(a_{n})\ :\ n\in{\mathbf{N}})$ and likewise for $f(\bar{b})$. It
follows that $f$ cannot be defined on the ultrapower as a quotient of the
product structure.

The conclusion we draw from the previous paragraph is that if we want to
extend an ultraproduct construction to additional structure on a metric space,
we are going to have to assume some form of uniform continuity. In fact, a
similar argument to the one just given shows that if one wants to construct an
ultraproduct of uniformly bounded metric spaces $(X_{n},d_{n})$ for
$n\in{\mathbf{N}}$ each of which is equipped with a uniformly continuous unary
function $f_{n}$, the uniform continuity must be uniform along the sequence of
structures, that is, for every $\epsilon>0$, there is $\delta>0$ so that for
any $n\in{\mathbf{N}}$ and any $a,b\in X_{n}$, if $d_{n}(a,b)<\delta$, then
$d_{n}(f_{n}(a),f_{n}(b))\leq\epsilon$ (see the discussion at the beginning of
Section 3 where we address the asymmetry in the above inequalities).

##  3\. Metric structures and languages

###  3.1. Continuous languages and their interpretation

We now introduce the structures we are interested in studying and the
languages of the intended logic at the same time. A _metric structure_
$\mathcal{M}$, the continuous analog of a classical structure, will be multi-
sorted. The language will have a collection of sorts $\mathfrak{S}$. For each
sort $S\in\mathfrak{S}$, the language specifies a positive real number
$B_{S}$. The intended interpretation of $S$ in a metric structure
$\mathcal{M}$ is a bounded, complete, non-empty metric space $S^{\mathcal{M}}$
whose diameter is at most $B_{S}$. There is also a relation symbol $d_{S}$ in
the language which is to be interpreted as the metric on the space
$S^{\mathcal{M}}$.

A language also contains a set of function symbols $\mathfrak{F}$ and relation
symbols $\mathfrak{R}$ (these are sometimes called predicate symbols in other
presentations). Each of these symbols comes with some additional information;
we first treat function symbols. If $f\in\mathfrak{F}$, then $f$ has a domain
and co-domain as specified by the language. The domain of $f$, denoted
$dom(f)$, is a product of sorts $S_{1}\times\cdots\times S_{n_{f}}$ for some
$n_{f}\in{\mathbf{N}}$, and the co-domain of $f$, denoted $cod(f)$, is a sort
$S_{f}$. In addition, the language specifies an increasing, continuous
function $\delta_{f}:[0,1]\rightarrow[0,1]$ satisfying
$\lim_{\epsilon\rightarrow 0^{+}}\delta_{f}(\epsilon)=0$; $\delta_{f}$ is
called the _uniform continuity modulus_ of $f$. The function $\delta_{f}$ is
specified by the language (and motivated by the discussion in the previous
section).

######  Comment 3.1.

It may seem strong to insist that the uniform continuity modulus above is a
continuous function. As it turns out, it always can be arranged:

######  Proposition 3.2.

[10, Proposition 2.10 and Remark 2.12] Let $F,G\colon X\rightarrow[0,1]$ be
such that

$(\forall\epsilon>0)(\exists\delta>0)(\forall x\in X)(F(x)<\delta\text{
implies }G(x)\leq\epsilon).$

Then there exists an increasing, continuous function
$\alpha\colon[0,1]\rightarrow[0,1]$ such that $\alpha(0)=0$ and such that, for
all $x\in X$, we have $G(x)\leq\alpha(F(x))$. In fact, one may choose $\alpha$
so that it only depends on the map $\epsilon\mapsto\delta$ and not on the
particular functions $F$ and $G$.

Proposition 3.2 is quite useful throughout continuous model theory. For
example, it is useful in expressing certain implications (which are otherwise
difficult to express given that continuous logic is a “positive” logic); see
[10, Section 7]. We shall have occasion to use this proposition in Section 8
below.

In a metric structure $\mathcal{M}$ for this language, the function symbol $f$
is interpreted as a uniformly continuous function

$f^{\mathcal{M}}:S_{1}^{\mathcal{M}}\times\ldots\times
S_{n_{f}}^{\mathcal{M}}\rightarrow S_{f}^{\mathcal{M}}$

where the uniform continuity of $f^{\mathcal{M}}$ is witnessed by
$\delta_{f}$, that is, for all $\epsilon>0$ and $a_{i},b_{i}\in
S_{i}^{\mathcal{M}}$ satisfying $d_{S_{i}}(a_{i},b_{i})<\delta_{f}(\epsilon)$
for all $i=1,\ldots,n$, we have

$d_{S_{f}}(f^{\mathcal{M}}(a_{1},\ldots,a_{n_{f}}),f^{\mathcal{M}}(b_{1},\ldots,b_{n_{f}}))\leq\epsilon.$

The careful reader will notice the asymmetry between strict inequality and
weak inequality in this definition of uniform continuity. The short
explanation for the asymmetry is that we want this definition to pass easily
through the ultraproduct construction. Nevertheless, the definition here is
equivalent to one where we have strict inequalities on both sides.

Constant symbols will be thought of as function symbols with an empty sequence
of sorts as domain and some sort as co-domain. The interpretation in a metric
structure will be a single element in the chosen co-domain.

For the relation symbols, if $R\in\mathfrak{R}$, the language specifies a
domain, denoted $dom(R)$, which is a product of sorts $S_{1}\times\cdots\times
S_{n_{R}}$ for some $n_{R}\in{\mathbf{N}}$. The language also provides a bound
$B_{R}>0$ and a uniform continuity modulus $\delta_{R}$. In a metric structure
$\mathcal{M}$ for this language, $R$ is interpreted as a uniformly continuous
function $R^{\mathcal{M}}:S_{1}^{\mathcal{M}}\times\ldots\times
S_{n_{R}}^{\mathcal{M}}\to[-B_{R},B_{R}]\subseteq\mathbb{R}$ with uniform
continuity witnessed by $\delta_{R}$ as above.

To summarize, a metric language ${\mathcal{L}}$ will contain:

  * •

a set of sorts $\mathfrak{S}$ together with, for every $S\in\mathfrak{S}$, a
relation symbol $d_{S}$ and number $B_{S}>0$,

  * •

a set of function symbols $\mathfrak{F}$ together with, for every
$f\in\mathfrak{F}$, a product of sorts $dom(f)$, a sort $cod(f)$, and a
uniform continuity modulus $\delta_{f}$, and

  * •

a set of relation symbols $\mathfrak{R}$ together with, for every
$R\in\mathfrak{R}$, a product of sorts $dom(R)$, a number $B_{R}>0$, and a
uniform continuity modulus $\delta_{R}$.

A metric structure $\mathcal{M}$ for ${\mathcal{L}}$ (also called an
${\mathcal{L}}$-structure) specifies the following:

  * •

for every sort $S\in\mathfrak{S}$, a complete non-empty metric space
$S^{\mathcal{M}}$, with metric $d_{S}^{\mathcal{M}}$ of diameter bounded by
$B_{S}$,

  * •

for every $f\in\mathfrak{F}$, a uniformly continuous function
$f^{\mathcal{M}}$ whose uniform continuity is witnessed by $\delta_{f}$ and
with domain $S_{1}^{\mathcal{M}}\times\cdots\times S_{n}^{\mathcal{M}}$ and
co-domain $S^{\mathcal{M}}$, where $dom(f)=S_{1}\times\ldots\times S_{n}$ and
$cod(f)=S$, and

  * •

for every $R\in\mathfrak{R}$, a real-valued, bounded, uniformly continuous
function $R^{\mathcal{M}}$ with uniform continuity modulus $\delta_{R}$,
domain $S_{1}^{\mathcal{M}}\times\cdots\times S_{n}^{\mathcal{M}}$, where
$dom(R)=S_{1}\times\ldots\times S_{n}$, and co-domain $[-B_{R},B_{R}]$.

For ${\mathcal{L}}$-structures $\mathcal{M}$ and $\mathcal{N}$, we say that
$\mathcal{N}$ is a _substructure_ of $\mathcal{M}$ if

  * •

for every $S\in\mathfrak{S}$, $S^{\mathcal{N}}$ is a closed subspace of
$S^{\mathcal{M}}$,

  * •

for every $f\in\mathfrak{F}$, $f^{\mathcal{N}}$ is the restriction of
$f^{\mathcal{M}}$ to $S_{1}^{\mathcal{N}}\times\ldots\times
S_{n}^{\mathcal{N}}$, where $dom(f)=S_{1}\times\ldots\times S_{n}$, and

  * •

for every $R\in\mathfrak{R}$, $R^{\mathcal{N}}$ is the restriction of
$R^{\mathcal{M}}$ to $S_{1}^{\mathcal{N}}\times\ldots\times
S_{n}^{\mathcal{N}}$, where $dom(R)=S_{1}\times\ldots\times S_{n}$.

If ${\mathcal{L}}^{\prime}\subseteq{\mathcal{L}}$ are two languages and
$\mathcal{M}$ is an ${\mathcal{L}}$-structure, then by
$\mathcal{M}\restriction{\mathcal{L}}^{\prime}$ we mean the
${\mathcal{L}}^{\prime}$-structure obtained from $\mathcal{M}$ by only
interpreting those sorts, relations and functions arising from
${\mathcal{L}}^{\prime}$. We call
$\mathcal{M}\restriction{\mathcal{L}}^{\prime}$ the _reduct_ of $\mathcal{M}$
to ${\mathcal{L}}^{\prime}$ and we refer to $\mathcal{M}$ as an _expansion_ of
$\mathcal{M}\restriction{\mathcal{L}}^{\prime}$ to ${\mathcal{L}}$.

We want to consider several categories of ${\mathcal{L}}$-structures. All of
these categories will have ${\mathcal{L}}$-structures themselves as objects;
the difference between these categories will be the morphisms. For now, we
will consider two choices for maps between two ${\mathcal{L}}$-structures,
$\rho:\mathcal{M}\rightarrow\mathcal{N}$, by which we mean a family of maps
$(\rho_{S}:S\in\mathfrak{S})$ such that $\rho_{S}:S^{\mathcal{M}}\rightarrow
S^{\mathcal{N}}$. Below, we will write $\bar{a}\in\mathcal{M}$ to mean that
$\bar{a}$ is a tuple from the union of the interpretations of the sorts of
$\mathcal{M}$ and by $\rho(\bar{a})$ we will mean $\rho_{S}^{\mathcal{M}}$
applied to the elements of the tuple $\bar{a}$ for the appropriate $S$’s.

  * •

$\rho$ is a _homomorphism_ if:

    * –

for all function symbols $f$ of ${\mathcal{L}}$ and appropriately sorted
$\bar{a}\in\mathcal{M}$, we have
$\rho(f^{\mathcal{M}}(\bar{a}))=f^{\mathcal{N}}(\rho(\bar{a}))$;

    * –

for all relation symbols $R$ in ${\mathcal{L}}$ and appropriately sorted
$\bar{a}\in\mathcal{M}$, we have $R^{\mathcal{M}}(\bar{a})\geq
R^{\mathcal{N}}(\rho(\bar{a}))$.

  * •

$\rho$ is an _embedding_ if it is a homomorphism which furthermore satisfies,
for all relation symbols $R$ in ${\mathcal{L}}$ and appropriately sorted
$\bar{a}\in\mathcal{M}$,
$R^{\mathcal{M}}(\bar{a})=R^{\mathcal{N}}(\rho(\bar{a}))$. Notice that if
$\rho$ is an embedding, then $\rho_{S}$ is an isometric embedding for all
sorts $S$ of ${\mathcal{L}}$.

In all categories we consider, $\rho$ is an _isomorphism_ if it is an
embedding and $\rho_{S}$ is surjective for all $S$. If
$\rho:\mathcal{M}\rightarrow\mathcal{N}$ is an embedding, then by
$\rho(\mathcal{M})$ we will mean the substructure of $\mathcal{N}$ induced on
the image of the maps $\rho_{S}$ for all sorts $S$.

###  3.2. Examples

######  Example 3.3.

A toy example of a metric structure is a bounded complete metric space. The
language has one sort and one binary relation symbol for the metric. There are
no uniform continuity requirements here.

A slightly more involved situation arises if one wants to consider an
_unbounded_ complete metric space $(X,d)$. While there is no canonical way to
deal with this situation, the following approach is helpful, particularly when
there is more structure as we will see later. Fix a basepoint $\star\in X$.
Introduce in the language sorts $S_{n}$ for $n\in{\mathbf{N}}$. $\\{a\in
X:d(a,\star)\leq n\\}$ is the intended interpretation of the sort $S_{n}$. The
metric on $S_{n}$ will just be the restriction of $d$ to this sort. For $m<n$,
we also introduce function symbols $i_{m,n}$ with domain $S_{m}$, co-domain
$S_{n}$, and the identity function for modulus of uniform continuity. The
intended interpretation of $i_{m,n}$ is the natural inclusion of $S_{m}$ into
$S_{n}$.

######  Example 3.4.

A particularly interesting bounded metric space from the model-theoretic
perspective is the Urysohn sphere $U$. In [42], Urysohn constructed a
separable complete $1$-bounded metric space which is both _universal_ , that
is, every other separable 1-bounded metric space isometrically embeds into
$U$, and _ultrahomogeneous_ , that is, if $A,B\subset U$ are finite and
$f:A\rightarrow B$ is an isometric bijection, then $f$ can be extended to an
automorphism of $U$. $U$ is the unique separable complete $1$-bounded metric
space which is both universal and ultrahomogeneous. Since $U$ is bounded, it
is automatically an example of a metric structure.

One way to build $U$ is via a Fraïssé-like construction using the class
$\mathcal{C}$ of finite metric spaces with rational distances at most 1. (To
see how Fraïssé constructions are done in the continuous setting, see
Vignati’s article in this volume.) There are only countably many objects in
$\mathcal{C}$ and so, besides bookkeeping, one is led to the following
problem: given $A,B,C\in\mathcal{C}$ with $A\subset B$ and $A\subset C$, how
can one amalgamate $B$ and $C$ over $A$? To do this, one needs to decide the
distance $d(b,c)$ for $b\in B\setminus A$ and $c\in C\setminus A$. We record
the following lemma, whose proof is left as an exercise.

######  Lemma 3.5.

Suppose that $A,B,C$ are all finite metric spaces with $A\subset B$ and
$A\subset C$ and $B$ and $C$ are extensions of $A$. Then $B$ and $C$ can be
amalgamated over $A$ to form the metric space $B\cup_{A}C$ with the following
properties:

  * •

the underlying set is $B\cup C$,

  * •

the metric extends the metric on both $B$ and $C$, and

  * •

the metric further satisfies

$d(b,c):=\min_{a\in A}(d(b,a)+d(a,c))$

for $b\in B\setminus A$ and $c\in C\setminus A$.

######  Exercise 3.6.

Prove Lemma 3.5.

Using Lemma 3.5, one can form a chain of finite metric spaces from
$\mathcal{C}$ in the style of a Fraïssé construction which yields a countable
metric space $U_{0}$ with the property that whenever $A,B\in\mathcal{C}$ are
such that $A\subset B$ and $A\subset U_{0}$, then there is a $B_{0}\subset
U_{0}$ with $A\subset B_{0}$ and an isometry $i:B\rightarrow B_{0}$ which is
the identity on $A$. A mildly tedious exercise shows that the completion $U$
of $U_{0}$ satisfies the defining properties of the Urysohn sphere.

######  Exercise 3.7.

Verify the claim made at the end of the previous example.

######  Example 3.8.

A classical (discrete) structure can be thought of as a metric structure as
follows. Suppose that $\mathcal{M}$ is a classical structure in a classical
language ${\mathcal{L}}$. Equip each sort of $\mathcal{M}$ with the discrete
metric (that is, $d(a,b)=1$ if $a\neq b$). Additionally, for each relation
symbol $R\in{\mathcal{L}}$, reinterpret $R$ by the function
$g_{R}=1-char(R^{M})$, where $char(R^{M})$ is the characteristic function of
$R^{M}$. Note that $\bar{a}\in R^{M}$ iff $g_{R}(\bar{a})=0$.222Although
arbitrary, the convention in continuous logic is that 0 represents true; see
section 4 for further discussion. Moreover, $g_{R}$ is uniformly continuous as
is the interpretation of every function symbol. For completeness, we should
specify that the identity function is the modulus of continuity for all
function and relation symbols. In this way, one can think of continuous logic
as an extension of classical logic.

######  Example 3.9.

Recall that a Hilbert space is a complex inner product space which is complete
with respect to the induced metric. We wish to capture the class of Hilbert
spaces as an example of a class of metric structures. Here is the language
${\mathcal{L}}_{HS}$ and standard interpretation we will work with:

  1. (1)

For each $n\in{\mathbf{N}}$, we have a sort $S_{n}$. The intended
interpretation of $S_{n}$ in a Hilbert space is the ball centered at $0$ of
radius $n$. On $S_{n}$, there is a metric symbol with bound $2n$ whose
intended interpretation is the metric induced by the inner product.

  2. (2)

For each $n\in{\mathbf{N}}$, we have a binary function symbol $+_{n}$ with
domain $S_{n}\times S_{n}$ and co-domain $S_{2n}$. The intended interpretation
for a Hilbert space is addition on the ball of radius $n$. The uniform
continuity modulus is $\epsilon\mapsto\epsilon/2$.

  3. (3)

For each $n\in{\mathbf{N}}$, we have a constant symbol $0_{n}$ in sort $S_{n}$
which will be interpreted as 0.

  4. (4)

For each $n\in{\mathbf{N}}$ and $\lambda\in\mathbf{C}$, there is a unary
function symbol $\lambda_{n}$ with domain $S_{n}$ and co-domain $S_{m}$, where
$m=\lceil|\lambda|\rceil$. The uniform continuity modulus can be taken to be
$\epsilon\mapsto\epsilon/m$ The intended interpretation is scalar
multiplication by $\lambda$.

  5. (5)

For each $m,n\in{\mathbf{N}}$ with $m<n$, we have unary function symbols
$i_{m,n}$ with domain $S_{m}$ and co-domain $S_{n}$. The intended
interpretation is the inclusion map from the ball of radius $m$ into the ball
of radius $n$ and the uniform continuity modulus is the identity function.

  6. (6)

For each $n\in{\mathbf{N}}$, we have two binary relation symbols
$Re(\langle\cdot,\cdot\rangle)_{n}$ and $Im(\langle\cdot,\cdot\rangle)_{n}$ on
$S_{n}$. The intended interpretation of these symbols is the restriction to
$S_{n}$ of the real and imaginary parts of the inner product. The bounds for
each of these symbols are $n^{2}$ and the moduli of uniform continuity can be
take to be $\epsilon\mapsto\epsilon/2n$.

If $H$ is a Hilbert space, then the ${\mathcal{L}}_{HS}$-structure just
described will be denoted by $D(H)$ and referred to as the _dissection of
$H$_. In practice, we will write formulas in this language which will omit the
subscripts when the intention is clear. We may also write the inner product
symbols without reference to the real and imaginary part if it is clear that
an equivalent formula can be written adhering to the above formalism.

One of the most important examples for the current volume is the class of
$\mathrm{C}^{*}$-algebras. Let us look at this class in detail.

######  Example 3.10.

Given a $\mathrm{C}^{*}$-algebra $A$, the natural metric on $A$ is that
induced by the operator norm. As in the case of Hilbert spaces treated in the
previous example, this metric is unbounded. Once again, we get around this
issue by introducing a series of sorts to represent operator norm balls of
various radii. As before, we fix sorts $S_{n}$ for each $n\in{\mathbf{N}}$
with the intended interpretation being the operator norm ball of radius $n$ in
$A$. The intended metric on each sort is just the restriction of the metric
induced by the operator norm to the given sort. The language will also have a
number of function symbols. Since we will be dissecting
$\mathrm{C}^{*}$-algebras, as in the case of Hilbert spaces, we will need to
consider the restriction of functions like addition and multiplication to each
sort and we need to connect the sorts via embedding maps. With that in mind,
we introduce the language ${\mathcal{L}}_{C^{*}}$ with its intended
interpretation:

  1. (1)

For each $n\in{\mathbf{N}}$, there are binary function symbols $+_{n}$ and
$\cdot_{n}$ with domain $S_{n}\times S_{n}$ and co-domains $S_{2n}$ and
$S_{n^{2}}$ respectively. The intended interpretation is the restriction of
addition and multiplication on $A$ to the operator norm ball of radius $n$.
The uniform continuity modulus for $+_{n}$ is $\epsilon\mapsto\epsilon/2$ and
for $\cdot_{n}$ is $\epsilon\mapsto\epsilon/2n$.

  2. (2)

For each $n\in{\mathbf{N}}$, there is a unary function symbol
$\cdot^{\ast_{n}}$ with domain and co-domain $S_{n}$. The intended
interpretation is the restriction of the adjoint to the operator norm ball of
radius $n$. The uniform continuity modulus is the identity function.

  3. (3)

For each $n\in{\mathbf{N}}$, there is a constant symbol $0_{n}$ in $S_{n}$.
The intended interpretation is 0.

  4. (4)

For each $\lambda\in\mathbf{C}$ and $n\in{\mathbf{N}}$, we have a unary
function symbol $\lambda_{n}$ with domain $S_{n}$ and co-domain $S_{m}$, where
$m=\lceil|\lambda|\rceil$. The uniform continuity modulus of this symbol is
$\epsilon\mapsto\epsilon/m$.

  5. (5)

For each $n\in{\mathbf{N}}$, the metric symbol on $S_{n}$, denoted $d_{n}$,
will be interpreted as $\|x-y\|$ for $x,y$ in the operator norm ball of $A$ of
radius $n$.

  6. (6)

For each $m,n\in{\mathbf{N}}$ with $m<n$, there is a unary function symbol
$i_{m,n}$ with domain $S_{m}$ and co-domain $S_{n}$. The intended
interpretation is the inclusion map between $S_{m}^{A}$ and $S_{n}^{A}$. The
uniform continuity modulus is the identity map.

Given a $\mathrm{C}^{*}$-algebra $A$, the ${\mathcal{L}}_{C^{*}}$-structure
considered above is denoted $D(A)$ and is called the _dissection of $A$_. It
is clear that if we start with $A$ and consider $D(A)$, we can then recover
$A$ from $D(A)$ (simply take the union of the sorts and piece together the
operations as given). Moreover, $D(A)\cong D(B)$ (as
${\mathcal{L}}_{C^{*}}$-structures) if and only if $A\cong B$ (as
$\mathrm{C}^{*}$-algebras).

We now address a subtle point. Suppose that we have a
${\mathcal{L}}_{C^{*}}$-substructure $\mathcal{M}\subseteq D(A)$ for some
$\mathrm{C}^{*}$-algebra $A$. Does $\mathcal{M}$ arise as $D(B)$ for some
subalgebra $B\subseteq A$? To be clear, it is easy to see that if one
considers the direct limit of the sorts $S_{n}^{\mathcal{M}}$ along the
embeddings arising from the maps $i_{m,n}$, we do indeed obtain a
$\mathrm{C}^{*}$-subalgebra $B$ of $A$ (the completeness of each individual
sort guarantees that the union is complete). What is in question is whether
each individual sort $S_{n}$ captures exactly the elements of $B$ which are of
operator norm at most $n$. In order to see that we can arrange for this to
happen, we need the following fact. The functional analytic argument that
underlies this fact can be found in [19, section 3.1 at the top of page 486].

######  Fact 3.11.

For any $n\in{\mathbf{N}}$, there are one-variable polynomials $q^{n}_{k}$
($k\in{\mathbf{N}}$) such that if $A$ is a $\mathrm{C}^{*}$-algebra and $a\in
A$ satisfies $\|a\|\leq n$, then $\|q_{k}^{n}(a)\|\leq 1$ for all
$k\in{\mathbf{N}}$. If moreover $\|a\|\leq 1$, then $q_{k}^{n}(a)\to a$ as
$k\to\infty$.

We henceforth assume that, for each $k,n\in\mathbb{N}$ we have added function
symbols $\mathbf{q^{n}_{k}}$ to the language ${\mathcal{L}}_{C^{*}}$ with
domain $S_{n}$ and co-domain $S_{1}$. The modulus of continuity can be taken
to be the modulus of continuity of the polynomial $q^{k}_{n}$ when restricted
to the operator norm ball of radius $n$. In the dissection of a
$\mathrm{C}^{*}$-algebra, we will interpret $\mathbf{q^{n}_{k}}$ by the value
of the corresponding polynomial (taking values in $S_{1}$). Since each
polynomial $q^{n}_{k}$ is naturally a composition of the functions in the
language of $\mathrm{C}^{*}$-algebras, there is some $m\geq n$ such that
$S_{m}$ will be the (naïve) co-domain of $q^{n}_{k}$ when restricted to
$S_{n}$. When $\mathbf{q^{n}_{k}}$ is interpreted in the dissection of a
$\mathrm{C}^{*}$-algebra, we have

$i_{1,m}(\mathbf{q^{n}_{k}}(x))=q^{n}_{k}(x)$

for all $x$ in sort $S_{n}$. The justification for adding these function
symbols is as follows.

Suppose that $\mathcal{M}$ and $B$ are as above and $\|a\|\leq 1$ for some
$a\in B$. Take $n\in{\mathbf{N}}$ for which $a\in S_{n}^{\mathcal{M}}$.
Consider $q^{n}_{k}$ for $k\in{\mathbf{N}}$ as in Fact 3.11. Then in $B$,
$q^{n}_{k}(a)$ tends to $a$ in operator norm. On the other hand, since the co-
domain of $\mathbf{q^{n}_{k}}$ is $S_{1}$,
$(\mathbf{q^{n}_{k}})^{\mathcal{M}}(a)$ converges to something in
$S_{1}^{\mathcal{M}}$, call it $b$. Since $i_{1,n}$ is an isometric embedding,
$i_{1,n}^{\mathcal{M}}(\mathbf{q^{n}_{k}}(a))$ converges to $a$ in
$S_{n}^{\mathcal{M}}$ and hence $i_{1,n}^{M}(b)=a$, which means that $a$ and
$b$ are identified in $B$. We conclude that $D(B)\cong M$.

The dissection functor $D$ is in fact an equivalence of categories from the
category of $\mathrm{C}^{*}$-algebras with homomorphisms as morphisms and
${\mathcal{L}}_{C^{*}}$-structures of the form $D(A)$ for
$\mathrm{C}^{*}$-algebras $A$, again with homomorphisms as morphisms. The
equivalence between these categories is actually stronger than this, but this
stronger statement will have to wait until we define ultraproducts of
structures.

##  4\. Formulas

###  4.1. Basic Formulas

We now introduce the syntax of formulas for continuous logic. Fix a continuous
language ${\mathcal{L}}$ with sorts $\mathfrak{S}$, function symbols
$\mathfrak{F}$, and relation symbols $\mathfrak{R}$.

For each sort $S\in\mathfrak{S}$, we introduce variables $x_{n}^{S}$ for
$n\in{\mathbf{N}}$. As in classical logic, we need to define terms before
formulas. Terms in ${\mathcal{L}}$, along with their domain, co-domain, and
associated uniform continuity modulus, are defined inductively as follows:

  1. (1)

If $x$ is a variable of sort $S$, then $x$ is a term. Its domain and co-domain
are $S$ and its uniform continuity modulus is the identity function.

  2. (2)

If $f\in\mathfrak{F}$ is a function symbol with domain
$S_{1}\times\ldots\times S_{n}$ and co-domain $S$ and
$\tau_{1},\ldots,\tau_{n}$ are terms with co-domains $S_{1},\ldots,S_{n}$
respectively, then $f(\tau_{1},\ldots,\tau_{n})$ is a term with co-domain $S$
and domain determined by composition. The uniform continuity modulus of this
term is also determined by composition; for instance, one can take

$\epsilon\mapsto\min\\{\delta_{1}(\delta_{f}(\epsilon)/2),\ldots,\delta_{n}((\delta_{f}(\epsilon)/2)\\},$

where $\delta_{f}$ is the uniform continuity modulus of $f$ and $\delta_{k}$
is the uniform continuity modulus of $\tau_{k}$ for every $k=1,\ldots,n$.

######  Exercise 4.1.

Verify that the function displayed at the end of item (2) above is indeed a
uniform continuity modulus for $f(\tau_{1},\ldots,\tau_{n})$.

The _basic formulas_ of ${\mathcal{L}}$ are now defined by induction. We use
the term basic formula because, as we will see later in this article, we will
want to introduce a more general notion of formula to accommodate the
approximate nature of continuous logic.333We hope there is no confusion with
this use of the term basic formula and its various uses in classical logic.
Each basic formula will have a domain, bound, and uniform continuity modulus
as is the case for relation symbols.

  1. (1)

Suppose that $R\in\mathfrak{R}$ has domain $S_{1}\times\ldots\times S_{n}$ and
bound $B_{R}$, and $\tau_{1},\ldots,\tau_{n}$ are terms with co-domains
$S_{1},\ldots,S_{n}$ respectively. Then $R(\tau_{1},\ldots,\tau_{n})$ is a
basic formula with bound $B_{R}$, and domain and uniform continuity modulus
determined by composition. In particular, since all the symbols for metrics on
the sorts are included in $\mathfrak{R}$, if $\tau_{1}$ and $\tau_{2}$ are
sorts with the same co-domain $S$, then $d_{S}(\tau_{1},\tau_{2})$ is a basic
formula.

  2. (2)

If $f:\mathbf{R}^{n}\rightarrow\mathbf{R}$ is a continuous function and
$\varphi_{1},\ldots,\varphi_{n}$ are basic formulas, then
$\psi:=f(\varphi_{1},\ldots,\varphi_{n})$ is also a basic formula. If
$B_{1},\ldots,B_{n}$ are the bounds of $\varphi_{1},\ldots,\varphi_{n}$
respectively, then the bound of $\psi$ is the minimum $B$ such that

$f(\prod_{i=1}^{n}[-B_{i},B_{i}])\subseteq[-B,B].$

The domain of $\psi$ is determined by composition. The uniform continuity
modulus of $\psi$ is also determined by composition from the uniform
continuity moduli of the $\varphi_{i}$’s and a fixed uniform continuity
modulus of $f$ restricted to $\prod_{i=1}^{n}[-B_{i},B_{i}]$.

  3. (3)

Suppose that $x$ is a variable and $\varphi$ is a formula. We can then form
two quantified basic formulas $\sup_{x}\varphi$ and $\inf_{x}\varphi$. The
bound and uniform continuity modulus of these formulas is the same as
$\varphi$. The domain is only effected by the possible removal of the sort
associated with $x$.

The basic formulas arising from the first clause are called _atomic formulas_.
Basic formulas arising from the first two clauses are called _quantifier-free_
basic formulas.

######  Comment 4.2.

In the second clause above, we have chosen to be very generous about the
functions - the connectives - we allow. It is convenient theoretically to
allow all continuous functions (which are actually uniformly continuous since
we are only really interested in their values on some hypercube in
$\mathbf{R}^{n}$). It is sometimes worthwhile to work with a smaller
collection of connectives. The expressive power of continuous logic would not
change if we used a collection of connectives which were dense in the set of
all continuous functions. For instance, we could restrict ourselves to using
only polynomials with rational coefficients as connectives. Other restricted
sets of connectives have been suggested (see [10, Section 6] for more
details). As we will see, it is the density character of the set of formulas
which matters the most in continuous logic and not the cardinality of the set
of formulas.

Another set of basic formulas to highlight are the _prenex_ formulas, which
are those basic formulas beginning with a block of quantifiers followed by a
quan-tifier-free basic formula. In a natural (pseudo)metric defined on the
space of all basic formulas (see Subsection 5.1), the prenex formulas are
dense. We will come back to prenex formulas in Subsection 7.2.

We now consider the interpretation of basic formulas in a metric structure.
Fix an ${\mathcal{L}}$-structure $\mathcal{M}$.

A term $\tau$ is interpreted in $\mathcal{M}$ by $\tau^{\mathcal{M}}$ exactly
as it would be in classical logic by following the inductive definition and
composing.

######  Exercise 4.3.

Verify that the domain, co-domain and uniform continuity modulus of $\tau$ as
known to the language are in fact the domain, co-domain and uniform continuity
modulus of $\tau^{\mathcal{M}}$.

The interpretation of basic formulas is not much more complicated. Suppose
that $\bar{a}=(a_{1},\ldots,a_{n})$ is a sequence of sorted elements of
$\mathcal{M}$ and the free variables $\bar{x}=(x_{1},\ldots,x_{n})$ of a basic
formula $\varphi$ are similarly sorted. We wish to define the interpretation
$\varphi^{\mathcal{M}}(\bar{a})$ inductively:

  1. (1)

If $\varphi:=R(\tau_{1},\ldots,\tau_{k})$ for terms
$\tau_{1},\ldots,\tau_{k}$, then

$\varphi^{\mathcal{M}}(\bar{a}):=R^{\mathcal{M}}(\tau_{1}^{\mathcal{M}}(\bar{a}),\ldots,\tau_{k}^{\mathcal{M}}(\bar{a})).$

  2. (2)

If $\varphi:=f(\psi_{1},\ldots,\psi_{k})$ for basic formulas
$\psi_{1},\ldots,\psi_{k}$ and a continuous real-valued function $f$, then

$\varphi^{\mathcal{M}}(\bar{a}):=f(\psi^{\mathcal{M}}_{1}(\bar{a}),\ldots,\psi^{\mathcal{M}}_{k}(\bar{a})).$

  3. (3)

If $\varphi:=\sup_{x}\psi$, then

$\varphi^{\mathcal{M}}(\bar{a}):=\sup\\{\psi^{\mathcal{M}}(b,\bar{a})\colon
b\in S^{\mathcal{M}}\\}$

where $S$ is the sort of $x$. Notice that this is well-defined since the co-
domain of $\psi^{\mathcal{M}}$ is bounded.

Similarly, if $\varphi:=\inf_{x}\psi$, then

$\varphi^{\mathcal{M}}(\bar{a}):=\inf\\{\psi^{\mathcal{M}}(b,\bar{a})\colon
b\in S^{\mathcal{M}}\\}$

where again $S$ is the sort of $x$.

######  Exercise 4.4.

Verify that in each case of the above definition, these formulas have bound,
domain and uniform continuity modulus known to the language.

###  4.2. Some examples of formulas

Since it takes some getting used to writing expressions in continuous logic,
let us look at some standard ways of expressing certain statements.

######  Example 4.5.

Suppose we have two terms $\tau(\bar{x})$ and $\sigma(\bar{x})$ with the same
co-domain. How do we assert that they are equal when they are interpreted? If
$d$ is the metric symbol on the sort of the common co-domain of the terms,
then the sentence $\sup_{\bar{x}}d(\tau(\bar{x}),\sigma(\bar{x}))$ evaluates
to $0$ in some metric structure $\mathcal{M}$ if and only if the functions
$\tau^{\mathcal{M}}$ and $\sigma^{\mathcal{M}}$ are equal.

######  Example 4.6.

We sometimes wish to assert that one formula is less than or equal to another
in value. We do this with the help of the truncated substraction function
$x\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ y:=\max\\{0,x-y\\}$. Note
that $\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ $ is a continuous function
from $\mathbb{R}^{2}$ to $\mathbb{R}$, hence may be used as a connective.
Suppose that $\varphi(\bar{x})$ and $\psi(\bar{x})$ are two formulas. Then the
sentence

$\sup_{\bar{x}}(\varphi(\bar{x})\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ \psi(\bar{x}))$

evaluates to $0$ in a structure $\mathcal{M}$ if and only if
$\varphi^{\mathcal{M}}\leq\psi^{\mathcal{M}}$ as functions.

######  Example 4.7.

Another useful thing to be able to write out is the isomorphism type of some
finite metric space. Suppose that $A=\\{a_{1},\ldots,a_{n}\\}$ is a finite
metric space with $n$ distinct elements and metric $\delta$. Set
$r_{ij}=\delta(a_{i},a_{j})$ for $1\leq i<j\leq n$. Consider the formula

$D_{A}(x_{1},\ldots,x_{n})=\max_{1\leq i<j\leq n}|d(x_{i},x_{j})-r_{ij}|,$

where $x_{1},\ldots,x_{n}$ are variables of sort $S$ and $d$ is the metric
symbol for that sort. Note that $\max$ is a continuous function (here of
$n(n-1)$ inputs) as is $a\mapsto|a-r|$, hence they may be used as connectives
in the formation of the formula $D_{A}$ above. If we have a structure
$\mathcal{M}$ with sort $S$ and $b_{1},\ldots,b_{n}\in S^{\mathcal{M}}$, then
$\varphi^{\mathcal{M}}(b_{1},\ldots,b_{n})=0$ if and only if the map
$a_{i}\mapsto b_{i}$ for $i=1,\ldots,n$ is an isometric embedding of $A$ into
$S^{\mathcal{M}}$.

##  5\. Basic Continuous Model Theory

###  5.1. Some terminology

Before defining a more general notion of formula, we need to introduce some
logical terminology which roughly parallels the classical case.

Fix a metric language ${\mathcal{L}}$. A sentence in ${\mathcal{L}}$ is an
${\mathcal{L}}$-formula with no free variables. The set of
${\mathcal{L}}$-sentences will be denoted $Sent({\mathcal{L}})$. A set of
sentences $\Gamma$ is satisfiable if there is an ${\mathcal{L}}$-structure
$\mathcal{M}$ so that $\varphi^{\mathcal{M}}=0$ 444The choice of 0 here is
somewhat arbitrary. If we were interested in whether a certain sentence
$\varphi$ evaluated to some real number $r$ then, we could equivalently ask if
the sentence $\varphi-r$ was satisfied.  for all $\varphi\in\Gamma$, in which
case we say that $\mathcal{M}$ _satisfies $\Gamma$_ and we write
$\mathcal{M}\models\Gamma$. When $\Gamma=\\{\varphi\\}$, we write
$\mathcal{M}\models\varphi$ instead of $\mathcal{M}\models\\{\varphi\\}$ and
say that $\mathcal{M}$ satisfies $\varphi$. We extend this notation by
writing, for $\Gamma$ a set of sentences and $\varphi$ a sentence,
$\Gamma\models\varphi$ to mean that whenever $\mathcal{M}\models\Gamma$, then
$\mathcal{M}\models\varphi$.

A set of satisfiable (${\mathcal{L}}$-)sentences $T$ is is called an _(
${\mathcal{L}}$)-theory_. We say that a class of ${\mathcal{L}}$-structures
$\mathcal{C}$ is _elementary_ (or _axiomatizable_) if there is an
${\mathcal{L}}$-theory $T$ such that $\mathcal{C}$ is the collection of models
of $T$.

For an ${\mathcal{L}}$-structure $\mathcal{M}$, consider the linear
_evaluation map_

$ev_{\mathcal{M}}\colon Sent({\mathcal{L}})\rightarrow\mathbf{R}\text{ defined
by }ev_{\mathcal{M}}(\varphi)=\varphi^{\mathcal{M}}.$

Notice that if $ev_{M}(\varphi)=r$, then $ev_{M}(\varphi-r)=0$, hence
$ev_{\mathcal{M}}$ is completely determined by its kernel. With this in mind,
it is convenient to define _the theory of $\mathcal{M}$_, $Th(\mathcal{M})$,
as the set of sentences $\varphi$ such that $\varphi^{\mathcal{M}}=0$. Notice
also that $ev_{\mathcal{M}}$ is more than linear: if
$\varphi_{1},\ldots,\varphi_{n}$ are ${\mathcal{L}}$-sentences and $f$ is a
continuous real-valued function on $\mathbf{R}^{n}$, then

$ev_{\mathcal{M}}(f(\varphi_{1},\ldots,\varphi_{n}))=f(ev_{\mathcal{M}}(\varphi_{1}),\ldots,ev_{\mathcal{M}}(\varphi_{n})).$

Two ${\mathcal{L}}$-structures $\mathcal{M}$ and $\mathcal{N}$ are
_elementarily equivalent_ , written $\mathcal{M}\equiv\mathcal{N}$, if
$Th(\mathcal{M})=Th(\mathcal{N})$. A set of sentences $\Gamma$ is _complete_
if it is satisfiable, and whenever $\mathcal{M}$ and $\mathcal{N}$ satisfy
$\Gamma$, then $\mathcal{M}\equiv\mathcal{N}$. Notice that for an
${\mathcal{L}}$-structure $\mathcal{M}$, $Th(\mathcal{M})$ is a complete
(${\mathcal{L}}$-)theory. If $\mathcal{N}$ is a substructure of $\mathcal{M}$,
then we say that $\mathcal{N}$ is an _elementary substructure_ of
$\mathcal{M}$, written $\mathcal{N}\preceq\mathcal{M}$, if whenever
$\varphi(\bar{x})$ is an ${\mathcal{L}}$-formula and $\bar{a}\in\mathcal{N}$
is a sequence sorted in the same manner as the variables $\bar{x}$, then
$\varphi^{\mathcal{N}}(\bar{a})=\varphi^{\mathcal{M}}(\bar{a})$. We write
$\mathcal{N}\prec\mathcal{M}$ if $\mathcal{N}\preceq\mathcal{M}$ and
$\mathcal{N}\neq\mathcal{M}$. If $\rho:\mathcal{M}\rightarrow\mathcal{N}$ is
an embedding, then it is an _elementary embedding_ if
$\rho(\mathcal{M})\preceq\mathcal{N}$.

We can now define another category of ${\mathcal{L}}$-structures. Given an
${\mathcal{L}}$-theory $T$, $Mod(T)$ is the category with models of $T$ as
objects and elementary embeddings as morphisms. If the theory $T$ is empty,
that is, the collection of objects is just the collection of all
${\mathcal{L}}$-structures, then we refer to this category as
$Str({\mathcal{L}})$.

###  5.2. General Notion of Formula

We now generalize the notion of basic formula. It is important to note that
this general notion of formula is relative to a background theory. The general
notion of formula follows from introducing the following semi-norm on the set
of basic formulas. Fix an ${\mathcal{L}}$-theory $T$ and a fixed set of
variables $\bar{x}$. Given a basic formula $\varphi(\bar{x})$, define
$\|\varphi(\bar{x})\|_{T}=\sup\\{|\varphi^{\mathcal{M}}(\bar{a})|\colon\bar{a}\in\mathcal{M},\mathcal{M}\models
T\\}$. Let $Form_{\bar{x}}(T,{\mathcal{L}})$ be the completion of the set of
basic ${\mathcal{L}}$-formulas in free variables $\bar{x}$ with respect to the
pseudometric induced by the semi-norm $\|\cdot\|_{T}$ (that is, the distance
between $\varphi$ and $\psi$ is $\|\varphi-\psi\|_{T}$). We say $\varphi$ and
$\psi$ are _$T$ -equivalent_ if $\|\varphi-\psi\|_{T}=0$. Thus,
$Form_{\bar{x}}(T)$ is obtained by first identifying $T$-equivalent formulae
and then completing the resulting metric space. Elements of
$Form_{\bar{x}}(T,{\mathcal{L}})$ will be called _$T$ -formulas_ and are
limits of basic formulas in the sense of the semi-norm $\|\cdot\|_{T}$. If
$T=\emptyset$, we will refer to elements of $Form(\emptyset,{\mathcal{L}})$
simply as _${\mathcal{L}}$ -formulas_. If $\varphi$ is a $T$-formula which is
the limit of basic formulas $\varphi_{n}$, then we can interpret $\varphi$ in
a model $\mathcal{M}$ of $T$ by setting
$\varphi^{\mathcal{M}}=\lim_{n}\varphi_{n}^{\mathcal{M}}$.

######  Exercise 5.1.

Verify that the definition of $\varphi^{\mathcal{M}}$ for $\varphi$ a
$T$-formula given above is independent of the choice of representative
sequence. Moreover, prove that for each $T$-formula $\varphi$, there is $B>0$
such that $\varphi^{\mathcal{M}}$ takes values in $[-B,B]$ for all models
$\mathcal{M}$ of $T$.

Notice that for a theory $T$, the collection of $T$-formulas is closed under
composition with continuous functions i.e. if $\varphi_{1},\ldots,\varphi_{n}$
are $T$-formulas and $f:\mathbf{R}^{n}\rightarrow\mathbf{R}$ is a continuous
function then $f(\varphi_{1},\ldots,\varphi_{n})$ is a $T$-formula. Moreover,
the set of $T$-formulas is closed under $\sup$ and $\inf$. That is, if
$\varphi(x,\bar{y})$ is a $T$-formula then so is $\sup_{x}\varphi(x,\bar{y})$
and $\inf_{x}\varphi(x,\bar{y})$.

######  Example 5.2.

Suppose that we have a theory $T$ and $T$-formulas $\varphi_{n}$ in variables
$\bar{x}$ with bounds $B_{n}$ for $n\in{\mathbf{N}}$. Then the following is a
$T$-formula in the sense just defined:

$\sum_{n\in{\mathbf{N}}}\frac{\varphi(\bar{x})}{B_{n}2^{n}}.$

It is not hard to see that all $T$-formulas can be realized as weighted sums
of basic formulas.

$Form_{\bar{x}}(T,{\mathcal{L}})$ has the structure of a real normed algebra:
it contains the constant functions and is closed under addition and
multiplication. It will be convenient to generalize this notion as follows.

######  Definition 5.3.

A _real algebra system $A$ of $T$-formulas_ consists of, for every sequence of
variables $\bar{x}$, a closed subalgebra $A_{\bar{x}}$ of
$Form_{\bar{x}}(T,{\mathcal{L}})$.

We have three particular cases of real algebra systems in mind.

######  Example 5.4.

  1. (1)

Suppose that ${\mathcal{L}}^{\prime}\subseteq{\mathcal{L}}$. Given a sequence
$\bar{x}$ of variables, define $A_{\bar{x}}$ to be the closure in
$Form_{\bar{x}}(T,{\mathcal{L}})$ of the set of basic
${\mathcal{L}}^{\prime}$-formulas. $A$ is then a real algebra system of
$T$-formulas.

  2. (2)

Given a sequence $\bar{x}$ of variables, let $A_{\bar{x}}$ be the closure in
$Form_{\bar{x}}(\emptyset,{\mathcal{L}})$ of the set of quantifier-free basic
${\mathcal{L}}$-formulas. Then $A$ is a real algebra system of
${\mathcal{L}}$-formulas whose elements are called _quantifier-free formulas_.

  3. (3)

Let $A_{\bar{x}}$ be the closure in $Form_{\bar{x}}(\emptyset,{\mathcal{L}})$
of the set of prenex formulas in ${\mathcal{L}}$ in the free variables
$\bar{x}$. Then $A$ is a real algebra system.

For a topological space $X$, we let $\chi(X)$ denote the _density character of
$X$_, namely the smallest cardinality of a dense subset of $X$. We will refer
to the _density character of a language ${\mathcal{L}}$ with respect to a
theory $T$_, denoted by $\chi(T,{\mathcal{L}})$, as

$\sum_{\bar{x}}\chi(Form_{\bar{x}}(T,{\mathcal{L}})),$

where the sup is over all tuples $\bar{x}$ of variables. If $T$ is the empty
theory, we will omit it from the notation and just write
$\chi({\mathcal{L}})$. If $\chi({\mathcal{L}})=\aleph_{0}$, we say that
${\mathcal{L}}$ is _separable_. We also define the density character of an
${\mathcal{L}}$-structure $\mathcal{M}$, denoted $\chi(\mathcal{M})$, to be

$\sup_{S\in\mathfrak{S}}\chi(S^{\mathcal{M}}).$

###  5.3. First model-theoretic results

######  Proposition 5.5 (Tarski-Vaught test).

Suppose that $\mathcal{N}\subseteq\mathcal{M}$. Then the following are
equivalent:

  1. (1)

$\mathcal{N}\preceq\mathcal{M}$.

  2. (2)

For all basic ${\mathcal{L}}$-formulas $\varphi(y,\bar{x})$ and all
$\bar{a}\in\mathcal{N}$,

$\inf\\{\varphi^{\mathcal{M}}(b,\bar{a})\colon
b\in\mathcal{N}\\}=\inf\\{\varphi^{\mathcal{M}}(b,\bar{a})\colon
b\in\mathcal{M}\\}.$

###### Proof.

(1) implies (2) by the definition of elementary substructure. For (2) implies
(1), we argue by induction on the formation of basic formulas. The interesting
case is that of an $\inf$ quantifier. Thus, suppose
$\varphi(\bar{x})=\inf_{y}\psi(y,\bar{x})$ and $\bar{a}\in\mathcal{N}$. By
induction, we always have
$\varphi^{\mathcal{N}}(\bar{a})\geq\varphi^{\mathcal{M}}(\bar{a})$. To prove
the reverse inequality, fix $\epsilon>0$ and take $b\in\mathcal{M}$ such that
$\psi^{\mathcal{M}}(b,\bar{a})<\varphi^{\mathcal{M}}(\bar{a})+\epsilon$. By
condition (2), we can find $b^{\prime}\in\mathcal{N}$ such that
$\psi^{\mathcal{M}}(b^{\prime},\bar{a})<\varphi^{\mathcal{M}}(\bar{a})+\epsilon$,
and so by induction and letting $\epsilon$ tend to 0, we have
$\varphi^{\mathcal{N}}(\bar{a})\leq\varphi^{\mathcal{M}}(\bar{a})$. ∎

######  Theorem 5.6 (Downward Löwenheim-Skolem).

Given $X\subseteq\mathcal{M}$, there is $\mathcal{N}\preceq\mathcal{M}$ such
that $X\subseteq N$ and $\chi(\mathcal{N})\leq\chi(X)+\chi({\mathcal{L}})$.

###### Proof.

We accomplish the creation of $\mathcal{N}$ by iteratively closing off in
order to satisfy the Tarski-Vaught test; we only sketch of the details. Fix a
set of formulas $\\{\varphi_{i}(y,\bar{x}_{i})\colon i\in I\\}$ which is dense
in
$Form(Th(\mathcal{M}),{\mathcal{L}}):=\bigcup_{\bar{x}}Form_{\bar{x}}(Th(\mathcal{M}),{\mathcal{L}})$
with $|I|=\chi({\mathcal{L}})$. We create an increasing sequence $(X_{n})$ of
subsets of $\mathcal{M}$ such that:

  1. (1)

$X_{0}=X$,

  2. (2)

for each $n\in{\mathbf{N}}$, $i\in I$, and $\bar{a}\in X_{n}$, there is a
sequence $(b_{n})$ contained in $X_{n+1}$ such that

$\textstyle{(\inf_{y}\varphi(y,\bar{a}))^{\mathcal{M}}=\inf\\{\varphi^{\mathcal{M}}(b_{n},\bar{a}):n\in{\mathbf{N}}\\}},$

and

  3. (3)

$\chi(X_{n})\leq\chi(X)+\chi({\mathcal{L}})$.

We let $N$ be the closure (in $M$) of the union of the $X_{n}$’s and leave it
as an exercise to the reader to check that $N$ is the universe of a
substructure $\mathcal{N}$ of $\mathcal{M}$ which is in fact an elementary
substructure of $\mathcal{M}$. ∎

######  Exercise 5.7.

Verify the claim made at the end of the previous proof.

######  Definition 5.8.

Fix an ${\mathcal{L}}$-structure $\mathcal{M}$ and a subset
$A\subseteq\mathcal{M}$. The language ${\mathcal{L}}_{A}$ is ${\mathcal{L}}$
together with a new constant symbol $c_{a}$ for every $a\in A$ (and where
$c_{a}$ has the same sort as $a$). $\mathcal{M}$ can be canonically expanded
to an ${\mathcal{L}}_{A}$-structure $\mathcal{M}_{A}$ by interpreting $c_{a}$
as $a$ for every $a\in A$.

We define two types of ${\mathcal{L}}_{M}$-theories (often referred to as
diagrams):

  1. (1)

The _atomic diagram_ of $\mathcal{M}$, denoted $Diag(\mathcal{M})$, is the set

$\\{\varphi\colon\varphi\text{ is an }\text{ an atomic
${\mathcal{L}}_{\mathcal{M}}$-sentence and
}\mathcal{M}_{\mathcal{M}}\models\varphi\\}.$

  2. (2)

The _elementary diagram_ of $\mathcal{M}$, $Elem(\mathcal{M})$, is the set

$\\{\varphi\colon\varphi\text{ is an }\text{ an basic
${\mathcal{L}}_{\mathcal{M}}$-sentence and
}\mathcal{M}_{\mathcal{M}}\models\varphi\\}.$

######  Proposition 5.9.

For ${\mathcal{L}}$-structures $\mathcal{M}$ and $\mathcal{N}$ we have that:

  1. (1)

$\mathcal{M}$ can be embedded into $\mathcal{N}$ if and only if $\mathcal{N}$
can be expanded to an ${\mathcal{L}}_{\mathcal{M}}$-structure which satisfies
the atomic diagram of $\mathcal{M}$.

  2. (2)

$\mathcal{M}$ can be elementarily embedded into $\mathcal{N}$ if and only if
$\mathcal{N}$ can be expanded to an ${\mathcal{L}}_{\mathcal{M}}$-structure
which satisfies the elementary diagram of $\mathcal{M}$.

###### Proof.

The proofs are similar so we will only prove (2). If
$f\colon\mathcal{M}\rightarrow\mathcal{N}$ is an elementary embedding, then by
interpreting $c_{m}$ in $\mathcal{N}$ by $f(m)$, it is straightforward to show
this expansion of $\mathcal{N}$ satisfies the elementary diagram of
$\mathcal{M}$. In the other direction, if $\tilde{\mathcal{N}}$ is an
${\mathcal{L}}_{\mathcal{M}}$ expansion of $\mathcal{N}$ which satisfies the
elementary diagram of $\mathcal{M}$, then define
$f:\mathcal{M}\rightarrow\mathcal{N}$ by $f(m)=c^{\mathcal{N}}_{m}$ for all
$m\in\mathcal{M}$. Again it is straightforward to show that this is an
elementary map. ∎

The following result is analogous to the classical result regarding unions of
chains.

######  Proposition 5.10.

The category of ${\mathcal{L}}$-structures with elementary embeddings as
morphisms has directed colimits. More precisely, given:

  1. (1)

a directed partial order $(P,<)$ and a family of ${\mathcal{L}}$-structures
$(\mathcal{M}_{i}\colon i\in P)$, and

  2. (2)

elementary maps $\rho_{ij}:\mathcal{M}_{i}\rightarrow\mathcal{M}_{j}$ for
every $i<j$ satisfying $\rho_{jk}\circ\rho_{ij}=\rho_{ik}$ whenever $i<j<k$,

then there is an ${\mathcal{L}}$-structure $\mathcal{N}$ and elementary maps
$\nu_{i}:\mathcal{M}_{i}\rightarrow\mathcal{N}$ such that

  1. (1)

$\nu_{i}=\nu_{j}\circ\rho_{ij}$ for $i<j$, and

  2. (2)

$\mathcal{N}$ is the closure of $\bigcup_{i\in P}\nu_{i}(\mathcal{M}_{i})$.

######  Exercise 5.11.

Prove the previous proposition.

###  5.4. Ehrenfeucht-Fraïssé games

We now introduce the continuous version of Ehrenfeucht-Fraïssé games which
provide a way of recognizing elementary equivalence. These games have been
useful in the study of theories of various operator algebras (see for example
[25, 28]).

Fix a set of basic ${\mathcal{L}}$-formulas $\Delta$ in the variables
$\bar{x}=(x_{i}\colon 1\leq i\leq n)$, as well as an $\epsilon>0$. Suppose
$\mathcal{M}$ and $\mathcal{N}$ are two ${\mathcal{L}}$-structures. We
describe a game, the $EF(\mathcal{M},\mathcal{N},\Delta,\epsilon)$-game,
between two players, Player I and Player II. The game has $n$ rounds. In the
ith round, Player I chooses either $a_{i}\in\mathcal{M}$ or
$b_{i}\in\mathcal{N}$ of whatever sort the variable $x_{i}$ belongs to and
then Player II replies with $b_{i}\in\mathcal{N}$ or $a_{i}\in\mathcal{M}$
respectively. After $n$ rounds, there are two sequences
$\bar{a}=(a_{1},\ldots,a_{n})$ and $\bar{b}=(b_{1},\ldots,b_{n})$. Player II
wins the game if for every $\varphi(\bar{x})\in\Delta$, we have

$|\varphi^{\mathcal{M}}(\bar{a})-\varphi^{\mathcal{N}}(\bar{b})|<\epsilon.$

######  Theorem 5.12.

For two ${\mathcal{L}}$-structures $\mathcal{M}$ and $\mathcal{N}$, the
following are equivalent:

  1. (1)

$\mathcal{M}\equiv\mathcal{N}$.

  2. (2)

For every finite set $\Delta$ of atomic ${\mathcal{L}}$-formulas and every
$\epsilon>0$, Player II has a winning strategy for the
$EF(\mathcal{M},\mathcal{N},\Delta,\epsilon)$-game.

  3. (3)

For every finite set $\Delta$ of basic ${\mathcal{L}}$-formulas and every
$\epsilon>0$, Player II has a winning strategy for the
$EF(\mathcal{M},\mathcal{N},\Delta,\epsilon)$-game.

######  Exercise 5.13.

Prove Theorem 5.12. (Hint: For the dirction (3) implies (1), proceed by
induction on the natural notion of _quantifier depth_ of a basic
${\mathcal{L}}$-formula.)

A reader looking for a solution to the previous exercise can consult [29].

###  5.5. Examples of continuous theories

######  Example 5.14 (The Urysohn sphere).

The theory of the Urysohn sphere is axiomatized by sentences which express an
extension property characterizing the space we described in Example 3.4 We let
the theory $T^{ext}$ consist of the sentences $\varphi_{A,B}$ defined by
(recalling the notation from Example 4.7)

$\sup_{\bar{x}}(\inf_{y}D_{B}(\bar{x},y)\buildrel\textstyle\ .\over{\hbox{
\vrule height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ D_{A}(\bar{x})),$

where $n\geq 1$, $A=\\{a_{1},\ldots,a_{n}\\}$ and
$B=\\{a_{1},\ldots,a_{n},b\\}$ are $1$-bounded metric spaces, and
$\bar{x}=x_{1},\ldots,x_{n}$.

From our original characterization of the Urysohn sphere, it is clear that all
the sentences $\varphi_{A,B}$ are satisfied in $U$.

Before we show that $T^{ext}$ axiomatizes the theory of $U$, we first describe
a different amalgamation construction than the one from Example 3.4. Suppose
that $A$, $B=A\cup\\{b\\}$ and $C=A\cup\\{c\\}$ are all finite metric spaces
with $b\not=c$ and with metrics $d_{A},d_{B}$ and $d_{C}$ respectively for
which $d_{B}$ and $d_{C}$ extend the metric $d_{A}$. We wish to put a metric
$d$ on $B\cup C$ which extends both $d_{B}$ and $d_{C}$; in other words, we
must decide the value of $d(b,c)$. For the purposes of the argument to follow,
we set

$d(b,c)=\max_{a\in A}|d_{B}(b,a)-d_{C}(c,a)|.$

######  Exercise 5.15.

Prove that $d$ is indeed a metric on $B\cup C$.

We denote the resulting the resulting metric space $B\sqcup_{A}C$.

Now to see that $T^{ext}$ in fact axiomatizes the theory of $U$, it suffices
to prove the stronger statement that any separable model of $T^{ext}$ is
isomorphic to $U$. So suppose that $\mathcal{M}$ is a separable model of
$T^{ext}$. One proves that $\mathcal{M}$ is isomorphic to $U$ using a standard
back and forth argument. We will concentrate on the inductive step and leave
the rest of the details to the reader. Consider a finite metric space
$A=\\{a_{1},\ldots,a_{n}\\}\subset\mathcal{M}$ and an abstract one point
extension $B=A\cup\\{b\\}$ of $A$. We wish to find an isomorphic copy of $B$
extending $A$ in $\mathcal{M}$. First of all, we use the fact that
$\varphi_{A,B}^{\mathcal{M}}=0$ to find some $b_{0}\in\mathcal{M}$ such that
$D^{\mathcal{M}}_{B}(a_{1},\ldots,a_{n},b_{0})<1/2$. If we set $r_{a}=d(b,a)$
for $a\in A$, then we have that $|d(b_{0},a)-r_{a}|<1/2$ for all $a\in A$.

Set $B_{0}:=\\{a_{1},\ldots,a_{n},b_{0}\\}$. We now inductively build a
sequence $(b_{m})$ from $\mathcal{M}$ such that, setting
$B_{m}:=\\{a_{1},\ldots,a_{n},b_{m}\\}$ and $\hat{B}_{m}:=B_{m}\sqcup_{A}B$,
we have

$D_{\hat{B}_{m}}(a_{1},\ldots,a_{n},b_{m},b_{m+1})<1/2^{m+1}.$

Note that we can indeed obtain $b_{m+1}\in\mathcal{M}$ by invoking the fact
that $\varphi_{B_{m},\hat{B}_{m}}^{\mathcal{M}}=0$. This construction yields
$|d(b_{m},a)-r_{a}|<1/2^{m+1}$ and also $d(b_{m},b_{m+1})<3/2^{m+2}$. It is
now clear that $(b_{m}\colon m\in{\mathbf{N}})$ is a Cauchy sequence in
$\mathcal{M}$; letting $\tilde{b}\in\mathcal{M}$ be the limit of this
sequence, we get that $d(\tilde{b},a)=r_{a}$ for all $a\in A$ and so the map
$a_{1},\ldots,a_{n},b\mapsto a_{1},\ldots,a_{n},\tilde{b}$ is an isometry,
yielding the desired copy of $B$ in $\mathcal{M}$.

We now turn to some examples that have more structure than just the metric
symbol and are key to many of the articles in this volume.

######  Example 5.16 (Hilbert space).

We now write sentences (or axioms) that are true in all (dissections of)
Hilbert spaces using the language ${\mathcal{L}}_{HS}$. These sentences will
in fact axiomatize the theory of (dissections of) Hilbert spaces.

The first set of axioms will express that we are dealing with a complex vector
space. Due to the presence of the sorts $S_{n}$, we will need infinitely many
sentences to express the usual axioms. For instance, for each
$n\in{\mathbf{N}}$, we will have a sentence

$\sup_{x,y\in
S_{n}}d_{n}(\lambda_{n}(x+_{n}y),\lambda_{n}(x)+_{m}\lambda_{n}(y)),$

where $\lambda\in\mathbf{C}$ and $S_{m}$ is the co-domain of $\lambda_{n}$. Of
course, if these sentences hold in our structure, then we will know that
$\lambda(x+y)=\lambda x+\lambda y$ for all $x$ and $y$. We leave it as an
exercise to write out in a similar fashion all other sentences needed to
guarantee that we have a complex vector space.

The second set of axioms expresses that we have an inner product and expresses
its relationship with the metric on each sort. For instance, we have the
sentences

$\sup_{x\in S_{n}}|d_{n}(x,0)^{2}-Re\langle x,x\rangle|.$

We leave it as an exercise to express the other axioms related to the inner
product.

We need a third set of axioms which tell us that the inclusion maps between
the sorts are isometric embeddings that preserve the algebraic operations.
First, we need to express that the inclusion maps themselves are compatible:
for $n<m<k$, we include sentences

$\sup_{x\in S_{n}}d_{k}(i_{m,k}i_{n,m}(x),i_{n,k}(x)),$

which assert that $i_{m,k}i_{n,m}=i_{n,k}$ An instance of the inclusion maps
preserving the algebraic structure are the sentences, for $n<m$ and
$\lambda\in\mathbf{C}$,

$\sup_{x\in S_{n}}d_{l}(i_{k,l}(\lambda_{n}x),\lambda_{m}i_{n,m}(x)),$

where $S_{k}$ is the co-domain of $\lambda_{n}$ and $S_{l}$ is the co-domain
of $\lambda_{m}$.

Finally, we want to express that the sorts are interpreted correctly, that is,
$S_{n}$ should be the ball of radius $n$. We express this fact with two
axioms:

$\sup_{x\in S_{1}}(d_{1}(x,0)\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ 1)$

and

$\sup_{x\in S_{n}}\min\\{1\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ \|x\|,\inf_{y\in
S_{1}}d_{n}(y,i_{1,n}(y)\\}.$

The first axiom says that everything in $S_{1}$ should have norm at most 1 and
by scaling, everything in $S_{n}$ should have norm at most $n$. The second
axiom says that if something in $S_{n}$ has norm less than $1$, then it is in
the closure of the image of the inclusion map from $S_{1}$. Using the
completeness of the sorts, we obtain that anything of norm at most 1 in
$S_{n}$ arises from something in $S_{1}$. Consequently, if these two axioms
are satisfied (along with all the others above), then $S_{1}$ is the unit ball
of a Hilbert space, and the direct limit of the sorts, via the embeddings, is
a Hilbert space.

If we denote by $T_{HS}$ the set of sentences listed above, then we conclude:

######  Theorem 5.17.

$T_{HS}$ axiomatizes the class of dissections of Hilbert spaces. Moreover,
models of $T_{HS}$ with homomorphisms as morphisms and the category of Hilbert
spaces with homomorphisms as morphisms are equivalent via the dissection
functor.

######  Example 5.18 ($\mathrm{C}^{*}$-algebras).

As in the previous example, we now write out sentences that axiomatize the
class of (dissections of) $\mathrm{C}^{*}$-algebras in the language
${\mathcal{L}}_{C^{*}}$ from Example 3.10.

First of all we, need to express that the structure is a complex *-algebra.
This requires writing out a number of equations in the manner described above
in the Hilbert space example. We will not write out all the equations, but
here is an example:

$\sup_{x,y\in S_{n}}d_{n}((xy)^{*},y^{*}x^{*}).$

There is one such sentence for every $n\in{\mathbf{N}}$. Of course, this set
of sentences is expressing the relationship between multiplication and the
adjoint in a $\mathrm{C}^{*}$-algebra, namely that $(xy)^{*}=y^{*}x^{*}$ for
all $x$ and $y$.

We also want to say that the underlying structure is a normed algebra. Again,
we only write out a sample and leave it as an exercise to write out the rest.
It is tempting to write the triangle inequality as

$\forall_{x,y\in S_{n}}\|x+y\|\leq\|x\|+\|y\|$

but more formally it is written as

$\sup_{x,y\in S_{n}}\left(\|x+y\|\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ (\|x\|+\|y\|)\right),$

where $\|z\|$ is shorthand for $d(z,0)$. The latter sentence evaluates to $0$
in a ${\mathcal{L}}_{C^{*}}$-structure precisely when the triangle inequality
holds.

We also want our Banach *-algebra to be a $\mathrm{C}^{*}$-algebra. The
$\mathrm{C}^{*}$-identity is written as

$\sup_{x\in S_{n}}\left|\|x^{*}x\|-\|x\|^{2}\right|,$

where we use the above convention for $\|\cdot\|$. We include one such
sentence for every $n\in{\mathbf{N}}$ although, in light of the other axioms,
it would be enough to include this axiom only for $n=1$.

As in the case of Hilbert spaces, there are now some sentences which must be
included in order to make the formalism of continuous logic match with the
normal operator algebraic setting. To start with, we have the embedding maps
$i_{m,n}$. We can write out sentences which will express that these maps are
isometric embeddings and they preserve the relevant algebraic structure
(addition, multiplication and the adjoint). We leave the formulation of these
sentences to the reader.

We also want the sorts $S_{n}$ to be interpreted as the operator norm balls of
radius $n$. We need two sets of sentences. First, we include sentences

$\sup_{x\in S_{n}}(\|x\|\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ n),$

which says that every element of the sort $S_{n}$ has norm at most $n$.
Finally, we record sentences which will guarantee that all the elements of
norm at most $n$ lie in $S_{n}$. Recall from Example 3.10 the introduction of
function symbols $\mathbf{q^{n}_{k}}$ with domain $S_{n}$ and co-domain
$S_{1}$. They are to represent polynomials $q^{n}_{k}$ and so we write
sentences

$\sup_{x\in S_{n}}d_{m}(i_{1,m}(\mathbf{q^{n}_{k}}(x)),q^{n}_{k}(x)),$

where $S_{m}$ is the co-domain of the term $q^{n}_{k}$. We will call the set
of sentences that we have outlined in this example $T_{C^{*}}$. By the
argument after Lemma 3.11, we see that the ${\mathcal{L}}_{C^{*}}$-structures
which satisfy $T_{C^{*}}$ are precisely those of the form $D(A)$ for some
$\mathrm{C}^{*}$-algebra $A$. We conclude:

######  Theorem 5.19.

$T_{C^{*}}$ axiomatizes the class of dissections of $\mathrm{C}^{*}$-algebras.
Moreover the category of $\mathrm{C}^{*}$-algebras and the category of models
of $T_{C^{*}}$ (with homomorphisms as morphisms) are equivalent via the
dissection functor.

##  6\. Ultraproducts

###  6.1. Ultraproducts of metric structures

Fix a metric language ${\mathcal{L}}=(\mathfrak{S,F,R})$, an index set $I$, an
ultrafilter ${\mathcal{U}}$ on $I$, and ${\mathcal{L}}$-structures
$\mathcal{M}_{i}$ for $i\in I$. We construct the _(metric) ultraproduct_
$\mathcal{N}:=\prod_{\mathcal{U}}\mathcal{M}_{i}$ as follows:

  * •

For each sort $S\in\mathfrak{S}$, we let $S^{\mathcal{N}}$ be the metric space
$\prod_{\mathcal{U}}(S^{\mathcal{M}_{i}},d_{i})$, where $d_{i}$ is the metric
on $S^{\mathcal{M}_{i}}$. We interpret the metric on $S^{\mathcal{N}}$ as
$\lim_{\mathcal{U}}d_{i}$. Recall that this is well-defined since all the
metric spaces involved are uniformly bounded by the bound $B_{S}$.

  * •

For each $f\in\mathfrak{F}$ whose domain is $S_{1}\times\ldots\times S_{n}$,
we define $f^{\mathcal{N}}$ by

$f^{\mathcal{N}}([(a^{1}_{i})]_{\mathcal{U}},\ldots,[(a^{n}_{i})]_{\mathcal{U}})=[(f(a^{1}_{i},\ldots,a^{n}_{i}))]_{\mathcal{U}},$

where $[(a^{j}_{i})]_{\mathcal{U}}\in S^{\mathcal{N}}_{j}$ for all
$j=1,\ldots,n$. Again, since all interpretations of $f$ satisfy the same
uniform continuity modulus, this definition of $f^{\mathcal{N}}$ is well-
defined and $f^{\mathcal{N}}$ satisfies the uniform continuity modulus
specified by the language.

  * •

For each $R\in\mathfrak{R}$, we define $R^{\mathcal{N}}$ by

$R^{\mathcal{N}}([(a^{1}_{i})]_{\mathcal{U}},\ldots,[(a^{n}_{i})]_{\mathcal{U}})=\lim_{\mathcal{U}}R^{\mathcal{M}_{i}}(a^{1}_{i},\ldots,a^{n}_{i}),$

where $[(a^{j}_{i})]_{\mathcal{U}}\in S^{N}_{j}$ for all $j=1,\ldots,n$. As in
the case of function symbols, since the interpretation of $R$ is uniformly
bounded in all $\mathcal{M}_{i}$ with the same uniform continuity modulus,
this definition of $R^{\mathcal{N}}$ is well-defined and $R^{\mathcal{N}}$
satisfies the uniform continuity modulus specified by the language.

######  Exercise 6.1.

Verify that $\prod_{\mathcal{U}}\mathcal{M}_{i}$ is indeed an
${\mathcal{L}}$-structure.

If all the $\mathcal{M}_{i}$ are the same ${\mathcal{L}}$-structure
$\mathcal{M}$, then we call the resulting ultraproduct the _ultrapower_ and
denote it by $\mathcal{M}^{\mathcal{U}}$.

As in classical logic, it is important to be able to evaluate formulas in the
ultraproduct. Here is the appropriate version of _Łoś’ Theorem_.

######  Theorem 6.2.

Suppose that $\mathcal{M}_{i}$ is an ${\mathcal{L}}$-structure for all $i\in
I$ and ${\mathcal{U}}$ is an ultrafilter on $I$. Set
$\mathcal{N}=\prod_{\mathcal{U}}\mathcal{M}_{i}$. For an
${\mathcal{L}}$-formula $\varphi(\bar{x})$ and
$\bar{a}=[(\bar{a}_{i})]_{\mathcal{U}}\in\mathcal{N}$ sorted the same as the
variables $\bar{x}$, we have

$\varphi^{\mathcal{N}}(\bar{a})=\lim_{\mathcal{U}}\varphi^{\mathcal{M}_{i}}(\bar{a}_{i}).$

###### Proof.

The proof is by induction on the formulation of basic formulas. We only treat
the case of $\varphi(\bar{x})=\inf_{y}\psi(y,\bar{x})$.

Suppose that $\lim_{\mathcal{U}}\varphi^{\mathcal{M}_{i}}(\bar{a}_{i})>r$ for
some $r\in\mathbf{R}$. Set $X=\\{i\in I:\varphi^{M_{i}}(\bar{a}_{i})>r\\}$ and
note that $X\in{\mathcal{U}}$. Fix $b=[(b_{i})]_{\mathcal{U}}\in\mathcal{N}$.
For each $i\in X$, we have $\psi^{\mathcal{M}_{i}}(b_{i},\bar{a}_{i})>r$. By
induction, we have $\psi^{\mathcal{N}}(b,\bar{a})\geq r$. Since this was true
for all $b\in\mathcal{N}$, we have $\varphi^{\mathcal{N}}(\bar{a})\geq r$ and
thus
$\varphi^{\mathcal{N}}(\bar{a})\geq\lim_{\mathcal{U}}\varphi^{\mathcal{M}_{i}}(\bar{a}_{i})$.

Now suppose that $s=\varphi^{\mathcal{N}}(\bar{a})>r$ but
$\lim_{\mathcal{U}}\varphi^{\mathcal{M}_{i}}(\bar{a}_{i})\leq r$. Pick
$\epsilon>0$ small enough so that $r+\epsilon<s$ and let $X=\\{i\in
I\colon\varphi^{\mathcal{M}_{i}}(\bar{a}_{i})<r+\epsilon\\}\in{\mathcal{U}}$.
For $i\in X$, choose $b_{i}\in\mathcal{M}_{i}$ so that
$\psi^{\mathcal{M}_{i}}(b_{i},\bar{a}_{i})<r+\epsilon$. Set
$b=[(b_{i})]_{\mathcal{U}}$. By induction we have
$\psi^{\mathcal{N}}(b,\bar{a})\leq r+\epsilon<s$, which is a contradiction. ∎

######  Exercise 6.3.

Verify the remaining cases in the proof of Łos’s theorem including
generalizing to arbitrary formulas from basic formulas.

###  6.2. Applications of the ultraproduct

We say that a set of sentences $\Gamma$ is _finitely satisfiable_ if every
finite subset of $\Gamma$ is satisfiable. We say that $\Gamma$ is
_approximately finitely satisfiable_ if, for every finite subset
$\Gamma_{0}\subset\Gamma$ and every $\epsilon>0$, there is an
${\mathcal{L}}$-structure $\mathcal{M}$ so that
$|\varphi^{\mathcal{M}}|\leq\epsilon$ for every $\varphi\in\Gamma_{0}$.
Equivalently, $\Gamma$ is approximately finitely satisfiable if the set of
sentences $\\{|\varphi|\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\
\epsilon\colon\varphi\in\Gamma,\ \epsilon>0\\}$ is finitely satisfiable.

######  Theorem 6.4 (Compactness Theorem).

For a metric language ${\mathcal{L}}$ and a set of ${\mathcal{L}}$-sentences
$\Gamma$, the following are equivalent:

  1. (1)

$\Gamma$ is satisfiable.

  2. (2)

$\Gamma$ is finitely satisfiable.

  3. (3)

$\Gamma$ is approximately finitely satisfiable.

###### Proof.

Clearly the conditions decrease in strength. To show that (3) implies (1),
consider $I$ to be the set of finite subsets of $\Gamma\cup{\mathbf{N}}$
(disjoint union) which have non-empty intersection with both $\Gamma$ and
${\mathbf{N}}$. If $i=F\cup X$ is an element of $I$ with $F\subset\Gamma$ and
$X\subset{\mathbf{N}}$, let $M_{i}$ be an ${\mathcal{L}}$-structure such that
$|\varphi^{M_{i}}|\leq 1/m$ for all $\varphi\in F$, where $m=\max\\{n\colon
n\in X\\}$. For $\varphi\in\Gamma$ and $n\in{\mathbf{N}}$, let $O_{\varphi,n}$
be the set of $i\in I$ which contain both $\varphi$ and $n$. Notice that
$Y=\\{O_{\varphi,n}\colon\varphi\in\Gamma,n\in{\mathbf{N}}\\}$ has the finite
intersection property. Let ${\mathcal{U}}$ be an ultrafilter on $I$ which
contains $Y$. Consider the ultraproduct
$\mathcal{N}=\prod_{\mathcal{U}}M_{i}$. For every $\varphi\in\Gamma$ and every
$n\in{\mathbf{N}}$, we have $O_{\varphi,n}\in{\mathcal{U}}$, so by the Łoś
Theorem, we have $|\varphi^{\mathcal{N}}|\leq\frac{1}{n}$ for all $n$ and
hence $\varphi^{\mathcal{N}}=0$. It follows that $\mathcal{N}$ satisfies
$\Gamma$. ∎

We can use the compactness theorem and the method of expansion by constants to
give a version of the upward Löwenheim-Skolem theorem in the continuous
setting. We say that a metric structure $\mathcal{M}$ is _compact_ if
$S^{\mathcal{M}}$ is a compact metric space for each sort $S$ in the language.

######  Theorem 6.5.

Suppose that $\mathcal{M}$ is a non-compact ${\mathcal{L}}$-structure and
$\chi(Th(\mathcal{M}),{\mathcal{L}})\leq\lambda$. Then $\mathcal{M}$ has an
elementary extension $\mathcal{N}$ such that $\chi(\mathcal{N})=\lambda$.

###### Proof.

Since $\mathcal{M}$ is not compact, there is a sort $S$ and an $\epsilon>0$
such that the collection of $\epsilon$-balls of $S^{\mathcal{M}}$ does not
have a finite subcover. Now consider the language ${\mathcal{L}}^{\prime}$
obtained from ${\mathcal{L}}$ by introducing new constant symbols $c_{\alpha}$
of sort $S$ for $\alpha<\lambda$. Consider the ${\mathcal{L}}^{\prime}$-theory
$T^{\prime}$ made up of $Elem(\mathcal{M})$ together with

$\\{d(c_{\alpha},c_{\beta})\geq\epsilon:\alpha<\beta<\lambda\\}.$

Note that $T^{\prime}$ is finitely satisfiable and
$\chi(T^{\prime},{\mathcal{L}}^{\prime})=\lambda$. By the compactness theorem
and the downward Löwenheim-Skolem theorem, $T^{\prime}$ has a model with
density character $\lambda$. Taking the reduct of this model to
${\mathcal{L}}$, we get the required model of $T$ of density character
$\lambda$. ∎

###  6.3. Elementary equivalence and ultraproducts

We begin this section with an exercise.

######  Exercise 6.6.

For ${\mathcal{L}}$-structures $\mathcal{M}$ and $\mathcal{N}$, we have that
$\mathcal{M}\equiv\mathcal{N}$ if and only if there is an
${\mathcal{L}}$-structure $\mathcal{P}$ such that $\mathcal{M}$ and
$\mathcal{N}$ both elementarily embed into $\mathcal{P}$.

This exercise can be significantly strengthened:

######  Theorem 6.7 (Keisler-Shelah).

For ${\mathcal{L}}$-structures $\mathcal{M}$ and $\mathcal{N}$, we have that
$\mathcal{M}\equiv\mathcal{N}$ if and only if there are ultrafilters
${\mathcal{U}}$ and ${\mathcal{V}}$ such that
$\mathcal{M}^{\mathcal{U}}\cong\mathcal{N}^{\mathcal{V}}$.

The proof in the classical case can be found in [35, 40]. In the continuous
case, a proof appears in [27] while a proof in the positive bounded case
appears in [32]. It is important to notice that in the Keisler-Shelah theorem,
the index sets for the ultrafilters need not be countable.

In the continuous setting, it is often difficult to explicitly write out a
sentence that distinguishes the theories of two structures. The approach of
showing that no two ultrapowers are isomorphic has been used to good effect in
separating theories of II1 factors (see [14], [16] and Section 4 in the
author’s article with Goldbring in this volume).

EF-games were discussed in the previous section. There is also an infinite
version of an EF-game involving ultrapowers which is sometimes easier to work
with. We describe this game only in the case where ${\mathcal{L}}$ is
separable. Given two ${\mathcal{L}}$-structures $\mathcal{M}$ and
$\mathcal{N}$, the $\infty$-$EF(\mathcal{M},\mathcal{N})$-game is a two player
game between Player I and Player II which now goes on for $\omega$ many
rounds. The players play as in a finite EF-game, this time creating two
sequences $(a_{i}:i\in{\mathbf{N}})$ in $\mathcal{M}$ and
$(b_{i}:i\in{\mathbf{N}})$ in $\mathcal{N}$. Player II wins the game if the
map $a_{i}\mapsto b_{i}$, for $i\in{\mathbf{N}}$, extends to an isomorphism of
${\mathcal{L}}$-substructures of $\mathcal{M}$ and $\mathcal{N}$ respectively.

######  Theorem 6.8.

Assume ${\mathcal{L}}$ is separable. Then for two ${\mathcal{L}}$-structures
$\mathcal{M}$ and $\mathcal{N}$, the following are equivalent:

  1. (1)

$\mathcal{M}\equiv\mathcal{N}$.

  2. (2)

For some (equiv. any) non-principal ultrafilter ${\mathcal{U}}$ on
$\mathbb{N}$, player II has a winning strategy for the
$\infty$-$EF(\mathcal{M}^{\mathcal{U}},\mathcal{N}^{\mathcal{U}})$-game.

######  Exercise 6.9.

Prove the previous theorem.

###  6.4. Elementary classes

We now give a characterization of elementary classes which parallels a result
from classical first order logic. Fix a class $\mathcal{C}$ of
${\mathcal{L}}$-structures. We say that $\mathcal{C}$ is _closed under
ultraroots_ if for any ultrafilter ${\mathcal{U}}$, whenever
$\mathcal{N}^{\mathcal{U}}\in\mathcal{C}$, then $\mathcal{N}\in\mathcal{C}$.

######  Theorem 6.10.

Suppose that $\mathcal{C}$ is a class of ${\mathcal{L}}$-structures. The
following are equivalent:

  1. (1)

$\mathcal{C}$ is an elementary class.

  2. (2)

$\mathcal{C}$ is closed under isomorphisms, ultraproducts, and elementary
submodels.

  3. (3)

$\mathcal{C}$ is closed under isomorphisms, ultraproducts, and ultraroots.

###### Proof.

Clearly (1) implies both (2) and (3). We first prove (2) implies (1) and then
modify the proof to get (3) implies (1). Thus, assume (2) and let $T$ be the
theory of $\mathcal{C}$, that is, let $T$ be the set of all sentences
$\varphi$ such that $\varphi^{\mathcal{N}}=0$ for all
$\mathcal{N}\in\mathcal{C}$. We show that $\mathcal{C}$ is the collection of
models of $T$. It is clear that all elements of $\mathcal{C}$ model $T$. On
the other hand, fix a model $\mathcal{M}$ of $T$. By (2), it suffices to
elementarily embed $\mathcal{M}$ into an ultraproduct of structures from
$\mathcal{C}$. To this end, suppose $\varphi(c_{\bar{m}})$ is in
$Elem(\mathcal{M})$ for some sequence of constants $c_{\bar{m}}$ with
$\bar{m}\in\mathcal{M}$. Now consider $\inf_{\bar{x}}|\varphi(\bar{x})|$, an
${\mathcal{L}}$-sentence whose value in $\mathcal{M}$ is 0. Fix $\epsilon>0$.
Then there is $\mathcal{N}_{\varphi,\epsilon}\in\mathcal{C}$ which satisfies
$\inf_{\bar{x}}|\varphi(\bar{x})|<\epsilon$ (for otherwise the sentence
$\epsilon\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\
\inf_{\bar{x}}|\varphi(\bar{x})|$ belongs to $T$, contradicting the fact that
$\mathcal{M}\models T$). By taking an ultraproduct over all
$\mathcal{N}_{\varphi,\epsilon}$ as $\varphi$ and $\epsilon$ vary, we can
elementarily embed $\mathcal{M}$ into an ultraproduct of elements of
$\mathcal{C}$, as desired.

To obtain (3) implies (1), notice that the previous argument showed (assuming
that $\mathcal{C}$ is merely closed under isomorphisms and ultraproducts) that
$\mathcal{M}\equiv\mathcal{N}$ for some $\mathcal{N}$ in $\mathcal{C}$ (namely
an ultraproduct of structures from $\mathcal{C}$). By the Keisler-Shelah
theorem, $\mathcal{M}^{\mathcal{U}}\cong\mathcal{N}^{\mathcal{V}}$ for some
ultrafilters ${\mathcal{U}}$ and ${\mathcal{V}}$. Assuming (3), we have that
$\mathcal{M}\in\mathcal{C}$. ∎

Although the semantic characterization of elementary class is the same in
continuous logic as in classical logic, it plays a somewhat bigger role in the
continuous setting as it is often difficult to explicitly write out sentences
that axiomatize a given class of metric structures. For instance, although the
class of W∗-probability spaces (see [2] for the definition) was axiomatized in
a complicated language in [17], it was relatively easy to show using the above
semantic characterization that this class was elementary in a more natural
language [26]; an explicit axiomatization in this language will only finally
appear in [3].

######  Exercise 6.11.

Referring back to Example 3.10 of the class of $\mathrm{C}^{*}$-algebras and
their dissections as metric structures, we want to see that the ultraproduct
in the metric structure sense and the $\mathrm{C}^{*}$-algebra sense match up.
Recall that if $(A_{i}:i\in I)$ is a family of $\mathrm{C}^{*}$-algebras and
${\mathcal{U}}$ is an ultrafilter on $I$, then we set
$\prod_{I}^{\infty}A_{i}$ to be

$\\{\bar{a}\in\prod_{I}A_{i}:\text{there is }B>0\text{ so that }\|a_{i}\|\leq
B\text{ for all }i\in I\\}$

and

$J=\\{\bar{a}\in\prod_{I}^{\infty}A_{i}:\lim_{{\mathcal{U}}}\|a_{i}\|=0\\}.$

The C*-algebraic ultraproduct of $(A_{i})$ with respect to ${\mathcal{U}}$ is
then defined to be

$\prod_{\mathcal{U}}A_{i}=\prod_{I}^{\infty}A_{i}/J.$

Prove that $D(\prod_{\mathcal{U}}A_{i})=\prod_{\mathcal{U}}D(A_{i})$, where
the ultraproduct appearing on the right-hand side is the ultraproduct of
metric structures.

This exercise, together with Example 3.10, shows, by Theorem 6.10, that the
class of dissections of $\mathrm{C}^{*}$-algebras is an elementary class,
categorically equivalent to the class of $\mathrm{C}^{*}$-algebras via the
dissection functor which even preserves ultraproducts. Of course, we already
know that the class of dissections is an elementary class because they are
exactly the ${\mathcal{L}}_{C^{*}}$-structures which satisfy the theory
$T_{C^{*}}$ from Example 5.18.

##  7\. Types

###  7.1. The type space

Suppose that $T$ is a theory in some language ${\mathcal{L}}$. Fix a sequence
of sorted variables $\bar{x}$. The _space of $\bar{x}$-types of $T$_, denoted
$S_{\bar{x}}(T)$, is the set of functions of the form
$tp^{\mathcal{M}}(\bar{a})(\varphi(\bar{x})):=\varphi^{\mathcal{M}}(\bar{a})$,
where $\mathcal{M}$ is a model of $T$, $\bar{a}\in\mathcal{M}$ (sorted in the
same way as the variables in $\bar{x}$), and $\varphi$ is an
${\mathcal{L}}$-formula whose free variables are among $\bar{x}$.
$tp^{\mathcal{M}}(\bar{a})$ is called the _complete type of $a$ in
$\mathcal{M}$_ (complete meaning that the value of every formula $\varphi$ is
completely specified). We use letters such as $p$ and $q$ to denote complete
types. If $p\in S_{\bar{x}}(T)$ and $\bar{a}\in\mathcal{M}$ is such that
$tp^{\mathcal{M}}(\bar{a})=p$, then we say that $\bar{a}$ _realizes_ $p$ and
that $p$ is _realized in $\mathcal{M}$_. Just as with complete theories,
complete types are determined by knowing the kernel of the type functional:

$tp^{\mathcal{M}}(\bar{a})(\varphi(\bar{x}))=r\text{ iff
}\varphi(\bar{x})-r\in ker(tp^{\mathcal{M}}(\bar{a})).$

It is convenient to talk about partial types as well. Suppose $\Sigma$ is a
set of ${\mathcal{L}}$-formulas in free variables $\bar{x}$ and $p$ is a
complete type in the variables $\bar{x}$. Then the corresponding _partial (
$\Sigma$)-type_ is the function $p\restriction\Sigma$. If $\Sigma$ is the set
of all quantifier-free formulas in the free variables $\bar{x}$, we call the
$\Sigma$-type a _quantifier-free type_.

As in the classical case, the type space $S_{\bar{x}}(T)$ carries a natural
topology. For $\varphi\in Form_{\bar{x}}(T,{\mathcal{L}})$ and real numbers
$r<s$, set

$O^{T}(\varphi,(r,s))=\\{p\in S_{\bar{x}}(T)\colon p(\varphi)\in(r,s)\\}.$

######  Exercise 7.1.

  1. (1)

Prove that the set of all $O^{T}(\varphi,(r,s))$ is a base for a Hausdorff
topology on $S_{\bar{x}}(T)$, called the _logic topology_.

  2. (2)

Prove that the logic topology on $S_{\bar{x}}(T)$ is compact. (Hint: use the
compactness theorem.)

  3. (3)

Prove that if $\pi(\bar{x})$ is a partial type, then the set $\\{p\in
S_{\bar{x}}(T)\ :\ p\text{ extends }\pi\\}$ is a closed subset of
$S_{\bar{x}}(T)$.

  4. (4)

In fact, show that every non-empty closed in the logic topology on
$S_{\bar{x}}(T)$ has the form $\\{p\in S_{\bar{x}}(T)\ :\ p\text{ extends
}\pi\\}$, where $\pi$ is a partial type. (Hint: Show that those $p\in
S_{\bar{x}}(T)$ for which $p(\varphi)\leq r$ are the same as those which
extend the partial type $\pi$ where $\pi(\varphi\buildrel\textstyle\
.\over{\hbox{ \vrule height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\
r)=0$.)

If the theory $T$ is complete, the type space also has a natural _metric
topology_ : for $p,q\in S_{\bar{x}}(T)$, we set $d(p,q)$ to be the infinum of
$d(\bar{a},\bar{b})$, where $p=tp^{\mathcal{M}}({\bar{a}})$ and
$q=tp^{\mathcal{M}}({\bar{b}})$ for some model $\mathcal{M}$ of $T$ and some
$\bar{a},\bar{b}\in\mathcal{M}$ . The completeness of the theory guarantees
that $d(p,q)$ is defined (not infinite) for every pair of types $p$ and $q$.
The symmetry and reflexivity of $d(p,q)$ are clear. To see that the triangle
inequality holds, fix $p,q,r\in S_{\bar{x}}(T)$. By compactness, we can find
models $\mathcal{M}$ and $\mathcal{N}$ of $T$ and
$\bar{a},\bar{b}\in\mathcal{M}$, $\bar{b}^{\prime},\bar{c}\in\mathcal{N}$ with
$p=tp^{\mathcal{M}}(\bar{a})$,
$q=tp^{\mathcal{M}}(\bar{b})=tp^{\mathcal{N}}(\bar{b}^{\prime})$,
$r=tp^{\mathcal{N}}(\bar{c})$, $d(p,q)=d(\bar{a},\bar{b})$ and
$d(q,r)=d(\bar{b}^{\prime},\bar{c})$. We leave it as an exercise that by
taking a common elementary extension of $\mathcal{M}$ and $\mathcal{N}$, we
can assume that $\mathcal{M}=\mathcal{N}$ and $\bar{b}=\bar{b}^{\prime}$. By
the triangle inequality (in $\mathcal{M}$), $d(p,q)+d(q,r)\geq
d(\bar{a},\bar{c})\geq d(p,r)$.

######  Exercise 7.2.

  1. (1)

Show that the metric topology refines the logic topology on $S_{\bar{x}}(T)$.

  2. (2)

Show that $S_{\bar{x}}(T)$ is complete with respect to the metric topology.

We will see later that there are model theoretic consequences when these two
topologies agree (even locally).

###  7.2. Some uses of the Stone-Weierstrass theorem in continuous logic

To understand the extension from basic formulas to more general formulas in a
more abstract fashion, we remind the reader of the background necessary for
the Stone-Weierstrass theorem.

Suppose that $X$ is a topological space and set $C(X,\mathbf{R})$ to be the
set of continuous functions from $X$ to $\mathbf{R}$. $C(X,\mathbf{R})$ has a
natural real algebra structure by considering pointwise addition and
multiplication together with scalar multiplication by elements of
$\mathbf{R}$. It is also naturally topologized by uniform convergence, that
is, for $f\in C(X,\mathbf{R})$ and $\epsilon>0$, the set

$\\{g\in C(X,\mathbf{R})\colon|f(x)-g(x)|<\epsilon\text{ for all }x\in X\\}$

is a basic open set. When $X$ is compact, $C(X,\mathbf{R})$ is metrizable by
the $\sup$-norm. For $A\subseteq C(X,\mathbf{R})$, we say that $A$ _separates
points_ if for all $x,y\in X$, there is $f\in A$ such that $f(x)\neq f(y)$.

######  Theorem 7.3 (Stone-Weierstrass theorem).

Suppose that $X$ is a compact, Hausdorf space and $A$ is a real subalgebra of
$C(X,\mathbf{R})$. If the constant function $1$ belongs to $A$, then $A$ is
dense in $C(X,\mathbf{R})$ if and only if $A$ separates points.

If $\varphi(\bar{x})$ is an ${\mathcal{L}}$-formula and $T$ is an
${\mathcal{L}}$-theory, then there is a natural evaluation map
$f_{\varphi}\colon S_{\bar{x}}(T)\rightarrow\mathbf{R}$ given by
$f_{\varphi}(p)=p(\varphi)$. With the logic topology on the type space
$S_{\bar{x}}(T)$, it is easy to see that $f_{\varphi}$ is continuous. We want
to use the Stone-Weierstrass theorem to give another understanding of formulas
in continuous model theory. In fact, this alternative perspective is really
the reason behind extending the class of formulas.

######  Theorem 7.4.

Suppose that $T$ is a theory, $\bar{x}$ a sequence of variables, and
$X=S_{\bar{x}}(T)$. Then the evaluation map $ev$ from
$Form_{\bar{x}}(T,{\mathcal{L}})$ to $C(X,R)$ given by
$ev(\varphi)=f_{\varphi}$ is an isometry which commutes with all continuous
real-valued functions, that is, if $f:\mathbf{R}^{n}\rightarrow\mathbf{R}$ is
a continuous function and $\varphi_{1},\ldots,\varphi_{n}\in
Form_{\bar{x}}(T,{\mathcal{L}})$, then

$f\circ(ev(\varphi_{1}),\ldots,ev(\varphi_{n}))=ev(f(\varphi_{1},\ldots,\varphi_{n})).$

###### Proof.

Note that the range of the evaluation map restricted to basic formulas is a
real subalgebra containing 1 and which separates points. It follows then from
the Stone-Weierstrass theorem that the evaluation map is onto. The map is
norm-preserving since if $\varphi(\bar{x})$ is a basic formula such that
$\|\varphi\|_{T}=r$, then on the one hand, $\|ev(\varphi)\|\leq r$ in
$C(X,\mathbf{R})$, while by compactness, we can find some $p\in
S_{\bar{x}}(T)$ such that $ev(|\varphi|)(p)=r$, hence $\|ev(\varphi)\|=r$.
Commutation with continuous functions is immediate. ∎

We need a slight strengthening of the previous theorem for real algebra
systems (see Definition 5.3). The proof follows from compactness and the
Stone-Weierstrass theorem.

######  Proposition 7.5.

Suppose that $T$ is an ${\mathcal{L}}$-theory and $A$ is real algebra system
of $T$-formulas. Let $X$ be the set of restrictions of elements in
$S_{\bar{x}}(T)$ to formulas in $A_{\bar{x}}$. Then

  1. (1)

$X$ is compact, and

  2. (2)

if the range of the evaluation map from $A_{\bar{x}}$ to $C(X,\mathbf{R})$
separates points then the evaluation map is an isometry that commutes with all
continuous functions.

######  Exercise 7.6.

Prove the previous proposition.

As mentioned before, three places where the previous proposition will be
useful are for the following real algebra systems:

  1. (1)

$A_{\bar{x}}$ is the closure of the basic ${\mathcal{L}}^{\prime}$-formulas in
$Form_{\bar{x}}(T,{\mathcal{L}})$ for ${\mathcal{L}}^{\prime}$, a sublanguage
of ${\mathcal{L}}$, and $T$, an ${\mathcal{L}}$-theory.

  2. (2)

$A_{\bar{x}}$ the set of quantifier-free ${\mathcal{L}}$-formulas in the free-
variables $\bar{x}$.

  3. (3)

$A_{\bar{x}}$ the set of prenex formulas in ${\mathcal{L}}$ in the free
variables $\bar{x}$. Note that prenex formulas in ${\mathcal{L}}$ are dense in
the set of all ${\mathcal{L}}$-formulas. (See Section 6 of [10] for details.)

###  7.3. Saturation

Suppose that $\mathcal{M}$ is an ${\mathcal{L}}$-structure and
$A\subset\mathcal{M}$. We say that $p$ is a _(partial) type over $A$_ if $p$
is a (partial) type in ${\mathcal{L}}_{A}$ with respect to the theory of
$\mathcal{M}_{A}$. Consequently, if $p$ is a partial type over $A$, there is
an elementary extension $\mathcal{N}$ of $\mathcal{M}$ and
$\bar{b}\in\mathcal{N}$ realizing $p$, that is, if $\varphi(\bar{x},\bar{a})$
is an ${\mathcal{L}}_{A}$-formula (in the domain of $p$), then
$p(\varphi(\bar{x},\bar{a}))=\varphi^{\mathcal{N}}(\bar{b},\bar{a})$.

######  Definition 7.7.

For $\kappa$ an infinite cardinal, we say that an ${\mathcal{L}}$-structure
$\mathcal{M}$ is _$\kappa$ -saturated_ if, whenever $A\subseteq\mathcal{M}$ is
such that $\chi(A)<\kappa$ and $p$ is a type over $A$, then $p$ is realized in
$\mathcal{M}$. $\mathcal{M}$ is said to be _saturated_ if it is
$\chi(\mathcal{M})$-saturated.

As in the case of classical first order logic, saturated models typically only
exist under additional set theoretic assumptions. For instance, if
$2^{\kappa}=\kappa^{+}$, then the following proposition yields that if
$\chi(\mathcal{M})=\kappa$, then $\mathcal{M}$ has a saturated elementary
extension of density character $\kappa^{+}$.

######  Proposition 7.8.

Suppose that $\mathcal{M}$ is an ${\mathcal{L}}$-structure and
$\chi({\mathcal{L}})\leq\chi(\mathcal{M})=\kappa$. Then there is an elementary
extension $\mathcal{N}$ of $\mathcal{M}$ such that $\mathcal{N}$ is
$\kappa^{+}$-saturated and $\chi(\mathcal{N})\leq 2^{\kappa}$.

###### Proof.

We construct $\mathcal{N}$ as a union of an increasing chain
$(\mathcal{M}_{\alpha})_{\alpha<\kappa^{+}}$ such that:

  1. (1)

$M_{0}=\mathcal{M}$,

  2. (2)

if $\delta<\kappa^{+}$ is a limit ordinal, then $\mathcal{M}_{\delta}$ is the
completion of $\bigcup_{\alpha<\delta}\mathcal{M}_{\alpha}$ (that is, we take
the direct limit of the $\mathcal{M}_{\alpha}$’s as described in Proposition
5.10),

  3. (3)

$\chi(\mathcal{M}_{\alpha})\leq 2^{\kappa}$ for all $\alpha<\kappa^{+}$, and

  4. (4)

for every $\alpha<\kappa^{+}$, $\mathcal{M}_{\alpha}\prec M_{\alpha+1}$ and
for every $A\subseteq\mathcal{M}_{\alpha}$ with $\chi(A)\leq\kappa$, every
type $p$ over $A$ is realized in $\mathcal{M}_{\alpha+1}$.

Only the last point needs comment. There are $2^{\kappa}$ many subsets of size
$\kappa$ of a set of size $2^{\kappa}$ and at most $2^{\kappa}$ many types
over a set of density character $\kappa$. Consequently, we need to realize
$2^{\kappa}$ many types, which one can do one at a time with a chain of length
$2^{\kappa}$ since any individual type can be realized in an elementary
extension of density character at most $2^{\kappa}$. ∎

One model-theoretic reason for working with ultraproducts is that they are
always somewhat saturated:

######  Exercise 7.9.

Suppose that ${\mathcal{L}}$ is a separable language, $\mathcal{M}_{n}$ is an
${\mathcal{L}}$-structure for all $n\in{\mathbf{N}}$, and ${\mathcal{U}}$ is a
non-principal ultrafilter on ${\mathbf{N}}$. Show that
$\prod_{\mathcal{U}}\mathcal{M}_{n}$ is $\aleph_{1}$-saturated.

Ultraproducts can also produce structures of higher saturation as the
following proposition indicates. The ultrafilters used in the proof of this
proposition are called _good ultrafilters_ (see [22]). A proof of the
existence of good ultrafilters can be found in [36] and the saturation of the
ultraproduct can be found in [35]; see also [22, Chapter 8].

######  Proposition 7.10.

For every infinite cardinal $\kappa$, there is an ultrafilter ${\mathcal{U}}$
on $\kappa$ such that if ${\mathcal{L}}$ has density character at most
$\kappa$ and $\mathcal{M}_{\alpha}$ is an ${\mathcal{L}}$-structure for all
$\alpha<\kappa$, then $\prod_{\mathcal{U}}\mathcal{M}_{\alpha}$ is
$\kappa^{+}$-saturated.

###  7.4. Beth definability

We now prove the Beth Definability theorem in continuous logic. This theorem
gives us an abstract criterion for recognizing relations that can be expressed
by a formula. As we will see, this theorem plays a wider role in continuous
logic than in classical logic due to the difficulty in identifying which
relations are exactly formulas in the continuous setting.

######  Theorem 7.11 (Beth Definability).

Suppose that ${\mathcal{L}}^{\prime}\subseteq{\mathcal{L}}$ are two continuous
languages with the same sorts. Further, suppose $T$ is an
${\mathcal{L}}$-theory. If the forgetful functor $F:Mod(T)\rightarrow
Str({\mathcal{L}}^{\prime})$ given by
$F(\mathcal{M})=\mathcal{M}\restriction{\mathcal{L}}^{\prime}$ is an
equivalence of categories onto the image of $F$, then every
${\mathcal{L}}$-formula is $T$-equivalent to an
${\mathcal{L}}^{\prime}$-formula.

###### Proof.

Suppose that $\varphi(\bar{x})$ is an ${\mathcal{L}}$-formula. For
$\epsilon>0$, consider the set of sentences $\Sigma_{\epsilon}$ in the
language ${\mathcal{L}}$ with two tuples of constants $\bar{a}$ and $\bar{b}$
added consisting of $T$ together with

$\\{|\psi(\bar{a})-\psi(\bar{b})|\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\
\frac{1}{n}:\psi(\bar{x})\text{ is an ${\mathcal{L}}^{\prime}$-formula,
}n\in{\mathbf{N}}\\}\cup\\{\epsilon\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\
|\varphi(\bar{a})-\varphi(\bar{b})|\\}.$

If $\Sigma_{\epsilon}$ is unsatisfiable for all $\epsilon$, then by
compactness, $\varphi$ defines a continuous real-valued function on the
${\mathcal{L}}^{\prime}$-restrictions of ${\mathcal{L}}$-types in the
variables $\bar{x}$ and so by Proposition 7.5 applied to the real algebra of
${\mathcal{L}}^{\prime}$-formulas, $\varphi$ is $T$-equivalent to an
${\mathcal{L}}^{\prime}$-formula, which is the desired conclusion.

Based on the previous paragraph, we now suppose, towards a contradiction, that
$\Sigma_{\epsilon}$ is satisfiable for some $\epsilon>0$. We can thus find a
model $\mathcal{M}$ of $T$ and $\bar{a},\bar{b}\in\mathcal{M}$ such that
$\bar{a}$ and $\bar{b}$ have the same ${\mathcal{L}}^{\prime}$-type but
$\varphi^{\mathcal{M}}(\bar{a})\neq\varphi^{\mathcal{M}}(\bar{b})$.

Take an $|M|^{+}$-saturated elementary extension $\mathcal{N}$ of
$\mathcal{M}$. Let $\mathcal{M}^{\prime}$ and $\mathcal{N}^{\prime}$ be the
reducts of $\mathcal{M}$ and $N$ to ${\mathcal{L}}^{\prime}$. Since
$\mathcal{N}^{\prime}$ is also $|\mathcal{M}^{\prime}|^{+}$-saturated, we can
find an ${\mathcal{L}}^{\prime}$-elementary map
$\rho\colon\mathcal{M}^{\prime}\rightarrow N^{\prime}$ such that
$\rho(\bar{b})=\bar{a}$. Since $F$ is an equivalence of categories, $\rho$ is
also an ${\mathcal{L}}$-elementary map, which contradicts that
$\varphi^{\mathcal{M}}(\bar{a})\neq\varphi^{\mathcal{M}}(\bar{b})$. ∎

##  8\. Definable Sets

###  8.1. Introducing definable sets

We will now look at one of the biggest differences between continuous model
theory and classical model theory. In the classical setting, it is often
advantageous to be able to quantify over a subset of the universe which is
described by a formula. For instance, if $\varphi(x)$ is a formula expressing
some property, it is straightforward to also express "for all $x$, if
$\varphi(x)$ then …" or "there exists $x$ such that $\varphi(x)$ and …". In
the continuous setting, where formulas take on real values, the subsets over
which one can quantify is a delicate matter.

Suppose that $\mathcal{M}$ is an ${\mathcal{L}}$-structure and
$\varphi(\bar{x})$ is an ${\mathcal{L}}$-formula. The _zero-set of $\varphi$
in $\mathcal{M}$_, written $Z^{\mathcal{M}}(\varphi)$, is the set
$\\{\bar{a}\in\mathcal{M}\colon\varphi^{\mathcal{M}}(\bar{a})=0\\}$. Naively
one might think that one can quantify over zero sets of formulas, but as we
will soon see, that is not quite correct.

Suppose that $T$ is an ${\mathcal{L}}$-theory and $\bar{S}$ is a tuple of
sorts from ${\mathcal{L}}$. A _$T$ -functor (for $\bar{S}$)_ is a functor
$X\colon Mod(T)\rightarrow Met$, where $Met$ is the category of metric spaces
with isometric embeddings as morphisms, $X(\mathcal{M})$ is a closed subspace
of $\bar{S}(\mathcal{M})$, and if $\rho:\mathcal{M}\rightarrow\mathcal{N}$ is
an elementary map in $Mod(T)$, then $X(\rho)$ is the restriction of $\rho$ to
$X(\mathcal{M})$.

######  Example 8.1.

A natural example of a $T$-functor is $X_{\varphi}$ for some formula
$\varphi$, where
$X_{\varphi}(\mathcal{M})=Z(\varphi^{\mathcal{M}})=\\{\bar{a}\in\mathcal{M}\colon\varphi^{\mathcal{M}}(\bar{a})=0\\}$,
the zero set of $\varphi$.

######  Theorem 8.2.

Suppose that $T$ is an ${\mathcal{L}}$-theory and $X$ is a $T$-functor for
$\bar{S}$. The following are equivalent:

  1. (1)

There is a $T$-formula $\varphi(\bar{x})$ such that for any model
$\mathcal{M}$ of $T$ and any $\bar{a}\in\mathcal{M}$,

$\varphi^{\mathcal{M}}(\bar{a})=d(\bar{a},X(\mathcal{M})).$

  2. (2)

For any $T$-formula $\psi(\bar{x},\bar{y})$, there is a $T$-formula
$\chi(\bar{y})$ such that for any model $\mathcal{M}$ of $T$ and any
$\bar{a}\in\mathcal{M}$,

$\chi^{\mathcal{M}}(\bar{a})=\inf\\{\psi^{\mathcal{M}}(\bar{b},\bar{a})\colon\bar{b}\in
X(\mathcal{M})\\}$

(or equivalently the analogous statement replacing $\inf$ by $\sup$).

  3. (3)

For every $\epsilon>0$, there is a $T$-formula $\varphi(\bar{x})$ and
$\delta>0$ such that, for all models $\mathcal{M}$ of $T$:

     * •

$X(M)\subseteq Z(\varphi^{\mathcal{M}})$, and

     * •

For all $\bar{a}\in\mathcal{M}$, if $\varphi^{\mathcal{M}}(\bar{a})<\delta$,
then $d(\bar{a},X(\mathcal{M}))\leq\epsilon$.

  4. (4)

For every $\epsilon>0$, there is a basic ${\mathcal{L}}$-formula
$\varphi(\bar{x})$ and $\delta>0$ such that, for all models $\mathcal{M}$ of
$T$:

     * •

$X(\mathcal{M})\subseteq Z(\varphi^{\mathcal{M}})$, and

     * •

For all $\bar{a}\in\mathcal{M}$, if $\varphi^{\mathcal{M}}(\bar{a})<\delta$,
then $d(\bar{a},X(\mathcal{M}))\leq\epsilon$.

  5. (5)

For any set $I$, family of ${\mathcal{L}}$-structures $\mathcal{M}_{i}$ for
$i\in I$, and ultrafilter ${\mathcal{U}}$ on $I$,

$X(\mathcal{N})=\prod_{\mathcal{U}}X(\mathcal{M}_{i}),\text{ where
}\mathcal{N}=\prod_{\mathcal{U}}\mathcal{M}_{i}.$

######  Comment 8.3.

Before we begin the proof of Theorem 8.2, we want to address one small point.
What do we do with the empty functor, that is, the functor $X$ which satisfies
$X(\mathcal{M})=\emptyset$ for all models $\mathcal{M}$ of $T$? The empty
functor certainly satisfies condition (5) above; what about the other four
conditions? In condition (1) we must decide what the distance is to the empty
set - it should be the maximum possible value of the metric (and hence is
given by a formula). In (2), the $\inf$ is taken over an empty set hence
equals the maximum possible value of $\psi$ \- again, a formula. In (3) and
(4), we are measuring the distance to the empty set and so we again take this
to be the upper bound on the metric. Consequently, the empty functor satisfies
the equivalent conditions of Theorem 8.2 when conditions (1)-(4) are suitably
interpreted. Moreover, if $X$ satisfies any of the conditions of the theorem
and $X(\mathcal{M})$ is empty for some model $\mathcal{M}$ of $T$, then it is
empty for all models $\mathcal{M}$ of $T$ (and thus satisfies all of the other
conditions in the theorem).

###### Proof of Theorem 8.2.

Based on the previous comment, we can assume, without loss of generality, that
$X(\mathcal{M})\neq\emptyset$ for all models $\mathcal{M}$ of $T$.

The proof of (1) implies (2) can be found in [10, Theorem 9.17]. We only
remark that if $d_{X}(x)$ is a formula which expresses the distance from $x$
to $X$ in any model of $T$ and $\alpha$ is a uniform continuity modulus for
the formula $\psi$, then in any model $\mathcal{M}$ of $T$ (remembering that
$X(\mathcal{M})$ is not empty),
$\inf\\{\psi^{\mathcal{M}}(\bar{b},\bar{a})\colon\bar{b}\in X(\mathcal{M})\\}$
equals

$\inf_{\bar{b}\in\mathcal{M}}(\psi^{\mathcal{M}}(\bar{b},\bar{a})+\alpha(d^{\mathcal{M}}_{X}(\bar{b}))).$

It is easy to see that (2) implies (3). For (3) implies (4), it is enough to
remember that $T$-formulas are uniformly approximated by basic
${\mathcal{L}}$-formulas. To see that (4) implies (5), we first show that
$\prod_{\mathcal{U}}X(\mathcal{M}_{i})\subseteq X(\mathcal{N})$. To this end,
fix $\epsilon>0$ and let $\varphi$ and $\delta$ be as in (4). If
$[(a_{i})]_{\mathcal{U}}\in\prod_{\mathcal{U}}X(\mathcal{M}_{i})$, then
$\varphi^{\mathcal{M}_{i}}(a_{i})=0$ for all $i\in I$, hence
$\varphi^{\mathcal{N}}([a_{i}]_{\mathcal{U}})=0$ and thus
$d([(a_{i})]_{\mathcal{U}},X(\mathcal{N}))\leq\epsilon$. Since $\epsilon>0$
was arbitrary, we have that $[(a_{i})]_{\mathcal{U}}\in X(\mathcal{N})$. Now
suppose, towards a contradiction, that there is $[(a_{i})]_{\mathcal{U}}\in
X(\mathcal{N})\setminus\prod_{\mathcal{U}}X(\mathcal{M}_{i})$. Since
$\prod_{\mathcal{U}}X(\mathcal{M}_{i})$ is closed in $\mathcal{N}$, there is
$\epsilon>0$ such that
$d([(a_{i})]_{\mathcal{U}},\prod_{\mathcal{U}}X(\mathcal{M}_{i}))>\epsilon$.
Let $\varphi$ and $\delta>0$ be as in (4). Since $X(\mathcal{N})\subseteq
Z(\varphi^{\mathcal{N}})$, we have that
$\varphi^{\mathcal{M}_{i}}(a_{i})<\delta$ for ${\mathcal{U}}$-almost all $i\in
I$, hence $d(a_{i},X(\mathcal{M}_{i}))\leq\epsilon$ for ${\mathcal{U}}$-almost
all $i\in I$, which is a contradiction.

It remains to show that (5) implies (1). Let $\mathcal{C}$ be the class of
structures

$\\{(\mathcal{M},d_{X}^{\mathcal{M}})\colon\mathcal{M}\models T\\},$

where $d_{X}^{\mathcal{M}}$ measures the distance from an element to
$X(\mathcal{M})$. Note that measuring the distance to a closed set is indeed
an allowable relation in continuous logic: the bound is the maximum of the
bounds on the metrics in $\bar{S}$ and the modulus of uniform continuity is
the identity function. By Theorem 6.10, condition (5) guarantees that
$\mathcal{C}$ is an elementary class. The forgetful functor from $\mathcal{C}$
onto $Mod(T)$ is an equivalence of categories since any model of $T$ extends
uniquely to an object in $\mathcal{C}$. By the Beth Definability theorem, we
conclude that $d_{X}$ is in fact equivalent to a $T$-formula. ∎

If $X$ is a $T$-functor (for $\bar{S})$ satisfying any of the equivalent
conditions of the previous theorem, then we say that $X$ is a _$T$ -definable
set_. By condition (2) of the previous theorem, $(T$-)definable sets are
exactly those sets in metric structures over which one can quantify.

###  8.2. Examples and non-examples

We begin with some examples of definable sets.

######  Example 8.4.

Any sort is a definable set relative to any theory as is any finite product of
sorts. Perhaps less trivially, the range of any term is definable, since if we
are given a term $\tau(\bar{x})$ and we wish to quantify over the range of
$\tau$, for instance $\inf\\{\varphi^{\mathcal{M}}(y)\colon
y\in\text{range}(\tau^{\mathcal{M}})\\}$, we would evaluate
$\inf_{\bar{x}}\varphi(\tau(\bar{x}))$. This fact already pays dividends in
the case of operator algebras, where we can express any self-adjoint element
as $(x+x^{*})/2$ and any positive element as $x^{*}x$, hence both of these
sets of elements are definable relative to theory of
$\mathrm{C}^{*}$-algebras.

######  Example 8.5.

A slightly less trivial example is that the set of projections is definable
relative to the class of $\mathrm{C}^{*}$-algebras. Recall that the element
$p$ in a $\mathrm{C}^{*}$-algebra $A$ is a projection if it is self-adjoint
and satisfies $p^{2}=p$. To see that the set of projections is definable, we
use some functional calculus. Suppose we have a self-adjoint element $b$ in
some $\mathrm{C}^{*}$-algebra $A$ satisfying $\|b^{2}-b\|<\epsilon$, where
$\epsilon<1/4$. We know that the subalgebra $B$ of $A$ generated by $b$ and
$1_{A}$ is isomorphic to $C(\sigma(b))$ by an isomorphism sending $b$ to the
identity function and $1_{A}$ to the constant function $1$, where $\sigma(b)$
is the spectrum of $b$ and $C(\sigma(b))$ is the $\mathrm{C}^{*}$-algebra of
complex-valued continuous functions on $\sigma(b)$. By applying the
isomorphism, in $C(\sigma(b))$, we have $\|x^{2}-x\|<\epsilon$ and so
$\sigma(b)$ can be partitioned into two disjoint open sets $O_{0}$ and $O_{1}$
with $i\in O_{i}$ for $i=0,1$. If we let $\pi$ be the function which is
constantly $i$ on $O_{i}$, then this is a continuous function on $\sigma(b)$.
Additionally, $\pi$ is a projection and $\|\pi-x\|<\epsilon$. Pulling the
isomorphism from $C(\sigma(b))$ back into $B$, we find a projection $p\in B$
such that $\|b-p\|<\epsilon$. By Theorem 8.2 (3), the set of projections is
definable relative to the theory of $\mathrm{C}^{*}$-algebras.

We now give two non-examples to demonstrate that the notion of definable set
is quite distinct from the notion of zero set. The first is a somewhat
abstract example.

######  Example 8.6.

The structure $\mathcal{M}$ has a single sort with underlying set $[0,1]$
equipped with the discrete metric and a single relation symbol $R$ which is
interpreted as $R(x)=x$. Let $T=Th(\mathcal{M})$ and consider the $T$-functor
$X$, for $\mathcal{N}\in Mod(T)$, defined by
$X(\mathcal{N})=\\{a\in\mathcal{N}\colon R^{\mathcal{N}}(a)\leq 1/2\\}$. There
are a variety of ways to see that $X$ is not definable. We will use the
ultraproduct characterization. Notice that if ${\mathcal{U}}$ is a non-
principal ultrafilter on ${\mathbf{N}}$, then the sequence
$(1/2+1/n:n\in{\mathbf{N}})$ has $R$-value $1/2$ in
$\mathcal{M}^{\mathcal{U}}$ but the distance from this element to every
element in $[0,1/2]^{\mathcal{U}}$ is 1. This shows that
$X(\mathcal{M})^{\mathcal{U}}\neq X(M^{\mathcal{U}})$ and so $X$ is not
$T$-definable.

######  Example 8.7.

An example that appears in [18] in the context of $\mathrm{C}^{*}$-algebras is
the set of normal elements. In a $\mathrm{C}^{*}$-algebra, the element $a$ is
said to be normal if it commutes with its adjoint, hence we are looking at the
zero set of $\|a^{*}a-aa^{*}\|$. The set of normal elements in a
$\mathrm{C}^{*}$-algebra is not definable. (See [18, Proposition 3.2.0.8] for
a proof.)

###  8.3. Principal types

For emphasis, we record the following remark made during Comment 8.3.

######  Proposition 8.8.

If $X$ is a $T$-definable set, then $X(\mathcal{M})$ is non-empty for some
model $\mathcal{M}$ of $T$ if and only if $X(\mathcal{M})$ is non-empty for
all models $\mathcal{M}$ of $T$.

The following proposition makes a connection between the logic topology and
the metric on $S_{\bar{x}}(T)$. We say that a (partial) type is _principal_
relative to a theory $T$ if the $T$-functor $X$ which sends $\mathcal{M}$ to
the set of realizations of $p$ in $\mathcal{M}$ is a $T$-definable set. By
Proposition 8.8, any principal type is realized in all models of $T$; the
converse of this statement is the continuous form of the omitting types
theorem (proven in Section 10 below), and uses the next result in a crucial
way.

######  Proposition 8.9.

For $p\in S_{\bar{x}}(T)$, the following are equivalent:

  1. (1)

$p$ is principal relative to $T$.

  2. (2)

Every $\epsilon$-ball around $p$ contains a logical open neighborhood of $p$.

  3. (3)

Every $\epsilon$-ball around $p$ has nonempty interior in the logic topology.

###### Proof.

If $p$ is principal, then (2) follows from Theorem 8.2 (4).

We now prove that (2) implies (1). This argument is based on the proof of [10,
Theorem 9.12]. Fix $n\in{\mathbf{N}}$ and consider a formula $\varphi_{n}(x)$
such that $p(\varphi_{n})=0$ and $p\in
O^{T}(\varphi_{n},(-\infty,\delta_{n}))\subseteq B(p,1/n)$. It follows that if
$\mathcal{M}$ is a model of $T$ and $a\in\mathcal{M}$ satisfies
$\varphi_{n}^{\mathcal{M}}(a)<\delta_{n}$, then $d(tp^{\mathcal{M}}(a),p)\leq
1/n$. Now consider the $T$-formula $P(x)$ defined by

$\sum_{n}\frac{|\varphi_{n}(x)|}{B_{n}2^{n}},$

where $B_{n}$ is the bound for the formula $\varphi_{n}$ (see Example 5.2).
Notice that, for all $\epsilon>0$, there is $\delta>0$ so that, for all models
$\mathcal{M}$ of $T$ and all $a\in\mathcal{M}$, if
$P^{\mathcal{M}}(a)<\delta$, then $d(tp^{\mathcal{M}}(a),p)<\epsilon$. Using
Proposition 3.2, we can find an increasing continuous function $\alpha$ with
$\alpha(0)=0$ such that $d(tp(a),p)\leq\alpha(P^{\mathcal{M}}(a))$ holds for
all models $\mathcal{M}$ of $T$ and all $a\in\mathcal{M}$. Setting
$D(x)=\inf_{y}(\alpha(P(y))+d(x,y))$, we claim that $D(x)=d(x,p(\mathcal{M}))$
for all models $\mathcal{M}$ of $T$.

To see this, first assume that $\mathcal{M}$ is $\omega$-saturated, which in
particular implies that for all $a\in\mathcal{M}$, we have
$d(a,p(\mathcal{M}))=d(tp^{\mathcal{M}}(a),p)$. Fix $a\in\mathcal{M}$; we
first show that $D^{\mathcal{M}}(a)\leq d(a,p(\mathcal{M}))$. Recalling that
$P(y)=0$ whenever $y$ realizes $p$, we see that

$D^{\mathcal{M}}(a)=(\inf_{y}(\alpha(P(y))+d(a,y)))^{\mathcal{M}}\leq\inf_{y\in
p(\mathcal{M})}d(a,y)=d(a,p(\mathcal{M})).$

Note that this inequality did not use the $\omega$-saturation assumption. For
the other inequality, given $b\in\mathcal{M}$, we have
$\alpha(P^{\mathcal{M}}(b))\geq d(tp^{\mathcal{M}}(b),p)=d(b,p(\mathcal{M}))$,
hence

$D^{\mathcal{M}}(a)=(\inf_{y}(\alpha(P(y))+d(a,y)))^{\mathcal{M}}\geq\inf_{y\in\mathcal{M}}(d(y,p(\mathcal{M}))+d(a,y))\geq
d(a,p(\mathcal{M})).$

Now suppose that $\mathcal{N}$ is an arbitrary model of $T$ and $\mathcal{M}$
an $\omega$-saturated elementary extension, hence
$D^{\mathcal{M}}(x)=d(x,p(\mathcal{M}))$ by the previous paragraph. We now
show that $D^{\mathcal{N}}(a)=d(a,p(\mathcal{N}))$ for all $a\in\mathcal{N}$.
As noted above, the inequality $D^{\mathcal{N}}(a)\leq d(a,p(\mathcal{N}))$
holds without the $\omega$-saturation assumption. For the other inequality,
fix $\epsilon>0$; we will show $d(a,p(\mathcal{N}))\leq
D^{\mathcal{N}}(a)+\epsilon$, which suffices by letting $\epsilon$ tend to 0.
Towards this end, first notice that if $a\in\mathcal{N}$ is such that
$P^{\mathcal{N}}(a)=0$, then $a$ realizes $p$ and so
$p(\mathcal{N})=Z(P^{\mathcal{N}})$.

Now choose $a=a_{0}\in\mathcal{N}$. We know that
$D^{\mathcal{M}}(a)=d(a,p(\mathcal{M}))$ which implies that there is
$c\in\mathcal{M}$ so that $D^{\mathcal{M}}(c)=0$ and
$d(a,c)=D^{\mathcal{M}}(a)$. So $\mathcal{M}$ satisfies
$\inf_{y}\max\\{D(y),|d(a,y)-D(a)|\\}$. By elementarity, we can choose
$a_{1}\in\mathcal{N}$ so that $D^{\mathcal{N}}(a_{1})\leq\frac{\epsilon}{8}$
and $|D^{\mathcal{N}}(a_{0})-d(a_{0},a_{1})|\leq\frac{\epsilon}{8}$. We
continue to create a Cauchy sequence $(a_{n})$ in $\mathcal{N}$ such that

  * •

$D^{\mathcal{N}}(a_{n})\leq\frac{\epsilon}{2^{n+2}}$, and

  * •

$|D^{\mathcal{N}}(a_{n})-d(a_{n},a_{n+1})|\leq\frac{\epsilon}{2^{n+2}}$.

Given that we have constructed $a_{n}$, we note that since
$D^{\mathcal{N}}(a_{n})\leq\frac{\epsilon}{2^{n+2}}$, in $\mathcal{M}$ we can
find $c$ realizing $p$ so that $D^{\mathcal{M}}(c)=0$ and
$D^{\mathcal{M}}(a_{n})=d(a_{n},c)$. By elementarity of $\mathcal{N}$ in
$\mathcal{M}$, we can construct $a_{n+1}$ satisfying the properties listed
above. By the completeness of $\mathcal{N}$, the sequence $(a_{n})$ has a
limit $b\in\mathcal{N}$ and by the continuity of $D^{\mathcal{N}}$, we have
that $D^{\mathcal{N}}(b)=0$, hence $b$ realizes $p$. We also conclude from our
two items that $d(a_{n},a_{n+1})\leq\frac{\epsilon}{2^{n+1}}$ for all $n$. We
thus have

$d(a,p(\mathcal{N}))\leq
d(a,b)=\lim_{n}d(a,a_{n})\leq\lim_{n}(d(a_{0},a_{1})+\sum_{j=1}^{n-1}d(a_{j},a_{j+1}))\leq
D^{\mathcal{N}}(a)+\epsilon.$

We have thus finished the proof that (2) implies (1).

The direction (2) implies (3) is trivial, so it remains to prove (3) implies
(2). Suppose that the nonempty logic open set $O^{T}(\varphi,(r,s))$ is
contained in the $\epsilon$-ball around $p$. Choose $r^{\prime}$ and
$s^{\prime}$ so that $r<r^{\prime}<s^{\prime}<s$ and such that, setting
$\psi(x)=\inf_{y}\max(r^{\prime}\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\
\varphi(y),\varphi(y)\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\
s^{\prime},d(x,y)\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\ \epsilon)$, we have
$p(\psi)=0$. It follows that $p$ belongs to the logic open set
$O^{T}(\psi,(-\infty,s^{\prime\prime}))$ for any $s^{\prime\prime}>0$; if
$r<r^{\prime}-s^{\prime\prime}$, $s^{\prime}+s^{\prime\prime}<s$ and
$s^{\prime\prime}<\epsilon$, then $O^{T}(\psi,(-\infty,s^{\prime\prime}))$ is
contained in the $3\epsilon$-ball around $p$. Since $\epsilon$ is arbitrary,
this proves (2). ∎

##  9\. Quantifier elimination

We say that a theory $T$ in a language ${\mathcal{L}}$ has _quantifier
elimination_ if, for every ${\mathcal{L}}$-formula $\varphi(\bar{x})$, there
is a quantifier-free ${\mathcal{L}}$-formula $\psi(\bar{x})$ which is
$T$-equivalent to $\varphi(\bar{x})$. In terms of basic
${\mathcal{L}}$-formulas, this says: for every $\epsilon>0$ and every basic
${\mathcal{L}}$-formula $\varphi(\bar{x})$, there is a quantifier-free basic
${\mathcal{L}}$-formula $\psi$ such that
$\|\varphi(\bar{x})-\psi(\bar{x})\|_{T}<\epsilon$.

We will give three characterizations of quantifier elimination. The first is
syntactical.

######  Proposition 9.1.

Suppose that $T$ is an ${\mathcal{L}}$-theory. Then $T$ has quantifier-
elimination if and only if every formula of the form
$\inf_{x}\varphi(x,\bar{y})$, where $\varphi(x,\bar{y})$ is a basic
${\mathcal{L}}$-formula, is $T$-equivalent to a quantifier-free
${\mathcal{L}}$-formula.

###### Proof.

The forward direction is immediate and the backward direction is proven by
induction on the formation of basic ${\mathcal{L}}$-formulas, the quantifier
case being taken care of by the backwards assumption and the connective case
being immediate. ∎

######  Proposition 9.2.

Suppose that $T$ is an ${\mathcal{L}}$-theory. Then $T$ has quantifier-
elimination if and only if whenever $\mathcal{M}$ is a model of $T$ and
$\bar{a},\bar{b}\in\mathcal{M}$ have the same values for basic atomic
formulas, then they satisfy the same complete type.

###### Proof.

This follows from Proposition 7.5 applied to the real algebra system of
quantifier-free formulas. ∎

######  Example 9.3.

We can use Proposition 9.2 to see that the theory $T$ of the Urysohn sphere
$U$ has quantifier elimination. Indeed, suppose that $\mathcal{N}$ is a model
of $T$ and $\bar{a},\bar{b}\in\mathcal{N}$ have the same quantifier-free type.
Without loss of generality, we can assume that $\mathcal{N}$ is separable and
thus we may further assume that $\mathcal{N}$ is $U$ itself by the back-and-
forth argument given in Example 5.14. Since $\bar{a}$ and $\bar{b}$ have the
same quantifier-free type, the map $f$ sending $\bar{a}\mapsto\bar{b}$ is an
isometry. Since $U$ is ultrahomogeneous, $f$ extends to an automorphism of
$U$, which implies that $\bar{a}$ and $\bar{b}$ have the same complete type in
$U$, as desired.

A more semantic characterization of quantifier elimination is given by the
following:

######  Proposition 9.4.

Suppose $T$ is an ${\mathcal{L}}$-theory. Then $T$ has quantifier elimination
if and only if $T$ has the property that whenever $\mathcal{M}$ is a model of
$T$, $\bar{a}$ and $\bar{b}\in\mathcal{M}$ have the same quantifier-free type,
then there is $\mathcal{N}$ with $\mathcal{M}\prec\mathcal{N}$ such that the
map sending $\bar{a}$ to $\bar{b}$ can be extended to an embedding of
$\mathcal{M}$ into $\mathcal{N}$.

Note that if $\mathcal{M}$ in the Proposition is separable then $\mathcal{N}$
could be taken to be $\mathcal{M}^{\mathcal{U}}$ where ${\mathcal{U}}$ is a
non-principal ultrafilter on ${\mathbf{N}}$.

###### Proof.

We leave the proof of the forward direction as an exercise to the reader and
sketch a proof of the backwards direction using Proposition 9.1. Fix a basic
quantifier-free ${\mathcal{L}}$-formula $\varphi(x,\bar{y})$. Suppose that for
some $\epsilon$, the following set of sentences is satisfiable:

$\\{|\psi(\bar{c})-\psi(\bar{d})|\colon\psi(\bar{y})\text{ is a basic
quantifier-free ${\mathcal{L}}$-formula}\\}\\\
\cup\\{\epsilon\buildrel\textstyle\ .\over{\hbox{ \vrule
height=3.0pt,depth=0.0pt,width=0.0pt}{\smash{-}}}\
|\inf_{x}\varphi(x,\bar{c})-\inf_{x}\varphi(x,\bar{d})|\\},$

where $\bar{c}$ and $\bar{d}$ are sequences of new constants. It follows that
there is a model $\mathcal{M}$ of $T$ and $\bar{a},\bar{b}\in\mathcal{M}$ with
the same quantifier-free type but
$(\inf_{x}\varphi)^{\mathcal{M}}(x,\bar{a})<(\inf_{x}\varphi)^{\mathcal{M}}(x,\bar{b})$.
By assumption, there is an elementary extension $\mathcal{N}$ of $\mathcal{M}$
such that the map $\bar{a}\mapsto\bar{b}$ extends to an embedding $f$ from
$\mathcal{M}$ to $\mathcal{N}$. However, if we choose $c\in\mathcal{M}$ such
that
$\varphi^{\mathcal{M}}(c,\bar{a})<(\inf_{x}\varphi)^{\mathcal{M}}(x,\bar{b})=(\inf_{x}\varphi)^{\mathcal{N}}(x,\bar{b})$,
then we have a contradiction when we consider the value of
$\varphi^{\mathcal{N}}(f(c),\bar{b})$.

Consequently, the above set of sentences cannot be satisfiable for any
$\epsilon$. By compactness, for any $\epsilon>0$, we can find, after some
manipulation, a quantifier-free basic formula $\psi(\bar{x})$ and $\delta>0$
such that, for any model $\mathcal{M}$ of $T$ and
$\bar{a},\bar{b}\in\mathcal{M}$,

$|\psi(\bar{a})-\psi(\bar{b})|<\delta\text{ implies
}|\inf_{x}\varphi(x,\bar{a})-\inf_{x}\varphi(x,\bar{b})|\leq\epsilon.$

By Proposition 7.5 applied to the real algebra system of quantifier-free
formulas, we have that $\inf_{x}\varphi(x,\bar{y})$ is equivalent to a
quantifier-free formula. By Proposition 9.1, $T$ has quantifier elimination. ∎

######  Exercise 9.5.

Prove the forward direction of the previous proposition.

######  Example 9.6.

We can use the previous proposition to show that theory of in-finite-
dimensional Hilbert spaces admits quantifier-elimination. (We leave it to the
reader as an exercise to verify that infinite-dimensionality is expressible in
continuous logic.) Indeed, suppose that $\mathcal{H}$ is an infinite-
dimensional Hilbert space and that $\bar{a},\bar{b}\in\mathcal{H}$ are tuples
with the same quantifier-free type. Letting $\mathcal{H}_{0}$ and
$\mathcal{H}_{1}$ denote the finite-dimensional subspaces of $\mathcal{H}$
generated by $\bar{a}$ and $\bar{b}$ respectively. It follows that the map
$a_{i}\mapsto b_{i}$ for $i=1,\ldots,n$ extends to an isomorphism
$\mathcal{H}_{0}\to\mathcal{H}_{1}$. Since $\mathcal{H}$ is infinite-
dimensional, we have that the dimension of the orthogonal complement
$\mathcal{H}_{0}^{\perp}$ of $\mathcal{H}_{0}$ in $\mathcal{H}$ is the same as
the dimension of the orthogonal complement $\mathcal{H}_{1}^{\perp}$ of
$\mathcal{H}_{1}$ in $\mathcal{H}$. Thus, mapping $\mathcal{H}_{0}^{\perp}$
isomorphically into $\mathcal{H}_{1}^{\perp}$ allows one to extend the
original mapping to an automorphism of $\mathcal{H}$. Note that in this
example, there is no need for an elementary extension; in more complicated
examples, passing to an elementary extension is in fact necessary.

##  10\. Imaginaries

In classical model theory, imaginary elements play an important role. The
construction of the theory $T^{eq}$ from $T$ creates the largest expansion of
$T$ for which the category of models is equivalent. Although somewhat more
complicated in the continuous setting, one can define imaginaries for metric
structures which have similar properties. We consider them in the next three
subsections.

###  10.1. Products

Fix a continuous language ${\mathcal{L}}$ and an ${\mathcal{L}}$-theory $T$.
Suppose that $\bar{S}=(S_{n}:n\in{\mathbf{N}})$ is a sequence of sorts from
${\mathcal{L}}$. We add one new sort $S$ to ${\mathcal{L}}$ to form