Langage et concepts catégoriques pour les mathématiques et l’informatique

This is a wiki for a course at the MSTII "École doctorale" of Grenoble.

Students are encouraged to participate by extending the wiki, adding proofs, corrections for exercices etc. To be able to modify the wiki, you need to register (upper right corner). Please use your real name...

News

Courses are on wednesdays morning, 9'00 to 12'00 in room F218 at the "UFR IMAG".

• first course on the 25th of February: categories, functors, natural transformations.
• March 4. : monads, adjunctions.
• March 11. : limits and colimits.

Basic Concepts

Categories

{{Definition | CPO: CPOs and continuous functions

• ...
• Set: sets and functions (ie sets with no structures, and arbitrary functions)

Generalizing the definition, we obtain the official definition of category:

Definition. A category ${\mathcal {C}}$ is given by:

• a collection ${\mathcal {C}}_{o}$ of objects, (notation: $A,B,C,X,Y,...$)
• for each pair $A,B$ of objects, a collection ${\mathcal {C}}[A,B]$ of morphisms from $A$ to $B$, (notation $f:A\to B$)
• for any object $A$, a special morphism $i_{A}:A\to A$
• for all objects $A,B,C$, a composition $\circ :{\mathcal {C}}[B,C]\times {\mathcal {C}}[A,B]\to {\mathcal {C}}[A,C]$,

such that:

• $f\in {\mathcal {C}}[A,B]\implies f\circ i_{A}=i_{B}\circ f=f$
• $f\circ (g\circ h)=(f\circ g)\circ h$ whenever it makes sense.

All concrete categories are categories, and here are some examples that are not obviously concrete:

• Graph: graphs and graph morphisms
• Rel: sets and relations
• Set×Set: pairs of sets, pairs of functions
• Set$^{op}$: opposite of Set
• P, whenever (P,<) is a preorder (at most one morphism between objects)
• M, whenever (M,e,×) is a monoid (a single object)

We sometimes write $gf$ instead of $g\circ f$.

In a given category ${\mathcal {C}}$, there are analogues of the notions of injective and surjective functions in Set. We will see that on concrete categories, they are actually slightly more general. The idea of injectivity gives rise to monomorphisms, and surjectivity gives rise to epimorphisms.

Definition.

A morphism $f\colon A\to B$ is a monomorphism iff for all object $C$ and morphisms $g,h\colon C\to A$, we have $fg=fh$ implies $g=h$.

The morphism $f$ is an epimorphism when it is a monomorphism in ${\mathcal {C}}^{op}$. Explicitly, when for all object $C$ and morphisms $g,h\colon B\to C$, we have $gf=hf$ implies $g=h$.

 isomorphism

Exercice

1. Prove that in Set, epic is equivalent to surjective and monic is equivalent to injective.
2. Prove the same thing in Ab, the category of commutative groups. (One thing is not obvious.)
3. Prove the same thing in Grp, the category of (non necessarily commutative) groups. (One thing is not obvious at all.)
4. Prove that $i:\mathbf {Z} \to \mathbf {Q}$ is an epimorphism in the category of rings with multiplicative neutral. (Note that it is not surjective.)
5. In Set, we saw that f is a monic iff $\forall x,y:1\to A,f\circ x=f\circ y\implies x=y$, where 1 is any singleton set. Can you find a set C such that f is epic iff $\forall p,q:B\to C,p\circ f=j\circ f\implies p=q$?
6. In Group, can you find an object playing a role similar to 1, ie a group G s.t. f is monic iff $\forall x,y:G\to A,f\circ x=f\circ y\implies x=y$. (We saw that we cannot use the singleton group ({e},e,×) to do that...)

Functors

Informally, a functor is a map between two categories which somehow preserves the structure of categories (namely, composition).

Definition. A functor $F$ from a category ${\mathcal {C}}$ to a category ${\mathcal {D}}$, noted $F\colon {\mathcal {C}}\to {\mathcal {D}}$, is given by:

• a map which sends every object $A$ of ${\mathcal {C}}$ to an object $FA$ in ${\mathcal {D}}$, and
• a map which sends every morphism $f\colon A\to B$ in ${\mathcal {C}}$, to a morphism $Ff$ in ${\mathcal {D}}[FA,FB]$,

such that:

• $F$ preserves identities, i.e., $F(id_{A})=id_{FA}$, and
• $F$ preserves composition: $F(f\circ g)=F(f)\circ F(g)$.

Exercice

1. Take a functor $F\colon {\mathcal {C}}\to {\mathcal {D}}$, $f,g,h$ three morphisms in ${\mathcal {C}}$, and $f'=Ff$, $g'=Fg$, $h'=Fh$. When $h'=f'\circ g'$, can we say something interesting about $f$, $g$ and $h$?
2. Do functors preserve monomorphisms? Do functors preserve epimorphisms?
3. Let F be a functor and F(f) = g, if g is a mono (resp. epi), is f a mono (resp. epi)?

If not, try to find some simple and natural condition on the functor to make that true.

Answer

1. No, since $f$ and $g$ may not even compose! This is the case when $f$ has type $A\to B$, and $g\colon C\to D$, with $F$ collapsing $D$ and $A$ (i.e., $FA=FD$).
2. Functors in general do not preserve mono- nor epimorphisms. We build a counter-example for monomorphisms. Let $\mathbf {2}$ be the category with two objects $\star$ and $\bullet$, and exactly one morphism $m\colon \star \to \bullet$. This is a preorder, so $m$ is monic. Now take ${\mathcal {C}}$ with two objects $\star$ and $\bullet$, exactly one morphism $m\colon \star \to \bullet$, and one extra morphism $n\colon \star \to \star$, different from the identity. Because of $n\neq id_{\star }$, yet $m\circ n=m\circ id$, $m$ is not monic in ${\mathcal {C}}$. The functor which sends $\star$ to $\star$, $\bullet$ to $\bullet$ and $m$ in $\mathbf {2}$ to $m$ in ${\mathcal {C}}$, does not preserve monomorphisms.
3. In general, the answer is (again) no. For monos, take for example the functor ${\mathcal {C}}\to \mathbf {2}$ which sends $n$ to the identity. Yet, when $F$ is faithful, then $f$ is monic (or epic).

Definition. A functor $F$ is faithful when, for any two morphisms $f,g$, $Ff=Fg$ implies $f=g$ ($F$ is injective on morphisms).

Definition. A functor $F$ is full when, for any two objects $A,B$, if $g$ is a morphism $FA\to FB$, then there exists $f\colon A\to B$ with $Ff=g$ ($F$ is surjective on morphisms).

Exercice

Find an "interesting" functor from Set to Group.

Answer Let $F$ be the functor which sends:

• every set $X$ to the free group generated by $X$, and
• every function $f\colon X\to Y$ to a group morphism defined by: $Ff(x_{1}^{\alpha _{1}}\times \dots \times x_{k}^{\alpha _{k}})=f(x_{1})^{\alpha _{1}}\times \dots \times f(x_{k})^{\alpha _{k}}$.

Exercice

If ${\mathcal {C}}$ is a locally small category and A one of its objects, let $Y_{A}:X\mapsto {\mathcal {C}}[X,A]$. Show that this operation from objects of ${\mathcal {C}}$ to sets can be extended into a contravariant functor ${\mathcal {C}}$ to Set.

Answer Let $f\colon X\to Y$ be a morphism in ${\mathcal {C}}$, then $Y_{A}(f)$ is expected to be a function from the set ${\mathcal {C}}[Y,A]$ to the set ${\mathcal {C}}[X,A]$. We can take, for any morphism $m\in {\mathcal {C}}[Y,A]$: $Y_{A}(f)(m)=m\circ f$.

This extends $Y_{A}$ to a contravariant functor, since $Y_{A}(id_{X})=id_{{\mathcal {C}}[X,A]}$ and $Y_{A}(f\circ g)(m)=m\circ (f\circ g)=(m\circ f)\circ g=(Y_{A}(g)\circ Y_{A}(f))(m)$.

Natural Transformations

Definition. Let $F$ and $G$ be two functors ${\mathcal {C}}\to {\mathcal {D}}$. A natural transformation $\alpha$ from $F$ to $G$ is given by:

• a morphism $\alpha _{A}\colon FA\to GA$ in ${\mathcal {D}}$ for every object $A$ in ${\mathcal {C}}$,
• such that, for any morphism $f\colon A\to B$, we have $Gf\circ \alpha _{A}=\alpha _{B}\circ Ff$.

Exercice

If $P(X)$ is the set of permutation of a (finite) set X; and $L(X)$ the set of its linear orderings, we have $\#(L(X))=\#(L(X))=n!$ where $n=\#(X)$. Thus, there is a bijection (iso in Set) between P(X) and L(X).

1. Show that we can extend P and L to functors from B to Set, where B is the category of finite sets and bijections,
2. Show that there can be no natural transformation from P to L,
3. Conclude that there is no natural isomorphism between P and L.

Adjunctions

About Limits and Colimits

One of the main thrusts of category theory is to define concepts by their properties rather than by explicit construction. In general this is just called abstraction, but in good cases, concepts are defined by their properties, at least canonically if not uniquely.

The chief example of this is binary products in Set. The product $A\times B$ of two sets $A$ and $B$ is generally thought of as the set of pairs $(x,y)$ with $x\in A$ and $y\in B$. But strictly speaking, or rather set-theoretically speaking, one has to construct it by cautious use of the axioms of Zermelo-Fraenkel set theory.

Instead, in any category ${\mathcal {C}}$, for any objects $A$ and $B$ categorists put:

Definition. A product of $A$ and $B$ is an object $C$ with arrows

$A\xleftarrow {\pi _{1}} C\xrightarrow {\pi _{2}} B$

such that for any object $D$ and arrows

$A\xleftarrow {f} D\xrightarrow {g} B$

there exists a unique arrow $h$ making the diagram

commute, i.e., $\pi _{1}\circ h=f$ and $\pi _{2}\circ h=g$.

The standard constructions in Set all have this property, and all the non-standard ones you can think of also do, e.g., the set of pairs $(\emptyset ,x,y)$ with $x\in A$ and $y\in B$.

Conversely, any set with this property is as good as any other construction of $A\times B$.

Products are determined canonically by this property property. We will give a more precise meaning to this in later lectures; for now we just state:

Lemma.

For any other product

$A\xleftarrow {p} E\xrightarrow {q} B$

of

$A$ and $B$, there is a unique isomorphism pair $(r,s)$ such that the diagrams

and

commute.

Other basic examples

====Discussion: any syntax defines the free something==== The issue of variable binding.

Limites and Colimits

Limits

Example. Cartesian product.

Definition. Binary product.

Theorem. The product of X and Y, if it exists, is unique up to isomorphism. (proof)

Examples. Set, Grp, Ab, Part.

Examples. Preorder, Subset(E), Prop with entailment.

Definition. Diagram. Cone. Limit.

Example. Limits in Set.

Examples. Shape of diagrams for products, pullbacks, equalizers.

Example. Monos as pullbacks.

Theorem. The limit of a diagram d, if it exists, is unique up to isomorphism.

Theorem. A category with "all" products and equalizers has "all" limits.

Theorem. A category with a terminal object and all binary products and all equalizers has "all" finite limits.

Colimits

Definition. Cocone. Colimit.

Examples. Sums in Set, Grp, Ab.

Examples. Shape of diagrams for sums, initial objects, pushouts, coequalizers.

Example. Epis as pushouts.

Theorem. The colimit of a diagram d, if it exists, is unique up to isomorphism.

Example. The most general unifier (of two terms) is a coequalizer in the "category of substitutions".

Theorem. A category with "all" sums and coequalizers has "all" colimits.

Theorem. A category with an initial object and all binary sums and all coequalizers has all finite colimits.

Limits, colimits and adjunctions

Theorem. A right adjoint preserves limits. A left adjoint preserves colimits. (with proof of existence)

Example. The adjunction between Set and Grp

Sums and products

A category is distributive if the canonical map from AxB+AxC to Ax(B+C) is an isomorphism.

A category is extensive if the canonical functor + from C/A x C/B to C/(A+B) is an equivalence.

Example. "if..then..else.." from B=1+1 and extensivity.

Course Complements, references

One of the best books about category theory is

• Saunder MacLane, "Categories for the Working Mathematician".

It is a little "dry", in the sense that learning categories from it is not the easiest task on earth, but it still is one of the best references.

I haven't really read it carefully, but here is what Wikipedia has to say on category theory.