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

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.

Globular sets as models of (n,r)-categories

One of the concerns of mine is the presheaf theory of categories and higher categories, and the use of presheaf topoi to create models for higher categories. The basic presheaf topoi I would like to focus in on are the (n,r)-globular sets.

Definition. Let a 0-globular set be a set. Then an (n+1)-globular set is a quiver with an n-globular set as its hom classes.

So for example, a quiver is a 1-globular set and all of its hom classes are simply sets. A 2-globular set is simply a quiver such that each hom class is itself its own quiver. Equivalently, that means that a 2-globular set is like a 2-quiver with the condition that $s \circ t = s \circ s$ and $t \circ s = t \circ t$ so that all 2-morphisms are between parallel pairs of 1-morphisms. The relationship to topos theory is that these are presheaves over the globe category $G_n$.

Definition. let $G_n$ denote the nth globe category. This has source and target morphisms from (n+1)-morphisms to n-morphisms with the condition that $s \circ t = s \circ s$ and $t \circ s = t \circ t$ for each source and target morphism.

It follows that an n-globular set is actually an object of the presheaf topos $Sets^G_n$. It follows that we can use presheaf topos theory to reason about n-globular sets.

Proposition. the section preorder of an n-globular set is a height (e.g max chain length) n+1 partial order.

Proof. the n-globe category is an endotrivial partially ordered category, so it follows that the section preorder is a partial order. Its chains are determined by chains of n-morphisms followed by (n-1)-morphisms all the way to 0-morphisms. It follows that the chain can have length no more then $(n+1)$. $\square$

The subobject lattice $Sub(G)$ of a globular set $G$ in the topos $Sets^{G_n}$ is simply a distributive lattice of the max chain length n+1 partial order. The congruence lattice $Con(G)$ is formed in the standard way it is formed for any presheaf object in a topos. The first thing we see is that $Sets^{G_n}$ lacks identity morphisms so it is not a good model for n-categories. Instead it is a model for n-semicategories. To resolve this we define and implement unital n-globular sets.

Definition. we construct the unital n-globe category $U_n$ in the following manner:

• we have n-morphisms for all 0,...,n
• we have nth source and nth target morphisms for each m-morphism going to an (m-n) morphism. These are denoted $s^n$ and $t^n$
• we have nth identity morphisms $id^n$ that take an m-morphism to an (m+n) identity morphism
• every morphism in $U_n$ can canonically be represented as a pair of $id^n s^m$ or as a pair $id_n t^m$ representing the n-th identity morphism on an mth-source or an mth-target morphism.
• the composition of two morphisms $id^w s^x$ and $id^y t^z$ proceeds by canceling out as many identities as possible by removing pairs of $s$ and $id$. Then if identities are remaining they get $id^{y-x+w}$ by combining identity morphisms as the identity part in front of $t_z$. If $x > y$ then we cancel out $id^y$ and we get $id^w s^{x-z}$ because when we get $s^n$ composed with $t^n$ we combine the two with the source/target type the last to be called. So this can canonically define composition in the unital n-globe category.

It follows that a unital n-globular set is simply a copresheaf in the fundamental topos $Sets^{U_n}$. This presheaf definition may not be the exact one you always want so another approach is as follows:

Definition. a unital n-globular set can be defined from the data of a n-globular set as well as identity morphisms for each m-morphism with $m \lt n$. The identity morphisms for a morphism $m$ have the property that their source and target morphisms are both $m$.

We now have an underlying presheaf model for n-categories. The distinction between the two is readily apparent:

• A 2-semicategory can be defined as a compositionally enriched 2-globular set. An ordered semigroup, for example, is a 2-semicategory. As a not necessarily globular set, it doesn't require the definition of identities.
• A 2-category is a compositionally enriched unital 2-globular set. It has identity morphisms for each object, and two identity morphisms for each 1-morphism defined by its underlying globular structure.

We now have two different topoi, with the later one, $Sets^{U_n}$, providing a better presheaf topos theoretic model for n-categories, and yet our discussion still cannot end here. There is one more detail, which leads to the formation of $(n,r)$-categories. As we shall see each of these different $(n,r)$-categories actually has its own special type of underlying globular structure.

We can start with groupoids which are $(1,0)$-categories. In the most basic case we might treat a groupoid as simply a special case of a 1-category. But in actually, a groupoid is a structured dependency quiver, which is to say a unital quiver with an extra inverse function $inv: Arrows(Q) \to Arrows(Q)$ that takes any edge and maps it to its inverse. These dependency quivers are actually used in the topos theory of undirected graphs, whilst ordinary quivers are used in the topos theory of directed graphs.

We now actually have a better terminology for dependency quivers. They can now be considered to simply be the unital (1,0)-globular sets. So the $(n,r)$ category theory terminology matches the underlying globular set terminology, and this same approach in fact generalizes onwards to infinity.

The next case is that of 2-categories. Here we distinguish between three cases: (2,0) categories which are simply the 2-groupoids, (2,1) categories which have all 2-morphisms invertible, and ordinary 2-categories. Each of these different types of (n,r) categories has their own corresponding class of globular set, in the same way that groupoids are distinguished by unital (1,0)-globular sets.

A (2,1)-globular set has an inverse for 2-morphisms, and a (2,0)-globular set has an inverse for both 2-morphisms and 1-morphisms. A (2,2)-globular set is just an ordinary unital 2-globular set. Each of these different types of globular sets correspond to special classes of presheaves, in the same way as we constructed presheaves for dependency quivers. This generalises to the theory of (n,r) globular sets.

• a (0,0)-globular set is just a set
• a (1,0) globular set is a dependency quiver
• a (1,1) globular set is a unital quiver
• a (2,0) globular set is a unital 2-globular set with an inverse function for 1-morphisms and 2-morphisms
• a (2,1) globular set is a unital 2-globular set with an inverse function for 2-morphisms
• a (2,2) globular set is a unital 2-globular set

So these different types of (n,r)-globular set determine the different types of (n,r)-category that can be formed over them. The type of an (n,r) category is determined by the underlying presheaf that it enriches.

Definition. the category $G_{(n,m)}$ is the unital globe category $U_n$ with an inverse adjoined for all morphisms with index greater then $m$.

Definition. an (n,r) globular set is a presheaf in the topos $Sets^{G_{(n,m)}}$.

Every $(n,r)$ type encodes its own type of globular set and it has its own topos. At the same time, the type of for semicategories, and n-semicategories is determined by having an n-globular set without identities, so much like how $(n,r)$ categories are distinguished from one another by their underlying globular set, the same is true for how semicategories are distinguished from their corresponding categories.

In fact, rather or not an object is a category, semicategory, groupoid, 2-semicategory, 2-category, 2-groupoid, (2,1)-category, etc can always be determined by the topos of its underlying globular set. So the highest level classification of categories comes from their globular topos. Categories and their generalisations can always be identified by two different aspects:

• Combinatorial structure: the underlying globular set of the category, rather or not it is an (n,r)-globular set, has identities, etc.
• Algebraic structure: the compositional aspect of the category, which allows you to extend a quiver or other globular set with the composition of morphisms.

The combinatorial structure of a category can always be understood with topos theory and selected topoi like $Sets^{G_n}$ and $Sets^{G_{(n,m)}}$. One of the things that I have strongly emphasized is the topos theoretic foundations of algebra, and that presheaves are the best models we have for algebraic stuctures, but the full realisation of this programme is a subject for further development.

We have noticed by this formalisation that the different types of $(n,r)$ categories are distinguished presheaf theoretically by the type of their underlying globular sets. A slightly different situation occurs when considering $\infty$-categories. $\infty$-categories are defined by other base topoi like $\infty$-globular sets and simplicial sets. An $\infty$-category is then just a different type of presheaf. Higher categories then fit nicely into our foundations in presheaf topos theory.

The development of higher category theory does not challenge our foundation in presheaf topos theory. If anything, it actually reinforces it because all the different types of higher category construction are determined by the different types of presheaves. We will model higher categories using presheaf topos theory.

References:
(n,r)-Categories
Globular sets
Geometric shapes for higher structures

The subobject classifier in the topos Sets^(->)

In order to demonstrate operations in on objects of the elementary copresheaf topos $Sets^{\to}$ we should first create a function object. This can be done as of Locus 1.2 using the mapfn function, which converts a clojure.lang.IPersistentMap into a SetFunction. You can also perform the same conversion using the standard to-function method.

(def f
  (mapfn 
    {:a :x, 
     :b :x, 
     :d :y, 
     :e :y, 
     :f :z}))

Once you have defined a function, you can display it using the visualize routine which will give you a diagram like this, demonstrating a surjective function. When we define a subobject classifier in a topos, we also need an object of truth values. The object of truth values in the topos of functions $Sets^{\to}$ is a function that looks like this. The subobject classifier in the topos $Sets^{\to}$ is then a morphism in $Sets^{\to}$, but that means it is also an object in the topos $Sets^{T_2 \times T_2}$ and a presheaf object of a topos in its own right. We get a subfunction from the pair (#{:a :d}, #{:x :y}). The resulting subobject classifier in the topos $Sets^{T_2 \times T_2}$ looks like this: I recently mentioned that $Sets^{\to}$ is a concrete category. This is a new development that I only implemented in Locus 1.2, when I decided that everything should be made into a concrete category in order to implement structure copresheaves and to expose as many morphisms as possible to reasoning in the topos $Sets^{\to}$. This means that the subobject classifier in $Sets^{\to}$ itself has an underlying function that looks like this: This demonstrates that the subobject classifier in $Sets^{\to}$ is like a function on the elements of functions. The elements of functions are inputs labeled by zero and outputs labeled by one, and the maps between them map inputs to inputs and outputs to outputs. We map inputs to $0$, $\frac{1}{2}$ and $1$ depending upon rather they are in the set, their image is in the set, or if their image isn't even in the set at all. So this gives a different notion of truth then we are used to in $Sets$.

When we think of a function $f: A \to B$ we don't typically think of it as a structured set, in fact I am not familiar with any text that describes them as such nor anything that describes $Sets^{\to}$ as a concrete category. This requires a fundamental rethinking of one of the most basic objects of mathematics: functions. We must now consider functions to be like structured sets again.

The beauty of this construction is that when can then take morphisms in $Sets^{\to}$ and consider them to be objects in $Sets^{\to}$ again so we can use the categorical logic of $Sets^{\to}$ on them. In particular, we see that the underlying function of the diamond copresheaf demonstrated above has a function congruence which maps the first part of the input to the first part of the output, demonstrating that morphisms of functions preserve input/output types.

The justification of representing everything as a structured set and every category as a concrete category, is actually primarily so that every morphism can be structured function. This way we can always reason about any morphism in a concrete category using the fundamental topos $Sets^{\to}$ which is our most deepest goal. This requires that we rethink our understanding of presheaves, so that we can consider the different layers of presheaf representations that mathematical objects can be exposed to.

References:
Topoi: The Categorial Analysis of Logic by Robert Goldblatt