Abstract
The category R e l is the category of sets (objects) and relations (morphisms). Equipped with the direct product of sets, R e l is a monoidal category. Moreover, R e l is a locally posetal 2-category, since every homset R e l(A,B) is a poset with respect to inclusion. We examine the 2-category of monoids R e l M o n in this category. The morphism we use are lax. This category includes, as subcategories, various interesting classes: hypergroups, partial monoids (which include various types of quantum logics, for example effect algebras) and small categories. We show how the 2-categorical structure gives rise to several previously defined notions in these categories, for example certain types of congruence relations on generalized effect algebras. This explains where these definitions come from.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
A strict 2-category [6, 10] is a category with “morphisms between morphisms” or, in other words, a category where the set of all homomorphisms between two objects carries the structure of a category. The most important example is C a t – the category of small categories.
The most straightforward definition of a strict 2-category is relatively simple: it is a category enriched [20] in the (cartesian closed) category C a t. Unfortunately, this definition is not general enough to cover many interesting cases, because it may happen that the composition of 1-cells is associative only up to a 2-isomorphism (for example, the category of spans over S e t is not strict), so one has to weaken the axioms, obtaining a notion of a weak 2-category, sometimes called a bicategory. We refer the reader to [19, 23, 25] for an introduction to the subject of 2-categories and to [2, 24] for category-theoretical terminology.
The starting point of the formal category theory is the observation that one can formulate various categorical notions (for example, monads, adjunctions, Kan extensions) in the language of 2-categories. Changing the underlying 2-category from C a t to some other 2-category \(\boldsymbol {\mathcal {C}}\), it may then happen that these notions give rise to either well-known or new notions, perhaps allowing for a new insight. Let us illustrate this phenomenon by an example:
Example 1
For every category \(\boldsymbol {\mathcal {C}}\), there is a bicategory of spans \(\text {Span}(\boldsymbol {\mathcal {C}})\) (see [24, Chapter XII, Section 7]). If \(\boldsymbol {\mathcal {C}}\) is S e t then the monads in \(\text {Span}(\boldsymbol {\mathcal {C}})\) are small categories. If \(\boldsymbol {\mathcal {C}}\) is the category of groups then the monads in \(\text {Span}(\boldsymbol {\mathcal {C}})\) are the twisted modules (see [24, Chapter XII, Section 8]).
The aim of this paper is to examine the notions “adjunction” and “monad” in the 2-category of monoids in the monoidal 2-category of sets and relations, equipped with the direct product of sets (R e l,×,1). We denote this 2-category of monoids by R e l M o n. This category includes partial monoids (which include effect algebras), as well as small categories (considered as sets of arrows equipped with the composition).
Realistically, one probably cannot hope to achieve some sort of “real result” from these considerations. However, we find it interesting and surprising that some notions and conditions used in quantum logics appear to come from monads and adjunctions in R e l M o n. Moreover, there are other concrete manifestations of these abstract notions in other parts of mathematics, as demonstrated by several examples.
Recently, there were several other papers published in the area of categorical quantum mechanics [1] that concern R e l and R e l M o n. In [15] and [17], authors establish an interesting equivalence between special dagger Frobenius structures in the dagger monoidal category \(\mathbf {Rel}(\boldsymbol {\mathcal {C}})\) and internal groupoids in \(\boldsymbol {\mathcal {C}}\), for a regular category \(\boldsymbol {\mathcal {C}}\). In [8], the results from [15] are extended to describe a correspondence between certain types of generalized groupoids and associative structures in R e l, establishing a link between these abstract results and Poisson sigma models. In [16], monads on dagger categories are investigated. In [28], effect algebras are characterized as certain monoids in R e l, using merely the dagger-compact structure of R e l.
2 The 2-Category of Sets and Relations
In this section, we review some elementary facts concerning the 2-category of sets and relations. Everything in this section is well-known, see [4].
The category of sets and relations, denoted by R e l, is a category whose objects (or 0-cells) are sets and arrows (or 1-cells) are relations \(f\subseteq A\times B\). The composite of arrows f:A→B and g:B→C is the arrow (g∘f):A→C given by the rule
The identity arrow id A :A→A is the identity relation id A ={(a,a):a∈A}.
Note that there is an obvious faithful functor U:S e t→R e l that is identity on objects and takes a mapping f:A→B to its graph
This forgetful functor is a left adjoint, the corresponding right adjoint is the powerset/image functor P:R e l→S e t. This adjunction induces the well-known covariant powerset monad on S e t. R e l is then isomorphic to the Kleisli category for this monad.
Moreover, the category of sets and relations is a 2-category: if h 1,h 2 are relations A→B, then a 2-cell h 1→h 2 is simply the fact that \(h_{1}\subseteq h_{2}\). Thus, every hom-category in R e l is a poset.
As usual, we draw a 2-cell in a commutative diagram as a double arrow, for example
means that \(g_{1}\circ f_{1}\subseteq g_{2}\circ f_{2}\). Note that on the level of elements, the diagram (1) means that
-
for every a∈A and d∈D such that there is a c∈C with (a,c)∈f 1 and (c,d)∈g 1,
-
there exists b∈B such that (a,b)∈f 2 and (b,d)∈g 2.
Besides the structure of a 2-category, R e l carries the structure of a dagger category: there is an involution functor ‡:R e l→R e l op that is identity on objects. For a relation \(f\subseteq A\times B\), \(f^{\dag }\subseteq B\times A\) is the relation given by the equivalence
If A,B∈R e l, then the disjoint union of sets A⊔B is both the product and the coproduct of A,B in R e l. Since R e l lacks some (co)equalizers, it is not a (co)complete category.
Considering R e l as a 2-category, we may look at various category-theoretic notions in R e l.
Recall [23], that in a 2-category a 1-cell f:A→B is left adjoint to a 1-cell g:B→A if and only if there are 2-cells η:id A →g∘f and ε:f∘g→id B such that in the hom-categories [A,B] and [B,A] the diagrams
commute.
However, since every hom-category in R e l is a poset, these conditions are automatically valid whenever there exist 2-cells \(\text {id}_{A}\subseteq gf\) and \(fg\subseteq \text {id}_{B}\). A straightforward reasoning gives us the following fact.
Fact 1
An arrow f:A→B in R e l is a left adjoint to an arrow g:B→Aif and only if f is (a graph of) a mapping A→B and g = f ‡.
Note that this implies that the canonical inclusion S e t→R e l embeds S e t into R e l as the subcategory of left-adjoints in the 2-category R e l.
Recall [29], that a monad in a 2-category is an object A equipped with a triple (s,η,μ), where s:A→A, η:id A →s and μ:s∘s→s such that in the hom-category [A,A] the equations μ∘s η = μ∘η s=id s and μ∘s μ = μ∘μ s hold.
Similarly as for the notion of a left-adjoint, the fact that R e l is enriched in P o s implies that these equations for η and μ are valid whenever η and μ exist. Thus, an s:A→A in R e l is an underlying 1-cell of a monad if and only if \(\text {id}_{A}\subseteq s\) and \(s\circ s\subseteq s\). In other words,
Fact 2
Monads in R e l are preorders.
Indeed, observe that \(\text {id}_{A}\subseteq s\) means that s is a reflexive and \(s\circ s\subseteq s\) means that s is transitive.
In a 2-category, if f is left adjoint to g (in symbols f⊣g), then the quadruple (f,g,η,ε) gives rise to a monad (g f,η,g ε f) on the domain of f.
In the 2-category C a t, every monad arises from an adjunction. This is not true in R e l.
Fact 3
A monad s:A→A in R e l arises from an adjunction if and only if s is an equivalence relation.
Indeed, if f:A→B is a mapping (that means, a left adjoint in R e l), then the monad associated with the corresponding adjunction is f ‡∘f:A→A. This is the equivalence relation on A given by the decomposition of A to the fibers of f, usually called the kernel of f. On the other hand, if ∼ is an equivalence relation on A, then we have an obvious adjunction between A and the quotient A/∼ that in turn gives rise to ∼.
3 Monoids in R e l
It is easy to see that the cartesian product × of sets is a bifunctor from R e l×R e l to R e l.
As × is the product in S e t, it satisfies the coherence conditions for a monoidal category [24, Chapter VII]), so (R e l,×,1) is a monoidal category.
Definition 1
Let \((\boldsymbol {\mathcal {C}},\otimes ,1)\) be a monoidal category. A monoid in \(\boldsymbol {\mathcal {C}}\) is a triple (A,e,∗), where A is an object of \(\boldsymbol {\mathcal {C}}\), e:1→A and ∗:A⊗A→A such that the following diagrams commute
Here, λ,ρ and α denote the (left and right) unitors and the associator of the monoidal category \(\boldsymbol {\mathcal {C}}\).
The triangle diagrams are called the right (left) unit axioms. The pentagon diagram is called the associativity axiom.
The monoids in the category (R e l,×,1) are called relational monoids.
Let us spell out the axioms of a relational monoid in detail. Let (A,e,∗) be a relational monoid. Since e:1→A is a relation, we may identify e with a subset
of A, which we call the set of units of A.
The ∗ is a relation from A×A to A, so it is a subset of (A×A)×A. We shall write \((a_{1},a_{2}){\overset {*}{\mapsto }}a\) to denote the fact that \(((a_{1},a_{2}),a)\in *\subseteq (A\times A)\times A\).
The right unit axiom means that, for every a∈A, there is y∈E A such that \((a,y){\overset {*}{\mapsto }} a\) and, at the same time, whenever there is a y∈E A such that \((a,y){\overset {*}{\mapsto }} b\), then a = b. The meaning of the left unit axiom is similar.
Associativity axiom means that for every quadruple a 1,a 2,a 3,z of elements of A, the following statements are equivalent:
-
there exists w∈A such that \((a_{1},a_{2}){\overset {*}{\mapsto }} w\) and \((w,a_{3}){\overset {*}{\mapsto }} z\);
-
there exists \(w^{\prime }\in A\) such that \((a_{2},a_{3}){\overset {*}{\mapsto }} w^{\prime }\) and \((a_{1},w^{\prime }){\overset {*}{\mapsto }} z\).
We know that every ordinary monoid A in S e t has exactly one unit. In general, this is not true for relational monoids.
Proposition 1
Let A be a relational monoid. For every a∈A, there is exactly one y∈E A (called the right unit of a) such that \((a,y){\overset {*}{\mapsto }} a\).
Proof
By previous remarks, there exists y∈E A such that \((a,y){\overset {*}{\mapsto }} a\). Let us prove that this y is unique.
Let \(y^{\prime }\) be another right unit of a. We see that
By the associativity axiom, there is some z∈A such that
So, in particular, \((y,y^{\prime }){\overset {*}{\mapsto }} z\) and \(y^{\prime }\in E_{A}\). Therefore, by the right unit axiom, y = z. Similarly, by the left unit axiom, \(y^{\prime }=z\) and this implies \(y=y^{\prime }\). □
By a symmetrical argument, there is exactly one left unit for every element of A.
Let us consider some examples of relational monoids.
Example 2
Every ordinary monoid in S e t is a relational monoid.
Example 3
Every hypergroup [30] is a relational monoid.
Example 4
Every small category is a relational monoid: the underlying set of the relational monoid corresponding to a category C is the set all arrows in C. Multiplication is the composition of arrows and the set of units is the set of all identity arrows of C. This observation goes back to the seminal paper [3], see also [15, 21] for more results on the connections between R e l M o n and C a t.
Example 5
As a consequence of the previous example, the set of all comparable pairs in a poset is a relational monoid.
Explicitly, let (A,≤) be a poset, write Q(A) for the set of all comparable pairs of elements of A. In lattice theory, the elements of Q(A) are called quotients. As usual (see for example [14]) we write b/a∈Q(A) to express the facts that that a,b∈A and a≤b.
Let us equip Q(A) with the relation ∗:Q(A)×Q(A)→Q(A) given by the rule \((b/a,d/c){\overset {*}{\mapsto }} (d/a)\) if and only if b = c and the relation e:1→Q(A) that selects the trivial quotients of the type a/a.
Then (Q(A),∗,e) is a relational monoid.
Example 6
Let \(\mathbb R_{0}^{+}\) be the set of all nonnegative real numbers, let \(*:\mathbb R_{0}^{+}\times \mathbb R_{0}^{+}\to \mathbb R_{0}^{+}\) be a relation given by the rule \((a,b){\overset {*}{\mapsto }} x\) if and only if a≤x≤a + b and let \(e:1\to \mathbb R_{0}^{+}\) be a relation that picks out 0 from \(\mathbb R_{0}^{+}\). Then \((\mathbb R_{0}^{+},*,e)\) is a relational monoid. Note that ∗ is not a partial mapping.
For every monoidal category (C,⊗,1), the class of monoids in C comes equipped with a standard notion of morphism between monoids, giving rise to a category of monoids in C. However, this notion does not work in examples we are interested in. It turns out that another notion is more appropriate for our purposes.
For relational monoids A,B and a relation h:A→B, we say that h is a morphism of relational monoids if and only if there are 2-cells
By a category of relational monoids we mean a 2-category in which
-
0-cells are relational monoids,
-
1-cells are morphisms of relational monoids,
-
2-cells are the inclusions of relations, inherited from R e l.
The category of relational monoids is denoted by R e l M o n.
Example 7
The power set \(P(\mathbb N^{+})\) of the set of all positive natural numbers, equipped with a elementwise multiplication, is a monoid with a neutral element {1}. Let us define a relation \(h\colon P(\mathbb N^{+})\to \mathbb N\), where \(\mathbb N\) is the additive monoid of natural numbers, by the rule (X,n)∈h if and only if there is some a∈X such that the length of the prime decomposition of a is equal to n. Then h is a morphism in R e l M o n from \(P(\mathbb N^{+})\) to \((\mathbb N,+,0)\) that is not a graph of mapping.
Since R e l M o n is a 2-category, we may consider adjunctions in R e l M o n. Let A,B be relational monoids, let f:A→B and g:B→A be morphisms in R e l M o n. Then it is easy to check that f is left adjoint to g if and only if f is a mapping and g = f ‡.
From this, we obtain a characterization of left adjoints in R e l M o n.
Proposition 2
A morphism f:A→B of relational monoids is a left adjoint if and only if f is a mapping and the following conditions are satisfied.
-
(L1)
For all b 1 ,b 2 ∈B and a∈A such that \((b_{1},b_{2}){\overset {*}{\mapsto }} f(a)\) there exist a 1 ,a 2 ∈A such that f(a 1 )=b 1 , f(a 2 )=b 2 and \((a_{1},a_{2}){\overset {*}{\mapsto }} a\).
-
(L2)
If x∈A and f(x)∈E B , then x∈E A .
Proof
Clearly, a morphism of relational monoids f is left adjoint in R e l M o n if and only if f is left adjoint in R e l (that means, a mapping) and f ‡ is a morphism in R e l M o n. It remains to observe that the conditions (L1) and (L2) just spell out that the right adjoint f ‡ is a morphism of relational monoids. □
Example 8
Let K be a field. Let K m (X) be set of all monic polynomials over K equipped with the multiplication of polynomials. Then K m (X) is an ordinary monoid in S e t, hence it is a relational monoid. Consider the mapping \(\delta \colon K_{m}(X)\to \mathbb N\) that takes every polynomial to its degree. Then δ is a morphism of monoids. Moreover, δ is a left adjoint in R e l M o n if and only if K is algebraically closed.
Indeed, let δ be a left adjoint in R e l M o n and let p be a monic polynomial of degree greater than 1. Since we have δ(p)=1+(δ(p)−1), property (L1) of Proposition 2 implies that there are p 1,p 2∈K m (X) such that δ(p 1)=1, δ(p 2) = δ(p)−1 and p = p 1.p 2. So p is divisible by a polynomial of degree 1, hence p has a root.
Assume that K is algebraically closed. Let us prove (L1), (L2) of Proposition 2. Let p∈K m (X) and suppose that δ(p) = n 1 + n 2. To prove (L1), we need to find monic polynomials such that p = p 1.p 2, δ(p 1) = n 1 and δ(p 2) = n 2. This is easy, because p is a product of some polynomials of degree 1. Moreover, δ(p)=0 if and only if p=1 (this is why we have to consider monic polynomials). So (L2) holds and hence δ is left adjoint in R e l M o n.
4 Monads in R e l M o n
A monad in the 2-category R e l M o n on a relational monoid (A,∗,e) is necessarily a monad in R e l on the underlying set A. Thus a monad on (A,∗,e) is a preorder on the set A which is, at the same time, an endomorphism of the relational monoid A.
Explicitly, a preorder ≤ on A is a monad in R e l M o n if and only if for all \(a_{1},a_{2},a,a^{\prime }\in A\) such that \((a_{1},a_{2}){\overset {*}{\mapsto }} a\leq a^{\prime }\), there are \(a^{\prime }_{1},a^{\prime }_{2}\in A\) such that \(a_{1}\leq a^{\prime }_{1}\), \(a_{2}\leq a^{\prime }_{2}\) and \((a_{1}^{\prime },a_{2}^{\prime }){\overset {*}{\mapsto }} a^{\prime }\), moreover, for every y∈E A , y≤x implies that x∈E A .Footnote 1 Let us look at some examples of monads in in R e l M o n.
Example 9
Consider the monoid \((\mathbb N,+,0)\). Equip \(\mathbb N\) with the divisibility partial order ∣, meaning that \(a\mid a^{\prime }\) if and only if there is \(b\in \mathbb N\) such that \(ab=a^{\prime }\). Assume that \(a_{1}+a_{2}=a\mid a^{\prime }\). Then there is b such that \((a_{1}+a_{2})b=a^{\prime }\) and, putting \(a^{\prime }_{1}=a_{1}b\), \(a^{\prime }_{2}=a_{2}b\) we see that \(a_{1}\mid a^{\prime }_{1}\), \(a_{2}\mid a^{\prime }_{2}\) and \(a^{\prime }_{1}+a^{\prime }_{2}=a^{\prime }\). Moreover 0∣x implies that x=0. Therefore, ∣ is a monad on \(\mathbb N\).
Example 10
Let Σ be a set. Consider the free monoid Σ∗, consisting of all words over the alphabet Σ, equipped with the concatenation of words. Recall, that a word y is a subword of a word x if we can obtain y from x by deleting the letters at some positions in x. For example, the word abc is a subword of the word cacbacab. For x,y∈Σ∗ write x≥y if and only if y is a subword of x. Then ≥ is a monad on Σ∗.
Indeed, if y is a subword of x 1.x 2, then y = y 1.y 2, where y 1 is a subword of x 1 and y 2 is a subword of x 2. Moreover, x is a subword of the empty word if and only if x is empty. Therefore, ≥ is a monad on the free monoid.
Let E n d o(R e l M o n) be a category, in which
-
objects are all pairs (A, f), where f is an endomorphism f:A→A in R e l M o n
-
a morphism ν:(A,f)→(B,g) is an oplax commutative square
where ν is a morphism of relational monoids.
We write M n d(R e l M o n) for the full subcategory of monads in E n d o(R e l M o n).
Lemma 1
Let A,B be relational monoids, let (f i ) i∈I be a family of morphisms with f i :A→B. Then the relation \(f=\bigcup _{i\in I}f_{i}\colon A\to B\) is a morphism of relational monoids.
Proof
Trivial. □
Theorem 1
Mnd(RelMon) is a reflexive subcategory of E n d o(R e l M o n).
Proof
Let (A,f) be an object of E n d o(R e l M o n)). Write c l(f) for the reflexive and transitive closure of the relation f. As \(cl(f)=\bigcup _{i=0}^{\infty } f^{i}\) is a union of a family of morphisms, c l(f) is an endomorphism of A, so (A,c l(f)) is an object of E n d o(R e l M o n). Moreover, since c l(f) is a preorder, (A,c l(f)) is an object of M n d(R e l M o n). We claim that the morphism
is a reflection, that means, for every object (B,≤) of M n d(R e l M o n) and for every arrow u:(A,f)→(B≤) there is unique dotted arrow such that
commutes. Note that, if the dotted arrow exists, then it must be induced by u. So it suffices to prove that u induces a morphism in E n d o(R e l M o n) from (A,c l(f)) to (B,≤).
We claim that, for all \(n\in \mathbb N\), u induces a morphism in E n d o(R e l M o n) from (A,f n) to (B,≤). For n=0 this is trivial. Suppose that our claim is valid for n = k. Pasting together the 2-cells
gives us the 2-cell
Thus, for all \(n\in \mathbb N\), \((u\circ f^{n})\subseteq (\leq \circ u)\). Taking the union of these inclusions over \(n\in \mathbb N\) gives us the inclusion \((u\circ cl(f))\subseteq (\leq \circ u)\), meaning that u induces a morphism in E n d o(R e l M o n). □
Thus, every endomorphism in R e l M o n generates a monad in R e l M o n.
Example 11
Consider the monoid \((\mathbb N,+,0)\), fix \(k\in \mathbb N\setminus \{0\}\) and the endomorphism \(f_{k}\colon \mathbb N\to \mathbb N\) given by f k (a) = k a. The reflection of the object \((\mathbb N,f_{k})\) of E n d o(R e l M o n) is a monad \((\mathbb N,\leq _{k})\), where the preorder ≤ k is given by the rule a≤ k b if and only if a∣b and b/a is a power of k.
5 Modular Lattices as Monads in R e l M o n
We have seen (Example 5), that for every poset the set of all quotients Q(A) is a relational monoid. Let A be a lattice. There is a canonical partial order ↗ on Q(A) given by the rule b/a↗d/c if and only if a = b∧c and d = b∨c. This partial order plays a central role in the theory of lattice congruences (see [14]).
Recall, that a lattice is modular if and only if, for all x≤y, y∧(x∨z) = x∨(y∧z).
Proposition 3
Let A be a lattice. Then (Q(A),↗) is a monad in R e l M o n if and only if A is a modular lattice.
Proof
The statement that (A,↗) is a monad means that the diagrams
commute. The commutativity of the triangle diagram means that a/a↗c/b implies that b = c. This is easily seen to be true for every lattice A.
The commutativity of the square is equivalent to the following property of the lattice A:
(**) For every \(b/a,c/b,c^{\prime }/a^{\prime }\in Q(A)\) such that \((b/a)\circ (c/b)=c/a\nearrow c^{\prime }/a^{\prime }\) there exists \(b^{\prime }\in A\) such that \(a^{\prime }\leq b^{\prime }\leq c^{\prime }\) and \(b/a\nearrow b^{\prime }/a^{\prime }\), \(c/b\nearrow c^{\prime }/b^{\prime }\).
Let us prove that the modularity of A implies the property (**). Suppose that A is a modular lattice and let \(a,b,c,a^{\prime },c^{\prime }\) be as in the assumption of (**). Let us put \(b^{\prime }=b\vee a^{\prime }\) so that \(b/a\nearrow b^{\prime }/a^{\prime }\). We claim that \(c/b\nearrow c^{\prime }/b^{\prime }\), that means, \(c\vee b^{\prime }=c^{\prime }\), \(c\wedge b^{\prime }=b\). Since \(c/a\nearrow c^{\prime }/a^{\prime }\), we see that
and, applying the modular law with b≤c, we obtain
which means that \(c/b\nearrow c^{\prime }/b^{\prime }\).
Suppose that A is a lattice satisfying the (**) property. Let x,y,z∈A be such that x≤y. We need to prove that y∧(x∨z) = x∨(y∧z). Put a = y∧z, b = x∨(y∧z), c = y, \(a^{\prime }=z\), \(c^{\prime }=y\vee z\). We see that \(a,b,c,a^{\prime },c^{\prime }\) satisfy the assumptions of (**), hence there is a \(b^{\prime }\) such that \(a^{\prime }\leq b^{\prime }\leq c^{\prime }\) and \(b/a\nearrow b^{\prime }/a^{\prime }\), \(c/b\nearrow c^{\prime }/b^{\prime }\). This implies that \(b=c\wedge b^{\prime }=c\wedge (b\vee a^{\prime })\) and therefore
□
For modular lattices A and B and a lattice morphism ν:A→B, we write Q(ν):Q(A)→Q(B) for the mapping given by the rule Q(ν)(a/b) = ν(a)/ν(b).
Corollary 1
Q is a functor from the category of modular lattices to the category M n d(R e l M o n).
Proof
The proof is straightforward and is thus omitted. □
6 Quantum Structures as Relational Monoids
Let (P,+,0) be a partial algebra with a nullary operation 0 and a binary partial operation + . Denote the domain of + by ⊥. P is called a partial abelian monoid if and only if for all a,b,c∈P the following conditions are satisfied:
-
(P1)
b⊥c and a⊥b + c implies a⊥b, a + b⊥c, a+(b + c)=(a + b) + c.
-
(P2)
a⊥b implies b⊥a and a + b = b + a
-
(P3)
a⊥0 and a+0 = a.
A partial abelian monoid P is positive if and only if, for all a,b∈P, a + b=0 implies a = b=0. A partial abelian monoid is cancellative if and only if, for all a,b,c∈P, a + c = a + b implies b = c. A cancellative and positive partial abelian monoid is called a generalized effect algebra.
On every generalized effect algebra, there is a canonical partial order given by the rule a≤c if and only if there is b such that a + b = c. A generalized effect algebra that is upper bounded is an effect algebra. Effect algebras were introduced in [11], the definition we give here is different but equivalent with the original one. See also [22] and [12] for other axiomatizations of effect algebras.
The prototype effect algebra is \((\boldsymbol {\mathcal {E}}(\mathbb {H}),\oplus ,0,I)\), where \(\mathbb H\) is a Hilbert space and \(\boldsymbol {\mathcal {E}}(\mathbb H)\) consists of all self-adjoint operators A of \(\mathbb H\) such that 0≤A≤I. For \(A,B\in \boldsymbol {\mathcal {E}}(\mathbb H)\), A⊕B is defined iff A + B≤I and then A⊕B = A + B. The set \(\boldsymbol {\mathcal {E}}(\mathbb H)\) plays an important role in the foundations of quantum mechanics [5, 27].
It is obvious that every generalized effect algebra is a monoid in R e l M o n. Let A,B be generalized effect algebras. A mapping f:A→B is a morphism of generalized effect algebras if and only if f(0)=0 and for all x,y∈A such that x⊥y we have f(x)⊥f(y) and f(x + y) = f(x) + f(y). Note that every morphism of generalized effect algebras is a morphism in R e l M o n. Thus, the category of generalized effect algebras is a subcategory of R e l M o n.
Example 12
Let (E,+,0) be a generalized effect algebra. What does it mean that the canonical partial order ≥ is a monad in R e l M o n on E? The square diagram means that, for all x 1,x 2,y∈E, x 1 + x 2≥y implies that there are y 1,y 2∈E such that x 1≥y 1, x 2≥y 2 and y = y 1 + y 2. This is a well-known condition, called the Riesz decomposition property [13, 18]. The triangle diagram means that 0≥x implies that x=0, which is true in any generalized effect algebra. Thus, ≥ is a monad on a generalized effect algebra if and only if the generalized effect algebra satisfies the Riesz decomposition property.
Similarly as in R e l, a monad (A,≤) in R e l M o n arises from an adjunction if and only if the preorder ≤ is an equivalence.
Explicitly, this gives us the following conditions:
-
(M1)
∼ is an equivalence.
-
(M2)
The diagram
commutes.
-
(M3)
If x∼y and y is a unit of A, then x is a unit of A.
Proposition 4
[7] Let (A,+,0) be a partial abelian monoid. Let \(\sim \subseteq A\times A\) be a relation satisfying the following:
-
(C1)
∼ is an equivalence relation.
-
(C2)
If x 1 +y 1 exists, x 2 +y 2 exists, x 1 ∼x 2 and y 1 ∼y 2 , then x 1 +y 1 ∼x 2 +y 2.
-
(C5)
If x+y exists and (x+y)∼z, then there are x 1 ,y 1 ∈A such that x 1 ∼x, y 1 ∼y and x 1 +y 1 = z.Footnote 2
Define a partial operation + on the quotient A/∼ by the rule [x] ∼ +[y] ∼ =[x 1 +y 1 ] ∼ , where x 1 ,y 1 ∈A are such that x 1 ∼x, y 1 ∼y and x 1 +y 1 exists. Then + is well defined on A/∼ and (A/∼,+,[0] ∼ ) is a partial abelian monoid.
Let us note that the conditions from Proposition 4 are not necessary for an equivalence to induce a partial abelian monoid structure on A/∼, they are merely sufficient.
Proposition 5
Let (A,+,0) and (B,+,0) be a partial abelian monoids, let f:A→B be a left adjoint in R e l M o n. Then the monad on A arising from the adjunction f⊣f ‡ satisfies the conditions in Proposition 4.
Proof
The monad ∼: = f ‡∘f is an equivalence, so (C1) is satisfied.
Let x 1,x 2,y 1,y 2 be as in the assumptions of (C2). In this context that means f(x 1) = f(x 2), f(y 1) = f(y 2). Since f is a morphism in R e l M o n,
commutes, so the existence of x 1 + x 2 in A implies the existence of f(x 1) + f(x 2) in B and f(x 1 + x 2) = f(x 1) + f(x 2). Similarly, f(y 1 + y 2) = f(y 1) + f(y 2), so f(x 1 + x 2) = f(y 1 + y 2), meaning that x 1 + x 2∼y 1 + y 2.
Suppose that x + y exists and that x + y∼z, that means, f(x + y) = f(z). By Proposition 2 (L1), there are x 1,y 1 such that f(x 1) = f(x), f(y 1) = f(y) and x 1 + y 1 = z, so (C5) holds. □
Proposition 6
Let ∼ be a relation on a partial abelian monoid (A,+,0), satisfying the conditions from Proposition 4 and an additional condition
Then the quotient map f:A→A/∼ given by f(x)=[x]∼ is a left adjoint in R e l M o n and ∼=f ‡ ∘f.
Proof
By [7], f is a morphism of partial abelian monoids, hence it is a morphism in R e l M o n. The condition (C5) implies (L1) and the additional condition implies (L2). □
Thus, we may say that some of the conditions from the paper [7] come from the 2-structure on R e l M o n.
Finally, let us mention another definition, from the classical paper [26].
Definition 2
Let A be a complete orthomodular lattice. A dimension equivalence on A is a equivalence relation on A such that
-
(A)
If a∼0, then a=0.
-
(B)
If a 1⊥a 2 and a 1∨a 2∼b, then there exists an orthogonal decomposition of b, b = b 1∨b 2, such that b 1∼a 1 and b 2∼a 2.
-
(C)
If {a α } and {b α } are pairwise orthogonal families of elements, such that a α ∼b α for all α, then \(\bigvee _{\alpha } a_{\alpha }=\bigvee _{\alpha } b_{\alpha }\).
-
(D)
If a and b are not orthogonal in A then there are nonzero a 1,b 1 in A such that a≥a 1, b≥b 1 and a 1∼b 1.
An orthomodular lattice can be defined as an effect algebra that is lattice-ordered and satisfies the condition a⊥a ⇒ a=0. Note that (A) is (M3), (B) is (M2) and (C) is an infinitary version of (C2). So a dimensional equivalence on an orthomodular lattice is a particular type of monad in R e l M o n arising from an adjunction. It remains an open problem whether we can obtain the conditions (C) and (D) using the 2-categorical machinery within R e l M o n. Especially, the condition (D) remains a puzzle to us.
References
Abramsky, S., Coecke, B.: Categorical Quantum Mechanics. In: Engesser, K., Gabbay, D. M., Lehmann, D. (eds.) Handbook of Quantum Logic and Quantum Structures, p. 261–32, Elsevier, Amsterdam (2009)
Awodey, S.: Category Theory. Number 49 in Oxford Logic Guides. Oxford University Press (2006)
Barr, M.: Relational algebras, pp 39–55. Springer Berlin Heidelberg, Berlin (1970)
Bénabou, J.: Introduction to bicategories Reports of the Midwest Category Seminar, pp. 1–77. Springer (1967)
Bush, P., Grabowski, M., Lahti, P.: Operational Quantum Physics. Springer-Verlag, Berlin (1995)
Bénabou, J.: Catégories relatives. C.R. Acad. Sci. Paris 260, 3824–3827 (1965)
Chevalier, G., Pulmannová, S.: Some ideal lattices in partial abelian monoids and effect algebras. Order 17, 75–92 (2000)
Contreras, I.: Groupoids, Frobenius algebras and Poisson sigma models. In: Mathematical Aspects of Quantum Field Theories pp. 413–426. Springer (2015)
Dvurečenskij, A., Pulmannová, S.: New Trends in Quantum Structures. Kluwer, Dordrecht and Ister Science, Bratislava (2000)
Ehresmann, C.: Catégories structurées. Ann. Sci. École Norm. Sup. 80(3), 349–426 (1963)
Foulis, D. J., Bennett, M. K.: Effect algebras and unsharp quantum logics. Found. Phys. 24, 1325–1346 (1994)
Giuntini, R., Greuling, H.: Toward a formal language for unsharp properties. Found. Phys. 19, 931–945 (1989)
Goodearl, K. R.: Partially ordered abelian groups with interpolation. Amer. Math. Soc, Providence (1986)
Grätzer, G.: General Lattice Theory. Birkhäuser, second edition (1998)
Heunen, C., Contreras, I., Cattaneo, A. S.: Relative Frobenius algebras are groupoids. Journal of Pure and Applied Algebra 217, 114–124 (2013)
Heunen, C., Karvonen, M.: Monads on dagger categories. Theory and Applications of Categories 31, 1016–1043 (2016)
Heunen, C., Tull, S.: Categories of relations as models of quantum theory. In: Quantum Physics and Logic 2015 volume 195 of Electronic Proceedings in Theoretical Computer Science, pp. 247–261 (2015)
Jenča, G., Pulmannová, S.: Quotients of partial abelian monoids and the Riesz decomposition property. Algebra univ 47, 443–477 (2002)
Kelly, G. M., Street, R.: Review of the elements of 2-categories. In Category seminar, pp. 75–103. Springer (1974)
Kelly, M.: Basic concepts of enriched category theory, volume 64. CUP Archive (1982)
Kenney, T., Paré, R.: Categories as monoids in Span, Rel and Sup. Cahiers de topologie et géométrie différentielle catégoriques 52(3), 209–240 (2011)
Kôpka, F., Chovanec, F.: D-posets. Math. Slovaca 44, 21–34 (1994)
Lack, S.: A 2-categories companion. In: Towards higher categories, pp. 105–191. Springer (2010)
Lane, S. M.: Categories for the Working Mathematician. Number 5 in Graduate Texts in Mathematics. Springer-Verlag (1971)
Tom Leinster: Higher operads, higher categories, volume 298. Cambridge University Press (2004)
Loomis, L. H.: The lattice theoretic background of the dimension theory of operator algebras. Memoirs of the AMS, 18 (1955)
Ludwig, G.: Foundations of Quantum Mechanics. Springer-Verlag, Berlin (1983)
Pavlovic, D., Seidel, P.-M.: (modular) effect algebras are equivalent to (Frobenius) antispecial algebras. In: Ross Duncan and Chris Heunen, editors, Proceedings 13th International Conference on Quantum Physics and Logic, Glasgow, Scotland, 6-10 June 2016, volume 236 of Electronic Proceedings in Theoretical Computer Science, pp. 145–160. Open Publishing Association (2017)
Ross Street: The formal theory of monads. Journal of Pure and Applied Algebra 2(2), 149–168 (1972)
Wall, H. S.: Hypergroups. American Journal of Mathematics 59(1), 77–98 (1937)
Acknowledgments
We are indebted to both anonymous referees for valuable comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by grants VEGA 2/0069/16, 1/0420/15, Slovakia and by the Slovak Research and Development Agency under the contract APVV-14-0013.
Rights and permissions
About this article
Cite this article
Jenčová, A., Jenča, G. On Monoids in the Category of Sets and Relations. Int J Theor Phys 56, 3757–3769 (2017). https://doi.org/10.1007/s10773-017-3304-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10773-017-3304-z