Notes from Goldblatt's Topoi book

arrow
Paris

A topos is a categorical interpretation of boolean logic. We will start with some prerequisite set theory and category theory, build up the intuition for subobject classifiers, give an interpretation of set theory, and then move to formalizing boolean algebra using sheaves. The study of topoi is the study of cartesian-closed categories with subobject classifiers, and a category of sheaves over is a complete boolean algebra.

Some set theoretic foundations

The study of set theory starts with the study of Russell's paradox, and axiomatization into Zermelo-Frankel set theory with no paradoxes. To understand Russell's paradox, we first introduce the principle of comprehension: says that is an element of a set that satisfies the predicate . Now, we construct the Russell set , and ask if is a member of this set. If , then its elements belong to a set satisfying the predicate , yielding ; if , then its elements belong to a set satisfying the predicate , yielding . This leads to a contradictory conclusion.

In ZF set theory, we say that a set can only be built up from another set using logical connectives like , , and . The axioms can only be applied to a set and the result is always a set. The comprehension principle is replaced by a separation principle: Given a set , and a predicate , there exists a set whose members are precisely the members of that satisfy the predicate. isn't admitted as a set in this theory, thus resolving the contradiction.

In category theory, the central concept of membership of an element in a set is replaced by the concept of a morphism between objects whose internal structures (elements) are opaque.

Functions to elementary category theory

We would first like to ask how functions are formalized in terms of sets. A function takes objects of to objects of , represented as the pair , such that . This formalism is weak because it doesn't include the domain, codomain, or the relation explicitly. To remedy this, we define the , with as the domain, the codomain, and

the relation. Note that functions are composable yielding a unique satisfying the associative law .

We can further abstract functions to arrows between objects in a category. The notion of "set membership" is an "internal notion" between the various members of the object, and needs to be "externalized". Let's start with some category theory.

A category consists of a bunch of objects, a bunch of arrows between the objects, including the identity arrow for each , with an associative law for compositions:

A pre-order is defined as a category in which there is at most one arrow, , between any two objects and . In this kind of category, called there is only one way to define composites. If and are any objects on a pre-order category, and is a binary relation, then we can identify two properties of :

  1. Reflexivity: for each , we have , the identity arrow.
  2. Transitivity: whenever and , we have .

The typical example is to think of two non-comparable subsets of a set. With identity arrows omitted, this looks like:

With one additional property described below, a pre-order becomes a partial ordering:

  1. Anti-symmetry: whenever and , we have .

A set together with the relation , denoted as , is called a poset. The specific category we have used to encode above is called , the category of finite ordinals. In , these three statements are equivalent:

With one additional property, a partial ordering becomes a total ordering:

  1. Connexity: For all , , pRq or qRp.

Using to denote the relation, we can encode as , , , and so on, yielding

This is a total order.

Let us now consider categories with more than one arrow between two objects. A monoid is defined as an algebraic structure 𝟙 where is a function from . A monoid naturally gives rise to a category with just one object: . We can instantiate it with , , and 𝟙 to obtain the familiar notion of addition of natural numbers:

If , then we use to denote the set of arrows from to . A subcategory is defined as:

  1. All objects of are objects of .
  2. ; all arrows of are present in .

A full subcategory of is defined as such that ; in other words, has no arrows other than the ones already present in . is a full subcategory of , the category of finite sets.

Before introducing comma categories, let us briefly introduce arrow categories as a prerequisite. An arrow category has as objects, the functions , and arrows between objects and , the pair of arrows such that the following diagram commutes:

A comma category can be viewed as a special case of an arrow categories with fixed domain or codomain. is the category of real-valued functions; the codomain of the category is fixed to . An arrow from to is the arrow that makes the following commute:

can be construed to a as follows:

Similarly, we can define to be a comma category with a fixed domain instead of codomain:

Set membership, categorically

To work our way up to subobject classifiers, we need to build some prerequisite material. First, let us introduce the notion of monic and epic arrows, corresponding to injective and surjective functions in . is injective if , and surjective if .

If is monic, indicated as , the diagram above commutes, and

In other words, a monic is said to be left-cancelable.


If is monic, so is .


If is epic, indicated as , the diagram above commutes, and

In other words, an epic is said to be right-cancelable.

An iso arrow, indicated as , corresponds to a bijective function in . It is invertible, and its action can be thought of as a "relabeling"; as an example, attaches to every element of .

Every iso is both monic and epic, but "iso" isn't equivalent to "monic and epic". Consider in which all arrows are monic and epic, but the only iso arrows are the identities, since no natural number has an additive inverse.


is iso, if and are, with .


An initial object 𝟘 is such that, for every in , there exists only one arrow 𝟘, and a terminal object 𝟙 is such that, for every in , there exists only one arrow 𝟙. In , is distinguished to be the initial object because there exists only one function from to every other element in the category, namely , the empty function; the graph of is empty; and , the singleton set is distinguished to be the terminal object.


All initial objects are isomorphic to each other. By duality, all terminal objects are also isomorphic to each other.

Indeed, let 𝟘𝟘 be two initial objects. Consider 𝟘𝟘𝟘𝟘 so that 𝟘𝟘𝟘 and 𝟘; so , and 𝟘𝟘.


𝟙 is monic.

𝟙

. Now, is true because there is only one arrow to it from any given object, and hence, is monic.


𝟙.

By uniqueness of identity arrow, 𝟙.


If , then and .

By definition of product, since this diagram commutes,

Hence, and .


.

The following diagram commutes:

yielding:

Combining and , we get:


.

For isomorphism, there needs to exist and , such that 𝟙. From the diagram, we see that this is indeed the case: