Category of Sets

Constructions in Set

Almost every category met so far has been a category of sets-with-structure: groups, vector spaces, topological spaces, each a set carrying extra data, with structure-preserving maps between them. Beneath all of them sits the plainest category of all, the one whose objects are sets with no structure whatsoever and whose morphisms are arbitrary functions. We write it \(\mathbf{Set}\). A set, in this view, is a bag of points carrying no order, no algebra, and no notion of nearness. A function is simply an assignment of one point of the target to each point of the source. Composition of functions is associative and every set has an identity function, so the data form a category in the now-familiar sense.

Most of the universal constructions that the abstract theory treats in full generality can first be met in \(\mathbf{Set}\) in concrete form, where they reduce to transparent operations on bags of points. Meeting them there first is the surest way to recognize them later in their abstract dress.

Empty and one-element sets

There is a set \(\varnothing\) with no elements, and a set \(1\) with exactly one element. Each has a defining mapping property. Suppose we are asked to specify a function from a set \(A\) to a set \(B\). The task is to choose, for each element of \(A\), an element of \(B\). The larger \(A\) is, the more choices the task demands, and the smaller \(A\) is, the fewer. When \(A\) is empty the task is vacuous, since there are no elements to send anywhere, and there is exactly one way to perform a task with no steps. Hence for every set \(B\) there is exactly one function \(\varnothing \to B\). Dually, a function \(A \to 1\) must send every element of \(A\) to the sole element of \(1\), so there is exactly one such function for each \(A\).

These uniqueness statements are precisely the conditions met earlier in the abstract. The set \(\varnothing\) is an initial object of \(\mathbf{Set}\), and \(1\) is a terminal object.

The terminal set repays a second look. A function \(1 \to B\) is no more and no less than a choice of one element of \(B\), since to give the function is to say where the single point of \(1\) lands. Functions \(1 \to B\) therefore correspond exactly to elements of \(B\). The notion of element, seemingly more primitive than the notion of function, is thus recovered as a special case of it. A point of \(B\) is a morphism out of the terminal object. This is the first sign of a recurring theme: structure that looks set-theoretically basic can be re-described arrow-theoretically.

Products and coproducts

Any two sets \(A\) and \(B\) have a product, the set of ordered pairs \[ A \times B = \{ (a, b) \mid a \in A,\ b \in B \}. \] More generally, for any family \((A_i)_{i \in I}\) indexed by a set \(I\) there is a product set \(\prod_{i \in I} A_i\) whose elements are the families \((a_i)_{i \in I}\) with \(a_i \in A_i\) for each \(i\), two such families being equal exactly when they agree coordinatewise.

Dually, any two sets have a coproduct, formed by placing all the points of both into one bag while keeping a record of which set each came from: \[ A + B = \{ (a, 0) \mid a \in A \} \cup \{ (b, 1) \mid b \in B \}. \] The tags \(0\) and \(1\) keep the two summands disjoint even when \(A\) and \(B\) overlap, which is why the coproduct is also called the disjoint union and written \(A \amalg B\). If \(A\) and \(B\) are finite with \(m\) and \(n\) elements, then \(A + B\) has \(m + n\) elements regardless of any overlap between the original sets. This feature distinguishes it sharply from the ordinary union \(A \cup B\), which only makes sense once \(A\) and \(B\) sit inside a common set and which may identify elements the coproduct keeps apart.

Both constructions are instances of the adjoint pattern already isolated in the abstract. Recall that the diagonal functor \(\Delta : \mathbf{Set} \to \mathbf{Set} \times \mathbf{Set}\) sends a set \(A\) to the pair \((A, A)\), using the product category as its target. The product and the coproduct are exactly the right and left adjoints of \(\Delta\). For the product, the universal property of \(A \times B\) displayed above is precisely the bijection \[ \begin{align*} (\mathbf{Set} \times \mathbf{Set})\bigl(\Delta X, (A,B)\bigr) &= \mathbf{Set}(X, A) \times \mathbf{Set}(X, B) \\\\ &\cong \mathbf{Set}\bigl(X, A \times B\bigr), \end{align*} \] natural in \(X\) and in the pair \((A, B)\). The first equality is the definition of morphisms in the product category, where a map \(\Delta X \to (A,B)\) is a pair of functions \(X \to A\) and \(X \to B\). The second is the universal property pairing them into a single map \(X \to A \times B\). This exhibits \({\times}\) as right adjoint to \(\Delta\), and the coproduct property is the mirror bijection exhibiting \({+}\) as left adjoint.

The bare set-level operations of pairing and disjoint union are thus not ad hoc. Each is forced, up to unique isomorphism, by an adjunction to the most elementary functor there is.

Function sets and the exponential

For any two sets \(A\) and \(B\) we may form the set \(A^B\) of all functions from \(B\) to \(A\). This is a product in disguise. The set \(A^B\) is the product \(\prod_{b \in B} A\) of the constant family that returns \(A\) at every index, since an element of that product is a choice of one element of \(A\) for each \(b \in B\), that is, a function \(B \to A\).

The notation is chosen to echo arithmetic, and the analogy is exact for finite sets. If \(A\) has \(m\) elements and \(B\) has \(n\), then \(A^B\) has \(m^n\) elements, while \(A \times B\) has \(mn\) and \(A + B\) has \(m + n\). The set-level isomorphisms \[ A^{B + C} \cong A^B \times A^C, \quad (A^B)^C \cong A^{B \times C} \] hold for all sets, finite or not, and are the categorical counterparts of the laws of exponents.

The second of these displays the structure already encountered as currying. A function of two arguments \(C \times B \to A\) is the same thing as a function \(C \to A^B\) of one argument returning a function. In \(\mathbf{Set}\) this is the bijection \[ \mathbf{Set}(C \times B,\, A) \cong \mathbf{Set}(C,\, A^B), \] natural in \(C\) and in \(A\), which says that \(-{} \times B\) is left adjoint to \((-)^B\). The function set \(A^B\) is the concrete realization of the object whose existence the abstract currying adjunction only posited.

Power sets and characteristic functions

Let \(2\) denote the two-element set \(1 + 1\), whose elements we name \(\mathtt{true}\) and \(\mathtt{false}\). Given a set \(A\) and a subset \(S \subseteq A\), there is a function \(\chi_S : A \to 2\), the characteristic function of \(S\), defined by \[ \chi_S(a) = \begin{cases} \mathtt{true} & \text{if } a \in S, \\ \mathtt{false} & \text{if } a \notin S. \end{cases} \] Conversely, a function \(f : A \to 2\) determines the subset \(f^{-1}\{\mathtt{true}\} = \{a \in A \mid f(a) = \mathtt{true}\}\). These two passages are mutually inverse, since \(\chi_S^{-1}\{\mathtt{true}\} = S\) and \(\chi_{f^{-1}\{\mathtt{true}\}} = f\). Subsets of \(A\) therefore correspond exactly to functions \(A \to 2\).

The functions from \(A\) to \(2\) form, by the previous construction, the set \(2^A\). Read through the correspondence just established, \(2^A\) is the set of all subsets of \(A\). We call it the power set of \(A\) and write it \(\mathcal{P}(A)\). The set \(2\) thus plays a double role, as a two-element set and as the receptacle that classifies subsets, and the identification \(\mathcal{P}(A) \cong 2^A\) is the bridge between them. This small fact is the seed of the general phenomenon by which a single object can classify the subobjects of every other, and it will return when the size of \(\mathcal{P}(A)\) is measured against the size of \(A\) later on this page.

Equalizers and Quotients

The constructions of the previous section build new sets out of old by pairing, tagging, or forming functions. Two further constructions go the other way. They carve out a part of a set, or collapse a set down, according to a condition. Both are governed by mapping properties of exactly the kind already seen, and each will reappear in the abstract theory, the first among the limits and the second among the colimits. It is worth meeting them concretely while the meaning is still plain.

Equalizers

It would be convenient to be able to specify a subset of a set \(A\) by writing down a property its elements are to satisfy, \(S = \{ a \in A \mid \text{some property of } a \text{ holds} \}\). Giving a general account of what a property is turns out to be delicate, but there is one kind of property that is entirely transparent: the equality of two functions. Given a parallel pair of functions \(f, g : A \rightrightarrows B\) with the same source and target, the elements of \(A\) on which they agree form a subset \[ E = \{ a \in A \mid f(a) = g(a) \}. \]

This subset is the equalizer of \(f\) and \(g\): the part of \(A\) on which the two functions are equalized. It comes with an inclusion \(e : E \hookrightarrow A\) satisfying \(f \circ e = g \circ e\), and it is the universal such object.

The equalizer turns a defining equation into a subobject. The kernel of a linear map, for instance, is the equalizer of that map and the zero map. The uniqueness clause is what makes the construction canonical rather than merely possible.

Quotients

Where the equalizer selects a part, the quotient collapses a whole. Quotient constructions are pervasive, from quotient groups and rings in algebra to identification spaces in topology, but the most basic context is that of sets. Let \(A\) be a set and \(\sim\) an equivalence relation on \(A\). There is a set \(A/{\sim}\), the quotient of \(A\) by \(\sim\), whose elements are the equivalence classes. The quotient group of group theory is a special case. Given a group \(G\) and a normal subgroup \(N\), the relation \(g \sim h \iff gh^{-1} \in N\) is an equivalence relation, and \(G/{\sim}\) is exactly the quotient group \(G/N\).

The quotient comes with a canonical map \[ p : A \longrightarrow A/{\sim}, \] sending each element to its equivalence class. It is surjective, and it has the defining feature \(p(a) = p(a') \iff a \sim a'\). In words, the map identifies precisely the elements that \(\sim\) declares equivalent, and no others. This map is universal among all functions out of \(A\) that respect the relation.

Thus, for any set \(B\), the functions \(A/{\sim} \to B\) correspond one-to-one with the functions \(A \to B\) that are constant on equivalence classes. This single fact is the engine behind the isomorphism theorems of algebra. A homomorphism that kills a normal subgroup factors uniquely through the quotient, because killing the subgroup is precisely the relation-respecting condition. When the subgroup is the whole kernel, the induced map is an isomorphism onto the image, which is the first isomorphism theorem.

Equalizer and quotient are dual in spirit. The equalizer is built from an inclusion into \(A\) and tests functions into \(A\), while the quotient is built from a surjection out of \(A\) and tests functions out of \(A\). Indeed the quotient is a coequalizer. Viewing the equivalence relation as a pair of projections \(R \rightrightarrows A\) from the set \(R \subseteq A \times A\) of related pairs, we see that the canonical map \(p\) coequalizes them universally, the exact dual of the way the inclusion \(e\) equalizes \(f\) and \(g\).

The equalizer is a limit, assembled from a diagram by a universal cone into it, and the quotient is a colimit, assembled by a universal cone out of it. The general definitions that subsume both belong to the abstract theory of limits and colimits, which takes these very examples in \(\mathbf{Set}\) as its point of departure. That theory also recovers products, coproducts, and the empty and one-element sets as further special cases.

Small, Large, and Locally Small

The definition of a category speaks of a collection of objects and, for each pair of objects, a collection of morphisms. So far the word collection has been left deliberately vague. The reason is that in many of the categories already met, these collections are too big to be sets. The collection of all groups, of all vector spaces, or of all topological spaces cannot itself be a set, on pain of contradiction, and neither can the collection of all sets. To say this precisely, and to see why it matters, requires a controlled vocabulary for size.

We use the word class informally for any collection of mathematical objects. Every set is a class, but not every class is a set. A class is called small if it is a set, and large otherwise. The distinction is not a technicality invented for its own sake. It is forced on us by a theorem.

There is no largest set

The fact that drives everything in this section is that sets can always be enlarged. The power-set construction met earlier does exactly that, and it does so strictly.

This inequality already shows there can be no largest set. From any set \(X\), the power set \(\mathcal{P}(X)\) is strictly larger, and the power set of that is larger still. More is true, and it is the form we need. Given any family of sets at all, there is a set isomorphic to none of its members.

The consequence is the slogan to remember: any individual set is small, but the class of all sets is large. If the sets formed a set, that set would index a family containing every set, and the proposition just proved would produce a set isomorphic to no member of that family, a contradiction. The collection of all sets, even the collection of isomorphism classes of sets, is genuinely too big to be a set.

Locally small categories and hom-sets

With small and large in hand we can grade categories by size. Smallness asks that all the morphisms together form a set. If they do, then so do the objects, since each object is named by its identity morphism. The most useful size condition is weaker and almost always met. It asks only that the morphisms between any fixed pair of objects form a set.

Small implies locally small, but not conversely. The category \(\mathbf{Set}\) is locally small, because for any two sets \(A\) and \(B\) the functions from \(A\) to \(B\) form a set, namely the function set \(B^A\) constructed earlier. Yet \(\mathbf{Set}\) is large, since its objects already form a large class. The same pattern holds for \(\mathbf{Grp}\), \(\mathbf{Vect}_k\), \(\mathbf{Ring}\), and \(\mathbf{Top}\). A morphism between two structured sets is in particular a function between the underlying sets, so the morphisms between two given objects form a set, and each of these categories is locally small while being large overall.

Local smallness is the hypothesis under which the hom-set notation \(\mathscr{A}(A, B)\), used freely up to now, is literally a set. It is exactly what is needed to regard \(\mathscr{A}(A, -)\) as a functor into \(\mathbf{Set}\), the construction on which the representable functors to come will rest.

Essentially small categories

There is a coarser notion, essential smallness, that ignores the difference between a category and any equivalent one. The category of finite sets is the standard example. It is large as it stands, since there are proper-class-many finite sets, but it is equivalent to the small category with one object for each \(n \in \{0, 1, 2, \ldots\}\), and so is essentially small. The question for \(\mathbf{Set}\) is whether the same rescue is possible, and it is not.

Were \(\mathbf{Set}\) essentially small, its isomorphism classes of objects would form a set. But two sets are isomorphic in \(\mathbf{Set}\) exactly when they are in bijection, so the isomorphism classes are the cardinalities, and the proposition above shows these form a large class. Hence \(\mathbf{Set}\) is not essentially small, that is, no small category is equivalent to it. The obstruction is precisely the strict growth of the power set. The same fact, transported along an encoding of strings, separates the countably many Turing machines from the uncountably many languages, so a single diagonal argument underlies both results.

The category of small categories

Smallness is what makes it safe to gather categories into a category. The collection of all categories and functors is itself a sprawling thing, and restricting to the small ones yields a well-behaved object.

The restriction to small categories is what keeps \(\mathbf{Cat}\) honest. A functor \(\mathscr{A} \to \mathscr{B}\) between small categories is itself a piece of set-sized data, so the morphisms of \(\mathbf{Cat}\) between any two objects form a set, and \(\mathbf{Cat}\) is locally small.

The category \(\mathbf{Cat}\) is also the home in which the monoids of the adjunction page acquire their final description. A monoid is by definition a set equipped with an associative multiplication and a unit. The one-object category it determines has a single object, the monoid elements as endomorphisms, and multiplication as composition, so it has a set of morphisms and is therefore small. The one-object categories form a full subcategory of \(\mathbf{Cat}\), and assigning to each monoid its one-object category is an equivalence between the category of monoids and that subcategory. A monoid and its one-object category are, categorically, the same thing seen twice. Through this identification a group \(G\), being in particular a monoid, becomes a one-object category, and an action of \(G\) on a set \(X\) is exactly a functor from that category to \(\mathbf{Set}\) sending its single object to \(X\). The functor axioms are the action axioms, since the identity element must act as the identity function and a product must act as the composite of the actions of its factors. A linear action of \(G\) on a vector space is, in the same way, a functor to \(\mathbf{Vect}_k\).

Foundations as an Interface

Step back from the individual constructions and look at what was actually used. Nowhere on this page was a set defined. We never said what a set is, nor what a function is. Instead we listed things one can do with them: form products and coproducts, take function sets and power sets, cut out equalizers, collapse quotients, recognize an empty set and a one-element set by their mapping properties. Every construction was characterized by how it behaves under functions, that is, by a universal property, and the explicit descriptions of elements served only to show that an object with that behavior exists.

Working this way is a deliberate stance, and it is worth making explicit because it inverts the usual order of explanation. One might expect to define a set, then derive its properties. Definitions in mathematics normally depend on earlier definitions. A vector space is an abelian group with scalar multiplication, an abelian group is a group with a commutativity law, and a group is a set with operations. The chain has to stop somewhere, for otherwise the words would rest on nothing. Set and function are where it stops. They are taken as primitive, not defined in terms of anything prior.

But if they are undefined, how can we reason about them rigorously? The resolution is to specify them not by what they are but by what they do. We agree on a list of properties and treat them as the rules of the game. The list says that there is an initial object, there is a terminal object, products exist, function sets exist, power sets are strictly larger, and so on. Disputes about the nature of sets are then settled not by appeal to intuition, which differs from person to person, but by consulting the list. Whether \(\varnothing\) is initial is decided by the agreed rules, and the secret inner constitution of the empty set plays no part.

The analogy is not loose. The discipline of specifying a structure by its mapping properties is the same discipline that lets a type system reason about programs it cannot see inside. A function type \(A^B\) is the type of functions from \(B\) to \(A\), and the currying isomorphism \((A^B)^C \cong A^{B \times C}\), read on the other side of the correspondence between proofs and programs, is the rule that a function of two arguments may be supplied one at a time. The classifier \(2\) that distinguishes subsets is the type of booleans. The constructions of this page are, simultaneously, the type formers of a programming language: product types and function types, and, given more structure, sum types and a type of truth values. For products and function types this coincidence is not an accident but a theorem: the structural identity between a cartesian closed category and a typed calculus.

The size theory plays its part in this picture too. Local smallness is the guarantee that the morphisms between two objects can themselves be packaged as an object of \(\mathbf{Set}\), so that the interface can talk about its own collections of maps without overflowing. It is the condition that will let each object \(A\) of a locally small category be probed by the functor \(\mathscr{A}(A, -)\) that records all the maps out of it, turning objects into the data of their relationships. The largeness of \(\mathbf{Set}\), which no equivalence can tame into a small category, is the source of its expressive power rather than a defect. An interface rich enough to classify all sets cannot be one of the things it classifies.