1 Introduction
The development of theories of continuous limiting structures of combinatorial objects is a subject with a rich history and many actively developing directions [Reference Elek and Szegedy16, Reference Goldbring and Towsner23, Reference Kardoš, Král, Liebenau and Mach30, Reference Lovász33, Reference Nesetril and de Mendez40, Reference Razborov46]. In many of these approaches, the interface of model-theoretic techniques, especially ultraproduct constructions and ultralimits, with analytic concepts such as measurability plays a central role. Though still a young subject, the model theory of metric structures as developed in the seminal work of Ben Yaacov et al. [Reference Ben Yaacov, Alexander, Ward Henson and Usvyatsov4] has provided a powerful toolkit of model-theoretic methods which are well adapted for a wide range of analytic objects, such as Banach spaces, dynamical systems, and operator algebras [Reference Ben Yaacov, Alexander, Ward Henson and Usvyatsov4, Reference Farah, Hart, Lupini, Robert, Tikuisis, Vignati and Winter18, Reference Goldbring22, Reference Sinclair51]. In fact, many of the widely studied classes of metric structures possess a lattice structure which is either crucial to their axiomatization, as in the case of Boolean algebras and
$L^p$
-spaces [Reference Ben Yaacov, Alexander, Ward Henson and Usvyatsov4, Reference Henson and Raynaud26], or is at least central to the general theory, such as the lattice of projections in the theory von Neumann algebras [Reference Farah, Hart and Sherman19]. The goal of the present manuscript is then to isolate and study metric lattices as structures in their own right, with a more explicitly combinatorial bent, and with the thesis that the framework of the model theory of metric structures can be fruitfully used to explore notions of analytic limiting structures. After developing the general theory, we provide applications to the special case of finite partition lattices, investigating which properties, from the model-theoretic point of view, limits of such lattices ought to have. Our analysis complements and clarifies earlier work on inductive limits of partition lattices by Björner [Reference Björner9, Reference Björner10].
A finite lattice
$L$
with a minimal element
$0$
comes equipped with a height function, where the height
$|x|$
of an element
$x$
is the smallest number of atoms (minimal non-zero elements) whose join is
$x$
. If this height function is an order-preserving map to
$\mathbb Z$
and satisfies the submodularity condition
$|x+y| + |xy|\leq |x| + |y|$
, where
$x+y$
and
$xy$
are the meet and join, respectively, of
$x$
and
$y$
, then lattice is said to be geometric [Reference Birkhoff8, Chapter IV]. Wilcox and Smiley [Reference Wilcox and Smiley53] realized that the height function on a geometric lattice could be used to define a metric on the lattice and that algebraic properties of the lattice, such as modularity, could be phrased in terms of properties of the metric. This point of view was greatly expanded and developed in works of Sachs [Reference Sachs49], Björner [Reference Björner9, Reference Björner10], and Björner and Lovász [Reference Björner and Lovász12] where a study of continuous inductive limits of certain classes of geometric lattices was initiated, inspired by von Neumann’s theory of continuous geometries [Reference von Neumann42]. A very much related line of inquiry was recently launched by Lovász on the limiting theory of submodular functions [Reference Lovász34] and continuous limits of matroids [Reference Lovász35] (see also [Reference Bérczi, Borbényi, Lovász and Tóth5, Reference Kardoš, Král, Liebenau and Mach30]). We note that there is a correspondence between matroids and geometric lattices, though this correspondence is not functorial in the sense that many important constructions on either side do not carry over to the other. On the model-theoretic side, the model theory of probability spaces, that is, of metrized Boolean lattices, was fully developed in [Reference Ben Yaacov, Alexander, Ward Henson and Usvyatsov4] (see also the expository paper [Reference Berenstein and Henson6]). These works form the point of departure for what follows.
After recalling some background in lattice theory and the model theory of metric structures in Section 2, our first task is to describe a first-order theory for metric lattices which is suitably general to capture all geometric lattices with metrics which come from their height (rank) functions. Immediately, we are confronted with the fact that while the join function is jointly contractive in the metric, the meet function does not possess a uniform modulus of continuity over all geometric lattices [Reference Björner10, p. 23]. From the perspective of model theory, this means that we are forbidden from using the meet operation in any expression. While Björner and Lovász in [Reference Björner and Lovász12] address this issue by studying limits for a more restrictive class of lattices which possess a continuous “pseudointersection” operation, we take up the theory of metric lattices from scratch and show that most of the meaningful properties which contain meet operations in their definitions (for instance, submodularity) actually imply, and therefore can be rephrased in terms of, expressions only involving the join operation. The tradeoff is that one must modestly increase the quantifier complexity of these expressions by taking infima and/or suprema over additional variables, rather than simple inequalities. In the case of metrically complete metric lattices, we then show that the meet can be canonically and uniquely reconstructed from the join. This is the content of Section 3.
We note that while the morphisms in our category of metric lattices need only preserve the join operation, this is likely the correct perspective, as this provides a more natural framework for studying quotients. For instance, sequences of “sparse” lattices might be suitably characterized as uniformly continuous quotients of Boolean or modular objects. A discussion of this, along with general constructions and examples, is found in Section 4. The section culminates in an interesting connection between lattice metrics and conditionally negative definite kernels induced by the join operation which was independently investigated by Lovász [Reference Lovász34] in the case of Boolean lattices.
Section 5 is the part of the article most directly focused on model theory proper. The main result of the section is to show that in the case of (metrically) modular lattices, the meet operation is definable which essentially means that it is permissible to write formal expressions using both the meet and join operations for this class. While the utility of our theory mainly lies in handling non-modular lattices, this serves as an important check that our axioms recover the right framework in the “tame” case of modular lattices where the meet operation is also uniformly contractive in the metric. Subsequently, we provide additional axioms for recovering distributive and Boolean metric lattices. Moreover, we show that the model theory of probability spaces as defined in [Reference Ben Yaacov, Alexander, Ward Henson and Usvyatsov4] can be recovered as a special case (i.e., an elementary class) within our more general metric lattice framework.
In Section 6 we apply our analysis to the set of finite partition lattices. From the model-theoretic perspective a good limiting object for this category ought to satisfy every formula satisfied by all finite partition lattices. We call such a complete metric lattice a pseudofinite partition lattice and seek to understand their structure. As emphasized in the prior work of Björner [Reference Björner9], the modular elements form a core for the partition lattice which is crucial to understanding the limiting structure. Therefore, the first major result in this section, Proposition 6.5, demonstrates that the distance to the modular elements can be uniformly controlled by a first-order formula over all finite partition lattices, so the modular elements form a definable set of elements. While the modular elements of a finite partition lattice do not form a sublattice, they do so approximately as the size of the partition set tends to infinity. As a consequence, for any infinite pseudofinite partition lattice, the modular elements form a complete Boolean sublattice (Proposition 6.15) which is consistent with the continuous partition lattice constructed by Björner. We then initiate a study of the full lattice relative to this Boolean core by assigning to every
$x$
element its set of modular complements
$\Gamma (x)$
or “selectors,” which are so termed as they select a unique element of each block of
$x$
in the case of a finite partition lattice. We then show, through a series of intricate combinatorial arguments culminating in Proposition 6.35, that the selectors can effectively reconstruct any infinite pseudofinite partition lattice as a meet subsemilattice of the lattice of subsets of a complete Boolean lattice. In this way our investigations may provide a suitable framework for a continuous limiting theory of matroids.
2 Model theory of metric structures
In this article we will use the model-theoretical framework as detailed in [Reference Ben Yaacov, Alexander, Ward Henson and Usvyatsov4, Reference Hart25] for the case of one-sorted structures. In particular, we define the following terms:
-
• A language, or signature, $\mathfrak L$
contains the usual sets of function, relation, and constant symbols with their respective arity, as in first-order logic. Additionally, the language will associate to each relation symbol
$R$
a function
$\Delta _R:[0,1]\rightarrow [0,1]$
, such that
$\lim _{\epsilon \rightarrow 0^+}\Delta (\epsilon )=0$
, which we call the uniform continuity modulus of
$R$
, and similarly for the function symbols. -
• The logical symbols used in first-order logic of $x=y$
,
$\forall _x$
, and
$\exists _x$
are replaced by
$d(x,y)=0$
,
$\sup _x$
, and
$\inf _x$
, respectively. Connectives are now all continuous functions
$u:[0,1]^n\to [0,1]$
for every
$n$
. -
• Given a language $\mathfrak L$
we say that
$\mathcal M$
is an
$\mathfrak L$
-structure if
$\mathcal M$
consists of a complete metric space of diameter one along with a collection of functions and distinguished elements satisfying the following. For every function symbol
$f\in \mathfrak L$
there is a corresponding uniformly continuous function
$f^{\mathcal M}: M^{a(f)} \rightarrow M$
where
$a(f)$
is the arity of
$f$
and
$\Delta _f$
is a witness of the uniform continuity of
$f^{\mathcal M}$
. For every relation symbol
$R\in \mathcal L$
there is a corresponding uniformly continuous function
$R^{\mathcal M}: M^{a(R)}\rightarrow [0,1]$
where
$a(R)$
is the arity of
$R$
and
$\Delta _R$
is a witness of the uniform continuity of
$R^{\mathcal M}$
. For every constant symbol
$c\in \mathfrak L$
there is a corresponding distinguished element
$c^{\mathcal M}\in M$
. -
• The notions of substructure and embedding between $\mathcal L$
-structures are defined in an analogous way to first-order logic. -
• The $\mathfrak L$
-terms are constructed analogously to classical first-order logic. Similarly, the
$\mathfrak L$
-formulas are constructed following the same process as in first-order logic. A formula with no unquantified variables is called a sentence. A formula
$\varphi (x)$
is satisfied for some tuple
$a\in M$
for
$\mathcal M$
an
$\mathcal L$
-structure if
$\varphi ^{\mathcal M}(a)=0$
. -
• Let $\Sigma $
be a set of
$\mathcal L$
-sentences. We say that an
$\mathfrak L$
-structure models
$\Sigma $
, written
$\mathcal M\models \Sigma $
if
$\sigma ^{\mathcal M}=0$
for all
$\sigma \in \Sigma $
. The set
$\Sigma $
is satisfiable if it admits a model, in which case we write
$\operatorname {\mathrm {Mod}}(\Sigma )$
for the class of all models of
$\Sigma $
. -
• An $\mathfrak L$
-theory is a collection of satisfiable
$\mathfrak L$
-sentences. -
• A definable predicate or $T$
-formula is the limit of a sequence of formulas that converge uniformly over all models
$\mathcal M$
of an
$\mathfrak L$
-theory
$T$
. -
• A homomorphism $\rho : \mathcal M\to \mathcal N$
of
$\mathfrak L$
-structures is said to be elementary if it preserves the values of all sentences.
For a complete treatment of the model theory of metric structures the reader may consult [Reference Ben Yaacov, Alexander, Ward Henson and Usvyatsov4], [Reference Farah, Hart, Lupini, Robert, Tikuisis, Vignati and Winter18], or [Reference Hart25]. Besides the general notions mentioned before, we will also use the following model-theoretical results about definability.
Let
$\mathfrak L$
be a signature and
$T$
an
$\mathfrak L$
-theory. We say that a functor
$\mathcal X:\operatorname {\mathrm {Mod}}(T)\to \mathsf {Met}$
, where
$\mathsf {Met}$
is the category of metric spaces with isometric embeddings, is a
$T$
-functor if
$\mathcal X(\mathcal M)$
is a closed subspace of
$M$
and if for every elementary map
$\rho :\mathcal M\to \mathcal N$
of
$T$
-models,
$\mathcal X(\rho )=\rho \upharpoonright _{\mathcal X(\mathcal M)}$
.
Roughly, a
$T$
-functor is said to be definable if the distance to
$\mathcal X(\mathcal M)$
is computable in terms of a formula (see the first item in the theorem below). The following theorem found in [Reference Hart25] gives a full picture of the meaning of definability in the context of the model theory of metric structures.
Theorem 2.1 [Reference Hart25, Theorem 8.2]
Let’s consider a signature
$\mathcal L$
, a
$\mathcal L$
-theory
$T$
, and a
$T$
-functor
$\mathcal X$
. The following are equivalent:
-
(1) There is a $T$
-formula
$\varphi (\bar {x})$
such that for any model
$\mathcal M$
of
$T$
and any
$\bar {a}\in \mathcal M$
, $$ \begin{align*}\varphi^{\mathcal M}(\bar{a})=d(\bar{a},\mathcal X(\mathcal M)).\end{align*} $$
-
(2) For any $T$
-formula
$\psi (\bar {x},\bar {y})$
, there is a
$T$
-formula
$\sigma (\bar {y})$
such that for any model
$\mathcal M$
of
$T$
and any
$\bar {a}\in \mathcal M$
, $$ \begin{align*}\sigma^{\mathcal M}(\bar{a})=\inf_{\bar{x}\in\mathcal X(\mathcal M)}\psi^{\mathcal M}(\bar{x},\bar{a})\end{align*} $$
(or equivalently the analogous statement replacing $\inf $
by
$\sup $
). -
(3) For every $\varepsilon>0$
, there is a
$T$
-formula
$\varphi (\bar {x})$
and
$\delta>0$
such that, for all models
$\mathcal M$
of
$T$
:-
• $\mathcal X(\mathcal M)\subset \{\bar {a}\in \mathcal M:\varphi ^{\mathcal M}(\bar {a})=0\}$
; -
• for all $\bar {a}\in \mathcal M$
, if
$\varphi ^{\mathcal M}(\bar {a})<\delta $
, then
$d(\bar {a},\mathcal X(\mathcal M))\leq \varepsilon $
.
-
-
(4) For every $\varepsilon>0$
, there is a basic
$\mathfrak L$
-formula
$\varphi (\bar {x})$
and
$\delta>0$
such that, for all models
$\mathcal M$
of
$T$
:-
• $\mathcal X(\mathcal M)\subset \{\bar {a}\in \mathcal M:\varphi ^{\mathcal M}(\bar {a})=0\}$
; -
• for all $\bar {a}\in \mathcal M$
, if
$\varphi ^{\mathcal M}(\bar {a})<\delta $
, then
$d(\bar {a},\mathcal X(\mathcal M))\leq \varepsilon $
.
-
-
(5) For any set $I$
, family of
$\mathfrak L$
-structures
$\mathcal M_i$
for
$i\in I$
, and ultrafilter
$\mathcal U$
on
$I$
, $$ \begin{align*}\mathcal X(\mathcal N)=\prod_{\mathcal U} \mathcal X(\mathcal M_i)\text{, where } \mathcal N=\prod_{\mathcal U} \mathcal M_i.\end{align*} $$
The Beth Definability Theorem is a powerful tool in model theory since it offers a criterion to identify relations and predicates that can be expressed by formulas, and it establishes a connection between the explicit sense of definability, using formulas, to the implicit sense of definability, using models of a theory. The following formulation of the theorem appears in [Reference Hart25].
Definition 2.2. Let
$\mathfrak L$
be a continuous language,
$T$
an
$\mathfrak L$
-theory, and
$\varphi (\bar {x}),\psi (\bar {x})$
two
$T$
-formulas. We say that
$\varphi (\bar {x})$
is
$T$
-equivalent to
$\psi (\bar {x})$
if and only if for every model
$\mathcal M$
of
$T, \bar {a}\in M, \psi ^{\mathcal M}(\bar {a})=\varphi ^{\mathcal M}(\bar {a})$
, i.e., their interpretations for any model of the theory are the same function.
Theorem 2.3 (Beth Definability Theorem).
Suppose that
$\mathfrak L'\subseteq \mathfrak L$
are two continuous languages with the same sorts. Further, suppose
$T$
is an
$\mathfrak L$
-theory. If the forgetful functor
$F$
from models of
$T$
to
$\mathfrak L'$
-structures given by restriction is an equivalence of categories onto the image of
$F$
, then every
$\mathfrak L$
-formula is
$T$
-equivalent to an
$\mathfrak L'$
-formula.
As it is claimed in [Reference Hart25], this result is even more important in the context of continuous logic given the challenge of identifying definable predicates as limits of explicit formulas. We will use this to prove the definability of the meet operation under certain circumstances. Specifically, we will use the following corollary of the Beth Definability Theorem found in [Reference Farah, Hart, Lupini, Robert, Tikuisis, Vignati and Winter18, Corollary 4.2.3].
Corollary 2.4. Suppose that
$\mathcal {C}$
is an elementary class of structures in a language
$\mathfrak L$
and, for every
$A\in \mathcal {C}$
, the structure
$A$
is expanded by a predicate
$P_A$
which is uniformly continuous with uniform continuity modulus independent of our choice of A. Let
$\mathcal {C}' := \{(A,P_A): A \in \mathcal {C}\}$
be a class of structures for an expanded language
$\mathcal {L}'$
with a predicate for
$P$
. If
$\mathcal {C}'$
is an elementary class for a theory
$T'$
in the language
$\mathfrak L'$
, then
$P$
is
$T'$
-equivalent to a definable predicate in
$\mathfrak L$
.
Remark 2.5. For the purposes of this article, we will use “formula” to refer to either an
$\mathfrak L$
-formula,
$T$
-formula, or definable predicate in general. For a more detailed explanation of each one and their differences we recommend the reader to check [Reference Hart25].
3 Metric lattices
A semilattice is a set
$L$
equipped with a commutative, associative, idempotent binary operation
$+$
. We can see that this operation defines a partial order
$\leq $
on
$L$
by
$x\leq y$
if
$x+y=y$
, and a strict partial order by setting
$x<y$
if and only if
$x\leq y$
and
$x\neq y$
. This choice of partial order creates what is often referred to as an upper semilattice in the literature: when we refer to a partial order on a semilattice, we will always mean this one. Further, we will always assume that semilattices are equipped with (unique) elements
$0$
and
$1$
so that
$0+x=x$
and
$1+x=1$
for all
$x\in L$
.
Definition 3.1. A tuple
$\mathcal L =(L, <, +, \cdot , 0, 1)$
a lattice if:
-
(1) $(L,<)$
is a partially ordered set with a maximal element
$1$
and a minimal element
$0$
; -
(2) $+,\cdot $
are commutative, associative, idempotent binary operations; -
(3) $x\leq y$
if and only if
$x+y=y$
if and only if
$xy=x$
.
Following convention, we will refer to
$+$
as the join and
$\cdot $
as the meet. Note that the conditions imply that
$\sum _{i=1}^k x_i$
is the least upper bound of
$\{x_1,\dotsc ,x_k\}$
and
$\prod _{i=1}^k x_i$
is the greatest lower bound. Furthermore, if for any subset
$S\subset L$
we can find its lowest upper bound and its greatest lower bound we say that the lattice is complete and we will denote them by
$\Sigma _{x\in S} x$
and
$\prod _{x\in S}x$
, respectively.
If
$\mathcal L$
is a finite semilattice, more generally, if the partial order is complete, then the meet operation
$xy$
can be defined in terms of this order as the maximal element simultaneously below both
$x$
and
$y$
. When generalizing beyond finite lattices, this poses an interesting choice of category in terms of whether to consider lattice or semilattice morphisms.
Definition 3.2. A metric lattice is a tuple
$\mathcal L = (L, <, +, \cdot , 0, 1, d)$
so that
$(L, <, +, \cdot , 0, 1)$
is a lattice and
$d$
is a metric on
$L$
satisfying:
-
(1) $d(1,0) =1$
; -
(2) $d(x+z,y+z)\leq d(x,y)$
; -
(3) $d(x,y)\leq d(x+y,0) - d(xy,0)$
for all
$x,y,z,\in L$
. If
$(L,d)$
is a complete metric space, we say that
$\mathcal L$
is a complete metric lattice. We call a metric satisfying the last condition semi-modular.
Remark 3.3. Notice that condition (2) implies that
by the triangle inequality, so
$L\times L\ni (x,y)\mapsto x+y\in L$
is jointly uniformly continuous.
Given a metric lattice
$\mathcal L = (L, <, +, \cdot , 0, 1, d)$
, we can define a rank function
$|\cdot |: L\to \mathbb R_{\geq 0}$
by
The semi-modular condition on the metric then becomes
Proposition 3.4. If
$\mathcal L = (L, <, +, \cdot , 0, 1, d)$
is a metric lattice, then:
-
(1) $x<y$
implies that
$|x| < |y|$
. -
(2) $d(x,y)\in [0,1]$
for all
$x,y\in L$
.
Proof. If
$x < y$
, then
$xy = x < y = x+y$
, so
$0 < d(x,y) \leq |y| - |x|$
by (3.3). Since
$0\leq x\leq 1$
for all
$x\in L$
, it follows that
$0\leq |x|\leq 1$
. As a consequence,
Remark 3.5. This definition differs from the definition given in [Reference Wilcox and Smiley53]. It can be seen that a metric lattice as defined therein is also a metric lattice in our sense. Indeed, the only difference is the insistence that
$d(x,y) = 2|x+y| - |x| - |y|$
. For a metric lattice we define
Proposition 3.6. For a metric lattice
$\mathcal L$
the following are true:
-
(1) $||x|-|y||\leq d(x,y)$
. -
(2) $d(x,y) = |y| - |x|$
for
$x<y$
. -
(3) $d'(x,y) = 2|x+y| - |x| - |y|$
. -
(4) $|x+y|+|xy|\leq |x|+|y|$
. -
(5) If $z\leq x$
, then
$|z|+|y+x|\leq |z+y|+|x|$
. -
(6) $d'$
is a metric and
$\mathcal L' = (L,d')$
is a metric lattice. -
(7) $d(x,y)\leq d'(x,y)\leq 2\,d(x,y)$
.
Proof. We prove each item sequentially.
-
(1) Since $d$
is a metric, by the reverse triangle inequality, we have that $$ \begin{align*}||x|-|y||=|d(x,0)-d(y,0)|\leq d(x,y).\end{align*} $$
-
(2) If $x<y$
, by the previous point and the semi-modular condition, we conclude that $$\begin{align*}||y|-|x||=|y|-|x|\leq d(x,y)\leq |x+y|-|xy|=|y|-|x|;\end{align*}$$
thus, $d(x,y)=|y|-|x|$
. -
(3) From item $(2)$
, we have that $$ \begin{align*} \begin{aligned} d'(x,y)=d(x+y,x)+d(x+y,y) &= \left(|x+y|-|x|\right) + \left(|x+y|-|y|\right)\\ &=2|x+y|-|x|-|y|. \end{aligned} \end{align*} $$
-
(4) Again by item $(2)$
, we have that
$d(x+y,x)=|x+y|-|x|$
and
$d(y,xy)=|y|-|xy|$
. Also, from condition
$(2)$
in the definition of a metric lattice, we have that $$\begin{align*}|x+y|-|x|=d(x+y,x)=d(x+y,x+xy)\leq d(y,xy)=|y|-|xy|;\end{align*}$$
thus, we get that $|x+y|+|xy|\leq |x|+|y|$
. -
(5) By item $(4)$
, we have that for
$x,y,z\in L$
, $$\begin{align*}|(z+y)x|+|z+y+x|\leq |z+y|+|x|.\end{align*}$$
Since $z\leq z+y,x$
, we have that
$z\leq (z+y)x$
and
$z+y+x=y+x$
; thus, by Proposition 3.4.1 we get that $$\begin{align*}|z|+|y+x|\leq |(z+y)x|+|z+y+x|\leq |z+y|+|x|.\end{align*}$$
-
(6) We first prove that $d'$
is a metric. Since
$d$
is a metric, it is clear that
$d'(x,y)\geq 0$
,
$d'(x,x)=0$
, and
$d'(x,y)=d'(y,x)$
.Using our definition of a metric lattice and items $(2)$
and
$(3)$
, we can follow the strategy given in [Reference Wilcox and Smiley53, Theorem 1.1] to prove the triangle inequality. Indeed, by item
$(3)$
and Proposition 3.4.1, we get that $$ \begin{align*} d'(x,z)+d'(z,y)-d'(x,y)&=2(|x+z|+|z+y|-|x+y|-|z|)\\ &\geq 2(|x+z|+|z+y|-|x+y+z|-|z|). \end{align*} $$
Using inequality $(5)$
with
$z\leq x+z$
, we conclude that $$\begin{align*}2(|x+z|+|z+y|-|x+y+z|-|z|)\geq 0\; ;\end{align*}$$
therefore, $d'(x,y)\leq d'(x,z)+d'(y,z)$
.Now we need to check that $(L,d')$
satisfies the axioms of being a metric lattice. Note that
$d'(x,0) = |x|$
, so
$d'$
induces the same rank function as
$d$
. We have that $$ \begin{align*} \begin{aligned} &d'(x,y) - d'(x+z,y+z)\\ &\quad= (2|x+y| - |x| - |y|) - (2|x+y+z| - |x+z| - |y+z|)\\ &\quad= (|x + z| - |x|) + (|y+z| - |y|) - 2(|x+y+z| - |x+y|)\\ &\quad= d(x+z,x) + d(y+z,y) - 2\,d(x+y+z,x+y) \geq 0 \end{aligned} \end{align*} $$
by item (2) and Definition 3.2.2. It follows from item (4) that
$$\begin{align*}d'(x,y)\leq |x+y| - |xy|.\end{align*}$$
-
(7) By Definition 3.2.2 and the triangle inequality, we have that
$$ \begin{align*} d(x,y)&\leq d(x,x+y)+d(y,x+y)&\\ &=d(x+x,x+y)+d(x+y,y+y)&\\ &\leq d(x,y)+d(x,y) =2\,d(x,y). \end{align*} $$
Thus, by the definition of $d'$
, we conclude
$d(x,y)\leq d'(x,y)\leq 2\, d(x,y).\\[-18pt]$
Proposition 3.7. If
$\mathcal L$
is a metric lattice, then we have that
for all
$x,y,z\in L$
. As a consequence,
for all
$x,y,z\in L$
.
Proof. Since
$z\leq z+x$
, we can apply Proposition 3.6.5 to get
By Proposition 3.4 we know that
$|x+y|\leq |y+z+x|$
, so we conclude that
for all
$x,y,z,\in L$
. This result, along with Propositions 3.6.3 and 3.6.7, gives us
for all
$x,y,z\in L$
.
Remark 3.8. From Proposition 3.6.2 we see that the metrics
$d$
and
$d'$
agree on any chain (totally ordered subset) of
$L$
. By the proof of item (7) in the same, we have that if
$d$
and
$\tilde d$
are metrics that induce a metric lattice structure on the same lattice and for which the rank functions agree, then
$d(x,y)\leq 2\tilde d(x,y)$
. In general, the set of metrics on a lattice can be quite large. For example, take any Borel regular measure
$\mu $
of full support on
$[0,1]$
. We say that two Borel sets
$A,B$
are equivalent if
$\mu (A\Delta B)=0$
, and write
$[A]$
for the equivalence class of
$A$
. For any measure
$\nu $
in the same absolute continuity class as
$\mu $
, i.e.,
$\mu (A)=0 \Leftrightarrow \nu (A)=0$
, the equivalence classes are the same, and each one induces a metric lattice structure on the same lattice of equivalence classes of Borel sets by
$d_\nu ([A],[B]) = \nu (A \cup B) - \nu (A\cap B)$
.
Remark 3.9. Let’s define
and note this expression is symmetric in the variables
$x,y,z$
and that
$[x,y,z]_d = [x,y,z]_{d'}$
. From equation (3.6) of Proposition 3.7 we see that for all
$x,y,z\in L$
for any metric lattice. Further, by Proposition 3.6.2 we have that
Thus, we have the following corollary.
Corollary 3.10. Every metric lattice
$\mathcal L$
satisfies the following inequality:
for all
$x,y,z\in L$
.
This last inequality is a strengthening of the semi-modular condition (3) from Definition 3.2 since we can get back the semimodular condition by substituting
$z=xy$
.
Note that
$d'(x,y)\leq |x+y| + d'(x+z,x) + d'(y+z,y) - |z|$
is equivalent to
$d'$
satisfying the triangle inequality.
3.1 Modularity
In a lattice
$L$
, a pair
$(x,y)$
of elements is called a modular pair if
$xy + z = x(y+z)$
for all
$z\leq x$
. Note that this relation need not be symmetric: if it is, we will call the lattice semi-modular. As will be seen below, in Section 5.2, the detailed study of modularity from the metric lattice perspective occupies a prominent place in the theory as modularity is essentially equivalent to continuity of the meet operation.
Definition 3.11. Given a metric lattice
$\mathcal L$
, we say that
$(x,y)\in L^2$
is a metrically modular pair if
equivalently, if
$d'(x,y) = |x+y| - |xy|$
. Note that, unlike modularity of a pair, metric modularity is a symmetric relation. We say that
$x\in L$
is metrically modular if
$(x,y)$
is a metrically modular pair for all
$y\in L$
and that
$\mathcal L$
is metrically modular if every pair
$(x,y)\in L^2$
is a metrically modular pair.
Proposition 3.12. For a metric lattice, every metrically modular pair
$(x,y)$
is a modular pair.
Proof. Let’s suppose that
$(x,y)$
is a metrically modular pair. To prove that they are a modular pair we need to show that for all
$z\leq x, z+yx=(z+y)x$
. We already know that for all
$z\leq x$
we have the inequalities
$z+yx\leq (z+y), x$
, hence
$z+yx\leq (z+y)x$
. Now using Proposition 3.4.1 with
$yx\leq y$
and Proposition 3.6.4 we have that for all
$z\leq x$
We conclude that
$|(z+y)x|=|z+yx|$
; thus, as
$|\cdot |$
is strictly increasing, it follows that
$(z+y)x=z+yx$
.
Remark 3.13. We say that a metric lattice
$\mathcal L$
is strongly metrically semi-modular if
for all
$x,y,z\in L$
; equivalently, if
for all
$x,y,z\in L$
. It is clear that
$|x+y| - |xy| \geq \inf _z [x,y,z]_d$
; thus, strong semi-modularity is equivalent to
for all
$x,y\in \mathcal L$
. In fact, we have that a metric lattice
$\mathcal L$
is strongly metrically semi-modular if and only if it is metrically modular.
Indeed, assume
$\mathcal L$
is strongly metrically semi-modular. Setting
$y=z$
, we get that
$|x|+|y|\leq |x+y|+|xy|$
for all
$x,y\in L$
. By Proposition 3.6 we have the reverse inequality, so
$\mathcal L$
is metrically modular. On the other hand, if
$\mathcal L$
is metrically modular, we have
$d'(x,y) = |x+y| - |xy|$
; therefore, by Proposition 3.7 we have
$|x+y|-|xy|\leq [x,y,z]_d$
.
Definition 3.14. Let
$\mathcal L$
be a lattice. We say that a function
$\rho : L\times L\to \mathbb R_{\geq 0}$
is a quasi-metric if:
-
(1) $\rho (x,y) = \rho (y,x)$
; -
(2) $\rho (x,y)=0$
if and only if
$x=y$
; -
(3) $\rho (x,y)\leq \rho (x,z)+\rho (y,z)$
when
$z\leq x$
or
$z\leq y$
.
Proposition 3.15. Let
$\mathcal L$
be a metric lattice, and let
The following are true:
-
(1) $\delta (x,y)$
is a quasi-metric. -
(2) $\delta (x,0) = |x|$
for all
$x\in L$
. -
(3) $d'(x,y)\leq \delta (x,y)$
. -
(4) $\delta $
is a metric if and only if
$\mathcal L$
is metrically modular.
Proof. We begin with the proofs of the numbered assertions.
-
(1) First note that since $xy\leq x,y$
, we have that
$|xy|\leq |x|,|y|$
, so
$\delta (x,y)\geq 0$
. It is clear that
$\delta (x,y)=\delta (y,x)$
and that if
$x=y$
, then
$\delta (x,y)=0$
. Now, if
$x\neq y$
, we have that
$x\neq xy$
or
$y\neq xy$
; therefore,
$|x|>|xy|$
or
$|y|>|xy|$
and we get that
$\delta (x,y)>0$
. Thus, we conclude that
$\delta (x,y)=0$
if and if
$x=y$
. Now to conclude that
$\delta $
is a quasi-metric we need to check the last condition.If $z\in L$
is such that
$z\leq x$
or
$z\leq y$
, then
$|xz|\leq |xy|$
or
$|yz|\leq |xy|$
and given that
$|xz|,|yz|\leq |z|$
we conclude that
$|xz|+|yz|\leq |z|+|xy|$
. Using this inequality we get $$\begin{align*}|x|+|y|+2|xz|+2|yz|\leq |x|+|z|+|y|+|z|+2|xy|,\end{align*}$$
hence,
$$ \begin{align*} \begin{aligned} \delta(x,y)&=|x|+|y|-2|xy|\\ &\leq |x|+|z|-2|xz|+|y|+|z|-2|yz|=\delta(x,z)+\delta(y,z). \end{aligned} \end{align*} $$
Thus, $\delta $
is a quasi-metric. -
(2) It is clear that $\delta (x,0)=|x|+|0|-2|0|=|x|-0=|x|$
for all
$x\in L$
. -
(3) By Proposition 3.6.4 we know that for all $x,y\in L$
$$ \begin{align*}|x+y|+|xy|\leq |x|+|y|.\end{align*} $$
We can reorder the terms to get
$$\begin{align*}2|x+y|-|x|-|y|\leq|x|+|y|-2|xy|;\end{align*}$$
thus, $d'(x,y)\leq \delta (x,y)$
. -
(4) For the last assertion, if $\delta $
satisfies the triangle inequality, then for all
$x,y,z\in L$
we have that $$\begin{align*}|x|+|y|-2|xy|\leq |x|+|z|-2|xz|+|z|+|y|-2|yx|,\end{align*}$$
which shows that
$$\begin{align*}|xz|+|yz|\leq|z|+|xy|.\end{align*}$$
Taking $z=x+y$
we have that
$|x|+|y|\leq |x+y|+|xy|$
. We already know that
$|x+y|+|xy|\leq |x|+|y|$
, so we conclude that all pairs
$x,y\in L$
are metrically modular pairs.In the other direction, if $\mathcal L$
is metrically modular, then
$\delta (x,y) = d'(x,y)$
, so is a metric by Proposition 3.6.6.
3.2 Complete metric lattices
Metric completeness is another crucial aspect of our study, as it allows to deduce algebraic structure from analytic arguments. The next result is the key observation which underpins the usage of metric completeness throughout.
Lemma 3.16. If
$\mathcal L$
is a complete metric lattice, then any monotone net converges.
Proof. Let
$\mathcal A$
be a directed set and suppose
$(x_a)_{a\in \mathcal A}$
is an increasing net. Then
$(|x_a|)_{a\in \mathcal A}$
is increasing and bounded by
$1$
, hence
$\alpha := \lim _{\mathcal A} |x_a|$
exists. Given
$\epsilon>0$
, if
$\alpha -\epsilon < |x_a| \leq |x_{b}|\leq \alpha $
for
$a\leq b$
, then
$d(x_a,x_{b}) = |x_b| - |x_a|< \epsilon $
by Proposition 3.6.2. Thus,
$(x_a)_{a\in \mathcal A}$
is a Cauchy net and
$x^* = \lim _{\mathcal A} x_a$
exists by metric completeness. Similarly, if
$(x_a)_{a\in A}$
is a decreasing net,
$\lim _{\mathcal A} x_a$
exists.
Proposition 3.17. If
$\mathcal L$
is a complete metric lattice and
$S\subseteq L$
is closed under
$+$
(resp. closed under
$\cdot $
), then the least upper bound (resp. greatest lower bound) of
$S$
exists and belongs to the closure of
$S$
.
Proof. Let
$\mathcal F$
be the collection of all finite subsets of
$S$
. Consider the net
$(x_F)_{F\in \mathcal F}$
where
$x_F := \sum _{x\in F} x$
. We have that
$x$
is an upper bound for
$S$
if and only if
$x_F\leq x$
for all
$F\in \mathcal F$
. As
$(x_F)$
is increasing,
$x^* = \lim _{\mathcal F} x_F$
exists by Lemma 3.16. Clearly
$x_F + x_G = x_G$
if
$F\subset G$
, so passing to limits we have that
$x_F + x^* = x^*$
which shows that
$x^*$
is an upper bound for
$S$
. If
$S$
is closed under
$+$
, then
$x_F\in S$
, so
$x^*$
belongs to the closure of
$S$
.
It now suffices to check that
$x^*$
is the least upper bound. If
$y$
is another upper bound for
$S$
, then so is
$x^*y$
, so without loss of generality we may only consider the case when
$x_F\leq y < x^*$
for all
$F\in \mathcal F$
. However, we would then have that by Proposition 3.6.2 that
$d(x_F,x^*) = |x^*| - |x_F| \geq |x^*| - |y|>0$
, which is a contradiction.
The proof when
$S$
is closed under
$\cdot $
with the greatest lower bound follows nearly identically.
The following consequence is readily apparent.
Corollary 3.18. A complete metric lattice is complete as a lattice.
Remark 3.19. An important consequence of the previous results is the existence of
$\liminf $
and
$\limsup $
for any sequence in a complete metric lattice, i.e., given a sequence
$(x_n)$
there exist
$\limsup x_n:=\lim _{n\to \infty }\sum _{k=n}^\infty x_k$
and
$ \liminf x_n:=\lim _{n\to \infty } \prod _{k=n}^\infty x_k $
. For more details of their construction see Propositions 3.21 and 5.14, respectively.
Lemma 3.20. Let
$\mathcal L$
be a complete metric lattice. If
$(x_i)$
is a sequence in
$L$
, by Proposition 3.17 we can set
$z = \sum _ix_i$
and we have that
Proof. Setting
$z_n = \sum _{i=1}^n x_i$
, we have that
$( z_n)$
is an increasing sequence, so
$(z_n)$
is Cauchy and
$z_n\to z$
by Lemma 3.16. We have inductively that
hence, the result obtains in the limit by continuity.
Proposition 3.21. Let
$\mathcal L$
be a complete metric lattice. A pair
$x,y\in L$
is metrically modular if and only if for every
$n\in \mathbb N$
there is
$z\in L$
so that
Proof. The “only if” direction follows by choosing
$z = xy$
and using Proposition 3.6.4. For the converse, fix
$x,y\in L$
. Choose
$z_i\in L$
for
$n = 2^i$
as above, we will proceed to construct
$t$
the
$\limsup z_i$
. Set
$t_k = \sum _{i=k}^\infty z_i$
with
$t_k^N = \sum _{i=k}^N z_i$
, noting that
$t_k^N\to t_k$
as
$N\to \infty $
by Lemma 3.16. For
$k<l$
and
$M> N$
we have that
$d(t_k^M + t_l^N, t_k^M)=0$
, so
when
$k< l$
. Taking the limit in
$N$
, we see that
$d(t_k + t_l, t_k)=0$
, or
$t_l\leq t_k$
when
$k< l$
. Since
$(t_k)$
is therefore decreasing, it is Cauchy. Set
$t = \lim _k t_k$
. By Lemma 3.20, we have that
$d(t_k+x,x), d(t_k+y,y)\leq \sum _{i=k}^\infty 2^{-i}\to 0$
as
$k\to \infty $
; thus,
$d(t+x,x)= d(t+y,y)=0$
or
$t\leq xy$
.
Since
$t_k\geq z_k$
, we have that
for all
$k\in \mathbb N$
which implies that
The result is now apparent by Proposition 3.6.4.
3.3 Metrically complete semilattices
In the presence of metric completeness we can describe a metric lattice using only uniformly continuous operations, a point which will be crucial for the purpose of axiomatization as metric structures.
Definition 3.22. We define a pseudo-metric semilattice to be a structure
$\mathcal P = (P,+,0,1,d)$
where the following hold:
-
(1) $(P,d)$
is a pseudo-metric space; -
(2) $0,1\in P$
are distinguished elements; -
(3) $+: P\times P\to P$
is a commutative, associative, idempotent (
$x+x = x$
) operation; -
(4) $0+x = x$
and
$1+x =1$
for all
$x\in P$
.
Further, we require the following axioms:
-
(1) $d(1,0) =1$
; -
(2) $d(x+z,y+z)\leq d(x,y)$
; -
(3) $d(x,y)\leq d(x+y,0) + d(x+z,x) + d(y+z,y) - d(z,0)$
for all
$x,y,z\in P$
.
We say that
$\mathcal P$
is a metric semilattice if
$(P,d)$
is a metric space and that
$\mathcal P$
is complete if
$(P,d)$
is a complete metric space.
Remark 3.23. The property “
$d(x,y)\leq d(x+y,0) + d(x+z,x) + d(y+z,y) - d(z,0)$
for all
$x,y,z\in P$
” implies “
$d(x,y)\leq d(x+y,0) - d(z,0)$
for all
$x,y,z\in P$
with
$z\leq x,y$
.” Inspection of the proofs of Propositions 3.4 and 3.6 will convince the reader that these properties are equivalent.
Proposition 3.24. Let
$\mathcal P$
be a semilattice and let
$f: P\to [0,1]$
be a strictly increasing function with
$f(0)=0$
and
$f(1)=1$
. We have that
$d_f(x,y) := 2\,f(x+y) - f(x) - f(y)$
defines a semilattice metric on
$L$
if and only if
$f$
satisfies the “exchange relation”
whenever
$z\leq x$
.
Proof. If
$d_f$
is a semilattice metric, then
$f$
satisfies the exchange relation by adapting the proof of Proposition 3.6.5. Conversely,
$d_f$
satisfies the triangle inequality if and only if
$f(x+y) + f(z) \leq f(x+z) + f(y+z)$
. Applying the exchange relation to
$x+z$
,
$y$
, and
$z$
, we obtain
for all
$x,y,z\in L$
. We have that
$d_f(x+z,y+z)\leq d_f(x,y)$
if and only if
This may be obtained from two applications of the previous inequality, permuting the variables
$x,y$
, and
$z$
appropriately.
Remark 3.25. For a semilattice
$\mathcal P$
and a map
$f:P\to \mathbb R$
, the key inequality used in the proof of Proposition 3.24 is that for all
$x,y,z\in P$
This property is referred to as strong subadditivity in the literature [Reference Choquet14, Reference Niculescu44]. We direct the reader to Proposition 4.17 below for a related result. For a lattice, the exchange relation and strong subadditivity are equivalent to
$f$
being submodular, that is,
$f(x+y) + f(xy)\leq f(x) + f(y)$
.
Lemma 3.26. Let
$\mathcal P$
be a pseudo-metric semilattice. Let
$(P',d')$
be the metric quotient of
$(P,d)$
and define
$\mathcal P'= (P', +', [0], [1], d')$
where
$[x]+'[y] := [x+y]$
. Then
$\mathcal P'$
is a metric semilattice.
Proof. It suffices to check that
$+': P'\times P'\to P'$
is well defined. Letting
$[x_1] = [x_2]$
and
$[y_1] = [y_2]$
, we have that
Therefore,
$[x_1+y_1] = [x_2+y_2]$
and the join operation is well defined.
Lemma 3.27. If
$\mathcal P$
is a pseudo-metric semilattice, then declaring
$x\leq y$
if
$y =x+y$
defines a partial order on
$P$
where
$0$
and
$1$
are the minimal and maximal elements, respectively, and where
$x+y$
is the least upper bound of
$\{x,y\}$
. Additionally,
$d(x,y)\leq |y|- |x|$
when
$x\leq y$
. (We define
$|x| = d(x,0)$
as above in the lattice case.)
Proof. First let’s prove that
$\leq $
is a partial order. It is clear that for all
$x\in \mathcal P,x\leq x$
since
$+$
is idempotent,
$\leq $
is reflexive. If for a pair
$x,y\in \mathcal P, x\leq y$
, and
$y\leq x$
, then
$y=x+y=y+x=x$
, so
$\leq $
is antisymmetric. Lastly, for all
$x,y,z\in \mathcal P$
if
$x\leq y$
and
$y\leq z$
, then
$z=y+z$
and
$y=x+y$
; therefore,
$z=y+z=(x+y)+z=x+(y+z)=x+z$
, so
$x\leq z$
and we conclude that
$\leq $
is transitive. In conclusion, it is a partial order.
By Definition 3.22(4) it is clear that for all
$x\in \mathcal P,0\leq x\leq 1$
; thus,
$0$
and
$1$
are the minimal and maximal elements, respectively. By idempotency, commutativity, and associativity of
$+$
, we get
$x+y=x+(x+y)=y+(x+y)$
, and thus
$x,y\leq x+y$
. If
$x,y\leq z$
, then
$(x+y)+ z = x + (y+z) = x+ z = z$
, so
$x+y\leq z$
. Finally, if
$x\leq y$
, we can use the axiom (3) about
$d$
in Definition 1.21 to obtain
The next proposition follows in exactly the same way as Proposition 3.17.
Proposition 3.28. If
$\mathcal P$
is a complete metric semilattice, then every set
$S\subset P$
has a least upper bound. If
$S$
is closed under
$+$
, then the least upper bound belongs to the closure of
$S$
.
By Corollary 3.10 we have that every metric lattice is an example of a metric semilattice. We now prove a partial converse.
Proposition 3.29. Every complete metric semilattice
$\mathcal P$
is a complete metric lattice with
$0$
and
$1$
being the minimal and maximal element, respectively, and
$+$
being the lattice join operation.
Proof. Let us consider
Then
$\phi _{x,y}(z)=0$
if and only if
$z$
is a lower bound for
$\{x,y\}$
. The sum of two common lower bounds for
$x$
and
$y$
is again a common lower bound, as
$z+x = z'+x =x$
implies that
$z+z'+x = x$
. Moreover, the set of all lower bounds is closed by continuity of
$\phi _{x,y}$
, so the set of common lower bounds for
$x$
and
$y$
must have a largest element by Proposition 3.28. We define
$xy$
as this element. The function
$(x,y)\mapsto xy$
is clearly commutative and idempotent. We have that
$t\leq (xy)z$
if and only if
$t\leq xy,z$
if and only if
$t\leq x,y,z$
which shows that it is also associative. The remaining parts of Definition 3.1 are easy to check.
The following result was proved in [Reference Wilcox and Smiley53, Section 3]. We present a more direct approach here.
Corollary 3.30. Let
$\mathcal L$
be a metric lattice. We have that the metric completion
$\overline {\mathcal L}$
is a metric lattice and the canonical inclusion
$L\hookrightarrow \overline {L}$
is an isometric embedding of metric semilattices.
Proof. If
$\mathcal L$
is a metric lattice, then it is also a metric semilattice. The metric completion of a semilattice is again a metric semilattice as the
$+$
operation is uniformly continuous.
Proposition 3.31. Let
$\mathcal L$
and
$\mathcal L'$
be complete metric lattices and
$\phi : \mathcal L\to \mathcal L'$
a continuous semilattice homomorphism, that is,
$\phi (0)=0$
,
$\phi (1)=1$
, and
$\phi (x+y) = \phi (x)+\phi (y)$
for all
$x,y\in L$
. We have that the subsemilattice
$\phi (L)\subset L'$
is a complete metric lattice.
Proof. By Proposition 3.28 we need only show that
$\phi (L)$
is closed. First suppose that
$(\phi (x_n))$
is an increasing sequence, so that
$\phi (x_n)\to z$
for some
$z\in L'$
by Lemma 3.16. Setting
$y_n = \sum _{k=1}^n x_n$
and
$y = \sum _{k=1}^\infty x_k$
, we have that
$y_n\to y$
and so
$\phi (x_n)=\phi (y_n)\to \phi (y)$
by continuity. Therefore,
$z = \phi (y)$
.
Now let
$\phi (x_n)\to z$
be arbitrary. By passing to a subsequence, we may assume that
$d(\phi (x_n),z)< \frac {1}{2^n}$
. For
$n< L$
, we set
$y_{n,L} = \phi (\sum _{k=n}^L x_k) = \sum _{k=n}^L \phi (x_k)$
and
$y_n = \phi (\sum _{k=n}^\infty x_k)$
so that by the previous paragraph
$y_{n,L}\to y_n$
as
$L\to \infty $
and by Lemma 3.20 we have that
$d(y_n+z,z)\to 0$
as
$n\to \infty $
.
Setting
$w_n = \sum _{k=n}^\infty x_k\in L$
, we have that
$(w_n)$
is a decreasing sequence, so has a limit
$w\in L$
. We have
$y_n = \phi (w_n)\to \phi (w) =: y\in \phi (L)$
by continuity. Therefore, by the previous paragraph we have that
$d(y+z,z)=0$
or
$y\leq z$
. On the other hand,
$y_n \geq \phi (x_k)$
for all
$k>n$
, so
$y_n = y_n + \phi (x_k)\to y_n+z$
as
$k\to \infty $
. Thus,
$y = y+z$
, which implies that
$y\geq z$
. Altogether this shows that
$z\in \phi (L)$
, which establishes the result.
4 Examples
In this section we detail various constructions of lattice metrics. For the case of finite Boolean lattices, there is some overlap with results obtained by Lovász in [Reference Lovász34, Section 9] which the authors were unaware of during the completion of the manuscript. However, the perspective presented here is more general and in some ways complementary to those results.
Example 4.1. For a finite set
$E$
, let
$\mathcal B(E)$
be the lattice of subsets of
$E$
under the normalized Hamming metric
$d(A,B) := \frac {|A\Delta B|}{|E|}$
for
$A,B\in 2^E$
.
Example 4.2. Let
$E$
be a finite set. Given
$x,y$
partitions of
$E$
we can define a partial order by
$x\leq y$
if and only if
$x$
refines
$y$
, that is, if for all
$B\in x$
, exists a
$B'\in y$
such that
$B\subseteq B'$
. Let
$\mathcal P(E)$
be the lattice of partitions of
$E$
with the metric
where for a partition
$\# x$
denotes the number of blocks. When
$E = [[n]] := \{1,\dotsc ,n\}$
, we denote
$P(E)$
by
$P_n$
.
Example 4.3. Let
$E$
be a finite set. We say that
$r: 2^E\to \mathbb N_0$
is a rank function if the following hold for all
$A,B\in 2^E$
:
-
(1) $r(A)\leq |A|$
; -
(2) $A\subset B$
implies that
$r(A)\leq r(B)$
; -
(3) $r(A\cup B) + r(A\cap B)\leq r(A) + r(B)$
.
There is a one-to-one correspondence between rank functions on a set
$E$
and matroids on the same set (see [Reference Oxley45, Section 1.3].
For a rank function define the pseudo-metric
$D_r(A,B) := 2\,r(A\cup B) - r(A) - r(B)$
.
Lemma 4.4. If
$r$
is a rank function on
$E$
, then
$D_r(A,B)\leq |A \Delta B|$
.
Proof. It follows from submodularity that
$D_r(A,B)\leq r(A\cup B) - r(A\cap B)$
. Using submodularity and disjointness, we have that
so altogether
$D_r(A,B) \leq r(A\setminus B) + r(B\setminus A)\leq |A\setminus B| + |B\setminus A| = |A\Delta B|$
.
Definition 4.5. We say that a rank function
$r: 2^E\to \mathbb N_0$
is
$k$
-sparse if
Example 4.6. If
$G = (V,E)$
is a
$k$
-regular graph and
$r: 2^E\to \mathbb N_0$
is given by
$r(A)$
is the maximal cardinality of the edges of a forest in
$(V, A)$
, then
$r$
is
$k$
-sparse.
For a rank function
$r$
on
$E$
, let’s define the normalized rank distance by
$d_r(A,B) = D_r(A,B)/r(E)$
. Let
$\mathcal L_r(E) = (L_r(E), <,+,\cdot , d_r)$
be the quotient metric lattice associated with the pseudo-metric lattice
$(2^E, d_r)$
. Since
$2^E$
is a finite lattice, the fact that
$\mathcal L_r(E)$
is a metric lattice follows from Lemma 3.26 and Proposition 3.29. The lattice
$\mathcal L_r(E)$
is referred to as the lattice of flats of the associated matroid. The following proposition is evident.
Proposition 4.7. For a rank function
$r$
on
$E$
which is
$k$
-sparse, we have that the quotient map
$q: 2^E\to L_r(E)$
from
$\mathcal B(E)$
with the normalized Hamming metric to
$\mathcal L_r(E)$
induces a surjective,
$k$
-Lipschitz metric semilattice homomorphism
$\mathcal B(E)\to \mathcal L_r(E)$
.
Definition 4.8. Let
$\mathcal P$
be a semilattice. We say that a function
$\rho : P\to \mathbb R$
is positive definite (resp. positive semidefinite) if for all
$x_1,\dotsc , x_n\in P$
, the matrix
is positive definite (resp. positive semidefinite).
Example 4.9. For
$x\in P$
, define
$\rho _x: P\to \{0,1\}$
by
$\rho _x(y) = 1$
if
$y\leq x$
and
$\rho _x(y)=0$
otherwise. Then
$\rho _x$
is positive semidefinite.
The next lemma begins to show how positive (semi)definiteness imposes strong restrictions on the function
$\rho $
.
Lemma 4.10. If
$\rho : P\to \mathbb R$
is positive semidefinite, then
$\rho $
is positive and non-increasing, with
$\rho $
being strictly decreasing if
$\rho $
is positive definite.
Proof. We have
$\rho (x) = \rho (x+x)\geq 0$
by positive definiteness. If
$y> x$
, then the matrix
is positive semidefinite, which implies that
$\rho (x)\geq \rho (y)$
with strict inequality in the positive definite case.
Let
$\mathcal P = (P,+,0,1)$
be a complete semilattice (thus, every subset of
$P$
has a least upper bound). We define the order topology on
$P$
to be the topology generated by the collection of closed sets
for each
$x\in L$
. Let
$\mathcal C$
be the
$\sigma $
-algebra generated by the sets
$\{C_x: x\in P\}$
.
Example 4.11. If
$\mu $
is a measure on
$(P, \mathcal C)$
, then
$\rho (x) := \mu (C_x)$
is positive semidefinite since, using that
$x+y$
is the least upper bound of
$\{x,y\}$
,
Indeed, choosing
$x_1,\dotsc ,x_n$
in
$P$
and
$g_1,\dotsc , g_n\in \mathbb R$
. Setting
$g = \sum _{i=1}^n g_i 1_{C_{x_i}}$
, we have that
If
$\mathcal P$
is a finite semilattice, then for every function
$f: P\to \mathbb R$
, there is a unique function
$f^\mu : P\to \mathbb R$
so that
The function
$f^\mu $
is known as the Möbius inversion of
$f$
. We refer the reader to [Reference Aigner1, Section IV.2] or [Reference Rota48] for a detailed treatment of this topic. Setting
$n = |P|$
, we fix an enumeration
$x_1,x_2,\dotsc ,x_{n}$
of
$P$
so that
$x_i\leq x_j$
only if
$i\leq j$
. We define the
$n\times n$
zeta matrix of
$\mathcal P$
by
where
$\delta _{ab}$
is the Kronecker delta. That is,
$\zeta _{ij} = 1$
if
$x_i\leq x_j$
and
$0$
otherwise. Since
$\zeta $
is upper triangular with ones on the main diagonal, it is invertible. For a sequence
$a =(a_1,\dotsc ,a_{n})$
, let
$D_a$
be the diagonal matrix with entries
$[D_a]_{ii} = a_i$
. The following identity is due independently to Lindström [Reference Lindström32] and Wilf [Reference Wilf54]:
The following result which provides a converse to Example 4.11 was first observed by Mattila and Haukkanen in the positive definite case [Reference Mattila and Haukkanen37]. We give a simple proof that extends to the positive semidefinite case as well.
Proposition 4.12. Let
$\mathcal P$
be a finite semilattice. We have that
$\rho : P\to \mathbb R$
is positive semidefinite (resp. positive definite) if and only if there is a measure
$m_\rho $
on
$P$
(resp. a measure of full support on P) so that
Proof. Example 4.11 verifies the ‘if’ direction. For the converse, it is a standard fact that if
$A\in M_n(\mathbb R)$
is positive semidefinite, then
$BAB^t$
is as well for any
$B\in M_n(\mathbb R)$
, with the same holding for positive definiteness in the case that
$B$
is invertible. Thus,
$\zeta ^{-1}[\rho (x_i+x_y)](\zeta ^{-1})^t = D_{\rho ^\mu }$
is a positive (semi)definite diagonal matrix by equation (4.1). This is equivalent to
$\rho ^\mu \geq 0$
in the positive semidefinite case and
$\rho ^\mu>0$
in the positive definite case. For
$A\subseteq P$
, we then define
$m_\rho (A):= \sum _{x\in A} \rho ^\mu (x)$
. The result now follows by Möbius inversion.
Remark 4.13. More generally, integral representation theorems for positive definite functions on semilattices give analogous measure representations under suitable topological regularity assumptions (see, e.g., [Reference Berg, Christensen and Ressel7]).
Example 4.14. Let
$K\in M_n(\mathbb C)$
be a Hermitian matrix with spectrum in
$[0,1]$
. And let
$L = 2^{[[n]]}$
be the lattice of subsets of
$[[n]] = \{1,\dotsc ,n\}$
. By a result of Lyons [Reference Lyons36] there is a measure
$\mu _K$
on
$L$
so that
for all
$S\subseteq [[n]]$
where
$K_S$
is the principal submatrix of
$K$
given by deleting all entries in rows or columns not indexed by
$S$
. Note that
$1 = \mu (L) =\mu (C_{\emptyset }) = \det (K_{\emptyset })$
by convention.
The existence of such a measure can be reduced to case where
$P$
is an orthogonal projection. Indeed, any Hermitian, contractive
$n\times n$
matrix can be realized as a principal submatrix of a
$2n\times 2n$
orthogonal projection and positive semidefiniteness of kernels is closed under restriction.
Suppose
$P$
is of rank
$r$
, and define
By viewing
$P = VV^*$
for a isometry
$V: \mathbb C^r\to \mathbb C^n$
we have by the Cauchy–Binet formula that
hence
$\rho (S) = m(C_S)$
for
Definition 4.15. We say that a function
$\eta : P\to \mathbb R$
is conditionally negative definite if
when
$\sum _i c_i = 0$
for all
$x_1,\dotsc ,x_n\in P$
.
Remark 4.16. By Schoenberg’s theorem [Reference Roe47, Proposition 11.2],
$\eta $
is conditionally negative definite if and only if
$x\mapsto \exp (-t\eta (x))$
is positive semidefinite for all
$t\geq 0$
. Therefore, we have that every conditionally negative definite function is increasing.
For
$\eta $
conditionally negative definite, define
which is again conditionally negative definite with
$d_\eta (x,x)=0$
and
$d_\eta (x,y)\geq 0$
for all
$x,y\in P$
. We note that
is again conditionally negative definite and that
Proposition 4.17. For
$\eta $
conditionally negative definite we have that
$(\mathcal P,d_\eta )$
is a pseudo-metric semilattice. Moreover, if
$\exp (-\eta )$
is positive definite, then
$d_\eta $
is a semilattice metric on
$\mathcal P$
.
Proof. We write
$|x|$
for
$|x|_\eta $
and
$d(x,y)$
for
$d_\eta (x,y)$
for brevity. If
$\exp (-\eta )$
is positive definite, then
$|x|$
is strictly increasing, from which it easily follows that
$d(x,y)>0$
if
$x\not = y$
.
By Proposition 3.24 and Remark 3.25, we need only check that strong subadditivity holds, that is,
Consider the matrix
which is
$|a_i+a_j|$
where
$a_1=x+z$
,
$a_2 =y+z$
,
$a_3= z$
, and
$a_4 = x+y+z$
. Since
$|x|$
is conditionally negative definite, we have
$\xi K \xi ^t\leq 0$
where
$\xi = [1,1,-1,-1]$
. We calculate
which proves the assertion.
Example 4.18. If
$\rho :P\to \mathbb R$
is positive semidefinite, then
$x\mapsto a - \rho (x)$
for
$a\in \mathbb R$
is clearly conditionally negative definite. Thus, if
$(\Omega , \mathcal B, \mu )$
is a probability space, then
$X\mapsto \mu (X^c)$
is positive semidefinite, and
$X\mapsto \mu (X) = 1 - \mu (X^c)$
is conditionally negative definite.
Accordingly, let
$(\Omega ,\mathcal B)$
be a Borel space, and let
$\Phi $
be a finite measure on
$(\Omega \times \Omega , \mathcal B\otimes \mathcal B)$
. The map
$\rho _\Phi : \mathcal B\ni X\mapsto \Phi (X^c\times X^c)$
is positive semidefinite, since
Therefore,
is conditionally negative definite and
$\exp (-t\eta _\Phi )$
is positive semidefinite for
$t\geq 0$
. Moreover, we can see that
$d_\Phi (X,Y) = \eta _\Phi (X\cup Y) - \eta _\Phi (X) - \eta _\Phi (Y)$
gives the lattice of Borel sets the structure of a pseudo-metric pre-lattice.
Question 4.19. In [Reference Lovász34, Section 9] it is shown that for finite Boolean lattices conditional negative definiteness coincides with a sequence of inequalities which strengthen submodularity first considered by Choquet [Reference Choquet14]. These inequalities already imply, in the metric case, that elements of the lattice are uniquely complemented (see Remark 5.16 below). It would be interesting to determine if there is a similar characterization of conditionally negative definite functions on semilattices in general.
Let
$\mathcal P$
be a finite semilattice and let
$x_1,\dotsc ,x_n$
be an enumeration of the elements of
$P$
such that
$x_i \leq x_j$
only if
$i\leq j$
. Given a function
$f: P\to \mathbb R$
, we say that a subset
$S\subseteq [[n]]$
is a chain if
$\{x_i: i\in S\}$
is totally ordered. We say that an
$n\times n$
matrix
$A$
is totally
$\mathcal P$
-non-negative if for all chains
$S,T$
with
$|S| = |T|$
we have that
$\det (A_{S,T}) \geq 0$
, where
$A_{S,T}$
is the submatrix of
$A$
consisting of the rows
$S$
and columns
$T$
. If
$\mathcal P = [[n]]$
with
$i+j = \max \{i,j\}$
, then total
$\mathcal P$
-positivity corresponds with the usual notion of
$k$
-total non-negativity of matrices [Reference Ando2].
We say that
$f: P\to \mathbb R_{\geq 0}$
is totally
$\mathcal P$
-non-negative if the associated matrix
is totally
$\mathcal P$
-non-negative. We note that even though such a matrix is symmetric, it is not clear that a variant of Sylvester’s criterion would apply to show that a totally
$\mathcal P$
-non-negative matrix is positive semidefinite. However, considering the
$3\times 3$
principal submatrix corresponding to a triple
$z\leq x,y$
,
We see that total
$\mathcal P$
-non-negativity implies that
$f$
is non-increasing and consequently
$f$
satisfies the celebrated “FKG inequality” [Reference Fortuin, Kasteleyn and Ginibre20]
whenever
$z\leq x,y$
. Note that the determinant of the
$2\times 2$
-upper right block is necessarily non-positive if
$f$
is non-increasing, but is not considered unless
$x < y$
, in which case it is
$0$
. Evidently, if
$f$
is the characteristic function of
$P\setminus C_x$
for any
$x\in P$
, then
$f$
is totally non-negative as the non-zero entries are constant and form a rectangle in the upper left corner of the associated matrix.
It would be interesting to completely characterize such matrices. For
$\mathcal P = [[n]]$
with
$i+j = \max \{i,j\}$
this is true for all
$f: [[n]]\to \mathbb R_{\geq 0}$
which are non-increasing [Reference Ando2, Example 7.I(f)]. However, the example of
$2^n\ni S\mapsto \det (K_S)$
above shows that this is false in general as
$\det (K_{S\cup T})\det (K_{S\cap T})\leq \det (K_S)\det (K_T)$
for all matrices
$K$
that are positive semidefinite by Kotelyanskii’s inequality [Reference Horn and Johnson27, Theorem 7.8.9].
5 Model theoretic aspects
We now turn to studying the model theory of metric lattices. We define a language
$\mathfrak L$
as follows.
5.1 Language and axioms for metric lattices
-
(1) There is a single sort $(X,d)$
consisting of a complete metric space of diameter
$1$
. -
(2) There are constant symbols $0$
and
$1$
. -
(3) A function symbol $+:X\times X\to X$
which is a contraction where
$X\times X$
is equipped with the
$\ell ^1$
-metric,
$d_1((x,y),(w,z)) = d(x,w) + d(y,z)$
.
For axioms we require the following collection of sentences
$T_{ML}$
:
-
(1) $d(0,1)-1$
; -
(2) $\sup _x d(x+0,x) + d(x+1,1)$
; -
(3) $\sup _x d(x+x,x)$
; -
(4) $\sup _{x,y} d(x+y,y+x)$
; -
(5) $\sup _{x,y,z} d((x+y)+z,x+(y+z))$
; -
(6) $\sup _{x,y,z} (d(x+z,y+z) \stackrel{.}{-} d(x,y))$
; -
(7) $\sup _{x,y,z} \left ([d(x,y) + d(z,0)] \stackrel{.}{-} [d(x+y,0) + d(x+z,x) + d(y+z,y)]\right )$
.
Clearly, every model of
$T_{ML}$
is complete metric semilattice. The following proposition summarizes the main results of Section 3.3.
Proposition 5.1. We have that
$\mathfrak L$
-structures
$\mathcal M$
and
$\mathcal N$
are models of
$T_{ML}$
if and only if
$\mathcal M$
and
$\mathcal N$
are complete metric lattices. Furthermore, the
$\mathfrak L$
-structure homomorphisms
$\phi :\mathcal M\to \mathcal N$
are exactly the contractive maps so that
$\phi (0)=0$
,
$\phi (1)=1$
, and
$\phi (x+y) = \phi (x)+\phi (y)$
for all
$x,y\in \mathcal M$
and
$\phi (\mathcal M)\subseteq \mathcal N$
is a model of
$T_{ML}$
.
5.2 Axioms for metrically modular lattices
Consider the sentence
and the theory
Proposition 5.2. We have that an
$\mathfrak L$
-structure
$\mathcal M$
models
$T_{MML}$
if and only if it is a metrically modular complete metric lattice.
Proof. This follows directly from Proposition 3.21.
Our objective will be to show that the meet operation is definable in
$T_{MML}$
, which in our context means that we need to prove that the predicate
$P(x,y,z):=d(xy,z)$
is definable.
Lemma 5.3. If
$\mathcal M$
is a metric lattice and
$(x,z),(y,z)$
are metrically modular pairs, then
$d'(xz,yz)\leq d'(x,y)$
and
$d(xz,yz)\leq 2\,d(x,y)$
.
Proof. We follow the proof given in [Reference Sachs49, Lemma 21]. Applying Proposition 3.6.4 to
$x+y$
and
$z$
, we get
$|z(x+y)|\leq |z|+|x+y|-|z+x+y|$
. Since
$(z,y)$
is a metrically modular pair, i.e.,
$|zy|=|z|+|y|-|z+y|$
, it follows that
Using a similar argument, we can show that
$|z(x+y)|-|zx|\leq |x+y|-|x|$
; therefore,
Now observe that as
$zx,zy\leq z(x+y)$
, we have
$zx+zy\leq z(x+y)$
, so
$|zx+zy|\leq |z(x+y)|$
and we can conclude
$d'(zy,zx)=2|zx+zy|-|zx|-|zy|\leq d'(x,y)$
. This proves the first part of the lemma.
For the second part, we use Proposition 3.6.7:
Remark 5.4. Let
noting that for complete metric lattices
$\varphi (x,y)=0$
is equivalent to
$(x,y)$
being a metrically modular pair by Proposition 3.21. In light of the previous lemma, it is natural to ask whether
$\varphi (x,z),\varphi (y,z)<\epsilon $
implies that
$d(xz,yz)\leq 2d(x,y)+K\epsilon $
for some fixed constant
$K$
. The answer turns out to be ‘no’. Indeed, we will show that for every
$K$
there is a finite partition lattice
$P_\bullet $
, a real number
$\varepsilon>0$
, and partitions
$x,y,z\in P_\bullet $
such that
$\varphi (x,z),\varphi (y,z)<\varepsilon $
and
$d(xz,yz)>2d(x,y)+K\varepsilon $
.
Given
$K$
, take a natural number
$n> K+2$
, set
$\varepsilon =\frac {1}{3n-2}$
, and consider the finite partition lattice of the set
$\{1,2,3,\ldots ,3n\}$
, which we will note as
$P_{3n}$
. Here the norm of a partition
$x$
is
$|x|:=\frac {3n-\#x}{3n-1}$
where
$\#x$
is the number of blocks in the partition
$x$
, and the distance of two partitions is
$d(x,y):=2|x+y|-|x|-|y| = d'(x,y)$
.
Consider the following partitions:
We compute the partitions
$x+z,y+z, x+y, xz, yz$
, and
$xz+yz$
which we will need for later:
It is clear that
$|x+z|=|y+z|=|x+y|=1$
. Further,
Now, let’s check that
$\varphi (x,z),\varphi (y,z)<\varepsilon $
. Observe that
$|x|+|z|\leq |x+z|+|z|$
,
and
$|z+z|-|z|=0$
, so
$\varphi (x,z)< \frac {1}{3n-1}<\epsilon $
. Similarly
$\varphi (y,z)<\varepsilon $
. However, we have that
and
Since
$n>K+2$
, we conclude that
In general picking
$n>K+S$
we can use this counterexample to get that
$\varphi (x,z)<\varepsilon , \varphi (y,z)<\varepsilon $
and
$d(xz,yz)>Sd(x,y)+K\varepsilon $
.
Lemma 5.5. Let
$\{\mathcal M_i: i\in I\}$
be a collection of metrically modular complete metric lattices, and
$\mathcal U$
a non-principal ultrafilter on
$I$
. Let
$\mathcal M = \prod _{i\in \mathcal U} \mathcal M_i$
be the ultraproduct. For
$x,y\in \mathcal M$
with representatives
$x = (x_i)$
and
$y = (y_i)$
we have that
$xy = (x_iy_i)$
.
Proof. Clearly
$x_iy_i\leq x_i,y_i$
, hence
$(x_iy_i)\leq x,y$
and
$(x_iy_i)\leq xy$
. In the other direction, suppose that
$z\leq x,y$
with representative
$z = (z_i)$
. We therefore have that
$d_i(x_i+z_i,x_i)\to 0$
and
$d(y_i+z_i,y_i)\to 0$
as
$i\to \mathcal U$
. By metric modularity, we have that
with the corresponding equations holding for
$d_i(y_iz_i,z_i)$
. By Lemma 5.3 and the triangle inequality,
as
$i\to \mathcal U$
. Therefore,
$z= (x_iy_iz_i)\leq (x_iy_i)$
so
$xy\leq (x_iy_i)$
.
In order to show the next result we will invoke the Beth Definability Theorem which we discussed in the preliminaries.
Proposition 5.6. The predicate
$P(x,y,z) = d(xy,z)$
is definable for the elementary class
$\operatorname {\mathrm {Mod}}(T_{MML})$
of metrically modular complete metric lattices.
Proof. First, we prove that for all
$\mathcal {M}\in \operatorname {\mathrm {Mod}}(T_{MML})$
the predicate
$P^{\mathcal {M}}(x,y,x):=d(xy,z)$
satisfies the conditions of Corollary 2.4. Observe that given
$x,y,z,w\in \mathcal {M}$
we can apply the Lemma 5.3 plus the triangle inequality to get
Therefore, the meet operation is uniformly continuous. Now note that if we take
using the triangle inequality we obtain
and
therefore,
Finally, we have that
Since the predicates
$P^{\mathcal {M}}$
are thus uniformly continuous with common modulus of continuity for every
$\mathcal {M}\in \operatorname {\mathrm {Mod}}(T_{MML})$
, we can take the class
of structures for our expanded language with a predicate for
$P$
, which is interpreted in each
$\mathcal {M}\in \operatorname {\mathrm {Mod}}(T_{MML})$
as
$P^{\mathcal {M}}$
. The class
$\mathcal {C}'$
is axiomatizable by the following theory in our expanded language:
so by Corollary 2.4 we conclude that the meet function is axiomatizable in the theory of metrically modular complete metric lattices.
In fact, we can show that
$d(z,xy)$
is bounded above by an explicit formula in
$(x,y,z)$
, which directly shows that
$d(z,xy)$
is definable. We thank the reviewer for the next result and its proof.
Proposition 5.7. If
$\mathcal M$
is a metrically modular complete metric lattice, then for all
$x,y,z\in M$
we have
Proof. By the proof of Lemma 5.5 and Proposition 5.6 we note that
also
Thus,
5.3 Axioms for distributive and complemented lattices
Since the predicate
$d(xy,z)$
is
$T_{MML}$
-equivalent to a definable predicate or formula in
$\mathfrak L$
(due to the general definition of formula we are using), we know there is formula
$\phi _m$
such that for every model
$\mathcal M$
of
$T_{MML}$
and all
$x,y,z\in M, \phi _m(x,y,z)=d(xy,z)$
. Using this we can axiomatize the theory of distributive metrically modular complete metric lattices.
To do so, we define the sentence
and consider the theory
Proposition 5.8. Let
$\mathcal M$
be an
$\mathfrak L$
-structure, then
$\mathcal M$
models
$T_{DML}$
if and only if it is a distributive metrically modular complete metric lattice.
Proof. It is clear that if
$\mathcal M$
is a distributive metrically modular complete metric lattice, then it is a model of
$T_{DML}$
. Now let’s suppose that
$\mathcal M$
is a model of
$T_{DML}$
. By Proposition 5.2 we know that
$\mathcal M$
is a metrically modular complete metric lattice, so we just need to prove that
$\mathcal M$
has the distributive property.
Let us fix
$x,y,z\in \mathcal M$
. Since
$\mathcal M$
models
$T_{DML}$
, it satisfies
$\sigma _{\text {dist}}$
, so for every
$n\in \mathbb N$
there are a
$t_n$
and a
$w_n$
such that
Therefore,
$t_n\rightarrow xy$
,
$w_n\rightarrow xz$
, and
$t_n+w_n\rightarrow xy+xz$
as
$n\rightarrow \infty $
, where the first two limits are immediate and the last follows from these by uniform continuity of the join operation (Remark 3.3). Finally we observe that for every
$n\in \mathbb N$
thus,
$d(x(y+z),xy+xz)=0$
, or equivalently
$x(y+z)=xy+xz$
. This implies that
$x+yz=(x+y)(x+z)$
; thus,
$\mathcal M$
is a distributive metrically modular complete metric lattice.
Definition 5.9. For
$\mathcal L$
a lattice, we say that
$x\in \mathcal L$
is complemented if there exist a
$y\in \mathcal L$
such that
$x+y=1$
and
$xy=0$
. We refer to
$y$
as a complement of
$x$
. We say that
$\mathcal L$
is a complemented lattice if every element of
$\mathcal L$
is complemented.
Lemma 5.10. Let
$\mathcal L$
be a metric lattice, and fix
$x\in L$
. If
$d'(x,y)=1$
, then
$y$
is a complement of
$x$
. If
$y\in L$
is metrically modular, then the converse is also true.
Proof. If
$d'(x,y)=1$
, then
$1=d'(x,y)=2|x+y|-|x|-|y|\leq |x+y|-|xy|$
; thus,
$1+|xy|\leq |x+y|\leq 1$
. We conclude that
$|x+y|=1$
and
$|xy|=0$
, therefore,
$x+y=1$
and
$xy=0$
.
Since
$y$
is metrically modular, then
$d'(x,y)=|x+y|-|xy|$
. Thus, if
$y$
is a complement of
$x, d'(x,y)=|x+y|-|xy|=1-0=1$
.
Remark 5.11. For the converse statement in the previous result, the assumption of metric modularity is necessary. To see this, consider the finite partition lattice of a set with four elements,
$P_4$
, and the partitions
Since
$x+y=1,xy=0, |x|,|y|=\frac {4-2}{3}=\frac {2}{3},$
and
$|x+y|+|xy|=1<\frac {4}{3}=|x|+|y|$
, we observe that
$P_4$
is not metrically modular and
$y$
is a complement of
$x$
. However,
$d(x,y)=2|x+y|-|x|-|y|=2-\frac {2}{3}-\frac {2}{3}=\frac {2}{3}<1$
.
For the following result we need this lemma.
Lemma 5.12. Let
$\mathcal M$
be a distributive metrically modular complete metric lattice. If
$(x_i)$
is a sequence in
$\mathcal M$
, then setting
$z=\Pi _i x_i$
we have that
and
if the sum converges.
Proof. Setting
$z_n=\Pi _{i=1}^n x_i$
, we have that
$(z_n)$
is a decreasing sequence, so
$(z_n)$
is Cauchy and
$z_n\rightarrow z$
by Lemma 3.16. Using Lemma 5.3 and the distributive property we have inductively that
hence, the result obtains in the limit by continuity. The argument works the same with
$d'$
replacing
$d$
.
Definition 5.13. Let
$\mathcal L$
be a metric lattice. We say that
$x\in L$
is weakly complemented if
$\sup _y d'(x,y)=1$
. We say that
$\mathcal L$
is weakly complemented if
$\inf _x\sup _y d'(x,y)=1$
.
Proposition 5.14. Let
$\mathcal M$
be a distributive, metrically modular complete metric lattice. We have that
$x\in \mathcal M$
is weakly complemented if and only if
$x$
is complemented, and that complement is unique.
Proof. We know that complemented implies weakly complemented by Lemma 5.10, so we only need to prove the converse.
Since
$x\in \mathcal M$
is weakly complemented, we can choose for every
$i\in \mathbb N$
a
$z_i\in \mathcal M$
such that
$1-2^{-i}<d'(x,z_i)\leq 1$
. Given that for every metric lattice the inequality
$d'(x,y)\leq |x+y|-|xy|\leq 1$
holds, we can conclude that for every
$i\in \mathbb N, 1-2^{-i}<|x+z_i|-|xz_i|$
, and thus,
Therefore, for every
$n\in \mathbb N$
, we have that
$d'(x+z_n,1),\, d'(xz_n,0)<2^{-n}$
. Let’s construct
$t=\liminf z_i$
.
We define
$t_k^N:=\Pi _{i=k}^N z_i$
and
$t_k:=\Pi _{i=k}^\infty z_i$
, noting that
$t_k^N\rightarrow t_k$
as
$N\rightarrow \infty $
by Lemma 3.16. For
$k<l$
and
$M>N$
we have that
$d'(t_k^Mt_l^N, t_k^M)=0$
, so
$\lim _{M\rightarrow \infty }d'(t_k^Mt_l^N,t_k^M)=d'(t_kt_l^N,t_k)=0$
when
$k<l$
by Lemma 5.3. Now, taking the limit as
$N$
tends to
$\infty $
, we have that
$d'(t_kt_l,t_k)=0$
when
$k<l$
, so
$(t_k)$
is increasing, therefore Cauchy. Setting
$t=\lim _k t_k$
, from
$t\geq t_k$
and Lemma 5.12, we observe that for every
$k\in \mathbb N$
we have that
Using that
$t_k\leq z_k$
for every
$k$
we get
In either case the right side of the inequality tends to
$0$
as
$k$
tends to
$\infty $
, therefore
$d(x+t,1)=d(xt,0)=0$
. In other words
$x+t=1$
and
$xt=0$
, which shows that
$t$
is a complement of
$x$
. To prove uniqueness suppose
$t'$
is another complement of
$x$
. Using the distributive property we have that
and the result obtains.
Remark 5.15. There are cases where complements do not exist. For example, consider the lattice
$L_n:=B_n\cup \{1^+\}$
where
$B_n$
is the Boolean algebra with
$n$
atoms, with minimum
$0$
, maximum
$1$
, and
$1^+$
is an additional element above
$1$
. By setting,
$|\cdot |: L_n\to [0,1]$
with
for all
$a\in B_n$
, and
$|1^+|=1$
, we have that
$L_n$
is a distributive, metrically modular complete metric lattice where the only elements with complements are
$0$
and
$1^+$
. Also note that in this example
$d=d'$
and
$\inf _x\sup _y d'(x,y)=\frac {n}{n-1}<1$
.
Remark 5.16. Consider the inequality
which we may rephrase as
$2|x+y+z|\geq d'(x,z) + d'(y,z) + d'(x,y)$
. It is easy to see that this implies that if both
$x$
and
$y$
complement
$z$
, then
$x=y$
.
Uniqueness of complements does not hold for metric lattices in general (see Lemma 6.19), though by [Reference Dilworth15] every lattice is a sublattice of a uniquely complemented lattice. Consider the partition lattice
$P_3$
, which is not uniquely complemented. In this case the inequality also fails to hold. Consider
$x_1:=\{\{1\},\{2,3\}\}, x_2:=\{\{2\},\{1,3\}\}$
, and
$x_3:=\{\{3\},\{1,2\}\}$
, observe that
$|x_1|=|x_2|=|x_3|=\frac {1}{2}$
and
$|x_1+|x_2|=|x_1+x_3|=|x_2+x_3|=|x_1+x_2+x_3|=1$
. Therefore,
Question 5.17. For each
$S\subseteq [[n]]$
, we write
$x_S := \sum _{i\in S} x_i$
, with
$x_\emptyset := \prod _i x_i$
. For which lattices does the “inclusion/exclusion” inequality hold that
This condition for an
$n$
-tuple is witnessed by
so defines an elementary class. This condition is formally dual, exchanging meets and joins, with Hrushovski’s notion of “flatness” for pregeometries [Reference Hrushovski28].
5.4 Metric lattices and Boolean algebras
A lattice which is distributive and complemented is referred to as a Boolean algebra. Thus, it follows from the last result that a distributive metrically modular metrically complemented complete metric lattice is a Boolean algebra.
Notation 5.18. For a Boolean algebra
$\mathcal A$
we will denote the (unique) complement of
$x\in \mathcal A$
by
$x^c$
.
Lemma 5.19. Let
$\mathcal M$
be a distributive, metrically modular complete metric lattice. For every
$x,y\in \mathcal M$
we have that
$d'(x^c,y^c) = d'(x,y)$
.
Proof. From the definition, we know that
$\mathcal M$
is a Boolean algebra. For
$x\in \mathrm{M}{\kern-6pt ,}$
we observe by metric modularity that
$1=|x+x^c|-|xx^c|=|x|+|x^c|$
. Therefore, by metric modularity and De Morgan’s laws we get that
Now let’s consider the sentences
and
and the theory
Next, we will prove that this theory and the following
$L^{pr}$
-theory
$\mathsf {PR}$
found in [Reference Berenstein and Henson6, Section 4] are equivalent.
Definition 5.20. The continuous signature
$L^{pr}$
is defined as follows:
-
• $\mu $
as an unitary predicate symbol with modulus of uniform continuity
$\Delta _\mu (\varepsilon )=\varepsilon $
. -
• $\cap $
and
$\cup $
as binary operations with modulus of uniform continuity
$\Delta _\cap (\varepsilon )=\Delta _\cup (\varepsilon ) =\frac {\varepsilon }{2}$
.
$\cdot ^c$
as an unitary operation symbol with modulus of uniform continuity
$\Delta _c(\varepsilon )=\varepsilon $
. -
• $1$
and
$0$
as constant symbols.
The
$L^{pr}$
-theory is formed by the following
$L^{pr}$
-conditions:
-
• Boolean algebra axioms: As stated in [Reference Berenstein and Henson6, Section 4], each one of these is the $\forall $
-closure of an equation between terms, so it can be expressed in our setting as a condition. Example: From the axiom
$\forall x,y (x\cap y= y\cap x)$
we get the condition
$\sup _{x,y}d(x\cap y,y\cap x)$
. -
• Measure axioms:
-
– $\mu (0)=0$
and
$\mu (1)=1.$
-
– $\sup _{x,y}(\mu (x\cap y) \stackrel{.}{-} \mu (x)).$
-
– $\sup _{x,y}(\mu (x) \stackrel{.}{-}\mu (x\cup y)).$
-
– $\sup _{x,y}|(\mu (x) \stackrel{.}{-}\mu (x\cap y))-(\mu (x\cup y) \stackrel{.}{-}\mu (y))|.$
-
-
• Identification of $d$
and
$\mu $
:
$\sup _{x,y}|d(x,y)-\mu (x\Delta y)|.$
We are considering
$\mathfrak L\subset L^{pr}$
where the constant symbols are the same and
$+$
corresponds to the
$\cup $
symbol.
Proposition 5.21. If
$\mathcal M$
is an
$\mathfrak L$
-structure, then
$\mathcal M$
is a model of
$T_{BML}$
if and only if
$M$
(viewed as an
$L^{pr}$
-structure) is a model of
$\mathsf {PR}$
.
Proof. Let’s suppose that
$\mathcal M\models T_{BML}$
. First let’s check that
$\mathcal M$
can be seen as an
$L^{pr}$
-structure. It is clear that
$\mathcal M$
has a single sort, diameter
$1$
, a couple of distinguished elements
$0$
, and
$1$
, and a function
$+$
with modulus of uniform continuity
$\Delta (\varepsilon )=\varepsilon /2$
, which is the interpretation of
$\cup $
. We need to find interpretations for
$\cap ,\cdot ^c$
and the measure
$\mu $
. Using Proposition 3.6.1 and Lemmas 5.3 and 5.19 it is easy to check that
$|\cdot |$
,
$\cdot $
, and
$\cdot ^c$
each have the modulus of continuity necessary to take them as interpretations of
$\mu $
,
$\cap $
, and
$\cdot ^c$
, respectively. Thus, we can view
$\mathcal M$
as an
$L^{pr}$
structure.
We now need to check that
$\mathcal M$
interpreted as an
$L^{pr}$
structure satisfies the axioms of
$\mathsf {PR}$
. Since
$\mathcal M$
is a Boolean algebra, it is clear that it satisfies the axioms about Boolean algebras, it also satisfies the axiom about the connection between
$\mu $
and
$d$
because by
$\sigma _{d'}$
we get that for every
$x,y\in \mathcal M$
where
$x\Delta y:= xy^c+x^cy$
.
For the measure axioms, we can check that
$|0|=0$
and
$|1|=1$
. By Proposition 2.4, the sentence
$\sigma _{\text {mod}}$
and the behavior defined for
$+$
and
$\cdot ^c$
it follows that
$\mathcal M$
satisfies the axioms of measure. Therefore, it is a model of
$\mathsf {PR}$
.
Now let’s suppose that
$\mathcal M$
is a
$L^{pr}$
-structure. It is clear that we can view
$\mathcal M$
as an
$\mathfrak L$
structure, when we forget about the interpretations of
$\cap ,\cdot ^c$
, and
$\mu $
. (Note, however, that from the axiom
$(3)$
of
$\mathsf {PR}$
it follows that
$\mu =|\cdot |$
.) Now let’s check that it satisfies the axioms of
$T_{BML}$
. We proceed sequentially.
-
TML ) The first five axioms follow easily from the axioms of $\mathsf {PR}$
, the sixth axiom follows from the inequality
$(x+z)\Delta (y+z)\leq x\Delta y$
in Boolean algebras plus the measure and metric axioms of
$\mathsf {PR}$
theory. The last axiom follows from the modularity expressed by the measure axioms and Proposition 3.7. Hence
$\mathcal M$
satisfies
$T_{ML}$
. -
TMML ) From the measure axioms it is clear that $\mathcal M$
is metrically modular; thus, by Proposition 5.2 it models
$T_{MML}$
-
TDML ) This follows from Proposition 5.8 and the Boolean algebra axioms.
-
TBML ) This follows from metric modularity, the Boolean algebra axioms, and Proposition 5.14.
Proposition 5.22. Let
$\mathcal M$
be a complete metric lattice. If
$\mathcal N\subseteq \mathcal M$
is a sublattice which is either: (1) metrically modular, distributive, and metrically complemented or (2) Boolean, then
$\overline {\mathcal N}$
is a sublattice with the same properties.
Proof. First, let’s prove that every
$\overline {\mathcal N}$
is metrically modular. Given
$x,y\in \overline {\mathcal N}$
, we know by uniform continuity of the
$\mathfrak L$
-formula
$\varphi $
defined in equation (5.3), that for every
$\varepsilon>0$
there is a
$\delta>0$
such that if
$d(x,x'),d(y,y')<\delta $
, then
$|\varphi (x,y)-\varphi (x',y')|<\varepsilon $
. Since
$x,y\in \overline {\mathcal N}$
and
$\mathcal N$
is metrically modular, for each
$\varepsilon>0$
there are some
$x_\varepsilon ,y_\varepsilon \in \mathcal N$
such that
$d(x,x_\varepsilon ),d(y,y_\varepsilon )<\delta $
and
$\varphi (x_\varepsilon ,y_\varepsilon )=0$
. It follows from this that
$|\varphi (x,y)-\varphi (x_\varepsilon ,y_\varepsilon )|=|\varphi (x,y)|<\varepsilon $
for every
$\varepsilon>0$
, so we conclude that
$\varphi (x,y)=0$
for any
$x,y\in \overline {\mathcal N}$
, as desired.
Now observe that for any
$x,y\in \overline {\mathcal N}$
, there are Cauchy sequences
$(x_n),(y_n)$
such that
$x_n\to x$
and
$y_n\to y$
. From the uniform continuity of the join operation on
$\mathcal M$
it follows that
$x_n+y_n\to x+y$
on
$M$
, in addition
$x_n+y_n\in \mathcal N$
for each
$n$
since
$\mathcal N$
is a sublattice. So we can conclude that
$x+y\in \overline {\mathcal N}$
. Though the meet operation isn’t necessarily uniformly continuous, by Proposition 5.6 we know that it is uniformly continuous on metrically modular sets. Since
$\overline {\mathcal N}$
is metrically modular and
$x,y,x_n,y_n\in \overline {\mathcal N}$
, we have that
$x_ny_n\to xy$
and
$x_ny_n\in \mathcal N$
for each
$n$
, concluding that
$xy\in \overline {\mathcal N}$
. So
$\overline {\mathcal N}$
is a sublattice.
Finally, let’s prove that it is distributive and metrically complemented. Taking
$x,y,z\in \overline {\mathcal N}$
and sequences
$(x_n),(y_n),(z_n)$
on
$\mathcal N$
such that
$x_n\to x, y_n\to y$
and
$z_n\to z$
it is clear by the uniform continuity of the join and meet operations that
$x_n(y_n+z_n)\to x(y+z)$
and
$z_ny_n+x_nz_n\to xy+xz$
. However, as
$\mathcal N$
is Boolean and
$x_n,y_n,z_n\in \mathcal N$
for each
$n$
, so it follows that
$x_n(y_n+z_n)=x_ny_n+x_nz_n$
and we conclude that
$x(y+z)=xy+xz$
for any
$x,y,z\in \overline {\mathcal N}$
, or in other words that
$\overline {\mathcal N}$
is distributive. On the other hand, we know that
$\sup _y d(x,y)=1$
for every
$x\in \mathcal N$
, as that expression is uniformly continuous, we get that
$\sup _y d(x,y)=1$
for every
$x\in \overline {\mathcal N}$
. We conclude that
$\overline {\mathcal N}$
is also metrically complemented, and therefore the proposition is proved.
6 Partition lattices
6.1 Finite partition lattices
We begin by fixing some notation and terminology which will be crucial for this section.
Definition 6.1. Let
$P_n$
denote the lattice of partitions of the set
$[[n]] := \{1,\dotsc ,n\}$
with the following order: Given
$x,y$
partitions of
$[[n]]$
,
$x\leq y$
if and only if for all
$A\in x$
there is a
$B\in y$
such that
$A\subset B$
. Given a partition
$x\in P_n$
we define
-
(1) $\langle x\rangle $
as the number of blocks of
$x$
that are singletons, -
(2) $[x]$
as the number of blocks of
$x$
that have at least two elements, -
(3) $\#x = \langle x\rangle + [x]$
as the number of blocks of
$x$
, -
(4) $|x|=\frac {n-\#x}{n-1}$
as the norm of
$P_n$
, and -
(5) for $S\subseteq [[n]]$
,
$i(x,S)$
as the number of blocks of
$x$
which have non-empty intersection with
$S$
. (Note
$i(x,[[n]]) = \#x$
.)
If
$[x]\leq 1$
, then
$x$
is called a singular partition. Every non-zero singular partition is defined by its unique block with more than two elements, which we will call the basic block of
$x$
, in which case we will define
$B_x\subseteq [[n]]$
to be the basic block of
$x$
. By convention
$B_0 = \{1\}$
is the basic block of
$0$
. We will denote the set of singular partitions in
$P_n$
by
$\Sigma _n$
.
Recall that
$P_n$
can be viewed as a metric lattice when equipped with the metric
We will implicitly assume that
$P_n$
is equipped with this metric.
The following formulas are readily apparent.
Lemma 6.2. For
$x,y\in P_n$
with
$y$
singular, we have that
and
Lemma 6.3. For any partition
$x\in P_n$
we have that
Proof. We fix
$x\in P_n$
. If
$y$
is a singular partition, then by Lemma 6.2 we get that
We will use this formula to show that a closest singular partition to
$x$
is the one whose basic block is the union of all of the non-singleton blocks of the partition
$x$
.
Let’s denote this partition by
$\pi _x$
. Since
$x\leq \pi _x$
, it is clear that
Setting
$B_{\pi _x}$
to be the basic block of
$\pi _x$
, for another singular partition
$y$
with basic block
$B_y$
, let
$k$
be the number of elements in
$B_{\pi _x}\setminus B_y$
and
$l$
be the number of elements in
$B_y\setminus B_{\pi _x}$
. Since
$B_{\pi _x}$
is the disjoint union of blocks of
$x$
of size at least two, the removal of the elements
$B_{\pi _x}\setminus B_y$
decreases
$i(x,B_{\pi _x})$
by at most
$\lfloor k/2 \rfloor $
, while the addition of elements from
$B_y\setminus B_{\pi _x}$
increases
$i(x,B_{\pi _x})$
by exactly
$l$
since every block of
$x$
intersecting
$B_y\setminus B_{\pi _x}$
is a singleton. Therefore, we have that
It follows that
In this way the result obtains.
The next results will show that the set of modular partitions is exactly
$\Sigma _n$
and that it is a definable set with respect to the “theory of finite partition lattices,”
$T_{FPL}$
(see Definition 6.12).
Lemma 6.4. For all partitions
$x,y\in P_n$
with
$x\leq y$
we have that
Proof. We begin by noting that
$x\leq y$
implies that
$\#x\geq \#y$
and
$\langle x\rangle \geq \langle y\rangle $
, however
$[x] - [y]$
can be negative. Next, observe that
since a block of size at least two of
$y$
either contains a block of size at least two of
$x$
or is obtained by merging at least two singleton blocks of
$x$
. As
$\langle y\rangle $
singleton blocks must remain, there are at most
$\langle x\rangle - \langle y\rangle $
blocks which can be merged. Rearranging this equation we get that
hence,
The result thus obtains.
Recall the formula
which measures how far
$(x,y)$
is from being a modular pair.
Proposition 6.5. For any
$x\in P_n$
, we have that
where
$\varphi $
is the metric-modular pair equation defined in (5.3)
Proof. Given a partition
$x\in P_n$
, by choosing two distinct elements from any block of size at least two, we can write
Using this notation, we define a partition
$x^*$
in the following way. If
$[x]$
is even, then
If
$[x]$
is odd, then
We observe that
if
$[x]$
is even, and
if
$[x]$
is odd. Thus, we can compute and note that
Using this notation we will write
and
and refer to these as the i-th pair in
$x$
and
$x^*$
, respectively.
We claim that
which establishes the result by Lemma 6.3.
Since
for any partition
$p\in P_n$
, and by the definition of
$\varphi $
(line 5.3), the previous condition is equivalent to showing that for all
$t\in P_n$
, we have that
We assume that
$\#x-\frac {[x]-1}{48}<\#(x+t)$
and
$\#x^*-\frac {[x]-1}{48}<\#(x^*+t)$
. Setting
we have that
as all other terms are integers.
Since
$\langle p \rangle \geq \langle q\rangle $
whenever
$p\leq q$
, we have that
By similar reasoning for
$x^*$
, we conclude using line (6.2) that
Applying Lemma 6.4 to the pairs
$x\leq x+t$
and
$x^*\leq x^*+t$
and using (6.2) and (6.5), we have that
Next, note that by the inequalities (6.7) that there are at least
$\langle x\rangle - 2m$
singleton blocks of
$x$
which still appear as singleton blocks of
$x+t$
. It follows that these must also be singleton blocks of
$t$
, so
Finally, we note that from line (6.6) that there are
$[x]-m$
blocks of
$x$
of size at least two which belong to pairwise distinct blocks of
$x+t$
. We denote an analogous set of blocks of
$x$
by
$D$
. Similarly, we denote an analogous set of blocks of
$x^*$
by
$D^*$
. For each index
$i\in \{1,\dotsc ,\lfloor [x]/2\rfloor \}$
such that both blocks of the pair
$C_i$
of
$x$
are elements of
$D$
and both blocks of the pair
$C_i^*$
are elements of
$D^*$
, the elements
$\{a_{2i-1}, b_{2i-1}, a_{2i}, b_{2i}\}$
must belong to distinct blocks of
$t$
which aren’t among the
$\langle x\rangle -2m$
singleton blocks chosen in the previous paragraph. We will call these pairs the “repeated pairs.”
For
$x$
, at most
$m$
blocks of size at least two do not belong to
$D$
, so there are at least
pairs
$C_i$
among the blocks of
$D$
. Similarly there are at least
$\lfloor [x^*]/2\rfloor - m = \lfloor [x]/2\rfloor - m$
pairs
$C_i^*$
among the blocks of
$D^*$
. Therefore, the number of repeated pairs is at least
$\lfloor [x]/2\rfloor - 2m$
. Using this along with the estimate (6.7) we conclude that
since
$m\geq 1$
.
It follows from lines (6.2) and (6.9) that
which suffices to show that equation (6.4) is satisfied, proving the result.
Corollary 6.6. If
$P_n$
is a finite partition lattice, then
$x\in P_n$
is metrically modular if and only if
$x$
is singular.
Proof. The “only if” direction follows directly from Proposition 6.5. For the “if” direction, we fix a singular partition
$x\in P_n$
and an arbitrary partition
$y$
. By Lemma 6.2 we have that
$\#(x+y) + \#xy = \#x + \#y$
, hence
$|x+y| + |xy| = |x| + |y|$
.
Corollary 6.7. Let
$\mathcal U$
be a non-principal ultrafilter on
$\mathbb N$
and
$P = \prod _{\mathcal U} P_n$
be an ultraproduct of finite partition lattices. We have that
$x\in P$
is metrically modular if and only if
$x$
is an ultraproduct of singular partitions.
Proof. Suppose
$x\in P$
is metrically modular, and let
$(x_n)\in \prod _{n\in \mathbb N} P_n$
be a representative sequence for
$x$
. By Łos’ theorem we have that
$\lim _{n\to \mathcal U} \sup _{y\in P_n}\varphi (x_n,y) =0$
; hence, by Proposition 6.5 we have that
$\lim _{n\to \mathcal U} d(x_n, \Sigma _n)=0$
. Thus, we can find
$x_n'\in \Sigma _n$
so that
$\lim _{n\to \mathcal U} d(x_n,x_n')= 0$
.
In the other direction, by Corollary 6.6 every singular element of
$\Sigma _n$
is metrically modular, hence so is every element of
$\prod _{n\in \mathcal U} \Sigma _n$
by Proposition 6.5 and Łos’ theorem.
Definition 6.8. Let
$P_n$
be the finite partition lattice of a set with
$n$
elements. A sublattice
$A$
is called singular if every
$x\in A$
is a singular partition.
Definition 6.9. Let
$\mathcal L=(L,<,+,\cdot ,0,1)$
be a lattice. An element
$x\in L$
is called and atom if and only if
$x\neq 0$
and for all
$y\in L$
, if
$0\leq y\leq x$
, then
$y=0$
or
$y=x$
.
Lemma 6.10. Let
$A$
be a maximal singular distributive sublattice of
$P_n$
. The following claims are true:
-
(1) There must exist an element $a^*\in [[n]]$
such that
$a^*$
belongs to the basic block of every non-zero partition of
$A$
. -
(2) The atoms of $A$
are the singular partitions
$x_e$
for
$e\in [[n]]-\{a^*\}$
, where
$x_e$
is the singular partition with basic block
$\{a^*,e\}$
. -
(3) $A\models T_{BML}$
. -
(4) $A$
is a maximal Boolean sublattice of
$P_n$
. -
(5) For every singular partition $x\in P_n$
, we have that
$d(x,A) \leq \frac {1}{n-1}$
.
Proof. We prove each claim in turn.
-
(1) Let us suppose the claim is false, then $\bigcap _{x\in A,x\neq 0} B_x=\emptyset $
. Since for all
$x\in A$
, there is an atom
$x'\leq x$
such that
$B_{x'}\subset B_x$
we have $$\begin{align*}\bigcap_{x\in A, x \text{ atom}} B_x=\bigcap_{x\in A,x\neq0} B_x=\emptyset. \end{align*}$$
Now, given atoms $x,y\in A, x\neq y, B_x\cap B_y\neq \emptyset $
, otherwise
$x+y$
would not be a singular partition, and as
$xy=0$
, then
$|B_x\cap B_y|=1$
. Thus, as
$\bigcap _{x\in A, x \text { atom}} B_x=\emptyset $
there must be different atoms
$x,y,z\in A$
with basic blocks
$B_x$
,
$B_y$
, and
$B_z$
, respectively, such that
$B_x\cap B_y=\{a\}, B_x\cap B_z=\{b\}, B_y\cap B_x=\{c\}$
, and
$B_x\cap B_y\cap B_z=\emptyset $
. Observe that
$x(y+z)\neq 0$
because
$\{a,b\}\subset B_x\cap (B_y\cup B_z)=B_{x(y+z)}$
, but as
$x,y$
, and
$z$
are atoms we have that
$xy+xz=0+0=0\neq x(y+z)$
. Hence
$A$
wouldn’t be distributive. -
(2) Let $A^*$
be the sublattice generated by all such
$x_e$
. It’s clear that
$A^*$
is Boolean as it can be seen to be isomorphic to the lattice
$2^{[[n]]-\{a^*\}}$
by associating to each
$X\subseteq [[n]]-\{a^*\}$
the singular partition with basic block
$X\cup \{a^*\}$
. By the previous claim there is an
$a^*$
which belongs to the basic block of every non-zero singular partition in
$A$
, hence
$A\subseteq A^*$
. Equality then follows by maximality of
$A$
. -
(3) It is clear that the isomorphism of $A^*$
with the Boolean lattice
$2^{[[n]]-\{a^*\}}$
given in the previous item is isometric with respect to the canonical lattice metric on
$2^{[[n]]-\{a^*\}}$
induced by the counting measure. -
(4) For any partition $x$
not belonging to
$A$
there is a block which contains a pair of elements
$\{e,e'\}\subseteq [[n]]-\{a^*\}$
. We have that
$x(x_e+x_{e'})\neq xx_e+xx_{e'}$
because the pair
$\{e,e'\}$
is included in a block of
$x(x_e+x_{e'})$
but
$e$
and
$e'$
are in different blocks of the partition
$xx_e+xx_{e'}$
. Therefore,
$A\cup \{x\}$
cannot generate a Boolean sublattice by failure of distributivity; hence,
$A$
is maximal Boolean. -
(5) Let $x\in P_n$
be a singular partition with basic block
$B_x$
. We choose
$y\in A$
to be the singular partition with basic block
$B_x\cup \{a^*\}$
and observe that $$\begin{align*}d(x,y)=\frac{\#x-\#y}{n-1}\leq\frac{\#x-(\#x-1)}{n-1}=\frac{1}{n-1}.\\[-42pt] \end{align*}$$
Now, we can use this lemma to prove our result.
Proposition 6.11. Let
$\mathcal U$
be a non-principal ultrafilter on
$\mathbb N$
. For each
$n\in \mathbb N$
choose
$A_n\subseteq P_n$
a maximal singular sublattice. We have that
$\prod _{n\in \mathcal U} A_n$
is a Boolean sublattice of
$\prod _{n\in \mathcal U} P_n$
and is equal to the set of metrically modular elements of
$\prod _{n\in \mathcal U} P_n$
.
Proof. We begin by showing that every metrically modular element of
$\prod _{n\in \mathcal U} P_n$
belongs to
$\prod _{n\in \mathcal U} A_n$
. Indeed, if
$x$
is metrically modular, by Corollary 6.7 there is representative sequence
$(x_n)$
with
$x_n\in P_n$
singular for
$\mathcal U$
-generic
$n$
. Hence, by Lemma 6.10.5 we have that
$x$
has a representative sequence
$(x_n')$
with
$x_n'\in A_n$
for
$\mathcal U$
-generic
$n$
, and
$x\in \prod _{n\in \mathcal U} A_n$
. On the other hand it is clear that if
$x\in \prod _{n\in \mathcal U}A_n$
, then
$x$
is singular again by Lemma 6.7. Finally,
$\prod _{n\in \mathcal U} A_n$
is a Boolean algebra because by Lemma 6.10 we know that each
$A_n\models T_{BML}$
so
$\prod _{n\in \mathcal U}A_n\models T_{BML}$
, and therefore it is a Boolean sublattice of
$\prod _{n\in \mathcal U} P_n$
.
6.2 Pseudofinite partition lattices
Definition 6.12. We write
$T_{FPL}$
as the theory of the set
$\{P_n :n\in \mathbb N\}$
, that is,
$\mathcal M\models T_{FPL}$
if and only if
$\sigma ^{\mathcal M} =0$
for any sentence so that
$\sup _n \sigma ^{P_n} =0$
. We then say that
$\mathcal M$
is a pseudofinite partition lattice. Note that any ultraproduct of finite partition lattices is a pseudofinite partition lattice.
In this section we investigate the properties of
$T_{FPL}$
. Let
$\mathcal M\models T_{ML}$
, and consider the functor
$\mathcal M\mapsto \mu (\mathcal M)$
which sends
$\mathcal M$
to its collection of metrically modular elements. (Note that
$\mu (\mathcal M)$
is always non-empty since
$0$
and
$1$
are modular.) We begin with the following observation which is a direct consequence of Proposition 6.5 and Corollary 6.6.
Lemma 6.13. We have that
$\mathcal M\mapsto \mu (\mathcal M)$
is a definable functor in
$T_{FPL}$
.
Proof. Indeed, the quoted results show that every “approximately modular” element of any finite partition lattice is uniformly close, independent of the size of the partition lattice, to a singular partition and that singular partitions are modular.
Remark 6.14. By Theorem 2.1, it follows that we may quantify over modular elements in
$T_{FPL}$
.
Proposition 6.15. If
$\mathcal M\models T_{FPL}$
and
$\mathcal M$
is infinite, then
$\mu (\mathcal M)$
is a Boolean sublattice.
Proof. It is well known (see, for instance, [Reference Goldbring21, Lemma 16.2.4]) that if
$\mathcal M\models T_{FPL}$
, then it admits an elementary embedding into an ultraproduct
$\prod _{i\in U} P_{n_i}$
. As
$\mathcal M$
has density character at least
$\aleph _0$
, we must have that
$\lim _{i\in U} n_i =\infty $
. Since modularity and being a Boolean sublattice are definable properties by Lemma 6.13 and Proposition 5.21, respectively, the result follows by Proposition 6.11.
Question 6.16. Is
$\mu (\mathcal M)$
definable for an arbitrary model of
$T_{ML}$
?
Regarding this question, note that the formula
$\varphi $
(equation (6.4)) is not enough to define or control the meet in
$T_{ML}$
, as it was showed in Remark 5.4, but it is enough to show the definability of
$\mu (\mathcal M)$
in models of
$T_{FPL}$
.
6.3 Sets of selectors
Definition 6.17. Let
$\mathcal L$
be a metric lattice, and let us fix
$x\in L$
. We say that an element
$y\in \mu (\mathcal L)$
is a selector for
$x$
if
$y$
complements
$x$
.
As we will see, the set of selectors play an interesting role in the context of
$T_{FPL}$
. In the following results, we show that the set of selectors of a partition is a non-empty definable set and that such sets allows us to recover the partitions by comparing the usual distance
$d(x,y)$
with the Hausdorff distance between sets of selectors.
The following is a straightforward consequence of Lemma 5.10.
Lemma 6.18. We have that
$y$
is a selector for
$x$
if and only if
$x+y=1$
and
$|x| + |y| = 1$
.
Lemma 6.19. Let
$P_n$
be a finite partition lattice. We have that every element
$x\in P_n$
admits a selector. The set of selectors is the set of all singular partitions whose main block intersects each block of
$x$
at exactly one element.
Proof. Given a partition
$x$
and a singular partition
$y$
of
$P_n$
whose main block
$B_y$
intersects each block of
$x$
at exactly one element we observe that
$B_y$
contains all singletons of
$x$
and since it intersects every other block of
$x$
, it is clear that
$x+y=\{[[n]]\}=1$
. On the other hand, we observe that
$|B_y|=\langle x\rangle +[x]=\#x$
; therefore,
$\#y= n-\#x+1$
. Consequently,
so this direction follows by Lemma 6.18.
Now suppose
$y$
is a selector of
$x$
. As, by Corollary 6.6,
$y$
is singular, and
$xy=0, x+y=1$
, we know that
and
From the first equality it follows that
$\#x=i(x,B_y)$
, that is, the main block intersects each block of
$x$
, and from the second that
$\#x=i(x, B_y)=|B_y|$
, so the main block of
$y$
has exactly
$\#x$
elements. This concludes the proof.
The main result of this section is that the same is true for any pseudofinite partition lattice.
Proposition 6.20. If
$\mathcal M\models T_{FPL}$
, then every element
$x\in M$
admits a selector.
In order to prove this proposition, we will first require a few intermediate results.
Lemma 6.21. Let
$\mathcal M\models T_{FPL}$
, and let
$x\in \mathcal M$
and
$y\in \mu (\mathcal M)$
. We have that
Proof. We claim that for any finite partition lattice
$P$
and any
$x\in P$
and
$y\in \mu (P)$
, there is
$z\in \mu (P)$
so that
$d(y,z)\leq d(x+y,1)$
and
$d(x+z,1)=0$
. From this, the result easily follows.
Let
$P_{n+1}$
be the finite partition lattice on
$n+1$
elements, and let us fix a partition
$x$
and a singular partition
$y$
. By Corollary 6.6 we know that every element of
$\mu (P_{n+1})$
is a singular partition. Now, using Lemma 6.2 we can compute
Defining
$k := \#x- i(x,B_y)$
, we have that
$d(x+y,1)=\frac {k}{n}$
. Observe that from Lemma 6.2 it also follows that
$x+y=1$
if and only if
$i(x,B_y)=\#x$
. By the definition of
$i(x,B_y)$
there are
$k$
blocks of
$x$
that do not intersect
$B_y$
; denote them by
$C_1,\ldots , C_k$
. Taking
$c_i\in C_i$
for
$1\leq i\leq k$
we define a new singular partition
$z$
where
$B_z:= B_y\cup \{c_i\}_{i=1}^k$
. We see that
$i(x,B_z)=\#x, y\leq z$
, and
$\#z=\#y-k$
, so we conclude that
$x+z=1$
and
finishing the proof.
Corollary 6.22. Let
$\mathcal M\models T_{FPL}$
. For any
$x\in M$
,
$y\in \mu (\mathcal M)$
, and
$\epsilon>0$
, there is
$z\in \mu (M)$
so that
$x+z=1$
and
$d(y,z)\leq (1+\epsilon )\,d(x+y,1)$
.
Proof. Given such
$x,y\in M$
, if
$x+y=1$
, the claim is immediately true, so let’s suppose
$x+y\neq 1$
, i.e.,
$d(x+y,1)>0$
, and pick
$\epsilon>0$
by Lemma 6.21 we may inductively construct a sequence
$(z_n)$
in
$\mu (\mathcal M)$
in the following way:
-
• Let $z_0 = y$
. -
• Given $z_n$
, take
$z_{n+1}$
such that
$d(z_{n+1},z_n)\leq d(x+z_n,1)+2^{-(n+1)}\epsilon d(x+y,1)$
and
$d(x+z_{n+1},1)\leq 2^{-(n+2)}\epsilon d(x+y,1)$
.
By construction we have that
$d(z_{n+1},z_n)\leq 2 \cdot 2^{-(n+1)}\epsilon d(x+y,1)=2^{-n}\epsilon d(x+y,1)$
for
$n>1$
. Thus, by the triangle inequality,
$(z_n)$
is Cauchy and converges to
$z\in \mu (\mathcal M)$
with
$x+z=1$
and
$d(z,y)\leq d(x+y,1)+\epsilon d(x+y,1)$
, proving the result.
We define the following
$\mathfrak L$
-formula for models of
$T_{FPL}$
:
Lemma 6.23. The following formula holds in
$T_{FPL}$
:
Proof. We claim that for any finite partition lattice
$P = P_{n+1}$
and any
$y\in P$
and
$z\in \mu (P)$
, there is
$w\in \mu (P)$
so that
From this the result easily follows.
We fix
$y$
and
$z$
as above, and define the numbers
Note that
and
By the definition of
$i(y,B_z)$
we get that there are
$k$
blocks,
$C_1,\dotsc ,C_k$
of
$y$
which do not intersect
$B_z$
and
$l$
additional elements,
$x_1,\dotsc ,x_l$
of
$B_z$
which belong to blocks whose intersection with
$B_z$
contains at least one other element. Taking an element
$c_i\in C_i$
from each of the
$k$
blocks, as we did in the proof of Lemma 6.21, we let
$w$
be the singular partition for which
$B_w = (B_z\setminus \{x_1,\dotsc ,x_l\})\cup \{c_1,\dotsc ,c_k\}$
. By construction we have that
$|B_w|=\#y=|B_z|+k-l$
,
$y+w=1$
,
$1=|y|+|w|$
, and
$z+w$
is a singular partition. Finally, we note that
and
as desired.
Lemma 6.24. Let
$\mathcal L$
be a metric lattice and
$\sum _{n=0}^\infty a_n$
a convergent series of non-negative real numbers. If
$(x_n)$
is a sequence in
$\mathcal L$
such that
for all
$n\in \mathbb N$
, then
$(x_n)$
is Cauchy.
Proof. Let
$x_{(n,k)} := x_n + x_{n+1} + \dotsb + x_{n+k}$
. We have by the triangle inequality and the property that
$d(x+z,y+z)\leq d(x,y)$
that
We conclude that
hence,
for all
$n,k\in \mathbb N$
. Setting
$\alpha = \liminf _n |x_n|$
, it follows that
$\lim _n |x_n| = \alpha $
; thus,
$(|x_n|)$
is a Cauchy sequence. It now follows from (6.10) that
for all
$k\in \mathbb N$
. Thus,
$(x_n)$
is Cauchy in
$d'$
, hence for
$d$
as well.
Notation 6.25. For
$\mathcal M\models T_{FPL}$
and
$x\in M$
, we write
$\Gamma (x)$
for the set of all selectors of
$x$
in
$M$
.
The next proposition is a quantitative version of Proposition 6.20, so easily implies that result.
Proposition 6.26. Let
$\mathcal M\models T_{FPL}$
and
$\epsilon>0$
. If
$y\in \mathcal M, z\in \mu (\mathcal M)$
, and
$y+z=1$
, then there exists
$w\in \mu (\mathcal M)$
such that
$w\in \Gamma (y)$
and
$d(z,w)\leq (1+\epsilon )|1-|y|-|z||$
.
Proof. Since
$y+z=1$
, by Lemma 6.18 we have that
$z\in \Gamma (y)$
if and only if
$|1 - |y| - |z|| = 0$
. Thus, without loss of generality we may assume that
$|1 - |y| - |z||\not = 0$
. It also follows from Lemma 6.23 that
$\chi _z(y)=0$
; therefore, for every
$\epsilon>0$
we can find
$w\in \mu (\mathcal M)$
so that
By Corollary 6.22 we can find a modular element
$w'$
so that
$w'+y=1$
and
Thus, for any
$z\in \mu (\mathcal M)$
with
$y+z=1$
and all
$\epsilon>0$
we can find
$w'\in \mu (\mathcal M)$
so that
$y+w'=1$
,
Starting with
$w_0=z$
and some
$\epsilon>0$
, we may thus inductively construct a sequence
$(w_n)$
in
$\mu (\mathcal M)$
so that
$y+w_{n}=1$
,
$d(w_0,w_1)\leq (1+\frac {\epsilon }{2})(|1-|y|-|w_0||)$
and for all
$n>1$
By the last inequality, the sequence
$(w_n)$
is Cauchy; thus, by completeness
$(w_n)$
converges to a selector
$w$
of
$y$
so that
In this way the result obtains.
Corollary 6.27. Let
$\mathcal M\models T_{FPL}$
, consider
$x,y\in M$
and
$\epsilon>0$
. If
$z\in \Gamma (x)$
, then there is
$w\in \Gamma (y)$
so that
$d(z,w)\leq (3+\epsilon )\, d(x,y)$
.
Proof. Using that
$z\in \Gamma (x)$
and Corollary 6.22, we know there exist a
$z'$
such that
$y+z'=1$
and
$d(z,z')\leq (1+\epsilon )\,d(z+y,1)\leq (1+\epsilon )(d(z+y,z+x)+d(z+x,1))\leq (1+\epsilon )\,d(x,y)$
. Now, using Proposition 6.26 we know that there is a
$w\in \Gamma (y)$
such that
so we can conclude that
As
$\epsilon>0$
is arbitrary, this proves the statement.
The next result proves that the set of selectors of a given element is definable.
Proposition 6.28. Given
$\mathcal M\models T_{FPL}$
and
$x\in M$
. For every
$y\in M$
we have that
where
$\varphi $
is defined as in line (5.3).
Proof. Applying the results from Proposition 6.5, Corollary 6.22, and Proposition 6.26 we have that:
-
• there is a $y'\in \mu (\mathcal M)$
such that
$d(y,y')\leq 48\sup _w\varphi (y,w)$
; -
• there is a $z\in \mu (\mathcal M)$
such that
$x+z=1$
and
$d(y',z)\leq (1+\epsilon )\,d(y'+x,1)$
; -
• there is a $z'\in \Gamma (x)$
such that
$d(z,z')\leq (1+\epsilon )|1-|x|-|z||$
.
We observe that
$d(y,\Gamma (x))\leq d(y,z')\leq d(y,y')+d(y',z)+d(z,z')$
. Developing this inequality using the mentioned results we have that for every
$\epsilon>0$
:
Finally, as by letting
$\epsilon $
tend to zero we conclude that
as was desired.
Corollary 6.29. For all
$\mathcal M\models T_{FPL}$
and
$x\in M$
,
$\Gamma (x)$
is definable.
Proof. This follows from the previous result by Theorem 2.1.3.
We recall that the Hausdorff distance between two subsets
$A$
and
$B$
of a metric space
$(X,d)$
is defined as
Proposition 6.30. Given a finite partition lattice
$P_n$
and
$x,y\in P_n$
, we have that
Furthermore, given
$z\in \Gamma (x),w\in \Gamma (y)$
, we have that
and
where
$\gamma (x,y):=\displaystyle \min _{z\in \Gamma (x)}\max _{w\in \Gamma (y)}|B_z\cap B_w| $
.
Proof. Let’s start by proving the formula (6.12). By Corollary 6.6, we can claim that for every pair of singular partitions
$z,w\in P_n$
that
Indeed, if
$B_z\cap B_w\neq \emptyset $
, then
and if and if
$B_z\cap B_w=\emptyset $
, then
Altogether, this establishes formula (6.12).
We now proceed to formula (6.13). Fixing
$z\in \Gamma (x)$
we see that
Observe that we can always find a
$w\in \Gamma (y)$
such that
$|B_z\cap B_w|\geq \#(x+y)\geq 1$
because we can eliminate elements of
$B_z$
until we get a selector of
$x+y$
which will have a main block of cardinality
$\#(x+y)$
; we can then add elements to get a selector
$w$
of
$y$
. Therefore, we can conclude that, for every
$z\in \Gamma (x),$
Formula (6.13) now follows easily. Finally, note that
$\gamma (x,y), \gamma (y,x)\geq \#(x+y)$
by the observations made in the previous paragraph; thus, we can conclude that
$d_{Haus}(\Gamma (x),\Gamma (y))\leq d(x,y)$
as desired.
Corollary 6.31. Given
$\mathcal M\models T_{FPL}$
and
$x,y\in M, d_{Haus}(\Gamma (x),\Gamma (y))$
is definable and
Proof. By Corollary 6.29, we know that for any
$x,y\in M$
,
$\Gamma (x)$
and
$\Gamma (y)$
are definable; thus, the expression
is a definable predicate in
$(x,y)$
. Finally, by Proposition 6.30, we know that (6.14) holds for all finite partition lattices, proving the statement.
Remark 6.32. Equality generally fails to hold. Consider partitions
$x,y$
of
$P_6$
defined as follows:
$x:=\{\{1,4\},\{2,3\},\{5,6\}\}$
and
$y:=\{\{1,2\},\{4,5\},\{3\},\{6\}\}$
. Note that
However, we can check that for any
$z\in \Gamma (x)$
there exists a
$w\in \Gamma (y)$
such that
$|B_z\cap B_w|=2$
, similarly for any
$w\in \Gamma (y)$
. Therefore, by Proposition 6.30 we conclude that
$d_{Haus}(\Gamma (x),\Gamma (y))=\frac {4+3-2\cdot 2}{5}=\frac {3}{5}<1=d(x,y)$
.
However, we can, in fact, bound
$d(x,y)$
using a multiple of
$d_{Haus}(\Gamma (x),\Gamma (y))$
. Before presenting the result, we introduce the following notation and remarks.
Definition 6.33. In
$P_n$
, given
$x\in P_n$
and
$S\subset [[n]]$
we define the restriction of
$x$
to
$S$
as
$x_S:=\{B\cap S: B\in x\}$
.
If we impose some conditions on
$S$
, the restrictions will have good behavior.
Remark 6.34. Consider
$x,y,z\in P_n$
with
$z:=\{B_1,\ldots , B_m\}\geq x,y$
. Then the following claims are true:
-
• $\#x=\sum _{i=1}^m \#x_{B_i}$
; -
• $t\in \Gamma (x)$
if and only if there exists
$t_i\in \Gamma (x_{B_i})$
for
$i=1,\ldots ,m$
such that
$B_t= \sqcup _{i=1}^m B_{t_i}$
; -
• $\gamma (x,y)=\sum _{i=1}^m \gamma (x_{B_i},y_{B_i})$
.
Proposition 6.35. Given
$\mathcal {M}\models T_{FPL}$
and
$x,y\in M$
, we have that
Consequently,
for all
$x,y\in M$
.
Proof. We will show that the inequality holds for all finite partition lattices, from there it follows that
$T_{FPL}$
implies the statement. Let’s consider the finite partition lattice
$P_n$
and
$x,y\in P_n$
.
Firstly, observe that for each
$B\in x+y$
if
$x_B\leq y_B$
, then
$\#y_B=1$
, and thus
Considering the partition
$\{H,H^c\}\geq x+y$
, where
and using Proposition 6.30 we note that
and
Since it is clear that
$\#x_H-\#(x+y)_H\leq 2(\#x_H+\#y_H-2\#(x+y)_H)$
, we need to focus on the
$H^c$
part. Therefore, by replacing
$x$
and
$y$
by
$x_{H^c}$
and
$y_{H^c}$
, we can assume without loss of generality that for all
$B\in x+y, x_B\nleq y_B$
and
$y_B\nleq x_B$
. We need to show
Recalling that
$d(x,x+y) = (\#x - \#(x+y))/(n-1)$
, this is equivalent to showing
We will establish this through a series of claims. Before proceeding further, let us introduce some definitions.
Under the assumption that
$x_B\not \leq y_B$
and
$y_B\not \leq x_B$
for all
$B\in x+y$
, we define a graph
$\mathcal G_x = (\mathcal V_x, \mathcal E_x)$
as follows. The vertices of
$\mathcal G_x$
are the blocks of
$x$
. Two blocks
$A,B\in x$
are connected by an edge if there is some block
$C\in y$
so that
$A\cap C$
and
$B\cap C$
are both nonempty, and
$A\in x$
has a self loop if there is
$Y\in y$
so that
$Y\subseteq A$
. By our assumptions, every vertex is incident to at least one edge that is not a self loop. We note that this graph is not simple in the sense that we allow two blocks to be joined by multiple edges, one for each block of
$y$
which intersects each of the blocks non-trivially. We thus have an edge labeling function
$\ell _x: \mathcal E_x\to y$
which sends each edge to the block of
$y$
that induces it. For an edge
$e\in \mathcal E_x$
, we refer to
$\ell _x(e)$
as the label of
$e$
.
We fix a maximum matching, i.e., a matching of maximal cardinality,
$P:=\{\{A_i, B_i\}\}_{i=1}^{N}$
of the vertices of
$\mathcal G_x$
and let
$\{\{C_j\}\}_{j=1}^{S}$
enumerate the unmatched vertices. We consider the quotient graph
$\widetilde {\mathcal G}_x = (\widetilde {\mathcal V}_x, \widetilde {\mathcal E}_x)$
of
$\mathcal G_x$
obtained by identifying the vertices corresponding to
$A_i$
and
$B_i$
for each
$i=1,\dotsc , N$
and leaving the
$C_j$
for.
${j=1,\ldots ,S}$
. We partition
$\widetilde {\mathcal V}_x$
into two sets
$U_x = \{u_1,\dotsc , u_N\}$
and
$V_x = \{v_1,\dotsc ,v_S\}$
corresponding, respectively, to the sets of matched vertex pairs and unmatched vertices.
Before continuing, we bring attention to the following delicate distinction: an edge
$e\in \mathcal E_x$
is incident to
$\{A,B\}\subset \mathcal G_x$
if and only if
$e$
is incident to both
$A$
and
$B$
, while an edge
$e'\in \widetilde {\mathcal E}_x$
is incident to
$\{A,B\}$
if and only if
$e'$
is incident to
$A$
or
$B$
. If this follows from the context in which set of edges we are working with, we will not mention it.
We define the function
$L_x: \widetilde {\mathcal V}_x\to 2^y$
by sending each vertex
$v\in V_x$
to the set of all labels of edges in
$\mathcal E_x$
incident to it, and each vertex
$u=\{A,B\}\in U_x$
to the set of all labels of edges in
$\mathcal E_x$
incident to
$\{A,B\}$
, that is incident to both
$A$
and
$B$
. For each subset
$S\subseteq \widetilde {\mathcal V}_x$
, we define its support
$\operatorname {\mathrm {supp}}(S)\subseteq 2^x$
to be the collection of the representative blocks of the elements of
$S$
. For example, if
$u = \{A,B\}\in U_x$
,
$\operatorname {\mathrm {supp}}(\{u\}) = \{A,B\}$
. Note that there can be multiple edges with the same label incident to a vertex
$v$
.
Interchanging the roles of
$x$
and
$y$
, we can define the graph
$\widetilde {\mathcal G}_y$
similarly, with
$U_y, V_y, L_y$
, etc., having the same interpretations.
Claim 6.36. With the same notation as above, the following statements are true:
-
(1) For $\{A, B\}:=u\in U_x$
and
$v:=\{C\},v':=\{C'\}\in V_x$
, distinct, if there is an edge
$e\in \mathcal E_x$
incident to
$\{A, C\}$
, then there is no edge
$e'\in \mathcal E_x$
incident to
$\{B, C'\}$
. -
(2) For $v,v'\in V_x$
, distinct, we have that
$L_x(v)\cap L_x(v') = \emptyset $
. -
(3) For $u,u'\in U_x$
and
$v,v'\in V_x$
, all distinct, if there are edges
$e, e'$
so that
$e$
is incident to
$\{u,v\}$
and
$e'$
is incident to
$\{u',v'\}$
, then
$L_x(u)\cap L_x(u') = \emptyset .$
Proof. We prove each assertion in turn.
-
(1) If there was an edge $e'\in \mathcal E_x$
incident to
$\{B, C'\}$
, then the set $$\begin{align*}(P\setminus\{\{A,B\}\})\cup\{\{A,C\}, \{B, C'\}\}\end{align*}$$
would be a matching of $\mathcal G_x$
of greater cardinality, contradicting that
$P$
is a maximum matching. -
(2) Let us denote by $C$
and
$C'$
the blocks of
$x$
corresponding to
$v, v'\in V_x$
. If
$L_x(v)\cap L_x(v')\neq \emptyset $
, then there exist edges
$e$
and
$e'$
incident to
$v$
and
$v'$
, respectively, such that
$\ell _x(e)=\ell _x(e')=Y\in y$
. By definition of
$\mathcal G_x$
this means that
$Y\cap C\neq \emptyset $
and
$Y\cap C'\neq \emptyset $
, so there is an edge
$e^*$
incident to
$\{v,v'\}$
, and
$P\cup \{v, v'\}$
would be a matching of
$\mathcal G_x$
. This is a contradiction, since
$P$
is a maximum matching. -
(3) Let us denote by $\{A, B\}, \{A', B'\}$
the sets of blocks of
$x$
corresponding to
$u, u'$
, respectively, and by
$C, C'$
the blocks of
$x$
corresponding to
$v, v'$
, respectively. If
$L_x(u)\cap L_x(u')\neq \emptyset $
, then there exist edges
$f, f'$
in
$\mathcal G_x$
incident to
$\{A, B\}$
and
$\{A', B'\}$
, respectively, such that
$\ell _x(f)=\ell _x(f')=Y$
. Therefore,
$A,A',B,B'$
all have non-empty intersection with
$Y$
. As
$e$
is incident to
$\{u,v\}$
and
$e'$
is incident to
$\{u',v'\}$
, we can assume without loss of generality that
$\{A,C\}$
and
$\{A',C'\}$
are incident in
$\mathcal G_x$
. Therefore, the set $$\begin{align*}(P \setminus\{\{A, B\}, \{A', B'\}\})\cup\{\{C, A\},\{B, B'\}, \{C, A'\}\}\end{align*}$$
is a matching of $\mathcal G_x$
, again contradicting maximality.
Claim 6.37. Keeping the same notation, the following statements are true:
-
(1) For $u\in U_x$
and
$v,v'\in V_x$
, distinct, if
$L_x(u)\cap L_x(v)\neq \emptyset $
, then there is no edge
$e$
incident to
$\{v',u\}$
. -
(2) For $u\in U_x$
and
$v_{i_1},\ldots , v_{i_n}\in V_x$
, all distinct, if there are edges
$e_1,\ldots , e_n$
incident to
$\{u, v_{i_1}\},\dots , \{u, v_{i_n}\}$
, respectively, then there exists
$X\in u\subset x$
such that
$X\cap \ell _x(e_i)\neq \emptyset $
for every
$i=1,\ldots , n$
.
Proof. The results follow from Claim 6.36.1
For each
$v_j\in V_x$
we define the set
$C(v_j):=\{a\in \widetilde {\mathcal G}_x: L_x(a)=L_x(v_j)\}$
and the set
$\mathfrak v_j:= \operatorname {\mathrm {supp}} C(v_j)$
. Let
$\overline {\mathfrak v}_j := \bigcup _{A\in \mathfrak v_j} A$
. Note that
and that
$j\neq j'$
implies
$C(v_j)\cap C(v_{j'})=\emptyset $
, by Claim 6.36.2. We define a new partition
$x'$
to be finest partition greater than
$x$
so that each
$\overline {\mathfrak v}_j$
is a block of
$x'$
. Now, we define
and note that
$|P'|=|P|-\sum _{j=1}^S|C(v_j)-1|$
.
Claim 6.38.
$P'$
is a maximum matching of
$\mathcal G_{x'}$
.
Proof. Let us suppose that there exists a matching
$Q'$
of
$x'$
with
$|Q'|>|P'|$
. By the previous observations, for all
$j,j'\in \{1,\ldots ,S\}$
, with
$j\neq j'$
, there are no edges in
$\mathcal E_{x'}$
incident to
$\{\overline {\mathfrak v}_j, \overline {\mathfrak v}_{j'}\}$
; therefore, any pair
$\{A, B\}\in Q'$
is of the form
$A, B\in x-\bigcup _{j=1}^S\mathfrak v_j$
, or
$A\in x-\bigcup _{j=1}^S\mathfrak v_j$
and
$B\in \{ \overline {\mathfrak v}_j\}_{j=1}^S$
. Let us denote by
$Q_1'$
the set of pairs of
$Q'$
corresponding to the first case, and by
$Q_2'$
the set of pairs corresponding to the second case. We can define a matching
$Q$
of
$\mathcal G_x$
the following way:
-
• Take all pairs in $Q_1'$
. -
• For each pair $\{A,B\}\in Q_2$
, taking
$A= \overline {\mathfrak v}_j$
, for some
$j$
, there exists
$B'\in x\cap \mathfrak v_j$
such that
$\{B, B'\}$
is an incident edge of
$\mathcal G_x$
. Note that by construction
$|\mathfrak v_j|= 2|C(v_j)|-1$
, and there exists
$Y\in y$
such that
$Y\cap X\neq \emptyset $
for all
$X\in \mathfrak v_j$
. Therefore, we can find a perfect matching of
$\{B\}\cup \mathfrak v_j$
as a subgraph of
$\mathcal G_x$
with size
$|C(v_j)|$
. -
• Otherwise, we take all pairs in $C(v_j)$
.
By construction it follows that the cardinal of this matching is
$|Q|=|Q'|+ \sum _{j=1}^S|C(v_j)-1|>|P'|+\sum _{j=1}^S|C(v_j)-1|=|P|$
, this is a contradiction since
$|P|$
is a maximum matching of
$\mathcal G_x$
; therefore,
$|P'|$
must be a maximum matching of
$\mathcal G_{x'}$
.
Claim 6.39. There exists a matching of
$\mathcal G_y$
of cardinality at least
$\left \lceil \frac {S}{2}\right \rceil $
.
Proof. Since
$P'$
is a maximum matching of
$x'$
and
$\{\overline {\mathfrak v}_j\}_{j=1}^S$
enumerates its unmatched vertices, we can define the sets
$U_{x'}, V_{x'}$
and the function
$L_{x'}:\widetilde {\mathcal V}_{x'}\to 2^y$
, and apply Claims 6.36 and 6.37 to them. Note that
$U_{x'}\subset U_x$
.
Let us define the sets
Note that for each
$v\in W_{x'}$
with
$v=\{\overline {\mathfrak v}_j\}$
for some
$j$
, if
$\{Y\}=L_{x'}(v)$
, then
$\overline {\mathfrak v}_j\subset Y$
and
$L_x(v_j)=\{Y\}=L_x(\overline {\mathfrak v}_j)$
. Since
$x_B\nleq y_B$
for all
$B\in x+y$
, we know that
$Y\neq \overline {\mathfrak v}_j$
, and by Claim 6.36.2. we know that there exists
$\{A, B\}=u\in U_{x'}$
such that
$Y\cap (A\cup B)\neq \emptyset $
. Since
$u\in U_{x'}$
, we know that
$u\notin C(v_i)$
, for all
$i\in \{1,\ldots , S\}$
, so
$L_{x'}(u)\neq \{Y\}$
. Therefore, we see that for each
$v\in W_{x'}$
there exists
$u\in U_{x'}$
such that there is an edge
$e$
incident to
$\{u,v\}$
and
$L_{x'}(u)\neq L_{x'}(v)$
. So, we can define a function
$\pi _{x'}: W_{x'}\to U_{x'}$
such that there exists an edge incident to
$\{v, \pi _{x'}(v)\}$
and
$L_{x'}(v)\neq L_{x'}(\pi _{x'}(v))$
.
For each
$v\in Z_{x'}$
, we can define a pair
$\{Y_v^0, Y_v^1\}\subseteq L_{x'}(v)$
, by definition of
$Z_{x'}$
We know that if
$v\neq v'$
, then
$\{Y_v^0, Y_v^1\}\cap \{Y_{v'}^0, Y_{v'}^1\}=\emptyset $
by disjointness of the sets
$C(v_j)$
; therefore, the set
$M_{Z_{x'}}:=\{\{Y_v^0, Y_v^1\}\}_{v\in Z_{x'}}$
is a matching of
$\mathcal G_y$
.
On the other hand, if
$u = \pi _{x'}(v)$
for some
$v\in W_{x'}$
, we can write
$\pi _{x'}^{-1}(u)=\{w_i\}_{i=1}^m$
. Writing
$L_{x'}(w_i)=\{Y_{w_i}\}$
for
$i=1,\ldots , m$
, we know, by Corollary 6.37.2, that there exists
$X\in u\subset x$
such that for all
$i\in \{1,\ldots , m\}, X\cap Y_{w_i}\neq \emptyset $
. By disjointness of the sets
$C(v_j)$
, we have that
$i\neq i'$
implies
$Y_{w_i}\neq Y_{w_{i'}}$
and by the construction of
$\pi _{x'}$
and Corollary 6.37.1 that
$L_{x'}(u)\not \subset \bigcup _{i=1}^m L_{x'}(w_i)$
. Therefore, we can define a matching of
$\mathcal G_y$
,
$M_u:=\{\{Y_{u,j}^0, Y_{u,j}^1\}\}_{j=1}^{\lceil m/2\rceil }$
where
$Y_{u,j}^i:= Y_{w_{2j-i}}$
for
$i=0,1$
and
$j=1,\ldots ,\lfloor m/2\rfloor $
and, if
$m$
is odd,
$Y_{u,\lceil m/2\rceil }^0:= Y_{w_m}$
and
$Y_{u,\lceil m/2\rceil }^1\in L_{x'}(u)-\{Y_{w_i}\}_{i=1}^m$
.
By disjointness of the sets
$C(v_j)$
, we also know that for all distinct
$u,u'$
in the image of
$\pi _{x'}$
the respective sets of matched vertices in
$M_u$
and
$M_{u'}$
are pairwise disjoint (if
$\{A,B\}\in M_u$
and
$\{B,C\}\in M_{u'}$
, then
$\{A,B\}\cap \{C,D\}=\emptyset $
) and pairwise disjoint from the matched vertices in
$M_{Z_{x'}}$
; thus, these matchings may be combined to form a matching
$M= M_{Z_{x'}}\cup (\bigcup _{u\in Im(\pi _{x'})} M_u)$
of
$\mathcal G_y$
. We now calculate
which establishes the claim.
Now, besides the maximum matching of
$\mathcal G_x$
previously fixed, we fix a maximum matching
$\{\{ A_i', B_i'\}\}_{i=1}^M$
of the vertices of
$\mathcal G_y$
and let
$\{\{C_j'\}\}_{j=1}^ R$
enumerate the unmatched vertices. Using the maximum matching of
$\mathcal G_x$
we define a singular partition
$z^*\in \Gamma (x)$
with main block
$B_{z^*}:=\{a_i,b_i\}_{i=1}^N\cup \{c_j\}_{j=1}^S$
where
$a_i\in A_i, b_i\in B_i$
, and
$\{a_i, b_i\}\subseteq Y\in y$
for
$i=1,\ldots , N$
and
$c_j\in C_j$
for
$j=1,\ldots , S$
. Similarly, we can define a singular partition
$w_*\in \Gamma (y)$
using the maximum matching of
$\mathcal G_y$
. It is clear by its construction that
$\max _{w\in \Gamma (y)}|B_{z^*} \cap B_w|\leq N+S$
and
$\max _{z\in \Gamma (x)}|B_z\cap B_{w^*}|\leq M+R$
; therefore,
Since
$\#x=2N+S$
and
$\#y=2M+R$
, we note that
To finish the proof, observe that by Claim 6.39 we know that
$S\leq 2M$
. Thus, we get
$R+S\leq R+ 2M\leq \#y+\#(x+y)$
and conclude that
6.4 Connections with continuous partition lattices
Björner and Lovász [Reference Björner and Lovász12] introduced an inductive limit-type construction on the class of pseudomodular lattices in order to produce examples of continuous limits of lattices. We refer the reader to [Reference Björner10] for a broad survey of this topic. In [Reference Björner9] Björner constructed in this fashion a continuous limit of partition lattice which we will denote by
$\Pi _\infty $
. This was realized as a sublattice of a lattice of measurable partitions in subsequent work of Haiman [Reference Haiman24].
We now describe the construction of
$\Pi _\infty $
. We will use
$\Pi _n$
to denote the finite partition lattice of the set
$\{0,1,\ldots ,n\}$
. As metric lattices
$\Pi _n$
and
$P_{n+1}$
are isomorphic. If
$kn=m$
, then a lattice homomorphism
is defined as follows. For a partition
$\pi =\{B_0,\dotsc ,B_p\}\in \Pi _n$
such that
$0\in B_0$
,
$\phi _n^m(\pi ):=\{C_0\}\cup \{C_{ij}\}_{1\leq i\leq p, 0\leq j\leq k-1}$
where
$C_{ij}:=\{kb-j|b\in B_i\}$
and
$C_0:=\{0,1,\dotsc ,m\}-\bigcup _{i,j} C_{ij}$
.
We then define
$\Pi _{(\infty )}$
as the direct limit of
$(\Pi _{k}, \phi _1^k)$
, which is a lattice with a rank function
$|\cdot |:\Pi _{(\infty )}\rightarrow [0,1]$
that only takes rational values. We then define
$\Pi _\infty $
as the metric completion of
$\Pi _{(\infty )}$
and note that
$\Pi _{(\infty )}$
is a sublattice of
$\Pi _\infty $
. Observe that for each
$k$
the construction induces a lattice embedding
$\phi _{k}:\Pi _k\rightarrow \Pi _{\infty }$
.
Question 6.40. Is
$\Pi _\infty $
a model of
$T_{FPL}$
?
We do not have a clear answer to the question. On the level of naive analogy,
$\Pi _\infty $
ought to be the right object in the category of “continuous partition lattices” corresponding to the hyperfinite II
$_1$
factor in the theory of tracial von Neumann algebras. It is known that the hyperfinite II
$_1$
factor is not pseudomatricial among tracial von Neumann algebras as pseudomatricial von Neumann algebras do not satisfy “property
$\Gamma $
” in contrast to the hyperfinite II
$_1$
factor [Reference Farah17]. We develop this analogy further below. For the meantime, we note that it would suffice to show that for every
$\mathfrak L$
-formula
$\psi (\bar x)$
we would have that
$\sup _{\bar a_n}|\psi ^{\Pi _\infty }(\phi _n(\bar a_n)) - \psi ^{\Pi _n}(\bar a_n)|\to 0$
as
$n\to \infty $
where
$\bar a_n$
ranges over all tuples in
$\Pi _n$
. This would be trivially satisfied if all embeddings
$\phi _n: \Pi _k\to \Pi _\infty $
are elementary. However, this is not the case.
Remark 6.41. For all positive integers
$n,k>1, \phi _n^{kn}(\Pi _n)$
is not an elementary substructure of
$\Pi _{kn}$
. Moreover, no
$\phi _n: \Pi _n\to \Pi _\infty $
is an elementary embedding.
Proof. Let’s consider the formula
$\psi (x)=\sup _y\varphi (x,y)$
where
$\varphi (x,y)$
is as in equation line (5.3). Picking a modular element
$a\in \Pi _n, a\neq 0$
, it is clear that
$\psi ^{\Pi _n}(a)=0$
. By Corollary 6.6 we know that
$a$
is a singular partition, so there is a main block
$A$
with cardinality at least
$2$
. By the definition of
$\phi _n^{kn}$
we know that
$\{A_j\}_{0\leq \leq k-1}\subset \phi _n^{kn}(a)$
where
$A_j=\{kb-j|b\in A\}$
. Since
$\phi _n^{kn}(a)$
has
$k$
blocks of cardinal
$\geq 2$
, it is not a singular partition; thus, by Corollary 6.6 we conclude that
$\psi ^{\Pi _{kn}}(\phi _n^{kn}(a))\neq 0$
.
Despite knowing that the embeddings are not elementary, we can still ask whether the embeddings allow us to approximate formulas of
$T_{FPL}$
uniformly. In other we are asking if for every
$\epsilon>0$
there exists
$N\in \mathbb N$
such that for all
$n\geq N$
, all
$\mathfrak L$
-formula
$\psi (\bar {x})$
, and all
$\bar {a}\in \Pi _n, |\psi ^{\Pi _n}(\bar {a})-\psi ^{P_{Bjorn}}(\varphi _n(\bar {a}))|<\epsilon $
.
The answer turns out to still be no. Let us pick
$\epsilon =\frac {1}{3}$
, for each
$n\in \mathbb N$
we can define the
$\mathfrak L$
-formula with
$n$
free variables,
$\psi _n(x_1,\ldots , x_n):=\sup _y\min \{d(x_1,y),\ldots ,d(x_n,y)\} $
. It is clear that for all
$n\in \mathbb N$
, if we denote
$|\Pi _n|=N$
and
$\Pi _n=\{a_i\}_{i=1}^N$
, then
$(\psi _N(a_1,\ldots , a_N))^{\Pi _n}=0$
. However, in
$\Pi _{2n}$
we can define the partition
$z:=\{\{0\}\}\cup \{\{2i-1, 2i\}\}_{i=1}^n$
. Note that for any partition
$x=\{B_0,\ldots , B_p\}\in \Pi _n$
we know that
$\varphi _n^{2n}(x)=\{C_0\}\cup \{C_{ij}\}_{1\leq i\leq p, j=1,0}$
where
$C_{ij}=\{2b-j|b\in B_i\}$
and
$C_0=\{0,1,\ldots , 2n\}-\bigcup _{i,j} C_{ij}$
, so for each
$m\in \{1,\ldots , n\}$
if
$m\in B_i\in x$
for some
$i\in \{1,\ldots ,p\}$
, then
$2m\in C_{i0}$
and
$2m-1\in C_{i1}$
. This implies that for all
$x\in \Pi _n, \varphi _n^{2n}(x)+z=\{C_0\}\cup \{C_{i0}\cup C_{i1}\}_{i=1}^p$
, and that
$\#(\varphi _n^{2n}(x)+z)=\#x$
. Now, if we compute the distance of
$\varphi _n^{2n}(x)$
and
$z$
, we get that
for all
$x\in \Pi _n$
. Therefore,
$\min \{d(\varphi _n^{2n}(a_1), z),\ldots , d(\varphi _n^{2n}(a_N), z)\}=\frac {1}{2}$
and it follows that
$\psi _N^{\Pi _\infty }(\varphi _n(a_1,\ldots , a_N))\geq \psi _N^{\Pi _{2n}}(\varphi _n^{2n}(a_1,\ldots , a_N))\geq \frac {1}{2}>0=\psi _N^{\Pi _n}(a_1,\ldots ,a_N)$
. We have proved that for all
$n\in \mathbb N$
there exists a formula
$\psi _{|\Pi _n|}(x_1,\ldots , x_{|\Pi _n|})$
and elements
$a_1,\ldots , a_{|\Pi _n|}\in \Pi _n$
such that
$|\psi _{|\Pi _n|}^{\Pi _n}(\bar {a})-\psi _{|\Pi _n|}^{\Pi _\infty }(\varphi _n(\bar {a}))|=\psi _{|\Pi _n|}^{\Pi _\infty }(\varphi _n(\bar {a}))-\psi _{|\Pi _n|}^{\Pi _n}(\bar {a})>\epsilon =\frac {1}{3}$
, so there is no uniform elementary approximation of the
$\mathfrak L$
-formulas through the embeddings.
Remark 6.42. One can, in fact, control the behavior for a restricted set of formulas. We say that an
$L$
-formula is in prenex form if it is of the form
$Q_{x_1}^1Q_{x_2}^2\dotsb Q_{x_n}^n\psi (\bar x, \bar y)$
where
$\psi $
is a quantifier-free formula and each
$Q_i$
is either
$\sup $
or
$\inf $
. Every formula is equivalent to one in prenex form. We call a prenex formula
$Q_{x_1}^1Q_{x_2}^2\dotsb Q_{x_n}^n\psi (\bar x, \bar y) \forall \exists $
if there is
$1\leq i \leq n$
so that
$Q_j = \sup $
for all
$j\leq i$
and
$Q_j = \inf $
for all
$j> i$
. It is a well-known fact that models of an
$\forall \exists $
-sentence are closed under inductive limits [Reference Chang and Keisler13, Theorem 3.2.3], hence we have the following proposition.
Proposition 6.43. If
$\sigma \in T_{FPL}$
is an
$\forall \exists $
sentence, then
$\Pi _\infty \models \sigma $
.
A natural question at this point is whether every formula in
$T_{FPL}$
is equivalent to an
$\forall \exists $
formula. Again, the answer is not totally clear. An interesting test case would be the sentence
$\inf _x\sup _y\varphi (x,y)\in T_{FPL}$
. This sentence is also true in
$\Pi _\infty $
by the results of Björner [Reference Björner9].
Perhaps the most fundamental open question is the following.
Question 6.44. How many models of
$T_{FPL}$
exist, up to isomorphism, of density character
$\aleph _0$
?
In an attempt to answer this question, one can try to formulate invariants which could be shown to hold for certain constructions.
Definition 6.45. Let
$\mathcal L$
be a metric lattice. We say that a net
$(a_n)$
in
$L$
is almost modular if
$\varphi (x,a_n)\to 0$
for all
$x\in L$
, where
$\varphi $
is as in equation line (5.3). We say that an almost modular net
$(a_n)$
is trivial if there exists a net of modular elements
$(b_n)$
in
$L$
so that
$d(a_n,b_n)\to 0$
. We say that a metric lattice has property
$\Gamma $
if there exists a non-trivial almost modular net.
The terminology “property
$\Gamma $
” is inspired by the theory of von Neumann algebras, specifically from the seminal work of Murray and von Neumann [Reference Murray and von Neumann39], where it is defined as the algebra having an almost central sequence which is bounded away from sequences of central elements. We do not claim any formal connection between the two.
Question 6.46. Does
$\Pi _\infty $
have property
$\Gamma $
?
Question 6.47. Do all models of
$T_{FPL}$
have property
$\Gamma $
?
Proposition 6.48. The following are equivalent:
-
(1) No model of $T_{FPL}$
has property
$\Gamma $
. -
(2) For every $\epsilon>0$
there exists
$k\in \mathbb N$
and
$\delta>0$
so that for all
$P_n$
, a finite partition lattice, there exists
$x_1,\dotsc , x_k$
in
$P_n$
so that
$\sum _{i=1}^k \varphi (x_i,y) < \delta $
implies that
$d(y,\Sigma _n)<\epsilon $
.
Proof. The proof of “(2) implies (1)” is straightforward.
For the proof of “(1) implies (2),” suppose that the second statement is false. That is, there is some
$\epsilon>0$
so that for all
$k,l\in \mathbb N$
we have that there is
$n_{l,k}\in \mathbb N$
so that for any choice of
$x_1,\dotsc ,x_k\in P_{n_{l,k}}$
there is
$y\in P_{n_{k,l}}$
with
$d(y,\Sigma _{n_{l,k}})\geq \epsilon $
and
$\sum _{i=1}^k\varphi (y,x_i)\leq \frac {1}{l}\epsilon $
. Specifically, for all
$k\in \mathbb N$
, there is
$n_k:=n_{k,k}\in \mathbb N$
such that for any choice of
$x_1,\dotsc ,x_k\in P_{n_k}$
there is
$y\in P_{n_k}$
with
$d(y,\Sigma _{n_k})\geq \epsilon $
and
$\sum _{i=1}^k\varphi (y,x_i)\leq \frac {1}{k}\epsilon $
. Fix a non-principal ultrafilter
$\mathcal U$
on
$\mathbb N$
, and consider the ultraproduct lattice
$\mathcal P = \prod _{k\in \mathbb N} P_{n_k}/\mathcal U$
. For any finite subset
$F = \{x_1,\dotsc ,x_l\}$
of
$\mathcal P$
choose representing sequences
$x_i = (x_{k,i})_{k\in \mathbb N}$
, and for each
$k\in \mathbb N, k\geq l$
we can pick
$y_{k,F}\in P_{n_k}$
such that
$d(y_{k,F},\Sigma _{n_k})\geq \epsilon $
and
$\sum _{i=1}^l\varphi (y_{k,F},x_{k,i})\leq \sum _{i=1}^l\varphi (y_{k,F},x_{k,i})+ (k-l)\varphi (y_{k,F},x_{k,l})\leq \frac {1}{k}\epsilon \leq \frac {1}{|F|}\epsilon $
, without loss of generality we can pick arbitrary elements of
$P_{n_k}$
to define
$y_{F,k}$
for each
$k< l$
. Setting
$y_F$
to be the class of
$(y_{k,F})$
in
$\mathcal P$
, we have that
$d(y_F, \Sigma _{\mathcal P})=d(y_F, \Pi _{k\in n} \Sigma _{n_k}/\mathcal U)=\lim _{k,\mathcal U}d(y_{k,F},\Sigma _{n_k})\geq \epsilon $
and
$\Sigma _{i=1}^l\varphi (y_F, x_i)=\lim _{k,\mathcal U} \sum _{i=1}^l\varphi (y_{k,F},x_{k,i})\leq \frac {1}{|F|}\epsilon $
. Therefore,
$(y_F)$
is a non-trivial almost modular net.
By Proposition 6.48 an affirmative answer to the following question would imply that no model of
$T_{FPL}$
has property
$\Gamma $
.
Question 6.49. Do there exist constants
$C,K$
so that for all
$P_n$
, a finite partition lattice, there exists
$x_1,\dotsc , x_K$
in
$P_n$
so that
$d(y,\Sigma _n)\leq C\sum _{i=1}^K \varphi (x_i,y)$
?
Although this seems like a very strong property, there are analogs of equally unexpected and strong “spectral gap” type properties for matrix algebras (see, for instance, [Reference Mulcahy and Sinclair38, Reference von Neumann41]). On the other hand, it is unknown whether there is a uniform spectral gap estimate over all non-
$\Gamma $
II
$_1$
factors, nor is it known whether the non-
$\Gamma $
II
$_1$
factors form an axiomatizable class [Reference Farah17].
It would be nice to have a simple description of the class of all pseudofinite partition lattices.
Question 6.50. Suppose that
$\mathcal L$
is a complete metric lattice with the following properties:
-
(1) The set of metrically modular elements is a Boolean lattice.
-
(2) For every $x\in L$
the set
$\Gamma (x)$
of all modular complements of
$x$
is nonempty. -
(3) For all $x,y\in L,$
$$\begin{align*}\frac{1}{4}d(x,y) \leq d_{Haus}(\Gamma(x),\Gamma(y))\leq d(x,y).\end{align*}$$
Does
$\mathcal L \models T_{FPL}$
?
The properties of the selector sets of partition lattices suggest a possible framework for a “Boolean” theory of limits of metric lattices or submodular functions in general, shedding light on a question of Lovász [Reference Lovász34, Problem 8.9]. Let
$\mathfrak B = (\mathcal B, \cup , \cap , \cdot ^c, d)$
be a complete metric Boolean lattice. For nonempty closed subsets
$P,Q$
of
$\mathcal B$
, we write
We consider a collection
$\Gamma $
of nonempty closed subsets of
$\mathcal B$
with the following properties:
-
(1) $\{0\}, \{1\}\in \Gamma $
. -
(2) For each $P\in \Gamma $
,
$|x| = |y|$
for all
$x,y\in P$
, we let
$||P||:=|x|$
for any
$x\in P$
. -
(3) For all $P,Q\in \Gamma , \{S\in \Gamma : S\subset P\cap Q\}\neq \emptyset $
and there is a unique
$R\in \Gamma $
with
$R\subseteq P\cap Q$
and
$||R||=\max \{||S||: S\in \Gamma \wedge S\subseteq P\cap Q\}$
. We write
$R = P\otimes Q$
. -
(4) $\Gamma $
is closed in the Hausdorff metric.
We observe that
$(\Gamma , \otimes )$
is a meet semilattice with
$\{0\}$
and
$\{1\}$
being the minimal and maximal elements, respectively. Note that for the induced ordering, we have that
$Q\leq P$
if and only if for every
$x\in Q$
there is
$y\in P$
so that
$x\leq y$
. For
$P, Q\in \Gamma $
let
$\rho (P,Q) : = \|P\| + \|Q\| - 2\|P\otimes Q\|$
.
Proposition 6.51. We have that
$(\Gamma , \otimes , \rho )$
is a complete metric semilattice.
Proof. It is straightforward to see that
$\Gamma $
is metrically complete follows from
$\Gamma $
being closed in the Hausdorff metric. Let
$P,Q,R\in \Gamma $
with
$R\leq P$
and
$x\in P, y\in Q, z\in R$
. We have that
whenever
$x\geq z$
. As this can always be arranged by assumption, it follows that
The result now follows by an adaptation of the proof of Proposition 3.24 to meet semilattices.
Remark 6.52. Let
$\mathcal P$
be an infinite pseudofinite partition lattice. Due to our previous work in Section 6.3, we believe it should be the case that the set
$\Gamma :=\{\Gamma (x) : x\in \mathcal P\}$
satisfies the above properties with respect to the Boolean algebra of modular elements of
$\mathcal P$
. Indeed, it can be checked that
$\{0\}=\Gamma (1), \{1\}=\Gamma (0)$
so (1) is satisfied, also (2) follows from Lemma 6.19 and (4) from Proposition 6.35. Given the length of the proof, we have decided to omit the details for the satisfaction of (3), but we mention some key points. Note that by the techniques used in the proof of Proposition 6.30 it follows that
$\Gamma (x+y) \subseteq \Gamma (x)\cap \Gamma (y)$
and
$1-|x+y|=||\Gamma (x+y)||=\max \{||\Gamma (z)||: \Gamma (z)\subseteq \Gamma (x)\cap \Gamma (y)\}$
for all finite partition lattices. From here, using the theory of selectors and the definability of the meet in the context we can prove that (3) is satisfied by
$\mathcal P$
, and thus
$\Gamma (x)\otimes \Gamma (y) = \Gamma (x+y)$
for all
$x,y\in P$
.
If given a metric lattice
$\mathcal L$
, we define the opposite lattice
$\overline {\mathcal L}$
by
$\bar x + \bar y = \overline {xy}$
,
$\bar x\cdot \bar y = \overline {x+y}$
, and
$d(\bar x, \bar y) = d(x,y)$
for all
$x,y\in L$
, we have that
$\overline {\mathcal L}$
is a meet metric semilattice. In this way
$\overline {\Gamma }$
is isometrically isomorphic to
$\mathcal P$
.
Question 6.53. Is every complete metric semilattice isometrically isomorphic to one of this form?
7 Further directions and questions
In their seminal work on continuous limits of lattices, Björner and Lovász [Reference Björner and Lovász12] isolate the following property as an essential ingredient for their constructions, which they call pseudomodularity. We will call a metric lattice
$\mathcal L$
pseudomodular if for all
$x,y\in L$
the set
$P_{xy} :=\{z\leq y : d(x+z,z) = d(x+y,y)\}$
has a unique least element.
Question 7.1. Do the pseudomodular complete metric lattices form an elementary class?
The following definition is inspired by the work of Krivine and Maurey [Reference Krivine and Maurey31].
Definition 7.2. We say that a metric lattice
$\mathcal L$
is stable if
for all sequences
$(x_i)$
and
$(y_j)$
in
$L$
for which both limits exist.
Question 7.3. Is there some “combinatorial” description of stable metric lattices?
Stability of geometric lattices in the context of classical model theory has been studied in [Reference Hyttinen and Paolini29].
Let
$G = (V,E)$
be a simple, undirected finite graph which is connected. We can associate to
$G$
a subsemilattice
$L(G)$
of
$P_n$
, where
$|V| = n$
, consisting of the set of all partitions of
$V$
whose blocks are the connected components of the subgraph induced by some
$E'\subseteq E$
. This turns out to be isomorphic to the lattice of flats of the graphical matroid associated with
$G$
. We note that
$L(K_n) = P_n$
, where
$K_n$
is the complete graph on
$n$
vertices.
Question 7.4. For which families of finite graphs, do the lattices
$L(G)$
form a Fraïssé class of metric structures as in [Reference Ben Yaacov3, Reference Vignati52]?
Such a class ought to have a canonical “hyperfinite” limiting object.
The next question turns to connections between our theory and the limiting theories of combinatorial structures using sampling densities as developed in [Reference Kardoš, Král, Liebenau and Mach30, Reference Lovász33, Reference Nesetril and de Mendez40, Reference Razborov46]. If
$\mathcal L$
is a geometric lattice with
$n$
atoms
$A_{\mathcal L}$
and
$\mathcal H$
is a fixed geometric lattice with
$k$
atoms, we write
Here
$\mathcal L_S$
denotes the sublattice of
$\mathcal L$
generated by
$S$
.
Question 7.5. For what
$\mathcal H$
does
$t(\mathcal H, \bullet )$
extend to a sentence in the theory of metric lattices?
As a first step towards answering this, one must consider the following.
Question 7.6. If
$(\mathcal L_n)$
and
$(\mathcal M_n)$
are sequences of geometric lattices (with appropriately normalized rank functions) and
$\mathcal U$
is an ultrafilter so that
$\prod _{\mathcal U} \mathcal L_n\cong \prod _{\mathcal U} \mathcal M_n$
isometrically isomorphically as metric lattices, does it hold that
$\lim _{\mathcal U} t(\mathcal H, \mathcal L_n) = \lim _{\mathcal U} t(\mathcal H, \mathcal M_n)$
?
We denote by
$NC_n$
the lattice of noncrossing partitions with respect to the usual cyclic order on
$\{1,\dotsc ,n\}$
. Note that
$NC_n$
is not a sublattice of the finite partition lattice
$P_n$
: The meets are the same, but the joins are different. The lattice of noncrossing partitions has a rich combinatorial structure in its own right (see [Reference Nica and Speicher43, Lecture 9] or [Reference Simion50]. For instance, noncrossing partition lattices are self-dual, while partition lattices are not. However, the rank function on
$NC_n$
inherited from
$P_n$
is not submodular for
$n\geq 4$
[Reference Simion50, p. 370]. Moreover, there is a canonical order-reversing lattice anti-isomomorphism
$\kappa _n: NC_n\to NC_n$
called the Kreweras complement. This poses a serious obstacle to realizing
$NC_n$
as a metric lattice for which the metric is compatible with
$\kappa _n$
, as the order-reversing property together with submodularity ought to give modularity.
Question 7.7. Is there a good continuous limiting theory of noncrossing partition lattices?
A satisfactory answer to this question likely would have connections with free probability theory [Reference Nica and Speicher43].
Finally, there are “weak order” structures on finite permutation groups [Reference Yanagimoto and Okamoto55], and finite Coxeter groups more generally [Reference Björner and Brenti11], which endow these groups with a lattice structures. While these lattice structures need not be geometric, since not all maximal chains need have the same length, they possess a strong property called semidistributivity:
Question 7.8. Is there a metric theory of semidistributive lattices?
Acknowledgments
The authors thank David Jekel for helpful comments on any earlier version of this manuscript and the anonymous referee for many suggestions which improved the exposition. The authors are grateful to the Colombia–Purdue Partnership and Andrés Villaveces for facilitating and supporting their collaboration.
Funding
The authors were supported by NSF Grant DMS-2055155.
Open access
