Topos constituents of a category

There are number of different ways to reason logically about a category. We could use methods of lattice theory, like lattices of subalgebras and congruences. Another approach is to relate categories to the ordered algebraic structures of mathematical logic like relation algebras. The decisive role is ultimately played by topos theory, which provides the logic for all algebraic structures.

The topos of quivers comes into play here, as one of the constituent topoi of a category. Every small category is associated with a forgetful functor to the topos of quivers, whose adjoint takes any quiver to the associated free category. The forgetful functor to the topos of sets is then a constituent part of this topos valued functor.

Proposition. let $F: Cat \to Quiv$ be the function which forgets the composition of the category, then $F$ is a functor.

Proof. let $f : A \to B$ be in $Arrows(Cat)$ then $F(f) : F(a) \to F(b)$ so that $F(s(f)) = F(a) = s(F(f))$ and $F(t(f)) = F(b) = t(F(f))$. This function splits a functor into its edge and vertex mappings so that $F(f) = (f_1,f_2)$ and so $F(f \circ g) = (f_1 \circ g_1, f_2 \circ g_2) = (f_1,g_1) \circ (f_2,g_2) = F(f) \circ F(g)$. Finally, $F(1_X) = (1_Ob(C),1_Arrows(c)) = 1_F(X)$. $\square$

Corollary. the map $G \circ F : Cat \to Quiv \to Sets$ makes $Cat$ into a concrete category. So $Sets$ is another one of the constituent topoi of $Cat$.

Much of the previous work in category theory, was done by considering $Cat$ to be a concrete category, and categories to be structured sets. In particular, this yields a significant simplification of the theory of functors. With this, we can consider functors to be a special type of function. In particular, we can apply the logic of functions provided by the topos of functions $Sets^{\to}$ to them. With this, we can conider categories to be structured quivers.

• Structured quivers
• Structured sets

We see, following the topos perspective that it doesn't matter so much rather or not a category is concrete, or rather its objects are structured sets. The most important fact is that it is constructed over a number of constituent topoi: these could be sets, quivers, functions, bijections, actions, or any other topos object.

In the case of categories, they are certainly not just determined by the data of a quiver. They are compositional quivers: they also include a function object. So it also remains to show the forgetful functor from any category to its composition function is a functor.

Definition. let $\circ : Cat \to Sets^{\to}$. Then $\circ$ has two components (1) its map any category $C$ to its composition function $\circ_C : Arrows(C)^2_* \to Arrows(C)$ and (2) given any functor $F: C \to D$ it maps it to a morphism of functions $\circ(G) : \circ_C \to \circ_D$ defined by $((F|_{Arrows(C)})^2_*,F|_{Arrows(C)})$

Theorem. let $\circ : Cat \to Sets^{\to}$ be the functor that maps any category to its composition function. Then $\circ$ is a functor.

Proof. let $F$ be a functor then $F(g \circ_C h) = F(g) \circ_D F(h)$ so that we have a commutative diagram like Which means that a functor is a morphism of functions $\circ_C$ to $\circ_D$. Then composition is defined componentwise over arrows, so this is a functor. $\square$

It follows that we can reason about categories using the topos $Quiv \times Sets^{\to}$ consisting of ordered pairs of a quiver and a function. This mirrors the process by which we considered all the algebraic structures of universal algebra in terms of elementary topoi. Here are the various constituent topoi of a category:

• Sets: the underlying set of a category makes $Cat$ into a concrete category
• $Sets^2$: the underlying set can also be considered to be two sets: the set of objects and the set of morphisms
• $Quiv$: the underlying quiver of a category
• $Sets^{\to}$: the composition function is a topos object

The data of a quiver with a function in $Quiv \times Sets^{\to}$ is enough to determine a category, but the quiver and the composition function of a category aren't just any functional quiver. They also have special properties as quivers and functions:

• The quiver of a category is preposetal, so that its underlying binary relation is a preorder.
• The composition function of a category is a partial semigroup, in the sense that if $(A \circ B) \circ C$ and $A \circ (B \circ C)$ both exist then they must coincide.

Categories exist at the intersection of order theory and semigroup theory: having a quiver extended over a preorder and a composition function that is a restriction of a semigroup. Both of these relations are reflected in the topos objects of a category: a quiver and a function.

As $Cat$ can be embedded in the topos $Quiv \times Sets^{\to}$ the elements of its logic: the lattices of subcategories and congruences can now be in the larger context of topos theory. Naturally, the subalgebras and congruences are a subset of what is possible in the larger topos context, because we require that subobjects and quotients remains categories instead of other functional quivers.

Indeed, this shows that since $Cat$ is not a topos, it contains only a subset of reasoning about even categories. This is one reason one $Cat$ can never be used as a foundation of mathematics (e.g ETCS) because it is too weak to properly reason about its own objects, and what they are. The topos perspective reveals deeper properties of categories, and all other algebraic structures which makes it absolutely indispensible.

An example of the power of the topos perspective, is that if we consider $\circ$ as an object of the topos of functions $Sets^{\to}$, we can get non-standard congruences not possible in $Cat$. When working with functions, there is always a need to do all kinds of input/output analysis and no subset of input/output relations is ever sufficent. This way, we can take any partition of the morphism pairs relation to get a quotient.

The congruence $Con(C)$ of a category, is a subset of all input/output relation valid for a category. By the topos perspective, it can defined by an ordered pair $(P,Q)$ which forms a quiver congruence and for which $(Q^2,Q)$ is a function congruence, so they are a subset of $Quiv \times Sets^{\to}$ congruences. This puts congruences in the larger context.

In the case of $Sub(C)$ the lattice of subcategories of a category $C$, the underlying quiver of a subcategory is a subquiver of the underlying quiver of its parent category. Likewise, the composition function is a subfunction of the parent composition function. As before, not all subobjects arise in this way, so the full theory of categorical structure can only be provided by topos theory.

Classical mathematicians correctly understood the importance of set theory in mathematical foundations. Set theory has withstood the test of the time, and any foundational system that ignores the importance of sets is bound to fail. Topos theory is just close enough to set theory, that it can extend it to create new foundations.

External links
Categories - the stacks project