The enriched presheaves framework

The Locus computer algebra system is going to be centered around the idea of presheaf theory. It is our claim that presheaves make for the best models of computation, and presheaves can be a unifying fabric for logical and functional programming. Logic programming is modeled using the topos $Sets$ and functional programming is modeled using $Sets^{\to}$.

With this initial effort, we saw that a number of presheaf topos $Sets^{C}$ had interesting properties. MSets and their topoi $Sets^M$ could be used to model the fundamental properties of monoids and their Green's relations through their subobject lattices. Categories can be described by the topos of compositional quivers or by simplicial sets using the nerve construction.

However, there is only so far you can go with this construction without considering other types of functors, like structure presheaves. This leads to the enriched presheaves framework in particular. I have in mind as part of this framework that modules, left modules, right modules, and bimodules should be considered to be types of Ab-enriched presheaves. This will allow more of our fundamental constructions to be integrated into the presheaf theoretic and sheaf theoretic world view.

First examples of enriched categories:
Let $Cat$ be the category of categories and functors. Then $Ord$, $CMon$, and $Ab$ are closed subcategories of $Cat$, and it follows naturally from this that they are self-enriched. So these form the most fundamental examples of enriched categories:

• Locally ordered categories: categories enriched in $Ord$
• Ringoids: categories enriched in $Ab$
• Semiringoids: categories enriched in $CMon$

Each of the categories $Ord$,$CMon$, and $Ab$ are also concrete: so abelian presheaves, preordered presheaves, and presheaves of commutative monoids are all examples of structure presheaves. Now using their enriched category structure we can form modules as special types of structure presheaves.

The general framework
The general framework is for defining an enriched category over a monoidal category, also called a $V$-enriched category. In particular, every cartesian monoidal category is a monoidal category $V$ which can be used to form enriched categories. Then a $V$-enriched structure presheaf is a functor from a $V$ enriched category to a $V$ enriched concrete category. If $V$ is a concrete closed category, then $V$ enriched functors to $V$ are used to form modules.

Modules as structure presheaves:
Rings in general are partially commutative, with totally commutative rings being a special case (*). In order to deal with this most general context, we need to deal with differences between left and right composition. This leads to notions of left and right modules, which fortunately can be handled nicely be the structure copresheaves framework.

• Left modules: $Ab$-enriched copresheaves of abelian groups
• Right modules: $Ab$-enriched presheaves of abelian groups
• Bimodules: $Ab$-enriched profunctors of abelian groups
• Modules: the same as left modules except that the source category $R$ is a commutative ring

How fortuitous that we already have presheaf-theoretic counterparts for each of the different types of modules. Left modules are just copresheaves, right modules are presheaves, and bimodules are profunctors.

Sets	Ab
Left modules	Copresheaves
Right modules	Presheaves
Bimodules	profunctors

This means in effect that whilst left modules, right modules, and bimodules are to be treated the same as in any other computer algebra system, in a presheaf based computer algebra system, we can in addition implement for them the methods get-object, get-morphism, get-set, and get-function so that they can optionally be treated as structure copresheaves as well. This will be a strictly advantageous result.

Semimodules as structure presheaves:
The same approach as for modules works for semimodules, if we replace all the enriched categorical machinery of $Ab$ with $CMon$. In fact, this will work for any similarly closed category.

• Left semimodules: $CMon$-enriched copresheaves of commutative monoids
• Right semimodules: $CMon$-enriched presheaves of commutative monoids
• Bisemimodules: $CMon$-enriched profunctors of commutative monoids
• Semimodules: the same as left semimodules except the source category is a commutative semiring

The generalisation of modules to semimodules is necessary because a great number of constructions in modern mathematics are based upon semirings. For instance, the ideals of a commutative ring form an idempotent semiring.

Presheaves of preorders:
In our presheaf theoretic foundations, we have already made presheaf versions of most categorical constructions. In particular, we can generalize the lattice of preorders on a set to the lattice of preorders on a presheaf.

Definition. let $F$ be a presheaf then $Ord(F)$ is its lattice of preorders. Its objects are presheaves of preorders with underlying presheaf $F$ with the join and meet defined componentwise.

Another construction is that for any given preorder $P$ we can form its condensation which is a partial order. This generalizes to preorderd presheaves, so that for any presheaf we can form its condensed presheaf of partial orders by composition with the condensation functor.

Definition. let $F$ be a presheaf of preorders then $C(F)$ is its underlying presheaf of partial orders.

We previously considered the idea of a locally ordered category. A special case is a locally ordered monoid. We can form modules over locally ordered monoids, in a similar manner to rings using this structured presheaf framework, and the same technique is even applicable to locally ordered categories.

Definition. let $C$ be a locally ordered category. Then a left module over $C$ is simply a $Ord$ copresheaf of partial orders well a right module is an $Ord$ enriched presheaf of partial orders.

In particular, let $M$ be a locally ordered monoid. Then as a monoid it has left and right MSets define over it. In the case that $M$ is locally ordered, these further form $Ord$ enriched presheaves of partial orders, which are order modules. These are analogous to the left and right induced modules over rings. Most modules over ordered monoids can be formed this way, or by their restrictions by change of index functors defined by monotone monoid homomorphisms.

References:
[1] Enriched categories

[2] Enriched functor

[3] Categorical algebra

[4] Presheaves

[5] Copresheaves

[6] Profunctors

Locus 1.5

Locus 1.5 has been pushed to github. I would say the impetus for the recent series of changes was so that I could implement various categorical adjunctions that generalize images/inverse images. Towards that end, I have a multimethod for images and preimages which dispatches its arguments based upon the type of both of its values. So we have that images can be formed from various function-like objects applied to various mathematical objects.

• Set images are applicable to partial functions and multi-valued functions as well as ordinary functions. The image of a set under a multivalued function or set relation can be formed by the image multimethod.
• In most textbooks on category theory there is a mention of the topos $Quiv$ of binary quivers, which consists of two parallel functions from the edge set to the vertex set. I have generalized this to ternary quivers, and indeed all the way to nary quivers. The nary quivers implementation is new in this version.
• Given any nary quiver there are set images and inverse images: the set image of a set of edges in a nary quiver is the union of the sets of vertices in each edge, or in other words the union of all set images of the set under each component function. Inverses images are uniquely defined so that they form an adjunction.
• I implemented two new concepts for completions sake: partial quivers and hyperquivers. A hyperquiver is a functor from the parallel arrows category $T_{2,n}$ but to $Rel$ instead of $Sets$. Partial quivers are defined the same way but using te subcategory of partial functions. Set images under hyperquivers are formed by the union of all set images produced by all hte multivalued functions of the hyperquiver.
• Set images are defined for MSets and so instances of the MSet class implement the image multimethod now. The image of a set under an MSet is the set of all outputs of all actionts on the MSet applied to all elements of the set. Inverse images are defined dually so they form an adjunction.
• Images and inverse images are defined for set partitions. So that given a function you can apply it to a SetPartition rather then a set and you will get the appropriate set partition as an output using the image multimethod. This implements the adjunction between partition images and inverse images.
• Likewise, given any preorder you can apply it to a function instead of a set to get the preorder image or inverse image.
• The adjointness definition of continuous maps is defined by topological images/inverse images. So given a member of the TopologicalSpace class, it is interpreted properly by the image method to get an output topological space which is the maximal topological space which makes that map continuous. Topological inverse images are also defined so this forms an adjunction. So images/inverse images work in the most contexts possible now.
• A new class of copresheaves: Galois copresheaves is implemented now. These are just Galois connections without any reference to any underlying ordering.
• A new order theory framework integrating adjunctions is provided. New classes for residuated maps, coresiduated maps, and Galois connections are defined. The framework for supporting adjunctions has been greatly improved, motivated by this work on images and inverse images.
• Finally, new support for ordered algebraic structures is provided by new classes. These will be the first step towards algebraic structures like quantales which can always be formed from any algebraic structure using images and inverse images.

The implementation of the images/preimages framework is a good and necessary first step. A great many categories are defined by image/inverse image adjunctions, but the next steps will see us further improve the support for structure presheaves. Structure presheaves are our main focus.

Condensation of semirings

Every semiring is canonically associated to a minimal congruence with naturally ordered quotient, which can be defined by the additive J classes of the semiring. The quotient by this minimal congruence is the condensation of $S$.

The condensation theory of semirings
All the basic ingredients in this proof are available in any basic text on semiring theory. The fundamental breakthrough here is just a result in a change in thinking related to semiring congruences.

Theorem. let $S$ be a semiring and let $H$ be the Green's $H$ relation of the additive monoid $+$ of $S$, then $H$ forms a semiring congruence of $S$.

Proof. let $a,b,c,d \in S$ with $a H b$ and $c H d$. Then by the definition of the Green's $H$ relation there exist elements $x_1,x_2,y_1,y_2$ such that \[ a + x_1 = b \] \[ a = b + y_1 \] \[ c + x_2 = d \] \[ c = d + y_2 \] We can now demonstrate that $(a + c) \space H \space (b + d)$ by a simple process of substitution: \[ a + c = b + d + y+1 + y_2 \] \[ b + d = a + c + x_1 + x_2 \] To demonstrate that $ac \space H \space bd$ we can simply use the distributive law once after substitution: \[ ac = (b + y_1)(d+ y_2) = bd + by_2 + dy_1 + y_1y_2 \] \[ bd = (a + x_1)(c + x_2) = ac + ax_2 + cx_1 + x_1x_2 \] The fact that $a H b$ and $c H d$ both imply that $a + c \space H \space b + d$ and $ac \space H \space bd$ means that $H$ is both an additive congruence and a multiplicative congruence. It follows that it is a semiring congruence. $\square$

Definition. let $S$ be a semiring and let $H$ be the $H$ classes of its additive monoid then the condensation of $S$ is the quotient $\frac{S}{H}$.

The additive monoid of $S$ is its condensation on the level of semigroup theory, so it is not hard to see that it is a $J$ trivial. This is equivalent to saying that $S$ is a naturall ordered semiring.

Corollary. $\frac{S}{H}$ is a naturally ordered semiring

This condensation mapping $\pi : S \to \frac{S}{H}$ is characterized by a universal property in the sense of category theory.

Corollary. let $S$ be a semiring then any mapping $f$ from $S$ to a naturally ordered semiring $R$ filters through the condensation homomorphism $\pi : S \to \frac{S}{H}$ by a unique morphism $m$. General structure theory of semirings:
This condensation theorem for semirings is the most general tool we have for defining a general structure theory for semirings. This is applicable to any semiring, and it characterizes the relationship between its order theoretic and algebraic properties.

* Every semiring is an extension of a partially ordered semiring.

The only case when the partial order doesn't matter is the case in which is trivial, which is rings. For a ring $R$ it is clearly the case that all elements are additively related, so its quotient is the trivial semiring. Every semiring has a maximal subring, which is generated by the set of all elements with additive inverses.

References:
semiring in nLab

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

Ontology of partial magmoids

The idea of a category is often best understood in terms of partial algebra, and this perspective is available in many places in the literature. The composition operation $\circ$ of a category is a partial binary operation on morphisms. In order to make sense of the idea of a partial binary operation, I have come to consider the horizontal categorification of a partial magma. Towards that end, here is an ontology of the classes of partial magmoids: All of these objects including categories themselves are presheaves in the topos of compositional quivers $CQ$. Investigations of the objects of this topos have lead to considerations of partial magmoids, and their utility as a foundation for partial algebra is a further justification. In this context, a partial magma is simply a partial magmoid with a single object.

A thin partial magmoid is a quiver $Q$ with a specially defined set of composition triples $(a,b)(b,c)(a,c)$ of the underlying relation of its set of morphisms that forms its partial composition domain. Unlike for thin categories or thin semigroupoids, thin partial magmoids don't need to be transitive. Instead, every quiver has a thin partial magmoid with an empty composition domain so a thin partial magmoid can be installed on any quiver.

So these are just two of the most basic types of partial magmoids, but another direction you can go in is to consider magmoids themselves which get you closer to the familiar concepts of total algebra. In that context, for a given magmoid $M$ every endomorphism algebra is a magma. All these different types of partial magmoids are related by the inclusion relationships in our ontology.

References:
Horizontal categorification

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

Horizontal categorification of binary operations

A fundamental first step in our understanding of abstract algebra is the process by which we can translate from a single-object structure like a monoid to get its many-object variant such as a category. In particular, it is by this process that we can consider generalisations of categories like magmoids.

Operation	Oidification
Partial magma	Partial magmoid
Magma	Magmoid
Semigroup	Semigroupoid
Monoid	Category
Group	Groupoid

For example, it is by this process by which I have managed to consider additional generalisations of categories like partial magmoids. In this context, a partial magmoid is simply the horizontal categorification of a partial magma. Partial magmoids are useful in the study of quotients.

I emphasize this comparison to demonstrate that semigroups and categories are not profoundly different subjects. Categories and monoids are alike in almost every way as they lie together on a common axis of odification. Either one can be used to study the other for all intents and purposes. Categories are just the nicer way of looking at things is all.

A far greater difference actually lies between order theory on the one hand and either category theory / semigroup theory on the other. The later subjects have far more algebraic flavour and can be seen as ways of studying higher forms of preorders, enriched with extra algebraic structure. Categories are like higher preorders. So these are far more genuinely different subjects.

Horizontal categorification is a nice tool that we can use to group mathematical subjects together. Subjects that are on the same line of horizontal categorification are the most similar to one another, and those subjects that are not are the most genuinely different from one another.

References:
Horizontal categorification

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

Adjoint definition of continuity

As category theory is basically the most fundamental object of mathematics, I am always looking for the most categorically appropriate way to define things. I have a new idea of a way of defining continuous maps of topological spaces $f: (X,\tau_1) \to (Y,\tau_2)$ which I think is really nice. Start by generalizing functions from taking values in sets to them taking values in topological spaces.

• Topological image: let $f: X \to Y$ be a function and let $\tau_1$ be a topology of $f$ then the topological image of $\tau_1$ is $f(\tau_1) = \{ U \subseteq Y : f^{-1}(U) \in \tau_1 \}$
• Topological inverse image: let $f: X \to Y$ be a function and let $\tau_2$ be a topology on $Y$ then the topological inverse image is $f^{-1}(\tau_2) = \{ f^{-1}(U) : U \in \tau_2 \}$.

Then if you recall the definition of a monotone galois connection, it states that $F: A \to B$ and $G: B \to A$ are monotone galois connections provided that: \[ F(a) \subseteq b \Leftrightarrow a \subseteq F(b) \] Let $f: A \to B$ be a function then its topological image and inverse image functions are monotone maps on the lattices of topological spaces of $A$ and $B$ with the topological image $f : Top(A) \to Top(B)$ and inverse image $f^{-1} : Top(B) \to Top(A)$ forming an adjoint pair. Then the if and only if condition is also the definition of continuity: \[ f(\tau_1) \subseteq \tau_2 \Leftrightarrow \tau_1 \subseteq f^{-1}(\tau_2) \Leftrightarrow \text{f is continuous} \] The key point is that the topological image and inverse image describe the extremal solutions to the continuity problem, and so they form an adjoint pair. We can now describe which functions of topological spaces are continuous and which topological spaces make a function continuous, so for example if we only have a topology on the input set we can get a topological on the output set using the topological image.

We can generalize the topological image and inverse image to families of functions to get the weakest topology that makes the family of functions continuous. So for example, in smooth manifolds and observables we define the topology on the dual space of an $\mathbb{R}$-algebra $F$ as the weakest topology that makes all $\mathbb{R}$-homomorphisms $m: F \to \mathbb{R}$ continuous. So these kinds of definitions where we need to form a minimal or maximal topology to make some set of functions continuous appears all the time, now we can give this concept its appropriate role.

Everything as much as possible should be defined in terms of adjoints like these, because by doing so you not only give a definition of something but also the way to compute its extremal solutions. So adjoints are one of the most fundamental objects of category theory, and I think at a later date I might elucidate how their fundamental importance extends beyond topology to almost every branch of math. But that is a discussion for another time.

References:
Galois connection
Adjoint functor

Object preserving congruences of categories

Let $C$ be a category then a wide congruence $(P,Q)$ is a congruence in which no two objects are equated with one another. In that case, a wide congruence of $C$ can simply be considered to be determined by the partition $Q$ which is called an arrow congruence in toposes, triples, and theories [1].

Definition. let $C$ be a category then an arrow congruence $E$ is a partition of $Arrows(C)$ such that $E$ is:

• Quiver congruence: $f E f'$ implies that $s(f) \, E \, s(f')$ and $t(f) \, E \, t(f'))$
• Compositional congruence: $f E f'$ and $g E g'$ such that $fg$ and $f'g'$ are defined then $(fg) E (f'g')$.

These coincide with the definition of a congruence of a category, with the condition that the object partition is the trivial partition that equates no objects.

We saw in that general context of congruences of categories, that given a congruence $(P,Q)$ of the category $C$ then its quotient need not be a category. Instead, it is quite often a partial magmoid. This unusual behavior of $Cat$ is a consequence of the fact that it is not a topos. We can solve this by embedding it in something with the nicer structure of a topos like the topos $CQ$ of compositional quivers.

The issue of partiality means that for some congruences $(P,Q)$ in the quotient structure for some morphisms $f: A \to B$ and $g: B \to C$ a composite $gf$ need not exist. We would like to study the special case of object preserving congruences, to see if they have category forming quotients. In that case, that tells us something about the behavior of congruences of categories and their quotients.

Theorem. let $C$ be a category and let $E$ be an arrow congruence of $C$. Form the equivalence minimal object congruence $M$. Then the quotient $\frac{C}{(M,E)}$ is a category.

Proof. in order for something to be a category it must have a number of properties:

1. this is a quiver congruence by definition so $\frac{C}{(M,E)}$ is a quiver.
2. it is also a unital quiver congruence because $(M,E)$ is a congruence of the identity function. No two objects are equated by $M$ so no two identity morphisms need to be equated by $E$. It follows that no matter what $(M,E)$ is a unital quiver congruence.
3. $\frac{C}{(M,E)}$ is certainly a quotient unital partial magmoid because it is a compositional congruence.
4. the only thing that remains therefore is to check for the totality of $\circ$

So to prove condition four, we will let $C_1: X \to Y$ and $C_2 : Y \to Z$. The only thing that remains is for us to prove that $C_2 \circ C_1$ exists. As objects are preserved, then for each $m : X \to Y$ and $n: Y \to Z$ with $m \in C_1$ and $n \in C_2$ then their composition $n \circ m$ exists and it is in a class $C_3$. Therefore, the composition of any two classes in $E$ exists. It follows that $\frac{C}{(M,E)}$ is not simply a partial magmoid, it is also total and therefore a category. $\square$

We see that if we have a category with four objects and two non-trivial morphisms $m: A \to B$ and $n: C \to D$ then if we equate $B$ and $C$ we get a quotient partial magmoid in which the composition of arrows need not be defined. The problem here is that we are equating two objects and not two morphisms. If we don't equate any two objects then the quotient is always a category.

Equating two objects in a congruence is something you should never do in a category theory, because these partial magmoid things come out and they can no longer be considered categories. However, in the object preserving case the setting of categories is enough. This theorem can naturally be generalized to magmoids and semigroupoids.

Corollary. let $M$ be a magmoid and $E$ an arrow congruence of $M$ then $\frac{M}{E}$ is a magmoid.

As in the case of categories, it is necessary that the magmoid congruence should preserve all objects so that the quotient is not a partial magmoid. If you equate two objects then in the quotient structure the composition may not exist. So equating objects can eliminate totality of a categorical structure. These arrow congruences form a lattice.

Definition. let $C$ be a category then define its lattice of arrow congruences $AC(C)$ as the set of arrow congruences of $C$ with the intersection of equivalence relations as its meet and the arrow congruence closure of the join of partitions as its join. The lower bound of $AC(C)$ is the congruence with $C$ as its quotient and the upper bound is the congruence with the underlying preorder of $C$ as its quotient.

The thin congruence of $C$ which equates all arrows in equal hom classes is the maximal arrow congruence in the lattice $AC(C)$. It produces the underlying preorder of $C$ as a quotient. Then if we consider the full congruence lattice of a category $Con(C)$ there is an embedding functor $F: AC(C) \to Con(C)$ that turns any arrow congruence into a categorical congruence by producing the partition which preserves all objects and that equates all morphisms accordingly.

Definition. let $F: C \to D$ be a functor then $F$ is an object preserving functor if for all objects $a,b \in Ob(C)$ then $F(a) = F(b)$ implies that $a = b$.

Definition. $Cat_*$ is the category of categories with only object preserving functors between them

Then $Cat_*$ has all epi-mono factorisations and there exists a homomorphism theorem for $Cat_*$: every single object preserving functor has an arrow congruence and an image category such that the quotient category is isomorphic to the image. This is a small part of the fuller theory of subobjects, quotients, and epi-mono factorisations in a topos but it is an interesting part of the bigger picture.

See also:
Object preserving congruences of quivers

References:
[1] Toposes, triples, and theories

Locus 1.4

The newest Locus version has been released to github. I have made several changes to make this program better organized.

• I have added special support for dealing with copresheaves over product and coproduct categories. A copresheaf over a product category $F: C \times D \to Sets$ is a simultaneously a bifunctor and a copresheaf. Support for the hom functor $Hom : C^{op} \times C \to Sets$ is provided with this new framework so for example we can deal with the Yoneda embedding. Support for copresheaves over coproducts is provided by index sums.
• Several improvements have been made in the compositional quivers framework introduced and developed in Locus 1.3. As mentioned previously, the presheaf topos theory of categories now has two components: the theory of Yoneda embeddings and the theory of compositional quivers.
• Corresponding to the support for hom bicopresheaves, we also have new classes to deal with the functor of points and its dual, the basis of representable presheaves and copresheaves used in the Yoneda embedding.
• Recall the definition of the arrow category $Arrow(C)$. Then this can be defined as a category whose objects are morphisms of $C$ and whose morphisms are pairs $(f,g)$ of morphisms that form a commuting diagram, but I feel the more categorical approach is to construct this using the functor category $Hom(T_2,C)$ so the arrow categories framework has been rewritten to be this way. In particular, the to-natural-transformation method can be applied to morphisms in arrow categories.
• In the same vein of making things more categorical, I have become a fan of Lawvere metrics. The distances framework is now based upon them, and $\mathbb{R}^{\infty}_+$ enriched categories. Distances should be studied by reference to certain types of enriched categories.
• I have provided support for cones and cocones as special types of natural transformations. This should be make the categorical implementation of limits/colimits easier. Set cones and cocones are also special types of morphisms of presheaves.
• The entire implementation of functors and presheaves in this program had to be changed on a basic level to help support structure presheaves. Functors are based upon the get-object and get-morphism multimethods while presheaves use the get-set and get-function multimethods. Structure presheaves implement both, so they are like functors and presheaves at the same time.
• I actually implemented section preorders using the section-preorder method. This is something I have talked about here but it wasn't converted into code until now. In the future this will be integrated with the category of elements of a presheaf.
• Among the first functors implemented in the structure presheaves framework are partial copresheaves which are functors to the category of sets and partial maps and relational copresheaves which are functors to $Rel$. I've known for a while that I would want to implement functors to $Rel$ but I didn't have a framework that felt quite right until now with the structure presheaves system. With structure presheaves everything feels quite right.
• Functors from monoids to the category of partial sets are now called PSets rather then PartialActionSystems because it always makes sense to abbreviate things you use a lot.
• We now have support for copresheaves of monoids and other structure copresheaves. The copresheaves of monoids will make way for other nice constructions like presheaves of abelian groups and presheaves of modules.

There is more to be done, but the one thing that remains clear is our strong committment to presheaf topos theory. Presheaves are the means by which we model computation.

Two aspects of the presheaf theory of categories

The topos theory of categories, and the idea of presheaf representations still requires further clarification. I think we can split up the presheaf topos theory of categories into two parts:

• The topos theory of the category of categories $Cat$ which is now provided by the topos of compositional quivers. This topos is defined by chaining appropriate quivers in a composition manner.
• The topos theory of a general category $C$ which is provided by the Yoneda embedding $F: C \to Sets^{C^{op}}$ which fully and faithfully embeds any category into its topos of presheaves.

So basically, the theory of compositional quivers which I have defined is actually part of the topos theory of the category of categories $Cat$ while the topos theory of Yoneda's embedding of categories is part of the theory of individual and specific categories. The Yoneda embedding produces a different topos $Sets^{C^{op}}$ for every category.

The usefulness of the Yoneda's embedding doesn't mean that the idea of presheaf representations shouldn't be further explored. For one we could study the different Yoneda's embeddings of categories and how they relate to Grothendieck topoi and their topological properties, which I now has been done before. For another thing, its still useful to consider presheaf representations aside from the Yoneda's embedding for various reasons.

In particular, when considering something like the presheaf representation of algebraic structures, in our topos theory of universal algebra, it is best to consider presheaf topoi over finite index categories. As an algebraic structure is constructed out of a finite number of sets and functions, it should be defined as a presheaf over a category with a finite number of objects and morphisms.

Using the appropriate presheaf representation can lead to easier computations, and so that leaves the issue open. Whenever we consider an algebraic structure, we should immediately ask what kind of presheaf is it. The kind of presheaf it is, is determined how its sets and functions are combined. So that is why categories belong to the topos of compositional quivers, as that topos defines the composition law which is that morphisms $m: A \to B$ composed with morphisms $n: B \to C$ should produce morphisms of the form $n \circ m: A \to C$.

These different little details are going to be important in our implementations. One thing is for sure: everything is a presheaf and presheaves (respectively sheaves) are the most important objects in algebra and geometry. Algebraic structures are presheaves, like how categories are presheaves in the topos of compositional quivers. Geometric structures are sheaves such as schemes.

References:
Yoneda embedding

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

The category of elements and section preorders

The category of elements of a copresheaf $F$ denoted $el(F)$ provides an algebraic context to the section preordering. In particular, we have that the section preordering on $F$ is just the object preordering of $el(F)$.

Proposition. let $F : C \to Sets$ be a copresheaf, then the object preordering of $el(F)$ is the section preordering of $F$.

This is useful because now we know that the section preordering of $F$ can be constructed from the object preorder of its category of elements. The subobject lattice of $F$ is then basically the Heyting algebra of the Alexandrov topology of open subsets of the section preorder.

See also:
Subobject lattices of presheaves

Object and morphism structures of categories

In partial algebra, we get to study a lot of structures that wouldn't be available to us otherwise in total algebra. In particular this is true of categories, which are often best studied using partial algebraic structures. Partial algebra can be used to establish structures on both the morphism and object sets of a category. To demonstrate this we can first create a category:

; the index category of the topos of quivers
(def example-category
  (n-arrow-category 2))

Then we can get the object and morphism structures of the category using Locus and its new support for partial algebraic structures. The morphic structure is a partial magma and the object structure is a partial action.

Morphism structure:
The morphic structure of the category is a partial magma which can be acquired by using the composition-operation routine. The composition operation of a category is a partial magma with a domain $R$ in which $(f,g) \in R$ provided that $Out(g) = In(f)$.

; the morphic structure of the example category
(def op 
  (composition-operation example-category))
  
; every partial algebraic operation is a partial magma
(partial-magma? op)
;=> true

Every single partial magma is now a special type of a partial magmoid. This is part of the same categorification process by which every magma is a magmoid, every semigroup is a semigroupoid, every group is a groupoid, and so on. But this is not an arbitrary notion, because partial magmoids are actually an important part of the theory of the topos of compositional quivers $Sets^{CQ}$.

(partial-magmoid? op)
;=> true

So everything in Locus is based upon the most categorical of foundations. Even when you are considering a partial magma of a category, you are just considering the single object version of a partial magmoid. With this partial composition magma, we can consider categories as types of partial algebraic operations.

Object structure:
In total algebra we focus on MSets and their topoi $Sets^M$. All the actions of such an MSet are total transformations, defined by the topos $Sets$ rather then the category of sets and partial functions. To generalize MSets we have to engage in a process that is two fold: we can replace the monoid with a partial algebra and we can replace the total transformations by partial transformations.

The result of this process is a PSet which is the action of a partial magma by partial transformations on a set. Now consider a category $C$ then its object set $Ob(C)$ is a PSet. The partial magma of this PSet is the composition operation on morphisms of a category we just defined, and its action on objects is by atomic partial transformations. Every arrow $f: A \to B$ is actually just a partial transformation $A \to B$ on $Ob(C)$ that is defined on only the one element $A$ and hence it is called atomic. We can get this PSet in Locus using the to-pset method.

; the object structure of the example category
(def example-action 
  (to-pset example-category))
  
; the resulting pset is an action by atomic charts
(atomic-chart-pset? example-action)
;=> true

The implementation of PSets in Locus now largely coincides with that of MSets, so a number of multimethods can be freely applied to either PSets or MSets and you will get the expected results. Examples include action preorders, action homomorphisms, action equality, and so on. We can use this to get the object preorder of a category, which is part of the object structure of a category induced by its PSet.

; the object preorder of the example category
(def object-preorder
  (action-preorder example-action))

So the object preorder of a category which has $A \subseteq B$ whenever there exists a morphism $f \in Hom(A,B)$ is actually the action preorder of a PSet. So its just another case of an action preorder. On the other hand, the action preorders of the PSets induced by the action of morphisms on themselves to the left, right, or in both directions are what produce the generalized Green's relations of a category.

Its not hard to see that a partial magmoid is actually equivalent to a PSet by atomic partial transformations, and a category is just a special case that has a number of conditions: totality, the existence of identities, and associativity. So a category can be recovered from its PSet in the same way that a transformation semigroup can be recovered from its MSet.

See also:
Action preorders

Presheaf representations of categories

I have recently described the representation of categories as composition quivers. This is useful for providing a topos from which we can consider and study categories. However, it is not strictly speaking the case that categories are equivalent to their composition quivers, or that things are implemented this way. There are two concepts:

• the category $C$ itself
• its presheaf representation

The two concepts don't need to coincide. While its reasonable to represent elementary categories without any additional structure as composition quivers, there are too many types of enriched categories for this to be the case in general. How for example does this apply to Ab-enriched categories. There are too many open questions for now.

Its reasonable for us to separate the two concepts for now. Instead, I suggest that we logicians study different presheaf representations so that we can apply categorical logic to different mathematical structures. In the same way that linear algebraists represent things with matrices to study them linear algebraically, we can represent mathematical structures with presheaves so that can be studied logically. This still needs to be researched further.

Congruence lattices of categories

Congruences are the most fundamental concept there is. For example, in ring theory we study congruences indirectly through ideals. Its unthinkable that such important structures as categories shouldn't have congruences define over them. Fortunately, we can solve this problem by embedding categories in an appropriate topos.

Background
A categorical congruence of a category $C$ is a unital-quiver congruence $(=_M,=_O)$ that satisfies the equivalent of a semigroup congruence on the composition operation of a category: \[ \forall a_1,a_2,b_1,b_2 : a_1 =_M a_2 \wedge b_2 =_M b_2 \Rightarrow a_1 \circ b_1 =_M a_2 \circ b_2 \] In other words, $((=_M)^2|_{D(C)},=_M)$ is a composition congruence where $(=_M)^2|_{D(C)}$ is the partition of the composition domain of $C$ induced by $=_M$. Then every such congruence induces a congruence $(=_M)^2|_{D(C)},=_M,=_O)$ of $C$ in the topos of compositional quivers.

Congruences of the two arrow category:
Consider the index category $T_2^*$ of the topos of quivers: Then it has a congruence lattice that looks like this: As a quiver is a functor on this category $T_2^*$, and every functor induces a categorical congruence, each of these congruences determine different types of quivers.

• The congruence that equates no objects and morphisms determines a generic quiver.
• The congruence that equates the source and arrow morphisms determines a coreflexive quiver. These are precisely the quivers whose underlying relations are coreflexive.
• The congruence that equates the object and morphism sets describes a quiver whose vertex and edge sets are the same.
• The congruence that equates the source and arrow morphisms and both objects determines a coreflexive quiver on a common set of edges and morphisms.
• The congruence that equates the source and identity morphisms makes it so that the source of each morphism is the morphism itself.
• The congruence that equates the target and identity morphisms makes it so that the target of each morphism is the morphism itself.
• The congruence that equates everything is a coreflexive quiver on a single set, where the source and target objects of a morphism are the morphism itself.

So the congruence lattice $Con(T_2^*)$ does tell us something interesting about this category, and the functors that can be formed on it. In the same way that the ideals lattice determines what morphisms can be sourced from a given ring. So for example, a homomorphism starting from a field must always be either trivial or injective because a field has only two ideals. This simple example fails to demonstrate the fact that the congruences of a category don't always coincide with the congruences of that category as a unital quiver.

Congruences of a total order on three elements:
Consider the three element total order $T_3$: Then its lattice of congruences as a unital quiver $Con(T_3)$ looks like this: On the other hand, its lattice of congruences as a category $Con(T_3)$ looks like this. Then its clearly smaller then its counterpart. In fact, the former has seven coatoms while the later has only four. So while it is note the case that the congruence lattice of $T_2^*$ is smaller for it as a category then as a unital quiver, in the general case the categorical congruence lattice is smaller because it has the extra condition of being a congruence of composition. It can clearly be seen:

Proposition. let $C$ with $Q$ its underlying quiver then $Con(C) \subseteq Con(Q)$ and $Con(C)$ is a meet subsemilattice of $Con(Q)$.

So categorical congruences are just defined from unital quiver congruences by the condition that compositions must be unique with respect the morphism partition. This makes them a subsemilattice of the unital quiver congruence lattice.

Congruences of the two pair category:
Consider a category with two different ordered pairs: Then its congruence lattice looks like this: Consider now the congruence that equates the objects one and two but no morphisms. Then this is certainly a valid congruence, for example we can define a monotone map from this thin category to $T_3$ that takes 0 to 0, 1 and 2 to 1, and 2 to 2 and as a monotone map that is a functor, and its underlying partition is a categorical congruence. However, consider the resulting quotient. Clearly it is not a category, because the composition of two arrows that have an intermediate object is not always defined.

Proposition. the quotient of a category by a congruence is not necessarily a category

Instead, the quotient of a category by a congruence is always a partial magmoid. Partial magmoids have no axioms that would prevent them from being closed under quotients, because any quotient of their binary operation is again a partial magma. So the category of partial magmoids is nicer then the category of categories $Cat$ in at least one way, but it is still not enough. The nicest categories are topoi.

The topos of composition quivers:
So we define the topos of composition quivers from a presheaf on the index category that looks like this: The relevant fact is that a category is essentially described by the data of three sets and six functions: the first, second, composition, identity, source, and target functions. This topos includes not only categories but all their generalisations like partial magmoids and beyond. Topos theory is the most advanced branch of mathematical logic we have available. Applying it to understanding categories can be very rewarding.

See also:
Congruence lattices of quivers

Locus 1.3.0

I published the next big version of Locus to github. It features the completed topos theory of categories based upon presheaf representations and compositional quivers. That is the main feature implemented in this new version. This is apparently original work, but once you think about it its pretty obvious there is no other way to thinking of categories except as presheaves of the compositional quiver type.

• Quivers, unital quivers, permutable quivers, dependency quivers, etc are all significantly improved so that you can run computations with their subobject and congruence lattices. Some of that has already been displayed here.
• Ternary quivers are now being implemented in Locus. These are like the familiar quivers used to describe graphs, except their edges have three arrows coming out of them. They are to a large extent responsible for the topos theory of abstract algebra, as binary operations are ternary quivers. Their three components are the first component, the second component, and the composite for any ordered pair. So magmas for example are ternary quivers.
• Categories are composition quivers, which are defined by a ternary quiver heading into a binary quiver consisting of morphisms and edges. The ternary quiver defines the composition binary operation of the category, and the composition of the underlying index category ensure that the ternary quiver operation is compositional on the binary quiver. This leads to the topos theory of categories, which is a great asset to us because it is best to think of categories as objects of a presheaf topos.
• By the same token we can study partial magmoids, which are the horizontal categorification of partial binary operations, magmoids, semigroupoids, groupoids, and all other related compositional structures via the topos of composition quivers. This justifies by implementation of these categorical algebraic structures in Locus, and my decision to consider them based upon topos theory to be special types of presheaves.
• Locus is going to be absolutely categorical. So for example, magmas will be magmoids, rings will be ringoids, ordered monoids will be two categories, etc. The only question is what type of structures you want to add on to a category. This new implementation of Locus sets the groundwork for that change.
• The next versions of Locus will study other presheaf related constructions on categories. The entire project is based upon presheaf foundations, and that now comes through by representing categories as presheaves.

Endotrivial categories

A thin category is a category $C$ such that for each object $a,b$ we have that $|Hom(a,b)| \leq 1$. We can generalize this condition by relaxing this axiom in a number of ways, including by requiring that $|Hom(a,b)| \leq 1$ only when $a$ and $b$ are equal. The result is the category of endotrivial categories. These categories have interesting order-theoretic properties.

Definition. a category $C$ is endotrivial provided that for each object $a \in Ob(C)$ we have that $|Hom(a,a)|$ = 1.

Partially ordered endotrivial categories:
As an introduction to endotrivial categories, we shall first consider the case of a partially ordered endotrivial category.

Definition. a endotrivial category is partially ordered provided that its object preorder is antisymmetric.

These categories have the following interesting characterisation which describes their role in category theory.

Proposition. a category $C$ is partially ordered endotrivial iff it has the property that for each symmetric pair of morphisms if they go in opposite directions $f: A \to B$ and $g: B \to A$ then $f = g$.

Proof. suppose that all opposite morphisms are equal. Then the category is endotrivial because if $f: A \to A$ and $g: A \to A$ are two endomorphisms then they are opposite because their respective sources equal the others targets and vice versa. So they must be equal, which implies that all endo hom classes are trivial. Further, suppose that $C$ is not antisymmetric then there exists $A \subseteq B$ and $B \subseteq A$ which means there are opposite edges $f: A \to B$ and $g : B \to A$ which violates the non-existence of opposite edges, so $C$ is partially ordered. $\square$

These categories are the strongly directed categories, in the sense that all their arrows are going the same direction along some partial order. As a direct generalisation of thin categories, they are one of the classes of categories that are most like partial orders.

Example 1. any partial order such as Young's lattice $\mathbb{Y}$ or the subobject lattice of a category $Sub(C)$ is a partially ordered endotrivial category.

Example 2. the index category $T_2^*$ of the elementary presheaf topos of quivers $Quiv$ is a partially ordered endotrivial category, as is any other index category for a nary quiver topos.

The general theory:
In the same way that partial orders are the basis of the entire theory of thin categories, the strongly directed categories are the basis of the whole theory of endotrivial categories.

Theorem. let $C$ be an endotrivial category and let $a,b$ be two objects in $Ob(C)$ that are related to one another in the object preorder, so that there exists $f: A \to B$ and $g : B \to A$. Then $a$ and $b$ are isomorphic.

Proof. $f : A \to B$ and $g : B \to A$ are composable so there exists composites $g \circ f : A \to A$ and $f \circ g : B \to B$, but in an endotrivial category all endomorphisms are equal so this means that $g \circ f = 1_A$ and $f \circ g = 1_B$ which implies that $f$ and $g$ are opposite isomorphisms. Therefore, $A$ and $B$ are isomorphic. $\square$

These allows us to characterize the skeletal endotrivial categories, which demonstrates that they are strongly directed. Thusly, endotrivial categories can be considered by their skeletal counterparts in the same way that thin categories are considered in terms of partial orders.

Corollary. the skeletal endotrivial categories are precisely the partially ordered endotrivial categories

The endotrivial categories can be considered to be generalisations of thin categories, but they could equally be considered to be the antithesis of monoids. This theorem provides their general theory.

Congruence lattices of undirected graphs

Locus can now compute the congruence lattices of undirected graphs using topos theory. This uses the topos of quivers with involution.

P3
Here is the path graph on three elements: Here is its congruence lattice: K3
Here is the complete graph on three elements: Here is its corresponding congruence lattice: P4
Here is the path graph on four elements: Here is its congruence lattice: S4
This is the star graph on four elements: Here is its congruence lattice: C4
Here is the cycle graph on four elements: Here is its congruence lattice: This congruence lattice is already getting quite big so we can stop this here. Rest assured that every undirected graph, and indeed every mathematical structure, has a congruence lattice defined over it even if we can't see it.

On the arrow category of partial semigroups

In the theory of semigroups of atomic charts, I described how categories are like partial semigroup homomorphisms from the partial semigroup of a category to the complete brandt semigroup of atomic charts. This is part of the partial algebraic theory of categories, which we can now extend here to deal with functors.

Definition. the category $PS$ of partial semigroups has two components:

• Objects: all maps $*: R \to X$ with $R \subseteq X^2$ that form partial semigroups so that if $(ab)c$ exists then so does $a(bc)$ and whenever they both exist they coincide $a(bc) = (ab)c$
• Morphisms: homomorphisms $f: (*_X: R \to X) \to (*_Y: S \to Y)$ defined by mappings of the form $f: X \to Y$ with the property that whenever $ab$ exists then $f(a)f(b)$ exists and $f(ab) = f(a)f(b)$

Then the arrow category of $PS$ is the standard arrow category defined in category theory: $PS^{\to}$. We will show that every category is associated to a partial semigroup homomorphism and every functor is associated to a morphism of partial semigroup homomorphisms in the arrow category. This leads to a functor: \[ A : Cat \to PS^{\to} \] This functor is the main way that we will form the partial algebraic theory of categories. In doing so, we will see that categories are just special types of actions in partial algebra.

Definition. the functor $A: Cat \to PS^{\to}$ has two components:

• the object part takes any category $C$ to a partial semigroup homomorphism $A(C): (Arrows(C),\circ) \to S_{Ob(C)}$ where $(Arrows(C),\circ)$ is the composition partial semigroup of the category and $S_{Ob(C)}$ is the complete brandt semigroup of partial transformations on the object set $Ob(C)$. Let $m: X \to Y$ be a morphism in $C$ then $A(C)(m)$ maps to the atomic action $(x,y) \in S_{Ob(C)}$.
• the morphism part takes any functor $F: C \to D$ to a morphism of partial semigroup homomorphisms $A(F) : A(C) \to A(D)$ which as a member of an arrow category has two components: (1) the arrow part of the functor $F$ which is a partial semigroup homomorphism from $(C,\circ)$ to $(D,\circ)$ and (2) a partial semigroup homomorphism of atomic partial transformation semigroups from $S_{Ob(C)}$ to $S_{Ob(D)}$ that maps $(x,y)$ to $(f(x),f(y))$.

This defines the object and morphism parts of the functor $A: Cat \to PS^{\to}$ and it describes how categories can be mapped to semigroup homomorphisms, while functors can be mapped to morphisms of partial semigroup morphisms but it doesn't definitively prove that this is a valid functor.

Theorem. the mapping $A: Cat \to PS^{\to}$ is a functor.

Proof. $A$ is a mapping from $Cat$ to $PS^{\to}$ which a functor to a morphism of partial semigroup homomorphisms. This forms a commutative diagram of the following form: Let $m : A \to B$ be an arrow in $C$ then by this commutative diagram we want to show that $A(F_M(m)) = F^*_O(A(m))$. In the first place $F(m) : F(A) \to F(B)$ so that $A(F(m)) = (F(A),F(B))$. On the other hand, $A(m) = (a,b)$ and $F(A(m)) = (f(a),f(b))$. It follows that this is a valid morphism of partial semigroups, so that $A : Cat \to PS^{\to}$ is a functor. $\square$

This demostrates the usefulness of the partial algebra construction, as every category can now be associated to partial semigroup homomorphism. We see that in general, all algebra should be done with a partial algebraic perspective in mind because that is how categories work. Categories are partially defined on composable morphisms, and so they are related to a number of interesting constructions in partial algebra.

References:
Semigroups of trivial charts

Total subobjects of quivers

Subobjects are categorically dual to quotients. In this context, if we were to dualize the idea of the lattice of thin congruences of a quiver, then its counterpart would have to be total subobjects. Let $Q$ be a quiver then a total quiver is one in which every object $o \in Ob(X)$ has at least one morphism going in to it $f : x \to o$ or going out of it $g : o \to y$. This produces the following duality:

• Subobjects: total subobjects can be determined from any morphism set
• Congruences: thin congruences can be determined from any output partition

The total function is an interior function on the lattice of subquivers $Sub(Q)$ whilst the thin function is a closure function on the lattice of congruences $Con(Q)$. We should always bear in mind that every concept in category theory has a categorical dual, so just as an object has congruences so too does it have subobjects.

See also:
Subobjects and quotients of thin quivers

External links:
Duality
Quivers

Object preserving congruences of quivers

Let $Q$ be a quiver. Then thin congruences are characterized by the fact that they are fully determined by their object partitions. It would be interesting to consider the dual case of partitions that collapse morphisms but no objects.

Theorem. let $Q$ be a quiver then its lattice of object-preserving congruences $L$ is equal to the direct product of the partition lattices of each of its hom classes: \[ L = \prod_{a,b \in Ob(Q)} Con(Hom(a,b)) \] Proof. let $P$ be a morphism partition for $Q$ and suppose that $a =_P b$ then since this is an object preserving partition, if $s(a) \not= s(b)$ or if $t(a) \not= t(b)$ that would imply that either $s(a) = s(b)$ or that $t(a) = t(b)$ with respect to the object partition induced by $P$, which would be a contradiction of the fact that this is supposed to be an object-preserving partition. So every pair of equal morphisms in $P$ must be parallel in $Q$.

Parallel pairs of morphisms are contained in hom classes $Hom(a,b)$ for pairs of objects $a,b \in Ob(Q)$. It follows that for any morphism $m : a \to b$ the only other morphisms it could be made equal to our those in $Hom(a,b)$. So its part of a congruence lattice $Con(Hom(a,b))$. Then consider all the hom classes of the quiver $Q$, they all have partition lattices that direct product to the set of all object-preserving partitions of $Q$. $\square$

We saw in the theory of thin congruences that the thin congruence associated with any object partition is in fact its equivalence maximal member. So this allows us to characterize the bounds of the lattice of object preserving congruences:

Corollary. let $Q$ be a quiver and let $L$ be its lattice of object-preserving congruences. Then its equivalence minimal member is the trivial partition which equates no elements, and its equivalence maximal member is the thin congruence.

This allows us to better characterize the relationship between thin congruences and object partitions. As we saw here, both thin congruences and object preserving congruences can both be characterized in terms of partition lattices. However, the same is not true for the lattice of congruences $Con(Q)$ of a general quiver $Q$ which need not have any familiar structure in terms of partition lattices.

References:
Quiver in nlab

Subobjects and quotients of thin quivers

Thin quivers are an important special case in presheaf topos theory. Suppose that we have a thin quiver $Q$ then we can form and consider its subobject and congruence lattices $Sub(Q)$ and $Con(Q)$ normally, but far more interesting is to consider subobjects and congruences of a thin quiver that remain thin.

Theorem 1. let $Q$ be a thin quiver, then every subobject of $Q$ is thin.

Proof. Thinness is a non-existence condition stating that there do not exist morphisms $m: A \to B$ and $n : A \to B$. Non-existence conditions are subset closed. $\square$

It is rather trivial that thin quivers are subobject closed, and that the subobjects of thin quivers are again thin. Of course, it also follows that any subcategory of a thin category is again thin. Far more interesting is the case of congruences of quivers that have thin quotients.

Lemma 1. let $Q$ be a thin quiver. Then $Q$ has no congruences that collapse two morphisms $m: A \to B$ and $n : C \to D$ without also equating two objects. $Q$ has a unique object-preserving partition.

Proof. $Q$ is a thin quiver it therefore follows that for the two morphisms $m$ and $n$ we must have either $A \not= C$ or $B \not= D$. Suppose that $A \not= C$ then we would have to equate $A$ and $C$ under the congruence so that would produce an equal pair of objects. Likewise, if $B \not= D$ then we would have to equate $B$ and $D$ also producing an equal pair of objects. So no two non-parallel morphisms can be equated under a thin quiver congruence. $\square$

This is the base case, which is that there is a unique congruence for the object partition that preserves all objects. Our goal is to show that there is a unique quiver congruence associated to every object partition.

Lemma 2. let $Q$ be a quiver, then the equivalence minimal congruence that turns $Q$ into a thin quiver $Thin(Q)$ is the congruence that equates all parallel pairs of morphisms in $Q$ and no objects. All other morphisms $f: Q \to T$ from $Q$ to a thin quiver factor through $Thin(Q)$.

Proof. let $Q$ be a quiver. Then in order for $Q$ to be thin there must not be any pairs of morphisms $m$ and $n$ with the property that $s(m) = s(n)$ and $t(m) = t(n)$. Thusly, to make $Q$ thin we can equate all such pairs of morphisms $m$ and $n$ to get the congruence $Thin(Q)$. This has as a quotient a thin quiver because it can not have any pairs $m$ and $n$ with $s(m) = s(n)$ and $t(m) = t(n)$ for if it did it would contradict the fact that we collapsed them. Then to see minimality, consider that any other congruence $C$ of $Q$ must also collapse all such pairs $m$ and $n$. It follows that $Thin(Q)$ is the minimal thin congruence. $\square$

With these two lemmas we now have have the means we need to prove our main theorem, which is that the thin congruences of a quiver are fully determined by object partitions.

Theorem 2. Let $Q$ be a quiver and $B$ a partition of its objects. Then there is a unique quiver congruence of $Q$ with $B$ its object partition that has a thin quotient.

Proof. there is always a unique quiver congruence associated to any object partition $B$ of a quiver $Q$: the congruence that collapses all objects in $B$ but no morphisms. We can always form this congruence by the pair $(id,B)$. Then the quotient of this congruence need not be thin. So by lemma 2 we can form a partition $A$ of the morphism set $E$ by equating all parallel edges which turns $\frac{Q}{(id,B)}$ into a thin quiver. This forms the following commutative diagram: Then also by lemma one, we see that every morphism from $Q$ to a thin quiver $T$ that goes through $B$ must filter through $\frac{Q}{(A,B)}$. However, by lemma one we know that no such further congruence can exist without further equating the objects of $B$. So $\frac{Q}{(A,B)}$ is the only thin quiver produced by a congruence with object partition $B$. It follows that thin congruences are fully determined by their object partitions. $\square$

If by theorem 2, we have that each object partition is uniquely associated to a thin congruence, then there is a one to one mapping $U : Con(Ob(Q)) \to Con(Q)$ that maps any object partition into a thin congruence.

Corollary. let $Q$ be a quiver then the suborder of $Con(Q)$ consisting of all thin congruences is isomorphic to the partition lattice $Con(Ob(Q))$ of partitions of the object set $Ob(Q)$.

It follows from this that the lattice of thin congruences of $Q$ is simply a partition lattice. We can further consider the thin mapping we defined in lemma 2 to be a closure operation on $Con(Q)$.

Corollary. $Thin: Con(Q) \to Con(Q)$ is a closure operation on the lattice of congruences of a quiver $Con(Q)$ that maps any congruence to its thin component.

The relevance of this result is that we can understand the epi-mono factorisations in the full subcategory of the topos $Quiv$ of thin quivers. We see from this that every morphism of directed graphs is determined by a vertex partition on the one hand a subset of vertices and edges on the other. The interesting thing about this is that it produces a dichotomy between congruences and subobjects, where only the later requires both object and morphism components.

Of particular interest is the application of this theory to considering subobjects and congruences of binary operations, which can simply be considered to be quivers with an algebraic function operation adjoined to them in the topos $Sets^{T_{2,3}}$ of ternary quivers. This leads into a more advanced topos theoretic theory of algebraic operations and their subobjects and congruences, which will be helpful in defining the topos theoretic foundations of algebra.

We see that topos theory provides the best foundation for combinatorics because topoi like $Quiv$ let you reason logically about graphs, digraphs, etc. $Sets^{[1,2]}$ lets you reason about hypergraphs. In order to make it the best foundation for abstract algebra we need to consider other topoi like $Sets^{T_{2,3}}$. In order to use topoi in geometry, as was originally intended, we can consider topoi of sheaves $Sh(X)$ of topological spaces. Every branch has its own topoi available for further study, which makes topos theory such an exciting field for further research and analysis.

References:
Quiver in nlab
Topoi: The Categorial Analysis of Logic