Categorical logic and topoi

Category theory and set theory are two of the pillars of modern mathematics. At first glance one might assume that these are disconnected branches of mathematical inquiry, but in actuality they are united by the theory of topoi. Topoi allow for the creation of a categorical set theory, which in turn can be used to create a categorical foundation of mathematics.

The foundation of categorical logic lies in the action preorders carved out by the action of composition of morphisms on one another. Action preorders can be condensed to get partial orders. In the case of topoi, at least one type of compositional action induces an action preorder with distributive lattice condensation, which can be used to recover the lattice of sets from the action of composition.

Elementary topoi:

Preliminaries:

Categories are a dualistic structure containing both objects and morphisms. Both of these two types of elements are preordered in different ways. Objects are preordered by the morphic preordering, and morphisms are preordered by the action of composition.

• Objects: morphic preordering
• Morphisms: action preordering

Categories have a second form of duality because they are non-commutative which means that there are two different types of composition. This means that morphisms can either act on the inputs or the outputs of the other morphism. Further special classes of actions can determined by special types of morphisms like monomorphisms, epimorphisms, and isomorphisms. This is clarified by the following diagram:

The isomorphisms of a category are composition closed, and so form the underlying groupoid of the category. The isomorphism action preordering of the category is therefore merely the action induced by the underlying groupoid. Two morphisms are isomorphic to one another if they can be reached by composition of isomorphisms. In general, given any subcategory we can get a preorder of morphisms determined by the action of that subcategory.

The first thing to realize is that given any morphism $f : A \to B$ then the input actions leave the output uneffected and the output actions leave the input object uneffected. Input and output objects therefore break up the input and output action preorders into connected components. The morphic preorder comes into play as the output object of any output action can only be a successor of $B$ and the input object of any input action can only be a predecessor of $A$. This is the manner in which the morphic preordering effects action preorderings.

Functions are destructive: In the category of sets each function has an image and input action can only decrease the image. Equating subobjects with images, composition is also decreasing for subobjects. Therefore, to recover the effect of functions on subobjects, we need to use a decreasing action preorder.

We can isolate the input and output structures by monomorphisms and epimorphisms. Therefore, the overall subobject preorder is merely the decreasing mono input action preorder. All subobject preorders are suborders of the overall decreasing mono input action preorder. In particular, for any object $A$ the preorder of subobjects is principal ideal of $1_A$. Objects are represented by their identity morphisms, and then all subobjects are morphisms reachable from the identity by input composition with a monomorphism.

Definition. for a category $C$ and any object $A$ then $Sub(A)$ is the condensation of the principal ideal induced by $1_A$ in the decreasing mono input action preordering.

We can dualize and define $Quot(A)$ the partial order of quotient objects by decreasing epi actions on the identity morphism $1_A$. The duality of $Sub(A)$ and $Quot(A)$, which emerge from two types of action preorder, is a consequence of the non-commutativity of categories. These two partial orders are generally the most important ones that exist for any category.

In a topoi, $Sub(A)$ forms a distributive lattice. In the topoi of sets, $Sub(A)$ is the power set of $A$. In this manner, we see how we can recover the ordering of sets simply from the effect of composition of functions. The power set ordering is recovered from the manner in which functions tear down and destroy images.

Subobject classifier:

Presented below is the standard categorical definition of the subobject classifier. Accompanying it is an explanation of what each of the categorical elements (commonly referred to by single letter variable names) refer to.

Objects:

• $a$ is the pullback object of the diagram and the subobject of $d$ which is being classified
• $d$ is the parent object of the subobject $a$
• 1 is any terminal object, which means that there is a unique morphism to it from any object
• $\Omega$ is the object of truth values, which is used to classify subobjects, it is selected ahead of time as part of the definition of the subobject classifier

Morphisms:

• true is an element monomorphism because it emerges from a terminal object. It selects a truth value element out of the object of truth values
• ! is a uniquely determined morphism because it is targeting a terminal object
• f is the inclusion monomorphism which embeds the subobject $a$ in the parent object $d$
• $x_f$ is the characteristic morphism, which must be uniquely determined from the rest of the diagram in a manner which makes it a pullback in order for the category to have a subobject classifier

Characterizing properties of topoi:

An elementary topoi is bicomplete meaning that it has an initial object, a terminal object, pullbacks and pushouts. It has exponentation, so that hom classes can be turned into objects of the category in their own right. Finally, it must have a subobject classifier.

Definition. an elementary topoi is a bicomplete category with exponentation and subobject classifiers

The subobject classifier means that epimorphism-monomorphism factorisations are unique up to a commuting isomorphism. The classifying morphisms of the subobject classifier $\chi_f$ are in bijection with the lattice of subobjects $Sub(A)$.

Lattice of subobjects:

While every category has an action preorder determined by the input action of monomorphisms, its not always guaranteed the condensations of principal ideals form lattices. On the other hand, in elementary topoi it is the case that the action of composition on morphisms creates lattices for each object.

• The meet of two morphisms in $Sub(A)$ is the pullback of the two monomorphisms
• The join of two morphisms in $Sub(A)$ is the monic component of the coproduct arrow determined the cocone formed by the pair of common output monomorphisms

There is a natural dichotomy between pullbacks and subobject classifiers. The subobject classifier is sort of like an inverse limit, in the sense that it is a fills out a diagram so that it forms a limit. In this manner, take the unique morphism $0 \to 1$ and form its subobject classifier. This produces an element morphism $false : 1 \to \Omega$ that selects the false truth value out of the object of truth values.

Then $false : 1 \to \Omega$ is an element monomorphism so we can get the subobject classifier of it with respect to $\Omega$ which is an endomorphism $\neg : \Omega \to \Omega$. The pseudo-complement of $f$ is then formed by the unique monomorphism which has $\neg \circ \chi_f$ as a subobject classifier. This makes $Sub(A)$ into a Heyting algebra.

Properties of topoi:

What makes set theory so special? The answer comes in certain completeness conditions that sets satisfy, but other structures do not. In representation theory it is customary to represent groups by group actions on vector spaces, in order theory on the other hand we represent partial orders by families of sets. For example, {{1},{1,2}} is merely the set system representation of the total order (1,2). When represented as set systems, you can see what sort of sets are missing from a partial order.

When we have an arbitrary partial order the first thing you might notice is that it lacks meets and joins. We can add them in by various means, including by the Dedekind-MacNeile completion. This embedding may still lack certain unions and intersections, so next we can add them to get a distributive lattice. For example, consider {{0},{1},{1,2}}. We can make this into a lattice by adding bounds {{},{0},{1},{1,2},{0,1,2}} but it is still not a distributive lattice. There is a single element missing {0,1} from making it distributive, so adding it we get {{},{0},{1},{0,1},{1,2},{0,1,2}}. Next we can add complements to get a boolean algebra.

Perhaps the most important property that makes sets so special is atomicity. Really, set theory is the theory of how things are built up from their most basic atomic building blocks. These atomic building blocks are typically called members, but the important point is that they are atoms. Singleton sets, which correspond directly to entities that cannot be broken down any further, are the building blocks of all sets. It is a deep and correct realisation that everything is built up of atoms, and so everything is a certain type of set.

If a lattice or any other structure is not atomistic, then in some sense it is missing the atoms originally used to build it up. For example, if we take a lattice ordered family of sets which is not atomistic, it is constructed from something that was atomistic but it is not anymore. So even atomicity is a sort of completeness condition. If we take the previous distributive lattice we had, and make it atomistic we get {{},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}} which is an embedding of a partial order in an atomic boolean algebra. Therefore we have a hierarchy of properties which distinguish sets: they are lattices, distributive lattices, boolean algebras, and atomistic. We can relate these distinguishing properties of sets to elementary topoi.

Definition. an elementary topoi is:

1. atomic if $Sub(A)$ is atomic for each object $A$
2. boolean if $Sub(A)$ is atomic for each object $A$

A category is essentially a structured set or class with two types of elements: objects and morphisms. If the objects form an atomic boolean algebra, then that addresses the question of the construction of objects from atoms. This leaves the question of how morphisms are originally constructed from atomic building blocks. If we consider morphisms as essentially functions, then clearly they are constructed from sets of ordered pairs. We can apply this to elementary topoi, to define elementary topoi that are capable of characterizing their morphisms by atoms, which are precisely the element arrows $1 \to A$.

Definition. an elementary topoi is well-pointed if for each $f : A \to B$ and $g : A \to B$ such that $f \not= g$ there exists $m : 1 \to A$ such that $f \circ m \not= g \circ m$.

In a well-pointed topoi the set used to define a function $f$ can be recovered by the sets of ordered pairs of element morphisms followed by the morphism produced by composition of $f$ with the element morphism. This is possible in a well-pointed topoi, but it may not be possible in all categories. Combining the properties that we have acquired together, we can determine what distinguishes the category of sets from other categories:

Definition. the category of sets forms an atomic boolean well-pointed topoi

The topoi of sets, which satisfies these properties, is in some sense the most complete category. Other categories are characterized by what they are lacking: such as certain limits, exponentation, a subobject classifier, subobject complements, well pointedness, etc. It is now possible to study categories that are not well-pointed, and in doing so temporarily forget the fact that functions are sets of ordered pairs. This leads to the distinctly categorical point of view.

At the start we mentioned that it is common to represent partial orders by set systems. This produces a monotone map from a partial order to the inclusion ordering of sets. Examples include the order isomorphism from a total order on two elements to its ordered pair {{0},{0,1}} and the order isomorphism from a well-order to its Von Neumann ordinal. In the same vein, we can create functors from categories to the topoi of sets. Although we are now studying objects like partial orders and categories that don't have all the nice completeness properties that sets have, we can relate them back to sets using set valued functors.

The category of sets:

We previously characterized the category of sets as an atomic boolean well-pointed elementary topoi, now we can consider its actual structure. The first thing to realize is that the action of composition of the topoi of sets creates two different types of lattices through condensation: the boolean algebra of sets $\mathcal{P}(A)$ and the order dual of the lattice of set partitions $Part(A)^d$. What this means is that compositional action is decreasing with respect to images and kernel equivalence relations. These two lattices fundamentally define the structure of the topoi of sets and functions.

• initial object : $\emptyset$
• terminal object : any singleton set
• products : the product in the category of sets is defined by the direct product in the lattice of partitions $Part(A)^d$. The product arrow is the morphism which maps each pair of morphism to its projection components in the direct product.
• coproducts: the coproduct in the category of sets is defined by the disjoint union in the lattice of sets $\mathcal{P}(A)$. Two sets can be made disjoint by giving them separate labels. The two sets in the coproduct are mapped to their labeled components. The coproduct map of a cocone with two maps on the labeled components then maps the disjoint union to its respective value under application of the function associated with the label.
• pullbacks: form the product function of two arrows going to a common output, then take the inverse image of the identity equivalence relation of that output which produces a subset of the product which is the pullback set.
• pushouts: the pushout of two morphisms $f$ and $g$ with a common input is the disjoint union with elements with a common pre-image identified together.
• subobject classifier : the subobject classifier converts any inclusion function to a function that returns true for all included elements and false for all other elements in the bivalent object of truth values
• exponentation: any hom class $(A,B)$ can be mapped to its function space $B^A$, then if we form the direct product of $B^A$ and $A$ there is a unique map from $A$ to $B^A \times A$ which identifies any function $f$ with its element in its function space and $A$ with its identity, for which any function $f$ filters through.
• element arrows $1 \to A$ generate any subobject by subobject join and they determine the equivalence of morphisms

The combination of these properties makes Set into an elementary topoi. The last one, that element arrows $1 \to A$ determine morphism equality make it into a well-pointed topoi. The property of being well-pointed is necessary to distinguish it from other topoi that are not well-pointed.

Set-valued functors:

It was previously mentioned that it is customary to represent any partial order by a set system. In category theory, it is equally important to consider structure preserving maps from categories to arbitrary categories to the topoi of sets. Here are some examples:

1. the defining property of concrete categories is that they have a faithful functor to the topoi of sets.

2. the mapping $f : I \to Set$ from a discrete category to $Set$. These are equivalent to multi-valued functions, as they associate each object of the discrete category to a set.

3. the mapping $f : T_2 \to Set$ from a total order on two elements to $Set$ which selects a single function $f : A \to B$ associated to the ordered pair.

4. monoid actions $f : M \to Set$ can be defined by a functor from a single-object category to $Set$.

5. simplicial sets $f : \Delta \to Set$ are set-valued functors from the category of non-empty finite ordinals and monotone maps to $Set$.

6. presheafs, monopresheafs, sheafs, and schemes are functors either to $Set$

The deep realisation of topoi theory is that any hom class of set-valued functors on a small category forms a topoi. All the constructions related to elementary topoi can therefore be applied to any of these functor categories. For example, there is a lattice of subobjects formed by classes of natural transformations of sheafs.

Sources:

[1]Topoi categorical analysis of logic
Robert Goldblatt

[2] Sheaves in geometry in logic
Saunders Maclane