*This is an extended version of a paper with the same title which has appeared in the proceedings of the International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), 299–318 (2020).

# A duality theoretic view on limits of finite structures

Mai Gehrke  CNRS and Université Côte d’Azur, Nice, France<EMAIL_ADDRESS>,
Tomáš Jakl  Department of Computer Science and Technology, University of
Cambridge, UK<EMAIL_ADDRESS>and  Luca Reggio  Department of Computer
Science, University of Oxford, UK<EMAIL_ADDRESS>
###### Abstract.

A systematic theory of _structural limits_ for finite models has been
developed by Nešetřil and Ossona de Mendez. It is based on the insight that
the collection of finite structures can be embedded, via a map they call the
_Stone pairing_ , in a space of measures, where the desired limits can be
computed. We show that a closely related but finer grained space of measures
arises—via Stone-Priestley duality and the notion of types from model
theory—by enriching the expressive power of first-order logic with certain
“probabilistic operators”. We provide a sound and complete calculus for this
extended logic and expose the functorial nature of this construction.

The consequences are two-fold. On the one hand, we identify the logical gist
of the theory of structural limits. On the other hand, our construction shows
that the duality theoretic variant of the Stone pairing captures the adding of
a layer of quantifiers, thus making a strong link to recent work on semiring
quantifiers in logic on words. In the process, we identify the model theoretic
notion of _types_ as the unifying concept behind this link. These results
contribute to bridging the strands of logic in computer science which focus on
semantics and on more algorithmic and complexity related areas, respectively.

###### Key words and phrases:

Stone duality; finitely additive measures; structural limits; finite model
theory; formal languages; logic on words

Mai Gehrke acknowledges support from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation program (grant
agreement No.670624).

Tomáš Jakl has received partial support from the EPSRC grant EP/T007257/1.

Luca Reggio has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie grant
agreement No.837724.

##  1\. Introduction

While topology plays an important role, via Stone duality, in many parts of
semantics, topological methods in more algorithmic and complexity oriented
areas of theoretical computer science are not so common. One of the few
examples, the one we want to consider here, is the study of limits of finite
relational structures. We will focus on the _structural limits_ introduced by
Nešetřil and Ossona de Mendez [25, 27]. These provide a common generalisation
of various notions of limits of finite structures studied in probability
theory, random graphs, structural graph theory, and finite model theory. The
basic construction in this work is the so-called _Stone pairing_. Given a
relational signature $\sigma$ and a first-order formula $\varphi$ in the
signature $\sigma$ with free variables $v_{1},\dots,v_{n}$, define

$\left<\varphi,A\right>=\frac{|\\{\overline{a}\in A^{n}\mid
A\models\varphi(\overline{a})\\}|}{|A|^{n}}\qquad\parbox{130.0002pt}{\centering\emph{(the
probability that a random assignment in $A$ satisfies
$\varphi$)}.\@add@centering}$ (1)

Nešetřil and Ossona de Mendez view the map $A\mapsto\left<\mkern
1.5mu\text{-}\mkern 1.5mu,A\right>$ as an embedding of the finite
$\sigma$-structures into the space of probability measures over the Stone
space dual to the Lindenbaum–Tarski algebra of all first-order formulas in the
signature $\sigma$. This space is complete and thus provides the desired limit
objects for all sequences of finite structures which embed as Cauchy
sequences.

Another example of topological methods in an algorithmically oriented area of
computer science is the use of profinite monoids in automata theory. In this
setting, profinite monoids are the subject of the extensive theory, based on
theorems by Eilenberg and Reiterman, and used, among others, to settle
decidability questions [28]. In [7], it was shown that this theory may be
understood as an application of Stone duality, thus making a bridge between
semantics and more algorithmically oriented work. Bridging this semantics-
versus-algorithmics gap in theoretical computer science has since gained quite
some momentum, notably with the recent strand of research by Abramsky, Dawar
and co-workers [2, 3]. In this spirit, a natural question is whether the
structural limits of Nešetřil and Ossona de Mendez also can be understood
semantically, and in particular whether the topological component may be seen
as an application of Stone duality.

More precisely, recent work on understanding quantifiers in the setting of
logic on finite words [10] has shown that adding a layer of certain
quantifiers (such as classical and modular quantifiers) corresponds dually to
a space-of-measures construction. The measures involved are not classical but
only finitely additive and they take values in finite semirings rather than in
the unit interval. Nevertheless, this appearance of _measures as duals of
quantifiers_ begs the further question whether the spaces of measures in the
theory of structural limits may be obtained via Stone duality from a semantic
addition of certain quantifiers to classical first-order logic.

The purpose of this paper is to address this question. Our main result is that
the Stone pairing of Nešetřil and Ossona de Mendez is related by a retraction
to a Stone space of measures, which is dual to the Lindenbaum–Tarski algebra
of a logic fragment obtained from first-order logic by adding one layer of
probabilistic quantifiers, and which arises in exactly the same way as the
spaces of semiring-valued measures in logic on words. That is, the Stone
pairing, although originating from other considerations, may be seen as
arising by duality from a semantic construction.

A foreseeable hurdle is that spaces of measures are not zero-dimensional and
hence outside the scope of Stone duality. In fact, this issue stems from non-
zero dimensionality of the unit interval $[0,1]$, in which is the classical
measures are valued. This is well-known to cause problems e.g. in attempts to
combine non-determinism and probability in domain theory [20]. However, in the
structural limits of Nešetřil and Ossona de Mendez, at the base, one only
needs to talk about finite models equipped with normal distributions and thus
only the finite intervals
${\mathbf{\Gamma}}_{n}=\\{0,\frac{1}{n},\frac{2}{n},\dots,1\\}$ are involved.
A careful duality theoretic analysis identifies a codirected diagram (i.e., an
inverse limit system) based on these intervals compatible with the Stone
pairing. The resulting inverse limit, which we denote ${\mathbf{\Gamma}}$, is
a Priestley space. It comes equipped with an algebra-like structure, which
allows us to reformulate many aspects of the theory of structural limits in
terms of ${\mathbf{\Gamma}}$-valued measures as opposed to $[0,1]$-valued
measures.

Some interesting features of ${\mathbf{\Gamma}}$, dictated by the nature of
the Stone pairing and the ensuing codirected diagram, are that

  * •

${\mathbf{\Gamma}}$ is based on a version of $[0,1]$ in which the rationals
are doubled;

  * •

${\mathbf{\Gamma}}$ comes with section-retraction maps
${[0,1]}$${{\mathbf{\Gamma}}}$${[0,1]}$$\scriptstyle{\iota}$$\scriptstyle{\gamma}$;

  * •

the map $\iota$ is lower semicontinuous while the map $\gamma$ is continuous.

These features are a consequence of general theory and precisely allow us to
witness continuous phenomena relative to $[0,1]$ in the setting of
${\mathbf{\Gamma}}$.

### Our contribution

We show that the ambient space of measures for the structural limits of
Nešetřil and Ossona de Mendez can be obtained via _“adding a layer of
quantifiers”_ in a suitable enrichment of first-order logic. The conceptual
framework for seeing this is that of _types_ from classical model theory. More
precisely, we will see that a variant of the Stone pairing is a map into a
space of measures with values in a Priestley space ${\mathbf{\Gamma}}$.
Further, we show that this map is in fact the embedding of the finite
structures into the space of ($0$-)types of an extension of first-order logic,
which we axiomatise. On the other hand, ${\mathbf{\Gamma}}$-valued measures
and $[0,1]$-valued measures are tightly related by a retraction-section pair
which allows the transfer of properties. These results identify the logical
gist of the theory of structural limits and provide a new interesting
connection between logic on words and the theory of structural limits in
finite model theory.

### Outline of the paper.

In section 2 we briefly recall Stone-Priestley duality, its application in
logic via spaces of types, and the particular instance of logic on words
(needed only to show the similarity of the constructions featuring in logic on
words and in the theory of structural limits).

In Section 3 we introduce the Priestley space ${\mathbf{\Gamma}}$ with its
additional operations, and show that it admits $[0,1]$ as a retract (the
duality theoretic analysis justifying the structure of ${\mathbf{\Gamma}}$ is
deferred to the appendix). The spaces of ${\mathbf{\Gamma}}$-valued measures
are introduced in Section 4, and the retraction of ${\mathbf{\Gamma}}$ onto
$[0,1]$ is lifted to the appropriate spaces of measures.

In Section 5, we introduce the ${\mathbf{\Gamma}}$-valued Stone pairing and
make the link with logic on words. Further, we compare convergence in the
space of ${\mathbf{\Gamma}}$-valued measures with the one considered by
Nešetřil and Ossona de Mendez. In Section 6, we show that constructing the
space of ${\mathbf{\Gamma}}$-valued measures dually corresponds to enriching
the logic with probabilistic operators.

To avoid overburdening the reader with technical details, we have decided to
postpone the derivation of ${\mathbf{\Gamma}}$ and its structure until the
appendix. This derivation relies on extended Priestley duality and the theory
of canonical extensions, which we recall in Appendix A. This general theory is
then applied in Appendix B to explain how the space ${\mathbf{\Gamma}}$ and
its algebra-like structure are derived.

##  2\. Preliminaries

#### Notation.

Throughout this paper, if $X\xrightarrow{f}Y\xrightarrow{g}Z$ are functions,
their composition is denoted $g\cdot f$. For a subset $S\subseteq X$,
$f_{\mathord{\upharpoonright}S}\colon S\to Y$ is the obvious restriction.
Given any set $T$, $\raisebox{2.03998pt}{\Large$\wp$}(T)$ denotes its power-
set. Further, for a poset $P$, $P^{\mathrm{op}}$ is the poset obtained by
turning the order of $P$ upside down.

###  2.1. Stone-Priestley duality

In this paper, we will need Stone duality for bounded distributive lattices in
the order-topological form due to Priestley [29]. It is a powerful and well
established tool in the study of propositional logic and semantics of
programming languages, see e.g. [15, 1] for major landmarks and [8] for an
overview of the role of duality methods in logic and computer science. We
briefly recall how this duality works.

A _compact ordered space_ is a pair $(X,\leq)$ where $X$ is a compact space
and $\leq$ is a partial order on $X$ which is closed in the product topology
of $X\times X$. (Note that such a space is automatically Hausdorff.) A compact
ordered space is a _Priestley space_ provided it is _totally order-
disconnected_. That is, for all $x,y\in X$ such that $x\not\leq y$, there is a
_clopen_ (i.e. simultaneously closed and open) $C\subseteq X$ which is an up-
set for $\leq$, and satisfies $x\in C$ but $y\notin C$. We recall the
construction of the Priestley space of a distributive lattice
$D$.111Throughout, we assume all distributive lattices are bounded, with the
bottom and top elements denoted by $0$ and $1$, respectively. Further, lattice
homomorphisms are required to preserve these bounds.

A non-empty proper subset $F\subset D$ is a _prime filter_ if it is _(i)_
upward closed (in the natural order of $D$), _(ii)_ closed under finite meets,
and _(iii)_ if $a\vee b\in F$, either $a\in F$ or $b\in F$. Denote by $X_{D}$
the set of all prime filters of $D$. By Stone’s Prime Filter Theorem, the map

$\displaystyle\llbracket\mkern 1.5mu\text{-}\mkern 1.5mu\rrbracket\colon
D\to\raisebox{2.03998pt}{\Large$\wp$}(X_{D}),\ \ a\mapsto\llbracket
a\rrbracket\coloneqq\\{F\in X_{D}\mid a\in F\\}$

is an embedding. Priestley’s insight was that $D$ can be recovered from
$X_{D}$, if the latter is equipped with the inclusion order and the topology
generated by the sets of the form $\llbracket a\rrbracket$ and their
complements. This makes $X_{D}$ into a Priestley space—the _dual space_ of
$D$—and the map $\llbracket\mkern 1.5mu\text{-}\mkern 1.5mu\rrbracket$ is an
isomorphism between $D$ and the lattice of clopen up-sets of $X_{D}$.
Conversely, any Priestley space $X$ is the dual space of the lattice of its
clopen up-sets. We call the latter the _dual lattice_ of $X$.

This correspondence extends to morphisms: if $h\colon D_{1}\to D_{2}$ is a
lattice homomorphism, then $h^{-1}\colon X_{D_{2}}\to X_{D_{1}}$ is a
_morphism of Priestley spaces_ , i.e. a continuous monotone map. In the other
direction, if $f\colon X_{1}\to X_{2}$ is a morphism of Priestley, then
$f^{-1}$ is a lattice homomorphism from the lattice of clopen up-sets of
$X_{2}$ to the lattice of clopen up-sets of $X_{1}$.

Priestley duality states that the ensuing functors are quasi-inverse, hence
the category $\mathbf{DLat}$ of distributive lattices with homomorphisms is
dually equivalent to the category $\mathbf{Pries}$ of Priestley spaces and
continuous monotone maps. When restricting to Boolean algebras, we recover the
celebrated Stone duality between the full subcategory $\mathbf{BA}$ of
$\mathbf{DLat}$ defined by Boolean algebras, and the full subcategory
$\mathbf{BStone}$ of $\mathbf{Pries}$ on those objects carrying the identity
order. These can be identified with the _Boolean (Stone) spaces_ , i.e.
compact Hausdorff spaces in which the clopen subsets form a basis for the
topology.

${\mathbf{DLat}}$${\mathbf{Pries}^{\mathrm{op}}}$${\mathbf{BA}}$${\mathbf{BStone}^{\mathrm{op}}}$
Figure 1. Priestley and Stone dualities.

###  2.2. Stone duality and logic: type spaces

The _theory of types_ is an important tool for first-order logic. We briefly
recall the concept as it is closely related to, and provides the link between,
two otherwise unrelated occurrences of topological methods in theoretical
computer science.

Consider a first-order signature $\sigma$ and a first-order theory $T$ in this
signature. For each $n\in\mathbb{N}$, let $\mathrm{Fm}_{n}$ denote the set of
first-order formulas whose free variables are among
$\overline{v}=\\{v_{1},\dots,v_{n}\\}$, and let $\mathrm{Mod}_{n}(T)$ denote
the class of all pairs $(A,\alpha)$ where $A$ is a model of $T$ and $\alpha$
is an interpretation of $\overline{v}$ in $A$.

Then the satisfaction relation, $(A,\alpha)\models\varphi(\overline{v})$, is a
binary relation from $\mathrm{Mod}_{n}(T)$ to $\mathrm{Fm}_{n}$. It induces
the equivalence relations of elementary equivalence and logical equivalence on
these sets, respectively. That is,

$\qquad\qquad(A,\alpha)\equiv(A^{\prime},\alpha^{\prime}){\quad\text{iff}\quad}\forall\varphi(\overline{v})\in\mathrm{Fm}_{n}\
\
(A,\alpha)\models\varphi(\overline{v})\iff(A^{\prime},\alpha^{\prime})\models\varphi(\overline{v})$

and

$\qquad\qquad\varphi(\overline{v})\approx\psi(\overline{v}){\quad\text{iff}\quad}\forall(A,\alpha)\in\mathrm{Mod}_{n}(T)\
\
(A,\alpha)\models\varphi(\overline{v})\iff(A,\alpha)\models\psi(\overline{v}).$

The quotient $\mathrm{FO}_{n}(T)\coloneqq\mathrm{Fm}_{n}/{\approx}$ carries a
natural Boolean algebra structure and is known as the _$n$ -th
Lindenbaum–Tarski algebra_ of $T$, while
$\operatorname{Typ}_{n}(T)\coloneqq\mathrm{Mod}_{n}/{\equiv}$ is naturally
endowed with a topology, generated by the sets
$\llbracket\varphi(\overline{v})\rrbracket\coloneqq\\{[(A,\alpha)]\mid(A,\alpha)\models\varphi(\overline{v})\\}$
for $\varphi(\overline{v})\in\mathrm{Fm}_{n}$, and is known as the _space of
$n$-types_ of $T$. Often, the Lindenbaum–Tarski algebra is defined by
quotienting $\mathrm{Fm}_{n}$ with respect to provable equivalence, where
$\varphi(\overline{v})$ and $\psi(\overline{v})$ are provably equivalent
(modulo $T$) if
$T\vdash\varphi(\overline{v})\leftrightarrow\psi(\overline{v})$. Gödel’s
completeness theorem states that these two quotient algebras are isomorphic
or, equivalently, that $\operatorname{Typ}_{n}(T)$ is the Stone dual of
$\mathrm{Fm}_{n}$ modulo provable equivalence.

The Boolean algebra $\mathrm{FO}(T)$ of _all_ first-order formulas modulo
logical equivalence over $T$ is the directed colimit of the
$\mathrm{FO}_{n}(T)$ for $n\in\mathbb{N}$ while its dual space,
$\operatorname{Typ}(T)$, is the codirected limit of the
$\operatorname{Typ}_{n}(T)$ for $n\in\mathbb{N}$ and consists of (equivalence
classes of) models equipped with interpretations of the full set of variables.

Now, consider the set $\mathrm{Fin}(T)$ consisting of isomorphism classes of
finite $T$-models. Because two finite models are elementarily equivalent
precisely when they are isomorphic, $\mathrm{Fin}(T)$ can be identified with a
subset of the space $\operatorname{Typ}_{0}(T)$ of $0$-types of $T$. If we
want to study finite models, there are two equivalent approaches: e.g. at the
level of sentences, we can either consider the theory $T_{\text{\em fin}}$ of
finite $T$-models, or the topological closure of $\mathrm{Fin}(T)$ in the
space $\operatorname{Typ}_{0}(T)$. This closure yields a space, which should
tell us about finite $T$-structures. Indeed, it is equal to
$\operatorname{Typ}_{0}(T_{\text{\em fin}})$, the space of pseudofinite
$T$-structures. For an application of this, see [16]. Below, we will see an
application in finite model theory of the case $T=\emptyset$ (in this case we
write $\mathrm{FO}(\sigma)$ and $\operatorname{Typ}(\sigma)$ instead of
$\mathrm{FO}(\emptyset)$ and $\operatorname{Typ}(\emptyset)$).

In light of the theory of types as exposed above, the Stone pairing of
Nešetřil and Ossona de Mendez (equation (1)) can be seen as an embedding of
finite structures into the space of finitely additive probability measures on
$\operatorname{Typ}(\sigma)$, which set-theoretically are finitely additive
functions $\mathrm{FO}(\sigma)\to[0,1]$. In fact, we will see that a finer
grained variant of the Stone pairing corresponds precisely to embedding finite
structures into the space of $0$-types of an extension of first-order logic,
cf. Theorem 6.5 and the discussion that follows the theorem.

###  2.3. Duality and logic on words

As mentioned in the introduction, spaces of measures arise via duality in the
study of semiring quantifiers in _logic on words_ [10]. In Section 5.1, we
will show that basically the same construction yields the Stone pairing of
Nešetřil and Ossona de Mendez. To make this analogy precise, here we provide a
brief overview of logic on words and the role of measure spaces. As the
technical development of the paper is independent from this material, the
reader can safely defer the reading of this section.

Logic on words, as introduced by Büchi, see e.g. [23] for a recent survey, is
a variation and specialisation of finite model theory where only models based
on words are considered. _I.e._ , a word $w\in A^{*}$ is seen as a relational
structure on $\\{1,\ldots,|w|\\}$, where $|w|$ is the length of $w$, equipped
with a unary relation $P_{a}$, for each $a\in A$, singling out the positions
in the word where the letter $a$ appears. Each sentence $\varphi$ in a
language interpretable over these structures yields a language
$L_{\varphi}\subseteq A^{*}$ consisting of the words satisfying $\varphi$.
Thus, logic fragments are considered modulo the theory of finite words and the
Lindenbaum–Tarski algebras are subalgebras of
$\raisebox{2.03998pt}{\Large$\wp$}(A^{*})$ consisting of the appropriate
$L_{\varphi}$’s, cf. [16] for a treatment of first-order logic on words.

For lack of logical completeness, the duals of the Lindenbaum–Tarski algebras
have more points than those given by models. Nevertheless, the dual spaces of
types, which act as compactifications and completions of the collections of
models, provide a powerful tool for studying logic fragments by topological
means. The central notion is that of _recognition_ , in which a Boolean
subalgebra
$\operatorname{\mathcal{B}}\subseteq\raisebox{2.03998pt}{\Large$\wp$}(A^{*})$
is studied by means of the dual map $\eta\colon\beta(A^{*})\to
X_{\operatorname{\mathcal{B}}}$. Here $\beta(A^{*})$ is the Stone dual of
$\raisebox{2.03998pt}{\Large$\wp$}(A^{*})$, also known in topology as the
Čech-Stone compactification of the discrete space $A^{*}$, and
$X_{\operatorname{\mathcal{B}}}$ is the Stone dual of
$\operatorname{\mathcal{B}}$. The set $A^{*}$ embeds in $\beta(A^{*})$, and
$\eta$ is uniquely determined by its restriction $\eta_{0}\colon A^{*}\to
X_{\operatorname{\mathcal{B}}}$. Now, Stone duality implies that $L\subseteq
A^{*}$ is in $\operatorname{\mathcal{B}}$ precisely when there is a clopen
subset $V\subseteq X_{\operatorname{\mathcal{B}}}$ so that
$\eta_{0}^{-1}(V)=L$. Anytime the latter is true for a map $\eta$ and a
language $L$ as above, one says that _$\eta$ recognises $L$_.222Here, being
beyond the scope of this paper, we are ignoring the important role of the
monoid structure available on the spaces (in the form of profinite monoids or
BiMs, cf. [16, 10]).

When studying logic fragments via recognition, the following inductive step is
central: given a notion of quantifier and a recogniser for a Boolean algebra
of formulas with a free variable, construct a recogniser for the Boolean
algebra generated by the formulas obtained by applying the quantifier. This
problem was solved in [10], using duality theory, in a general setting of
_semiring quantifiers_. The latter are defined as follows: let
$(S,+,\cdot,0_{S},1_{S})$ be a semiring, and $k\in S$. Given a formula
$\psi(v)$, the formula $\exists_{S,k}v.\psi(v)$ is true of a word $w\in A^{*}$
if, and only if,

$\underbrace{1_{S}+\cdots+1_{S}}_{\text{$m$ times}}=k$

where $m$ is the number of assignments of the variable $v$ in $w$ satisfying
$\psi(v)$. If $S=\mathbb{Z}/q\mathbb{Z}$, we obtain the so-called _modular
quantifiers_ , and for $S$ the two-element lattice we recover the existential
quantifier $\exists$.

To deal with formulas with a free variable, one considers maps of the form

$f\colon\beta((A\times 2)^{*})\to X,$

where the extra bit in $A\times 2$ is used to mark the interpretation of the
free variable. In [10] (see also [11]), it was shown that $L_{\psi(v)}$ is
recognised by $f$ if, and only if, for every $k\in S$ the language
$L_{\exists_{S,k}v.\psi(v)}$ is recognised by the composite

$\xi\colon
A^{*}\xrightarrow{\mathmakebox[3em]{R}}\widehat{\mathbf{S}}(\beta((A\times
2)^{*}))\xrightarrow{\mathmakebox[3em]{\widehat{\mathbf{S}}(f)}}\widehat{\mathbf{S}}(X),$
(2)

where $\widehat{\mathbf{S}}(X)$ is the space of finitely additive $S$-valued
measures on $X$, and $R$ maps $w\in A^{*}$ to the measure
$\mu_{w}\colon\raisebox{2.03998pt}{\Large$\wp$}((A\times 2)^{*})\to S$ sending
$K\subseteq(A\times 2)^{*}$ to the sum $1_{S}+\cdots+1_{S}$, $n_{w,K}$ times.
Here, $n_{w,K}$ is the number of interpretations $\alpha$ of the free variable
$v$ in $w$ such that the pair $(w,\alpha)$, seen as an element of $(A\times
2)^{*}$, belongs to $K$. Finally, $\widehat{\mathbf{S}}(f)$ sends a measure to
its pushforward along $f$.

##  3\. The space ${\mathbf{\Gamma}}$

Nešetřil and Ossona de Mendez observed in [25] that the Stone pairing
$\left<\mkern 1.5mu\text{-}\mkern 1.5mu,\mkern 1.5mu\text{-}\mkern
1.5mu\right>$ (cf. equation (1)), with its second argument fixed, yields a
finitely additive function $\mathrm{FO}(\sigma)\to[0,1]$. In other words,
given two first-order formulas $\varphi$ and $\psi$ and a finite
$\sigma$-structure $A$,

$\left<\varphi,A\right>+\left<\psi,A\right>=\left<\varphi\vee\psi,A\right>+\left<\varphi\wedge\psi,A\right>$

and also $\left<\mathbf{f},A\right>=0$ and $\left<\mathbf{t},A\right>=1$,
where $\mathbf{f}$ and $\mathbf{t}$ denote false and true, respectively. By
Stone duality, we can identify $\mathrm{FO}(\sigma)$ with the Boolean algebra
of clopen subsets of the space of types $\operatorname{Typ}(\sigma)$. By
assuming that clopen (equivalently, first-order definable) subsets of
$\operatorname{Typ}(\sigma)$ form the Boolean algebra of measurable subsets,
we view $\operatorname{Typ}(\sigma)$ as a measurable space. Then, assigning to
the second argument of the Stone pairing yields an embedding of
$\mathrm{Fin}(\sigma)$, the set of isomorphism classes of finite
$\sigma$-structures, into the space of finitely additive measures:

$\mathrm{Fin}(\sigma)\to\operatorname{\mathcal{M}_{I}}(\operatorname{Typ}(\sigma)),\qquad
A\mapsto\left<\mkern 1.5mu\text{-}\mkern 1.5mu,A\right>.$

The main obstacle in being able to use duality theory to investigate the
logical nature of the space
$\operatorname{\mathcal{M}_{I}}(\operatorname{Typ}(\sigma))$ is the fact that
this space is not zero-dimensional, and thus not amenable to the usual duality
theoretic methods. This is a direct consequence of the fact that
$\operatorname{\mathcal{M}_{I}}(\operatorname{Typ}(\sigma))$ is a closed
subspace of the product $[0,1]^{\mathrm{FO}(\sigma)}$, and thus inherits most
of its topological properties from the unit interval $[0,1]$. Consequently, in
order to exploit duality theory, e.g. in the form of Priestley duality, we
need to find a suitable Priestley space ${\mathbf{\Gamma}}$ that will play the
role of the unit interval.

The construction of ${\mathbf{\Gamma}}$ comes from the insight that the range
of the Stone pairing $\left<\mkern 1.5mu\text{-}\mkern 1.5mu,A\right>$, for a
finite $\sigma$-structure $A$ and formulas restricted to a fixed number of
free variables, can be confined to a chain of the form

${\mathbf{\Gamma}}_{n}=\\{0,\frac{1}{n},\frac{2}{n},\dots,1\\},$

where $n=|A|^{k}$ if $k$ is the number of free variables. Each
${\mathbf{\Gamma}}_{n}$, with the obvious total order and the discrete
topology, is a Priestley space. To allow for formulas with any number of free
variables, we require that ${\mathbf{\Gamma}}$ is obtained as a codirected
limit of all finite chains ${\mathbf{\Gamma}}_{n}$. If the maps in the
codirected diagram, say ${\mathbf{\Gamma}}_{m}\to{\mathbf{\Gamma}}_{n}$, are
monotone, we are guaranteed that ${\mathbf{\Gamma}}$ is a Priestley space, see
e.g. [17, Corollary VI.3.3]. There are two natural candidates for such maps,
namely the floor and ceiling functions

$\lfloor\mkern 1.5mu\text{-}\mkern
1.5mu\rfloor\colon{\mathbf{\Gamma}}_{nm}\twoheadrightarrow{\mathbf{\Gamma}}_{n}{\quad\text{and}\quad}\lceil\mkern
1.5mu\text{-}\mkern
1.5mu\rceil\colon{\mathbf{\Gamma}}_{nm}\twoheadrightarrow{\mathbf{\Gamma}}_{n}$

which send $\frac{a}{nm}$ to $\frac{b}{n}$ where $b=\lfloor a/m\rfloor$ and
$b=\lceil a/m\rceil$, respectively.

Lastly, we require that ${\mathbf{\Gamma}}$ comes equipped with some algebraic
structure which is rich enough so that we can define
${\mathbf{\Gamma}}$-valued measures. Since ${\mathbf{\Gamma}}$ will be
computed as a limit of the finite chains ${\mathbf{\Gamma}}_{n}$, the natural
way to identify this algebraic structure is to analyse the arithmetic
operations available on those finite chains. Given that we need to represent
finite additivity, it is natural to consider partial addition $x+y$ on
${\mathbf{\Gamma}}_{n}$, defined whenever $x+y\leq 1$.333Measures valued in
partial monoids have been considered in several places in the literature, see
e.g. [4]. The partial addition on ${\mathbf{\Gamma}}_{n}$ behaves well in many
respects, and even has a right adjoint:

$x+y\leq z\iff x\leq z-y$

where $z-y$ is the partial subtraction defined whenever $y\leq z$. However,
partial addition is not compatible with floor and ceiling functions. Indeed,
the operator dual to the partial addition on chains ${\mathbf{\Gamma}}_{n}$ is
not preserved by the lattice homomorphisms dual to the floor functions
$\lfloor\mkern 1.5mu\text{-}\mkern
1.5mu\rfloor\colon{\mathbf{\Gamma}}_{nm}\to{\mathbf{\Gamma}}_{n}$, nor by the
duals of the ceiling functions $\lfloor\mkern 1.5mu\text{-}\mkern
1.5mu\rfloor\colon{\mathbf{\Gamma}}_{nm}\to{\mathbf{\Gamma}}_{n}$. For more
details, see Appendix B.

On the other hand, as we shall now see, the partial subtraction is compatible
with floor functions. Note that, by the adjointness property stated above,
addition and subtraction are interdefinable, and so we preserve our ability to
express finite additivity. Let $L_{n}$ be the lattice dual to the Priestley
space ${\mathbf{\Gamma}}_{n}$, i.e. the lattice of up-sets of
${\mathbf{\Gamma}}_{n}$. In other words, $L_{n}$ is the finite chain

$L_{n}\enspace\cong\enspace(\bot<1<\frac{n-1}{n}<\dots<\frac{2}{n}<\frac{1}{n}<0).$

The following lemma provides a description of the operator on $L_{n}$ dual to
partial subtraction on ${\mathbf{\Gamma}}_{n}$, and relies on _extended_
Priestley duality between lattices with operators and Priestley spaces with
partial operations (or relations), see e.g. [15] and also [12, 13]. The
necessary background on extended Priestley duality, and a derivation of the
following fact, are offered in Appendix B.

######  Lemma 3.1.

The operator $\oplus\colon L_{n}\times L_{n}\to L_{n}$, defined by

$\frac{a}{n}\oplus\frac{b}{n}=\begin{cases}\bot&\text{ if }a+b>n\\\
\frac{a+b}{n}&\text{
otherwise}\end{cases}\quad{\quad\text{and}\quad}\quad\bot\oplus
u=u\oplus\bot=\bot$

is dual to the partial subtraction
$-\colon{\mathbf{\Gamma}}_{n}\times{\mathbf{\Gamma}}_{n}\rightharpoonup{\mathbf{\Gamma}}_{n}$
with domain $\mathrm{dom}(-)=\\{(z,x)\mid x\leq z\\}$.

It is immediate to see that the lattice homomorphisms dual to floor functions
are the lattice embeddings $i_{n,nm}\colon L_{n}\hookrightarrow L_{nm}$.
Moreover, these embeddings preserve $\oplus$, i.e.

$i_{n,nm}(u\oplus v)\enspace=\enspace i_{n,nm}(u)\oplus i_{n,nm}(v)$

for all $u,v\in L_{n}$. Note that this is not true for the duals of ceiling
functions (see Appendix B for details).

###  3.1. A concrete representation of ${\mathbf{\Gamma}}$.

In view of the discussion above, we define ${\mathbf{\Gamma}}$ as the limit of
the codirected diagram

$\\{\lfloor\mkern 1.5mu\text{-}\mkern
1.5mu\rfloor\colon{\mathbf{\Gamma}}_{mn}\twoheadrightarrow{\mathbf{\Gamma}}_{n}\mid
m,n\in\mathbb{N}\\},$

where $\mathbb{N}$ carries the (opposite of the) divisibility order. Since
this is a codirected diagram of finite discrete posets and monotone maps,
${\mathbf{\Gamma}}$ is naturally equipped with a structure of Priestley space,
see e.g. [17, Corollary VI.3.3]. The most lucid description of
${\mathbf{\Gamma}}$ is obtained by dualising this construction. Because the
category of Priestley spaces is dual to the category of distributive lattices,
${\mathbf{\Gamma}}$ is dual to the lattice obtained as the colimit
$\mathbf{L}$ of the directed system of lattice embeddings

$\\{i_{n,nm}\colon L_{n}\hookrightarrow L_{nm}\mid m,n\in\mathbb{N}\\}.$

The lattice $\mathbf{L}$ is given by

$\mathbf{L}=\\{\bot\\}\cup([0,1]\cap\mathbb{Q})^{\mathrm{op}},$

with $\bot<_{\mathbf{L}}q$ and $q\leq_{\mathbf{L}}p$ for every $p\leq q$ in
$[0,1]\cap\mathbb{Q}$. We can then identify the points of ${\mathbf{\Gamma}}$
with the prime filters of $\mathbf{L}$. Each $q\in[0,1]\cap\mathbb{Q}$ yields
a prime filter $q^{\circ}=\\{p\in\mathbf{L}\mid q\leq p\\}$, and each
$r\in(0,1]$ yields a prime filter $r^{-}=\\{p\in\mathbf{L}\mid r<p\\}$. It is
not difficult to see that all prime filters of $\mathbf{L}$ are of one of
these types, and so ${\mathbf{\Gamma}}$ can be represented as based on the set

$\\{r^{-}\mid r\in(0,1]\\}\cup\\{q^{\circ}\mid q\in[0,1]\cap\mathbb{Q}\\}.$

The order of ${\mathbf{\Gamma}}$ is the unique total order which has
$0^{\circ}$ as bottom element, satisfies $r^{*}<s^{*}$ if and only if $r<s$
for ${\scriptstyle\ast}\in\\{{\scriptstyle-},{\scriptstyle\circ}\\}$, and such
that $q^{\circ}$ is a cover of $q^{-}$ for every rational $q\in(0,1]$ (i.e.
$q^{-}<q^{\circ}$, and there is no element strictly in between). In a sense,
the elements of the form $q^{\circ}$ are regarded as _exact values_ , and
those of the form $r^{-}$ as _(lower) approximations_. Cf. Figure 2. The
topology of ${\mathbf{\Gamma}}$ is generated by the sets of the form

$\mathord{\uparrow}\mkern 1.0mup^{\circ}\coloneqq\\{x\in{\mathbf{\Gamma}}\mid
p^{\circ}\leq x\\}{\quad\text{and}\quad}\mathord{\downarrow}\mkern
1.0muq^{-}\coloneqq\\{x\in{\mathbf{\Gamma}}\mid x\leq q^{-}\\}$

for $p,q\in\mathbb{Q}\cap[0,1]$ such that $q\neq 0$.

$\bot$10$\mathbf{L}=$$r^{-}$$q^{\circ}$$q^{-}$$1^{\circ}$$1^{-}$$0^{\circ}$${\mathbf{\Gamma}}=$
Figure 2. The Priestley space ${\mathbf{\Gamma}}$ and its dual lattice
$\mathbf{L}$.

###  3.2. The algebraic structure on ${\mathbf{\Gamma}}$

Because the embeddings $i_{n,nm}\colon L_{n}\hookrightarrow L_{nm}$ preserve
the operators $\oplus\colon L_{n}\times L_{n}\to L_{n}$, the colimit lattice
$\mathbf{L}$ is naturally equipped with the operator
$\oplus\colon\mathbf{L}\times\mathbf{L}\to\mathbf{L}$ obtained by gluing
together all the operators on the finite sublattices $L_{n}$. By extended
Priestley duality, the operator $\oplus$ on $\mathbf{L}$ is dual to a pair of
partial operations $-$ and $\sim$ on ${\mathbf{\Gamma}}$.444Note that the
finite chains ${\mathbf{\Gamma}}_{n}$ come equipped, not only with the partial
subtraction $-$ as explained above, but also with a second partial operation
$\sim$. However, this additional piece of information is not needed in order
to recover $\oplus$ on $L_{n}$. This is a specific feature of finite lattices.
The first one, $-\colon\mathrm{\mathrm{dom}(-)}\to{\mathbf{\Gamma}}$, has
domain
$\mathrm{\mathrm{dom}(-)}=\\{(x,y)\in{\mathbf{\Gamma}}\times{\mathbf{\Gamma}}\mid
y\leq x\\}$ and is defined by

$\begin{aligned} r^{\circ}-s^{\circ}&\enspace=\enspace(r-s)^{\circ}\\\
r^{-}-s^{\circ}&\enspace=\enspace(r-s)^{-}\end{aligned}\qquad\qquad\begin{rcases*}r^{\circ}-s^{-}\\\
r^{-}-s^{-}\end{rcases*}\enspace=\enspace\begin{cases}(r-s)^{\circ}&\text{ if
}r-s\in\mathbb{Q}\\\ (r-s)^{-}&\text{ otherwise}.\end{cases}$

The second partial operation is definable in terms of $-$ and is given by

$\sim\colon\mathrm{\mathrm{dom}(-)}\to{\mathbf{\Gamma}},\ \ x\sim
y\coloneqq\bigvee{\\{x-q^{\circ}\mid y<q^{\circ}\leq x\\}}.$

Explicitly, we have $x\sim x=0^{\circ}$ and, whenever $y<x$,

$\displaystyle\begin{rcases*}r^{\circ}\sim s^{\circ}\\\ r^{-}\sim s^{-}\\\
r^{-}\sim s^{\circ}\end{rcases*}\enspace=\enspace(r-s)^{-},$
$\displaystyle\leavevmode\nobreak\ r^{\circ}\sim
s^{-}\enspace=\enspace\begin{cases}(r-s)^{\circ}&\text{ if
}r-s\in\mathbb{Q}\\\ (r-s)^{-}&\text{ otherwise}.\end{cases}$

The proof of the correspondence between $\oplus$ and the pair $(-,\sim)$ is
included in Appendix B.

The two partial operations on ${\mathbf{\Gamma}}$ have specific topological
and order-theoretic properties which are crucial in order to be able to
reconstruct $\oplus$. Moreover, we need both operations in order to recover
the classical $[0,1]$-valued measures as retracts of
${\mathbf{\Gamma}}$-valued measures (cf. the proof of Lemma 4.7 essential for
Theorem 4.10).

Here, we collect only the necessary properties of $-$ and $\sim$ needed in
Section 4. Recall that a map between ordered topological spaces is _lower_
(resp.  _upper_) _semicontinuous_ provided the preimage of any open down-set
(resp. open up-set) is open. The next lemma shows, in particular, that $-$ and
$\sim$ are semicontinuous, a key observation which will allows us to show that
the space of ${\mathbf{\Gamma}}$-valued measures is a Priestley space
(Proposition 4.3).

######  Lemma 3.2.

If $\mathrm{\mathrm{dom}(-)}$ is regarded as an ordered subspace of
${\mathbf{\Gamma}}\times{\mathbf{\Gamma}}{}^{\mathrm{op}}$, the following
hold:

  1. (1)

$\mathrm{\mathrm{dom}(-)}$ is a closed up-set in
${\mathbf{\Gamma}}\times{\mathbf{\Gamma}}{}^{\mathrm{op}}$;

  2. (2)

$-\colon\mathrm{\mathrm{dom}(-)}\to{\mathbf{\Gamma}}$ and
$\sim\colon\mathrm{\mathrm{dom}(-)}\to{\mathbf{\Gamma}}$ are monotone, i.e. if
$(x,y)\in\mathrm{\mathrm{dom}(-)}$, $x\leq x^{\prime}$ and $y^{\prime}\leq y$,
then $x-y\leq x^{\prime}-y^{\prime}$ and $x\sim y\leq x^{\prime}\sim
y^{\prime}$;

  3. (3)

$-\colon\mathrm{\mathrm{dom}(-)}\to{\mathbf{\Gamma}}$ is lower semicontinuous;

  4. (4)

$\sim\colon\mathrm{\mathrm{dom}(-)}\to{\mathbf{\Gamma}}$ is upper
semicontinuous.

###### Proof.

The properties (1)–(3) as stated above follow from the general theory of [12,
13] and we also included a direct proof in Appendix A. Item (4) requires extra
care because we extended the natural domain of definition of $\sim$ for our
application.

The general theory entails that the partial map $\sim^{\prime}$ defined as the
restriction of $\sim$ to $\\{(x,y)\mid y<x\\}$ is upper semicontinuous and
also that $\mathrm{dom}(\sim^{\prime})$ is an open up-set in
${\mathbf{\Gamma}}\times{\mathbf{\Gamma}}^{\mathrm{op}}$. To deduce (4), let
$q\in(0,1]\cap\mathbb{Q}$. Observe that $x=y$ implies that $x\sim
y=0^{\circ}\notin\mathord{\uparrow}\mkern 1.0muq^{\circ}$. Consequently, the
preimage of $\mathord{\uparrow}\mkern 1.0muq^{\circ}$ under $\sim$ is equal to
$(\sim^{\prime})^{-1}(\mathord{\uparrow}\mkern 1.0muq^{\circ})$, which is open
in the subspace topology of $\mathrm{dom}(\sim^{\prime})$. Since
$\mathrm{dom}(\sim^{\prime})$ is open in
${\mathbf{\Gamma}}\times{\mathbf{\Gamma}}$, the preimage
$(\sim)^{-1}(\mathord{\uparrow}\mkern 1.0muq^{\circ})$ is open in
${\mathbf{\Gamma}}\times{\mathbf{\Gamma}}$ and thus also open in the subspace
topology of $\mathrm{dom}(\sim)$. ∎

###  3.3. The retraction ${\mathbf{\Gamma}}\twoheadrightarrow[0,1]$

In this section we show that, with respect to appropriate topologies, the unit
interval $[0,1]$ can be obtained as a topological retract of
${\mathbf{\Gamma}}$, in a way which is compatible with the operation $-$. This
will be important in Sections 4 and 5, where we need to move between
[0,1]-valued and ${\mathbf{\Gamma}}$-valued measures. Let us define the
monotone surjection given by collapsing the doubled elements:

$\gamma\colon{\mathbf{\Gamma}}\to[0,1],\ \ r^{-},r^{\circ}\mapsto r.$ (3)

The map $\gamma$ has a right adjoint, given by

$\iota\colon[0,1]\to{\mathbf{\Gamma}},\
r\mapsto\begin{cases}r^{\circ}&\text{if }r\in\mathbb{Q}\\\
r^{-}&\text{otherwise}.\end{cases}$ (4)

Indeed, it is readily seen that, for all $y\in{\mathbf{\Gamma}}$ and
$x\in[0,1]$, $\gamma(y)\leq x$ if and only if $y\leq\iota(x)$. The composition
$\gamma\cdot\iota$ coincides with the identity on $[0,1]$, i.e. $\iota$ is a
section of $\gamma$. Moreover, this retraction lifts to a topological retract
provided we equip ${\mathbf{\Gamma}}$ and $[0,1]$ with the topologies
consisting of the open down-sets:

######  Lemma 3.3.

The map $\gamma\colon{\mathbf{\Gamma}}\to[0,1]$ is continuous and the map
$\iota\colon[0,1]\to{\mathbf{\Gamma}}$ is lower semicontinuous.

###### Proof.

To check continuity of $\gamma$ observe that, for $q\in\mathbb{Q}\cap(0,1)$,
the sets $\gamma^{-1}(q,1]$ and $\gamma^{-1}[0,q)$ coincide, respectively,
with the open sets

$\bigcup\\{\mathord{\uparrow}\mkern 1.0mup^{\circ}\mid
p\in\mathbb{Q}\cap[0,1]\text{ and
}q<p\\}{\enspace\text{and}\enspace}\bigcup\\{\mathord{\downarrow}\mkern
1.0mup^{-}\mid p\in\mathbb{Q}\cap(0,1]\text{ and }p<q\\}.$

Also, $\iota$ is lower semicontinuous, for
$\iota^{-1}(\mathord{\downarrow}\mkern 1.0muq^{-})=[0,q)$ whenever
$q\in\mathbb{Q}\cap(0,1]$. ∎

It is easy to see that both $\gamma$ and $\iota$ preserve the minus structure
available on ${\mathbf{\Gamma}}$ and $[0,1]$ (the unit interval is equipped
with the usual minus operation $x-y$ defined whenever $y\leq x$), that is,

  * •

$\gamma(x-y)=\gamma(x\sim y)=\gamma(x)-\gamma(y)$ whenever $y\leq x$ in
${\mathbf{\Gamma}}$, and

  * •

$\iota(x-y)=\iota(x)-\iota(y)$ whenever $y\leq x$ in $[0,1]$.

######  Remark 3.4.

$\iota\colon[0,1]\to{\mathbf{\Gamma}}$ is not upper semicontinuous because,
for every $q\in\mathbb{Q}\cap[0,1]$,

$\iota^{-1}(\mathord{\uparrow}\mkern 1.0muq^{\circ})=\\{x\in[0,1]\mid
q^{\circ}\leq\iota(x)\\}=\\{x\in[0,1]\mid\gamma(q^{\circ})\leq x\\}=[q,1].$

######  Remark 3.5.

The map $\gamma\colon{\mathbf{\Gamma}}\to[0,1]$ has, in addition to the right
adjoint $\iota$, also a left adjoint $\iota_{-}$, given by

$\iota_{-}\colon[0,1]\to{\mathbf{\Gamma}},\
x\mapsto\begin{cases}0^{\circ}&\text{if }x=0\\\
x^{-}&\text{otherwise}.\end{cases}$

The latter is also a section of $\gamma$, but in the following we shall mainly
work with the map $\iota$.

##  4\. Spaces of measures valued in ${\mathbf{\Gamma}}$ and in $[0,1]$

The aim of this section is to replace $[0,1]$-valued measures by
${\mathbf{\Gamma}}$-valued measures. The reason for doing this is two-fold.
First, the collection of all ${\mathbf{\Gamma}}$-valued measures is a
Priestley space (Proposition 4.3), and thus amenable to a duality theoretic
treatment and a dual logic interpretation (cf. Section 6). Second, it retains
more topological information than the space of $[0,1]$-valued measures.
Indeed, the former retracts onto the latter (Theorem 4.10).

Let $D$ be a distributive lattice. Recall that, classically, a monotone
function

$m\colon D\to[0,1]$

is a (finitely additive, probability) measure provided it satisfies $m(0)=0$,
$m(1)=1$, and $m(a)+m(b)=m(a\vee b)+m(a\wedge b)$ for all $a,b\in D$. The
latter property is equivalently expressed as

$\displaystyle\forall a,b\in D,\ \ m(a)-m(a\wedge b)=m(a\vee b)-m(b).$ (5)

We write $\operatorname{\mathcal{M}_{I}}(D)$ for the set of all measures
$D\to[0,1]$, and regard it as an ordered topological space, with the structure
induced by the product order and product topology of $[0,1]^{D}$. The notion
of (finitely additive, probability) ${\mathbf{\Gamma}}$-valued measure is
analogous to the classical one, except that the finite additivity property (5)
splits into two conditions, involving $-$ and $\sim$.

######  Definition 4.1.

Let $D$ be a distributive lattice. A _${\mathbf{\Gamma}}$ -valued measure_ (or
simply a _measure_) on $D$ is a function $\mu\colon D\to{\mathbf{\Gamma}}$
such that

  1. (1)

$\mu$ is monotone,

  2. (2)

$\mu(0)=0^{\circ}$ and $\mu(1)=1^{\circ}$, and

  3. (3)

for all $a,b\in D$,

$\mu(a)\sim\mu(a\wedge b)\leq\mu(a\vee b)-\mu(b){\enspace\text{ and
}\enspace}\mu(a)-\mu(a\wedge b)\geq\mu(a\vee b)\sim\mu(b).$

We denote by $\operatorname{\mathcal{M}_{\Gamma}}(D)$ the subset of
${\mathbf{\Gamma}}^{D}$ consisting of the measures $\mu\colon
D\to{\mathbf{\Gamma}}$.

Note that, if we only required one of the two inequalities in item (3) above,
we would essentially be considering finitely subadditive measures.

Since ${\mathbf{\Gamma}}$ is a Priestley space, so is ${\mathbf{\Gamma}}^{D}$
equipped with the product order and topology. Hence, we regard
$\operatorname{\mathcal{M}_{\Gamma}}(D)$ as an ordered topological space,
whose topology and order are induced by those of ${\mathbf{\Gamma}}^{D}$.
Explicitly, given measures $\mu,\nu\in\operatorname{\mathcal{M}_{\Gamma}}(D)$
we have $\mu\leq\nu$ if, and only if, $\mu(a)\leq\nu(a)$ for all $a\in D$.
Moreover, the topology of $\operatorname{\mathcal{M}_{\Gamma}}(D)$ is
generated by the sets of the form

$\llbracket
a<q\rrbracket\coloneqq\\{\nu\in\operatorname{\mathcal{M}_{\Gamma}}(D)\mid\nu(a)<q^{\circ}\\}$

and

$\llbracket a\geq
q\rrbracket\coloneqq\\{\nu\in\operatorname{\mathcal{M}_{\Gamma}}(D)\mid\nu(a)\geq
q^{\circ}\\},$

for all $a\in D$ and $q\in\mathbb{Q}\cap[0,1]$. Note that the sets $\llbracket
a<q\rrbracket$ are clopen down-sets, while the sets $\llbracket a\geq
q\rrbracket$ are clopen up-sets. It turns out that
$\operatorname{\mathcal{M}_{\Gamma}}(D)$ is a Priestley space (Proposition
4.3). The proof of this fact relies on the following lemma:

######  Lemma 4.2.

Let $X,Y$ be compact ordered spaces, $f\colon X\to Y$ a lower semicontinuous
function and $g\colon X\to Y$ an upper semicontinuous function. If
$X^{\prime}$ is a closed subset of $X$, then so is $\\{x\in X^{\prime}\mid
g(x)\leq f(x)\\}$.

###### Proof.

Whenever $g(x)\not\leq f(x)$ for some $x\in X$, there are an open down-set $U$
and open up-set $V$ of $Y$ which are disjoint and satisfy $f(x)\in U$ and
$g(x)\in V$. See e.g. [24, Theorem 4 p. 46]. Then, the open set $f^{-1}(U)\cap
g^{-1}(V)$ contains $x$ and is disjoint from $\\{x\in X\mid g(x)\leq f(x)\\}$.
Since $x$ was arbitrary, we conclude that the set $E\coloneqq\\{x\in X\mid
g(x)\leq f(x)\\}$ is closed. Therefore, if $X^{\prime}$ is a closed subset of
$X$, we deduce that $\\{x\in X^{\prime}\mid g(x)\leq f(x)\\}=E\cap X^{\prime}$
is also a closed subset of $X$. ∎

######  Proposition 4.3.

For any distributive lattice $D$, $\operatorname{\mathcal{M}_{\Gamma}}(D)$ is
a Priestley space.

###### Proof.

It suffices to show that $\operatorname{\mathcal{M}_{\Gamma}}(D)$ is a closed
subspace of ${\mathbf{\Gamma}}^{D}$. Let

$C_{1,2}\coloneqq\\{f\in{\mathbf{\Gamma}}^{D}\mid
f(0)=0^{\circ}\\}\cap\\{f\in{\mathbf{\Gamma}}^{D}\mid
f(1)=1^{\circ}\\}\cap\bigcap_{a\leq b}\\{f\in{\mathbf{\Gamma}}^{D}\mid
f(a)\leq f(b)\\}.$

Note that the evaluation maps
$\mathrm{ev}_{a}\colon{\mathbf{\Gamma}}^{D}\to{\mathbf{\Gamma}}$, $f\mapsto
f(a)$ are continuous for every $a\in D$. Thus, the first set in the
intersection defining $C_{1,2}$ is closed because it is the equaliser of the
evaluation map $\mathrm{ev}_{0}$ and the constant map of value $0^{\circ}$.
Similarly for the set $\\{f\in{\mathbf{\Gamma}}^{D}\mid f(1)=1^{\circ}\\}$.
The last set is the intersection of sets of the form
$\langle\mathrm{ev}_{a},\mathrm{ev}_{b}\rangle^{-1}(\leq)$, which are closed
because $\leq$ is closed in ${\mathbf{\Gamma}}\times{\mathbf{\Gamma}}$.
Whence, $C_{1,2}$ is a closed subset of ${\mathbf{\Gamma}}^{D}$. Moreover,

$\displaystyle\operatorname{\mathcal{M}_{\Gamma}}(D)=\bigcap_{a,b\in D}$
$\displaystyle\\{f\in C_{1,2}\mid f(a)\sim f(a\wedge b)\leq f(a\vee
b)-f(b)\\}$ $\displaystyle\cap\bigcap_{a,b\in D}$ $\displaystyle\\{f\in
C_{1,2}\mid f(a)-f(a\wedge b)\geq f(a\vee b)\sim f(b)\\}.$

From semicontinuity of $-$ and $\sim$ (Lemma 3.2), and Lemma 4.2, we conclude
that $\operatorname{\mathcal{M}_{\Gamma}}(D)$ is a closed subspace of
${\mathbf{\Gamma}}^{D}$. ∎

It turns out that the construction
$D\mapsto\operatorname{\mathcal{M}_{\Gamma}}(D)$ is functorial:

######  Lemma 4.4.

The assignment $D\mapsto\operatorname{\mathcal{M}_{\Gamma}}(D)$ can be
extended to a contravariant functor
$\operatorname{\mathcal{M}_{\Gamma}}\colon\mathbf{DLat}\to\mathbf{Pries}$ by
setting, for all lattice homomorphisms $h\colon D\to E$,

$\operatorname{\mathcal{M}_{\Gamma}}(h)\colon\operatorname{\mathcal{M}_{\Gamma}}(E)\to\operatorname{\mathcal{M}_{\Gamma}}(D),\
\ \mu\mapsto\mu\cdot h.$

###### Proof.

First, we show that if $h\colon D\to E$ is a lattice homomorphism and
$\mu\colon E\to{\mathbf{\Gamma}}$ is a measure, the composite map $\mu\cdot
h\colon D\to{\mathbf{\Gamma}}$ is also a measure. Since $\mu$ and $h$ are
monotone, so is $\mu\cdot h$. Further, $\mu(h(0))=\mu(0)=0^{\circ}$, and
$\mu(h(1))=\mu(1)=1^{\circ}$. For the third condition in Definition 4.1
observe that, for all $a,b\in D$,

$\displaystyle\mu(h(a))\sim\mu(h(a\wedge b))$
$\displaystyle=\mu(h(a))\sim\mu(h(a)\wedge h(b))$
$\displaystyle\leq\mu(h(a)\vee h(b))-\mu(h(b))$ $\displaystyle=\mu(h(a\vee
b))-\mu(h(b)),$

where the middle inequality holds because $\mu$ is a measure. The inequality

$\mu(h(a))-\mu(h(a\wedge b))\geq\mu(h(a\vee b))\sim\mu(h(b))$

is proved similarly. Thus, $\mu\cdot h\colon D\to{\mathbf{\Gamma}}$ is a
measure.

The mapping
$\operatorname{\mathcal{M}_{\Gamma}}(h)\colon\operatorname{\mathcal{M}_{\Gamma}}(E)\to\operatorname{\mathcal{M}_{\Gamma}}(D)$,
$\mu\mapsto\mu\cdot h$, is clearly monotone. With respect to continuity,
recall that the topology of $\operatorname{\mathcal{M}_{\Gamma}}(D)$ is
generated by the sets of the form $\llbracket
a<q\rrbracket=\\{\nu\in\operatorname{\mathcal{M}_{\Gamma}}(D)\mid\nu(a)<q^{\circ}\\}$
and $\llbracket a\geq
q\rrbracket=\\{\nu\in\operatorname{\mathcal{M}_{\Gamma}}(D)\mid\nu(a)\geq
q^{\circ}\\}$, with $a\in D$ and $q\in\mathbb{Q}\cap[0,1]$. We have

$\operatorname{\mathcal{M}_{\Gamma}}(h)^{-1}(\llbracket
a<q\rrbracket)=\\{\mu\in\operatorname{\mathcal{M}_{\Gamma}}(E)\mid\mu(h(a))<q^{\circ}\\}=\llbracket
h(a)<q\rrbracket$

which is open in $\operatorname{\mathcal{M}_{\Gamma}}(E)$. Similarly,
$\operatorname{\mathcal{M}_{\Gamma}}(h)^{-1}(\llbracket a\geq
q\rrbracket)=\llbracket h(a)\geq q\rrbracket$, showing that
$\operatorname{\mathcal{M}_{\Gamma}}(h)$ is continuous. Hence, in view of
Proposition 4.3, $\operatorname{\mathcal{M}_{\Gamma}}(h)$ is a morphism of
Priestley spaces. It is not difficult to see that identities and compositions
are preserved, therefore
$\operatorname{\mathcal{M}_{\Gamma}}\colon\mathbf{DLat}\to\mathbf{Pries}$ is a
contravariant functor. ∎

######  Remark 4.5.

We work with the contravariant functor
$\operatorname{\mathcal{M}_{\Gamma}}\colon\mathbf{DLat}\to\mathbf{Pries}$
because $\operatorname{\mathcal{M}_{\Gamma}}$ is concretely defined on the
lattice side. However, by Priestley duality, $\mathbf{DLat}$ is dually
equivalent to $\mathbf{Pries}$, so we can think of
$\operatorname{\mathcal{M}_{\Gamma}}$ as a covariant functor
$\mathbf{Pries}\to\mathbf{Pries}$ (this is the perspective traditionally
adopted in analysis, and also in the works of Nešetřil and Ossona de Mendez).
From this viewpoint, Section 6 provides a description of the endofunctor on
$\mathbf{DLat}$ dual to
$\operatorname{\mathcal{M}_{\Gamma}}\colon\mathbf{Pries}\to\mathbf{Pries}$.

Next, we establish a property of the functor
$\operatorname{\mathcal{M}_{\Gamma}}\colon\mathbf{DLat}\to\mathbf{Pries}$
which is very useful when approximating a fragment of a logic by smaller
fragments (see, e.g., Section 5.1).

######  Proposition 4.6.

The contravariant functor
$\operatorname{\mathcal{M}_{\Gamma}}\colon\mathbf{DLat}\to\mathbf{Pries}$
sends directed colimits to codirected limits.

###### Proof.

Let $D$ be the colimit in $\mathbf{DLat}$ of a directed diagram

$\\{h_{i,j}\colon D_{i}\to D_{j}\\}_{i\leq j},$

with colimit maps $\iota_{i}\colon D_{i}\to D$ (where $i$ and $j$ vary in a
directed poset $I$). We must show that the cone
$\\{\operatorname{\mathcal{M}_{\Gamma}}(\iota_{i})\colon\operatorname{\mathcal{M}_{\Gamma}}(D)\to\operatorname{\mathcal{M}_{\Gamma}}(D_{i})\\}_{i\in
I}$ is the limit of the diagram

$\big{\\{}\leavevmode\hbox to108.56pt{\vbox
to14.45pt{\pgfpicture\makeatletter\hbox{\hskip 54.27942pt\lower-8.3176pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}{}{}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{\offinterlineskip{}{}{{{}}{{}}}{{{}}}{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-57.27942pt}{-8.21776pt}\pgfsys@invoke{
}\hbox{\vbox{\halign{\pgf@matrix@init@row\pgf@matrix@step@column{\pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding&&\pgf@matrix@step@column{\pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding\cr\hfil\hskip
18.46535pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-15.46535pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{${\operatorname{\mathcal{M}_{\Gamma}}(D_{i})}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip
18.46535pt\hfil&\hfil\hskip 58.81412pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-15.81406pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{${\operatorname{\mathcal{M}_{\Gamma}}(D_{j})}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
18.81406pt\hfil\cr}}}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}{{{{}}}{{}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} {}{ {}{}{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.39998pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{{}}\pgfsys@moveto{19.45134pt}{-5.71776pt}\pgfsys@lineto{-19.74876pt}{-5.71776pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{-19.94875pt}{-5.71776pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-11.72849pt}{-1.26819pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{$\scriptstyle{\operatorname{\mathcal{M}_{\Gamma}}(h_{i,j})}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\big{\\}}_{i\leq j}.$

Let $Y$ be a Priestley space and $\\{g_{i}\colon
Y\to\operatorname{\mathcal{M}_{\Gamma}}(D_{i})\\}_{i\in I}$ a set of Priestley
morphisms such that $g_{i}=\operatorname{\mathcal{M}_{\Gamma}}(h_{i,j})\cdot
g_{j}$, for every $i\leq j$. We need to prove that there is a unique Priestley
morphism $\xi\colon Y\to\operatorname{\mathcal{M}_{\Gamma}}(D)$ such that
$\operatorname{\mathcal{M}_{\Gamma}}(\iota_{i})\cdot\xi=g_{i}$ for every $i$.

Note that, since directed colimits in $\mathbf{DLat}$ are computed in the
category of sets, for every element $a$ of $D$ there is an index $i\in I$ and
an element $a_{i}\in D_{i}$ such that $\iota_{i}(a_{i})=a$. Define

$\xi\colon Y\to\operatorname{\mathcal{M}_{\Gamma}}(D),\quad
y\mapsto\big{(}D\xrightarrow{\xi(y)}{\mathbf{\Gamma}},\ a\mapsto
g_{i}(y)(a_{i})\big{)},$

where $a_{i}$ satisfies $\iota(a_{i})=a$. This definition is independent of
the choice of $a_{i}$: for any other $a_{j}\in D_{j}$ such that
$\iota_{j}(a_{j})=a$, we have that $h_{i,k}(a_{i})=h_{j,k}(a_{j})$ for some
$k\geq i,j$, and so

$\displaystyle g_{i}(y)(a_{i})$ $\displaystyle=g_{k}(y)(h_{i,k}(a_{i}))$
$\displaystyle=g_{k}(y)(h_{j,k}(a_{j}))=g_{j}(y)(a_{j})$

for all $y\in Y$. Observe that, for every $y\in Y$, $\xi(y)$ is indeed a
measure $D\to{\mathbf{\Gamma}}$. For example, let $a,b\in D$. Then, because
$I$ is directed, there is an index $i$ such that $a=\iota_{i}(a_{i})$ and
$b=\iota_{i}(b_{i})$ for some $a_{i},b_{i}\in D_{i}$. Since $g_{i}(y)$ is a
measure, we have that

$\displaystyle\xi(y)(a)\sim\xi(y)(a\wedge b)$
$\displaystyle=g_{i}(y)(\iota_{i}(a_{i}))\sim
g_{i}(y)(\iota_{i}(a_{i})\wedge\iota_{i}(b_{i}))$ $\displaystyle\leq
g_{i}(y)(\iota_{i}(a_{i})\vee\iota_{i}(b_{i}))-g_{i}(y)(\iota_{i}(b_{i}))$
$\displaystyle=\xi(y)(a\vee b)-\xi(y)(b).$

The other properties are proved in the same spirit. Next, we show that $\xi$
is a Priestley morphism. Monotonicity is immediate: if $y\leq y^{\prime}$ in
$Y$ and $a_{i}\in D_{i}$, then

$\displaystyle\xi(y)(\iota_{i}(a_{i}))$ $\displaystyle=g_{i}(y)(a_{i})$
$\displaystyle\leq
g_{i}(y^{\prime})(a_{i})=\xi(y^{\prime})(\iota_{i}(a_{i})).$

For continuity, for all $a_{i}\in D_{i}$ and $q\in\mathbb{Q}\cap[0,1]$, we
have

$\displaystyle\xi^{-1}(\llbracket\iota_{i}(a_{i})<q\rrbracket)=\\{y\mid\xi(y)(\iota_{i}(a_{i}))<q^{\circ}\\}=\\{y\mid
g_{i}(y)(a_{i})<q^{\circ}\\}=g_{i}^{-1}(\llbracket a_{i}<q\rrbracket)$

and, similarly, $\xi^{-1}(\llbracket\iota_{i}(a_{i})\geq
q\rrbracket)=g_{i}^{-1}(\llbracket a_{i}\geq q\rrbracket)$. Lastly, we show
that $\xi$ is unique with these properties. Let $\lambda\colon
Y\to\operatorname{\mathcal{M}_{\Gamma}}(D)$ be a Priestley morphism such that
$g_{i}=\operatorname{\mathcal{M}_{\Gamma}}(\iota_{i})\cdot\lambda$ for every
$i\in I$. For every $a\in D$, and element $a_{i}\in D_{i}$ such that
$\iota_{i}(a_{i})=a$, we get

$\lambda(y)(a)=\lambda(y)(\iota_{i}(a_{i}))=g_{i}(y)(a_{i})=\xi(y)(\iota_{i}(a_{i}))=\xi(y)(a)$

for all $y\in Y$. Whence, $\lambda=\xi$. ∎

Recall the maps $\gamma\colon{\mathbf{\Gamma}}\to[0,1]$ and
$\iota\colon[0,1]\to{\mathbf{\Gamma}}$ from equations (3)–(4). In Section 3.3
we showed that this is a retraction-section pair. In Theorem 4.10 we will lift
this retraction to the spaces of measures. We start with an easy observation:

######  Lemma 4.7.

Let $D$ be a distributive lattice. The following statements hold:

  1. (1)

for every $\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D)$,
$\gamma\cdot\mu\in\operatorname{\mathcal{M}_{I}}(D)$,

  2. (2)

for every $m\in\operatorname{\mathcal{M}_{I}}(D)$, $\iota\cdot
m\in\operatorname{\mathcal{M}_{\Gamma}}(D)$.

###### Proof.

$(1)$ The only non-trivial condition to verify is finite additivity. As
pointed out after Lemma 3.3, the map $\gamma$ preserves both minus operations
on ${\mathbf{\Gamma}}$. Hence, for all $a,b\in D$, the inequalities
$\mu(a)\sim\mu(a\wedge b)\leq\mu(a\vee b)-\mu(b)$ and $\mu(a)-\mu(a\wedge
b)\geq\mu(a\vee b)\sim\mu(b)$ imply that
$\gamma\cdot\mu(a)-\gamma\cdot\mu(a\wedge b)=\gamma\cdot\mu(a\vee
b)-\gamma\cdot\mu(b)$.

$(2)$ The first two conditions in Definition 4.1 are immediate. The third
condition follows from the fact that $\iota(r-s)=\iota(r)-\iota(s)$ whenever
$s\leq r$ in $[0,1]$, and $x\sim y\leq x-y$ for every
$(x,y)\in\mathrm{\mathrm{dom}(-)}$. ∎

In view of the previous lemma, there are well-defined functions

$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(D)\to\operatorname{\mathcal{M}_{I}}(D),\
\mu\mapsto\gamma\cdot\mu\enspace\text{ and
}\enspace\iota^{\\#}\colon\operatorname{\mathcal{M}_{I}}(D)\to\operatorname{\mathcal{M}_{\Gamma}}(D),\
m\mapsto\iota\cdot m.$

######  Lemma 4.8.

$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(D)\to\operatorname{\mathcal{M}_{I}}(D)$
is a continuous and monotone map.

###### Proof.

The topology of $\operatorname{\mathcal{M}_{I}}(D)$ is generated by the sets
of the form $\\{m\in\operatorname{\mathcal{M}_{I}}(D)\mid m(a)\in O\\}$, for
$a\in D$ and $O$ an open subset of $[0,1]$. In turn,

$(\gamma^{\\#})^{-1}\\{m\in\operatorname{\mathcal{M}_{I}}(D)\mid m(a)\in
O\\}=\\{\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D)\mid\mu(a)\in\gamma^{-1}(O)\\}$

is open in $\operatorname{\mathcal{M}_{\Gamma}}(D)$ because
$\gamma\colon{\mathbf{\Gamma}}\to[0,1]$ is continuous by Lemma 3.3. This shows
that
$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(D)\to\operatorname{\mathcal{M}_{I}}(D)$
is continuous. Monotonicity is immediate. ∎

Note that
$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(D)\to\operatorname{\mathcal{M}_{I}}(D)$
is surjective, since it admits $\iota^{\\#}$ as a (set-theoretic) section. It
follows that $\operatorname{\mathcal{M}_{I}}(D)$ is a compact ordered space:

######  Corollary 4.9.

For each distributive lattice $D$, $\operatorname{\mathcal{M}_{I}}(D)$ is a
compact ordered space.

###### Proof.

The surjection
$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(D)\to\operatorname{\mathcal{M}_{I}}(D)$
is continuous (Lemma 4.8). Since $\operatorname{\mathcal{M}_{\Gamma}}(D)$ is
compact by Proposition 4.3, so is $\operatorname{\mathcal{M}_{I}}(D)$. The
order of $\operatorname{\mathcal{M}_{I}}(D)$ is clearly closed in the product
topology, thus $\operatorname{\mathcal{M}_{I}}(D)$ is a compact ordered space.
∎

Finally, we see that the set-theoretic retraction of
$\operatorname{\mathcal{M}_{\Gamma}}(D)$ onto
$\operatorname{\mathcal{M}_{I}}(D)$ lifts to the topological setting, provided
we restrict to the down-set topologies. If $(X,\leq)$ is a partially ordered
topological space, write $X^{\downarrow}$ for the space with the same
underlying set as $X$ and whose topology consists of the open down-sets of
$X$.

######  Theorem 4.10.

The maps
$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(D)^{\downarrow}\to\operatorname{\mathcal{M}_{I}}(D)^{\downarrow}$
and
$\iota^{\\#}\colon\operatorname{\mathcal{M}_{I}}(D)^{\downarrow}\to\operatorname{\mathcal{M}_{\Gamma}}(D)^{\downarrow}$
are a retraction-section pair of topological spaces.

###### Proof.

It suffices to show that $\gamma^{\\#}$ and $\iota^{\\#}$ are continuous. It
is not difficult to see, using Lemma 4.8, that
$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(D)^{\downarrow}\to\operatorname{\mathcal{M}_{I}}(D)^{\downarrow}$
is continuous. For the continuity of $\iota^{\\#}$, note that the topology of
$\operatorname{\mathcal{M}_{\Gamma}}(D)^{\downarrow}$ is generated by the sets
of the form $\llbracket a<q\rrbracket$, for $a\in D$ and
$q\in\mathbb{Q}\cap(0,1]$. We have

$\displaystyle(\iota^{\\#})^{-1}\llbracket a<q\rrbracket$
$\displaystyle=\\{m\in\operatorname{\mathcal{M}_{I}}(D)\mid
m(a)\in\iota^{-1}(\mathord{\downarrow}\mkern 1.0muq^{-})\\}$
$\displaystyle=\\{m\in\operatorname{\mathcal{M}_{I}}(D)\mid m(a)<q\\},$

which is an open set in $\operatorname{\mathcal{M}_{I}}(D)^{\downarrow}$. This
concludes the proof. ∎

##  5\. The ${\mathbf{\Gamma}}$-valued Stone pairing and limits of finite
structures

In the work of Nešetřil and Ossona de Mendez, the Stone pairing $\left<\mkern
1.5mu\text{-}\mkern 1.5mu,A\right>$ is $[0,1]$-valued, i.e. an element of
$\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$. In this section, we
show that basically the same construction for the recognisers arising from the
application of a layer of semiring quantifiers in logic on words (cf. Section
2.3) provides an embedding of finite $\sigma$-structures into the space of
${\mathbf{\Gamma}}$-valued measures. It turns out that this embedding is a
${\mathbf{\Gamma}}$-valued version of the Stone pairing. Hereafter we make a
notational difference, writing $\left<\mkern 1.5mu\text{-}\mkern 1.5mu,\mkern
1.5mu\text{-}\mkern 1.5mu\right>_{\mathrm{I}}$ for the (classical)
$[0,1]$-valued Stone pairing.

The main ingredient of the construction are the ${\mathbf{\Gamma}}$-valued
finitely supported functions. To start with, we point out that the partial
operation $-$ on ${\mathbf{\Gamma}}$ uniquely determines—by adjointness—a
partial “plus” operation on ${\mathbf{\Gamma}}$. Define

$+\colon\mathrm{\mathrm{dom}(+)}\to{\mathbf{\Gamma}},{\quad\text{where}\quad}\mathrm{\mathrm{dom}(+)}\coloneqq\\{(x,y)\mid
x\leq 1^{\circ}-y\\},$

by the following rules (whenever the expressions make sense):

$r^{\circ}+s^{\circ}=(r+s)^{\circ},\ \ r^{-}+s^{\circ}=(r+s)^{-},\ \
r^{\circ}+s^{-}=(r+s)^{-},{\enspace\text{and }\enspace}r^{-}+s^{-}=(r+s)^{-}.$

Then, for every $x\in{\mathbf{\Gamma}}$, the function $(\mkern
1.5mu\text{-}\mkern 1.5mu)+x$ sending $y$ to $y+x$ is left adjoint to the
function $(\mkern 1.5mu\text{-}\mkern 1.5mu)-x$ sending $y$ to $y-x$. This is
the content of the next lemma; for a proof, see the end of Appendix B.4.

######  Lemma 5.1.

For every $x\in{\mathbf{\Gamma}}$, the monotone map $(\mkern
1.5mu\text{-}\mkern 1.5mu)+x\colon[0^{\circ},1^{\circ}-x]\to[x,1^{\circ}]$ is
left adjoint to $(\mkern 1.5mu\text{-}\mkern
1.5mu)-x\colon[x,1^{\circ}]\to[0^{\circ},1^{\circ}-x]$.

This plus operation allows us to define the notion of finitely supported
${\mathbf{\Gamma}}$-valued function:

######  Definition 5.2.

For any set $X$, ${\mathcal{F}}(X)$ is the set of all functions $f\colon
X\to{\mathbf{\Gamma}}$ such that

  1. (1)

the set $\mathrm{supp}(f)\coloneqq\\{x\in X\mid f(x)\not=0^{\circ}\\}$ is
finite, and

  2. (2)

$f(x_{1})+\cdots+f(x_{n})$ is defined and equal to $1^{\circ}$, where
$\\{x_{1},\ldots,x_{n}\\}=\mathrm{supp}(f)$.

To improve readability, if the sum $y_{1}+\cdots+y_{m}$ exists in
${\mathbf{\Gamma}}$, we denote it $\sum_{i=1}^{m}{y_{i}}$. Finitely supported
functions in the above sense always determine measures over the power-set
algebra:

######  Lemma 5.3.

Let $X$ be any set. There is a well-defined mapping
$\int\colon{\mathcal{F}}(X)\to\operatorname{\mathcal{M}_{\Gamma}}(\raisebox{2.03998pt}{\Large$\wp$}(X))$,
assigning to every $f\in{\mathcal{F}}(X)$ the measure

$\textstyle\int f\colon M\mapsto\int_{M}f\coloneqq\sum\\{f(x)\mid x\in
M\cap\mathrm{supp}(f)\\}.$

###### Proof.

We wish to prove that $\int f$ is a measure for every $f\in{\mathcal{F}}(X)$.
First, observe that $\int_{\emptyset}f=0^{\circ}$ and $\int_{X}f=1^{\circ}$ by
definition. Moreover, $M\mapsto\int_{M}f$ is monotone because $x\leq x+y$ for
all $x,y\in{\mathbf{\Gamma}}$ for which $x+y$ is defined.

It remains to show that, for any $M,N\subseteq X$,

$\displaystyle\textstyle\int_{M}f\sim\int_{M\cap N}f\,\leq\,\int_{M\cup
N}f-\int_{N}f{\quad\text{and}\quad}\int_{M}f-\int_{M\cap
N}f\,\geq\,\int_{M\cup N}f\sim\int_{N}f.$ (6)

To simplify these expressions, set $m\coloneqq\int_{M\setminus N}f$,
$n\coloneqq\int_{N\setminus M}f$, and $i\coloneqq\int_{M\cap N}f$. Then, we
see that

$\textstyle\int_{M}f=m+i,\quad\int_{N}f=n+i{\enspace\text{and}\enspace}\int_{M\cup
N}=m+n+i.$

Consequently, the inequalities in (6) can be rewritten as

$(m+i)\sim
i\,\leq\,(m+n+i)-(n+i){\quad\text{and}\quad}(m+i)-i\,\geq\,(m+n+i)\sim(n+i).$

By Lemma 5.1, these are equivalent to

$((m+i)\sim
i)+(n+i)\,\leq\,m+n+i{\quad\text{and}\quad}((m+n+i)\sim(n+i))+i\leq m+i.$

Next, observe that, for all $x,y\in{\mathbf{\Gamma}}$ for which $x+y$ is
defined, $(x+y)\sim y$ is always of --type or equal to $0^{\circ}$, and so
$(x+y)\sim y=\iota_{-}(\gamma(x))$ (where the map
$\iota_{-}\colon[0,1]\to{\mathbf{\Gamma}}$ is defined as in Remark 3.5).
Consequently, $((m+i)\sim i)+n+i=\iota_{-}(\gamma(m))+n+i\leq m+n+i$ and
$((m+n+i)\sim(n+i))+i=\iota_{-}(\gamma(m))+i\leq m+i$. ∎

###  5.1. The ${\mathbf{\Gamma}}$-valued Stone pairing and logic on words

Fix a countably infinite set of variables $\\{v_{1},v_{2},\dots\\}$. Recall
that $\mathrm{FO}_{n}(\sigma)$ is the Lindenbaum–Tarski algebra of first-order
formulas with free variables among $\\{v_{1},\dots,v_{n}\\}$. The dual space
of $\mathrm{FO}_{n}(\sigma)$ is the space of $n$-types
$\operatorname{Typ}_{n}(\sigma)$. Its points are the elementary equivalence
classes of pairs $(A,\alpha)$, where $A$ is a $\sigma$-structure and
$\alpha\colon\\{v_{1},\dots,v_{n}\\}\to A$ is an interpretation of the
variables. Also, recall that $\mathrm{Fin}(\sigma)$ denotes the set of
isomorphism classes of finite $\sigma$-structures.

We would like to define a function
$\mathrm{Fin}(\sigma)\to{\mathcal{F}}(\operatorname{Typ}_{n}(\sigma))$ which,
intuitively, associates with a finite $\sigma$-structure $A$ the (normalised)
characteristic function of the finite set

$\\{(A,\alpha)\mid\alpha\colon\\{v_{1},\dots,v_{n}\\}\to A\\},$

which assigns value $(\frac{1}{|A|^{n}})^{\circ}$ to $(B,\beta)$ if $A=B$, and
$0$ otherwise. However, we need to slightly modify this definition to take
into account the fact that elements of $\operatorname{Typ}_{n}(\sigma)$ are
elementary equivalence classes of pairs $(B,\beta)$, and such an equivalence
class may contain several pairs whose first component is $A$.

Define the map
$\mathrm{Fin}(\sigma)\to{\mathcal{F}}(\operatorname{Typ}_{n}(\sigma))$ which
sends the isomorphism class of a finite $\sigma$-structure $A$ to the finitely
supported function $f_{n}^{A}$ whose value at an equivalence class
$E\in\operatorname{Typ}_{n}(\sigma)$ is

$f_{n}^{A}(E)\coloneqq\sum_{(A,\alpha)\in
E}\left(\frac{1}{|A|^{n}}\right)^{\circ}\quad\parbox{210.00032pt}{\centering\emph{(Add
$(\frac{1}{|A|^{n}})^{\circ}$ for every interpretation $\alpha$ of the free
variables s.t.\ $(A,\alpha)$ is in the equivalence class)}.\@add@centering}$

It is not difficult to see that this definition does not depend on the choice
of a representative in the isomorphism class of $A$.

By Lemma 5.3, we get a measure $\int
f_{n}^{A}\colon\raisebox{2.03998pt}{\Large$\wp$}(\operatorname{Typ}_{n}(\sigma))\to{\mathbf{\Gamma}}$.
Now, for each $\varphi\in\mathrm{FO}_{n}(\sigma)$, let
$\llbracket\varphi\rrbracket_{n}\subseteq\operatorname{Typ}_{n}(\sigma)$ be
the set of (equivalence classes of) $\sigma$-structures with interpretations
satisfying $\varphi$. By Stone duality we obtain an embedding
$\llbracket\mkern 1.5mu\text{-}\mkern
1.5mu\rrbracket_{n}\colon\mathrm{FO}_{n}(\sigma)\hookrightarrow\raisebox{2.03998pt}{\Large$\wp$}(\operatorname{Typ}_{n}(\sigma))$.
Restricting $\int f_{n}^{A}$ to $\mathrm{FO}_{n}(\sigma)$, we get a measure

$\textstyle\mu_{n}^{A}\colon\mathrm{FO}_{n}(\sigma)\to{\mathbf{\Gamma}},\quad\varphi\mapsto\int_{\llbracket\varphi\rrbracket_{n}}f_{n}^{A}.$

Summing up, we have the composite map

$\textstyle\mathrm{Fin}(\sigma)\to\operatorname{\mathcal{M}_{\Gamma}}(\raisebox{2.03998pt}{\Large$\wp$}(\operatorname{Typ}_{n}(\sigma)))\to\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}_{n}(\sigma)),\quad
A\mapsto\int f_{n}^{A}\mapsto\mu_{n}^{A}.$ (7)

Essentially the same construction is featured in logic on words, cf. equation
(2):

  * •

The set of finite $\sigma$-structures $\mathrm{Fin}(\sigma)$ corresponds to
the set of finite words $A^{*}$.

  * •

The collection $\operatorname{Typ}_{n}(\sigma)$ of (equivalence classes of)
$\sigma$-structures with interpretations corresponds to $(A\times 2)^{*}$ or,
interchangeably, $\beta(A\times 2)^{*}$ (in the case of one free variable).

  * •

The fragment $\mathrm{FO}_{n}(\sigma)$ of first-order logic corresponds to the
Boolean algebra of languages, defined by formulas with a free variable, dual
to the Boolean space $X$ appearing in (2).

  * •

The first map in the composite (7) sends a finite $\sigma$-structure $A$ to
the measure $\int f_{n}^{A}$ which, evaluated on
$K\subseteq\operatorname{Typ}_{n}(\sigma)$, counts the (proportion of)
interpretations $\alpha\colon\\{v_{1},\dots,v_{n}\\}\to A$ such that
$(A,\alpha)\in K$, similarly to $R$ from (2).

  * •

Finally, the second map in (7) sends a measure in
$\operatorname{\mathcal{M}_{\Gamma}}(\raisebox{2.03998pt}{\Large$\wp$}(\operatorname{Typ}_{n}(\sigma)))$
to its pushforward along $\llbracket\mkern 1.5mu\text{-}\mkern
1.5mu\rrbracket_{n}\colon\mathrm{FO}_{n}(\sigma)\hookrightarrow\raisebox{2.03998pt}{\Large$\wp$}(\operatorname{Typ}_{n}(\sigma))$.
This is the second map in the composition (2).

On the other hand, the assignment $A\mapsto\mu_{n}^{A}$ defined in (7) is also
closely related to the classical Stone pairing. Indeed, for every formula
$\varphi$ in $\mathrm{FO}_{n}(\sigma)$,

$\displaystyle\mu_{n}^{A}(\varphi)=\sum_{E\in\llbracket\varphi\rrbracket_{n}}{f_{n}^{A}(E)}=\sum_{E\in\llbracket\varphi\rrbracket_{n}}\sum_{(A,\alpha)\in
E}\left(\frac{1}{|A|^{n}}\right)^{\circ}$
$\displaystyle=\left(\frac{|\\{\overline{a}\in A^{n}\mid
A\models\varphi(\overline{a})|}{|A|^{n}}\right)^{\circ}=(\left<\varphi,A\right>_{\mathrm{I}})^{\circ}.$
(8)

In this sense, $\mu_{n}^{A}$ can be regarded as a ${\mathbf{\Gamma}}$-valued
Stone pairing, relative to the fragment $\mathrm{FO}_{n}(\sigma)$. Next, we
show how to extend this to the full first-order logic $\mathrm{FO}(\sigma)$.
First, we observe that—as in the classical case—the construction is invariant
under extensions of the set of free variables:

######  Lemma 5.4.

Given $m,n\in\mathbb{N}$ and $A\in\mathrm{Fin}(\sigma)$, if $m\geq n$ then
$(\mu_{m}^{A})_{\mathord{\upharpoonright}\mathrm{FO}_{n}(\sigma)}=\mu_{n}^{A}$.

###### Proof.

Every variable assignment $\alpha\colon\\{v_{1},\dots,v_{n}\\}\to A$ has
$|A|^{m-n}$ possible extensions
$\alpha^{\prime}\colon\\{v_{1},\dots,v_{m}\\}\to A$, to account for the $m-n$
unused variables. Moreover, for every $\varphi\in\mathrm{FO}_{n}(\sigma)$,
$(A,\alpha)\models\varphi$ if, and only if,
$(A,\alpha^{\prime})\models\varphi$. Because $\mu_{m}^{A}$ and $\mu_{n}^{A}$
take only values of ∘-type, and $p^{\circ}+q^{\circ}=(p+q)^{\circ}$, we see
that

$\displaystyle\mu_{n}^{A}(\varphi)$
$\displaystyle=\sum\left\\{\left(\frac{1}{|A|^{n}}\right)^{\circ}\mid\alpha\colon\\{v_{1},\dots,v_{n}\\}\to
A{\enspace\text{and}\enspace}(A,\alpha)\models\varphi\right\\}$
$\displaystyle=\sum\left\\{\left(\frac{|A|^{m-n}}{|A|^{m}}\right)^{\circ}\mid\alpha\colon\\{v_{1},\dots,v_{n}\\}\to
A{\enspace\text{and}\enspace}(A,\alpha)\models\varphi\right\\}$
$\displaystyle=\sum\left\\{\left(\frac{1}{|A|^{m}}\right)^{\circ}\mid\alpha^{\prime}\colon\\{v_{1},\dots,v_{m}\\}\to
A{\enspace\text{and}\enspace}(A,\alpha^{\prime})\models\varphi\right\\}=\mu_{m}^{A}(\varphi).\qed$

The Lindenbaum–Tarski algebra of all first-order formulas
$\mathrm{FO}(\sigma)$ is the directed colimit of the chain of its Boolean
subalgebras

$\mathrm{FO}_{0}(\sigma)\hookrightarrow\mathrm{FO}_{1}(\sigma)\hookrightarrow\mathrm{FO}_{2}(\sigma)\hookrightarrow\cdots.$

Since the functor $\operatorname{\mathcal{M}_{\Gamma}}$ turns directed
colimits into codirected limits (Proposition 4.6), the Priestley space
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ is the limit of the
diagram

$\left\\{\leavevmode\hbox to215.6pt{\vbox
to13.1pt{\pgfpicture\makeatletter\hbox{\hskip 107.8023pt\lower-8.09982pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}{}{}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{\offinterlineskip{}{}{{{}}{{}}}{{{}}}{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-110.8023pt}{-7.99998pt}\pgfsys@invoke{
}\hbox{\vbox{\halign{\pgf@matrix@init@row\pgf@matrix@step@column{\pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding&&\pgf@matrix@step@column{\pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding\cr\hfil\hskip
28.66277pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-25.66277pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{${\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}_{n}(\sigma))}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip
28.66277pt\hfil&\hfil\hskip 94.63959pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-66.63954pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{${{\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}_{m}(\sigma))\mid
m,n\in\mathbb{N},\ m\geq n}}$} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
69.63954pt\hfil\cr}}}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}{{{{}}}{{}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} {}{ {}{}{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.39998pt}\pgfsys@invoke{
}{}{}{}{}{}{{}}{}{}{{}}\pgfsys@moveto{-28.67673pt}{-5.49998pt}\pgfsys@lineto{-52.87682pt}{-5.49998pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{-51.63689pt}{-5.49998pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{-53.0768pt}{-5.49998pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-46.1768pt}{-1.50833pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{$\scriptstyle{q_{n,m}}$} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\right\\}$

where, for every measure
$\mu\colon\mathrm{FO}_{m}(\sigma)\to{\mathbf{\Gamma}}$, the measure
$q_{n,m}(\mu)$ is the restriction of $\mu$ to $\mathrm{FO}_{n}(\sigma)$. In
view of Lemma 5.4, for every $A\in\mathrm{Fin}(\sigma)$, the tuple
$(\mu_{n}^{A})_{n\in\mathbb{N}}$ is compatible with the restriction maps.
Thus, recalling that limits in the category of Priestley spaces are computed
as in sets, by universality of the limit construction this tuple yields a
measure

$\left<\mkern 1.5mu\text{-}\mkern
1.5mu,A\right>_{\mathrm{\Gamma}}\colon\mathrm{FO}(\sigma)\to{\mathbf{\Gamma}}$

in the space $\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ whose
restriction to $\mathrm{FO}_{n}(\sigma)$ coincides with $\mu_{n}^{A}$, for
every $n\in\mathbb{N}$. This we call the _${\mathbf{\Gamma}}$ -valued Stone
pairing_ associated with $A$. As in the classical case, using the fact that
any two non-isomorphic finite structures are separated by a first-order
sentence, it is not difficult to see that the mapping $A\mapsto\left<\mkern
1.5mu\text{-}\mkern 1.5mu,A\right>_{\mathrm{\Gamma}}$ gives an embedding

$\left<\mkern 1.5mu\text{-}\mkern 1.5mu,\mkern 1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{\Gamma}}\colon\mathrm{Fin}(\sigma)\hookrightarrow\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma)).$

The following theorem illustrates the relation between the classical Stone
pairing, namely $\left<\mkern 1.5mu\text{-}\mkern 1.5mu,\mkern
1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{I}}\colon\mathrm{Fin}(\sigma)\hookrightarrow\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$,
and the ${\mathbf{\Gamma}}$-valued one.

######  Theorem 5.5.

The following diagram commutes:

${\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))}$${\mathrm{Fin}(\sigma)}$${\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))}$$\scriptstyle{\gamma^{\\#}}$$\scriptstyle{\left<\mkern
1.5mu\text{-}\mkern 1.5mu,\mkern 1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{\Gamma}}}$$\scriptstyle{\left<\mkern 1.5mu\text{-}\mkern
1.5mu,\mkern 1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{I}}}$$\scriptstyle{\iota^{\\#}}$

###### Proof.

Fix an arbitrary finite $\sigma$-structure $A\in\mathrm{Fin}(\sigma)$. Let
$\varphi$ be a formula in $\mathrm{FO}(\sigma)$ with free variables among
$\\{v_{1},\dots,v_{n}\\}$, for some $n\in\mathbb{N}$. By construction,
$\left<\varphi,A\right>_{\mathrm{\Gamma}}=\mu_{n}^{A}(\varphi)$. Therefore, by
equation (8),
$\left<\varphi,A\right>_{\mathrm{\Gamma}}=(\left<\varphi,A\right>_{\mathrm{I}})^{\circ}$
and thus the statement follows at once. ∎

######  Remark 5.6.

The construction in this section works, mutatis mutandis, also for smaller
logic fragments, i.e. for sublattices $D\subseteq\mathrm{FO}(\sigma)$. This
corresponds to composing the embedding
$\mathrm{Fin}(\sigma)\hookrightarrow\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$
with the restriction map
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))\to\operatorname{\mathcal{M}_{\Gamma}}(D)$
sending a measure $\mu\colon\mathrm{FO}(\sigma)\to{\mathbf{\Gamma}}$ to
$\mu_{\mathord{\upharpoonright}D}\colon D\to{\mathbf{\Gamma}}$. The only
difference is that, in general, the ensuing map
$\mathrm{Fin}(\sigma)\to\operatorname{\mathcal{M}_{\Gamma}}(D)$ need not be
injective.

###  5.2. Limits in the spaces of measures

By Theorem 5.5, the ${\mathbf{\Gamma}}$-valued Stone pairing $\left<\mkern
1.5mu\text{-}\mkern 1.5mu,\mkern 1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{\Gamma}}$ and the classical Stone pairing $\left<\mkern
1.5mu\text{-}\mkern 1.5mu,\mkern 1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{I}}$ determine each other. However, the notions of
convergence associated with the spaces
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ and
$\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$ are different: since the
topology of $\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ is
richer, there are “fewer” convergent sequences. Recall from Lemma 4.8 that
$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))\to\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$
is continuous. Also, $\gamma^{\\#}(\left<\mkern 1.5mu\text{-}\mkern
1.5mu,A\right>_{\mathrm{\Gamma}})=\left<\mkern 1.5mu\text{-}\mkern
1.5mu,A\right>_{\mathrm{I}}$ by Theorem 5.5. Thus, for any sequence of finite
$\sigma$-structures $(A_{n})_{n\in\mathbb{N}}$, if

$\left<\mkern 1.5mu\text{-}\mkern 1.5mu,A_{n}\right>_{\mathrm{\Gamma}}$
converges to a measure $\mu$ in
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$

then

$\left<\mkern 1.5mu\text{-}\mkern 1.5mu,A_{n}\right>_{\mathrm{I}}$ converges
to the measure $\gamma^{\\#}(\mu)$ in
$\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$.

The converse is not true. For example, consider the signature $\sigma=\\{<\\}$
consisting of a single binary relation symbol, and let
$(A_{n})_{n\in\mathbb{N}}$ be the sequence of finite posets displayed in the
picture below.

$A_{1}$$A_{2}$$A_{3}$$A_{4}$$A_{5}$$A_{6}$$\cdots$

Consider the formula

$\psi(x)\coloneqq\forall y\,[\neg(x<y)]\wedge\exists
z\,[\neg(z<x)\wedge\neg(z=x)]$

stating that $x$ is maximal but not the maximum in the order given by $<$.
Then, for the sublattice $D=\\{\mathbf{f},\psi,\mathbf{t}\\}$ of
$\mathrm{FO}(\sigma)$, it is not difficult to see that the sequences
$\left<\mkern 1.5mu\text{-}\mkern 1.5mu,A_{n}\right>_{\mathrm{\Gamma}}$ and
$\left<\mkern 1.5mu\text{-}\mkern 1.5mu,A_{n}\right>_{\mathrm{I}}$ converge in
$\operatorname{\mathcal{M}_{\Gamma}}(D)$ and
$\operatorname{\mathcal{M}_{I}}(D)$, respectively. For instance,

$(\left<\psi,A_{n}\right>_{\mathrm{\Gamma}})_{n}=(0^{\circ},(\tfrac{2}{3})^{\circ},0^{\circ},(\tfrac{2}{4})^{\circ},1^{\circ},(\tfrac{2}{5})^{\circ},\ldots),$

which converges to $0^{\circ}$. However, if we consider the Boolean algebra
$B=\\{\mathbf{f},\psi,\neg\psi,\mathbf{t}\\}$, then the $\left<\mkern
1.5mu\text{-}\mkern 1.5mu,A_{n}\right>_{\mathrm{I}}$’s still converge whereas
the $\left<\mkern 1.5mu\text{-}\mkern 1.5mu,A_{n}\right>_{\mathrm{\Gamma}}$’s
do not. Just observe that the following sequence does not converge in
${\mathbf{\Gamma}}$ because the odd terms converge to $1^{\circ}$, while the
even terms converge to $1^{-}$:

$(\left<\neg\psi,A_{n}\right>_{\mathrm{\Gamma}})_{n}=(1^{\circ},(\tfrac{1}{3})^{\circ},1^{\circ},(\tfrac{2}{4})^{\circ},1^{\circ},(\tfrac{3}{5})^{\circ},\ldots).$

Nevertheless, there is a sequence $\left<\mkern 1.5mu\text{-}\mkern
1.5mu,A^{\prime}_{n}\right>_{\mathrm{\Gamma}}$ which converges in
$\operatorname{\mathcal{M}_{\Gamma}}(B)$ to a measure whose image under
$\gamma^{\\#}$ coincides with the limit of the $\left<\mkern
1.5mu\text{-}\mkern 1.5mu,A_{n}\right>_{\mathrm{I}}$’s (e.g., take the
subsequence $(A^{\prime}_{n})_{n\in\mathbb{N}}$ of $(A_{n})_{n\in\mathbb{N}}$
consisting of the even terms). In the next theorem, we will see that this is a
general fact.

Identify $\mathrm{Fin}(\sigma)$ with a subset of
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ (resp.
$\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$) through $\left<\mkern
1.5mu\text{-}\mkern 1.5mu,\mkern 1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{\Gamma}}$ (resp. $\left<\mkern 1.5mu\text{-}\mkern
1.5mu,\mkern 1.5mu\text{-}\mkern 1.5mu\right>_{\mathrm{I}}$). A central
question in the theory of structural limits, cf. [26], is to determine the
closure of $\mathrm{Fin}(\sigma)$ in
$\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$, which consists
precisely of the limits of sequences of finite structures. The following
theorem gives an answer to this question in terms of the corresponding
question for $\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$.

######  Theorem 5.7.

Let $\overline{\mathrm{Fin}(\sigma)}$ denote the closure of
$\mathrm{Fin}(\sigma)$ in
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$. Then the set
$\gamma^{\\#}(\overline{\mathrm{Fin}(\sigma)})$ coincides with the closure of
$\mathrm{Fin}(\sigma)$ in
$\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$.

###### Proof.

Write $U$ for the image of $\left<\mkern 1.5mu\text{-}\mkern 1.5mu,\mkern
1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{\Gamma}}\colon\mathrm{Fin}(\sigma)\hookrightarrow\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$,
and $V$ for the image of $\left<\mkern 1.5mu\text{-}\mkern 1.5mu,\mkern
1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{I}}\colon\mathrm{Fin}(\sigma)\hookrightarrow\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$.
We must prove that $\gamma^{\\#}(\overline{U})=\overline{V}$. By Theorem 5.5,
we have $\gamma^{\\#}(U)=V$. Recall that
$\gamma^{\\#}\colon\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))\to\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$
is continuous (Lemma 4.8), and the spaces
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ and
$\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$ are compact Hausdorff
(Proposition 4.3 and Corollary 4.9). Since continuous maps between compact
Hausdorff spaces are closed, we obtain
$\gamma^{\\#}(\overline{U})=\overline{\gamma^{\\#}(U)}=\overline{V}$. ∎

##  6\. The logic of measures

In view of Proposition 4.3 we know that, for any distributive lattice $D$, the
space $\operatorname{\mathcal{M}_{\Gamma}}(D)$ of ${\mathbf{\Gamma}}$-valued
measures on $D$ is a Priestley space, whence it has a dual distributive
lattice $\operatorname{\mathbf{P}}(D)$. In this section, we show that
$\operatorname{\mathbf{P}}(D)$ can be represented as the Lindenbaum–Tarski
algebra for a propositional logic $P\mkern-1.0mu\mathcal{L}_{D}$ obtained from
$D$ by adding probabilistic quantifiers.

The set of propositional variables of the logic $P\mkern-1.0mu\mathcal{L}_{D}$
consists of the symbols $\mathbb{P}_{\geq p}\,a$, for every $a\in D$ and
$p\in\mathbb{Q}\cap[0,1]$. The logical connectives that we shall consider are
$\mathbf{t},\mathbf{f},\wedge,\vee$, and the top and bottom elements of $D$
are denoted $\mathbf{t}^{*}$ and $\mathbf{f}^{*}$, respectively.555To avoid
cumbersome notation, we use the same symbols for infima in $D$ and
conjunctions in $P\mkern-1.0mu\mathcal{L}_{D}$, namely $\wedge$, and for
suprema in $D$ and disjunctions in $P\mkern-1.0mu\mathcal{L}_{D}$, namely
$\vee$. It will be clear from the context to which concept we are referring.
The logic $P\mkern-1.0mu\mathcal{L}_{D}$ is specified by the following rules,
for all $p,q,r\in\mathbb{Q}\cap[0,1]$ and $a,b\in D$ (along with the usual
ones for the connectives $\mathbf{t},\mathbf{f},\wedge,\vee$):

  1. (L1)

$\mathbb{P}_{\geq q}\,a\vdash\mathbb{P}_{\geq p}\,a$ whenever $p\leq q$

  2. (L2)

$\mathbf{t}\vdash\mathbb{P}_{\geq 0}\,\mathbf{f}^{*}$,
$\mathbf{t}\vdash\mathbb{P}_{\geq q}\,\mathbf{t}^{*}$, and $\mathbb{P}_{\geq
p}\,\mathbf{f}^{*}\vdash\mathbf{f}$ whenever $p>0$

  3. (L3)

$\mathbb{P}_{\geq q}\,a\vdash\mathbb{P}_{\geq q}\,b$ whenever $a\leq b$

  4. (L4)

$\mathbb{P}_{\geq p}\,a\,\wedge\,\mathbb{P}_{\geq q}\,b\vdash\mathbb{P}_{\geq
p+q-r}\,(a\vee b)\,\vee\,\mathbb{P}_{\geq r}\,(a\wedge b)$ whenever $0\leq
p+q-r\leq 1$

  5. (L5)

$\mathbb{P}_{\geq p+q-r}\,(a\vee b)\,\wedge\,\mathbb{P}_{\geq r}\,(a\wedge
b)\vdash\mathbb{P}_{\geq p}\,a\,\vee\,\mathbb{P}_{\geq q}\,b$ whenever $0\leq
p+q-r\leq 1$

The logic $P\mkern-1.0mu\mathcal{L}_{D}$ can be interpreted in the space of
measures $\operatorname{\mathcal{M}_{\Gamma}}(D)$ by setting, for every
$\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D)$,

$\mu\models\mathbb{P}_{\geq p}\,a\ \Leftrightarrow\ \mu(a)\geq p^{\circ}.$ (9)

This satisfaction relation extends in the obvious way to the closure of the
set of propositional variables under finite conjunctions and finite
disjunctions. For any two formulas $\varphi,\psi$ in the language of
$P\mkern-1.0mu\mathcal{L}_{D}$, we write $\varphi\models\psi$ provided that

$\forall\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D),\ \
\mu\models\varphi\text{ implies }\mu\models\psi.$

The interpretation of $P\mkern-1.0mu\mathcal{L}_{D}$ in
$\operatorname{\mathcal{M}_{\Gamma}}(D)$ given in (9) is sound:

######  Lemma 6.1 (Soundness).

If $\varphi\vdash\psi$ is any rule in (L1)–(L5), then $\varphi\models\psi$.

###### Proof.

(L1)–(L3) are easily verified, and we leave the details to the reader. We
spell out the case of (L4); the proof of (L5) is the same, mutatis mutandis.

Fix arbitrary $a,b\in D$ and $p,q,r\in\mathbb{Q}\cap[0,1]$ such that $0\leq
p+q-r\leq 1$. Let $\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D)$ be any
measure satisfying $\mu\models\mathbb{P}_{\geq p}\,a\,\wedge\,\mathbb{P}_{\geq
q}\,b$, i.e. $\mu(a)\geq p^{\circ}$ and $\mu(b)\geq q^{\circ}$. We must prove
that $\mu\models\mathbb{P}_{\geq p+q-r}\,(a\vee b)\,\vee\,\mathbb{P}_{\geq
r}\,(a\wedge b)$, that is either $\mu(a\vee b)\geq(p+q-r)^{\circ}$ or
$\mu(a\wedge b)\geq r^{\circ}$. Using the fact that $\mu$ is a measure, we get

$p^{\circ}\sim\mu(a\wedge b)\leq\mu(a)\sim\mu(a\wedge b)\leq\mu(a\vee
b)-\mu(b)\leq\mu(a\vee b)-q^{\circ}.$

If $\mu$ does not satisfy $\mu(a\wedge b)\geq r^{\circ}$, i.e. $\mu(a\wedge
b)\leq r^{-}$, then

$p^{\circ}\sim r^{-}\leq\mu(a\vee b)-q^{\circ}$

and therefore

$(p+q-r)^{\circ}=(p^{\circ}\sim r^{-})+q^{\circ}\leq(\mu(a\vee
b)-q^{\circ})+q^{\circ}\leq\mu(a\vee b).\qed$

In Theorem 6.4 below we will see that, in fact, $P\mkern-1.0mu\mathcal{L}_{D}$
is complete with respect to this measure-theoretic semantics. In other words,
$P\mkern-1.0mu\mathcal{L}_{D}$ is the logic of the space of measures
$\operatorname{\mathcal{M}_{\Gamma}}(D)$. To start with, we let
$\operatorname{\mathbf{P}}(D)$ be the Lindenbaum–Tarski algebra of
$P\mkern-1.0mu\mathcal{L}_{D}$, that is the quotient of the free distributive
lattice on the set

$\\{\mathbb{P}_{\geq p}\,a\mid p\in\mathbb{Q}\cap[0,1],\ a\in D\\}$

with respect to the congruence generated by the conditions (L1)–(L5). In
particular, recall from Section 2.2 that elements of
$\operatorname{\mathbf{P}}(D)$ are provable equivalence classes of formulas
$\varphi,\psi$ in the logic $P\mkern-1.0mu\mathcal{L}_{D}$. Moreover,
considering representatives, we have $\varphi\leq\psi$ in
$\operatorname{\mathbf{P}}(D)$ if, and only if, $\varphi\vdash\psi$ holds in
the logic $P\mkern-1.0mu\mathcal{L}_{D}$.

In order to show that every prime filter of $\operatorname{\mathbf{P}}(D)$
yields a measure in $\operatorname{\mathcal{M}_{\Gamma}}(D)$, we need the
following lemma:

######  Lemma 6.2.

The following statements hold:

  1. (1)

for every $x,y\in{\mathbf{\Gamma}}$ such that $y\leq x$, $x\sim
y=\bigvee{\\{p^{\circ}-q^{\circ}\mid y<q^{\circ}\leq p^{\circ}\leq x\\}}$;

  2. (2)

for every $x\in{\mathbf{\Gamma}}$, the map $x-(\mkern 1.5mu\text{-}\mkern
1.5mu)\colon[0^{\circ},x]\to{\mathbf{\Gamma}}$ sends suprema to infima.

###### Proof.

(1) Recall that, for every $x,y\in{\mathbf{\Gamma}}$ such that $y\leq x$,

$x\sim y=\bigvee{\\{x-q^{\circ}\mid y<q^{\circ}\leq x\\}}.$

So, it suffices to show that, whenever $q^{\circ}\leq x$,

$x-q^{\circ}=\bigvee{\\{p^{\circ}-q^{\circ}\mid q^{\circ}\leq p^{\circ}\leq
x\\}}.$

If $x=r^{\circ}$ for some $r\in\mathbb{Q}\cap[0,1]$, the supremum belongs to
the set $\\{p^{\circ}-q^{\circ}\mid q^{\circ}\leq p^{\circ}\leq x\\}$, and it
is precisely $r^{\circ}-q^{\circ}$. Thus, suppose $x=r^{-}$ for some
$r\in(0,1]$. To show the non-trivial inequality, pick $z\in{\mathbf{\Gamma}}$
such that $p^{\circ}-q^{\circ}\leq z$ whenever $q^{\circ}\leq p^{\circ}\leq
x$. Note that $\gamma(x)-q\leq\gamma(z)$, for otherwise we could find
$p\in\mathbb{Q}\cap[0,1]$ satisfying $q\leq p<\gamma(x)$ and $\gamma(z)<p-q$,
and so $z<p^{\circ}-q^{\circ}$. It follows that

$x-q^{\circ}=(\gamma(x)-q)^{-}\leq\gamma(z)^{-}\leq z.$

(2) Fix $x\in{\mathbf{\Gamma}}$. We must prove that, for every subset
$\\{y_{i}\mid i\in I\\}\subseteq[0^{\circ},x]$,

$x-\bigvee_{i\in I}{y_{i}}=\bigwedge_{i\in I}{(x-y_{i})}.$

By Lemma 3.2, the map $x-(\mkern 1.5mu\text{-}\mkern
1.5mu)\colon[0^{\circ},x]\to{\mathbf{\Gamma}}$ is lower continuous and order
reversing. Since the interval $[0^{\circ},x]$ is closed in
${\mathbf{\Gamma}}$, it is a compact ordered space with respect to the induced
order and topology (in fact, it is a Priestley space). The supremum
$\bigvee_{i\in I}{y_{i}}$ then coincides with the limit of $\\{y_{i}\mid i\in
I\\}$, regarded as a net in $[0^{\circ},x]$ (cf. [14, Proposition VI.1.3]). By
lower continuity of $x-(\mkern 1.5mu\text{-}\mkern 1.5mu)$, we have that
$x-\bigvee_{i\in I}{y_{i}}$, regarded as an element of
${\mathbf{\Gamma}}{}^{\mathrm{op}}$, is less than or equal to the supremum
(computed in ${\mathbf{\Gamma}}{}^{\mathrm{op}}$) of the $x-y_{i}$’s. That is,

$x-\bigvee_{i\in I}{y_{i}}\geq\bigwedge_{i\in I}{(x-y_{i})}$

in ${\mathbf{\Gamma}}$. The other inequality follows at once from the fact
that $x-(\mkern 1.5mu\text{-}\mkern 1.5mu)$ is order reversing. ∎

######  Proposition 6.3.

Let $F\subseteq\operatorname{\mathbf{P}}(D)$ be a prime filter. The assignment

$a\mapsto\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in F\\}}\quad\text{
defines a measure }\ \mu_{F}\colon D\to{\mathbf{\Gamma}}.$

###### Proof.

Condition (L2) entails at once that $\mu_{F}(\mathbf{f}^{*})=0^{\circ}$ and
$\mu_{F}(\mathbf{t}^{*})=1^{\circ}$. Further, suppose $a,b\in D$ and $a\leq
b$. Then $\\{q\mid\mathbb{P}_{\geq q}\,a\in
F\\}\subseteq\\{q\mid\mathbb{P}_{\geq q}\,b\in F\\}$ by (L3), and thus

$\mu_{F}(a)=\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in
F\\}}\leq\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,b\in F\\}}=\mu_{F}(b).$

That is, $\mu_{F}$ is monotone. This shows that $\mu_{F}$ satisfies the first
two conditions defining ${\mathbf{\Gamma}}$-valued measures (cf. Definition
4.1). We prove the first half of the third condition, as the other half is
proved in a similar fashion. We must show that, for every $a,b\in D$,

$\displaystyle\mu_{F}(a)\sim\mu_{F}(a\wedge b)\leq\mu_{F}(a\vee
b)-\mu_{F}(b).$ (10)

By item 1 in Lemma 6.2, the left-hand expression in (10) can be written as

$\mu_{F}(a)\sim\mu_{F}(a\wedge
b)=\bigvee{\\{p^{\circ}-r^{\circ}\mid\mu_{F}(a\wedge b)<r^{\circ}\leq
p^{\circ}\leq\mu_{F}(a)\\}}.$

Furthermore, we have $\mu_{F}(b)=\bigvee{\\{q^{\circ}\mid
q^{\circ}\leq\mu_{F}(b)\\}}$. Just observe that $\mathbb{P}_{\geq q}\,b\in F$
entails $q^{\circ}\leq\mu_{F}(b)$, and so

$\mu_{F}(b)=\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,b\in
F\\}}\leq\bigvee{\\{q^{\circ}\mid q^{\circ}\leq\mu_{F}(b)\\}}\leq\mu_{F}(b).$

By item 2 in Lemma 6.2, the right-hand expression in (10) is equivalently
expressed as

$\displaystyle\mu_{F}(a\vee b)-\mu_{F}(b)$ $\displaystyle=\mu_{F}(a\vee
b)-\bigvee{\\{q^{\circ}\mid q^{\circ}\leq\mu_{F}(b)\\}}$
$\displaystyle=\bigwedge{\\{\mu_{F}(a\vee b)-q^{\circ}\mid
q^{\circ}\leq\mu_{F}(b)\\}}.$

Therefore, we must prove that

$\bigvee{\\{p^{\circ}-r^{\circ}\mid\mu_{F}(a\wedge b)<r^{\circ}\leq
p^{\circ}\leq\mu_{F}(a)\\}}\leq\bigwedge{\\{\mu_{F}(a\vee b)-q^{\circ}\mid
q^{\circ}\leq\mu_{F}(b)\\}}.$

That is, whenever $\mu_{F}(a\wedge b)<r^{\circ}\leq p^{\circ}\leq\mu_{F}(a)$
and $q^{\circ}\leq\mu_{F}(b)$, we have

$(p-r)^{\circ}\leq\mu_{F}(a\vee b)-q^{\circ}.$

In view of Lemma 5.1, the latter inequality is equivalent to
$(p+q-r)^{\circ}\leq\mu_{F}(a\vee b)$. In turn, using (L4) and the fact that
$F$ is a prime filter, $\mathbb{P}_{\geq p}\,a,\mathbb{P}_{\geq q}\,b\in F$
and $\mathbb{P}_{\geq r}\,(a\wedge b)\notin F$ entail $\mathbb{P}_{\geq
p+q-r}\,(a\vee b)\in F$. Whence,

$\mu_{F}(a\vee b)=\bigvee{\\{s^{\circ}\mid\mathbb{P}_{\geq s}\,(a\vee b)\in
F\\}}\geq(p+q-r)^{\circ}.\qed$

We are now in a position to show that the dual lattice of the Priestley space
$\operatorname{\mathcal{M}_{\Gamma}}(D)$ is isomorphic to the
Lindenbaum–Tarski algebra $\operatorname{\mathbf{P}}(D)$ for the logic
$P\mkern-1.0mu\mathcal{L}_{D}$, built from the propositional variables
$\mathbb{P}_{\geq p}\,a$ by imposing the laws (L1)–(L5). This amounts to the
completeness of $P\mkern-1.0mu\mathcal{L}_{D}$ with respect to its
interpretation in $\operatorname{\mathcal{M}_{\Gamma}}(D)$.

######  Theorem 6.4 (Completeness).

Let $D$ be a distributive lattice. Then the lattice
$\operatorname{\mathbf{P}}(D)$ is isomorphic to the distributive lattice dual
to the Priestley space $\operatorname{\mathcal{M}_{\Gamma}}(D)$.

###### Proof.

Let $X_{\operatorname{\mathbf{P}}(D)}$ be the Priestley space dual to
$\operatorname{\mathbf{P}}(D)$. By Proposition 6.3, there is a map
$\vartheta\colon
X_{\operatorname{\mathbf{P}}(D)}\to\operatorname{\mathcal{M}_{\Gamma}}(D)$,
$F\mapsto\mu_{F}$. We claim that $\vartheta$ is an isomorphism of Priestley
space, i.e. a continuous bijection which is also an order embedding. The
statement then follows by duality.

It is not difficult to see that $\vartheta$ is monotone. Just observe that
$F_{1}\subseteq F_{2}$ implies

$\mu_{F_{1}}(a)=\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in
F_{1}\\}}\leq\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in
F_{1}\\}}=\mu_{F_{2}}(a)$

for all $a\in D$. Moreover, if $\mu_{F_{1}}(a)\not\leq\mu_{F_{2}}(a)$ for some
$a\in D$, then

$\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in
F_{1}\\}}=\mu_{F_{1}}(a)\not\leq\mu_{F_{2}}(a)=\bigwedge{\\{p^{-}\mid\mathbb{P}_{\geq
p}\,a\notin F_{2}\\}},$ (11)

where the last equality follows from the following fact:

######  Claim.

For every prime filter $F\in X_{\operatorname{\mathbf{P}}(D)}$,
$\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in
F\\}}=\bigwedge{\\{p^{-}\mid\mathbb{P}_{\geq p}\,a\notin F\\}}$.

###### Proof of Claim.

Fix an arbitrary $a\in D$. By (L1), it follows at once that

$\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in
F\\}}\leq\bigwedge{\\{p^{-}\mid\mathbb{P}_{\geq p}\,a\notin F\\}}.$

Suppose, by contradiction, that the inequality is strict. Then there must be
$r\in\mathbb{Q}\cap(0,1]$ such that

$\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in
F\\}}=r^{-}<r^{\circ}=\bigwedge{\\{p^{-}\mid\mathbb{P}_{\geq p}\,a\notin
F\\}}.$

(Just observe that $\\{q\mid\mathbb{P}_{\geq q}\,a\in F\\}$ and
$\\{p\mid\mathbb{P}_{\geq p}\,a\notin F\\}$ form a partition of
$\mathbb{Q}\cap[0,1]$.) If $\mathbb{P}_{\geq r}\,a\in F$, then
$r^{\circ}\leq\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in F\\}}=r^{-}$,
a contradiction. Similarly, if $\mathbb{P}_{\geq r}\,a\notin F$ we get
$r^{\circ}=\bigwedge{\\{p^{-}\mid\mathbb{P}_{\geq p}\,a\notin F\\}}\leq
r^{-}$, a contradiction. ∎

Equation (11) implies the existence of $p,q$ satisfying $\mathbb{P}_{\geq
q}\,a\in F_{1}$, $\mathbb{P}_{\geq p}\,a\notin F_{2}$ and $q^{\circ}\not\leq
p^{-}$, i.e. $q\geq p$. It follows by (L1) that $\mathbb{P}_{\geq p}\,a\in
F_{1}$. We conclude that $\mathbb{P}_{\geq p}\,a\in F_{1}\setminus F_{2}$,
whence $F_{1}\not\subseteq F_{2}$. This shows that $\vartheta$ is an order
embedding.

Next, we prove that $\vartheta$ is surjective. Fix a measure
$\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D)$. It is not hard to see, using
Lemma 6.1, that the filter $F_{\mu}\subseteq\operatorname{\mathbf{P}}(D)$
generated by

$\\{\mathbb{P}_{\geq q}\,a\mid a\in D,\ q\in\mathbb{Q}\cap[0,1],\
q^{\circ}\leq\mu(a)\\}$

is prime. Further,
$\vartheta(F_{\mu})(a)=\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq q}\,a\in
F_{\mu}\\}}=\bigvee{\\{q^{\circ}\mid q^{\circ}\leq\mu(a)\\}}=\mu(a)$ for every
$a\in D$. Hence, $\vartheta(F_{\mu})=\mu$ and $\vartheta$ is surjective. Since
$\vartheta$ is an order embedding, it is also injective, whence a bijection.

To settle the theorem, it remains to show that $\vartheta$ is continuous. For
every subset of $\operatorname{\mathcal{M}_{\Gamma}}(D)$ of the form
$\llbracket a\geq
p\rrbracket=\\{\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D)\mid\mu(a)\geq
p^{\circ}\\}$ where $a\in D$ and $p\in\mathbb{Q}\cap[0,1]$,

$\displaystyle\vartheta^{-1}(\llbracket a\geq p\rrbracket)$
$\displaystyle=\\{F\in X_{\operatorname{\mathbf{P}}(D)}\mid\mu_{F}(a)\geq
p^{\circ}\\}$ $\displaystyle=\\{F\in
X_{\operatorname{\mathbf{P}}(D)}\mid\bigvee{\\{q^{\circ}\mid\mathbb{P}_{\geq
q}\,a\in F\\}}\geq p^{\circ}\\}$ $\displaystyle=\\{F\in
X_{\operatorname{\mathbf{P}}(D)}\mid\mathbb{P}_{\geq p}\,a\in F\\}$

which is an open subset of $X_{\operatorname{\mathbf{P}}(D)}$. Similarly, for
a subset of $\operatorname{\mathcal{M}_{\Gamma}}(D)$ of the form $\llbracket
a<q\rrbracket=\\{\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D)\mid\mu(a)\leq
q^{-}\\}$ with $a\in D$ and $q\in\mathbb{Q}\cap(0,1]$, in view of the Claim
above we have that $\vartheta^{-1}(\llbracket a<q\rrbracket)=\\{F\in
X_{\operatorname{\mathbf{P}}(D)}\mid\mathbb{P}_{\geq q}\,a\notin F\\}$, which
is again open in $X_{\operatorname{\mathbf{P}}(D)}$. Hence, $\vartheta$ is
continuous. ∎

#### Adding Boolean complements.

By Theorem 6.4, for any distributive lattice $D$, the lattice of clopen up-
sets of $\operatorname{\mathcal{M}_{\Gamma}}(D)$ is isomorphic to the
Lindenbaum–Tarski algebra $\operatorname{\mathbf{P}}(D)$ of our “positive”
propositional logic $P\mkern-1.0mu\mathcal{L}_{D}$. Moving from the lattice of
clopen up-sets to the Boolean algebra of _all_ clopens logically corresponds
to adding negation to the logic. The logic obtained in this way can be
presented as follows.

Introduce a new propositional variable $\mathbb{P}_{<q}\,a$ for each $a\in D$
and $q\in\mathbb{Q}\cap[0,1]$. We add, along with the propositional connective
$\neg$, also a new rule to the logic $P\mkern-1.0mu\mathcal{L}_{D}$, stating
that $\mathbb{P}_{<q}\,a$ is the negation of $\mathbb{P}_{\geq q}\,a$:

  1. (L6)

$\mathbb{P}_{<q}\,a\wedge\mathbb{P}_{\geq q}\,a\vdash\mathbf{f}$ and
$\mathbf{t}\vdash\mathbb{P}_{<q}\,a\vee\mathbb{P}_{\geq q}\,a$

(Equivalently, $\mathbb{P}_{\geq q}\,a\vdash\neg\mathbb{P}_{<q}\,a$ and
$\neg\mathbb{P}_{<q}\,a\vdash\mathbb{P}_{\geq q}\,a$.) Write
$\mathcal{PL}^{*}_{D}$ for the ensuing logic.

For a measure $\mu\in\operatorname{\mathcal{M}_{\Gamma}}(D)$, the new
propositional variables are interpreted as

$\mu\models\mathbb{P}_{<q}\,a\ \Leftrightarrow\ \mu(a)<q^{\circ}.$

Clearly, (L6) is satisfied in $\operatorname{\mathcal{M}_{\Gamma}}(D)$.
Moreover, it is not difficult to see that the Boolean algebra of all clopen
subsets of $\operatorname{\mathcal{M}_{\Gamma}}(D)$ is isomorphic to the
quotient of the free distributive lattice on

$\\{\mathbb{P}_{\geq p}\,a\mid p\in\mathbb{Q}\cap[0,1],\ a\in
D\\}\cup\\{\mathbb{P}_{<q}\,b\mid q\in\mathbb{Q}\cap[0,1],\ b\in D\\}$

with respect to the congruence generated by (L1)–(L6). In turn, the latter is
isomorphic to the Lindenbaum–Tarski algebra of the logic
$\mathcal{PL}^{*}_{D}$. That is, $\mathcal{PL}^{*}_{D}$ is complete with
respect to its interpretation in $\operatorname{\mathcal{M}_{\Gamma}}(D)$.

#### Specialising to $\mathrm{FO}(\sigma)$.

Let us briefly discuss what happens when we instantiate $D$ with the full
first-order logic $\mathrm{FO}(\sigma)$. For a formula
$\varphi\in\mathrm{FO}(\sigma)$ with free variables among $v_{1},\dots,v_{n}$
and a rational $q\in\mathbb{Q}\cap[0,1]$, we have two new sentences
$\mathbb{P}_{\geq q}\,\varphi$ and $\mathbb{P}_{<q}\,\varphi$. For a finite
$\sigma$-structure $A$ identified—via the ${\mathbf{\Gamma}}$-valued Stone
pairing—with the measure $\left<\mkern 1.5mu\text{-}\mkern
1.5mu,A\right>_{\mathrm{\Gamma}}$,

$A\models\mathbb{P}_{\geq q}\,\varphi{\quad\text{if, and only
if,}\quad}\left<\varphi,A\right>_{\mathrm{\Gamma}}\geq q^{\circ}$

and

$A\models\mathbb{P}_{<q}\,\varphi{\quad\text{if, and only
if,}\quad}\left<\varphi,A\right>_{\mathrm{\Gamma}}<q^{\circ}.$

That is, $\mathbb{P}_{\geq q}\,\varphi$ is true in $A$ precisely when a random
assignment of the variables $v_{1},\dots,v_{n}$ in $A$ satisfies $\varphi$
with probability at least $q$. And similarly for $\mathbb{P}_{<q}\,\varphi$.

For example, in the language of (undirected) graphs, i.e. when $\sigma$
consists of one binary relation $R(\mkern 1.5mu\text{-}\mkern 1.5mu,\mkern
1.5mu\text{-}\mkern 1.5mu)$, the formula
$\mathbb{P}_{\geq\frac{1}{2}}\,R(x,x)$ in
$P\mkern-1.0mu\mathcal{L}_{\mathrm{FO}(\sigma)}$ expresses the property that
at least half of the vertices have a loop.

The following is a special instance of the results presented above:

######  Theorem 6.5.

The Boolean space $\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$
is dual to the Lindenbaum–Tarski algebra of the propositional logic having as
atoms $\mathbb{P}_{\geq q}\,\varphi$ and $\mathbb{P}_{<q}\,\varphi$, for each
$\varphi\in\mathrm{FO}(\sigma)$ and $q\in\mathbb{Q}\cap[0,1]$, and the
following inference rules (along with the usual ones for the Boolean
connectives):

$\begin{gathered}\mathbb{P}_{\geq p}\,\varphi\mathbb{P}_{\geq
q}\,\varphi\hskip 14.00003pt\mathbb{P}_{\geq q}\,\psi\mathbb{P}_{\geq
q}\,\varphi\hskip 14.00003pt\mathbb{P}_{\geq 0}\,\bot\hskip
14.00003pt\mathbb{P}_{<q}\,\bot\hskip 14.00003pt\mathbb{P}_{\geq
q}\,\top\hskip 14.00003pt\neg\mathbb{P}_{<q}\,\varphi\mathbb{P}_{\geq
q}\,\varphi\\\\[8.61108pt] \mathbb{P}_{\geq
p+q-r}\,(\varphi\vee\psi)\,\vee\,\mathbb{P}_{\geq
r}\,(\varphi\wedge\psi)\mathbb{P}_{\geq p}\,\varphi\,\wedge\,\mathbb{P}_{\geq
q}\,\psi\hskip 20.00003pt\mathbb{P}_{\geq p}\,\varphi\,\vee\,\mathbb{P}_{\geq
q}\,\psi\mathbb{P}_{\geq p+q-r}\,(\varphi\vee\psi)\,\wedge\,\mathbb{P}_{\geq
r}\,(\varphi\wedge\psi)\end{gathered}$

Therefore, if we regard $\mathbb{P}_{\geq q}\,$ and $\mathbb{P}_{<q}\,$ as
probabilistic quantifiers that bind all free variables of a given formula,
then the Stone pairing $\left<\mkern 1.5mu\text{-}\mkern 1.5mu,\mkern
1.5mu\text{-}\mkern
1.5mu\right>_{\mathrm{\Gamma}}\colon\mathrm{Fin}(\sigma)\to\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$
can be seen as the embedding of finite structures into the space of $0$-types
for the logic with probabilistic quantifiers axiomatised in the previous
theorem.

## Conclusion

Types are points of the dual space of a logic (identified with its
Lindenbaum–Tarski algebra). In classical first-order logic, $0$-types are just
the models modulo elementary equivalence. But when there are not ‘enough’
models, as in finite model theory, the spaces of types provide completions of
the sets of models.

In [10], it was shown that for logic on words and various quantifiers we have
that, given a Boolean algebra of formulas with a free variable, the space of
types of the Boolean algebra generated by the formulas obtained by
quantification is given by a space-of-measures construction. Here we have
shown that a suitable enrichment of first-order logic gives rise to a space of
measures $\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ closely
related to the space $\operatorname{\mathcal{M}_{I}}(\mathrm{FO}(\sigma))$
used in the theory of structural limits. Indeed, Theorem 5.5 tells us that the
ensuing Stone pairings interdetermine each other. Further, the Stone pairing
for $\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ is just the
embedding of the finite models in the completion/compactification provided by
the space of $0$-types of the enriched logic (Theorem 6.5).

These results identify the logical gist of the theory of structural limits,
and provide a new and interesting connection between logic on words and the
theory of structural limits in finite model theory. But we also expect that it
may prove a useful tool in its own right.

For instance, for structural limits, it is an open problem to characterise the
closure $\overline{\mathrm{Fin}(\sigma)}$ of the image of the $[0,1]$-valued
Stone pairing [26]. The same question translates equivalently to the
${\mathbf{\Gamma}}$-valued setting (Theorem 5.7), native to logic and where we
can use duality. The closure $\overline{\mathrm{Fin}(\sigma)}$, seen as a
subspace of $\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$, is
also a Priestley space and this embedding dually corresponds to a quotient of
the Lindenbaum–Tarski algebra of the enriched logic. Understanding this
quotient is crucial in order to characterise
$\overline{\mathrm{Fin}(\sigma)}$. One would expect that this is the subspace
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(T_{\text{\em fin}}))$ of
$\operatorname{\mathcal{M}_{\Gamma}}(\mathrm{FO}(\sigma))$ given by the
quotient $\mathrm{FO}(\sigma)\twoheadrightarrow\mathrm{FO}(T_{\text{\em
fin}})$ onto the theory of pseudofinite structures. The purpose of such a
characterisation would be to understand the points of the closure as
“generalised models”.

Another subject that we would like to investigate is that of zero-one laws.
The zero-one law for first-order logic states that the sequence of measures
for which the $n$th measure, on a sentence $\psi$, yields the proportion of
$n$-element structures satisfying $\psi$, converges to a $\\{0,1\\}$-valued
measure. Over ${\mathbf{\Gamma}}$ this will no longer be true as $1$ is split
into its “limiting” and “achieved” personae. Yet, we expect the above sequence
to converge also in this setting and, by Theorem 5.5, it will converge to a
$\\{0^{\circ},1^{-},1^{\circ}\\}$-valued measure. Understanding this finer
grained measure may yield useful information about the zero-one law.

Further, it would be interesting to investigate whether the limits for schema
mappings introduced by Kolaitis _et al._ [21] may be seen also as a type-
theoretic construction. Also, we would want to explore the connections with
other semantically inspired approaches to finite model theory, such as those
recently put forward by Abramsky, Dawar _et al._ [2, 3].

Finally, we mention that the axiomatisation of our logic with probabilistic
quantifiers (cf. Theorem 6.5) seems to be related to other axiomatisations of
logics arising from space-of-measures constructions which have appeared in the
literature. See e.g. [22, 5] for an axiomatisation based on the language of
$\sigma$-Boolean algebras, and [30] for an axiomatisation employing the
language of propositional geometric logic. The main difference resides in the
fact that our axiomatisation is based on a finitary logic which involves only
the basic Boolean connectives.

##  Appendix A Extended Priestley duality and canonical extensions

The purpose of this section is to provide the necessary background on extended
Priestley duality so that, in Appendix B, we can justify the definition of
${\mathbf{\Gamma}}$ and its structure. There is a rich literature on
extensions of the duality between distributive lattices and Priestley spaces
to dualities for lattices with additional operations, see e.g. [15]. The
prototypical example (in the case of Boolean algebras) is the celebrated
Jónsson–Tarski duality [18, 19], from which most of the theory originates.

We present an algebraic approach to extended Priestley duality which is based
on the theory of canonical extensions. Its main feature is that both the space
$X$ and its dual lattice $A$ embed (order-theoretically) into a complete
lattice $A^{\delta}$, the _canonical extension_ of $A$. This allows us to
capture Priestley duality in purely algebraic terms, and is an incredibly
powerful approach for dealing with additional operations on lattices. For
example, if $A$ comes equipped with a binary operation $h\colon A\times A\to
A$ then, by studying the relationship between the graph of $h$ and the points
of $X$ in the product $A^{\delta}\times A^{\delta}\times A^{\delta}$, we can
identify two partial binary operations on $X$ that fully capture $h$. An
instance of this situation is studied in this section. Our main inspiration
comes from [12, 13] and also [6].

###  A.1. Basic notation and terminology

The canonical extension of a (bounded) distributive lattice $A$ is an
embedding $e\colon A\hookrightarrow A^{\delta}$ of $A$ into a complete lattice
$A^{\delta}$ which is _dense_ and _compact_ :

  1. (Dense)

Every element of $A^{\delta}$ is both a join of meets and a meet of joins of
elements in the image of $e$.

  2. (Compact)

Given subsets $S$ and $T$ of $A$ with $\bigwedge{e(S)}\leq\bigvee{e(T)}$,
there are finite sets $S^{\prime}\subseteq S$ and $T^{\prime}\subseteq T$ such
that $\bigwedge{e(S^{\prime})}\leq\bigvee{e(T^{\prime})}$.

Canonical extensions of distributive lattices always exist and are unique, up
to isomorphism. In fact, $A^{\delta}$ is isomorphic to the lattice of all up-
sets of the Priestley space dual to $A$.666Note that, with respect to the
convention of Remark A.1 below, $A^{\delta}$ is actually isomorphic to the
down-sets of the dual space. In the following, we will always identify $A$
with a sublattice of its canonical extension $A^{\delta}$.

_Open elements_ of $A^{\delta}$ are those of the form $\bigvee S$, for some
$S\subseteq A$. The set of all open elements of $A^{\delta}$ is denoted
$\mathcal{I}(A^{\delta})$. In fact, there is a bijection between open elements
of $A^{\delta}$ and ideals of $A$, given by
$i\in\mathcal{I}(A^{\delta})\mapsto\mathord{\downarrow}\mkern 1.0mui\cap A$
and $I\subseteq A\mapsto\bigvee I$. The latter restricts to a bijection
between the set $\mathcal{M}^{\infty}(A^{\delta})$ of completely meet-
irreducible elements of $A^{\delta}$ and prime ideals of $A$. Recall that
$p\in A^{\delta}$ is _completely meet-irreducible_ if, for all $S\subseteq C$,
$\bigwedge S\leq p$ implies $a\leq p$ for some $a\in S$. The set
$\mathcal{F}(A^{\delta})$ of _closed elements_ of $A^{\delta}$, and the set
$\mathcal{J}^{\infty}(A^{\delta})$ of _completely join-irreducible elements_
of $A^{\delta}$ are defined order-dually.

Note that $\mathcal{M}^{\infty}(A^{\delta})$ does not include the top element
of $A^{\delta}$. However, it is sometimes useful to add it, and so we will
denote by $\mathcal{M}^{\infty}_{1}(A^{\delta})$ the set
$\mathcal{M}^{\infty}(A^{\delta})\cup\\{1\\}$ and, similarly,
$\mathcal{J}^{\infty}_{0}(A^{\delta})$ denotes the set
$\mathcal{J}^{\infty}(A^{\delta})\cup\\{0\\}$.

For a distributive lattice $A$, every element of $A^{\delta}$ is a meet of
completely meet-irreducible elements and a join of completely join-
irreducible. Moreover, if we equip $\mathcal{J}^{\infty}(A^{\delta})$ and
$\mathcal{M}^{\infty}(A^{\delta})$ with the partial orders induced by
$A^{\delta}$, we have an order-isomorphism

$\kappa\colon\mathcal{J}^{\infty}(A^{\delta})\to\mathcal{M}^{\infty}(A^{\delta}),\
\ j\mapsto\bigvee{\\{a\in A\mid j\not\leq a\\}}$

satisfying, for every
$m\in\mathcal{M}^{\infty}(A^{\delta}),j\in\mathcal{J}^{\infty}(A^{\delta})$
and $u\in A^{\delta}$,

$u\leq\kappa(j)\iff j\nleq u{\quad\text{and}\quad}\kappa^{-1}(m)\leq u\iff
u\nleq m.$

This corresponds to the fact that the complement of a prime filter is a prime
ideal, and vice versa. For more details, we refer the reader to [9].

###  A.2. Priestley duality

Thanks to the correspondence between prime filters (resp. prime ideals) of a
distributive lattice $A$ and completely join-irreducible (resp. completely
meet-irreducible) elements of $A^{\delta}$, we can retrieve the Priestley
space $X=(X,\leq,\tau)$ dual to $A$ by endowing either the set
$\mathcal{M}^{\infty}(A^{\delta})$, or the set
$\mathcal{J}^{\infty}(A^{\delta})$, with an order and topology. Both choices
result in the same space, but we opt for the former as it provides a minor
technical advantage in our applications. The order on
$\mathcal{M}^{\infty}(A^{\delta})$ is inherited from $A^{\delta}$ and the
subbase of the topology is formed by the sets $\\{m\mid a\nleq m\\}$ and their
complements, for every $a\in A$.

######  Remark A.1.

We warn the reader that, with the definition of dual Priestley space given in
Section 2.1, the Priestley space $X$ just defined is, in fact, dual to the
lattice $A^{\mathrm{op}}$ and not $A$. Just observe that, for
$m,n\in\mathcal{M}^{\infty}(A^{\delta})$,

$m\leq n\enspace\iff\enspace I_{m}\subseteq I_{n}\enspace\iff\enspace
F_{\kappa^{-1}(m)}\supseteq F_{\kappa^{-1}(n)},$

where $I_{m}=\\{a\in A\mid a\leq m\\}$ is the prime ideal corresponding to
$m\in\mathcal{M}^{\infty}(A^{\delta})$ and $F_{j}=\\{a\in A\mid j\leq a\\}$ is
the prime filter corresponding to $j\in\mathcal{J}^{\infty}(A^{\delta})$. When
working with canonical extensions, it is convenient to order prime filters by
_reverse_ inclusion, so that both $X$ and its dual lattice $A$ order-
theoretically embed into $A^{\delta}$. However, we opted for the inclusion
order in the main text because it gives the usual pointwise order between
measures. To apply the general theory to ${\mathbf{\Gamma}}$, in Appendix B we
will take order-duals on the lattice side.

To also capture the duality between lattice homomorphisms and Priestley
morphisms, we recall how maps between lattices extend to maps between their
canonical extensions. For a monotone map $f\colon A\to B$ between distributive
lattice, its _sigma extension_ $f^{\sigma}\colon A^{\delta}\to B^{\delta}$ is
defined by

$\displaystyle f^{\sigma}(k)$ $\displaystyle=\bigwedge\\{f(a)\mid a\in
A{\enspace\text{and}\enspace}k\leq a\\}\quad\text{for all
}k\in\mathcal{F}(A^{\delta})$ $\displaystyle f^{\sigma}(u)$
$\displaystyle=\bigvee\\{f^{\sigma}(k)\mid
k\in\mathcal{F}(A^{\delta}){\enspace\text{and}\enspace}k\leq
u\\}\quad\text{for all }u\in A^{\delta}$

and, dually, its _pi extension_ $f^{\pi}\colon A^{\delta}\to B^{\delta}$ is
defined by

$\displaystyle f^{\pi}(i)$ $\displaystyle=\bigvee\\{f(a)\mid a\in
A{\enspace\text{and}\enspace}a\leq i\\}\quad\text{for all
}i\in\mathcal{I}(A^{\delta})$ $\displaystyle f^{\pi}(u)$
$\displaystyle=\bigwedge\\{f^{\pi}(i)\mid
i\in\mathcal{I}(A^{\delta}){\enspace\text{and}\enspace}u\leq
i\\}\quad\text{for all }u\in A^{\delta}.$

The two extensions are closely related as they agree on open and closed
elements. Moreover, if $f$ preserves binary joins, then $f^{\sigma}$ preserves
all non-empty joins and, similarly, if $f$ preserves binary meets, then
$f^{\pi}$ preserves all non-empty meets.

Whenever $f^{\sigma}=f^{\pi}$, we say that $f$ is _smooth_ and denote the
unique extension by $f^{\delta}$. This happens, for example, when $f$
preserves finite (possibly empty) joins or finite meets. Recall that a
monotone map $f$ between complete lattices preserves all joins if and only if
it has a right adjoint $f^{\\#}$ and, dually, it preserves all meets precisely
when it has a left adjoint $f^{\flat}$. Moreover, if $h\colon A\to B$ is a
lattice homomorphism, the right adjoint $h^{\delta}{}^{\\#}$ of
$h^{\delta}\colon A^{\delta}\to B^{\delta}$ preserves completely meet-
irreducible elements and, dually, the left adjoint $h^{\delta}{}^{\flat}$
preserves completely join-irreducible elements. We can compute the continuous
monotone map dual to a homomorphism $h\colon A\to B$ as the restriction of
$h^{\delta}{}^{\\#}\colon B^{\delta}\to A^{\delta}$ to the completely meet-
irreducible elements. Note that, if we defined dual Priestley spaces as based
on $\mathcal{J}^{\infty}(A^{\delta})$, we would have to take the restriction
of $h^{\delta}{}^{\flat}\colon B^{\delta}\to A^{\delta}$ to completely join-
irreducible elements.

###  A.3. Duality theory for operators

In this section we outline some facts about the duality theory of normal
double quasioperators $A^{n}\to A$ based on [12, 13]. Double quasioperators
are double operators where arguments can have different monotonicity types. In
order to avoid the notational difficulties that arise when presenting the
theory for different monotonicity types, we assume that we have a three-sorted
binary operator which is monotone in both coordinates.

######  Definition A.2.

Let $A,B$ and $C$ be distributive lattices. A mapping $h\colon A\times B\to C$
between lattices is a _three-sorted operator_ if

  * •

$h$ is a double operator, i.e. $h$ preserves binary meets and binary joins in
both coordinates,

  * •

$h$ is dual-normal, that is, $h(a,1)=1=h(1,b)$ for every $a\in A$ and $b\in
B$, and

  * •

$h(0,0)=0$.

######  Remark A.3.

Everything true of three-sorted operators can also be applied to the dual
scenario as well, that is, to the double operators $g\colon A\times B\to C$
such that $g(a,0)=0=g(0,b)$ and $g(1,1)=1$. In this case, we simply treat $g$
as a three-sorted operator of the type $A^{\mathrm{op}}\times
B^{\mathrm{op}}\to C^{\mathrm{op}}$. Similarly, the same definition can be
used to deal with different monotonicity types, such as a double operator
which is antitone in the second coordinate $A\times B^{\mathrm{op}}\to C$.
Here, only the coordinates that are antitone have to be considered dually.

Throughout this section we fix a three-sorted operator $h\colon A\times B\to
C$. We denote the Priestley spaces dual to the distributive lattices $A$, $B$
and $C$ by $X$, $Y$ and $Z$, respectively. Because $h\colon A\times B\to C$
preserves finite meets (including the empty meet $1$) and binary joins in both
coordinates, its pi extension $f\coloneqq h^{\pi}\colon A^{\delta}\times
B^{\delta}\to C^{\delta}$ preserves all meets in both coordinates and its
sigma extension $g\coloneqq h^{\sigma}\colon A^{\delta}\times B^{\delta}\to
C^{\delta}$ is a complete operator (i.e. it preserves all non-empty joins in
both coordinates).

We will also make use of the map $@\colon A\to C$ defined as $a\mapsto
h(a,0)$. Observe that it preserves finite meets and finite joins, hence it is
a lattice homomorphism. The continuous monotone map $i\colon Z\to X$ dual to
$@\colon A\to C$ is simply the restriction of the right adjoint of
$@^{\delta}\colon A^{\delta}\to C^{\delta}$ to
$\mathcal{M}^{\infty}(C^{\delta})\to\mathcal{M}^{\infty}(A^{\delta})$.

######  Lemma A.4.

For every $u\in\mathcal{I}(A^{\delta})\cup\mathcal{F}(A^{\delta})$ we have
$@^{\delta}u=f(u,0)=g(u,0)$.

###### Proof.

For $i\in\mathcal{I}(A^{\delta})$, $f(i,0)=\bigvee\\{h(a,0)\mid a\in
A{\enspace\text{and}\enspace}a\leq i\\}=@^{\pi}i=@^{\delta}i$ because
$(A\times B)^{\delta}\cong A^{\delta}\times B^{\delta}$ and
$\mathcal{I}(A^{\delta}\times
B^{\delta})\cong\mathcal{I}(A^{\delta})\times\mathcal{I}(B^{\delta})$. Also,
$@^{\delta}i=g(i,0)$ holds because $f$ and $g$ agree on open and closed
elements. The same proof, mutatis mutandis, shows that
$@^{\delta}k=g(k,0)=f(k,0)$ for all $k\in\mathcal{F}(A^{\delta})$. ∎

###  A.4. The first partial operation

Traditionally, given a distributive lattice with a quasioperator, one endows
the dual Priestley space with two ternary relations satisfying certain
topological and order-theoretic properties which uniquely characterise the
quasioperator. As was already evident in [12, 13] (and successfully applied in
[6]), these two relations arise from two partial operations, by taking the
upwards or downwards closures of the codomains.

The first partial operation represents the pi extension of our operator
$h\colon A\times B\to C$. Fix $u\in A^{\delta}$. Since $f(u,\mkern
1.5mu\text{-}\mkern 1.5mu)$ preserves all meets, it has a left adjoint
$f^{\flat}_{1}\colon A^{\delta}\times C^{\delta}\to B^{\delta}$, i.e.

$f^{\flat}_{1}(u,w)\leq v{\quad\text{if, and only if,}\quad}w\leq
f(u,v)\qquad\forall v\in B^{\delta},\,w\in C^{\delta}.$

In fact, this left adjoint can be restricted to the points of the dual
Priestley spaces.

######  Lemma A.5.

The following statements hold:

  1. (1)

For all $w\in C^{\delta}$, $f^{\flat}_{1}(\mkern 1.5mu\text{-}\mkern 1.5mu,w)$
is antitone and sends meets to joins;

  2. (2)

$f^{\flat}_{1}$ restricts to a map
$\mathcal{M}^{\infty}(A^{\delta})^{\mathrm{op}}\times\mathcal{J}^{\infty}(C^{\delta})\to\mathcal{J}^{\infty}_{0}(B^{\delta})$;

  3. (3)

For $x\in X$ and $z\in Z$, $f^{\flat}_{1}(x,\kappa^{-1}(z))\neq 0$ iff $x\leq
i(z)$.

###### Proof.

Items 1 and 2 follow by Proposition 4.1 and Theorem 4.4, respectively, in
[12].

(3) By Lemma A.4 and the definition of $i$,
$f^{\flat}_{1}(x,\kappa^{-1}(z))\nleq 0$ iff $\kappa^{-1}(z)\nleq
f(x,0)=@^{\delta}x$ iff $@^{\delta}x\leq z$ iff $x\leq i(z)$. ∎

Recall that we assumed that Priestley duals are based on the sets of
completely meet-irreducible elements of the respective canonical extensions.
Therefore, Lemma A.5 shows that we can define the first partial operation

$-\colon Z\times X\rightharpoonup Y$

with $\mathrm{dom}(-)=\\{(z,x)\mid x\leq i(z)\\}$,777Observe that we decided
to flip the arguments of $f^{\flat}_{1}$. This is because we typically think
of the minus operation as being antitone in the second argument, whereas
$f^{\flat}_{1}$ is antitone in the first argument. by setting

$z-x\enspace\coloneqq\enspace\kappa(f^{\flat}_{1}(x,\kappa^{-1}(z))),$

where $\kappa$ is the order-isomorphism between
$\mathcal{J}^{\infty}(C^{\delta})$ and $\mathcal{M}^{\infty}(C^{\delta})$.

######  Lemma A.6.

If $\mathrm{dom}(-)$ is seen as a subspace of $Z\times X^{\mathrm{op}}$, the
following hold:

  1. (1)

$\mathrm{dom}(-)$ is a closed up-set of $Z\times X^{\mathrm{op}}$;

  2. (2)

$-\colon\mathrm{dom}(-)\to Y$ is lower semicontinuous and monotone.

###### Proof.

(1) $\mathrm{dom}(-)$ is an up-set because $i\colon Z\to X$ is monotone, and
is closed as it coincides with the preimage of the closed subspace ${\geq}$ of
$X\times X$ under the continuous map $i\times\mathrm{id}$.

(2) Given $a\in A$, set $\widehat{a}=\\{x\in X\mid a\nleq x\\}$. First,
observe that $(-)^{-1}(\widehat{a})$ is equal to the following open subset of
$\mathrm{dom}(-)$:

$\mathrm{dom}(-)\cap\bigcup_{b\in
A}\widehat{h(b,a)}\times(X\setminus\widehat{b}).$

For the right-to-left inclusion, assume that $h(b,a)\nleq z$, $b\leq x$, and
$x\leq i(z)$. Since $h(b,a)=f(b,a)$, we have $f(x,a)\nleq z$ iff
$\kappa^{-1}z\leq f(x,a)$ iff $f^{\flat}_{1}(x,\kappa^{-1}z)\leq$ iff $a\nleq
z-x$. Conversely, if $(z,x)\in\mathrm{dom}(-)$ then $a\leq x-x$ iff
$f^{\flat}_{1}(x,\kappa^{-1}z)\leq a$ iff $f(x,a)\nleq z$. Since
$x=\bigvee_{i}b_{i}$ for some non-empty subset $\\{b_{i}\\}_{i}$ of $A$, and
$f$ agrees with $g$ on open elements and $g$ distributes over non-empty joins,
$f(x,a)\nleq z$ iff $\bigvee_{i}h(b_{i},a)\nleq z$ iff $h(b_{i},a)\nleq$ for
some $i$. Consequently, $(z,x)$ belongs to