Schreiber category of sets, universes, categories

Introductory words on the need and role of foundations

We need the language of category theory in order to talk about sheaves. This language is very fundamental to mathematics, so much that in the course of setting it up one has to consider foundational issues: all of mathematics is supposed to be chain of rigorous deduction, but some very basic concepts need to be assumed be be universally understood by grace, and all deduction is based on these universally understood concepts.

This basic concept has traditionally be taken to be that of a collection of elements – a set – with a global binary relation – $\in$ – that determines which sets are elements of other sets. Naïve and obvious as it may seem, there is some subtlety hidden here, related to the global nature of the inclusion relation.

After the advent of category theory it was argued by Lawvere and others, that, roughly, what is truly fundamental is not so much the concept of a set itself, but rather the interrelation between sets in terms of functions between them. These form the category Set of sets.

In every development – notably in that that of sheaves and stacks — for which category theoretic language is crucial anyway, it is natural to take as foundations Lawvere’s Elementary Theory of the Category of Sets (ETCS), which takes as the fundamental concept the naïve theory of the category of sets and then develops everything else from within this context. Here “naïve” means “understood by grace” and not further deriveable.

One advantage of this perspective is that it allows to naturally address and handle concerns and disagreement about what actually does count as naive and universally accepted basis of all reasoning. This is because the crucial property of the naïve category of sets is that it is a kind of category called a topos: a “place” in which mathematics may be developed. When one strictly sticks in the development of mathematical notions to constructions within ETCS as opposed to, say, the traditional Zermelo-Fraenkel axiomatics for set theory, then all constructions and results make sense in any other topos. For instance in constructivism is a school which asserts that some axioms about naïve sets are not quite naïve enough and reject them, notably the axiom of excluded middle. This point of view turns out to be perfectly compatible, and in fact enforced, by the topos-theoretic perspective on foundations.

But because ETCS contains nonconstructive axioms (the axiom of choice, also strong extensionality if it is written in classical predicate calculus), not everything done there is acceptable to a constructivist. Similarly, these same axioms, as well as infinity, fail in some toposes, so not everything in ETCS works in any other topos. —Toby

Elementary Theory of the Category of Sets

• Elementary Theory of the Category of Sets – ETCS

• a “structural” formalization of set theory which combines the rich tradition of naïve (= pre-axiomatic) set theory with the insights of category theory

• literature:

  • Lawvere, Rosebrugh: Sets for Mathematics

  • Todd Trimble: ETCS I, II, III

• ETCS differs from non-structural material set theory in the way it handles the membership relation $\in$:

  • in ETCS “sets” and “elemens” are of different type: not every element of a set is necessarily a set itself;

  • no element exists in isolation: it always exists relative to the set that it is an element of.

  • there are also generalized elements: functions – conversely, functions between sets – called then morphisms in the category of sets – are regarded as primary, and the notion of element is derived from that: an element $s \in S$ of a set $S$ is regarded as the function $* \stackrel{\bullet \mapsto s}{\to} S$ that sends the single element of the singleton set $* = \{\bullet\}$ to $s$.

  • general category theoretic perspective: what matters are the morphisms $S \to T$, not so much any imagined “inner structure” of the objects $S$, $T$.

• in techical terms the categroy of sets Set to be described now is

  • a topos;

  • which is well-pointed;

  • satisfies the axiom of choice;

  • and is equipped with a natural numbers object

Now the definition.

Set consists of

• a collection of “objects” called “sets”, $S, T, \cdots$;

• a collection of “arrows” called “morphisms” called “functions” that go between pairs of objects, $f : S \to T, \cdots$

  • for every object $S$ a morphism denoted $Id_S : S \to S$, called the identity function on $S$;

• a composition operation $(R \stackrel{f}{\to} S , S \stackrel{g}{\to} T) \mapsto (R \stackrel{g \circ f}{\to} T)$ on all pairs of composable morphisms;

  • such that this comoposition is associative;

  • such that the morphisms of the form $Id_S$ are units with respect to this compositon.

Remark So far this would say that Set is a category: but the point is that we take the above now as a primitive notion and avoid saying “a category consists of a set/class of objects, etc.”. Rather, below we define the notion of category as a concept internal to Set.

Notation

A function $s : T \to S$ we also call an element $s \in S$ of $S$ with domain $T$ (or “stage of definition” $T$).

If we allow ourselves to denote comopsition $g \circ f$ simply by juxtaposition $g \circ f = g f$ then for $f : S \to T$ a function and $x : U \to S$ regarded as an element of $S$ (over domain $U$), the notation $f x : U \to T$ denotes consistently both the composition of two functions and the application of th function $f$ to the element $x$.

This is the sense in which ETCS is “structural”: there is no separate notion of element, everything is in the relational structure defined by composition of morphisms.

This structure of Set is required to satisfy the following axioms.

Axiom of products.

• Set admits finite products.

• This means first of all: For any two sets $S, T$, there is a set $C$ and functions $p_1: C \to S$, $p_2: C \to T$, such that given two elements $x \in S, y \in T$ over the same domain, there exists a unique element $\langle x, y \rangle \in C$ over that domain for which

$$p_1\langle x, y \rangle = x \qquad p_2\langle x, y \rangle = y$$

• In terms of morphisms this means: given two morphisms $x : U \to S$ and $y : U \to T$ , there exists a unique morphism $\langle x, y \rangle : U \to C$ such that the following diagram commutes

$$\array{ && U \\ & {}^x \swarrow &\downarrow^{\langle x , y \rangle}& \searrow^{y} \\ S &\stackrel{p_1}{\leftarrow}& C &\stackrel{p_2}{\to}& T }$$

A choice of product $C$ is usually denoted $S \times T$. To make a bridge with naive set-theory notation, we may suggestively write

$$S \times T :=_i \{\langle x, y \rangle: x \in S, y \in T\}$$

where the funny equality sign and bracketing notation on the right simply mean that the cartesian product is uniquely defined up to isomorphism by its collection of (generalized) elements, which correspond to pairs of elements.

• Moreover, admitting finite products also means that there is the empty product exists: there is an object $*$ in Set

  • which has a unique element $x \in *$ over any domain;

  • equivalently: such that for every other object $S$ there is a unique morphism $S \to *$

Notation

The above implies in particulat that for two functions $f : S \to S'$ and $g : T \to T'$ there is canonically a function denoted

$$f \times g : S\times T \to S' \times T'$$

induced by the universal property of $S' \times T'$ by from the existence of the two functions $f p_1 : S \times T \to S'$ and
$g p_2 : S \times T \to T'$

Axiom of equalizers.

For any two functions $\displaystyle f, g: S \rightrightarrows T$, there exists a function $i: E \to S$ such that

1. $f i = g i$,
2. Given $x \in S$ over some domain such that $f x = g x$, there exists a unique $x' \in e$ over the same domain such that $i x' = x$.

Equivalently, in morphism language:

1. $(E \stackrel{i}{\to} S \stackrel{f}{\to} T) = (E \stackrel{i}{\to} S \stackrel{g}{\to} T)$,
2. Given any other $x : U \to S$ such that $(U \stackrel{x}{\to} S \stackrel{f}{\to} T) = (U \stackrel{x}{\to} S \stackrel{g}{\to} T)$, there exists a unique $x' : U \to E$ over the same domain such that the following diagram commutes

$$\array{ && U \\ &{}^{x'}\swarrow& \downarrow^{x} \\ E &\stackrel{i}{\to}& S &\stackrel{\stackrel{g}{\to}}{\stackrel{f}{\to}}& T }$$

An equalizer $i: E \to S$ is again defined up to isomorphism by its collection of generalized elements, denoted $E :=_i \{x \in S: f(x) = g(x)\} \hookrightarrow S$.

Consequence: pullbacks

The axiom of products and the axiom of equalizers already ensure that Set has pullbacks

Given functions $f: S \to C, g: T \to C$ there exists a set $S \times_C T$ and functions $p_1 : S \times_C T \to S$ and $p_2 : S \times_C T \to T$ such that the diagram

$$\array{ S \times_C T &\stackrel{p_2}{\to}& T \\ \downarrow^{p_2} && \downarrow^{g} \\ S &\stackrel{f}{\to}& C }$$

commutes and such that for every other such diagram

$$\array{ U &\stackrel{y}{\to}& T \\ \downarrow^{x} && \downarrow^{g} \\ S &\stackrel{f}{\to}& C }$$

there is a unique function $R \to S \times_S T$ such that

$$\array{ && U \\ & {}^x \swarrow &\downarrow^{\langle x , y \rangle}& \searrow^{y} \\ S &\stackrel{p_1}{\leftarrow}& S \times_C T &\stackrel{p_2}{\to}& T }$$

One checks that indeed $S \times_C T$ is equivalently the equalizer of $f p_1$ and $g p_2$:

$$S \times_C T \hookrightarrow S \times T \stackrel{\stackrel{g p_2}{\to}}{\stackrel{f p_1}{\to}} C$$

Hence we may write

$$S \times_C T \simeq \{\langle x, y \rangle \in S \times T: f x = g y\}$$

$S \tines_C T$ is the fiber product of $f$ with $g$: over $c \in C$ it is the product of the fibers $f^{-1}c = \{x | f x = c\}$ and $g^{-1}c = \{y | g y = c\}$.

Terminology.

With this structure in hand, we obtain the useful notions of subsets and relations in Set.

A function $i: S \to T$ is injective if for every $x, y \in S$ over the same domain, $i x = i y$ implies $x = y$.

Equivalently, in morphism notation: $i$ is a monomorphism if for every $x : U \to S$ and $y : U \to S$, $i \circ x = i \circ y$ implies $x = y$.

Dually, a $f : S \to T$ is a a surjective function or epimorphism if for every $g : T \to U$ and $h : T \to U$, $g f = g h$ implies $g = h$.

Given a monomorphism $i: S \to T$ we may think of it as defining a “subset” $S$ of $T$, whose (generalized) elements correspond to those elements $z \in T$ which factor (evidently uniquely) through $i$. It is in that sense that we say $z \in T$ also “belongs to” a subset $S$, while, contrary to non-structural set theory, strictly speaking every element in the language of ETCS is element only of one single set.

A relation from $S$ to $T$ is an injective function or subset $R \hookrightarrow S \times T$.

Now we can state the next axiom

Axiom of power sets.

For every set $S$ there is a set denoted $P(S)$ or $\mathbf{2}^S$ and called the power set of $S$ and a relation $\in_S \hookrightarrow S \times \mathbf{2}^S$ to be thought of as “is element of subset $U \subset S$ in $S$” so that for every relation $R \hookrightarrow T \times S$, there exists a unique function $\chi_R: T \to \mathbf{2}^S$ such that $R$ is obtained up to isomorphism as the pullback

$$\{\langle x, y \rangle \in T \times S: y \in_S \chi_R(x)\} \,.$$

i.e the universal commutative diagram

$$\array{ R &\to& S \times T \\ \downarrow && \downarrow^{Id \times \chi_R} \\ \in_S &\hookrightarrow& S \times \mathbf{2}^S }$$

In other words, $\langle x, y \rangle$ belongs to $R$ if and only if $\langle y, \chi_R(x) \rangle$ belongs to $\in_S$.

Axiom of strong extensionality.

An element $x : * \to S$ with domain the terminal object we call an “ordinary element” of $S$. Then:

for functions

$$f, g: S \to T,$$

we have $f = g$ if and only if $f x = g x$ for all ordinary elements $x: * \to S$.

Consequence: ordinary element-based notions

Using this principle of extensionality, all the properties of Set described here in terms of generalized elements over varying domains, or, equivalently, described diagrammatically, translate equivalently to the usual element-based definitions. For instance, recall that a function $i : S \to T$ is a monomorphism if $(R \stackrel{f}{\to} S \stackrel{i}{\to} T)= (R \stackrel{g}{\to} S \stackrel{i}{\to} T)$ implies $f = g$. So in particular, for $R = *$ and $f = x : * \to S$, $g = y : * \to S$ ordinary elements, this says that $i x = i y$ implis $x = y$. The converse statement follows similarly.

Axiom of natural numbers object.

There is a set $\mathbf{N}$, together with an element $0: * \to \mathbf{N}$ and a function $s: \mathbf{N} \to \mathbf{N}$, which is initial among sets equipped with such data. That is, given a set $S$ together with an element $x: * \to S$ and a function $f: S \to S$, there exists a unique function $h: \mathbf{N} \to S$ such that

$$h(0) = x; \qquad h s = f h$$

Or, in elementwise notation, $h(n+1) = f h(n)$ for every (generalized) element $n \in \mathbf{N}$, where $n+1$ means $s(n)$. Under strong extensionality, we may drop the qualifier “generalized”.

$$\array{ * &\stackrel{0}{\to}& \mathbb{N} &\stackrel{s}{\to}& \mathbb{N} \\ & {}_x\searrow & \downarrow^{h} && \downarrow^{h} \\ && S &\stackrel{f}{\to} & S }$$

Axiom of choice?.

Every surjective function $f: S \to T$ admits a section, i.e., a function $\sigma : T \to S$ such that $f \sigma = Id_S$, the identity function.

Remark The axiom of choice tends to sound a bit mysterious in non-structural ZFC

set theory. The above structural formulation

gives a rather clear heuristic picture for what the axiom means. See the further remarks and examples at axiom of choice.

** Consequences and further axioms **

This defines the Elementary Theory of the Category of Sets. From these axioms now various further properties follow: notably Set can be shown to be a topos and in particular it is cartesian closed.

There is however so far one axiom missing, that we need. This is the axiom of universes that we will motivate now.

Grothendieck universes

In category theory we frequently want to deal with entities that are “collections of all collections of some sort”. It is familiar that one has to exercise some care here: famously, attempts to define concepts such as “the set of all sets” leads to inconsistencies. These are always due to a failure to preserve a hierarchy of notions of collections: if “Col” is some kind of collections, then “the collection of all Cols” is not in general a Col itself, and should be considered a a new notion, a “col+”, say.

The notion of Grothendieck universe is one way to formalize such a hierarchy of notions of collections. In this context, every collection is always a set in the sense that it is an object in the theory ETCS axiomatized above. But some of these sets behave essentially as if they were a “set+ of all set’s”, for some notion of set’.

universe in a topos

A universe in a topos $\mathcal{E}$ is a morphism $el:E\to U$ satisfying the axioms to follow. We think of $el:E\to U$ as a $U$-indexed family of objects (sets), and we define a morphism $a:A\to I$ (regarded as an $I$-indexed family of objects) to be $U$-small if there exists a morphism $f:I\to U$ and a pullback? square

$$\array{A & \to & E\\ ^a\downarrow && \downarrow^{el}\\ I& \underset{f}{\to} & U.}$$

Note that $f$ is not, in general, unique: a universe can contain many isomorphic sets. With this definition, the pullback of a $U$-small morphism is automatically again $U$-small. We say that an object $X$ is $U$-small if $X\to 1$ is $U$-small.

The axioms which must be satisfied are:

1. Every monomorphism? is $U$-small.

2. The composite of $U$-small morphisms is $U$-small.

3. If $f:A\to I$ and $g:B\to A$ are $U$-small, then so is the dependent product? $\Pi_f g$ (where $\Pi_f$ is the right adjoint to $f^*:\mathcal{E}/I\to \mathcal{E}/A$).

4. The subobject classifier? $\Omega = \mathbf{2}$ is $U$-small.

Let us unwrap what this means:

For $u : * \to U$ an ordinary element of $U$, write $E_u$ for the fiber of $E$ over $u$, i.e. for the pullback $* \times_U E$. We are to think of $E$ as the set of all sets $E_u$.

By definition, a single set $S$, regarded as the unique function $S \to *$, is $U$-small if it is isomorphic to one of these $E_u$.

As for $E \to U$, any function $S \to I$ may be thought of as a family of sets $S_i := * \times_I S$ parameterized by $I$. One finds that $S$ itself is the disjoint union of all the $S_i$ $S = \sqcup_{i \in I} S_i$. Therefore the first first axiom says that with $I \to *$ $U$-small and $S \to I$ a $U$-small family, also $S \to *$ is $U$-small, hence that $\sqcup_i S_i$ is $U$-small:

$U$-small indexed families of $U$-small sets are $U$-small.

Since $\emptyset \to \mathbf{2}$ is a monomorphism, and $\mathbf{2}$ is small by axiom 4), it follows that $\emptyset \to \Omega \to *$ is small and hence $\emptyset$ is a small set. Which sounds very reasonable.

The first axiom says that with $S$ a $U$-small set, also every subset of $S$ is $U$-small.

internal categories and functors

Let $A$ be any category. A category internal to $A$ consists of

• an object of objects $C_0 \in A$;

• an object of morphisms $C_1 \in A$;

together with

• source? and target? morphisms $s,t: C_1 \to C_0$;

• an identity assigning morphism? $e: C_0 \to C_1$;

• a composition? morphism $c: C_1 \times_{C_0} C_1 \to C_1$;

such that the following diagrams commute, expressing the usual category laws:

• laws specifying the source and target of identity morphisms:

$$\array{ C_0 & \stackrel{e}{\to} & C_1 \\ {} & 1\searrow & \darr s \\ {} & {} & C_0 } \quad\quad\quad\quad \array{ C_0 & \stackrel{e}{\to} & C_1 \\ {} & 1\searrow & \darr t \\ {} & {} & C_0 }$$

• laws specifying the source and target of composite morphisms:

$$\array{ C_1 \times_{C_0} C_1 & \stackrel{c}{\to} & C_1 \\ {}^{p_1}\downarrow & {} & \downarrow^{s} \\ C_1 & \stackrel{s}{\to} & C_0 } \quad\quad\quad\quad \array{ C_1 \times_{C_0} C_1 & \stackrel{c}{\to} & C_1 \\ {}^{p_2}\downarrow & {} & \downarrow^{t} \\ C_1 & \stackrel{t}{\to} & C_0 }$$

• the associative law for composition of morphisms:

$$\array{ C_1 \times_{C_0} C_1 \times_{C_0} C_1 & \stackrel{c\times_{C_0} 1}{\to} & C_1 \times_{C_0} C_1 \\ {}^{1\times_{C_0}c}\downarrow & {} & \downarrow^{c} \\ C_1 \times_{C_0} C_1 & \stackrel{c}{\to} & C_1 }$$

• the left and right unit laws for composition of morphisms:

$$\array{ C_1 \times_{C_0} C_1 & \stackrel{e \times_{C_0} 1}{\to} & C_1 \times_{C_0} C_1 & \stackrel{1 \times_{C_0} e}{\leftarrow} & C_1 \times_{C_0} C_1 \\ {} & {}^{p_2}\searrow & \downarrow^{c} & \swarrow^{p_1} & {} \\ {} & {} & C_1 & {} & {} }$$

Here, the pullback $C_1 \times_{C_0} C_1$ is defined via the square

$$\array{ C_1 \times_{C_0} C_1 & \stackrel{p_2}{\to} & C_1 \\ {}^{p_1}\downarrow & {} & \downarrow^{s} \\ C_1 & \stackrel{t}{\to} & C_0 }$$

internal functor

Internal to? an ambient category $A$, a functor $F : C \to D$ is

• a morphism of objects $F_0 : C_0 \to D_0$ in $A$;

• a morphisms of morphisms $F_1 : C_1 \to D_1$ in $A$;

• such that the following diagrams commute

  • respect for the source map: $\array{ C_1 &\stackrel{f_1}{\to}& D_1 \\ \downarrow^s && \downarrow^s \\ C_0 &\stackrel{f_0}{\to}& D_0 }$;

  • respect for the target map: $\array{ C_1 &\stackrel{f_1}{\to}& D_1 \\ \downarrow^t && \downarrow^t \\ C_0 &\stackrel{f_0}{\to}& D_0 }$;

  • respect for identities $\array{ C_0 &\stackrel{f_0}{\to}& D_0 \\ \downarrow^i && \downarrow^i \\ C_1 &\stackrel{f_1}{\to}& D_1 }$;

  • respect for composition $\array{ C_1 \times_{t,s} C_1 &\stackrel{f_1\times_{t,s} f_1}{\to}& D_1 \times_{t,s} D_1 \\ \downarrow^{\circ} && \downarrow^{\circ} \\ C_1 &\stackrel{f_1}{\to}& D_1 }$.

parameterized sets: presheaves

• Prägarben;

• Yoneda Lemma;

• adjungierte Funktoren

---

previous: heuristic introduction to sheaves, cohomology and higher stacks

– home: Garben und Stacks