nLab
Understanding limits in Set

Idea

On this page, we work work through several of the key examples of limits in the category Set. This is part of a bigger project: Understanding Constructions in Categories.

Recall that a limit, or universal cone, over a diagram $F:J\to \mathrm{Set}$ is a cone $T$ over $J$ such that, given any cone $T\prime$, there is a unique cone function from $T\prime$ to $T$.

Terminal Object

A terminal object is a universal cone over the empty diagram. In this section, we demonstrate how this leads us to the statement:

Any singleton (a one-element set) is a terminal object in $\mathrm{Set}$.

To demonstrate, first note that a cone over an empty diagram is just a set and a corresponding cone function is just a function. Therefore, we are looking for a “universal set” $•$ such that for an other set $C$, there is a unique function

$$f:C\to •.$$f:C\to\bullet.

Singletons fill the bill because for any element $c\in C$ we have the unique function defined by

$$f(c)=*.$$f(c) = *.

Therefore any singleton is a terminal object in $\mathrm{Set}$.

Product

A product is a universal cone over a discrete diagram. In this section, we demonstrate how this leads us to the statement:

Any cartesian product is a product in $\mathrm{Set}$.

To demonstrate, first note that a discrete diagram $F:J\to \mathrm{Set}$ produces a family of sets $(A_i)$ with no functions between them. A cone over the discrete diagram consists of a set $T$ and a single component

$$f_i:T\to A_i$$\f_i:T\to A_i

for each set $A_i$. Therefore, we are looking for a universal cone ${\prod }_i{A}_i$ such that for any other cone $T$, there is a unique cone function

$$f:T\to \prod _i{A}_i.$$f:T\to\prod_i A_i.

Cartesian product fills the bill because for any $t\in T$, we have the unique function defined by

$$f(t)=\prod _i{f}_i(t).$$f(t) = \prod_i f_i(t).

This function is unique because with any other function

$$g:T\to \prod _i{A}_i$$g:T\to\prod_i A_i

with ${\pi }_i\circ g=f_i$, then for any element $t\in T$

$$g(t)=\prod _i{f}_i(t)=\left(\prod _i{f}_i\right)(t)=f(t).$$g(t) = \prod_i f_i(t) = \left(\prod_i f_i\right)(t) = f(t).

Therefore $f=g$.

Equalizer

An equalizer is the universal cone over a parallel diagram

$$•\rightrightarrows •.$$\bullet\rightrightarrows\bullet.

In this section, we demonstrate how this leads us to the statement:

The equalizer of two functions is the subset on which both functions coincide.

To demonstrate, first note that a parallel diagram $F:J\to \mathrm{Set}$ produces two sets $X,Y$ with two parallel functions $f,g:X\to Y$. A cone over the parallel diagram consists of a set $T$ and two components

$$T_X:T\to X\text{and}{T}_Y:T\to Y.$$T_X:T\to X\quad\text{and}\quad T_Y:T\to Y.

This is the first example we encounter where the diagram contains morphisms so recall that with a cone we also want the the component diagrams to commute, i.e. we want

$$f\circ T_X=T_Y\text{and}g\circ T_X=T_Y.$$f\circ T_X = T_Y\quad\text{and}\quad g\circ T_X = T_Y.

Therefore, we are looking for a universal cone $\mathrm{Eq}$ such that for any other cone $T$, there is a unique function

$$f:T\to \mathrm{Eq}.$$f:T\to Eq.

Let’s first define the set

$$\mathrm{Eq}=\{x\in X\mid f(x)=g(x)\}$$Eq = \left\{x\in X|f(x)=g(x)\right\}

with two functions ${\mathrm{Eq}}_X:\mathrm{Eq}\to X$ and ${\mathrm{Eq}}_Y:\mathrm{Eq}\to Y$ defined by

$${\mathrm{Eq}}_X(x)=x\text{and}{\mathrm{Eq}}_Y(x)=f(x)$$Eq_X(x) = x\quad\text{and}\quad Eq_Y(x) = f(x)

and verify that it is indeed a cone. The only thing we need to check is that

$$g\circ {\mathrm{Eq}}_X={\mathrm{Eq}}_Y$$g\circ Eq_X = Eq_Y

which amounts to showing that $f(x)=g(x)$ for all $x\in \mathrm{Eq}$, but that is the definition of $\mathrm{Eq}$, so we do have a cone.

Now let $\varphi ,\psi :T\to \mathrm{Eq}$ be two cone functions. For any element $t\in T$, we have

$$T_X(t)={\mathrm{Eq}}_X\circ \varphi (t)={\mathrm{Eq}}_X\circ \psi (t)\Rightarrow \varphi (t)=\psi (t)$$T_X(t) = Eq_X\circ\phi(t) = Eq_X\circ\psi(t)\implies \phi(t)=\psi(t)

so that $\varphi =\psi$ and the cone function is unique.

Since every cone function $\varphi :T\to \mathrm{Eq}$ is unique, it follows that $\mathrm{Eq}$ together with ${\mathrm{Eq}}_X:\mathrm{Eq}\to X$ and ${\mathrm{Eq}}_Y:\mathrm{Eq}\to Y$ is a universal cone, i.e. $\mathrm{Eq}$ is an equalizer.

Pullbacks

A pullback is a universal cone over a cospan

$$\begin{array}{ccccccc}& & •& & & & •\\ & & & \searrow & & \swarrow & & \\ & & & & •& & & & \end{array}.$$\array{ && \bullet &&&& \bullet \\ & && \searrow & & \swarrow && \\ &&&& \bullet &&&& }.

In this section, we demonstrate how this leads us to the statement:

The pullback of two functions of sets is the set of pairs $(x,y)$ such that $f(x)=g(y)$.

To demonstrate, first note that a cospan $F:J\to \mathrm{Set}$ produces three sets $X,Y,Z$ with two functions $f:X\to Z$ and $g:Y\to Z$. A cone over the cospan consists of a set $T$ and three components

$$T_X:T\to X,T_Y:T\to Y,\text{and}{T}_Z:T\to Z$$T_X:T\to X,\quad T_Y:T\to Y,\quad\text{and}\quad T_Z:T\to Z

satisfying

$$f\circ T_X=T_Z\text{and}g\circ T_Y=T_Z,$$f\circ T_X = T_Z\quad\text{and}\quad g\circ T_Y = T_Z,

which implies, of course,

$$f\circ T_X=g\circ T_Y.$$f\circ T_X = g\circ T_Y.

Therefore, we are looking for a universal cone $\mathrm{Pb}$ such that for any other cone $T$, there is a unique function

$$f:T\to \mathrm{Pb}.$$f:T\to Pb.

Let’s first define the set

$$\mathrm{Pb}=\{(x,y)\mid f(x)=g(y)\}$$Pb = \left\{(x,y)|f(x)=g(y)\right\}

with three functions ${\pi }_X:\mathrm{Pb}\to X$, ${\pi }_Y:\mathrm{Pb}\to Y$, and $T_X:\mathrm{Pb}\to Z$ defined by

$${\pi }_X(x,y)=x,\text{and}{\pi }_Y(x,y)=y,\text{and}{T}_Z(x,y)=f(x)$$\pi_X(x,y) = x,\quad\text{and}\quad \pi_Y(x,y) = y,\quad\text{and}\quad T_Z(x,y) = f(x)

and verify that it is indeed a cone. The only thing we need to check is that

$$f\circ {\pi }_X=g\circ {\pi }_Y=T_Z$$f\circ\pi_X = g\circ \pi_Y = T_Z

which amounts to showing that $f(x)=g(y)$ for all $(x,y)\in \mathrm{Pb}$, but that is the definition of $\mathrm{Pb}$, so we do have a cone.

Now let $\varphi ,\psi :T\to \mathrm{Eq}$ be two cone functions with

$$\varphi (t)=({\varphi }_X(t),{\varphi }_Y(t)\text{and}\psi (t)=({\psi }_X(t),{\psi }_Y(t)$$\phi(t) = (\phi_X(t),\phi_Y(t)\quad\text{and}\quad\psi(t) = (\psi_X(t),\psi_Y(t)

for functions

$${\varphi }_X,{\psi }_X:T\to X\text{and}{\varphi }_Y,{\psi }_Y:T\to Y.$$\phi_X,\psi_X:T\to X\quad\text{and}\quad\phi_Y,\psi_Y:T\to Y.

For any element $t\in T$, we have

$$T_X(t)={\pi }_X\circ \varphi (t)={\pi }_X\circ \psi (t)\Rightarrow {\varphi }_X(t)={\psi }_X(t).$$T_X(t) = \pi_X\circ\phi(t) = \pi_X\circ\psi(t)\implies \phi_X(t)=\psi_X(t).

Similarly

$$T_Y(t)={\pi }_Y\circ \varphi (t)={\pi }_Y\circ \psi (t)\Rightarrow {\varphi }_Y(t)={\psi }_Y(t)$$T_Y(t) = \pi_Y\circ\phi(t) = \pi_Y\circ\psi(t)\implies \phi_Y(t)=\psi_Y(t)

so that $\varphi =\psi$ and the cone function is unique.

Since every cone function $\varphi :T\to \mathrm{Pb}$ is unique, it follows that $\mathrm{Pb}$ together with ${\pi }_X:\mathrm{Pb}\to X$, ${\pi }_Y:\mathrm{Pb}\to Y$, and $T_Z:\mathrm{Pb}\to Z$ is a universal cone, i.e. $\mathrm{Pb}$ is a pullback.

Fibred Products

Under Construction fibred products