---
title: "Size: Small, Large, Locally Small"
module: Foundations
moduleNumber: 1
lessonNumber: 6
order: 106
summary: >
  The objects of Set do not form a set, and pretending otherwise reproduces the
  classical paradoxes. Classes make the small/large distinction precise, with
  locally small and essentially small as the intermediate notions. Cantor's
  theorem shows Set and its algebraic relatives are large, and the function-based
  axiomatization of sets is the one category theory prefers to ZFC.
topics: [Foundations]
sources:
  - book: Leinster
    ref: "Ch. 3 — Interlude on sets; §3.1 Constructions with sets; §3.2 Small and large categories; §3.3 Historical remarks"
  - book: Simmons
    ref: "Ch. 1 §1.1 remarks on foundations"
draft: false
---

Every category met so far has been described with the deliberately vague word
"collection": a collection of objects, a collection of arrows. The vagueness has
a reason. For most of the categories that matter ($\mathbf{Set}$,
$\mathbf{Grp}$, $\mathbf{Top}$), the objects are too numerous to form a set, and
a theory that ignored the difference would inherit the paradoxes that set theory
spent the early twentieth century escaping. The distinction matters concretely at
the
[adjoint functor theorems](/category-theory/adjoints-limits/adjoint-functor-theorem),
where a size hypothesis is what makes a construction go through.

## Set-theoretic assumptions

Leinster's approach to foundations is to list the properties the category of
sets is expected to have, rather than to build sets from a membership relation.
The inventory, each item a fact about arrows:[^lein-constructions]

- **Initial and terminal objects.** $\emptyset$ admits exactly one function to
  any set; a one-element set $1$ admits exactly one function from any set.
  Elements are recovered as arrows: a function $1 \to B$ is precisely an element
  of $B$.
- **Products and sums.** Any family $(A_i)_{i \in I}$ has a product
  $\prod_i A_i$ (families of elements) and a sum $\sum_i A_i$ (disjoint union).
- **Function sets.** For sets $A, B$ there is a set $A^B$ of functions
  $B \to A$; the arithmetic notation is earned, since
  $A^{B+C} \cong A^B \times A^C$ and $(A^B)^C \cong A^{B \times C}$.
- **Subsets and the two-element set.** Subsets of $A$ correspond one-to-one
  with functions $A \to 2$; the powerset is $\mathcal{P}(A) = 2^A$.
- **Equalizers and quotients.** $\{a \in A \mid f(a) = g(a)\}$ exists for any
  parallel pair, and any equivalence relation has a quotient $A/\sim$ whose
  projection has a universal factorization property.
- **Natural numbers.** $\mathbb{N}$ with $0$ and successor supports unique
  recursive definitions.
- **Choice.** Every surjection has a section.

None of these is a theorem; with no prior definition of "set" there is nothing
to prove them from. They are the interface that the rest of mathematics
programs against, and each clause is a statement about the _category_
$\mathbf{Set}$ rather than about membership.

## Cardinality and Cantor's theorem

Comparison of sizes is defined through arrows as well. Write $|A| \le |B|$ when
an injection $A \to B$ exists; the expression $|A|$ has no standalone meaning.
Identities and composites of injections make $\le$ reflexive and transitive, and
the substance is the antisymmetry-up-to-isomorphism:

> **Theorem (Cantor–Bernstein).** If $|A| \le |B|$ and $|B| \le |A|$, then
> $A \cong B$.

We write $|A| = |B|$ ("same cardinality") for $A \cong B$, and $|A| < |B|$ for
$|A| \le |B|$ with $|A| \neq |B|$. The central theorem:

> **Theorem (Cantor).** For every set $A$, we have $|A| < |\mathcal{P}(A)|$.

> **Proof.** Given any
> function $f : A \to \mathcal{P}(A)$, the subset
> $D = \{a \in A \mid a \notin f(a)\}$ cannot be $f(a)$ for any $a$ (the element
> $a$ itself witnesses the disagreement), so no $f$ is surjective, while
> $a \mapsto \{a\}$ is an injection.[^lein-cantor]

Immediately, there is no biggest set: powerset always climbs strictly. And with
one more step, no set-indexed family of sets is exhaustive:

> **Proposition (Escape from any family).** For any set $I$ and family
> $(A_i)_{i \in I}$ of sets, there is a set not isomorphic to any $A_i$ — namely
> $A = \mathcal{P}\bigl( \sum_{i \in I} A_i \bigr)$, since each $A_j$ injects
> into the sum and Cantor lifts the inequality strictly.[^lein-escape]

$$
% caption: Cantor's ladder: each powerset is strictly bigger, so no set can
% index all sets; any proposed family is escaped by the powerset of its sum.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\node (A) at (0,0) {$A$};
\node (PA) at (2.6,0.8) {$\mathcal{P}(A)$};
\node (PPA) at (5.2,1.6) {$\mathcal{P}(\mathcal{P}(A))$};
\node (dots) at (7.6,2.3) {. . .};
\draw[->, acc, thick] (A) -- (PA) node[midway, below right] {$<$};
\draw[->, acc, thick] (PA) -- (PPA) node[midway, below right] {$<$};
\draw[->, acc, thick] (PPA) -- (dots);
\end{tikzpicture}
$$

$$
% caption: The diagonal argument as a table: row i records whether each a_j lies
% in f(a_i); flipping the boxed diagonal builds a subset D that differs from every
% row, so no f lists all subsets.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\node at (1.5,2.4) {$a_1$};
\node at (2.7,2.4) {$a_2$};
\node at (3.9,2.4) {$a_3$};
\node[anchor=east] at (0.9,1.6) {$f(a_1)$};
\node[anchor=east] at (0.9,0.8) {$f(a_2)$};
\node[anchor=east] at (0.9,0.0) {$f(a_3)$};
\node at (1.5,1.6) {$1$};
\node at (2.7,1.6) {$0$};
\node at (3.9,1.6) {$1$};
\node at (1.5,0.8) {$1$};
\node at (2.7,0.8) {$1$};
\node at (3.9,0.8) {$0$};
\node at (1.5,0.0) {$0$};
\node at (2.7,0.0) {$0$};
\node at (3.9,0.0) {$0$};
\draw[acc, thick] (1.2,1.3) rectangle (1.8,1.9);
\draw[acc, thick] (2.4,0.5) rectangle (3.0,1.1);
\draw[acc, thick] (3.6,-0.3) rectangle (4.2,0.3);
\node[anchor=east, acc] at (0.9,-0.9) {$D$};
\node[acc] at (1.5,-0.9) {$0$};
\node[acc] at (2.7,-0.9) {$0$};
\node[acc] at (3.9,-0.9) {$1$};
\end{tikzpicture}
$$

> **Worked example (Cantor's diagonal on a two-element set).** Let
> $A = \{1, 2\}$, so $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$ has
> four elements against $A$'s two. Any $f : A \to \mathcal{P}(A)$ names at most two
> subsets, so it cannot be surjective, and the diagonal subset exhibits one it
> misses. For $f(1) = \{1\}$, $f(2) = \emptyset$: since $1 \in f(1)$, $1 \notin D$;
> since $2 \notin f(2)$, $2 \in D$; hence $D = \{2\}$, which is neither
> $f(1) = \{1\}$ nor $f(2) = \emptyset$. The injection $a \mapsto \{a\}$ gives
> $|A| \le |\mathcal{P}(A)|$, and the missed $D$ makes it strict: $2 < 4$.

> **Worked example (Escaping a two-set family).** Take $I = \{1, 2\}$ with
> $A_1 = \{a\}$ and $A_2 = \{b, c\}$. Their sum is the three-element set
> $A_1 + A_2 = \{a, b, c\}$, so $\mathcal{P}(A_1 + A_2)$ has eight elements. Each
> $A_j$ injects into the sum, giving $|A_j| \le 3 < 8 = |\mathcal{P}(A_1 + A_2)|$,
> and by Cantor the powerset of the sum is isomorphic to neither $A_1$ nor $A_2$.
> The same construction over any set-indexed family produces a set outside it, so
> $\mathbf{Set}$ has more isomorphism classes than any set can index and is not
> essentially small.

## Small, large, locally small

The word for a collection that may be too big to be a set is **class**; the
usage here is informal but disciplined. All sets are classes; a class is
**small** if it is a set and **large** otherwise. The proposition above says
precisely that the class of isomorphism classes of sets is large. The crucial
asymmetry:[^lein-small]

> **Definition (Small, large, locally small).** A category $\mathcal{A}$ is
> **small** if the class of all its arrows is small (whence its objects, which
> correspond to identity arrows, form a set too), and **large** otherwise. It is
> **locally small** if each hom-class $\mathcal{A}(A, B)$ is a set, in which
> case the name "hom-set" is honest. A category is small iff it is locally
> small with a small class of objects.

$$
% caption: The three sizes as nested regimes: every small category is locally
% small, and a locally small category is small exactly when its objects form a
% set. Set sits in the middle ring.
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black, thick] (0,0) ellipse (5.0 and 2.6);
\node[black] at (0,2.25) {all categories};
\draw[acc, thick] (-0.4,-0.15) ellipse (3.7 and 1.85);
\node[acc] at (-0.4,1.35) {locally small};
\draw[acc, thick] (-1.2,-0.35) ellipse (2.1 and 1.1);
\node[acc] at (-1.2,0.35) {small};
\node[align=center] at (-1.2,-0.55) {f\/inite categories,\\monoids, posets};
\node[align=center, black] at (2.2,-0.75) {$\mathbf{Set}$, $\mathbf{Grp}$,\\$\mathbf{Top}$, $\mathbf{Vect}_k$};
\end{tikzpicture}
$$

The classification of the standard examples:

| Category | Small? | Locally small? | Why |
| --- | --- | --- | --- |
| a monoid, a poset, any finite category | yes | yes | arrows form a set by construction |
| $\mathbf{Set}$ | no | yes | functions $A \to B$ form the set $B^A$; objects form a proper class |
| $\mathbf{Grp}$, $\mathbf{Ring}$, $\mathbf{Vect}_k$, $\mathbf{Top}$ | no | yes | homomorphisms are a subclass of the function set |
| $\mathbf{Cat}$ (small categories) | no | yes | small categories form a proper class |
| $\mathbf{CAT}$ (all categories) | no | no | functors between large categories can form a proper class |

Local smallness is why the
[hom-functors](/category-theory/foundations/functors) can honestly
take values in $\mathbf{Set}$: for a locally small $\mathcal{C}$, each
$\mathcal{C}(A, B)$ is an object of $\mathbf{Set}$, and the
[Yoneda machinery](/category-theory/representables-yoneda/yoneda-lemma) built on
hom-functors quietly assumes it. Many authors fold local smallness into the
definition of category for exactly this reason.

### Essential smallness

Smallness is not invariant under equivalence: a category equivalent to a small
one may have a proper class of objects, all redundantly isomorphic. The robust
notion quotients that redundancy:

> **Definition (Essentially small).** A category is **essentially small** if it
> is equivalent to some small category.

The category of _finite_ sets has a proper class of objects, but every finite
set is isomorphic to some $\{1, \dots, n\}$, so it is equivalent to a small
category with objects indexed by $\mathbb{N}$. In an essentially small category the class of isomorphism
classes of objects is small (equivalences induce bijections on isomorphism
classes), and this gives the clean impossibility results:

> **Proposition.** $\mathbf{Set}$ is not essentially small.

> **Proof.** By the escape proposition, the isomorphism classes of sets form a
> large class.[^lein-notsmall]

The same strategy — show the category has at least as many non-isomorphic
objects as there are sets — handles the algebraic cases. For
$\mathbf{Vect}_k$: given any set-indexed family $(V_i)$ of vector spaces, let
$S = \mathcal{P}\bigl(\sum_i U(V_i)\bigr)$ where $U$ is the forgetful functor;
the free space $F(S)$ contains $S$ as a basis, so $|U(V_i)| < |S| \le |U F(S)|$
for every $i$, and $F(S) \not\cong V_i$. Neither $\mathbf{Grp}$, $\mathbf{Ab}$,
$\mathbf{Ring}$, nor $\mathbf{Top}$ is essentially small, by the same
free-object argument.

## Where the distinction matters

Three concrete places where ignoring the distinction produces error or
nonsense.

- **Self-membership.** If the objects of $\mathbf{Set}$ formed a set
  $W$, then $W$ would be a candidate element of itself, and
  Cantor's theorem applied to $W$ against the family _of all sets_ yields
  a set bigger than every set — a contradiction of exactly the Russell type.
  The objects of $\mathbf{Set}$ form a proper class, and Cantor's theorem speaks
  only about sets.
- **Hom-functors need targets.** $\mathcal{C}(A, -)$ is a functor _into
  $\mathbf{Set}$_ only when $\mathcal{C}$ is locally small. For a category with
  large hom-classes the representable machinery must be rebuilt against a
  bigger universe.
- **Limits over large diagrams.** A category with products indexed by a proper
  class collapses: a classical argument shows any such category is a preorder.
  The completeness notions of
  [the limits module](/category-theory/limits-colimits/limits) are therefore
  always _small_ completeness — all limits over small diagrams — and the
  solution-set condition in the
  [adjoint functor theorem](/category-theory/adjoints-limits/adjoint-functor-theorem)
  exists precisely to tame a large construction by a small amount of data.

$$
% caption: The paradox of self-containment: a set of all sets would have to
% contain its own powerset, which Cantor forbids; the containing ring must be a
% class, not a set.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black, thick, dashed] (0,0) ellipse (4.6 and 2.4);
\node[black] at (0,2.05) {all sets (a proper class)};
\draw[acc, thick] (-2.0,-0.2) circle (1.0);
\node[acc] at (-2.0,-0.2) {$W$?};
\draw[acc, thick] (1.6,-0.2) ellipse (1.7 and 1.2);
\node[acc, align=center] at (1.6,-0.2) {$\mathcal{P}(W)$\\strictly bigger};
\draw[->, black, thick] (-1.0,-0.2) -- (-0.2,-0.2);
\end{tikzpicture}
$$

Some treatments avoid classes by positing a hierarchy of _universes_: each
universe is a set large enough to contain all "ordinary" mathematics, with every
universe an element of a bigger one. "Small" then means
"in the chosen universe," and $\mathbf{Set}$ becomes a legitimate object one
level up. The bookkeeping is different; the discipline it enforces is the
same.[^universes]

## Historical remarks

Leinster closes his interlude with intellectual history that explains why
category theory treats "what are the elements really?" as a malformed
question.[^lein-history]

Cantor created set theory in the late nineteenth century and proved, among much
else, that infinity comes in different sizes. The axiomatizers who followed
(Zermelo, Fraenkel, and others, arriving at **ZFC**) took _sets and membership_
as the primitive notions. That choice has consequences that sit oddly with
mathematical practice:

- **Everything is a set.** In ZFC, $\sqrt{2}$ is a set, $\log$ is a set, and
  the number $4$ is officially
  $\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\},
  \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}\}$: an encoding,
  like a file format, that nobody intends literally.
- **Types are erased.** Because everything is a set, the question "is
  $\mathbb{Q} \in \sqrt{2}$?" is grammatical, and even has an answer, one that
  depends on the encoding conventions and means nothing. Working mathematics
  has an instinctive type discipline (a number is not a function is not a
  group), and membership-based foundations discard it.
- **Membership is global.** Any two sets can be intersected, so "does the
  cyclic group of order 10 meet $\mathbb{Z}$?" is a legitimate ZFC question.
  Its answer is again encoding-dependent noise.

The categorical alternative takes _sets and functions_ (with composition) as
primitive, exactly the inventory of assumptions listed above. One popular
categorical axiomatization can be summarized in ten clauses (composition is
associative and unital; there are terminal and empty sets; functions are
determined by their effect on elements; products, function sets, inverse
images, powersets-via-$2$, natural numbers, and sections of surjections exist).
Nothing in the list mentions a general notion of category; the axioms speak
directly about sets and functions, so there is no circularity in founding
categories on sets so axiomatized. The approach preserves types (asking
whether an element of a group equals an open set of a space is ungrammatical,
as it should be), and every meaningful theorem of Cantor's theory survives.

Category theory gets inside an object by probing it with arrows, never by
inspecting members. An element of $A$ is an arrow $1 \to A$; a subset of $A$ is an
arrow $A \to 2$;
[a variable element is any arrow into $A$](/category-theory/foundations/special-morphisms).
The membership relation is not denied; it is reconstructed as composition, at
which point it stops being primitive and becomes one construction among many. The
[next module](/category-theory/universal-properties/universal-properties) specifies
every basic construction of mathematics — products, quotients, function spaces,
free objects — purely by the pattern of arrows around it.

[^lein-constructions]: **Leinster**, _Basic Category Theory_, §3.1 — the properties of sets and functions taken as assumptions: initial/terminal objects, products, sums, function sets, subsets via $2$, equalizers, quotients with their universal property, natural numbers, and choice; and the discussion of their status as an interface rather than theorems.
[^lein-cantor]: **Leinster**, §3.2, Theorems 3.2.1–3.2.2 and Corollary 3.2.3 with Exercises 3.2.12–3.2.13 — the injection preorder, Cantor–Bernstein, Cantor's theorem via the diagonal subset, and the nonexistence of a biggest set.
[^lein-escape]: **Leinster**, §3.2, Proposition 3.2.4 — for any set-indexed family of sets, the powerset of the sum is isomorphic to none of them.
[^lein-small]: **Leinster**, §3.2 — classes, small and large, the definitions of small, locally small, and essentially small categories, with Examples 3.2.5–3.2.7 and Definition 3.2.10 ($\mathbf{Cat}$ versus $\mathbf{CAT}$).
[^lein-notsmall]: **Leinster**, §3.2, Propositions 3.2.8 and Example 3.2.9, Exercise 3.2.14 — $\mathbf{Set}$ is not essentially small, and the free-functor argument extending the result to $\mathbf{Vect}_k$, $\mathbf{Grp}$, $\mathbf{Ab}$, $\mathbf{Ring}$, and $\mathbf{Top}$.
[^universes]: Grothendieck universes: see [https://en.wikipedia.org/wiki/Grothendieck_universe](https://en.wikipedia.org/wiki/Grothendieck_universe) for the axiomatization and its use as an alternative to proper classes.
[^lein-history]: **Leinster**, §3.3 — Cantor's theory and its reception, types, the ZFC axiomatization and its encoding artifacts, the function-based (categorical) axiomatization of sets in ten informal clauses, and the non-circularity footnote for readers raised on ZFC.