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. A concrete category is given by:

• a collection of sets with structure,
• for any pair of such sets, a set of morphisms preserving the structure.

Morphisms should compose, and the identity should be a morphism.

This definition is a little informal, but here are some examples:

• Grp: groups and group morphisms
• Top: topological spaces and continuous functions
• Ring: rings and rings morphisms
• Vect: vectors spaces and linear maps
• 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} is given by:

• a collection Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}_o} of objects, (notation: Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}^{op}} . Explicitly, when for all object $C$ and morphisms Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle g,h \colon B \to C} , we have Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle gf = hf} implies Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} from a category Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} to a category Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{D}} , noted Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F \colon \mathcal{C} \to \mathcal{D}} , is given by:

• a map which sends every object Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle A} of Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} to an object Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle FA} in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{D}} , and
• a map which sends every morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f \colon A \to B} in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} , to a morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Ff} in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{D}[FA, FB]} ,

such that:

• Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} preserves identities, i.e., Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F(id_A) = id_{FA}} , and
• Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} preserves composition: Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F(f \circ g) = F(f) \circ F(g)} .

Exercice

1. Take a functor Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F \colon \mathcal{C} \to \mathcal{D}} , Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f, g, h} three morphisms in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} , and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f' = Ff} , Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle g' = Fg} , Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle h' = Fh} . When Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle h' = f' \circ g'} , can we say something interesting about Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f} , Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle g} and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f} and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle g} may not even compose! This is the case when Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f} has type Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle A \to B} , and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle g \colon C \to D} , with Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} collapsing Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle D} and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle A} (i.e., Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle FA = FD} ).
2. Functors in general do not preserve mono- nor epimorphisms. We build a counter-example for monomorphisms. Let Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathbf{2}} be the category with two objects Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \star} and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \bullet} , and exactly one morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m \colon \star \to \bullet} . This is a preorder, so Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m} is monic. Now take Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} with two objects Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \star} and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \bullet} , exactly one morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m \colon \star \to \bullet} , and one extra morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n \colon \star \to \star} , different from the identity. Because of Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n \neq id_\star} , yet Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m \circ n = m \circ id} , Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m} is not monic in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} . The functor which sends Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \star} to Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \star} , Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \bullet} to Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \bullet} and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m} in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathbf{2}} to Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m} in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} , does not preserve monomorphisms.
3. In general, the answer is (again) no. For monos, take for example the functor Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C} \to \mathbf{2}} which sends Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n} to the identity. Yet, when Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} is faithful, then Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f} is monic (or epic).

Definition. A functor Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} is faithful when, for any two morphisms Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f, g} , Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Ff = Fg} implies Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f=g} (Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} is injective on morphisms).

Definition. A functor Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} is full when, for any two objects Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle A, B} , if Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle g} is a morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle FA \to FB} , then there exists Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f \colon A \to B} with Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Ff = g} (Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} is surjective on morphisms).

Exercice

Find an "interesting" functor from Set to Group.

Answer Let Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} be the functor which sends:

• every set Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle X} to the free group generated by Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle X} , and
• every function Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f \colon X \to Y} to a group morphism defined by: Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} is a locally small category and A one of its objects, let Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Y_A : X \mapsto \mathcal{C}[X,A]} . Show that this operation from objects of Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} to sets can be extended into a contravariant functor Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} to Set.

Answer Let Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f\colon X \to Y} be a morphism in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} , then Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Y_A(f)} is expected to be a function from the set Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}[Y, A]} to the set Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}[X, A]} . We can take, for any morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m \in \mathcal{C}[Y,A]} : Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Y_A(f)(m) = m \circ f} .

This extends Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Y_A} to a contravariant functor, since Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Y_A(id_X) = id_{\mathcal{C}[X, A]}} and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle G} be two functors Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C} \to \mathcal{D}} . A natural transformation Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \alpha} from Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle F} to Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle G} is given by:

• a morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \alpha_A \colon FA \to GA} in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{D}} for every object Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle A} in Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} ,
• such that, for any morphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f \colon A \to B} , we have Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Gf \circ \alpha_A = \alpha_B \circ Ff} .

Exercice

If Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle P(X)} is the set of permutation of a (finite) set X; and Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle L(X)} the set of its linear orderings, we have Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \#(L(X)) = \#(L(X)) = n!} where Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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 and Monads

Preliminaries

2-categories and their diagrammatic calculus

This part is just to make the definitions of monads and adjunctions easier: we do not give the full details, and only intend to provide a few intuitions.

Definition. A 2-category is like a category: it has objects and morphisms between them. But it also has 2-cells, which are 'morphisms between morphisms':

These 2-cells must compose vertically and horizontally, satisfying the interchange law:

There is a more comfortable representation than the '2-diagrams' above. In pictures:

In words, the idea is to consider:

• objects as background colors,
• morphisms as vertical frontiers between them, and
• 2-cells as labelled dots.

Then, both compositions correspond to horizontal and vertical juxtaposition, respectively. For example, the interchange law corresponds to the two ways of parsing:

CAT as a 2-category

The prime example of a 2-category is of course Cat, the category of (small) categories. It has:

• objects: small categories,
• morphisms: functors,
• 2-cells: natural transformations.

Vertical composition of 2-cells is the obvious notion of composition of natural transformations.

Define the horizontal composition:

by

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle (\beta \bullet \alpha)_a = f' (f (a)) \xrightarrow{f' (\alpha_a)} f' (g (a)) \xrightarrow{\beta_{g (a)}} g' (g (a)) }

or equivalently

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle (\beta \bullet \alpha)_a = f' (f (a)) \xrightarrow{\beta_{f (a)}} g' (f (a)) \xrightarrow{g' (\alpha_a)} g' (g (a)).}

The two coincide by naturality. Observe that what we have actually done is:

• define whiskering, i.e., composing with an identity, both to the left and to the right, and
• observe that the two ways of defining horizontal composition from whiskering coincide.

This yields an equivalent definition of 2-categories.

Other basic examples

Discussion: any syntax defines the free something

The issue of variable binding.

Limits and Colimits

Limits

Example. Cartesian product.

Definition. Binary product.

Theorem. The product of X and Y, if it exists, is unique up to isomorphism. (with 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.

Monoidal categories

Definition and graphical calculus

• Definition
• Graphical calculus
• The 2-category of monoidal categories, strong monoidal functors, and monoidal transformations
• Coherence and its many definitions

From planar to symmetric monoidal categories

A teaser for the whole enchilada of variations on monoidal structure.

• Braided
• Balanced
• Symmetric
• Compact closed
• Traced monoidal categories and the Int/GoI construction

Monoidal categories for linear logic

• Linear logic
  • Sequent calculus
  • Intuitionnistic variant
  • Proof nets

• Symmetric monoidal closed categories

• Star-autonomous categories
  • Symmetric monoidal closed category with a dualising object
  • Symmetric monoidal category Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}} with:
    • a full and faithful contravariant endofunctor Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C}^{op} \xrightarrow{(-)^*} \mathcal{C} } , and
    • an isomorphism Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{C} (A \otimes B, C^*) \cong \mathcal{C} (A, (B \otimes C)^*).}

• Trimble-Hughes' free star-autonomous category
  • Split star-autonomy
  • The free star-autonomous category as a category of proof nets
  • Trimble rewiring

Perspectives

• Premonoidal categories and side effects
• Products and coproducts
• Monoidal 2-categories, monoidal double categories.

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.