nLab
Understanding limits in Set

Contents

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:JSetF:J\to Set is a cone TT over JJ such that, given any cone TT', there is a unique cone function from TT' to TT.

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 SetSet.

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” \bullet such that for an other set CC, there is a unique function

f:C.f:C\to\bullet.

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

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

Therefore any singleton is a terminal object in SetSet.

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 SetSet.

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

f i:TA i\f_i:T\to A_i

for each set A iA_i. Therefore, we are looking for a universal cone iA i\prod_i A_i such that for any other cone TT, there is a unique cone function

f:T iA i.f:T\to\prod_i A_i.

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

f(t)= if i(t).f(t) = \prod_i f_i(t).

This function is unique because with any other function

g:T iA ig:T\to\prod_i A_i

with π ig=f i\pi_i\circ g = f_i, then for any element tTt\in T

g(t)= if i(t)=( if i)(t)=f(t).g(t) = \prod_i f_i(t) = \left(\prod_i f_i\right)(t) = f(t).

Therefore f=gf = g.

Equalizer

An equalizer is the universal cone over a parallel diagram

.\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:JSetF:J\to Set produces two sets X,YX,Y with two parallel functions f,g:XYf,g:X\to Y. A cone over the parallel diagram consists of a set TT and two components

T X:TXandT Y:TY.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

fT X=T YandgT 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 EqEq such that for any other cone TT, there is a unique function

f:TEq.f:T\to Eq.

Let’s first define the set

Eq={xXf(x)=g(x)}Eq = \left\{x\in X|f(x)=g(x)\right\}

with two functions Eq X:EqXEq_X:Eq\to X and Eq Y:EqYEq_Y:Eq\to Y defined by

Eq X(x)=xandEq 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

gEq X=Eq Yg\circ Eq_X = Eq_Y

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

Now let ϕ,ψ:TEq\phi,\psi: T\to Eq be two cone functions. For any element tTt\in T, we have

T X(t)=Eq Xϕ(t)=Eq Xψ(t)ϕ(t)=ψ(t)T_X(t) = Eq_X\circ\phi(t) = Eq_X\circ\psi(t)\implies \phi(t)=\psi(t)

so that ϕ=ψ\phi = \psi and the cone function is unique.

Since every cone function ϕ:TEq\phi:T\to Eq is unique, it follows that EqEq together with Eq X:EqXEq_X:Eq\to X and Eq Y:EqYEq_Y:Eq\to Y is a universal cone, i.e. EqEq is an equalizer.

Pullbacks

A pullback is a universal cone over a cospan

. \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)(x,y) such that f(x)=g(y)f(x)=g(y).

To demonstrate, first note that a cospan F:JSetF:J\to Set produces three sets X,Y,ZX,Y,Z with two functions f:XZf:X\to Z and g:YZg:Y\to Z. A cone over the cospan consists of a set TT and three components

T X:TX,T Y:TY,andT Z:TZT_X:T\to X,\quad T_Y:T\to Y,\quad\text{and}\quad T_Z:T\to Z

satisfying

fT X=T ZandgT Y=T Z,f\circ T_X = T_Z\quad\text{and}\quad g\circ T_Y = T_Z,

which implies, of course,

fT X=gT Y.f\circ T_X = g\circ T_Y.

Therefore, we are looking for a universal cone PbPb such that for any other cone TT, there is a unique function

f:TPb.f:T\to Pb.

Let’s first define the set

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

with three functions π X:PbX\pi_X:Pb\to X, π Y:PbY\pi_Y:Pb\to Y, and T X:PbZT_X:Pb\to Z defined by

π X(x,y)=x,andπ Y(x,y)=y,andT 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π X=gπ Y=T Zf\circ\pi_X = g\circ \pi_Y = T_Z

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

Now let ϕ,ψ:TEq\phi,\psi: T\to Eq be two cone functions with

ϕ(t)=(ϕ X(t),ϕ Y(t)andψ(t)=(ψ X(t),ψ Y(t)\phi(t) = (\phi_X(t),\phi_Y(t)\quad\text{and}\quad\psi(t) = (\psi_X(t),\psi_Y(t)

for functions

ϕ X,ψ X:TXandϕ Y,ψ Y:TY.\phi_X,\psi_X:T\to X\quad\text{and}\quad\phi_Y,\psi_Y:T\to Y.

For any element tTt\in T, we have

T X(t)=π Xϕ(t)=π Xψ(t)ϕ X(t)=ψ 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)=π Yϕ(t)=π Yψ(t)ϕ Y(t)=ψ Y(t)T_Y(t) = \pi_Y\circ\phi(t) = \pi_Y\circ\psi(t)\implies \phi_Y(t)=\psi_Y(t)

so that ϕ=ψ\phi = \psi and the cone function is unique.

Since every cone function ϕ:TPb\phi:T\to Pb is unique, it follows that PbPb together with π X:PbX\pi_X:Pb\to X, π Y:PbY\pi_Y:Pb\to Y, and T Z:PbZT_Z:Pb\to Z is a universal cone, i.e. PbPb is a pullback.

Fibred Products

Under Construction fibred products

Revised on October 9, 2010 14:55:06 by Eric Forgy (219.78.39.176)