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 SetsETCS

  • 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:

  • 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 sSs \in S of a set SS is regarded as the function *sS* \stackrel{\bullet \mapsto s}{\to} S that sends the single element of the singleton set *={}* = \{\bullet\} to ss.

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

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

Now the definition.

Set consists of

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

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

    • for every object SS a morphism denoted Id S:SSId_S : S \to S, called the identity function on SS;
  • a composition operation (RfS,SgT)(RgfT)(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 SId_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:TSs : T \to S we also call an element sSs \in S of SS with domain TT (or “stage of definition” TT).

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

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 S, T, there is a set CC and functions p 1:CS p_1: C \to S, p 2:CT p_2: C \to T, such that given two elements xS,yT x \in S, y \in T over the same domain, there exists a unique element x,yC \langle x, y \rangle \in C over that domain for which

p 1x,y=xp 2x,y=y 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:US x : U \to S and y:UTy : U \to T , there exists a unique morphism x,y:UC \langle x, y \rangle : U \to C such that the following diagram commutes
U x x,y y S p 1 C p 2 T \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 C is usually denoted S×T S \times T. To make a bridge with naive set-theory notation, we may suggestively write

S×T:= i{x,y:xS,yT} 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* x \in * over any domain;

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

Notation

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

f×g:S×TS×T f \times g : S\times T \to S' \times T'

induced by the universal property of S×TS' \times T' by from the existence of the two functions fp 1:S×TS f p_1 : S \times T \to S' and
gp 2:S×TT g p_2 : S \times T \to T'

Axiom of equalizers.

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

  1. fi=gi f i = g i,
  2. Given xS x \in S over some domain such that fx=gx f x = g x, there exists a unique xe x' \in e over the same domain such that ix=x i x' = x.

Equivalently, in morphism language:

  1. (EiSfT)=(EiSgT)(E \stackrel{i}{\to} S \stackrel{f}{\to} T) = (E \stackrel{i}{\to} S \stackrel{g}{\to} T),
  2. Given any other x:US x : U \to S such that (UxSfT)=(UxSgT)(U \stackrel{x}{\to} S \stackrel{f}{\to} T) = (U \stackrel{x}{\to} S \stackrel{g}{\to} T), there exists a unique x:UE x' : U \to E over the same domain such that the following diagram commutes
U x x E i S fg T \array{ && U \\ &{}^{x'}\swarrow& \downarrow^{x} \\ E &\stackrel{i}{\to}& S &\stackrel{\stackrel{g}{\to}}{\stackrel{f}{\to}}& T }

An equalizer i:ES i: E \to S is again defined up to isomorphism by its collection of generalized elements, denoted E:= i{xS:f(x)=g(x)}S 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:SC,g:TC f: S \to C, g: T \to C there exists a set S× CTS \times_C T and functions p 1:S× CTSp_1 : S \times_C T \to S and p 2:S× CTTp_2 : S \times_C T \to T such that the diagram

S× CT p 2 T p 2 g S f C \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

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

there is a unique function RS× STR \to S \times_S T such that

U x x,y y S p 1 S× CT p 2 T \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× CTS \times_C T is equivalently the equalizer of fp 1f p_1 and gp 2g p_2:

S× CTS×Tfp 1gp 2C 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× CT{x,yS×T:fx=gy} S \times_C T \simeq \{\langle x, y \rangle \in S \times T: f x = g y\}

Stines CTS \tines_C T is the fiber product of ff with gg: over cCc \in C it is the product of the fibers f 1c={x|fx=c}f^{-1}c = \{x | f x = c\} and g 1c={y|gy=c}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:ST i: S \to T is injective if for every x,yS x, y \in S over the same domain, ix=iy i x = i y implies x=y x = y.

Equivalently, in morphism notation: ii is a monomorphism if for every x:USx : U \to S and y:USy : U \to S, ix=iyi \circ x = i \circ y implies x=yx = y.

Dually, a f:STf : S \to T is a a surjective function or epimorphism if for every g:TUg : T \to U and h:TUh : T \to U, gf=ghg f = g h implies g=hg = h.

Given a monomorphism i:ST i: S \to T we may think of it as defining a “subset” S S of T T, whose (generalized) elements correspond to those elements zT z \in T which factor (evidently uniquely) through i i. It is in that sense that we say zT z \in T also “belongs to” a subset S 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 S to T T is an injective function or subset RS×T R \hookrightarrow S \times T.

Now we can state the next axiom

Axiom of power sets.

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

{x,yT×S:y Sχ R(x)}. \{\langle x, y \rangle \in T \times S: y \in_S \chi_R(x)\} \,.

i.e the universal commutative diagram

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

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

Axiom of strong extensionality.

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

for functions

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

we have f=g f = g if and only if fx=gx f x = g x for all ordinary elements x:*S 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:STi : S \to T is a monomorphism if (RfSiT)=(RgSiT)(R \stackrel{f}{\to} S \stackrel{i}{\to} T)= (R \stackrel{g}{\to} S \stackrel{i}{\to} T) implies f=gf = g. So in particular, for R=*R = * and f=x:*Sf = x : * \to S, g=y:*Sg = y : * \to S ordinary elements, this says that ix=iyi x = i y implis x=yx = y. The converse statement follows similarly.

Axiom of natural numbers object.

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

h(0)=x;hs=fh h(0) = x; \qquad h s = f h

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

* 0 s x h h S f S \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:ST f: S \to T admits a section, i.e., a function σ:TS \sigma : T \to S such that fσ=Id S 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:EUel:E\to U satisfying the axioms to follow. We think of el:EUel:E\to U as a UU-indexed family of objects (sets), and we define a morphism a:AIa:A\to I (regarded as an II-indexed family of objects) to be UU-small if there exists a morphism f:IUf:I\to U and a pullback? square

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

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

The axioms which must be satisfied are:

  1. Every monomorphism? is UU-small.

  2. The composite of UU-small morphisms is UU-small.

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

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

Let us unwrap what this means:

For u:*Uu : * \to U an ordinary element of UU, write E uE_u for the fiber of EE over uu, i.e. for the pullback *× UE* \times_U E. We are to think of EE as the set of all sets E uE_u.

By definition, a single set SS, regarded as the unique function S*S \to *, is UU-small if it is isomorphic to one of these E uE_u.

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

UU-small indexed families of UU-small sets are UU-small.

Since 2\emptyset \to \mathbf{2} is a monomorphism, and 2\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 SS a UU-small set, also every subset of SS is UU-small.

internal categories and functors

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

  • an object of objects C 0AC_0 \in A;

  • an object of morphisms C 1AC_1 \in A;

together with

  • source? and target? morphisms s,t:C 1C 0s,t: C_1 \to C_0;

  • an identity assigning morphism? e:C 0C 1e: C_0 \to C_1;

  • a composition? morphism c:C 1× C 0C 1C 1c: 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:
C 0 e C 1 1 s C 0C 0 e C 1 1 t C 0 \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:
C 1× C 0C 1 c C 1 p 1 s C 1 s C 0C 1× C 0C 1 c C 1 p 2 t C 1 t C 0 \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:
C 1× C 0C 1× C 0C 1 c× C 01 C 1× C 0C 1 1× C 0c c C 1× C 0C 1 c C 1 \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:
C 1× C 0C 1 e× C 01 C 1× C 0C 1 1× C 0e C 1× C 0C 1 p 2 c p 1 C 1 \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× C 0C 1C_1 \times_{C_0} C_1 is defined via the square

C 1× C 0C 1 p 2 C 1 p 1 s C 1 t C 0 \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 AA, a functor F:CDF : C \to D is

  • a morphism of objects F 0:C 0D 0F_0 : C_0 \to D_0 in AA;

  • a morphisms of morphisms F 1:C 1D 1F_1 : C_1 \to D_1 in AA;

  • such that the following diagrams commute

    • respect for the source map: C 1 f 1 D 1 s s C 0 f 0 D 0 \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: C 1 f 1 D 1 t t C 0 f 0 D 0 \array{ C_1 &\stackrel{f_1}{\to}& D_1 \\ \downarrow^t && \downarrow^t \\ C_0 &\stackrel{f_0}{\to}& D_0 } ;

    • respect for identities C 0 f 0 D 0 i i C 1 f 1 D 1 \array{ C_0 &\stackrel{f_0}{\to}& D_0 \\ \downarrow^i && \downarrow^i \\ C_1 &\stackrel{f_1}{\to}& D_1 } ;

    • respect for composition C 1× t,sC 1 f 1× t,sf 1 D 1× t,sD 1 C 1 f 1 D 1 \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

Last revised on April 14, 2009 at 02:25:07. See the history of this page for a list of all contributions to it.