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.
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$
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 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.
No comments:
Post a Comment