# Convexity, Duality and Effects

Bart Jacobs

► To cite this version:

Bart Jacobs. Convexity, Duality and Effects. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. pp.1-19, 10.1007/978-3-642-15240-5_1 . hal-01054454

HAL Id: hal-01054454

https://inria.hal.science/hal-01054454

Submitted on 6 Aug 2014

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Convexity, Duality and Effects

Bart Jacobs,

Institute for Computing and Information Sciences (iCIS),
Radboud University Nijmegen, The Netherlands.

Webaddress: www.cs.ru.nl/B.Jacobs

May 22, 2010

## Abstract

This paper describes some basic relationships between mathematical structures that are relevant in quantum logic and probability, namely convex sets, effect algebras, and a new class of functors that we call ‘convex functors’; they include what are usually called probability distribution functors. These relationships take the form of three adjunctions. Two of these three are ‘dual’ adjunctions for convex sets, one time with the Boolean truth values {0, 1} as dualising object, and one time with the probability values [0, 1]. The third adjunction is between effect algebras and convex functors.

## 1 Introduction

A set $X$ is commonly called convex if for each pair of elements $x, y \in X$ and each number $r \in [0, 1]$ in the unit interval of real numbers the ‘convex’ sum $rx + (1-r)y$ is again in $X$. Informally this says that a whole line segment is contained in $X$ as soon as the endpoints are in $X$. Convexity is of course a well-established notion that finds applications in for instance geometry, probability theory, optimisation, economics and quantum mechanics (with mixed states as convex combinations of pure states). The definition of convexity (as just given) assumes a monoidal structure $+$ on the set $X$ and also a scalar multiplication $[0, 1] \times X \to X$. People have tried to capture this notion of convexity with fewer assumptions, see for instance [25], [27] or [12]. We shall use the latter source that involves a ternary operation $\langle -, -, -$rangle: $[0, 1] \times X \times X \to X$ satisfying a couple of equations, see Definition 3. We first recall (see e.g. [28, 8, 20, 6, 11]) that such convex structures can equivalently be described uniformly as algebras of a monad, namely of the distribution monad $\mathcal{D}$, see Theorem 4. Such an algebra map gives an interpretation of each formal convex combination $r_1x_1 + \cdots + r_nx_n$, where $r_1 + \cdots + r_n = 1$, as a single element of $X$. This algebraic formulation of convexity yields a description of a familiar embedding construction as an adjunction between convex sets and modules, see Proposition 2 below.
The main part of this paper concerns duality for convex spaces. We shall describe two dual adjunctions:

$$ \mathbf{PreFrm} \underset{\operatorname{Hom}(-, \{0,1\})}{\overset{\operatorname{Hom}(-, \{0,1\})}{\rightleftarrows}} \mathbf{Conv}^{\mathrm{op}} \underset{\operatorname{Hom}(-, [0,1])}{\overset{\operatorname{Hom}(-,[0,1])}{\rightleftarrows}} \mathbf{EA} \quad (1) $$

namely in Theorems 9 and 17. This diagram involves the following structures.

* The category **Conv** of convex sets, with as special objects the two element set $2 = \{0, 1\}$ of Booleans and the unit interval $[0, 1]$ of probabilities— where $[0, 1] \cong \mathcal{D}(2)$.

* The category **PreFrm** of preframes: posets with directed joins and finite meets, distributing over these joins, see [19]. These preframes are slightly more general than frames (or complete Heyting algebras) that occur in the familiar duality with topological spaces, see [18].

* The category **EA** of effect algebras (from [9], see also [7] for an overview): effect algebras have arisen in the foundations of quantum mechanics and are used to capture quantum effects, as studied in quantum statistics and quantum measurement theory, see e.g. [4].

The diagram (1) thus suggests that convex sets form a setting in which one can study both Boolean and probabilistic logics. It opens up new questions, like: can the adjunctions be refined further so that one actually obtains equivalences, like between Stone spaces and Boolean algebras or between compact Hausdorff spaces and commutative $C^*$-algebras (see [18] for an overview). This is left to future work. Dualities are important in algebra, topology and logic, for transferring results and techniques from one domain to another. They are used in the semantics of computation (see e.g. [1, 29]), but are relatively new in a quantum setting. They may become part of what is called in [2] an “extensive network of interlocking analogies between physics, topology, logic and computer science”.

In addition to the adjunctions in (1) another adjunction involving effect algebras is presented, namely a coreflection:

$$ \mathbf{EA} \underset{F \to F(2)}{\overset{\mathcal{D}}{\rightleftarrows}} \mathbf{Conv}(\mathbf{Sets}) \quad (2) $$

between effect algebras and what we call convex endofunctors. These functors capture the essentials of the probability distribution functor (or monad), which is generalised here from taking probability values in $[0, 1]$ to taking values in an arbitrary effect algebra. We expect that the adjunction (2) can be used to build a “triangle of adjunctions” in the style of [5], relating scalars (or probabilities), convex monads, and Lawvere theories with partially additive structure.
The paper starts with a section on multiset and distribution monads over semirings, including an adjunction between their categories of algebras. Section 3 recalls in Theorem 4 how (real) convex sets can be described as algebras of the distribution monad. Subsequently, Section 4 describes the adjunction on the left in (1) between convex sets and preframes, via prime filters in convex sets and Scott-open filters in preframes. Both can be described via homomorphisms to the dualising object {0, 1}. The adjunction on the right in (1) requires that we first sketch the basics of effect algebras. This is done in Section 5. The unit interval [0, 1] now serves as dualising object, where we note that effect algebra maps $E \to [0, 1]$ are commonly studied as states or measures in a quantum system. The paper concludes in Section 7 with the adjunction (2) between effect algebras and convex functors.

## 2 Multiset and distribution monads

This section describes the multiset monad $\mathcal{M}_S$, for a semiring $S$, and the distribution monad $\mathcal{D}$. The main result is an adjunction, in Proposition 2, between their categories of algebras. It is assumed that the reader is familiar with the basics of the theory of monads and their algebras. More information may be found in for instance [24, 3, 23].

Let $S$ be a semiring, consisting of a commutative additive monoid $(S, +, 0)$ and a multiplicative monoid $(S, \cdot, 1)$, where multiplication distributes over addition. One can define a “multiset” functor $\mathcal{M}_S: \text{Sets} \to \text{Sets}$ by:

$$ \mathcal{M}_S(X) = \{\varphi: X \to S \mid \text{supp}(\varphi) \text{ is finite}\}, $$

where $\text{supp}(\varphi) = \{x \in X \mid \varphi(x) \neq 0\}$ is the support of $\varphi$. For a function $f: X \to Y$ one defines $\mathcal{M}_S(f): \mathcal{M}_S(X) \to \mathcal{M}_S(Y)$ by:

$$ \mathcal{M}_S(f)(\varphi)(y) = \sum_{x \in f^{-1}(y)} \varphi(x). \qquad (3) $$

Such a multiset $\varphi \in \mathcal{M}_S(X)$ may be written as formal sum $s_1x_1 + \cdots + s_kx_k$ where $\text{supp}(\varphi) = \{x_1, \ldots, x_k\}$ and $s_i = \varphi(x_i) \in S$ describes the “multiplicity” of the element $x_i$. This formal sum notation might suggest an order $1, 2, \ldots, k$ among the summands, but this sum is considered, up-to-permutation of the summands. Also, the same element $x \in X$ may be counted multiple times, but $s_1x + s_2x$ is considered to be the same as $(s_1 + s_2)x$ within such expressions. With this formal sum notation one can write the application of $\mathcal{M}_S$ on a map $f$ as $\mathcal{M}_S(f)(\sum_i s_i x_i) = \sum_i s_i f(x_i)$.

This multiset functor is a monad, whose unit $\eta: X \to \mathcal{M}_S(X)$ is $\eta(x) = 1x$, and multiplication $\mu: \mathcal{M}_S(\mathcal{M}_S(X)) \to \mathcal{M}_S(X)$ is $\mu(\sum_i s_i \varphi_i)(x) = \sum_i s_i \cdot \varphi_i(x)$.

For the semiring $S = \mathbb{N}$ one gets the free commutative monoid $\mathcal{M}_{\mathbb{N}}(X)$ on a set $X$. And if $S = \mathbb{Z}$ one obtains the free Abelian group $\mathcal{M}_{\mathbb{Z}}(X)$ on $X$. The Boolean semiring $2 = \{0, 1\}$ yields the finite powerset monad $\mathcal{P}_{\text{fin}} = \mathcal{M}_2$.

An (Eilenberg-Moore) algebra $\alpha: \mathcal{M}_S(X) \to X$ for the multiset monad corresponds to a monoid structure on $X$—given by $x + y = \alpha(1x + 1y)$—together
with a scalar multiplication $\bullet$: $S \times X \to X$ given by $s \bullet x = \alpha(sx)$. It preserves the additive structure (of $S$ and of $X$) in each coordinate separately. This makes $X$ a module, for the semiring $S$. Conversely, such an $S$-module structure on a commutative monoid $M$ yields an algebra $M_S(M) \to M$ by $\sum_i s_i x_i \mapsto \sum_i s_i \bullet x_i$. Thus the category of algebras $Alg(M_S)$ is equivalent to the category $\text{Mod}_S$ of $S$-modules.

Analogously one defines the distribution monad $\mathcal{D}$ as:

$$ \mathcal{D}(X) = \{\varphi: X \to [0, 1] \mid \text{supp}(\varphi) \text{ is finite and } \sum_{x \in X} \varphi(x) = 1\}. \quad (4) $$

Elements of $\mathcal{D}(X)$ are convex combinations $s_1x_1 + \dots + s_kx_k$, where the probabilities $s_i \in [0, 1]$ satisfy $\sum_i s_i = 1$. In Section 7 we shall see how one can generalise the set of probabilities from the unit interval $[0, 1]$ to an arbitrary effect algebra. Unit and multiplication making $\mathcal{D}$ a monad can be defined as for $M_S$. This multiplication is well-defined since:

$$ \sum_x \mu(\sum_i s_i \varphi_i)(x) = \sum_x \sum_i s_i \cdot \varphi_i(x) = \sum_i s_i \cdot (\sum_x \varphi_i(x)) = \sum_i s_i = 1. $$

The inclusion maps $\mathcal{D}(X) \hookrightarrow M_{\mathbb{R}_{\ge 0}}(X)$, sending distributions to multisets over the non-negative real numbers $\mathbb{R}_{\ge 0}$, are natural and commute with the units and multiplications of the two monads, and thus form an example of a "map of monads".

We continue this section with a basic results, which is stated without proof, but with a few subsequent pointers.

**Theorem 1** For a monad $T$ on Sets, the category $Alg(T)$ of algebras is:

1. both complete and cocomplete, so has all limits and colimits;

2. symmetric monoidal closed in case the monad $T$ is "commutative". $\square$

A category of algebras is always "as complete" as its underlying category, see e.g. [23, 3]. Since **Sets** is complete, so is $Alg(T)$. Cocompleteness is special for algebras over **Sets** and follows from a result of Linton's, see [3, § 9.3, Prop. 4].

Monoidal structure in categories of algebras goes back to [22, 21]. Each monad on **Sets** is strong, via a "strength" map $\text{st}: X \times T(Y) \to T(X \times Y)$ given as $\text{st}(x, v) = T(\lambda y. (x, y))(v)$. There is also a swapped version $\text{st}': T(X) \times Y \to T(X \times Y)$ given by $\text{st}'(u, y) = T(\lambda x. (x, y))(u)$. The monad $T$ is called commutative if the two resulting maps $T(X) \times T(Y) \to T(X \times Y)$, obtained by either doing first $\text{st}$ and $\text{st}'$ or first $\text{st}'$ and then $\text{st}$, are equal.

The multiset monad $M_S$ is commutative if $S$ is a (multiplicatively) commutative semiring. The distribution monad $\mathcal{D}$ is always commutative.

The next construction goes back to [27] and occurs in many places (see e.g. [26, 20]) but is usually not formulated in the following way. It can be understood as a representation theorem turning a convex set into a module over the nonnegative reals.

**Proposition 2** The functor $\text{Mod}_{\mathbb{R}_{\ge 0}} = \text{Alg}(M_{\mathbb{R}_{\ge 0}}) \xrightarrow{U} \text{Alg}(\mathcal{D})$, induced by the map of monads $\mathcal{D} \Rightarrow M_{\mathbb{R}_{\ge 0}}$, has a left adjoint.
**Proof** We turn an algebra $\alpha: \mathcal{D}(X) \to X$ and into a module $F(X)$, where:

$$F(X) = \{0\} + \mathbb{R}_{>0} \times X,$$

with addition for $u, v \in F(X)$, in trivial cases given by $u+0 = u = 0+u$ and:

$$(s, x) + (t, y) = (s + t, \alpha(\frac{s}{s+t}x + \frac{t}{s+t}y))$$

A scalar multiplication $\bullet: \mathbb{R}_{\ge 0} \times F(X) \to F(X)$ is defined as:

$$s \bullet u = \begin{cases} 0 & \text{if } u = 0 \text{ or } s = 0 \\ (s \cdot t, x) & \text{if } u = (t, x) \text{ and } s \neq 0. \end{cases}$$

This makes $F(X)$ a module over $\mathbb{R}_{\ge 0}$. Next we show that $F$ is left adjoint to $U: \mathrm{Alg}(\mathcal{M}_{\mathbb{R}_{\ge 0}}) \to \mathrm{Alg}(\mathcal{D})$, via the following bijective correspondence.

$$\begin{array}{ccc} X \xrightarrow{f} U(Y) & \text{in } \mathrm{Alg}(\mathcal{D}) \\ \hline F(X) \xrightarrow{g} Y & \text{in } \mathrm{Alg}(\mathcal{M}_{\mathbb{R}_{\ge 0}}) \end{array}$$

It works as follows.

* Given $f: X \to U(Y)$ in $\mathrm{Alg}(\mathcal{D})$ define $\bar{f}: F(X) \to Y$ by $\bar{f}(0) = 0$ and $\bar{f}(r, x) = r \bullet f(x)$ where $\bullet$ is scalar multiplication in $Y$. This yields a homomorphism of modules, i.e. a homomorphism of $\mathcal{M}_{\mathbb{R}_{\ge 0}}$-algebras.

* Conversely, given $g: F(X) \to Y$ take $\bar{g}: X \to U(Y)$ to be $\bar{g}(x) = g(1, x)$. This yields a map of $\mathcal{D}$-algebras.

Finally we check that we actually have a bijective correspondence:

$$\bar{\bar{f}}(x) = \bar{f}(1, x) = 1 \bullet f(x) = f(x).$$

Similarly, $\bar{g}(0) = 0$ and:

$$\bar{g}(r, x) = r \bullet \bar{g}(x) = r \bullet g(1, x) = g(r \bullet (1, x)) = g(r, x). \quad \square$$

## 3 Convex Sets

This section introduces convex structures—or simply, convex sets—as described in [12] and recalls that such structures can also be described as algebras of the distribution monad $\mathcal{D}$.

**Definition 3** A convex set consists of a set $X$ together with a ternary operation $\langle - , - , - \rangle : [0, 1] \times X \times X \to X$ satisfying the following four requirements,

$$\begin{align*} \langle r, x, x \rangle &= x & \langle r, x, y \rangle &= \langle 1 - r, y, x \rangle \\ \langle 0, x, y \rangle &= y & \langle r, x, \langle s, y, z \rangle \rangle &= \langle r + (1 - r)s, \langle \frac{r}{r+(1-r)s}, x, y \rangle, z \rangle, \end{align*}$$
where $r \in [0, 1]$ and $x, y, z \in X$, and $(r + (1 - r)s) \neq 0$ in the last equation.

A morphism of convex structures $(X, \langle-, -, -\rangle_X) \to (Y, \langle-, -, -\rangle_Y)$ consists of an "affine" function $f: X \to Y$ satisfying $f(\langle r, x, x' \rangle_X) = \langle r, f(x), f(x') \rangle_Y$, for all $r \in [0, 1]$ and $x, x' \in X$. This yields a category **Conv**.

A convex set is sometimes called a barycentric algebra, using terminology from [27]. The tuple $\langle r, x, y \rangle$ can also be written as labeled sum $x +_r y$, like in [20], but the fourth condition becomes a bit difficult to read with this notation.

The next result recalls an alternative description of convex structures and their homomorphisms, namely as algebras of a monad. It goes back to [28] and also applies to compact Hausdorff spaces [20] or Polish spaces [6]. For convenience, a proof sketch is included.

**Theorem 4** *The category Conv of convex sets is isomorphic to the category Alg($\mathcal{D}$) of Eilenberg-Moore algebras of the distribution monad.*

**Proof** Given an algebra $\alpha: \mathcal{D}(X) \to X$ on a set $X$ one defines an operation $\langle-, -, -\rangle: [0, 1] \times X \times X \to X$ by $\langle r, x, y \rangle = \alpha(rx + (1-r)y)$. It is not hard to show that the four requirements from Definition 3 hold.

Conversely, given a convex set $X$ with ternary operation $\langle -, -, - \rangle$ one defines a function $\alpha: \mathcal{D}(X) \to X$ inductively by:

$$ \alpha(r_1 x_1 + \cdots + r_n x_n) = \begin{cases} x_1 & \text{if } r_1 = 1, \text{ so } r_2 = \cdots = r_n = 0 \quad (5) \\ \langle r_1, x_1, \alpha(\frac{r_2}{1-r_1}x_2 + \cdots + \frac{r_n}{1-r_1}x_n) \rangle & \text{otherwise, i.e. } r_1 < 1. \end{cases} $$

Repeated application of this definition yields:

$$ \alpha(r_1 x_1 + \cdots + r_n x_n) = \langle r_1, x_1, \langle \frac{r_2}{1-r_1}, x_2, \langle \frac{r_3}{1-r_1-r_2}, x_3, \langle \dots, \langle \frac{r_{n-1}}{1-r_1-\dots-r_{n-2}}, x_{n-1}, x_n \rangle \dots \rangle \rangle \dots \rangle \quad (6) $$

One first has to show that the function $\alpha$ in (5) is well-defined, in the sense that it does not depend on permutations of summands, see also [27, Lemma 2]. Via some elementary calculations one checks that exchanging the summands $r_i x_i$ and $r_{i+1} x_{i+1}$ produces the same result. In a next step one proves the algebra equations: $\alpha \circ \eta = \text{id}$ and $\alpha \circ \mu = \alpha \circ \mathcal{D}(\alpha)$. The first one is easy, since $\alpha(\eta(a)) = \alpha(1a) = a$, directly by applying (5). The second one requires more work. Explicitly, it amounts to:

$$ \alpha\left(\sum_{i \le n} r_i \alpha\left(\sum_{j \le m_i} s_{ij} x_{ij}\right)\right) = \alpha\left(\sum_{i \le n} \sum_{j \le m_i} (r_i s_{ij}) x_{ij}\right). \quad (7) $$

For the proof the following auxiliary result is convenient. It handles nested tuples in the second argument of a triple $\langle -, -, - \rangle$, just like the fourth equation in Definition 3 deals with nested structure in the third argument. In a general convex structure one has $\langle r, \langle s, x, y \rangle, z \rangle = \langle rs, x, \langle \frac{r(1-s)}{1-rs}, y, z \rangle \rangle$, assuming $rs \neq 1$. The rest is then left to the reader. $\square$
This theorem now allows us to apply Theorem 1 to the category **Conv** of (real) convex structures. First we may conclude that it is both complete and cocomplete; also, that the forgetful functor **Conv** → **Sets** has a left adjoint, giving free convex structures of the form $\mathcal{D}(X)$. And since $\mathcal{D}$ is a commutative monad, the category **Conv** is symmetric monoidal closed: maps $X \otimes Y \to Z$ in **Conv** correspond to functions $X \times Y \to Z$ that are “bi-homomorphisms”, i.e. homomorphisms of convex structures in each variable separately. In this special case the tensor unit is the final (singleton) convex set, since $\mathcal{D}(1) \cong 1$. Hence one has “tensors with projections”, see [15]. Closedness means that the functors $(-) \otimes Y$ have a right adjoint, given by $Y \to (-)$. Moreover, $\mathcal{D}(A \times B) \cong \mathcal{D}(A) \otimes \mathcal{D}(B)$, for sets A, B.

**Remark 5** We shall later use that a meet semilattice $(L, \wedge, 0)$ can be understood as a convex set $\mathcal{D}(L) \to L$ via:

$$r_1x_1 + \cdots + r_nx_n \mapsto x_1 \wedge \cdots \wedge x_n,$$

where it is (implicitly) assumed that $r_i \neq 0$. This can be extended to a functor $\mathbf{MSL} \to \mathbf{Conv}$. In particular, the two-element set $\{0, 1\}$ of Booleans is a convex set.

**Remark 6** The adjunction $\mathbf{Conv} = \mathrm{Alg}(\mathcal{D}) \hookrightarrow \mathbf{Sets}$ induces a comonad on the category **Conv**, which is also written as $\mathcal{D}$. An Eilenberg-Moore coalgebra $X \to \mathcal{D}(X)$ of this comonad can be understood as spectral decomposition: it maps an element $x$ in a convex set $X$ to a formal convex combination $\sum_i r_i x_i$, which, when interpreted in $X$, is equal to $x$. For instance, the density matrices on a finite dimensional Hilbert space form a convex set and carry such a spectral decomposition coalgebra (depending on a choice of basis). See also [14] for similar decompositions involving atoms and compact elements in ordered sets captured via the comonad induced on a category of algebras.

# 4 Prime filters in convex sets

The next definition follows [8], but uses filters instead of ideals.

**Definition 7** Let $\alpha: \mathcal{D}(X) \to X$ be an algebra of the distribution monad $\mathcal{D}$, making $X$ a convex set. We write $(\sum_{i \le n} s_i x_i) \in \mathcal{D}(X)$, with $s_i \ne 0$, for an arbitrary formal convex combination. A subset $U \subseteq X$ is called a:

* subalgebra if $\forall i \le n, x_i \in U$ implies $\alpha(\sum_i s_i x_i) \in U$;

* filter if $\alpha(\sum_i s_i x_i) \in U$ implies $x_i \in U$, for each $i$;

* prime filter if it is both a subalgebra and a filter.

It is not hard to see that subalgebras are closed under arbitrary intersections and under directed joins. Hence one can form the least subalgebra $\bar{V} \subseteq X$
containing an arbitrary set $V \subseteq X$, by intersection. Filters are closed under arbitrary intersections and joins, hence also prime filters are closed under arbitrary intersections and directed joins. We shall write $pFil(X)$ for the set of prime filters in a convex set $X$, ordered by inclusion.

**Lemma 8** Assume $X$ is a convex set. A subset $U \subseteq X$ is a prime filter if and only if it is the “true kernel” $f^{-1}(1)$ of a homomorphism of convex sets $f: X \to \{0,1\}$. It yields an order isomorphism:

$$pFil(X) \cong \operatorname{Hom}(X, \{0,1\}).$$

Here we consider $\{0,1\}$ as meet semilattice as described in Remark 5.

**Proof** Let $\alpha: \mathcal{D}(X) \to X$ be an algebra on $X$. Given a prime filter $U \subseteq X$, define $f_U(x) = 1$ iff $x \in U$. This yields a homomorphism of algebras/convex sets, since for a convex sum $\sum_i s_i x_i$ with $s_i \neq 0$,

$$ \begin{align*} (f_U \circ \alpha)(\sum_i s_i x_i) &= 1 &\iff \alpha(\sum_i s_i x_i) &\in U \\ &\iff \forall_i, x_i \in U &\text{ since } U \text{ is a prime filter} \\ &\iff \forall_i, f_U(x_i) = 1 \\ &\iff \sum_i s_i f_U(x) = \bigwedge_i f_U(x_i) = 1 \\ &\iff (\beta \circ \mathcal{D}_S(f_U))(\sum_i s_i x_i) = 1, \end{align*} $$

where $\beta: \mathcal{D}(\{0,1\}) \to \{0,1\}$ is the convex structure induced by the meet semi-lattice structure of $\{0,1\}$. Similarly one shows that such homomorphisms induce prime filters as their true-kernels. $\square$

We write **PreFrm** for the category of preframes. They consist of a poset $L$ with directed joins $\bigvee$ and finite meets $(1, \wedge)$ distributing over these joins: $x \wedge \bigvee_i y_i = \bigvee_i x \wedge y_i$. Morphisms in **PreFrm** preserve both finite meets and directed joins. The two-element set $\{0,1\}$ is obviously a preframe. Homomorphisms of preframes $L \to \{0,1\}$ correspond (as true-kernels) to Scott-open filters $U \subseteq L$, see [29]. They are upsets, closed under finite meets, with the property that if $\bigvee_i x_i \in U$ then $x_i \in U$ for some $i$.

We have seen so far that taking prime filters yields a contravariant functor $pFil = \operatorname{Hom}(-, \{0,1\}): \operatorname{Conv} = \operatorname{Alg}(\mathcal{D}) \to \operatorname{PreFrm}$. The main result of this section shows that this forms actually a (dual) adjunction.

**Theorem 9** There is a dual adjunction between convex sets and preframes:

$$ \begin{array}{ccc} \text{Conv}^{\text{op}} & \xleftarrow{\text{Hom}(-, \{0,1\})} & \text{PreFrm} \\ & \perp & \\ \text{Hom}(-, \{0,1\}) & \xrightarrow{} & \end{array} $$
**Proof** For a preframe $L$ the homset $\operatorname{Hom}(L, \{0, 1\})$ of Scott-open filters is closed under finite intersections: if $\bigvee_i^\uparrow x_i \in U_1 \cap \cdots \cap U_m$, then for each $j \le m$ there is an $i_j$ with $x_j \in U_{i_j}$. By directedness there is an $i$ with $x_i \ge x_{i_j}$ for each $j$, so that $x_i$ is in each $\tilde{U}_j$. Hence, $\operatorname{Hom}(L, \{0, 1\})$ carries a $\mathcal{D}$-algebra structure.

For a convex set $X$ we need to construct a bijective correspondence:

$$ \begin{array}{ccc} X & \to & \operatorname{Hom}(L, \{0, 1\}) \\ \hline L & \to & \operatorname{Hom}(X, \{0, 1\}) \end{array} \quad \begin{array}{l} \text{in Conv} \\ \text{in PreFrm} \end{array} $$

It is given in the usual way by swapping arguments. □

Homomorphisms from convex sets to the set of Boolean values $\{0, 1\}$ capture only a part of what is going on. Richer structures arise via homomorphisms to the unit interval $[0, 1]$. They give rise to effect algebras, instead of preframes, as will be shown in the next two sections.

# 5 Effect algebras

This section recalls the basic definition, examples and results of effect algebras. To start, we need the notion of partial commutative monoid (PCM). It consists of a set $M$ with a zero element $0 \in M$ and a partial binary operation $\otimes: M \times M \to M$ satisfying the three requirements below—involving the notation $x \perp y$ for: $x \otimes y$ is defined.

1. Commutativity: $x \perp y$ implies $y \perp x$ and $x \otimes y = y \otimes x$;

2. Associativity: $y \perp z$ and $x \perp (y \otimes z)$ implies $x \perp y$ and $(x \otimes y) \perp z$ and also $x \otimes (y \otimes z) = (x \otimes y) \otimes z$;

3. Zero: $0 \perp x$ and $0 \otimes x = x$;

When $x \perp y$ we say that elements $x, y$ are orthogonal. More generally, a subset of a PCM is called orthogonal if all its elements are pairwise orthogonal. In writing $x \otimes y$ it is usually implicitly assumed that $x \otimes y$ is defined, i.e. that $x, y$ are orthogonal.

An example of a PCM is the unit interval $[0, 1]$ of real numbers, where $\otimes$ is the partially defined sum $+$. The notation $\otimes$ for the sum might suggest a join, but this is not intended, as the example $[0, 1]$ shows. We wish to avoid the notation $\oplus$ (and its dual $\otimes$) that is more common in the context of effect algebras because we like to reserve these operations $\oplus, \otimes$ for tensors on categories.

As an aside, for the more categorically minded, a PCM may also be understood as a monoid in the category of sets and partial functions. However, we shall use total maps as morphisms between PCMs (and effect algebras).

The notion of effect algebra is due to [9], see also [7] for an overview.

**Definition 10** An effect algebra is a partial commutative monoid $(E, 0, \otimes)$ with an orthosupplement. The latter is a unary operation $(-)^{\perp}: E \to E$ satisfying:
1. $x^{\perp} \in E$ is the unique element in $E$ with $x \otimes x^{\perp} = 1$, where $1 = 0^{\perp}$;

2. $x \perp 1 \Rightarrow x = 0$.

**Example 11** We briefly discuss several classes of examples.

(1) A singleton set forms an example of a degenerate effect algebra, with $0 = 1$. A two element set $2 = \{0, 1\}$ is also an example.

(2) A more interesting example is the unit interval $[0, 1] \subseteq \mathbb{R}$ of real numbers, with $r^{\perp} = 1 - r$ and $r \otimes s$ is defined as $r + s$ in case this sum is in $[0, 1]$. In fact, for each positive number $M \in \mathbb{R}$ the interval $[0, M]_{\mathbb{R}} = \{r \in \mathbb{R} | 0 \le r \le M\}$ is an example of an effect algebra, with $r^{\perp} = M - r$.

Also the interval $[0, M]_{\mathbb{Q}} = \{q \in \mathbb{Q} | 0 \le q \le M\}$ of rational numbers, for positive $M \in \mathbb{Q}$, is an effect algebra. And so is the interval $[0, M]_{\mathbb{N}}$ of natural numbers, for $M \in \mathbb{N}$.

The general situation involves so-called "interval effect algebras", see e.g. [10] or [7, 1.4]. An Abelian group $(G, 0, -, +)$ is called ordered if it carries a partial order $\le$ such that $a \le b$ implies $a + c \le b + c$, for all $a, b, c \in G$. A positive point is an element $p \in G$ with $p \ge 0$. For such a point we write $[0, p]_G \subseteq G$ for the "interval" $[0, p] = \{a \in G | 0 \le a \le p\}$. It forms an effect algebra with $p$ as top, orthosupplement $a^{\perp} = p - a$, and sum $a + b$, which is considered to be defined in case $a + b \le p$.

(3) A separate class of examples has a join as sum $\otimes$. Let $(L, \vee, 0, (-)^{\perp})$ be an ortholattice: $\vee, 0$ are finite joins and complementation $(-)^{\perp}$ satisfies $x \le y \Rightarrow y^{\perp} \le x^{\perp}$, $x^{\perp \perp} = x$ and $x \vee x^{\perp} = 1 = 0^{\perp}$. This $L$ is called an orthomodular lattice if $x \le y$ implies $y = x \vee (x^{\perp} \wedge y)$. Such an orthomodular lattice forms an effect algebra in which $x \otimes y$ is defined if and only if $x \perp y$ (i.e. $x \le y^{\perp}$, or equivalently, $y \le x^{\perp}$); and in that case $x \otimes y = x \vee y$. This restriction of $\vee$ is needed for the validity of requirements (1) and (2) in Definition 10.

In particular, the lattice KSub($H$) of closed subsets of a Hilbert space $H$ is an orthomodular lattice and thus an effect algebra. This applies more generally to the kernel subobjects of an object in a dagger kernel category [13]. These kernels can also be described as self-adjoint endomaps below the identity, see [13, Prop. 12]—in group-representation style, like in the above point 2.

(4) Since Boolean algebras are (distributive) orthomodular lattices, they are also effect algebras. By distributivity, elements in a Boolean algebra are orthogonal if and only if they are disjoint, i.e. $x \perp y$ iff $x \wedge y = 0$. In particular, the Boolean algebra of measurable subsets of a measurable space forms an effect algebra, where $U \otimes V$ is defined if $U \cap V = \emptyset$, and is then equal to $U \cup V$.

An obvious next step is to organise effect algebras into a category **EA**.

**Definition 12** A homomorphism $E \to D$ of effect algebras is given by a function $f: E \to D$ between the underlying sets satisfying $f(1) = 1$, and if $x \perp x'$ in $E$ then both $f(x) \perp f(x')$ in $D$ and $f(x \otimes x') = f(x) \otimes f(x')$.

Effect algebras and their homomorphisms form a category, called **EA**.

Homomorphisms are like measurable maps. Indeed, for the effect algebra $\Sigma$ associated in Example 11 (4) with a measureable space $(X, \Sigma)$, effect algebra
homomorphisms $f: \Sigma \to [0, 1]$ satisfy $f(U \cup V) = f(U) + f(V)$ in case $U, V$ are disjoint—because then $U \otimes V$ is defined and equals $U \cup V$. In general, effect algebra homomorphisms $E \to [0, 1]$ to the unit interval are often called states.

Homomorphisms of effect algebras preserve all the relevant structure.

**Lemma 13** Let $f: E \to D$ be a homomorphism of effect algebras. Then:

$$f(x^{\perp}) = f(x)^{\perp} \quad \text{and thus} \quad f(0) = 0.$$

**Proof** From $1 = f(1) = f(x \otimes x^{\perp}) = f(x) \otimes f(x^{\perp})$ we get $f(x^{\perp}) = f(x)^{\perp}$ by uniqueness of orthosupplements. Hence: $f(0) = f(1^{\perp}) = f(1)^{\perp} = 1^{\perp} = 0$. $\square$

**Example 14** It is not hard to see that the one-element effect algebra 1 is final, and the two-element effect algebra 2 is initial.

Orthosupplement $(-)^{\perp}$ is an isomorphism $E \cong E^{\text{op}}$ in $\mathbf{EA}$, namely from $(E, 0, \otimes, (-)^{\perp})$ to $E^{\text{op}} = (E, 1, \otimes, (-)^{\perp})$, where $x \otimes y = (x^{\perp} \otimes y^{\perp})^{\perp}$. This makes $\mathbf{EA}$ and involutive category, see [16].

An element (or point) $x \in E$ of an effect algebra $E$ can be identified with a homomorphism $2 \times 2 \to E$ in $\mathbf{EA}$, as in:

$$2 \times 2 = \mathbf{MO}(2) = \left( \begin{array}{cc} \bullet & \bullet^{\perp} \\ \bullet & 0 \end{array} \right) \xrightarrow{x} E.$$

In [17] it shown that the category $\mathbf{EA}$ is complete and cocomplete, and has a symmetric monoidal structure.

# 6 Effect algebras and convex sets

The aim in this section is to establish the dual adjunction between convex sets and effect algebras on the right in the diagram (1) in the introduction. As we have seen, the unit interval $[0, 1]$ of real numbers is a prime example of a convex set. The set of states of an effect algebra—consisting of maps into $[0, 1]$—is also convex, as noticed for instance in [10].

**Lemma 15** Taking states yields a functor $S = \text{Hom}(-, [0, 1]): \mathbf{EA} \to \text{Conv}^{\text{op}}$.

**Proof** Let $E$ be an effect algebra with states $f_i: E \to [0, 1]$ and $r_i \in [0, 1]$ with $\sum_i r_i = 1$, then we can form a new state $f = r_1 f_1 + \cdots + r_n f_n$ by $f(x) = \sum_i r_i \cdot f_i(x)$, using multiplication $\cdot$ in $[0, 1]$. This yields a homomorphism of effect algebras $E \to [0, 1]$, since:

$$\bullet f(1) = \sum_i r_i \cdot f_i(1) = \sum_i r_i \cdot 1 = \sum_i r_i = 1;$$

• if $x \perp x'$ in $E$, then in $[0, 1]$:

$$\begin{align*} f(x \otimes x') &= \sum_i r_i \cdot f_i(x \otimes x') \\ &= \sum_i r_i \cdot (f_i(x) + f_i(x')) \\ &= \sum_i r_i \cdot f_i(x) + r_i \cdot f_i(x') \\ &= \sum_i r_i \cdot f_i(x) + \sum_i r_i \cdot f_i(x') \\ &= f(x) + f(x'). \end{align*}$$
Further, for a map of effect algebras $g: E \to D$ the induced function $S(g) = (-) \circ g: \operatorname{Hom}(D, [0, 1]) \to \operatorname{Hom}(E, [0, 1])$ is a map of convex sets:

$$ \begin{aligned} S(g)(\sum_i r_i f_i) &= \lambda x. (\sum_i r_i f_i)(g(x)) \\ &= \lambda x. \sum_i r_i \cdot f_i(g(x)) \\ &= \lambda x. \sum_i r_i \cdot S(g)(f_i)(x) \\ &= \sum_i r_i(S(g)(f_i)). \end{aligned} \quad \square $$

A set of state $S(E) = \operatorname{Hom}(E, [0, 1])$ is thus convex, but it does not have an underlying scalar multiplication $\bullet$: $[0, 1] \times S(E) \to S(E)$, since $r \bullet f = \lambda x. r \cdot f(x)$ need not be a map of effect algebras: $(r \bullet f)(1) = r \cdot f(1) = r \cdot 1 = r \neq 1$, in general.

Interestingly, there is also a Hom functor in the other direction.

**Lemma 16** For each convex set $X$ the homset $\operatorname{Hom}(X, [0, 1])$ of homomorphisms of convex sets is an effect algebra. In this way one gets a functor $\operatorname{Hom}(-, [0, 1]): \operatorname{Conv}^{\mathrm{op}} \to \mathrm{EA}$.

**Proof** Let $X$ be a convex set. We define effect algebra structure on the homset $\operatorname{Hom}(X, [0, 1])$ in a pointwise manner. There is an obvious zero element, namely the zero function $\lambda x. 0$. A partial sum $f + f'$ is defined as $(f + f')(x) = f(x) + f'(x)$, provided $f(x) + f'(x) \le 1$ for all $x \in X$. It is easy to see that this $f + f'$ is again a map of convex sets. Similarly, one defines $f^{\perp} = \lambda x. 1 - f(x)$, which is again a homomorphism since:

$$ \begin{aligned} f^{\perp}(r_1 x_1 + \cdots + r_n x_n) &= 1 - f(r_1 x_1 + \cdots + r_n x_n) \\ &= (r_1 + \cdots + r_n) - (r_1 \cdot f(x_1) + \cdots + r_n \cdot f(x_n)) \\ &= r_1 \cdot (1 - f(x_1)) + \cdots + r_n \cdot (1 - f(x_n)) \\ &= r_1 \cdot f^{\perp}(x_1) + \cdots + r_n \cdot f^{\perp}(x_n). \end{aligned} $$

Functoriality is easy: for a map $g: X \to Y$ of convex sets we obtain a map of effect algebras $(-) \circ g: \operatorname{Hom}(Y, [0, 1]) \to \operatorname{Hom}(X, [0, 1])$ by precomposition. $\square$

The next result is now an easy combination of the previous two lemmas.

**Theorem 17** There is a dual adjunction between convex sets and effect algebras:

<figure><img src="image_2.png" /></figure>

**Proof** We need to check that the unit and counit

$$ \begin{array}{ccc} E & \xrightarrow{\eta} & \operatorname{Hom}(S(E), [0, 1]) \\ x & \longleftarrow & \lambda f. f(x) \end{array} \qquad \begin{array}{ccc} X & \xrightarrow{\epsilon} & S(\operatorname{Hom}(X, [0, 1])) \\ x & \longleftarrow & \lambda f. f(x) \end{array} $$

are appropriate maps. First we check that $\eta$ is a morphism of effect algebras:
• $\eta(1) = \lambda f. f(1) = \lambda f. 1 = 1$;

• and if $x \perp x'$ in E, then:

$$
\begin{align*}
\eta(x \otimes x') &= \lambda f. f(x \otimes x') = \lambda f. f(x) + f(x') \\
&= \lambda f. \eta(x)(f) + \eta(x')(f) \\
&= \eta(x) + \eta(x').
\end{align*}
$$

Similarly $\varepsilon$ is a map of convex sets:

$$
\begin{align*}
\varepsilon(r_1 x_1 + \cdots + r_n x_n) &= \lambda f. f(r_1 x_1 + \cdots + r_n x_n) \\
&= \lambda f. r_1 \cdot f(x_1) + \cdots + r_n \cdot f(x_n) \\
&= \lambda f. r_1 \cdot \varepsilon(x_1)(f) + \cdots + r_n \cdot \varepsilon(x_n)(f) \\
&= r_1 \varepsilon(x_1) + \cdots + r_n \varepsilon(x_n). \quad \square
\end{align*}
$$

7 Effect algebras and convex functors

Let $\mathbf{A}$ be an arbitrary category with finite limits and finite coproducts (0, +)
which are disjoint and universal. This means that coprojections $\kappa_i$ are monic
and form pullback squares as on the left below, and additionally that in a square
as on the right below, the induced map $Z_1 + Z_2 \to Z$ is an isomorphism.

<figure><img src="image_3.png" /></figure>

In this setting one can prove that diagrams of the form below are pullbacks.

$$
\begin{tikzcd}
X \arrow[r, "\kappa_1"] \arrow[d, "f"] & X + Z \arrow[d, "f+g"] \\
Y \arrow[r, "\kappa_1"] & Y + Z
\end{tikzcd}
\qquad
\begin{array}{rcl}
X + W \arrow[r, "f+id"] & Y + W & (8) \\
\mathrel{\boxed{\phantom{XX}}} \arrow[d, "\mathrel{\boxed{\phantom{XX}}}"] & \mathrel{\boxed{\phantom{XX}}} \arrow[d, "\mathrel{\boxed{\phantom{XX}}}"] & \\
X + Z \arrow[r, "f+id"] & Y + Z
\end{array}
$$

The final object $1 \in \mathbf{A}$ can be used to obtain (representations of) natural numbers $\underline{n} \in \mathbf{A}$, for $n \in \mathbb{N}$. One simply puts:

$\underline{0} = 0 \quad \text{and} \quad \underline{n+1} = n+1.$

We shall use these “numbers” $\underline{n} \in \mathbf{A}$ with coprojections $\kappa_i: 1 \to \underline{n}$ for $1 \le i \le n$.
The following maps will be useful.

$$
\underline{n+1} \xrightarrow{\nabla_i} \underline{2} \quad \text{where} \quad \nabla_i \circ \kappa_j = \begin{cases} \kappa_1 & \text{if } i=j \\ \kappa_2 & \text{otherwise} \end{cases} \tag{9}
$$
(where $0 \le i \le n$ and $0 \le j \le n+1$). Writing the underlining gets tedious, so we often drop it when no confusion arises.

In **Sets** we identify $n$ (to be more precise: $\underline{n}$) with the set $\{1, 2, \dots, n\}$. The coprojection $\kappa_i: 1 \to n$ is then simply $i$. The maps $\nabla_i: n+1 \to 2$ from (9), for $1 \le i \le n$, satisfy $\nabla_i(j) = 1$ if $i = j$ and $\nabla_i(j) = 2$ if $i \ne j$.

We are now ready to introduce a new notion of convex functor. What we present is finitary version, because in the present context we only consider finite convex combinations, and correspondingly, finite (partial) sums in effect algebras.

**Definition 18** Let $\mathbf{A}$ be a category with disjoint and universal finite coproducts, and finite limits (as above). A functor $F: \mathbf{A} \to \mathbf{A}$ will be called convex if it satisfies the following three requirements.

$$1. F(1) \xrightarrow{\cong} 1;$$

2. $F$ preserves the following three pullbacks, which are special instances of (8).

$$ \begin{array}{ccc} \begin{array}{rcl} n & \xrightarrow{\kappa_1} & n+1 \\ \searrow & \searrow & \\ 1 & \xrightarrow{\kappa_1} & 1+1=2 \end{array} & \begin{array}{rcl} 1 & \xrightarrow{\kappa_1} & 1+n \\ \Vert & \Vert & \\ 1 & \xrightarrow{\kappa_1} & 1+1=2 \end{array} & \begin{array}{rcl} n+m & \xrightarrow{!+id} & 1+m \\ \text{id}+! & \searrow & \\ n+1 & \xrightarrow{!+id} & 1+1=2 \end{array} \end{array} \quad (10) $$

3. the following tuple is monic, involving the maps $\nabla_i$ from (9).

$$ F(\underline{n+1}) \xrightarrow{\langle F(\nabla_1), \dots, F(\nabla_n) \rangle} F(2) \times \dots \times F(2). \quad (11) $$

We shall write $\text{CNV}(\mathbf{A})$ for the category of convex endofunctors on $\mathbf{A}$, and natural transformations between them.

Convexity can in principle also be defined for functors $\mathbf{A} \to \mathbf{B}$ between different categories, but such generality is not needed here. A functor $F$ satisfying the first requirement $F(1) \cong 1$ is sometimes called *affine*, see e.g. [21, 15].

**Example 19** We shall shortly see a general construction to obtain convex functors in the form of probability distribution functors. But it is instructive to see a non-example first. The non-empty powerset functor $\mathcal{P}^+$: **Sets** $\to$ **Sets** is a possible candidate for a convex functor because $\mathcal{P}^+(1) \cong 1$. We shall skip the second condition in Definition 18 and show why the third one fails. The maps $\mathcal{P}^+(\nabla_i): \mathcal{P}^+(n+1) \to \mathcal{P}^+(2)$ are given by:

$$ \mathcal{P}^+(\nabla_i)(U) = \{1 \mid i \in U\} \cup \{2 \mid U - i \neq \emptyset\}. $$

If $U, V \in \mathcal{P}^+(n+1)$ satisfy $\mathcal{P}^+(\nabla_i)(U) = \mathcal{P}^+(\nabla_i)(V)$, then we have $i \in U \Leftrightarrow i \in V$ for $1 \le i \le n$. But we have no information about whether or not $n+1$ is in $U$ or $V$. Hence we don't have enough information to conclude $U = V$.
The following construction gives an important class of examples of convex functors on the category of sets. It generalises the construction of the distribution functor $\mathcal{D}$ in (4) from the unit interval $[0, 1]$ to an arbitrary effect algebra.

**Definition 20** For an effect algebra $E$ define a functor $\mathcal{D}_E: \text{Sets} \to \text{Sets}$ by:

$$ \mathcal{D}_E(X) = \{\varphi: X \to E \mid \text{supp}(\varphi) \text{ is finite and orthogonal, and } \bigoplus_{x \in E} \varphi(x) = 1\}. $$

For a function $f: X \to Y$ one gets $\mathcal{D}_E(f): \mathcal{D}_E(X) \to \mathcal{D}_E(Y)$ by:

$$ \mathcal{D}_E(f)(\varphi)(y) = \bigoplus_{x \in f^{-1}(y)} \varphi(x). $$

**Proposition 21** Functors $\mathcal{D}_E$ are convex, and satisfy $\mathcal{D}_E(2) \cong E$. The mapping $E \mapsto \mathcal{D}_E$ yields a functor $\text{EA} \to \text{Conv}(\text{Sets})$.

**Proof** We begin by describing what the sets $\mathcal{D}_E(1)$ and $\mathcal{D}_E(2)$ are. An element $\varphi \in \mathcal{D}_E(1)$ is a map $\varphi: \{1\} \to E$ with $\bigoplus_{x \in \{1\}} \varphi(x) = 1$. Hence $\varphi$ is completely determined as $\varphi(1) = 1$. Thus $\mathcal{D}_E(1) \cong 1$, making $\mathcal{D}_E$ an affine functor.

An element $\varphi \in \mathcal{D}_E(2)$ is a map $\varphi: \{1, 2\} \to E$ satisfying $\varphi(1) \perp \varphi(2)$ and $\varphi(1) \otimes \varphi(2) = 1$. Hence $\varphi(2) = \varphi(1)^{\perp}$, so that $\varphi$ is determined by $\varphi(1) \in E$. Thus $\mathcal{D}_E(2) \cong E$.

If we have two elements $\varphi, \psi \in \mathcal{D}_E(n+1)$ satisfying $\mathcal{D}_E(\nabla_i)(\varphi) = \mathcal{D}_E(\nabla_i)(\psi)$, for $1 \le i \le n$, then $\varphi(i) = \mathcal{D}_E(\nabla_i)(\varphi)(1) = \mathcal{D}_E(\nabla_i)(\psi)(1) = \psi(i)$. But then $\varphi = \psi$, as required in point 3 in Definition 18, since the remaining value at $n+1$ is determined by the others (unlike in Example 19):

$$ \varphi(n+1) = (\varphi(1) \otimes \dots \otimes \varphi(n))^{\perp} = (\psi(1) \otimes \dots \otimes \psi(n))^{\perp} = \psi(n+1). $$

We turn to point 2 and check that the functor $\mathcal{D}_E$ preserves the three pullbacks (10). For the first one, assume $\varphi \in \mathcal{D}_E(n+1)$ satisfies $\mathcal{D}_E(!+id)(\varphi) = \mathcal{D}_E(\kappa_1)(*)$, where $\kappa_1: 1 \to 1+1$ and $*$ is the single element $*=\lambda x. 1 \in \mathcal{D}_E(1)$. This means that $\varphi(1) \otimes \dots \otimes \varphi(n) = \mathcal{D}_E(!+id)(\varphi)(1) = \mathcal{D}_E(\kappa_1)(*) = 1$, and thus $\varphi(n+1) = 0$. Hence there is a unique element $\varphi' \in \mathcal{D}_E(n)$ with $\mathcal{D}_E(\kappa_1)(\varphi') = \varphi$, namely $\varphi'(i) = \varphi(i)$ for $1 \le i \le n$.

Preservation of the second pullback is left to the reader. For the third one, assume $\varphi \in \mathcal{D}_E(n+1)$ and $\psi \in \mathcal{D}_E(1+m)$ satisfying $\mathcal{D}_E(!+id)(\varphi) = \mathcal{D}_E(id+!)(\psi)$. This means:

$$ \varphi(1) \otimes \dots \otimes \varphi(n) = \psi(1) \qquad \varphi(n+1) = \psi(2) \otimes \dots \otimes \psi(m+1). $$

The $\chi \in \mathcal{D}_E(n+m)$ that we are looking for must satisfy $\varphi = \mathcal{D}_E(id+!)(\chi)$ and $\psi = \mathcal{D}_E(!+id)(\chi)$. That is:

$$ \varphi(i) = \chi(i), \text{ for } 1 \le i \le n, \qquad \varphi(n+1) = \chi(n+1) \otimes \dots \otimes \chi(n+m) $$

$$ \psi(1) = \chi(1) \otimes \dots \otimes \chi(n) \qquad \psi(j+1) = \chi(n+j-1), \text{ for } 2 \le j \le m+1. $$

Hence there is a precisely one choice for such a $\chi$, so that $\mathcal{D}_E$ applied the last pullback in (10) is again a pullback.
Finally we have to check that the mapping $E \mapsto \mathcal{D}_E$ is functorial. Given a map $g: E \to D$ in **EA**, there is a natural transformation $g \circ (-): \mathcal{D}_E \Rightarrow \mathcal{D}_D$, that is well-defined and natural because $g$ is a homomorphism. $\square$

The next step is to show that, in the reverse direction, a convex functor (on **Sets**) gives rise to an effect algebra.

**Proposition 22** Let $F$: **Sets** $\to$ **Sets** be a convex functor. Then $F(2)$ is an effect algebra, with the following structure:

$$0 = \left( 1 \xrightarrow{\cong} F(1) \xrightarrow{F(\kappa_2)} F(2) \right) \quad 1 = \left( 1 \xrightarrow{\cong} F(1) \xrightarrow{F(\kappa_1)} F(2) \right) \\ (-)^{\perp} = \left( F(2) \xrightarrow{\cong} F(2) \right) \qquad (12)$$

For $a, b \in F(2)$ we say $a \perp b$ if there is a 'bound' $\beta \in F(3)$ such that $F(\nabla_1)(\beta) = a$ and $F(\nabla_2)(\beta) = b$, with $\nabla_i$ as in (9). In that case we define:

$$a \otimes b = F(! + \mathrm{id})(\beta) \in F(2),$$

where $! + \mathrm{id}: 2 + 1 \to 2$ sends $1, 2 \mapsto 1$ and $3 \mapsto 2$.

Further, the mapping $F \mapsto F(2)$ yields a functor $\mathrm{CNV}(\mathbf{Sets}) \to \mathrm{EA}$.

It may be instructive to see what this partial sum $\otimes$ on $F(2)$ means for the convex functors $F = \mathcal{D}_E$ from Proposition 21. So assume $\varphi, \psi \in \mathcal{D}_E(2)$ have bound $\beta \in \mathcal{D}_E(3)$. The equations $\varphi = F(\nabla_1)(\beta)$ and $\psi = F(\nabla_2)(\beta)$ yield:

$$\varphi(1) = \beta(1) \qquad \varphi(2) = \beta(2) \otimes \beta(3) \qquad \psi(1) = \beta(2) \qquad \psi(2) = \beta(1) \otimes \beta(3).$$

In particular, the elements $\varphi(1), \psi(1)$ can be added, since $\varphi(1) \otimes \psi(1) \otimes \beta(3) = 1$. Thus, the sum $\varphi \otimes \psi = \mathcal{D}_E(! + \mathrm{id})(\beta) \in \mathcal{D}_E(2)$ satisfies:

$$(\varphi \otimes \psi)(1) = \beta(1) \otimes \beta(2) = \varphi(1) \otimes \psi(1)$$

$$(\varphi \otimes \psi)(2) = \beta(3) = (\beta(1) \otimes \beta(2))^{\perp} = (\varphi(1) \otimes \psi(1))^{\perp} = (\varphi \otimes \psi)(1)^{\perp}.$$

**Proof** We check some of the requirements that must hold for effect algebras.

The partial sum $\otimes$ is commutative, since if $\beta \in F(3)$ is a bound for $a, b \in F(2)$, then $\beta' = F([\kappa_2, \kappa_1] + \mathrm{id}) \in F(3)$ is a bound for $b, a$, with the same sum:

$$b \otimes a = F(! + \mathrm{id})(\beta') = F((! + \mathrm{id}) + ([\kappa_2, \kappa_1] + \mathrm{id}))(\beta) = F(! + \mathrm{id})(\beta) = a \otimes b.$$

The $0$ defined in (12) is a zero element for $\otimes$, since for an arbitrary element $a \in F(2)$ there is a bound $\alpha = F(\kappa_2)(a) \in F(1 + 2)$ for $0, a$ with sum $a$.

Associativity of $\otimes$ requires more work. Assume $a, b, c \in F(2)$ are given with $a \perp b$, say with bound $\alpha \in F(3)$, and $(a \otimes b) \perp c$, with bound $\beta \in F(3)$. The latter means $F(\nabla_1)(\beta) = a \otimes b = F(! + \mathrm{id})(\alpha)$. Thus we have a situation:

$$\begin{array}{ccc} F(2+2) & \xrightarrow{F(id+!)} & F(2+1) \ni \alpha \\ F(!+id) \downarrow & & \downarrow F(!+id) \\ \beta \in F(1+2) & \xrightarrow{F(id+!)=F(\nabla_1)} & F(2) \end{array}$$
Because this is a pullback that is preserved by $F$, see (10), there is a (unique) element $\gamma \in F(2+2)$ with $F(id+!)(\gamma) = \alpha$ and $F(!+id)(\gamma) = \beta$. We first consider the function $h: 4 \to 3$ given by $h(1) = h(4) = 3$, $h(2) = 1$, and $h(3) = 2$. It yields $\gamma' = F(h)(\gamma) \in F(3)$, which is a bound for $b, c$ with sum $b \otimes c$. We next take the function $k: 4 \to 3$ defined by $k(1) = 1$, $k(2) = k(3) = 2$, and $k(4) = 3$. Now $\gamma'' = F(k)(\gamma) \in F(3)$ is a bound for $a$ and $b \otimes c$. Finally we get:

$$ 
\begin{aligned}
a \otimes (b \otimes c) &= F(!+id)(\gamma'') = F((!+id) \circ k)(\gamma) \\
&= F((!+id) \circ (!+id))(\gamma) \\
&= F(!+id)(\beta) = (a \otimes b) \otimes c.
\end{aligned}
$$

The equation $a^{\perp} \otimes a = 1$ can be proven via the bound $\alpha = F(h)(a) \in F(3)$ for $h: 2 \to 3$ defined by $h(1) = 2$ and $h(2) = 1$.

We leave it to the reader to check that $a^{\perp}$ is the only element $b \in F(2)$ with $b \otimes a = 1$, and proceed by showing $1 \perp a \Rightarrow a = 0$. Assume thus $1 \perp a$, say via a bound $\alpha \in F(3)$ satisfying $F(\nabla_1)(\alpha) = 1 = F(\kappa_1)(*)$ and $F(\nabla_2)(\alpha) = a$. The first equation allows us to use preservation by $F$ of the second pullback in (10), since $\nabla_1 = id+!$. Hence we get $\alpha = F(\kappa_1)(*)$ for $\kappa_1: 1 \to 1+2$, and thus:

$$ a = F(\nabla_2)(\alpha) = F(\nabla_2 \circ \kappa_1)(*) = F(\kappa_2)(*) = 0. $$

Finally we have to prove functoriality of the mapping $F \mapsto F(2)$. If we have a natural transformation $\sigma: F \Rightarrow G$ between convex functors $F, G$, then the component $\sigma_2: F(2) \to G(2)$ is a map of effect algebras. It is easy to see that it preserves $0, 1 \in F(2)$. Next, assume $a, b \in F(2)$ are orthogonal, via bound $\alpha \in F(3)$ satisfying $F(\nabla_1)(\alpha) = a$ and $F(\nabla_2)(\alpha) = b$. Then $\sigma_3(\alpha) \in G(3)$ is a bound for $\sigma_2(a), \sigma_2(b) \in G(2)$ by naturality. Hence $\sigma_2(a) \perp \sigma_2(b)$. Further,

$$ \sigma_2(a) \otimes \sigma_2(b) = G(!+id)(\sigma_3(\alpha)) = \sigma_2(F(!+id)(\alpha)) = \sigma_2(a \otimes b). \quad \square $$

The main result is then the adjointness of these functors between effect algebras and convex functors.

**Theorem 23** The functor $\mathbf{EA} \to \mathbf{CNV}(\mathbf{Sets})$ from Proposition 21 given by $E \mapsto \mathcal{D}_E$ is left adjoint to the functor $F \mapsto F(2)$ from Proposition 22.

**Proof** For an effect algebra $E$ and a convex endofunctor $F$ on $\mathbf{Sets}$ we have to prove that there is a bijective correspondence:

$$ \begin{array}{ccc} \begin{array}{c} E \xrightarrow{f} F(2) \\ \mathcal{D}_E \xrightarrow{\sigma} F \end{array} & \text{in } \mathbf{EA} \\ \hline \mathcal{D}_E \xrightarrow{\sigma} F & \text{in } \mathbf{Conv}(\mathbf{Sets}) \end{array} $$

The upward direction is easy: one maps $\sigma: \mathcal{D}_E \Rightarrow F$ to:

$$ \bar{\sigma} = (E \xrightarrow{\cong} \mathcal{D}_E(2) \xrightarrow{\sigma_2} F(2)) $$
It is not hard to see that this is a map of effect algebras.

The other direction requires more work. So suppose we have $f: E \to F(2)$ in EA. We have to define a natural transformation $\bar{f}: D_E \Rightarrow F$. So assume $\varphi \in D_E(X)$, say with $\text{supp}(\varphi) = \{x_1, \dots, x_n\}$. The elements $\varphi(x_i) \in E$ are pairwise orthogonal, and thus so are $f(\varphi(x_i)) \in F(2)$. This means that there is a (unique) bound $\beta \in F(n+1)$ with $F(\nabla_i)(\beta) = f(\varphi(x_i))$, and also:

$$F(!+id)(\beta) = \bigcirc_i f(\varphi(x_i)) = f(\bigcirc_i \varphi(x_i)) = f(1) = 1 = F(\kappa_1)(\ast).$$

Now we need to use that pullbacks of the following form are preserved by $F$.

$$\begin{array}{ccc} n & \xrightarrow{\kappa_1} & n+1 \\ \searrow & & \searrow+\text{id} \\ 1 & \xrightarrow{\kappa_1} & 1+1=2 \end{array}$$

This yields a unique $\beta' \in F(n)$ with $F(\kappa_1)(\beta') = \beta$. Finally we put:

$$\bar{f}_X(\varphi) = \left( F(n \xrightarrow{[x_1, \dots, x_n]} X)(\beta') \right) \in F(X).$$

Remaining details are left to the reader. □

<figure><img src="image_4.png" /></figure>

An obvious next step is to extend this result to an adjunction between effect algebras with multiplication—like [0, 1] has—and convex monads. It can form part of a “triangle of adjunctions”, like in [5]. This will be elaborated elsewhere.

## Acknowledgements

Thanks to Dion Coumans, Chris Heunen, Bas Spitters and Jorik Mandemaker for feedback and/or helpful discussions.

## References

[1] S. Abramsky. Domain theory in logical form. Ann. Pure & Appl. Logic, 51(1/2):1-77, 1991.

[2] J.C. Baez and M. Stay. Physics, topology, logic and computation: A Rosetta stone. 2009. arxiv.org/abs/0903.0340.

[3] M. Barr and Ch. Wells. Toposes, Triples and Theories. Springer, Berlin, 1985. Revised and corrected version available from URL: www.cwru.edu/artsci/math/wells/pub/ttt.html.

[4] P. Busch, M. Grabowski, and P. Lahti. Operational Quantum Physics. Springer Verlag, Berlin, 1995.

[5] D. Coumans and B. Jacobs. Scalars, monads and categories, 2010. arxiv.org/abs/1003.0585.
[6] E.-E. Doberkat. Eilenberg-Moore algebras for stochastic relations. *Inf. & Comp.*, 204(12):1756–1781, 2006. Erratum and addendum in: 206(12):1476–1484, 2008.

[7] A. Dvurečenskij and S. Pulmannová. *New Trends in Quantum Structures*. Kluwer Acad. Publ., Dordrecht, 2000.

[8] J. Flood. Semiconvex geometry. *Journ. Austr. Math. Soc.*, Series A 30:496–510, 1981.

[9] D. J. Foulis and M.K. Bennett. Effect algebras and unsharp quantum logics. *Found. Physics*, 24(10):1331–1352, 1994.

[10] D. J. Foulis, R.J. Greechie, and M.K. Bennett. The transition to unigroups. *Int. Journ. Theor. Physics*, 37(1):45–63, 1998.

[11] T. Fritz. Convex spaces I: Definition and examples. arxiv.org/abs/0903.5522, 2009.

[12] S. Gudder. A general theory of convexity. *Milan Journal of Mathematics*, 49(1):89–96, 1979.

[13] C. Heunen and B. Jacobs. Quantum logic in dagger kernel categories. *Order*, 2010. doi:10.1007/s11083-010-9145-5.

[14] B. Jacobs. Coalgebras and approximation. In A. Nerode and Yu. V. Matiya-sevich, editors, *Logical Foundations of Computer Science*, number 813 in Lect. Notes Comp. Sci., pages 173–183. Springer, Berlin, 1994.

[15] B. Jacobs. Semantics of weakening and contraction. *Ann. Pure & Appl. Logic*, 69(1):73–106, 1994.

[16] B. Jacobs. Involutive categories and monoids, with a GNS-correspondence. In *Quantum Physics and Logic* (QPL), 2010.

[17] B. Jacobs and J. Mandemaker. Coreflections in algebraic quantum logic. In *Quantum Physics and Logic* (QPL), 2010.

[18] P.T. Johnstone. *Stone Spaces*. Number 3 in Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press, 1982.

[19] P.T. Johnstone and S. Vickers. Preframe presentations present. In A. Carboni, M.C. Pedicchio, and G. Rosolini, editors, *Como Conference on Category Theory*, number 1488 in Lect. Notes Math., pages 193–212. Springer, Berlin, 1991.

[20] K. Keimel. The monad of probability measures over compact ordered spaces and its Eilenberg-Moore algebras. *Topology and its Applications*, 156:227–239, 2008.
[21] A. Kock. Bilinearity and cartesian closed monads. *Math. Scand.*, 29:161-174, 1971.

[22] A. Kock. Closed categories generated by commutative monads. *Journ. Austr. Math. Soc.*, XII:405-424, 1971.

[23] E.G. Manes. *Algebraic Theories*. Springer, Berlin, 1974.

[24] S. Mac Lane. *Categories for the Working Mathematician*. Springer, Berlin, 1971.

[25] J. von Neumann and O. Morgenstern. *Theory of Games and Economic Behavior*. Princeton University Press, 1944.

[26] S. Pulmannová and S. Gudder. Representation theorem for convex effect algebras. *Commentationes Mathematicae Universitatis Carolinae*, 39(4):645-659, 1998. Available from http://dml.cz/dmlcz/119041.

[27] M.H. Stone. Postulates for the barycentric calculus. *Ann. Math.*, 29:25-30, 1949.

[28] T. Swirszcz. Monadic functors and convexity. *Bull. de l'Acad. Polonaise des Sciences. Sér. des sciences math., astr. et phys.*, 22:39-42, 1974.

[29] S. Vickers. *Topology Via Logic*. Number 5 in Tracts in Theor. Comp. Sci. Cambridge Univ. Press, 1989.