Closed pairs of adjunctions between lattices

Galois connections generalize closure conditions like those provided by the adjoint pairs of image/inverse image functions. In the special case of lattices, it can be shown that these closed pairs have certain special properties.

Definition. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection. Then we say that $(A,B)$ is a closed pair if it satisfies one of the equivalent conditions $F(A) \subseteq B$ or $A \subseteq G(B)$.

The point of Galois connections is that these closed pairs can be described by any one of two equivalent conditions. In the case of elementary set theory, these conditions are provided by the image and inverse image functions between sets.

Definition. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection. Let $A \times B$ be the product ordering on $A$ and $B$ defined in the natural way by the category of preorders. Define the partial order on the set of all closed pairs $C(F,G)$ to be the one induced on it by $A \times B$.

The special case of lattices warrants further examination. If there is a Galois connection between two lattices $A$ and $B$ then the product ordering $A \times B$ is itself a lattice, and so $C(F,G)$ is a suborder of a lattice. As we shall see, it is actually the most desirable type of suborder of a lattice.

Theorem. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection of lattices. Then $C(F,G)$ is a sublattice of $A \times B$.

Proof. let $(a,b)$ and $(c,d)$ be closed pairs. Then $F(a) \subseteq b$ and $G(c) \subseteq d$. Consider $(a \vee c, b \vee d)$. Then since $F(a) \subseteq b \subseteq b \vee d$ and $F(c) \subseteq d \subseteq b \vee d$ so both $F(a)$ and $F(c)$ are less then $b \vee d$. Then since $F(a) \vee F(c)$ is the least upper bound of $F(a)$ and $F(c)$ we have $F(a) \vee F(c) \subseteq b \vee d$. Then since $F$ preserves suprema we have $F(a \vee c) = F(a) \vee F(c)$ so that $F(a \vee c) \subseteq b \vee d$ which implies that $(a \vee c, b \vee d)$ is a closed pair. This demonstrates join-closedness. Meet-closedness follows by the dualizing. $\square$

Every sublattice $S$ of a lattice $L$ is associated to a closure operator and an interior operator. The closure of $x \in L$ is the meet of all of its successors in $S$ and its interior is the join of all of its predecessors. In the case of a monotone Galois connection, the computation of closure and interior operators on closed pairs are rather easier.

Definition. let $(a,b)$ be a pair in the product lattice $A \times B$ of a monotone Galois connection $(F,G)$ between lattices. Then the closure of $(a,b)$ is $(a,b \vee F(a))$ and the interior of $(a,b)$ is $(a \wedge G(b),b)$.

The most important Galois connections are actually between lattices, so this gets closer to what monotone Galois connections are actually about. In the special case of the image/inverse image functor, this demonstrates that the closed pairs of a $F: A \to B$ are a sublattice of $\wp(A) \times \wp(B)$. This lattice $\wp(A) \times \wp(B)$ is a distributive lattice, so this means that closed pairs form a distributive lattice, in fact they are the distributive lattice of subobjects of a $F: A \to B$ in the topos $Sets^{\to}$.

Example. let $f : A \to B$ be a multi-valued function in $Rel$, then $f$ induces a single-valued function $f: A \to \wp(B)$ in the topos $Sets$. Then for closed pairs $(a,b)$ we define a lower adjoint of $a$ to be $\{b : \exists c \in a : b \in f(c)\}$ and we define the upper adjoint of $b$ to be $\{d : r(d) \subseteq b \}$. Then closed pairs $(a,b)$ form a lattice: the lattice of subalgebras of a multi-valued function $Sub(f)$.

This basic concept is how we can define specialized subalgebras for hyperstructures, by generalizing the concept of subalgebras from classical algebra. Let $f: X^2 \to X$ be a hypersemigroup. Then a hypersubsemigroup of $f$ will simply be a pair $(S^2,S)$ that forms a closed pair with respect to $f$ which is induced by a subset $S \subseteq X$, and so on. In either case, the fundamental objects of lattice theory like lattices of subobjects come from adjoints.

References:
Galois connection

Functorial theory of Galois connections

We define the following category $C$ as an index category for monotone Galois connections: $C$ has four non-identity morphisms with the properties that $FG$ and $GF$ are idempotent, $FGF = F$ and $GFG = G$. A structure with these composition laws forms a category so $C$ is a well-defined category. We will use this category to examine the theory of Galois connections.

Galois connections as presheaves
Using the category $C$ we can define every monotone Galois connection as a presheaf of preorders in the functor category $[C,Ord]$. These are presheaves by the forgetful functor $F: Ord \to Sets$ from the category of preorders to the topos $Sets$.

Definition. let $(F,G)$ be a monotone Galois connection of preorders $A$ and $B$. Then their presheaf of preorders is defined by the diagram $C$ using the composed component arrows $FG$ and $GF$ as closure and interior operators.

This nicely encapsulates the entire datum of a monotone Galois connection into a single structure presheaf. The dual condition that all presheaves of preorders over $C$ is a monotone Galois connection is of course not true. Instead for that to happen the mappings of the presheaf need to have certain special conditions hold.

Properties of the component morphisms
The four morphisms in the Galois connection diagram $F$,$G$, $FG$, and $GF$ all belong to different types of categories and they all have their own theories associated to them:

• $F$: a residuated mapping (it reflects principal down sets)
• $G$: a coresiduated mapping (it reflects principal up sets)
• $GF$: a closure operator (idempotent, extensive, and monotone)
• $FG$: an interior operator (idempotent, decreasing, and monotone)

Each of these form different types of categories, because they are all closed under composition. The category of partial orders and residuated maps can be used to study the compositional properties of monotone Galois connections.

Presheaf perspective on order theory
It is increasingly my contention that the basic objects of order theory should be presheaves of preorders, and that this presheaf theoretic perspective should be applied to the subject. Let $S$ be a set, then it is associated to a lattice of preorders. A particular elegant construction is that we can associate instead to any presheaf $F: X \to Sets$ a lattice of presheaves of preorders.

I argue that the perspective of studying presheaves of preorders, which are functors $F: C \to Ord$ gives us the best theoretic footing on which to do order-theory from. In the same way that algebraic geometry studies certain presheaves of rings, order theory should be remade for presheaf foundations. In this context, a preorder is a presheaf over the trivial category, a monotone map is a presheaf over $T_2$, an order isomorphism is a presheaf over $K_2$, a Galois connection is a presheaf over $C$, and so on.

Presheaves and their topoi $Sets^C$ should be their basic object of study in any case in either logic or geometry. Topos theory is of the greastest foundational importance, however, when we get around to studying preorders, which are among the most fundamental objects of study then they should be considered by presheaves of preorders. I think the presheaf theoretic perspective will be getting greater acceptance and acknowledgement as time goes on.

Besides algebraic geometry, logic, and order theory it is desirable that presheaves should be used to reinterpret our understanding of computer science. Computation on the machine should be modeled by certain presheaves of memory locations, as this will produce the best results. So the presheaf perspective has the widest degree of applicability in different fields.

References:
Galois connection

The adjoint relationship between order and topology

The categories $Ord$ and $Top$ are the two most basic categories characterized by the adjoint relationships. The two categories $Ord$ and $Top$ are in turn adjointly related to one another, so this continues the basic theme of exploring adjoint relationships in category theory.

Theorem. let $f: (A,\tau_1) \to (B,\tau_2)$ be continuous then $Ord(f) : Ord(A) \to Ord(B)$ is a monotone map of specialization preorders.

Proof. the definition of the specialization preorder yields: \[a_1 \subseteq a_2 \Leftrightarrow \forall O \in \tau_1 : a_1 \in O \Rightarrow a_2 \in O\] We want that this would imply $f(a_1) \subseteq f(a_2)$. This will be demonstrated by using proof by contradiction. Suppose that $f(a_1) \not\subseteq f(a_2)$ then there exists $S$ such that $f(a_1) \in S$ and $f(a_2) \not\in S$. Then $f(a_1) \in S$ implies that $a_1 \in f^{-1}(S)$ and $a_2 \in f^{-1}(S)$ is logically equivalent to the condition that $f(a_2) \in S$ but we know that $f(a_2) \not\in S$ so $a_2 \not\in f^{-1}(S)$.

The inverse image of any open set is open, so $f^{-1}(S)$ is an open set, and it contains $a_1$ but not $a_2$ so it cannot be the case that $a_1 \in f^{-1}(S) \Rightarrow a_2 \in f^{-1}(S)$ which contradicts that $a_1 \subseteq a_2$. So by contradiction it cannot be the case that $f(a_1) \not= f(a_2)$ so $f(a_1) \subseteq f(a_2)$ which implies that $Ord(f) : Ord(A) \to Ord(B)$ is monotone. $\square$

Theorem. let $f: (A, \subseteq_A) \to (B, \subseteq_B)$ be a monotone map, then $f$ reflects upper sets.

Proof. let $I$ be an upper set of $B$ then consider $f^{-1}(I)$ and suppose that $a \in f^{-1}(I)$ then $f(a) \in I$ and now consider a $b$ with $a \subseteq b$. By monotonicity we have that $f(a) \subseteq f(b)$ and since $I$ is an upper set this implies that $f(b) \in I$. This in turn means that $b \in f^{-1}(I)$ so that $f^{-1}(I)$ is an upper set. $\square$

These two theorems are enough to construct an adjoint pair of functors from $Top$ to $Ord$, and these two theorems prove that these relationships are functorial.

• The specialization preorder functor: $P: Top \to Ord$ maps topologies to preorders.
• The Alexandrov topology functor: $T: Ord \to Top$ maps preorders to topologies.

Then these two functors define an adjoint relationship between order and topology. In particular, the Alexandrov topology is the largest topology with a given specialisation preorder. So the relationship $(P,\tau)$ which states that $P$ is a subpreorder of the specialisation preorder of $\tau$ is characterized by the monotone Galois connection $P(\tau) \subseteq P \Leftrightarrow \tau \subseteq T(P)$. So the relationship between preorders and topologies is governed by this adjoint pair of functors.

References:
Specialization order

The adjoint definition of monotonicity

A recent interest of mine is the ubiquity of adjoint relationships in mathematics, and the analysis of which categories are founded on adjoint relationships. The category $Ord$ of preorders and monotone maps is one example. We start by generalizing functions from taking values in points to taking values in preorders.

• Preorder image: let $f: A \to B$ be a function and let $\subseteq_R$ be a preorder on $A$ then define a preorder on $B$ by the preorder closure of $\{(f(x),f(y)): x \subseteq_R y\}$.
• Preorder inverse image: let $f: A \to B$ be a function and let $\subseteq_S$ be a preorder on $B$ then define a preorder on $A$ by $\{(a_1, a_2) : f(a_1) \subseteq_S f(a_2) \}$.

Then the interesting thing is that for any function $f: A \to B$ the definition of a monotonicity of $f$ with respect to two preorders can be defined by a monotone Galois connection expressed in terms of preorders on $A$ and $B$. In particular, for preorders $P$ on $A$ and $Q$ on $B$. \[ f(P) \subseteq Q \Leftrightarrow P \subseteq f^{-1}(Q) \Leftrightarrow \text{f is monotone} \] Every function $f: A \to B$ induces a dual pair of monotone maps $F: Ord(A) \to Ord(B)$ and $F^{-1} : Ord(B) \to Ord(A)$ from the lattices of preorders on $A$ to the lattice of preorders on $B$ which together form adjoint functors. The key realisation here is that preorders can be defined by the adjoint relationship between images/inverse images.

The preorder inverse image construction is particularly useful, because it induces an input preorder from an function to a preordered set. Consider the example of a set-valued function $f: A \to \mathcal{P}(B)$ then the preorder inverse image produces the familiar induced preorder on $A$. Similarly, for a ranking function $f: A \to \mathbb{N}$ this produces a preorder on $A$ by the size of its output numbers, and so on. So preorder images/inverse images are an important constructions in order theory, which can be described by adjoints.

References:
Galois connection
Adjoint functor

The section preorder of the Hom bicopresheaf

Let $C$ be a category and $Hom : C^{op} \times C \to Sets$ its hom bicopresheaf. Then the sections of $Hom$ are precisely the morphisms of $C$, where each section can be represented by a tuple $((a,b), m : a \to b)$ with $m \in Hom(a,b)$. With this construction, we can produce a preordering on $Arrows(C)$ differently, which is interesting for studying the algebro-logical theory of categories.

Theorem. let $C$ be a category then the section preorder of $Hom$ is the $J$ preorder of $C$.

Proof. let $m: a \to b$ and $n: c \to d$ be morphisms in $C$. Then for $m \subseteq n$ in the section preorder of $Hom$ it must be the case that there exists an ordered pair: \[ (i : c \to a, o : b \to d) \in C^{op} \times C \] \[ o \circ m \circ i = n \] This is precisely the definition of $m \subseteq_J n$. It follows that the $J$ preorder of $C$ is the section preorder of $Hom$. $\square$

This constructs the overall morphic preordering of a category $C$ from its hom copresheaf $Hom : C^{op} \times C \to Sets$. There are two other morphic preorders associated with a category $C$: the $L$ and $R$ preorders, both of which are suborders of $J$. These can be constructed by restricting the hom bicopresheaf $Hom: C^{op} \times C \to Sets$ to certain wide subcategories of its index category $C^{op} \times C$. This is the subject of the following lemma.

Lemma. let $F : C \to Sets$ be a functor and let $S \subseteq C$ be a wide subcategory then the section preorder of $F_S$ is a subpreorder of the section preorder of $F$.

Proof. let $(t_1,x_1) \subseteq (t_2, x_2)$ in the section preorder of $F_S$ then $\exists m : t_1 \to t_2 \in S$ such that $F_S(m)(x_1) = x_2$. But since $S \subseteq C$ we have that $m : t_1 \to t_2$ in $C$ such that $F(m)(x_1) = x_2$. So $a \subseteq_{F_S} b$ implies that $a \subseteq_{F} b$, which means that the section preorder of $F_S$ is a subpreorder of that of $F$. $\square$

We can use this lemma to construct the specialized $L$ and $R$ preordering on the morphism set of a category as subpreorders of the $J$ preorder produced by the Hom bicopresheaf.

Theorem. let $C$ be a category and $Hom : C^{op} \times C \to Sets$ its hom bicopresheaf. Then the output action preorder $L$ is the the section preorder of the restriction of $Hom$ to the wide subcategory with only output actions and $R$ is the section preorder of the resrtiction of $Hom$ to the wide subcategory containing only input actions.

Proof. if $m: a \to b \subseteq_L n: a \to c$ this means that there exists $o : b \to c$ with $o \circ m = n$ which is the same as saying there is $(1_a, o)$ in the wide subcategory of $C^{op} \times C$ with only output actions. Similarily for the right preorder $\subseteq_R$, so the $L$ and $R$ preorders are formed by the section preorders of restrictions of the hom bicopresheaf. $\square$

This produces an interpretation of the morphic preorders of a category $C$ that is much more suitable for our purposes. We can now define the morphic preordering of $C$ to simply be the object preordering of the category of elements of the hom functor. We have now two types of preorders on a category, both of which are object preorders of their respective categories:

• The preorder on $Ob(C)$ is the object preorder of $C$.
• The preorder on $Arrows(C)$ is the object preorder of the category of elements of the hom functor.

This is better because it is much more natural to work with object preorderings then any other type of preorder. Preorders themselves are defined as object preorders, and the composition operation of a category can add extra context to the logic of a preorder. Categories can be used to describe the algebraic laws of motion of preorders.

References:
Hom functor

Congruence lattices of quivers

Let $Q$ be a multi-directed graph, then $Q$ is associated to a lattice of congruences $Con(Q)$ which can be constructed using new and original algorithms of mine. A quiver can be seen as a presheaf over the following category: This category I call the double arrow category, because it has a repeated pair of arrows going from the first object to the second one. As a category, it has an underlying quiver $Q$. Its congruence lattice $Con(Q)$ looks like this: This defines the congruence lattice of a multi-directed graph, but the same could be applied to any directed graph without repeated edges. Consider the directed cycle graph $C_3$ on three elements: Then the congruence lattice of the directed cycle graph $Con(C_3)$ has this interesting structure: This different sort of congruence lattice for $Con(C_3)$ might look unexpected at first, but actually it makes perfect sense. It is formed by adjoining two different five elements congruence lattices of a three element set to one another. Recall that the congruence lattice $Con(S)$ of a set with three elements has the structure [1,3,1] and that it has five elements. The reason for this appearance is that the cycle $(0,1),(1,2),(2,0)$ has this unique property is that every vertex is in any two of its edges. Therefore, in order to form any congruence of $C_3$ you must first collapse all of its vertices.

We have shown that every directed multigraph is associated with a congruence lattice $Con(Q)$, but let us not forget that every object of a congruence lattice is associated with a quotient. In the case of $C_3$ all of the different congruences of the same size and height have the same quotient, and so all the different quotients of $C_3$ can be formed one after another. They are formed in five steps: starting with $C_3$, collapsing a pair of objects, then collapsing another pair of objects, then collapsing a pair of morphisms, then collpasing the last pair of morphisms.

We have now seen the congruence lattice $Con(C_3)$ of a directed cycle graph on three elements as well as all of its quotients. It had the unique structure of a weak order. It would be interesting to see if $C_4$ has the same structure of congruences: Then the congruence lattice of $Con(C_4)$ looks as displayed below. It does not have the property that it is two partition lattices adjoined to one another, because it doesn't have the property that any vertex is contained in any pair of edges. Nonetheless, you still have to collapse at least three objects before you can collapse one edge, so you can still visibly see the fifteen element partition lattice on four elements on the bottom connected to another one above it but now with some mixed congruences between them:

Another directed graph with an interesting congruence lattice is the strict total order $T_3$. It has a congruence lattice $Con(T_3)$ as displayed below. The reason for this interesting structure is that when you collapse two lower objects you then get repeated edges from the lower class to the upper one. These repeated edges can then be collapsed without equating more objects, and the same works in the other direction from above. So you get this interesting self dual structure in the form of a lattice. We have considered some interesting cases of directed graphs, but what if you have a repeated edges. In that case, we can see that repeated edges actually do have an effect on the appearance of the congruence lattice. A directed multigraph with repeated edges has as an atomic congruence a partition that equates two parallel edges rather then two vertices. So the atoms of such a congruence lattice don't necessarily generate a partition lattice, so they appear different. This is a non-thin quiver, so it has an atomic congruence that is not part of any partition lattice. It is the unique atom that is not a part of an element that covers three atoms. Consider two disconnected edges: Then their congruence lattice is displayed below. Initially, it just looks like a partition lattice on four elements, but there is a little bit more that meets the eye. There is one special congruence on the disconnected pair of edges: the one that equates both the minimal edges and that equates both the maximal edges. Then the two arrows can also be equated to get a parallel pair between two objects as a quotient. The disjoint arrows map is a function, but it is perhaps not a transformation because it is not closed. But we can make it one like this: Simply adding these two edges creates a much larger congruence lattice, which demonstrates how these congruence lattices tend to grow quite large for even small directed graphs: Topos theory generates congruence lattices for far more objects then classical lattice theory, which would only generated them for lattices or semilattices. We can now generate them for any poset. Consider the following poset: This poset is known as $[1,2]$ and its congruence lattice $Con([1,2])$ is of the following form: These congruence lattices are already getting quite larger. We can certainly go deeper, and create congruence lattices for even larger directed graphs and we can even run computations on them, but they will get too big for Graphviz to display nicely I think so we'll have to leave it at this. The congruence lattices generted so far should give you an inkling of the subject.

All these congruence lattices were generated by using the topos $Quiv$. This is just a small sampling of what can be done with topos theory, within only part of one subject. Topos theory is a logical theory of everything, and its techniques are the most widely applicable.

Subobject lattices of presheaves

Functions standout as among the most ubiquitous of mathematical structures. Ever since I first encountered functions, I have sought to reason about them logically. At first I met with failure. There was no overall framework available to me to fit everything together. The solution then occurred to me in topos theory.

We start by reasoning logically about presheaves, and then we can consider functions to be presheaves using $Sets^{\to}$. Within presheaf theory itself, we tend to focus first on subobject lattices of presheaves, but equally fundamental is to consider their dual categorical logic of quotients. The later is responsible for some of the most exciting developments in topos theory. Today we focus on the former.

Every step that we make in topos theory brings us closer to understanding the big picture view provided by topoi. With topos theory, we can build an overall unified theory of mathematical structures. This should be a topic of further research, so without further ado lets get started.

Sections
A copresheaf (set-valued functor) $F : C \to Sets$ is a special type of structured set whose members are sections. Sections are defined as certain ordered pairs.

Definition. Let $F : C \to Sets$ be a presheaf. Then a section $(o,m)$ is an ordered pair with $o \in Ob(C)$ and $m \in F(o)$.

A morphism of copresheaves is then a structured function on sections. Let $F : C \to Sets$ and $G : C \to Sets$ be copresheaves and let $\tau : F \to G$ be a natural transformation between them. Then $\tau(o,m) = (o, \tau_o(m))$ where $\tau_o$ is the component function of the natural transformation associated with the object $o \in Ob(C)$.

The action preorder of a copresheaf:
We associated to the set of sections of a presheaf a preorder on sections, that generalises the familiar action preorder of an MSet used to define Green's relations.

Definition. let $F : C \to Sets$ then we can define a binary relation $\subseteq$ on sections. \[ (o_1, m_1) \subseteq (o_2, m_2) \] \[ \exists g : o_1 \to o_2 \in Arrows(C) \text{ and } F(g)(m_1) = m_2 \] Proposition 1. The binary relation $\subseteq$ is a preorder.

Proof. let $(o,m) \in F$ then $\exists 1_o : o \to o \in Arrows(C)$ with $1_o(m) = m$ so that implies that $(o,m) \subseteq (o,m)$ with means that $\subseteq$ is reflexive. On the other hand, suppose that $(a,l), (b,m), (c,n)$ are sections of $F$ with $(a,l) \subseteq (b,m)$ and $(b,m) \subseteq (c,n)$. Then since $(a,l) \subseteq (b,m)$ there exists a morphism $f : a \to b$ with $f(l) = m$. Then because $(b,m) \subseteq (c,n)$ there exists a morphism $g: b \to c$ with $g(m) = n$.

As $f(l) = m$ and $g(m) = n$ by substitution we have that $g(f(l)) = n$. By the same token $(g \circ f)(l) = n$. So there exists a morphism $g \circ f : a \to c$ with the property that $g(f(l)) = n$ which implies that $(a,l) \subseteq (c,n)$. It follows that $\subseteq$ is transitive. Since it is both transitive and reflexive it is a preorder. $\square$

The process by which the transitivity of $\subseteq$ is ensured is the same process by which the underlying binary relation of a category is ensured to be a preorder. Each category is defined to be an algebraic extension of a preorder. The fact that $\subseteq$ is a preorder saves us from having to do a transitive closure, which aids us in computation of the action preorder.

The relationship to the object preorder:
Categories are deeply intertwined with preorders. This fact starts on the most basic level with the object preorder, which preorders the set $Ob(C)$ of objects of a category.

Definition. let $C$ be a category and $a,b \in Ob(C)$ then $a \subseteq b$ provided that $\exists f :a \to b \in Arrows(C)$.

This suggests a basic relationship between the preorder on sections of a copresheaf and the preorder on objects of its index category.

Definition. let $F: C \to Sets$ be a copresheaf then the mapping $t: Sections(F) \to Ob(C)$ that takes any section $(o,m)$ to its object part is a forgetful functor from the section preorder to the object preorder.

It follows that $t$ is a monotone map. As a consequence, we can always look to the object preorder of the index category as a first step to understanding the section preorder, so when we implement an algorithm for checking for membership in the action preorder relation, the first step will be to check inclusion in the object preorder.

Implementing the action preorder:
The definition of the section preorder of a copresheaf suggests a general mechanism for computing the preorder for a given copresheaf over an index category $C$. In particular, for any pair $(o_1,m_1)$ and $(o_2,m_2)$ we can compute their membership in the section preorder using the following algorithm:

• check that $o_1 \subseteq o_2$ in the object preorder of $C$
• compute the hom class $Hom(o_1, o_2)$ then loop through its members and check if a member $f$ in the hom class if $f(m_1) = m_2$. If such a member does satisfy this condition exit the loop and return true, otherwise return false.

This suggests the main requisite mechanism for computing the section preorder is the prior definition of a computable hom classes function $Hom(a,b)$ for objects of the index category $C$. The object preordering can easily be defined them from the emptyness of the hom class $Hom(a,b)$ or it can be defined separately if a quicker mechanism is available.

In the special case where in the index category $C$ is itself a preorder, then we can cut out the loop entirely as every hom class has a unique element. Then $(o_1,m_1) \subseteq (o_2,m_2)$ provided that $o_1 \subseteq o_2$ and $f(m_1) = m_2$ for the unique $f \in Hom(o_1,o_2)$. It follows naturally that preorders are a special case where in the action preorders on their sections are made amenable to easy computation.

Recovering the action preorder of a monoid:
Let $M$ be a monoid and $F: M \to Sets$ be a copresheaf on $M$ with underlying set $S$. Then we have that $a \subseteq b$ in $S$ provided that $\exists m \in M : ma = b$. Then this action preorder is isomorphic to the action preorder of sections of $F$ as a copresheaf. This demonstrates that this familiar concept is monoid theory is actually just a special case of something from presheaf theory.

The action preorder on $S$ is taken by defining that $a \subseteq b$ provided that $\exists m \in M : ma = b$. It is customary that a monoid has a single object which we call $0$ for the non-negative unsigned integer. So now all sections of the MSet are of the form $(0,x)$ for any $x \in S$. Then we have that $(0,a) \subseteq (0,b)$ provided that there exists $m : 0 \to 0$ in the monoid $M$ such that $m(a) = b$ which recovers the definition of the action preorder of the MSet. From now on we will simply refer to the action preorder of a copresheaf.

Partially ordered endotrivial categories:
A category $C$ is called endotrivial provided that $\forall x \in Ob(C)$ we have that $|End(C)| = 1$, so that the only morphism in any endomorphism monoid is the identity.

Theorem 1. let $C$ be an endotrivial category with an antisymmetric object preorder. Then the section preorder on a copresheaf $F : C \to Sets$ over $C$ is antisymmetric, and therefore it is a partial order as well.

Proof. suppose that $(o_1,m_1) \subseteq (o_2,m_2)$ and $(o_2,m_2) \subseteq (o_1,m_1)$. Then by the relationship to the object preorder, we have $o_1 \subseteq o_2$ and $o_2 \subseteq o_1$ but since this is an endotrivial preorder we have $o_1 = o_2$. So this means the sections are of the form $(o,m_1)$ and $(o,m_2)$ now in order for $(o,m_1) \subseteq (o,m_2)$ we must have that there exists $f \in Hom(o,o)$ such that $f(m_1) = m_2$.

However, $C$ is endotrivial so the hom class $Hom(o,o)$ contains only the identity $1_o$. Therefore $f = 1_o$ which implies that $f(m_1) = m_1$ and since $f(m_1) = m_2$ as well this implies that $m_1 = m_2$. Then substituting this back into our definition of the sections we get $(o_1,m_1)$ equals $(o_2,m_2)$. By the fact that the only symmetrically related pairs in $F$ are equal ones, we see that the section preorder $\subseteq$ is antisymmetric. $\subseteq$

Corollary 1. let $F: C \to Sets$ be a copresheaf over a partial order $C$. Then the section preorder of $F$ forms a partial order.

Example 1. let $Quiv$ be the topos of quivers. Then $Quiv$ is isomorphic to $Sets^{T_2^*}$ which is the copresheaf topos over the partially ordered endotrivial index category $T_2^*$. It follows that given any quiver $Q$ we have that its sections are partially ordered, with the condition that any morphism is dependent upon its source and target objects.

Example 2. let $(\mathbb{N},+)$ be the commutative monoid of addition over the non-negative integers. Then consider the self induced action $\mathbb{N}$-set of $\mathbb{N}$ acting on itself. Then since $(\mathbb{N},+)$ is a commutative J-trivial monoid, its self induced action preorder is also a partial order. However, $(\mathbb{N},+)$ is clearly not endotrivial. This demonstrates that the converse condition isn't true, as there are other types of copresheaves with antisymmetric section preorders.

The subobject lattice of a copresheaf
The nice thing about the section preorder of a copresheaf, a concept which introduced here, is that it completely determines the distributive subobject lattice of a copresheaf.

Proposition 2. Let $F : C \to Sets$ be a copresheaf. Then the subobject lattice of $F$ is isomorphic to the lattice of upper sets of its section preorder.

Proof. suppose that $F: C \to Sets$ is a presheaf with each $x \in Ob(C)$ associated to a set $F(x)$. Define another mapping, $\tau$ that takes each $x$ to some set $\tau(x) \subseteq F(x)$. Then in order for the subsets represented by $\tau$ to be a subobject of $F$ it must be the case that for each $a \in \tau(x)$ then for each morphism $m: x \to y$ starting at $x$ we have that $m(x) \in \tau_y$ so that $\tau$ is an upper set of the section preorder. In other direction, we can take each $\tau$ to form an inclusion function $\tau(x) \hookrightarrow F(x)$ and these components of a natural transformation determine a subobject of $F$. $\square$

Theorem 2. Let $F : C \to Sets$ be a copresheaf. Then the subobject lattice $Sub(F)$ is distributive.

Proof. By order theory we know that the upper sets of a preorder always form a distributive lattice. By proposition 2, we know that $Sub(F)$ is the lattice of upper sets of the section preorder. Therefore, $Sub(F)$ is distributive. $\square$

Distributive lattices tend to emerge from the lattice of upper sets of a preorder, for example recall that the lattice $Con(L)$ of congruences of a finite lattice is simply the upper sets of the induced preorder on atomic intervals. This new theorem defines the distributive lattice on subobjects of copresheaf in terms of the preorder on its section elements.

Copresheaves over groupoids
Lemma 1. Let $G$ be a groupoid and let $F: G \to Sets$ be a copresheaf. Then the section preorder on $F$ is symmetric.

Proof. suppose that $(o_1,m_1) \subseteq (o_2,m_2)$ then we have that there exists $f : o_1 \to o_2$ such that $f(m_1) = m_2$. By the fact that $G$ is a groupoid there also exists $f^{-1} : o_2 \to o_1$ and that $f^{-1}(f(m_1)) = f^{-1}(m_2) = m_1$. It follows that $f^{-1}(m_2) = m_1$. This implies that $(o_2,m_2) \subseteq (o_1,m_1)$. It follows that $\subseteq$ is symmetric. $\square$

Theorem 3. Let $G$ be a groupoid. Then the topos $Sets^G$ is boolean.

Proof. let $F \in Sets^G$ be a coresheaf $F : G \to Sets$ then by lemma 1 the section preorder on $F$ is symmetric. The upper sets of a symmetric preorder always form a boolean algebra, and so now by proposition 2 it follows that $Sub(F)$ is a boolean algebra. This means that $Sets^G$ is a boolean topos. $\square$

The restriction partial order on a sheaf:
Let $X$ be a topological space, then a sheaf on $X$ is a special type of presheaf $F : X \to Sets$ on the partially ordered set formed by $X$. By corollary 1, it follows that the section preorder on $F$ is antisymmetric and therefore it forms a partial order. We can simply call this the restriction partial order on the sheaf.

Definition. let $F: X \to Sets$ be a topological sheaf. Then the section preorder on $F$ is a partial order called the restriction order on $F$.

Theorem. let $F: X \to Sets$ be a topological sheaf and suppose that $s_i \in F(U_i)$ is a gluable family of sections (so that the $U_i$ form an open cover and the sections meet on intersections) then the glue $s$ is a least upper bound of the $s_i$ in the restriction partial order.

Proof. the glue $s$ has the property that $s_{U_i} = s_i$ for each $i \in I$ so it follows that $s_i \subseteq s$ for each $i \in I$ with respect to the restriction ordering of the sheaf. The gluing condition requires that the $U_i$ form a covering family, but then $U$ forms a least upper bound of the $U_i$. So by the relationship to the object preorder any other section must have an object at least as big as $U$ so no upper bound can be smaller then $s$. Therefore, $s$ is a least upper bound of the $s_i$ and furthermore by the locality condition it is a unique least upper bound of the $s_i$. $\square$

A sheaf is a partially ordered set of sections with a semilattice-like operation of gluing that produces the join of sections under certain conditions. A sheaf can almost always be considered to be like a set of functions, in which case the restriction ordering is simply the partial ordering on functions, that says that one function is a part of another if it is a restriction of it.

Furthermore, in that case the gluing operation is simply the special case of the union of two functions which can only exist when the two functions meet on their common intersections. As the union operation is a least upper bound, it immediately follows that the gluing is a special case of a least upper bound operation on a poset. As we see here, this follows directly from the abstract definition of a sheaf.

Set relations and flow models

In this post I will explain the role of morphisms in the allegory $Rel$ in the topos theoretic model of computation. The topos theory of computation occurs in layers starting with the theory of congruences in copresheaf topoi and then following that there is a higher level abstraction based upon flow models over production decompositions.

Topoi as foundations of computation:
The topos theoretic foundations of computation used in the Locus project are based upon congruence lattices in copresheaf topoi. In particular, we have the following distinction:

• Memory locations: congruences in $Sets$
• Data dependencies: congruences in $Sets^{\to}$

The advantage of this approach is its level of power and applicability. Congruences in the topos $Sets$ can be used not only to model individual memory locations, but also any property of a structure. Congruences in $Sets^{\to}$ provide an equally powerful means of handling data dependencies.

The next level of abstraction:
The congruence lattices of sets and functions are in general not distributive. On the other hand, subobject lattices are always distributive in any topos. We would like to handle the congruence lattices of sets and functions in a manner similar to more familiar distributive lattices and boolean algebras. So a second abstraction level makes this possible.

We establish the second layer of abstraction by reference to the allegory $Rel$ of sets and set relations. Memory locations are modeled by sets of places and data dependencies are modeled by relations between places. This produces a second layer in the model of memory and two classes are implemented to handle this second layer.

• Product decompositions: objects in $Rel$
• Flow models: morphisms in $Rel$

Memory is then modeled in a second layer of abstraction based upon $Rel$. To make this possible, we associate distributive lattices to the sets and relations of $Rel$. Let $S$ be in $Ob(Rel)$ then $Sub(S)$ is simply the boolean algebra of all subsets of $S$. On the other hand, suppose $R : A \to B$ is a morphism in $Rel$ then we define a subalgebra of $R$ by: \[ F = \{(X,Y) : \forall x \in X: R(x) \subseteq Y \} \] This generalises the distributive subalgebra lattice of a function $f : A \to B$ to relations. We define a closure operation by: \[ cl(X,Y) = (X, Y \cup \bigcup_{x \in X} R(x)) \] Then the data of this closure operation on the family of subalgebras with the natural ordering on pairs of sets $(F, cl)$ produces the distributive lattice of subalgebras of a relation. In fact, given a relation $R$ in $Rel$ and $(X,Y)$ a subalgebra we have a restriction: \[ R_{(X,Y)} : X \to Y \] Where $R_{(X,Y)}(x) = R(x)$ so that the restriction simply changes the source and target objects of the morphism. We need now to define special image and inverse images of sets in the allegory $Rel$ based upon the distributive lattice of subalgebras.

• Image: let $R : A \to B$ be a relation and $X \subseteq A$ then the image is defined by $R(X) = \bigcup_{x \in X} R(X)$.
• Inverse image: let $R : A \to B$ be a relation and $Y \subseteq B$ then the inverse image $R^{-1}(Y) = \{x \in X : R(X) \subseteq Y\}$.

The point of this dichotomy is that for $X \subseteq A$ the image $(X,R(X))$ is the smallest pair such that $(X,R(X))$ is a subrelation. On the other hand, for any $Y \subseteq B$ the inverse image $R^{-1}(Y)$ is the largest pair such that $(R^{-1}(Y),Y)$ is a subrelation. This reflects the role that images and inverse images play in constructing the distributive lattice of subobjects of a function.

A distinction occurs between the inverse image and the converse relation image, that does not occur on the level of functions. We define the converse relation image in the following manner: \[ R^C(Y) = \bigcup{y \in Y} : \{ x \in X : y \in r(X) \} \] This does not have anything to do with the construction of the distributive subalgebra lattice, but it is simply a consequence of the converse involution in the dagger category $Rel$. By clearly distinguishing between the types of relation images and constructing the distributive lattices $Sub(R)$ we are ready to start working with the second layer of abstraction.

Interfacing between the two abstraction levels:
We essentially want to have an abstraction level over memory locations and data dependencies that uses the allegory $Rel$ and the mechanisms we previously described. In order to do that, we need to relate sets to set congruences and relations to function congruences.

Definition. let $I$ be generating system for a boolean algebra of $Part(A)$ whose partitions all form direct products of one another then $I$ forms a product decomposition of $A$. This produces a correspondence from sets to partitions $f_I: \wp(I) \to Con(A)$.

Definition. let $f : A \to B$ be a function and suppose that $I$ and $J$ are product decompositions of $A$ and $B$. Then a flow model $F$ is a morphism $m : J \to I$ in the allegory $Rel$ such that for each $j \in J$ we have that $(f_I(m(j)),f_J(\{j\}))$ is a function congruence of $f$.

This provides a contravariant correspondence, as flow models from $A$ to $B$ are defined by set relations from locations in $B$ to locations in $A$. We now have two different monotone maps of lattices: \[ f_I: \wp(I) \to Con(A) \] \[ F: Sub(m) \to Con(f) \] In addition, we can use this abstraction to model partition images and inverse images in terms of their relational counterparts. Given a partition of $B$ indexed by $S$ in $J$ then its partition inverse image is the relational image of $m$ and dually for a partition of $A$ indexed by $S$ in $I$ its partition image is the relational inverse image of $m$ over that index set.

As a result, although we are able to model the theory of data dependencies using the allegory $Rel$ rather then a base topos, the topos theoretic foundations are always there and available to us by conversion. The abstractions provided over $Sets$ and $Sets^{\to}$ by $Rel$ can only ever produce subsets of the congruences of sets and functions.

There can be many different abstraction layers over our foundation in the topos of functions $Sets^{\to}$. For example, in semigroup theory we have an abstraction we have an abstraction layer whereby a congruence $C$ is defined by a single set rather then pairs of sets $(C^2,C)$. There can be many different abstraction layers, but as long as we keep ourselves firmly footed within the topos theoretic foundations in $Sets$ and $Sets^{\to}$ then we will always have a common interface for reasoning about different abstraction layers.

Compositionality:
Suppose that we have a function with a flow model $(f,m)$ in $Sets \times Rel^{op}$. Then the flow models describing distributive lattices of respective functions, compose with one another. The contravariance of the composition of flow models is a result of the obvious forgetful functor to the opposite category: \[ F: Sets \times Rel^{op} \to Rel^{op} \] The flow models of product decompositions provide a composable logic for reasoning about the relations between memory locations, which is modeled on an underlying topos theory. By maintaining flow models under composition we can maintain as much information about function congruences as possible.

References:
[1] The allegory Rel of sets and relations

[2] The topos Set of sets and functions

Functorality of the Alexandrov topology

A number of set systems associated to structured sets either preserve or reflect substructures and they therefore form functors to categories of hypergraphs or topologies. The Alexandrov topology consisting of all lower sets (respectively upper sets) of a poset is a basic example.

Lemma 1. Let $f: A \to B$ be a monotone map of posets. Let $L$ be a lower set of $B$, then $f^{-1}(L)$ is a lower set of $A$.

Proof. suppose that $a \in f^{-1}(L)$ then $f(a) \in L$ and further suppose that $b \subseteq a$. By the fact that $f$ is monotone we have $f(a) \subseteq f(b)$ and now by the fact that $f(b) \in L$ and $L$ is a lower set, we have that $f(a) \in L$. Which implies that $a \in f^{-1}$ so in short $b \subseteq a \text{ and } a \in f^{-1}(L)$. Therefore, $f^{-1}(L)$ is a lower set.

The dual proposition that monotone maps preserve lower sets is trivially false, consider $F : 1 \to 3$ that maps the singleton poset to the middle element of an ordered triple. Then this map preserves neither upper sets or lower sets. So the Alexandrov topology is not functorial to the category of topologies and open maps, but it is for the more relevent category $Top$ of topologies and continuous maps.

Theorem 1. $F: Ord \to Top$ is a covariant functor from the category of thin categories to the category of topological spaces and continuous maps.

Proof. (1) let $P$ be a thin category then $F(P)$ is the topology generated by the map of singletons that produces all predecessor elements and this is trivially an Alexandrov topology (2) and by lemma 1 for any functor $f : A \to B$ we have that $F(f) : F(A) \to F(B)$ is a continuous map. Finally (3) $F$ preserves composition by preserving underlying functions so $F$ is functorial. $\square$

The fact that monotone maps reflect lower sets (respectively upper sets) is simply a long line of a group of theorems dealing with the preservation and reflection of open sets. For example, the fact that the pre image of a prime ideal is a prime ideal is used in commutative algebra to describe the functoriality of the topology $Spec(R)$. We see that order ideals are not that different from ring ideals.

Visualisation of lattice polynomials

The basic units of algebraic logic are lattice polynomials, while the basic units of algebraic geometry are ring polynomials. Unlike their ring counterparts, lattice polynomials can form a tree structure. This leads to the possibility of using tree visualisation methods on lattice polynomials. In order to make this visualisation more effective, I developed a simple color scheme:

• Meet: red
• Join: green

Green is typically considered a positive color while red is a negative color. So it makes sense that the join should be green while the meet is red. Every non-leaf node in a lattice polynomial is either a meet or join term, and so can be coloured coded accordingly. Due to associativity, a well formed lattice polynomial should always alternate between green and red at each level. In order to implement this, I used dorothy to create graphviz files from lattice polynomials.

(require '[dorothy.core :as dot])
(require '[dorothy.jvm :refer (render save! show!)])

(defn get-coordinates
  "Get the coordinates of the leaf nodes of an S-expression."
  [coll]

  (if (not (seq? coll))
    '(())
    (apply
      concat
      (map
        (fn [i]
          (map
            (fn [c]
              (cons i c))
            (get-coordinates (nth coll i))))
        (range (count coll))))))

(defn get-coordinate-value
  "Get the value of an S-expression at the given coordinate."
  [coll coordinate]

  (if (empty? coordinate)
    coll
    (get-coordinate-value
      (nth coll (first coordinate))
      (rest coordinate))))

(defn create-digraph
  "Create a digraph from the arithmetical form 
   of a lattice polynomial."
  [coll]

  (letfn [(create-vertex [coll coordinate]
            (let [v (get-coordinate-value coll coordinate)
                  cstr (.toString coordinate)]
              (cond
                (= v '*) [cstr {:label     ""
                                :fillcolor "crimson"
                                :style     "filled"}]
                (= v '+) [cstr {:label     ""
                                :fillcolor "green"
                                :style     "filled"}]
                :else [cstr {:label (.toString v)}])))
          (create-vertices [coll coordinates]
            (concat
              (map
                (partial create-vertex coll)
                coordinates)))
          (find-next-leaf [coll coordinate]
            (if (seq? (get-coordinate-value coll coordinate))
              (find-next-leaf coll (concat coordinate (list 0)))
              coordinate))
          (successor-edges [coordinate]
            (let [fixed-coordinate (if (&= (count coordinate) 1)
                                     '()
                                     (butlast coordinate))
                  parent-sequence (get-coordinate-value 
                                    coll 
                                    fixed-coordinate)]
              (map
                (fn [i]
                  [(.toString 
                     (seq (concat fixed-coordinate (list 0))))
                   (.toString 
                     (seq (find-next-leaf 
                            coll 
                           (concat fixed-coordinate (list i)))))])
                (range 1 (count parent-sequence)))))
          (create-edges [coll coordinates]
            (apply
              concat
              (for [i coordinates
                    :when (= (last i) 0)]
                (successor-edges i))))]
    (let [coordinates (get-coordinates coll)]
      (vec
        (concat
          (create-vertices coll coordinates)
          (create-edges coll coordinates))))))

In order to demonstrate this approach to lattice polynomial visualisation, I have prepared a couple of examples. In order to encode a lattice polynomial as an S-expression, I use the arithmetical syntax of defining the meet operation as multiplication and the join operation as addition. This follows from the fact that the meet operation is the product operation in a thin category, while the join operation is the coproduct.

(def expoly1
  '(+ (* a b)
      (* c (+ d e))))

This simple approach can be used to visualize arbitrarily large lattice polynomials, with an arbitrary number of variables and operations nested to any depth. Therefore, our second example is a bit larger then the first.

(def expoly2
  '(* (+ (* a b)
         (* c d)
         e)
      (+ (* f g) h)
      (+ i j k)
      l))

This demonstrates a way of visualising lattice polynomials in algebraic logic. Of course, we can often perform visualisations of a different sort for the ring polynomials in algebraic geometry: the visualisation of algebraic varieties formed by ring polynomials. In either case, visualisation techniques will always be important in logic and geometry.

Algebraic laws of motion

The three subjects of order theory, semigroup theory, and category theory clearly form a common whole, described by the algebraic laws of motion. As algebraic descriptions of change, the closest relatives of categories are monoid actions. A common framework for describing the algebraic preorders associated to categories, monoids, etc will be presented based upon the laws of motion.

This is distinguished from the geometric theory of motion in a Lorentzian manifold. In that context, the laws of motion dictate that objects can only move along time-like future-pointing curves. This creates a geometric preorder on a Lorentzian manifold. As a consequence, there are both algebraic and geometric theories of motion.

Transformations:

Functions are among the most basic units of mathematics alongside sets. We will start by describing the changes in a set by functions from the set back to itself. This is generalized to include partial transformations, which allow us to describe changes on only parts of a set back to themselves.

• Transformations
• Permutations
• Partial transformations
• Charts

A first realization is that each of these units of change produce different types of semigroups. Permutations produce groups which are structures whose motions are reversible. Inverse semigroups of charts are their partial transformation counterpart. Total and partial transformations both lead to monoids.

Monotone Galois connections:

The different types of actions by transformations, permutations, charts, etc all necessarily produce preorders that describe how they move the elements of the sets they act upon.

Definitions. let $X$ be a set then for any set of partial transformations $S$ we define $Rel(S)$ to be the preorder closure of the set of all ordered pairs of $S$. For a preorder $R$ we define $Full(R)$ to be the full set of all partial transformations whose ordered pairs are in $R$. \[ Rel : Sub(PT_X) \to Po(X) \] \[ Full : Po(X) \to Sub(PT_X) \] Then these two form adjoints of one another between the lattice of preorders $Po(X)$ and the lattice of partial transformation semigroups $Sub(PT_X)$. $Rel$ is a lower adjoint and $Full$ is an upper adjoint.

Theorem. $Rel$ and $Full$ are adjoints of one another. \[ S \subseteq Full(R) \Leftrightarrow Rel(S) \subseteq R \] Proof. (1) suppose that $Rel(S) \subseteq R$ then every partial transformation of $S$ is included in $R$, so that $S \subseteq Full(R)$. (2) suppose that $S \subseteq Full(R)$ then every partial transformation of $S$ is included in $R$, which implies that $Rel(S) \subseteq S$. $\square$

The monotonicity of $Rel$ means that the larger a set of motions, the larger the corresponding preorder it moves in. The same general principle is true for any kind of motion. This is very useful in keeping track of the directions of special types of actions.

The monotone Galois connection between preorders and partial transformations can be restricted to other sets of transformations. Each of the different types of transformations has a corresponding complete system of transformations associated to a preorder: \[ Full : Po(X) \to Sub(PT_X) \] \[ FT : Po(X) \to Sub(T_X) \] \[ FPS : Po(X) \to Sub(PS_X) \] \[ FS : Po(X) \to Sub(S_X) \] These four have the obvious inclusions: $FT(X) \subseteq Full(X)$, $FPS(X) \subseteq Full(X)$, $FS(X) \subseteq FPS(X)$, and $FS(X) \subseteq FPS(X)$. In the case of actions by charts and permutations, we know they often form inverse semigroups or groups.

Theorem. let $E$ be a symmetric preorder on $X$, then $FPS(E)$ is an inverse subsemigroup of $PS_X$ and $FS(X)$ is a subgroup of $S_X$.

Proof. suppose that $p \subseteq E$ then $p^{-1} \subseteq E^{-1}$ because the transpose relation is monotone. $E^{-1} = E$ because $E$ is symmetric, so that $p^{-1} \subseteq E$, which means that $FPS(X)$ is inverse closed and $FS(X)$ is as well. $\square$

There is therefore a natural adjointness relationship between symmetric preorders and orbit symmetric permutation groups, which are the maximal permutation groups with a given orbit. This demonstrates the various ways in which we can get different types of actions from preorders, but there is yet one more.

A preorder $R$ on a set $X$ is a set of ordered pairs $(a,b)$ but an ordered pair is also an atomic partial transformation $\{(a,b)\}$ with a single element. This produces a partial semigroup action associated with any preorder $R$ on its ground set: \[ f: R \to PS_X \] By considering a preorder as an action on a set by atomic partial transformations, we can see that the underlying action preorder of an action is simply a way of reducing a transformation system to its simplest components: which are the ordered pairs that define movements from one point to another.

Monoid actions and categories:

The concept of a transformation semigroup can naturally be generalized to a monoid action. Instead of a fixed set of transformatinos, a monoid action can have a set of elements that transform another set.

* A monoid action is the action of a total semigroup on a set by a set of total transformations. \[ f : M \to T_X \] * A category is the action of a partial semigroup on a set by a set of atomic partial transformations. \[ f : Arrows(C) \to PT_{Ob(C)} \] This demonstrates that the morphisms of a category act on objects. A morphism $f : A \to B$ can move an object from point $A$ to point $B$, which is an atomic partial transformation.

	Elements	Actions
Monoid action	Elements	Transformations
Category	Objects	Morphisms

The action representatives of a monoid action for an ordered pair $(a,b)$ are $\{ m : ma = b \}$. The action representatives in a category are hom classes. The action preorder of a monoid action and the object preordering of a category, are both the underlying action preorders of their underlying partial transformations systems. Finally, the corresponding notion of a faithful monoid action in category is simply a preorder.

Definition. a faithful category is a preorder.

A preorder is a faithful category, because each morphism $f : A \to B$ produces a different atomic partial transformation $\{(A,B)\}$. Faithful categories can therefore be identified uniquely by their action preorders. The opposite notion, a completely faithless category is a trivial monoid action on a single object. In that case, every action of a morphism moves an object back to itself.

The idea of defining actions by atomic partial transformations is so fundamental that categories play an important role in the algebraic theory of motion and change. There closest relatives, as we have seen here are the monoid actions which also play an important role in models of change.

We have described both monoid actions and categories by their actions on an underlying set of objects. But another aspect of the algebraic laws of motion in monoid actions and categories, is that transformations and morphisms can act on themselves.

Definition. let $f : M \to T_X$ be a monoid action of $M$ on $X$. Then $M$ also acts on itself by the left, or right, or two sided actions. Dually for a category $f : Arrows(C) \to PS_{OB(C)}$. Green's preorders are the action preorders of these self-induced actions and Green's relations are defined from them.

The Green's relations merely described the algebraic laws of motion of a monoid, in therefore makes sense that in general they are the most important property of a given monoid. As they are very general concept dealing with the dynamics of motion, they can naturally be generalized to categories.

This produces the left, right, and two sided action preorders of a category. Furthermore, we can get subpreorders by subcategories like the mono preorder and the epi preorder. These produce the mono input action and epi input action preorders whose condensations are the posets of subobjects and quotients of a category.

An immediate difference between monoid actions and categroies is that the former form topoi, and the later do not. But the topoi of monoid actions comes by fixing a given ground monoid $M$ and then considering only $M$ sets, where categories can be constructed from many different kinds of partial semigroups.

A framework for higher category theory:

A general model of algebraic motions arises by keeping track of types of objects and how they can act on each other. In the simplest models of algebraic motion, we only have two types of objects: elements and transformations which can only act on each other in a single way but there is no reason that this cannot be generalized.

A 2-category is an algebraic system of motion, in which 2-morphisms can act on 1-morphisms to move them from point to another, 1-morphisms can act on objects. This is further generalized to tricategories, which are categories that are enriched over 2-categories and so on. In each case, we have a number of types that act on each other.

See also:
[1] Categories for order theorists

[2] Semigroup methods in category theory

References:
[1] Categories

Arithmetical properties of semilattices

Classical abstract algebra deals with homomorphisms between algebraic structures defined by certain equalities, by generalizing to inequalities we will treat the arithmetic properties of semilattices. A motivating application of this subject is that addition and multiplication of positive integers are properties of semilattices. Generalizing from this, we provide a general framework for associating commutative magmas to semilattices.

Order theoretic foundations of arithmetic

Every finite set is associated with a cardinal number. This associates the union semilattice of sets to addition in the following way: \[ |A \cap B| = 0 \Rightarrow |A| \cup |B| = |A| + |B| \] This forms a partial homomorphism from the union semilattice of finite sets to the addition commmutative semigroup of the non-negative integers. More then this, we have the following inequality: \[ |A \cup B| \leq |A| + |B| \] Thusly, addition is the maximal cardinality provided by the union of two sets with respect to their cardinalities. We can think of addition as a process by which we can combine two disjoint sets together. \[ |\{0,1\} \cup \{2,3\}| = |\{0,1\}| + |\{2,3\}| \] The multiplication of positive integers $(\mathbb{Z}_+,*)$ is associated to the intersection semilattice of set partitions. Two set partitions form an intersection matrix. The entries of this intersection matrix are the intersections of pairs of elements from each set partition.

	0,1	2,3	4,5
0,2	0	2	$\emptyset$
1,4	1	$\emptyset$	4
3,5	$\emptyset$	3	5

In the preceding example we see that not all entries in the intersection matrix of the two set partitions $\{\{0,1\},\{2,3\},\{4,5\}\}$ and $\{\{0,2\},\{1,4\},\{3,5\}$ are filled with non-empty elements. That means that they don't multiply, instead we get that $|P| = 3$, $|Q| = 3$, and $|P \cap Q| = 6$. Two set partitions multiply provided that all entries in their intersection matrix are non-empty as in the following example.

	0,1	2,3,4
0,2,4	0	2,4
1,3	1	3

These two set partitions form an indirect product of one another, because not every element in their intersection matrix is a singleton. The special case of a direct product occurs when each pairwise intersection of the two set partitions has cardinality one such as in the example below.

	0,1,2	3,4,5	6,7,8
0,3,6	0	3	6
1,4,7	1	4	7
6,7,8	6	7	8

With these intersection matrices, we see that there is a special case in which the interesction of set partitions is multiplicative much like how the union of sets is additive. This is described in the formula below: \[ \forall s \in P, t \in Q : |s \cap t| \not= 0 \Rightarrow |P \cap Q| = |P| + |Q| \] Multiplication can be thought of as determining the area of a rectangle where the two numbers are the width or height of the rectangle. In practice this rectangular area is the area enclosed by the intersection matrix of the two set partitions. As all entries of the intersection are enclosed in this rectangle, we have the following inequality: \[ |P \cap Q| \leq |P|*|Q| \] Addition is associated to the union of sets and multiplication is associated to the intersection of partitions. This is encodeded in the following table:

Table of commutative semigroups

	Semilattice	Arithmetic
Additive theory	Set union	Addition
Multiplicative theory	Partition intersection	Multiplication

The columns of this table can be combined to form a topos or a commutative semiring. The rows of this table form order morphisms, which describe certain inequalities inherent to semilattices. These order morphisms are our object of study today.

Order morphisms:

One of the central concepts of category theory is that of an arrow category. Using arrow categories, homomorphisms can be described by certain morphisms of morphisms: $(i,o): f \to g$. This commutative diagram can be described in symbolic form as: \[ o(f(x)) = g(i(x)) \] The idea of an order morphism is to replace the equality of a commutative diagram with an inequality: \[ o(f(x)) \leq g(i(x)) \] \[ o(f(x)) \geq g(i(x)) \] An order-theoretic morphism of functions has two forms: $f \ge g$ and $g \ge f$, determined by the two ways we change the equality in the commutative diagram into an inequality. An example from commutative algebra is the valuation map from a field to a totally ordered group, which has the following inequality: \[ v(a+b) \geq min(v(a),v(b)) \] If we look back at the inequalities that relate addition and multiplication to their respective semilattices, they take the same form. This puts these inequalities into a broad class, which we can be apply to a number of different algebraic structures. \[ |A \cup B| \leq |A| + |B| \] \[ |P \cap Q| \leq |P|*|Q| \] To simplify things, we tend to focus on an order morphism of form $(v^2,v)$ which can be defined by a single function $v$. The function $v : A \to B$ can have anything from a semilattice to a field as its input, but its output must always be always be a poset of some kind.

If $B$ is a poset, then the hom class $Hom(B^2,B)$ is partially ordered so that $g_1 : B^2 \to B$ is less then or equal to $g_2 : B^2 \to B$ provided that $\forall b : g_1(b) \leq g_2(b)$. Then given a function $f : A^2 \to A$ and a function $v: A \to B$ there is a subset $S$ of the hom class $Hom(B^2,B)$ with $g \in S$ provided that: \[ v(f(x,y)) \leq g(v(x),v(y)) \] Suppose that we have two functions $g_1, g_2 : B^2 \to B$ such that $g_1 \leq g_2$ then if $v(f(x,y)) \leq g_1(v(x),v(y))$ then $v(f(x,y)) \leq g_2(v(x),v(y))$. So that set of all $g \in S$ is an upper set in $Hom(B^2,B)$. The function $g$ is an upper bound of $f$ with respect to $v$.

Definition. let $v : A \to B$ be a function to a poset $B$ and let $f: A^2 \to A$. Then $g : B^2 \to B$ is a functional upper bound provided that $v(f(x,y)) \leq g(v(x),v(y))$. Dually, it is a functional lower bound provided that $g(v(x),v(y)) \leq v(f(x,y))$.

The fact that $Hom(B^2,B)$ is partially ordered means that we can define functional least upper bounds and functional greatest lower bounds: or functional infima and suprema for short. This is the key concept we need to define the arithmetical properties of semilattices.

Definition. let $v : A \to B$ be a function to a poset $B$ and let $f: A^2 \to A$. Then $g : B^2 \to B$ is a functional suprema provided that $v(f(x,y)) \leq g(v(x),v(y))$ and $g$ is minimal amongst all $Hom(B^2,B)$ that have this property. Functional infima are defined dually.

A key realisation is that addition and multiplication are not just upper bounds for set union and partition intersection, they are the functional suprema of these semilattices. So addition and multiplication are inherent properties of their respective semilattices.

Semilattice theory:

In order to define the functional suprema of semilattices, we first need some ranking function to optimize for. A ranking function is naturally provided for any finite semilattice $S$: \[ h : S \to \omega \] Wherein $h(x)$ is the maximal chain length of the principal ideal of $x$. This can naturally be generalized from finite semilattices to any semilattice which forbids the following total order types: $\{\omega^*,\omega+1\}$. Then the maximal chain length of the prinicipal ideal of any element will be finite.

We have a semilattice operation $\vee$ and a ranking function $h$ so now we can define a functional upper bound to be any function $\cdot$ with $h(a \vee b) \leq h(a) \cdot h(b)$. Furthermore, we can define the functional suprema to be the $\omega+1$ join of all heights of joins of elements with a given height pair: \[ n \cdot m = \bigvee \{h(a \vee b) : h(a) = n, h(b) = m \} \] This can be used as a simple algorithm to compute the arithmetical properties of the simplest semilattices. The resulting binary operation is the functional suprema of $\vee$ with respect to $h$. We call this operation the arithmetic operation of the semilattice.

Definition. the arithmetical operation of a well ordered semilattice $\vee$ is the functional suprema of $\vee$ with respect to $h$.

Addition and multiplication of positive integers can be produced in this way, from certain semilattices. As we shall see, there are other commutative operations associated to semilattices.

Finite boolean algebras:
Let $B_n$ be a finite boolean algebra. Then $B_n$ is associated to a commutative aperiodic monogenic monoid $I_n$ .

Proposition. the arithmetic operation of $B_n$ is the commutative aperiodic monogenic monoid $I_n$.

Let $(\mathbb{N},+)$ be the arithmetic operation of finite set union. Then $I_n$ is the Rees factor semigroup of the ideal $(n+1)$. The arithmetical property of a finite boolean algebra can be considered to be a part of the arithmetic of finite set union determined by a Rees semigroup congruence.

Finite partition lattices:
Let $Part(A)$ be the finite partition lattice. Then the arithmetic operation of $Part(A)$ is the Rees factor semigroup of $(\mathbb{Z}_+,*)$ determined by the ideal $(n+1),...$ where $n$ is the cardinality of $A$.

Proposition. the arithmetic of $Part(A)$ for a finite partition lattice is the Rees factor semigroup of $(\mathbb{Z}_+,*)$ determined by the ideal $(n+1),...$.

In this senes, the arithmetical properties of finite partition lattices precisely mirror those of finite boolean algebras. Much as in that case, these commutative semigroups are arrived at by cutting off part of the possibilities of multiplication.

The algebraic preorder of these Rees factor semigroups of multiplication all have meet subsemilattices of the first $n$ integers with an extra number adjoined as their algebraic preorders.

Interval semilattices:
Let $I$ be the set of all non-empty intervals in the range from $1$ to $n$. Then the commutative semigroup associated to $I$ is the null semigroup in which every element goes to zero.

Proposition. the arithmetic operation of the interval semilattice is the null commutative semigroup

This can be clearly seen because in an interval semilattice we can always maximize any pair by choosing elements of a given size at opposite sides of the semilattice. As a result, null semigroups are yet another example of a commutative semigroup associated to a semilattice.

Ordinal sums
Let $S$ and $T$ be semilattices and consider their ordered sum $S + T$ in which every element in $S$ is less then every element in $T$. Then the result is a semilattice, with arithmetic operation equal to the ordered sum of $S$ and $T$.

In particular, if $S$ and $T$ are associated to commutative semigroups $A$ and $B$ then $S+T$ is associated to the commutative semigroup $A+B$ with ${{A},{B}}$ a congruence with ordered pair semilattice quotient. An immediate application of this is that the arithmetic operation of a finite total order is trivial:

Proposition. let $T_n$ be a finite total order semilattice, then its arithmetic operation is $T_n$ itself.

Commutative monogenic aperiodic commutative semigroups can be formed by the finite boolean algebra minus the empty set. Then by the characterization theorem of finite totally ordered commutative semigroups this can be used to construct all totally ordered finite commutative semigroups.

Elementary properties:
Given this formalisation, a number of elementary properties of the arithmetic operations of semilattices can be inferred.

Lemma. $h$ is monotone

Proof. let $a \subseteq b$ then a maximal chain of $a$ can be extended to a maximal chain of $b$. The larger maximal chain of $b$ has a larger cardinality, so the maximal chain length of the principal ideal of $b$ is at least that of $a$. $\square$

The fact that $h$ is monotone means that the functional suprema of $\vee$ with respect to it is biextensive. The fact that semilattices are commutative means that their arithmetical operations are as well. These combine into the characterisation theorem for arithmetical operations of semilattices.

Theorem. let $S$ be a semilattice with finite maximal chain length $n$. Then the arithmetic operation $\cdot$ of $S$ is a bi-extensive commutative magma with $n$ elements.

Proof. The commutative property of $\cdot$ follows immediately from the commutativity of the semilattice $\vee$. By the fact that $h$ is monotone we have $h(x) \subseteq h(x \vee y)$ and $h(y) \subseteq h(x \vee y)$. This implies that $h(x) \vee h(y) \leq h(x \vee y)$. By the fact that $\cdot$ is a functional upper bound $h(x \vee y) \leq h(x)\cdot h(y)$ and so by combining inequalities we have $h(x) \vee h(y) \leq h(x \vee y) \leq h(x) \cdot h(y)$. This can be reduced to $h(x) \vee h(y) \leq h(x) \cdot h(y)$ which implies that $\cdot$ is bi-extensive. $\square$

Commutative semigroups that are biextensive over a partial order are necessarily J-trivial, so the following collary immediately follows:

Corollary. if the arithmetic operation of a semilattice is a semigroup, it is a commutative J-trivial semigroup

It is worth noticing that the addition and multiplication of positive integers are commutative J-trivial semigroups as is any semilattice. The class of commutative J-trivial semigroups generalizes semilattices to allow for elements that are not idempotent.

An exceptional semilattice
The following semilattice is not height associative: This has the following non-associative commutative magma as its arithmetic operation:

[[1 2 3 4 5]
 [2 3 4 4 5]
 [3 4 4 5 5]
 [4 4 5 5 5]
 [5 5 5 5 5]

This demonstrates that semilattices don't necessarily need to have associative arithmetic operations.

Idempotent height classes:
We have seen that a number of commutative J-trivial semigroups arise from the arithmetical properties of semilattices, but there are some restrictions to the set of possible commutative semigroups that arise in this way. The first restriction is a consequence of a property of idempotent height classes.

Theorem. let $n$ be an idempotent height class in a semilattice $S$ then $n$ has at most one element.

Proof. suppose that $h(a) = h(b) = n$ then by the fact that $h$ is monotone $h(a) \vee h(b) \leq h(a \vee b) \leq h(a)\cdot h(b)$ but $h(a) \vee h(b)$ is not either $h(a)$ or $h(b)$ because $a \not= b$ so $h(a) \vee h(b) \le h(a) \cdot h(b)$ which means that $n$ is not idempotent. $\square$

This can be used to characterize the arithmetical properties of finite graded semilattices. If a semilattice is graded, then every element must go through an idempotent height class which reduces the operation to an ordinal sum.

Proposition. every finite graded semilattice has an arithmetic operation which is the ordinal sum of finite commutative unitpotent magmas. In the commutative case it is an ordinal sum of nilpotent semigroups.

In the case of posets that are not graded, this restriction doesn't need to occur. For example, $[{[1,1],1},1]$ is the smallest non-graded tree and it has as an arithmetic operation the unique commutative J-trivial semigroup of order type [2,1] with two idempotents.

Corollary. the only idempotent commutative magmas that arise from finite total orders are the finite total order semilattices.

The smallest commutative J-trivial semigroup that cannot emerge from the arithmetic operation of any semilattice is the semilattice with order type [2,1] which is the smallest semilattice that is not a total order. We can construct commutative semigroups of order type [n,1] with one less idempotent then a semilattice by taking a chain and a singleton and adjoining a common parent to both of them.

Height preserving suborders:
The different arithmetic operations on the height classes of a partial order are partially ordered pointwise. As a consequence, the arithmetic operation is monotone over height preserving order extension.

Proposition. let $P \subseteq E$ be a height preserving suborder then the arithmetic operation of $P$ is less then that of $E$ in the pointwise ordering.

A finite boolean algebra is a case in point, given any maximal chain in $B_n$ we get a total order semilattice which is less then addition: $max(a,b) \leq a+b$. The number of join irreducibles in a finite distributive lattice is one less then the maximal chain length. The maximal chains correspond to linear extenions of the join irreducibles. This creates a height preserving embedding of a finite distributive lattice in a finite boolean algebra, so that the arithmetic operation of such a lattice is less then addition.

Proposition. the arithmetic operations of finite distributive lattices are subadditive

The distributive lattice of sets is inherently linked to addition. The cardinality of the disjoint union of sets is the sum of their cardinalities. This proposition relates finite distributive lattices in general to addition.

References:

[1] Commutative algebra volume one
Zariski and Samuel

[2] Commutative algebra volume two
Zariski and Samuel

[3] Lattice theory: foundation
George Gratzer

[4] Lattice theory: first concepts and distributive lattices
George gratzer

[5] Algebraic theory of lattices
Crawley and Dilworth

[6] Commutative semigroups
Grillet

[7] Finitely generated commutative semigroups
László Rédei

[8] Finitely generated commutative monoids
J.C. Rosales and Pedro A. García-Sánchez

Multiset representations of partial orders

Every partial order can be embedded in a boolean algebra, by representing each element of the poset as sets. A natural generalisation of this is to represent each element of the poset as a multiset. In order to do this, we need to determine when an element is a multiple of another. This occurs when it has at most one irreducible predecessor. This is implemented below.

(defn irreducible-representation
  [family elem]

  (let [predecessors (direct-subdimembers family elem)]
    (if (= (count predecessors) 1)
      (let [predecessor (first predecessors)]
        (let [dipredecessors (direct-subdimembers 
                                family 
                                predecessor)]
          (if (= (count dipredecessors) 1)
            (let [next-coll (frequencies
                             (irreducible-representation 
                               family 
                               predecessor))]
              (Multiset. {(first (keys next-coll)) 
                          (inc (first (vals next-coll)))}))
            (Multiset. {elem 1}))))
      (Multiset. {}))))

(defn clan-representations
  [family]

  (set
   (map
    (fn [i]
      (let [coll (subdimembers family i)]
        (apply
         join
         (map
          (fn [i]
            (irreducible-representation family i))
          coll))))
    (apply union family))))