Wednesday, July 7, 2021

Lattice ordered semimodules of multisets

The free commutative monoid $F(S)$ on a set $S$ consists of all multisets on $S$. This has a natural semiring action by $\mathbb{N}$, so $F(S)$ is a semimodule. The algebraic preorder of $F(S)$ is not only a partial order, since $F(S)$ is J-trivial, but it also a lattice.

Commutativity and semimodule theory:
A semiring action on a commutative monoid is defined by a structure preserving map from $R$ to $End(M)$. This requires that three conditions must be satisfied:
  • Action: $(ab)^n = a^nb^n$
  • Additivity $a^n a^m = a^(n+m)$
  • Multiplicativity $(a^n)^m = a^{nm}$
Every commutative monoid is a $\mathbb{N}$ semimodule. In a non-commutative monoid we can get the last two conditions, but we cannot get the first. Thusly, the techniques of semimodule theory cannot be applied to non-commutative monoids.

Commutativity and lattice theory:
The algebraic preordering of the free commutative semigroup is a lattice. This provides a natural link between commutative operations and lattices. Additionally, it is a distributive lattice of multisets.

On the other hand, the algebraic preordering on a non-commutative free semigroup is in general not a lattice. It is a partial order which orders lists by consecutive subsequences. Thusly, the techniques of lattice theory cannot be applied to non-commutative monoids. It seems that the lattice ordered semimodule structure is something that can only be applied in the commutative case.

Examination of the ordered algebraic structure:
An ordered monoid is an internal monoid in the category of preorders and monotone maps. It is not hard to see that $(\mathbb{N},\le,+)$ is an ordered monoid, but it has the stronger property that its action is biextensive. This naturally trasfers to the free commutative monoid $(F(S),+)$.
  • Monotone: $\forall a,b,c : a \leq b \implies a+c \leq b+c$
  • Biextensive: $\forall a,b : a \leq a + b$
The commutative monoid of all multiset addition actions is a submonoid of the monoid of all increasing monotone actions on the distributive lattice of multisets. We can therefore say that $F(S)$ is not only an ordered semimodule, its actions are also increasing.

Linear maps:
Recall from basic list processing, that mapcat replaces each element of a list with another list and then concatenates them all together. The corresponding operation over multisets is the unordered mapcat, which takes any element of a multiset and replaces it with another multiset, then adds them altogether.

The linear maps of free commutative semimodules $m : F(S) \to F(T)$ are precisely those defined by some unordered mapcat function $f : S \to F(T)$ that takes each element of the underlying set to a multiset in $F(T)$. This is also a monotone map of ordered semimodules. Therefore, the category of ordered semimodules can be used to understand the maps of free commutative monoids.

Tuesday, July 6, 2021

Commutative connected components

A number of different types of subsets of graphs provide example of commutatively necessary subsemigroups. A special case worth examining is when the connected components of a commuting graph are subsemigroups. A further special case is when commutative connectivity forms a congruence then its quotient will be a rectangular band.

In the other direction, if a semigroup has a rectangular band quotient, then its commuting graph is necessarily disconnected. The congruence classes of the congruence with rectangular band quotient are all disjoint unions of connected components of the commuting graph.

In order for the commutative connectivity partition of a semigroup to be non-trivial, the commuting graph of the semirgoup must not be connected. This already rules out any finite semigroup with idempotent commutative, such as any finite inverse semigroup.

Theorem. let $S$ be a semigroup and let $C$ be a commutativity connected subsemigroup of $S$ then $C$ is a radical subsemigroup.

Proof. let $y$ be an element in $C$ and suppose that there exists $x \in S$ and $n \in \mathbb{Z}_+$ such that $x^n = y$. Then $x * x^n = x^{n+1} = x^n * x$ which implies that $xy=yx$. Now since $x$ and $y$ commute we have that $x$ is in the same commutativity connected component as $y$, therefore $y \in C$. It follows that $C$ is a radical subsemigroup. $\square$

An example is the free semigroup on $n$ generators, in that case two lists only commute if they share a common generator. The commutativity connected components of the free semigroup are all principal radical subsemigroups, and so the commuting graph of a free semigroup is a cluster graph. A cluster graph is a special case of a class of graphs whose connected components all form subsemigroups.

Theorem. let $G$ be a trivially perfect commuting graph of a semigroup. Then all connected components of $G$ are radical subsemigroups.

Proof. trivially perfect graphs are precisely the graphs for which every connected component has a universal vertex. Therefore, let $C$ be a connected component of $G$, then let $x$ be a universal vertex of $C$. Then since $x$ is a universal vertex of $C$, $C$ is equal to the centralizer of $x$. Therefore, $C$ is a subsemigroup of $G$, and by the previous theorem it is a radical subsemigroup as well. $\square$

Every single graph of order four or less is either trivially perfect or connected. It is therefore an immediate consequence that commutative connected components are subsemigroups for all semigroups that are of order four or less. It seems that in at least the simplest cases, the connected components of the commuting graph are subsemigroups but this doesn't appear to be the case in general.

Monday, July 5, 2021

Categories for order theorists

Preorders can only describe the direction that objects that move in, they cannot explain the dynamic forces responsible for the motion of objects. Categories are just one way to explain motion in a preorder, defined by axiomatizing moves from one point to another as morphisms. Monoid actions are another way to explain motion in a preorder.

The order-theoretic perspective on categories requires further examination beyond what was provided by my first post. In particular, we need order-theoretic foundations for functors. This is provided by a homomorphism theorem which relates functors to subalgebra and congruence lattices. This leads to the following more complete account of the order theoretic foundations of category theory.
  1. Order-theoretic introduction of categories
  2. Lattices of subcategories
  3. Lattices of congruences of categories
  4. Theory of functors
  5. Natural transformations
Notes:

[1] The idea of recasting "structure preserving maps" as structure including maps provides a very direct accounting of how most categories are extensions of preorders. Monotone maps, continuous maps, relation homomorphisms, etc all correspond to structural inclusions in corresponding partial orders. This is formalized by hom class comparisons.

[2] There is a lot more that can be done to put category theory on a good order-theoretic footing. There are also many partial orders related to categories that are worthy of further examination. Everything is a work in progress.

[3] In these posts I mostly deal with locally small categories as structured sets. There are also large categories which can be treated as structured proper classes. The differences can be worked out in an axiomatic set theoretic account of categories. The important point is that categories can be treated as a sort of structured collection.

Sunday, July 4, 2021

Natural transformations

The trinity of concepts of category theory: categories, functors, and natural transformations form an ordered triple. So it makes sense to introduce functors before dealing with natural transformations. The introduction of functors suggested a basic perspective in which they are treated like functions, and that in turn suggested certain things about the structure and parts of functors.

Natural transformations, however, force us to change our perspective on functors. Natural transformations treat functors not like functions, but rather like indexed families of objects and morphisms. This leads to a slight change of perspective on the nature of functors, which will be dealt with now.

Morphisms of morphisms:
Let $C$ be a category, then $C^{\to}$ is its arrow category consisting of all morphisms of $C$ as objects and as morphisms ordered pairs $(i,o)$ of morphisms of $C$ that satisfy the commutative diagram: If the topos $Sets$ is the quintessential example of a category, then the topos of functions $Sets^{\to}$ is the quintessential example of an arrow category.

Functors as indexed families:
By turning the category of locally small categories into a concrete category, we considered functors as functions. What if a functor $F : C \to D$ is actually a family of objects indexed by a category $C$: objects in the category $D$ and the arrow category $D^{\to}$.
  • For each $X \in Ob(C)$ we have an object $F(X)$ in $D$
  • For each $m \in Arrows(C)$ we have an object $F(m)$ in $D^{\to}$
It would then seem that because functors are indexed families of objects, they can be treated as objects of a category themselves. This is indeed possible with functor categories and natural transformations, which operate on the objects indexed by a functor componentwise.

Natural transformations:
As functors are indexed families of objects, morphisms of functors are naturally morphisms of each object indexed by them. Let $F,G : C \to D$ be two functors and let $t : F \to G$ be a componentwise morphism of functors. Then $t$ maps categorical elements in $F$ to those of $G$. In particular,
  • $t$ associates to each object $X$ in $C$ a $D$ morphism from $F(X)$ to $G(X)$
  • $t$ associates to each morphism $m$ in $C$ a $D^{\to}$ morphism from $F(m)$ to $G(m)$
The standard way to define a componentwise morphism of functors is by defining the object mapping by a functon $t: Ob(C) \to Arrows(D)$. Then the morphism mapping is defined by doubling up the object mapping so that for any $C$ morphism $f: A \to B$ then $(t_A,t_B)$ is the morphism of morphisms $F(f) \to G(f)$. This simply means that $t$ satisfies the following commutative diagram: The componentwise nature of natural transformations explains why everything in a functor category is defined by componentwise versions of constructions in certain underlying categories. For example, in topoi of set-valued functors all limits/colimits are defined componentwise.

The componentwise nature of functor categories, suggests that the best way to understand them is by their output category $D$ and its arrow category $D^{\to}$. In particular, the most useful tools for studying any topos of set-valued functors are $Sets$ and $Sets^{\to}$ and all other constructions are defined over them. Morphisms in $D$ and $D^{\to}$ are the basic units that make up all natural transformations.

Enriched categories:
Let $Ab$ be the category of commutative groups. Then componentwise addition in $Ab$ gives each hom class $Hom(G,H)$ of commutative groups the structure of a commutative group. In general, the idea of an enriched category is that we can take hom classes of any given category, and define certain additional componentwise algebraic operations on it.

The description of natural transformations simply makes the concrete category $Cat$ into an enriched category, so that each hom class $Hom(F,G)$ has the structure of a category. These hom classes $Hom(F,G)$ are then all the different categories of functors. This suggests natural transformations are no more rare of a concept then any componentwise operation on homomorphisms encountered in abstract algebra.

New perspective on functors:
Our previous analysis of functors focused on their relationship to functions, determined by making the category $Cat$ into a concrete category. Then parts of functions could be determined on the function-level, but the idea of making functors into families means that they have different types of parts.

In the same way that a family of sets not only has subsets of itself, but also subsets of its members a functor not only has parts but it also has parts of its elements. Thus a subfunctor is defined by a natural transformation that takes each categorical element of a functor to a subobject, and a quotient functor does the same for quotients. We thus arrive at a different kind of construction on functors defined componentwise.

Saturday, July 3, 2021

Theory of functors

The category of locally small categories is a concrete category. As a consequence of this, every category has an underlying set and every functor has an underlying function. As functions are very well understood objects, we can understand functors by reference to their underlying functions. By this treatment, functors are simply the homomorphism functions of categories.

Parts referred to by functors:
The homomorphisms for basic algebraic structures like monoids are well known. These show that the kernel of any homomorphism is a congruence and the image is a subalgebra. We will now present the analagous result for categories.
  • The image of a functor is a categorical system of a subcategory.
  • The kernel of a functor is a categorical congruence.
The image is embedded in a subcategory by closure, as is the case for any categorical system. If a functor is object injective, then its image is necessarily a subcategory. These two homomorphism theorems for categories relate functors to the lattices of subalgebras $Sub(C)$ and congruences $Con(C)$ of a category.

Parts of functors:
A functor is a type of function, which means it is also an algebraic structure in its own right with its own subobjects and quotients. Subobjects are restrictions, and quotients are input/output relationships where in some partition of the input determines a partition of the output.

Every functor can be restricted to an object function and a morphism function. A functor is then simply a coproduct of its object and morphism functions. On the most basic level, the subobjects of a functor are individual ordered pairs of categorical elements from the two categories. Another case when you might get a subobject of a functor is by restriction to a subcategory of the domain.

Quotients are generally more interesting because they can tell you more about the functioning of a functor. There are some quotient relationships inherent to any functor. Recall the following hierarchy of properties of a morphism. Then if we have the morphism function part of a functor we have that the input object of the input of the functor determines the input object of the output of the functor. Likewise, the output object of the input determines the output object of the output. In both cases, the quotient function is the object function. By combination of these, we can also get that input output pairs of morphism determines input output pairs of their output.

Limits and colimits of categories:
The concrete category $Cat$ of locally small categories $Cat$ has all small limits/colimits. In particular, we can form products and coproducts of categories. The coproduct of two categories has the objects in the two categories in separate connected components. The product has as morphisms ordered pairs of morphisms of the two categories with composition between them piecewise.

Universal algebraic properties of categories:
In conclusion, categories have all the trappings of any algebraic structure studied in universal algebra. They have underlying sets, homomorphisms, subalgebras, congruences, free objects, products, coproducts, varieties and pseudovarieties, and so on. The elementary theory of categories is provided by constructions of universal algebra applicable to any algebraic structure.

Friday, July 2, 2021

Lattices of congruences of categories

Every algebraic structure in universal algebra is associated with two types of lattices: lattices of subalgebras and lattices of categories. Categories in this sense are no different then any other structure we have encountered in universal algebra. Let $C$ be a category, then its lattice of subcategories is $Sub(C)$ and its lattice of congruences is $Con(C)$ which we will now construct.

Categorical partitions:
Let $C$ be a category. Then its underlying set consists of both its objects and morphisms. Therefore, a partition of the domain of a category is a set partition with its set of objects and morphisms as a ground set. A noticeable property of categories is the separation of objects and morphisms. This separation holds for categorical partitions.
  • Object partition: a set partition of $Ob(C)$
  • Morphism partition: a set partition of $Arrows(C)$
There are therefore two ways to represent a categorical partition: either as a partition of the underlying set of objects and morphisms or as an ordered pair of partitions $(O,M)$ of the object and morphism sets.

Compositional congruences:
The composition function of a category $\circ : M_2^* \to M$ only effects the morphism system of the category. Compositional congruences therefore can be phrased entirely in terms of morphism partitions. A morphism partition $M$ is a compositional congruence provided that: \[ \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 \] It follows from the definition of functors that for any functor $F$ we have $F(fg) = F(f)F(g)$ for all morphisms $f$ and $g$ in $C$. This clearly implies that the morphism partition induced by any functor must at least be a compositional congruence.

Congruence closure:
Let $(O,M)$ be a partition of the object and morphism sets of a category. Then in order for a partition of this form to be a congruence it must satisfy a number of preservation conditions defined by logical implications:
  • Composition : $a_1 =_M a_2 \wedge b_2 =_M b_2 \Rightarrow a_1 \circ b_1 =_M a_2 \circ b_2$
  • Identities: $1_X =_M 1_Y \Leftrightarrow X =_O Y$
  • Inputs: $f =_M g \Rightarrow Source(f) =_O Source(g)$
  • Outputs: $f =_M g \Rightarrow Target(f) =_O Target(g)$
Let $(O,M)$ be a partition of a category $C$. Then the congruence closure of $(O,M)$ is determined by running through all logical implications until a closed set is produced. A partition that satisfies all four identities is a categorical congruence.

Definition. a categorical congruence is a partition that separates objects from morphisms that preserves composition, identities, inputs, and outpust.

The four conditions correspond to the four conditions placed on any functor, so the equivalence relation induced by any functor is a categorical congruence.

Lattice of congruences of a category
The set of congruences of a category forms a closure system with an upper bound equal to the maximal congruence, which makes all objects and morphisms equal. The closed sets of this closure operation therefore form a lattice.

Definition. let $C$ be a category then $Con(C)$ is the set of all categorical congruences on $C$ ordered by inclusion.

A well known special case consists of all object-injective congruences. These form an interval in the lattice of congruences of a category from the minimal congruence to the hom congruence, which equates all morphisms in each hom class.

Quotients:
Let $C$ be a category and let $P = (O,M)$ be a congruence of $C$. Then we can define a partial magmoid $\frac{C}{P}$ with $O$ classes as its objects and $M$ classes as its morphisms. The axioms of source preservation and target preservation mean that $\frac{C}{P}$ is a valid quiver, so it only remains to construct a valid composition operation for $\frac{C}{P}$ in order for it to be a partial magmoid.

Let the composition operation of the quiver $\circ$ be presented as a ternary relation $R \subseteq Arrows(C)^3$. Then we can construct a composition operation for $\frac{C}{P}$ by a map from $R$ to $M^3$ that maps each ordered triple in $R$ to an ordered triple in $M^3$ by the projection $\pi : Arrows(C) \to M$ applied to each component of the triple. \[ \pi^3 : R \to M^3 \] We are interested in the image $S$ of this projection map. By the fact that $M$ is a compositional congruence, this image is a single valued ternary relation, and so it can also be cast to a binary operation. Consider any triple $T$ in $S$. Then by the fact that $\frac{C}{P}$ is a valid quiver, each morphism class is associated to a hom class $(O_1,O_2)$ consisting of a pair of object classes.

The fact that any triple $T$ is the image of $R$ means that there is a triple of morphisms $(f : A \to B, g : B \to C, g \circ f : A \to C)$ whose image under $\pi^3$ is equal to $T$. This image has hom classes $((\pi(A),\pi(B))$, $(\pi(B),\pi(C))$ and $(\pi(A),\pi(C))$. It follows that the object classes of any triple take the form $((O_1,O_2),(O_2,O_3),(O_1,O_3))$ which means that this composition respects quotient hom classes.

If we have a triple of morphisms $(f,g,h)$ then the two types of composition $f \circ (g \circ h)$ and $(f \circ g) \circ h$ are equal, so they belong in the same $M$ class. It follows that quotient composition respects associtaivity. The partition preserves identities, so there is a quotient identity morphism for each object. This is clearly an identity for quotient composition. Therefore, $\frac{C}{P}$ is a partial magmoid.

Lattices of subcategories

Every structure is characterized by its component parts. In the case of categories, a locally small category $C$ can be considered to be a special type of structured set. The parts of a category are determined by subsets of its underlying set. Subcategories are parts of categories which are themselves categories.

We define the elements of a category to be either its objects or morphisms. It follows that the underlying set of a category is the coproduct of its object and morphism sets. This produces a combined ontology of categorical elements containing both objects and morphisms as special cases. The characterization of categories as structured sets produces a corresponding ontology of sets of elements of categories. These sets of categorical elements are called categorical systems, and they form a broad generalization of both object systems and morphism systems. Subcategories are merely a special case.

As a first step toward subcategories, we can require that a categorical system have all the objects of its morphisms. This produces the lattice of subquivers of a category, which forms a distributive lattice. This distributive lattice characterizes the fact that categorical elements have a dependency ordering in which morphisms are dependent on the objects they refer to.

The requirement that a categorical system preserves identities still produces a distributive lattice, in this case with identity morphisms equivalent to the objects they refer to. It is the condition of composition closure that makes the lattice of subcategories $Sub(C)$ of a category $C$ lose distributivity. The lattice of subsemigroupoids, which also has composition closure, also doesn't need to be distributive.

A number of special cases of categorical systems emerge from the various object and morphism preorders of a category. These are essentially the ideals of a category, commonly known as either sieves or cribles. These lattices, as lattices of ideals, are naturally distributive. An ontology of categorical systems like these is presented below.

A special case is the lattice of subgroupoids which is used in groupoid theory. The lattice of subcategories $Sub(C)$ contains a number of sublattices. The lattice of discrete subcategories is an example of a boolean sublattice. The lattice of wide subcategories consists of the interval of subcategories with the maximal discrete subcategory as its minimal element. Wide subgroupoids emerge from the combination of the two conditions.

The first special case we will be considering are hom complete subcategories. These correspond naturally to subpreorders of the morphic preordering, so they naturally produce a link between categories and order theory. This will further illuminate the order-theoretic nature of categories.

Suborders of a category

Categories can be characterized as sorts of generalized posets. This is formalized by the functor of categories that takes any category to its underlying morphic preorder, and a functor to its underlynig monotone map. This functor reflects subcategories, which produces our notion of suborders of a category.

Theorem. the morphic preordering $R : Cat \to Ord$ is an epifunctor from the category of categories to the category of preorders and monotone maps. It takes each category its underlying preorder, and each functor to its underlying monotone map.

Proof. (1) let $f : C \to D$ be a functor and $R(f) : R(C) \to R(D)$ its underlying object map between preorders. Then if $A \subseteq B$ in $R(C)$ that means $\exists m \in C : m : A \to B$. Then the output of $f$ on $m$ has signature $f(m) : f(A) \to f(B)$. Which means that $\exists f(m) \in Arrows(D)$ such that $f(m)$ has signature $f(A) \to f(B)$. Therefore, $f(A) \subseteq f(B)$ in $R(D)$. It follows that $R(f)$ is monotone.

(2) Let $1_C : C \to C$ be the identity endofunctor, then its underlying monotone map is $1_{R(C)} : R(C) \to R(C)$ which is an identity of preorders. Therefore, $R(C)$ preserves identities.

(3) Let $f : A \to B$ and $g : B \to C$ be functors. Then $R(f \circ g)$ takes $Ob(A) \to Ob(C)$ by $f \circ g$. Therefore, $R(f \circ g)(x) = f(g(x))$. This is equal to $R(f) \circ R(g)$ so $R(fg) = R(f) \circ R(g)$. $\square$

By presenting any preorder as a thin category, we can also get a functor that maps any category to its underlying preorder. This maps objects to objects and morphisms to edges in the preorder.

Theorem. let $C$ be a category and $\pi : C \to R(C)$ the map from $C$ to its morphic preordering. Then $\pi$ is an epimorphism of categories.

Proof. let $f,g \in Arrows(C)$ with $f : A \to B$ and $g : B \to C$. Then $\pi(f) = (A,B)$, $\pi(g) = (B,C)$ and $\pi(g \circ f) = (A,C) = (A,B) \circ (A,C)$. Therefore, $\pi(f \circ g) = \pi(f) \circ \pi(g)$ so $\pi$ is a functor. $\square$

Lemma. let $F : C \to D$ be a functor, then $f$ reflects subcategories.

Proof. Let $S$ be a subcategory of $D$. Then this can be proven in three stages.

(1) let $let f \in Arrows(C)$ with $f : A \to B$ such that $F(f) \in S$. Then $F(f) : F(A) \to F(B)$ so by the fact that $S$ is a subcategory, $F(A),F(B) \in S$. It follows that $F^{-1}(S)$ is at least a subquiver.

(2) let $X \in Ob(C)$ such that $F(X) \in S$ then $F(1_X) = 1_{F(X)}$. By the fact that $S$ is a subcategory, and $F(X) \in S$ we have that $1_{F(X)} \in S$. It follows that $F^{-1}(S)$ is identity closed.

(3) let $f : A \to B$ and $g : B \to C$ such that $f,g \in Arrows(C)$ and $F(f),F(g) \in S$. Then $F(g \circ f) = F(g) \circ F(f)$. By the fact that $S$ is a subcategory, and that $F(g) \in S$ and $F(f) \in S$ we have that $F(g) \circ F(f) \in S$. It follows that $F^{-1}(S)$ is composition closed. $\square$

We can precede these previous two lemmas to get that the map $\pi$ reflects subcategories, so the following corollary follows immediately.

Corollary. $\pi$ reflects subcategories

We can now define the suborders of a category to the subcategories produced by reflection of the $\pi$ functor, which maps each category to its underlying preorder.

Definition. let $C$ be a category with a suborder $S$ of its morphic preordering $R$. The suborder of the corresponding category is the reflection of $S$ with respect to the functor $\pi : C \to R$.

The lattice of preorders can be denoted $Po(R)$. Then clearly the lattice of preorders of $R$ is clearly equal to the lattice of categories of $R$ presented as a thin category. At this point, we have a lattice monomorphism from the lattice of preorders $Po(R)$ to the lattice of subcategories of any category $C$. \[ s : Po(R) \to Sub(C) \] Every suborder of a category is hom-complete, meaning that for any hom class in the subcategory $S$ every morphism in the same hom class in $C$ is in $S$. This leads the notion of hom completion, which completes a category by adding all morphisms in hom classes of the parent category to it. Therefore, the image of this lattice monomorphism is the lattice of hom complete subcategories of a category.

The lattice of preorders doesn't appear as much as its special case: the lattice of equivalence relations $Part(A)$. This lattice is clearly a suborder of the lattice of preorders, and we will also show that it is a sublattice.

Lemma. let $R$ be a symmetric relation, then its transitive closure is symmetric

Proof. if we have $(A,B),(B,C) \in R$ then we have $(A,C)$ by transitivity. By symmetry we have $(B,A),(C,B)$ are in $R$ as well so $(C,A)$ is in $R$ so transitive closure preserves symmetry. $\square$

Theorem. $Part(A)$ is a sublattice of $Po(R)$

Proof. (1) the intersection of equivalence relations is an equivalence relation so it is clearly a meet subsemilattice (2) the union of reflexive, symmetric relations is symmetric and reflexive so in order to prove join closure all we need is to demonstrate that transitive closure preserves symmetry, by the previous lemma it does so $Part(A)$ is a sublattice. $\square$

We can express this in categorical terms, by replacing the symmetric relations with groupoids. Equivalence relations are then equivalent to thin groupoids.

Theorem. $Part(A)$ is the sublattice of wide subgroupids of the subcategory lattice of the complete thin groupoid.

A special case of a suborder is an induced suborder, which is a subset of a preorder based upon a set of vertices in which all edges between the vertices are included in the suborder. The corresponding categorical notion is a full subcategory. This produces a lattice monomorphism from subsets of $Ob(C)$ to $Sub(C)$, which is weaker then the suborder morphism. \[ f : \wp(Ob(C)) \to Sub(C) \] The corresponding type of category for which all subcategories are full is the class of discrete categories. Then the subcategory lattice of a discrete category is a boolean algebra of sets. We therefore have a characterization of $\wp(S)$ and $Part(A)$ in terms of subcategory lattices.

Subcategory producing functions:

The most important types of morphisms like monomorphisms, epimorphisms, isomorphisms, and endomorphisms are composition closed. This means all these types of morphisms are associated to types of subcategories of any category $C$.

Theorem. let $C$ be a category, then the categories of monos, epis, bis, split epis, split monos, isos, endos, and autos are all subcatgories.

Proof. (1) let $f$ and $g$ be monos. Then $fx = fy \Rightarrow x=y$. Therefore, if we have $g(fx) = g(fy)$ this implies that $fx = fy$ which implies $x=y$ so mononess is composition closed. Dually for epis, then bis are simply the intersection of epis and monos.

(2) Let $f,g$ be split epimorphisms then the inverse of $g \circ f$ is equal to $f^{-} \circ g^{-1}$ because $g \circ f \circ f^{-1} \circ g^{-1}$ which clearly cancels to the identity. In the other direction, if we have $f,g$ as split monomorphisms then $g \circ f$ has inverse $f^{-1} \circ g^{-1}$ so that $f^{-1} \circ g^{-1} \circ g \circ f$ clearly cances to the identity. The composition closure of isomorphisms follows from the intersection of split monos and split epis.

(3) Endomorphisms are clearly composition closed, and they are hom-complete so they are also the suborder produced by the coreflexive relation on $Ob(C)$. $\square$

Let $C$ be a category, then the subcategory of morphisms of one of these types is a subcategory. This can be applied to get the underlying groupoid of a category.

Definition. Let $C$ be a category, then the subcategory generated by its isomorphisms is the underlying groupoid of $C$.

We can get the underlying subgroupoid of a subcategory. In general, for any class of morphisms that generates types of subcategories, we can get an action on $Sub(C)$. \[ f : Sub(C) \to Sub(C) \] This construction of an action on the lattice of subcategories invites us to consider the effect of taking subcategories on the different types of morphisms.
  • Monos,epis, and bis are preserved under subcategories
  • Iso are preserved by preserved under extensions.
  • Endos are preserved under both subcategories and extensions.
In the case of non-torsion groups, some subgroups do not preserve inverses. So isomorphims cannot be preserved by all subcategories. Monomorphisms and epimorphisms forbid certain pairs of morphisms related to them, so clearly they are closed under subcategories. As isos are closed under extensions, the underlying groupoid is a monotone map.

Ideals theory:

Categories are certain types of partial semigroups on edge sets of quivers, so its not hard to see why the ideals theory of categories is essentially the same as that of semigroups. We have three different types of preorder inherent to any category:
  • Input action preorder: $f \subseteq g$ means $\exists h : f \circ h = g$
  • Output action preorder: $f \subseteq g$ means $\exists h : h \circ f = g$
  • Two sided action preorder: $f \subseteq g$ means $\exists h_1,h_2 : h_1 \circ f \circ h_2 = g$
These correspond to the left, right, and two sided preorders of a semigroup. The Green's relations of a category are then simply the strongly connected components of these preorders: R is the connectivity of the input action preorder, L is the connectivity of the output action preorder, and J is the connectivity of the two sided preorder. The Green's relations D and H can be formed by the lattice of partitions $Part(A)$.

It is self-evident that ideals of form subcategories, because they are closed under composition with respect to morphisms from the overall category $C$. An interesting construction occurs where in we can change the category of morphisms acting on $I$ to some other subcategory $S$. This produces a family of three types of monotone maps from the lattice of subcategories to the lattice of preorders: \[ L : Sub(C) \to Po(Ob(C)) \] \[ R : Sub(C) \to Po(Ob(C)) \] \[ J : Sub(C) \to Po(Ob(C)) \] As these preorders are constructed from the actions of subcategories, their ideals don't need to be subcategories. An important example is an isomorphism ideal, which is an ideal with respect to two sided action of the underlying groupoid. Subcategories that are also closed under underlying groupoid action are called replete.

Repletion forms a closure action on the lattice of subcategories $Sub(C)$, and so the family of all replete subcategories forms a lattice determined by the skeleton of the category. Action preorders can also be formed by the mono and epi subcategories.
  • The preorder of subobjects is the input action preorder of the mono subcategory.
  • The preorder of quotients is the output action preorder of the epi subcategory.
The preorders of subobjects and quotients are therefore simply special cases of preorders determined by the monotone maps from the lattice of subcategories to the lattice of preorders. Posets of subobjects and quotients are then the condensations of the principal filters of either preorder.

The monotonicity of the map from subcategories to preorders means that smaller subcategories can only have smaller preorders of subobjects and quotients. This is translated to the language of subobject and quotient posets by the condensation which produces partial orders from preorders.

Connected components:

The underlying morphic preorder on the objects of a category induces a partition of $Ob(C)$ into weakly connected components. The resulting partition topology on the objects of the category consisting of all connectivity closed object systems then induces a boolean algebra of full subcategories each of which is clearly a prime two-sided ideals of $C$.

A category with non-trivial connected components admits a coproduct decomposition, and so this leads to the following theorem which characterizes the lattice of subcategories of a coproduct category in terms of product lattices.

Theorem. $Sub(C + D) = Sub(C) \times Sub(D)$.

Proof. This can be proven by a one to one map. Let $C$ and $D$ be connected components of the category $C + D$ and let $S$ and $T$ be subcategories of $C$ and $D$ respectively. Then by the fact that $C$ and $D$ are prime subcategories $S \cup T$ is a subcategory of $C + D$ so the union leads to an injective map from $Sub(C) \times Sub(D)$ to $Sub(C + D)$. In the other direction, any subcategory of $C+D$ can be decomposed into a subcategory of $C$ and a subcategory of $D$ by taking full subcategories with respect to $Ob(C)$ and $Ob(D)$. $\square$

This simple construction allows us to determine the lattices of subcategories of antichain categories from the lattices of subcategories of the endomorphism monoids of the category.

Families of subcategories:

If we take $Sub(C)$ to be the lattice of subcategories of a category $C$, then a family of subcategories is simply one of its suborders. These suborders come in a number of forms.

Lower sets:
If $F$ is a subalgebra closed family of categories, then the family of all subcategories of $C$ in $F$ forms a lower set of $Sub(C)$. For example, the family of all thin subcategories of a category is a lower set as is the lattice of all discrete subcategories.

Closure systems:
The families of subgropoids, the various ideal-related construction on categories like replete subcategories, and so on all form closure systems. These are upper bound maintaining meet subsemilattices of $Sub(C)$.

Sublattices:
Besides the lattice of discrete subcategories, the lattice of subgroupoids forms a sublattice of the lattice of subcategories of a groupoid. This can be proven in the following theorem.

Theorem. let $G$ be a groupoid and let $A,B \subseteq G$ be subgroupoids. Then the subcategory join $A \vee B$ is a subgroupoid.

Proof. the subcategory join $A \vee B$ consists of all words of the form $a_1 b_1 a_2 b_2 a_3 b_3 ... $. This simply has inverse $b_3^{-1} a_3^{-1} b_2^{-1} a_2^{-1} b_1^{-1} a_1^{-1}$. The words of $A \vee B$ have inverses, so join preserves inverses. The fact that the subcategory join of subgroupoids is a subgroupoid means that the lattice of subgroupoids is a sublattice of the lattice of subcategories.