7.2: The Category Set as an Exemplar Topos

We want to think about a very abstract sort of thing, called a topos, because we will see that behavior types form a topos. To get started, we begin with one of the easiest toposes to think about, namely the topos Set of sets. In this section we will discuss commonalities between sets and every other topos. We will go into some details about the category of sets, so as to give intuition for other toposes. In particular, we’ll pay careful attention to the logic of sets, because we eventually want to understand the logic of behaviors.

Indeed, logic and sets are closely related. For example, the logical statement more formally known as a predicate likes_cats defines a function from the set P of people to the set \(\mathbb{B}\) = {false, true} of truth values, where Brendan \(\in\) P maps to true because he likes cats whereas Ursula \(\in\) P maps to false because she does not. Alternatively, likes_cats also defines a subset of P, consisting of exactly the people that do like cats

{p \(\in\) P | likes_cats(p)}.

In terms of these subsets, logical operations correspond to set operations, e.g. AND corresponds to intersection: indeed, the set of people for (mapped to true by) the predicate likes_cats_AND_likes_dogs is equal to the intersection of the set for likes_cats and the set for likes_dogs.

We saw in Chapter 3 that such operations, which are examples of database queries, can be described in terms of limits and colimits in Set. Indeed, the category Set has many such structures and properties, which together make logic possible in that setting. In this section we want to identify these properties, and show how logical operations can be defined using them.

Why would we want to abstractly find such structures and properties? In the next section, we’ll start our search for other categories that also have them. Such categories, called toposes, will be Set-like enough to do logic, but have much more complex and interesting semantics. Indeed, we will discuss one whose logic allows us to reason not about properties of sets, but about behavioral properties of very general machines.

Set-like properties enjoyed by any topos

Although we will not prove it in this book, toposes are categories that are similar to Set in many ways. Here are some facts that are true of any topos \(\mathcal{E}\):

1. \(\mathcal{E}\) has all limits,
2. \(\mathcal{E}\) has all colimits,
3. \(\mathcal{E}\) is cartesian closed,
4. \(\mathcal{E}\) has epi-mono factorizations,
5. \(\mathcal{E} \text { has a subobject classifier } 1 \stackrel{\text { true }}{\longrightarrow} \Omega \text { . }\)

In particular, since Set is a topos, all of the above facts are true for \(\mathcal{E}\) = Set. Our first goal is to briefly review these concepts, focusing most on the subobject classifier.

Limits and colimits. We discussed limits and colimits briefly in Section 3.4.2, but the basic idea is that one can make new objects from old by taking products, using equations to define subobjects, forming disjoint unions, and taking quotients.object 0. One of the most important types of limit (resp. colimit) is that of pullbacks (resp. pushouts); see Example 3.99 and Definition 6.19. For our work below, we’ll need to know a touch more about pullbacks than we have discussed so far, so let’s begin there.

Suppose that C is a category and consider the diagrams below:

In the left-hand square, the corner symbol \(\text { I }\) unambiguously means that the square (B, C, E, F) is a pullback. But in the right-hand square, does the corner symbol mean that (A, B, D, E) is a pullback or that (A, C, D, F) is a pullback? It’s ambiguous, but as we next show, it becomes unambiguous if the right-hand square is a pullback.

Proposition 7.3.

In the commutative diagram below, suppose that the (B, C, B′, C′) square is a pullback:

Then the (A, B, A′, B′) square is a pullback iff the (A, C, A′, C′) rectangle is a pullback.

Exercise 7.4.

Prove Proposition 7.3 using the definition of limit from Section 3.4.2. ♦

Epi-mono factorizations. The abbreviation ‘epi’ stands for epimorphism, and the ab- breviation ‘mono’ stands for monomorphism. Epimorphisms are maps that act like surjections, and monomorphisms are maps that act like injections.\(^{3}\) We can define them formally in terms of pushouts and pullbacks.

Definition 7.5.

Let C be a category, and let f : A → B be a morphism. It is called a monomorphism (resp. epimorphism) if the square to the left is a pullback (resp. the square to the right is a pushout):

Exercise 7.6.

Show that in Set, monomorphisms are just injections:

1. Show that if f is a monomorphism then it is injective.
2. Show that if f : A → B is injective then it is a monomorphism. ♦

Exercise 7.7.

1. Show that the pullback of an isomorphism along any morphism is an isomorphism. That is, suppose that i: B′ → B is an isomorphism and f : A → B is any morphism. Show that i′ is an isomorphism, in the following diagram:

2. Show that for any map f : A → B, the square shown is a pullback:

♦

Exercise 7.8.

Suppose the following diagram is a pullback in a category C:

Use Proposition 7.3 and Exercise 7.7 to show that if f is a monomorphism, then so is f ′. ♦

Now that we have defined epimorphisms and monomorphisms, we can say what epi-mono factorizations are. We say that a morphism f : C → D in E has an epi-mono factorization if it has an ‘image’; that is, there is an object im( f ), an epimorphism C \(\twoheadrightarrow\) im(f), and a monomorphism im(f) \(\rightarrowtail\) D, whose composite is f.

In Set, epimorphisms are surjections and monomorphisms are injections.

Every function f : C → D may be factored as a surjective function onto its image im( f ) = { f (c) | c \(\in\) C}, followed by the inclusion of this image into the codomain D. Moreover, this factorization is unique up to isomorphism.

Exercise 7.9.

Factor the following function f : 3 → 3 as an epimorphism followed by a monomorphism.

♦

This is the case in any topos \(\mathcal{E}\): for any morphism f : c → d, there exists an epimorphism e and a monomorphism m such that f = (e ; m) is their composite.

Cartesian closed. A category C being cartesian closed means that C has a symmetric monoidal structure given by products, and it is monoidal closed with respect to this. (We previously saw monoidal closure in Definition 2.79 (for preorders) and Proposition 4.60, as a corollary of compact closure.) Slightly more down-to-earth, cartesian closure means that for any two objects C, D \(\in\) C, there is a ‘hom-object’ D\(^{C}\) \(\in\) C and a natural isomorphism for any A \(\in\) C:

C(A × C, D) \(\cong\) C(A, D\(^{C}\)) (7.10)

Think of it this way. Suppose you’re A and I’m C, and we’re interacting through some game f(−,−): A × C → D: for whatever action a \(\in\) A that you take and action c \(\in\) C that I take, f (a, c) is some value in D. Since you’re self-centered but loving, you think of this situation as though you’re creating a game experience for me. When you do a, you make a game f (a, −): C → D for me alone. In the formalism, D\(^{C}\) represents the set of games for me. So now you’ve transformed a two-player game, valued in D, into a one-player game, you’re the player, valued in... one player games valued in D. This transformation is invertible you can switch your point of view at will and it’s called currying. This is the content of Example 3.72.

Exercise 7.11.

Let V = (V, ≤, I, ⊗) be a (unital, commutative) quantale see Definition 2.90 and suppose it satisfies the following for all v, w, x \(\in\) V:

• v ≤ I,

• v ⊗ w ≤ v and v ⊗ w ≤ w, and

• if x ≤ v and x ≤ w then x ≤ v ⊗ w.

1. Show that V is a cartesian closed category, in fact a cartesian closed preorder.

2. Can every cartesian closed preorder be obtained in this way? ♦

Subobject classifier. The concept of a subobject classifier requires more attention, because its existence has huge consequences for a category C. In particular, it creates the setting for a rich system of higher order logic to exist inside C; it does so by providing some things called ‘truth values’. The higher order logic manifests in its fully glory when C has finite limits and is cartesian closed, because these facts give rise to the logical operations on truth values.4 In particular, the higher order logic exists in any topos.

We will explain subobject classifiers in as much detail as we can; in fact, it will be our subject for the rest of Section 7.2.

The subobject classifier

Before giving the definition of subobject classifiers, recall that monomorphisms in Set are injections, and any injection X \(\rightarrowtail\) Y is isomorphic to a subset of Y. This gives a simple and useful way to conceptualize monomorphisms into Y when reading the following definition: it will do no harm to think of them as subobjects of Y.

Definition 7.12.

Let \(\mathcal{E}\) be a category with finite limits, i.e. with pullbacks and a ter- minal object 1. A subobject classifier in \(\mathcal{E}\) consists of an object Ω \(\in\) \(\mathcal{E}\), together with a monomorphism true : 1 → Ω, satisfying the following property: for any objects X and Y and monomorphism m : X \(\rightarrowtail\) Y in \(\mathcal{E}\), there is a unique morphism \(\lceil{m}\rceil\) : Y → Ω such that the diagram on the left of Eq. (7.13) is a pullback in \(\mathcal{E}\):

We refer to \(\lceil{m}\rceil\) as the characteristic map of \(\lceil{m}\rceil\), or we say that m classifies \(\lceil{m}\rceil\). Conversely, given any map p : Y → Ω, we denote the pullback of true as on the right of Eq. (7.13).

A predicate on Y is a morphism Y → Ω.

Definition 7.12 is a bit difficult to get one’s mind around, partly because it is hard to imagine its consequences. It is like a superdense nugget from outer space, and through scientific explorations in the latter half of the 20th century, we have found that it brings super powers to whichever categories possess it. We will explain some of the consequences below, but very quickly, the idea is the following.

When a category has a subobject classifier, it provides a translator, turning subobjects of any object Y into maps from that Y to the particular object Ω. Pullback of the monomorphism true: 1 → Ω provides a translator going back, turning maps Y → Ω into subobjects of Y. We can replace our fantasy of the superdense nugget with a slightly more refined story: “any object Y understands itself—its parts and the logic of how they fit together—by asking questions of the oracle Ω, looking for what’s true.” Or to fully be precise but dry, “subobjects of Y are classified by predicates on Y.”

Let’s move from stories and slogans to concrete facts.

The subobject classifier in Set. Since Set is a topos, it has a subobject classifier. It will be a set with supposedly wonderful properties; what set is it?

The subobject classifier in Set is the set of booleans,

Ω\(_{Set}\) := \(\mathbb{B}\) = {true, false}. (7.14)

So in Set, the truth values are true and false.

By definition (Def. 7.12), the subobject classifier comes equipped with a morphism, generically called true: 1 → Ω; in the case of Set it is played by the function 1 → {true, false} that sends 1 to true. In other words, the morphism true is aptly named in this case.

For sets, monomorphism just means injection, as we mentioned above. So Defini- tion 7.12 says that for any injective function m : X \(\rightarrowtail\) Y between sets, we are supposed to be able to find a characteristic function \(\lceil{m}\rceil\): Y → {true,false} with some sort of pullback property.

We propose the following definition of \(\lceil{m}\rceil\):

In other words, if we think of X as a subobject of Y, then we make \(\lceil{m}\rceil\)(y) equal to true iff y \(\in\) X.

In particular, the subobject classifier property turns subsets X \(\subseteq\) Y into functions p : Y → \(\mathbb{B}\), and vice versa.

How it works is encoded in Definition 7.12, but the basic idea is that X will be the set of all things in Y that p sends to true:

X = {y \(\in\) Y | p(y) = true}. (7.15)

This might help explain our abstract notation {Y | p} in Eq. (7.13).

Exercise 7.16.

Let X = \(\mathbb{N}\) = {0, 1, 2, ...} and Y = \(\mathbb{Z}\) = {..., −1, 0, 1, 2, ...};

we have X \(\subseteq\) Y, so consider it as a monomorphism m : X \(\rightarrowtail\) Y.

It has a characteristic function \(\lceil{m}\rceil\) : Y → \(\mathbb{B}\), as in Definition 7.12.

1. What is \(\lceil{m}\rceil\)(−5) \(\in\) \(\mathbb{B}\)?

2. What is \(\lceil{m}\rceil\)(0) \(\in\) \(\mathbb{B}\)? ♦

Exercise 7.17.

1. Consider the identity function id\(_{\mathbb{N}}\) : \(\mathbb{N}\) → \(\mathbb{N}\).

It is an injection, so it has a characteristic function id\(\lceil{_{\mathbb{N}}}\rceil\) : \(\mathbb{N}\) → \(\mathbb{B}\).

Give a concrete description of id\(\lceil{_{\mathbb{N}}}\rceil\), i.e. its exact value for each natural number n \(\in\) \(\mathbb{N}\).

2. Consider the unique function !\(_{\mathbb{N}}\) : Ø → N from the empty set. Give a concrete description of \(\lceil{!_{\mathbb{N}}}\rceil\): \(\mathbb{N}\) → \(\mathbb{B}\). ♦

Logic in the topos Set

As we said above, the subobject classifier of any topos \(\mathcal{E}\) gives the setting in which to do logic. Before we explain a bit about how topos logic works in general, we continue to work concretely by focusing on logic in the topos Set.

Obtaining the AND operation. Consider the function 1 → \(\mathbb{B}\) × \(\mathbb{B}\) picking out the element (true, true). This is a monomorphism, so it defines a characteristic function \(\lceil{(true, true)}\rceil\) : \(\mathbb{B}\) × \(\mathbb{B}\) → \(\mathbb{B}\). What function is it? By Eq. (7.15) the only element of \(\mathbb{B}\) × \(\mathbb{B}\) that can be sent to true is (true, true). Thus \(\lceil{(true, true)}\rceil\) (P, Q) \(\in\) \(\mathbb{B}\) must be given by the following truth table

This is exactly the truth table for the AND of P and Q, i.e. for P \(\bigwedge\) Q. In other words, \(\lceil{(true, true)}\rceil\) = \(\bigwedge\).

Note that this defines \(\bigwedge\) as a function \(\bigwedge\): \(\mathbb{B}\) × \(\mathbb{B}\) → \(\mathbb{B}\), and we use the usual infix notation x \(\bigwedge\) y := \(\bigwedge\) (x, y).

Obtaining the OR operation. Let’s go backwards this time.

The truth table for the OR of P and Q, i.e. that of the function \(\bigvee\): \(\mathbb{B}\) × \(\mathbb{B}\) → \(\mathbb{B}\) defining OR, is:

If we wanted to obtain this function as the characteristic function \(\lceil{m}\rceil\) of some subset m : X \(\subseteq\) \(\mathbb{B}\) × \(\mathbb{B}\), what subset would X be? By Eq. (7.15), X should be the set of y \(\in\) Y that are sent to true. Thus m is the characteristic map for the three element subset

X = {(true, true), (true, false), (false, true)} \(\subseteq\) \(\mathbb{B}\) × \(\mathbb{B}\).

To prepare for later generalization of this idea in any topos, we want a way of thinking of X only in terms of properties listed at the beginning of Section 7.2.1. In fact, one can think of X as the union of {true} × \(\mathbb{B}\) and \(\mathbb{B}\) × {true} a colimit of limits involving the subobject classifier and terminal object. This description will construct an analogous subobject of Ω × Ω, and hence classify a map Ω × Ω → Ω, in any topos \(\mathcal{E}\).

Exercise 7.19.

Every boolean has a negation, ¬false = true and ¬true = false. The function ¬ : \(\mathbb{B}\) → \(\mathbb{B}\) is the characteristic function of some thing, (*?*).

1. What sort of thing should (*?*) be? For example, should ¬ be the characteristic function of an object? A topos? A morphism? A subobject? A pullback diagram?

2. Now that you know the sort of thing (*?*) is, which thing of that sort is it? ♦

Exercise 7.20.

Given two booleans P, Q, define P ⇒ Q to mean P = (P \(\bigwedge\) Q).

1. Write down the truth table for the statement P = (P \(\bigwedge\) Q):

2. If you already have an idea what P ⇒ Q should mean, does it agree with the last column of table above?

3. What is the characteristic function m : \(\mathbb{B}\) × \(\mathbb{B}\) → \(\mathbb{B}\) forP ⇒ Q?

4. What subobject does m classify? ♦

Exercise 7.21.

Consider the sets E := {n \(\in\) \(\mathbb{N}\) |n is even}, P := {n \(\in\) \(\mathbb{N}\) |n is prime}, and T := {n \(\in\) \(\mathbb{N}\) | n ≥ 10}. Each is a subset of N, so defines a function N → B.

1. What is \(\lceil{E}\rceil\)(17)?

2. What is \(\lceil{P}\rceil\)(17)?

3. What is \(\lceil{T}\rceil\)(17)?

4. Name the smallest three elements in the set classified by (\(\lceil{E}\rceil\) \(\bigwedge\) \(\lceil{P}\rceil\)) \(\bigvee\) \(\lceil{T}\rceil\). ♦

Review. Let’s take stock of where we are and where we’re going. In Section 7.1, we set out our goal of proving properties about behavior, and we said that topos theory is a good mathematical setting for doing that. We are now at the end of Section 7.2, which was about Set as an examplar topos. What happened?

In Section 7.2.1, we talked about properties of Set that are enjoyed by any topos: limits and colimits, cartesian closure, epi-mono factorizations, and subobject classifiers. Then in Section 7.2.2 we launched into thinking about the subobject classifier in general and in the specific topos Set, where it is the set \(\mathbb{B}\) of booleans because any subset of Y is classified by a specific predicate p : Y → \(\mathbb{B}\). Finally, in Section 7.2.3 we discussed how to understand logic in terms of Ω: there are various maps \(\bigwedge\), \(\bigvee\), ⇒: Ω × Ω → Ω and ¬: Ω → Ω etc., which serve as logical connectives. These are operations on truth values.

We have talked a lot about toposes, but we’ve only seen one so far: the category of sets. But we’ve actually seen more without knowing it: the category C-Inst of instances on any database schema from Definition 3.60 is a topos. Such toposes are called presheaf toposes and are fundamental, but we will focus on sheaf toposes, because our topos of behavior types will be a sheaf topos. Sheaves are fascinating, but highly abstract mathematical objects. They are not for the faint of mathematical heart (those who are faint of physical heart are welcome to proceed).