April 25, 2024
Besides it is an error to believe that rigour is the enemy of simplicity. On the contrary we find it confirmed by numerous examples that the rigorous method is at the same time the simpler and the more easily comprehended. The very effort for rigor forces us to find out simpler methods of proof. — David Hilbert
In classical mathematics everything is a set. Logicians like to say “the language of Set Theory is epsilon”, meaning only the symbol \in is used in specifying the axioms to indicate set membership. Category Theory provides an alternate way of doing math using objects and arrows. The canonical example of a category is \mathbf{Set}. The objects are sets and the arrows are functions from one set to another. If f\colon A\to B and g\colon B\to C are functions then the composition of f and g is g\circ f\colon A\to C where g\circ f(a) = g(f(a)).
Exercise. Show if f\colon A\to B, g\colon B\to C, and h\colon C\to D then h\circ(g\circ f) = (h\circ g)\circ f.
This makes writing h\circ g\circ f unambiguous. The identity function for a set A is 1_A(a) = a for a\in A.
Exercise. Show if f\colon A\to B then f\circ 1_A = f = 1_B\circ f.
A category consists of objects and arrows that can sometimes be composed. Arrows that can be composed are associative. Every object has an identity arrow. In category theory everything is defined in terms of objects and arrows. You will need to disabuse yourself of the notion that arrows are functions and objects have elements. Arrows are more general and lead to a notion of parameterized set elements (sheafs).
An arrow f from object A to object B is written f\colon A\to B.
The domain of f is \operatorname{dom}f = A and the codomain of f is \operatorname{cod}f = B The codomain is also called range, target, or but if you parlez Français.
We could do away with objects and use the domain and codomain of arrows, just as it is possible to use nand to define all other logical operators, but why make things more difficult?
The “set” of arrows from A to B is called \hom(A,B), or \hom_{\mathbf{C}}(A,B) to indicate they come from category \mathbf{C}. The scare quotes indicate this is not necessarily a set but standard terminology for this is homset. Hom is short for homomorphism indicating arrows preserve the structure of objects. Homsets are also written \mathbf{C}[A,B]. We will use the non-standard but more suggestive notation \{A\to B\} or \{A\to B\in \mathbf{C}\} when indicating the category is necessary.
If f\colon A\to B and g\colon B\to C then there exists an arrow g \circ f\colon A\to C, the composition of g with f.
Since we will be doing a lot of composing we just write gf instead of g \circ f. Some people prefer to use f;g instead of gf. In this notation f\colon A\to B and g\colon B\to C compose to f;g\colon A\to C keeping the arrow names in order. If this sort of trifling is a concern you can just write the arrows backwards: g\colon C\leftarrow B and f\colon B\leftarrow A so gf\colon C\leftarrow A.
Every object has an identity arrow. If f\colon A\to B then the identity arrows 1_A\colon A\to A and 1_B\colon B\to B satisfy f 1_A = f = 1_B f. One can always throw in identity arrows if they don’t exist.
Exercise. If e\colon A\to A has the property fe = f for all f\colon A\to B then e = 1_A.Taking f = 1_A, 1_A e = 1_A. By the definition of 1_A, 1_A e = e, hence 1_A = e.
Taking f = 1_B, e 1_B = 1_B. By the definition of 1_B, e 1_B = e, hence 1_B = e.
If f\colon A\to B, g\colon B\to C, and h\colon C\to D then we have arrows gf, hg, h(gf), and (hg)f. The associative law states (hg)f = h(gf) so hgf is unambiguous in category theory.
A collection of objects and arrow satisfying these laws is a category.
A category consists of objects and arrows. Every arrow f has two objects associated with it, its domain \operatorname{dom}{f} and its codomain \operatorname{cod}{f}. We write f\colon A\to B when A is the domain of f and B is the codomain of f. If f\colon A\to B and g\colon B\to C then gf\colon A\to C exists. If f\colon A\to B, g\colon B\to C, and h\colon C\to D then gf\colon A\to C and hg\colon C\to D exist and h(gf) = (hg)f.
Every object A has an identity arrow 1_A. If f\colon A\to B then f1_A = f = 1_B f.
Reversing all arrows in a catgory results in the opposite category \mathbf{C}^{op}.
Exercise. Show \mathbf{C}^{op} is a category.
A key concept in category theory is isomorphism. Two objects A and B are isomorphic if there exist arrows f\colon A\to B and g\colon B\to A with fg = 1_B and gf = 1_A and we write A\cong B. If A=B then 1_A = f = g = 1_B demonstrates A and A are isomorphic.
Exercise. Show isomorphism is an equivalence relation.
Hint: We have shown A\cong A for every object A. Show A\cong B implies B\cong A and A\cong B, B\cong C imply A\cong C.
Equivalence as a weakened form of equality. In the case of \mathbf{Set} it is a very weakened form; two sets are isomorphic if and only if they have the same cardinality. Adding structure to sets by reducing the number of functions creates finer grained equivalence relations.
Exercise. Show two sets in \mathbf{Set} are isomorphic if and only if they have the same cardinality.
We call f,g an isomorphism pair for A,B. If f,g and f,g' are isomporphims pairs for A,B then g = g' since g = g1_B = g(fg') = (gf)g' = 1_Ag' = g'. We write g = f^{-1} and, mutatis mutandis, f = g^{-1}.
Isomorphism pairs are not, in general, unique. We can define an equivalence relation on isomorphism pairs by (f,g)\tilde (f',g') if and only if they are isomorphism pairs for some A, B.
Exercise. Show this is an equivalence relation.
A functor F\colon\mathbf{A}\to\mathbf{B} takes objects and arrows of \mathbf{A} to objects and arrows of \mathbf{B} and respects the category structure. If f\colon A\to A', in \mathbf{A} then F(f)\colon F(A)\to F(A') in \mathbf{B} with F(gf) = F(g)F(f).
Exercise. Show F(gf) = F(g)F(f) implies F(1_A) = 1_{F(A)}.
This shows we only need to define a functor on arrows; objects ride along for free.
The category \mathbf{Cat} has objects categories and arrows functors. If F\colon\mathbf{A}\to\mathbf{B} and G\colon\mathbf{B}\to\mathbf{C} are functors then composition GF\colon\mathbf{A}\to\mathbf{C} is (GF)(A) = G(F(A)). The identity functor is the identity of \mathbf{Cat}.
The category \mathbf{2-Cat} has objects functors and arrows natural transformations. If F,G\colon\mathbf{A}\to\mathbf{B} are functors a natural transformation \eta\colon F\to G takes objects A of \mathbf{A} to arrows \eta_A of \mathbf{B}.
Natural transformations must satisfy h\colon A\to A' in \mathbf{A} then G(h)\eta_A = \eta_{A'}F(h) in \mathbf{B}.
In case you are wondering, \mathbf{n-Cat} can be defined for all positive integers n.
It is impossible to understand category theory without being familiar with examples of categories. They are its raison d’être. Many seemingly disparate constructs can be unified using category theory.
The category \mathbf{Mon} is the collection of all categories having only one object. Any such category is a monoid where the (one and only) identity arrow is the identity element of the monoid and composition of arrows is the binary operation of the moniod.
Exercise. Show any two arrows of a monoid can be composed.
The canonical example of a category is \mathbf{Set}. The objects are sets and the arrows are functions. People tried to come up with a purely category theory notion of \mathbf{Set} and ended up with topos theory. One does not simply consider ‘elements’ of a ‘set’. Composition is standared function composition, which is associative. The identity arrows are the identity functions 1_A\colon A\to A by 1_A(a) = a for a\in A.
Then there is \mathbf{Par}, the category of partial functions. It does not get the respect it deserves. Most functions are actually partial functions. The function x\mapsto 1/x is only a partial function from the real numbers to the real numbers. The partial functions f\colon A\to B and g\colon B\to C can be composed using gf(a) = c if and only if there exists b\in B with f(a) = b and g(b) = c. It has the same identity arrows as \mathbf{Set}.
A case could be made that \mathbf{Set} should be called \mathbf{Fun}.
\mathbf{Rel} is the category of relations. It generalizes \mathbf{Set} and \mathbf{Par}. A relation is a subset R\subseteq A\times B of the cartesian product. We write aRb for (a,b)\in R, a\in A, b\in B. The composition of relations R\colon A\to B and S\colon B\to C is SR = \{(a,c): aRb\text{ and } bRc \text{ for some }b\in B\}\subseteq A\times C.
Exercise: Show 1_A = \{(a,a):a\in A\} is the identity and composition of relations is associative.
There are a slew of examples of categories where the objects are sets ‘with structure’ and the arrows are functions that preserve that structure.
We have already seen \mathbf{Mon}, categories having exactly one object.
\mathbf{Grp} is the category of groups; the objects are groups and the arrows are homomorphisms, functions that preserve the group structure.
\mathbf{Vec} is the category of vector spaces; the objects are vector spaces and the arrows are linear transformations.
Rings, fields, and algebras provide more examples. The theme of category theory is to provide a unified treatment of various mathematical areas.
All of these examples satisfy a lemma of the form every arrow f\colon A\to B is a composition of arrows \pi\colon A\to A/\operatorname{ker}f, \nu\colon A/\operatorname{ker}f\to \operatorname{ran}B, and \iota\colon \operatorname{ran}B\to B where \pi is ‘onto’, \nu is ‘one-to-one’, and \iota is ‘inclusion’ for appropriate definitions of \operatorname{ker}, \operatorname{ran}, quotient /, onto, one-to-one, and inclusion. Arrows can be used to factor objects into smaller objects A/\operatorname{ker}f and \operatorname{ran}f.
\mathbf{Pre} is the category of presets. A preset is a set wtih a relation \preceq that is reflexive (a\preceq a) and transitive (a\preceq b and b\preceq c imply a\preceq b). Such relations are called preorders. Presets long predate categories, but this maps perfectly into the the definition of a category. The objects are elements of the set and there is an arrow x\to y if and only if x \preceq y. The identity arrow is the reflexive property and composition is the transitive law. Preorders have the property that homsets have at most one arrow. Every category with this property is a preset.
\mathbf{Pos} is the category of posets. A poset is a preset that is also antisymmetric (a\preceq b and b\preceq a imply a = b). Such relations are called partial orders. The category Set can be viewed as a poset under subset inclusion. The objects are sets and the arrows are f\colon A\to B if A\subseteq B.
\mathbf{Equ} is the category of equivalence relations. An equivalence relations is a preorder that is also symmetric (a\sim b implies b\sim a). Equivalence relations are used to classify objects.
\mathbf{Cat} is the category of categories. The objects are categories and the arrows are functors.
A functor from category C to category D takes objects of C to objects of D and arrows of C to arrows of D and preserves the category structure:
Exercise. What is the identity functor?
Exercise. Show composition of functors is associative.
You may now be wondering if there is a category of category of categories. There is and it is called 2-\mathbf{Cat}. The objects are functors and the arrows are natural transformations.
A natural transformation, \eta\colon F\to G, of functors F,G\colon\mathbf{C}\to\mathbf{D} takes objects of \mathbf{C} to arrows of \mathbf{D}. If h\colon A\to B in \mathbf{C} then F(h)\colon F(A)\to F(B) and G(h)\colon G(A)\to G(B) in \mathbf{D}. The arrows \eta_A\colon F(A)\to G(A) and \eta_B\colon G(A)\to G(B) in \mathbf{D} satisfy \eta_A F(h) = G(h)\eta_B.
The prototypical example of natural transformation arises in the category \mathbf{Vec}. The dual of a vector space is V^* = \hom(V,\mathbf{F}) where \mathbf{F} is the underlying field of the vector space. The dual pairing between V and V^* is \langle v,v^*\rangle = v^*(v). If T\colon V\to W is a linear transformation then T^*\colon W^*\to V^* via \langle Tv,w^*\rangle = \langle v,T^*w^*\rangle. Note T^{**}\colon V^{**}\to W^{**} and gives rise to a functor D in \mathbf{Vec} via V\mapsto V^{**} and T\mapsto T^{**}. There is a natural inclusion \iota_V\colon V\to V^{**} by \langle \iota_V v,v^*\rangle = \langle v, v^*\rangle. The property T^{**}\iota_V = \iota_W T says \iota\colon I\to D is a natural transformation where I is the identity functor of \mathbf{Vec}.
Exercise. Show T^{**}\iota_V = \iota_W T.
For v\in V and w^*\in W^*, \langle T^{**}\iota_V v,w^*\rangle =\langle \iota_V v,T^*w^*\rangle =\langle v,T^*w^*\rangle =\langle Tv,w^*\rangle =\langle \iota_W Tv,w^*\rangle.
Are there categories of categories of …? Yep. They are called n-\mathbf{Cat}. It’s categories all the way down.
Although \mathbf{Set} is a prototypical example of a category you will need to disabuse yourself of the notion objects have elements. Everything in category theory must be expressed in terms of objects and arrows. Attempts to express \mathbf{Set} purely in terms of objects and arrows leads to \mathbf{Top}, the category of topoi. This attempt failed in the sense that it did not lead back to the category \mathbf{Set}. It was succesful at giving a better understanding of the foundations of mathematics. As often happens in mathematics, following your nose leads to complications. For example, a sphere is a set. The elements of the set are points on the sphere. In a topoi the “elements” of the sphere are the tangent planes to each point. This is an example of a sheaf.
We have already seen how to use arrows to define isomorphisms. If A and B are isomorphic then there are arrows f\colon A\to B and g\colon B\to A with fg = 1_B and gf = 1_A. We say f\colon A\to B has right inverse g\colon B\to A when fg = 1_B and f has left inverse g when gf = 1_A.
Exercise. If f has right inverse g and left inverse g' show g = g'.We have g' = g'1_B = g'(fg) = (g'f)g = 1_Ag = g.
This shows an arrow with both a right and left inverse is an isomorphism.
If fh = fk implies h = k then f is called mono. If f has a right inverse and h,k\colon B\to C satisfy hf = kf then h = h1_B = hfg = kfg = k1_B = k. Arrows having a right inverse are mono.
If hf = kf implies h = k then f is called epi. If f has a left inverse and h,k\colon C\to A satisfy fh = fk then h = 1_Ah = gfh = gfk = 1_Ak = k. Arrows having a left inverse are epi.
In \mathbf{Set} mono arrows have a left inverse and epi arrows have a right inverse, but this is not true for every category.
An arrow that is both mono and epi is called iso.
Nobody understands the Yoneda Lemma. As Von Neumann said, “you don’t understand math, you just get used to it.” It is similar to Cayley’s theorem that states every group is (isomorphic to) a subgroup of the permutaion group of the set of group elements. The abstract notion of a group defined in terms of axioms can be represented by embedded it in a more familiar structure. The Yoneda Lemma is different from Cayley’s theorem in that it represents categories by embedding them in a less familiar structure.
If f\colon X\to Y and g\colon Y\to Z then gf\colon X\to Z so right composition induces
a map f\to Z\colon\{Y\to Z\}\to\{X\to
Z\}, (f\to Z)g = gf.
If g\colon Z\to X and f\colon X\to Y then fg\colon Z\to Y so left composition induces a
map Z\to f\colon\{Z\to X\}\to\{Z\to
Y\}, (Z\to f)g = fg.
Let \{\_\to Z\} be the category with
arrows f\to Z\colon\{Y\to Z\}\to\{X\to
Z\}, f\colon X\to Y.
If f\colon X\to Y and g\colon U\to V then f\to Z\colon\{Y\to Z\}\to\{X\to Z\} and g\to Z\colon\{V\to Z\}\to\{U\to Z\}.
If V = X we can compose fg\colon U\to Y in \mathbf{C} and (g\to Z)(f\to Z)\colon\{Y\to Z\}\to\{U\to Z\}
in \{\_\to Z\},
Exercise. Show fg\to Z = (g\to Z)(f\to Z).
Let \{Z\to\_\} be the category with
arrows Z\to f\colon\{Z\to X\}\to\{Z\to
Y\}, f\colon X\to Y.
If f\colon X\to Y and g\colon U\to V then Z\to f\colon\{Z\to X\}\to\{Z\to Y\} and Z\to g\colon\{Z\to U\}\to\{Z\to V\}.
If U = Y we can compose gf\colon X\to V in \mathbf{C} and (Z\to g)(Z\to f)\colon\{Z\to X\}\to\{Z\to V\}
in \{Z\to\_\},
Exercise. Show Z\to gf = (Z\to g)(Z\to f).
For every object Z in \mathbf{C} define the contravariant functor \to Z\colon\mathbf{C}\to\{\_\to Z\} by f\mapsto f\to Z. For every object Z in \mathbf{C} define the (covariant) functor \to Z\colon\mathbf{C}\to\{\_\to Z\} by f\mapsto Z\to F
The product \Pi_{i\in I} X_i = \Pi X_I of X_i is defined by arrows \pi_i\colon \Pi X_I\to X_i, i\in I. If for any arrows p_i\colon Y\to X_i there exists an arrow p\colon Y\to \Pi X_I with \pi_ip = p_i, i\in I. The product of X and Y is denoted X\times Y.
???
The cartesian product of X with itself Y times, \Pi X_Y = \Pi_{y\in Y} X, can be defined for any set Y. It can be identified with X^Y and has projections \pi_y\colon \Pi X_y\to X defined by \pi_y x = x(y), x\in X^Y, $yY. We write \pi_y x = x_y and x = (x_y) as an array in the product for x as a function in the exponential.
Exercise. If u,v\in\Pi X_Y and \pi_y u = \pi_y v for all y\in Y then u = v as functions in Y^X.
The sum \Sigma_{i\in I} X_i = \Sigma X_I of X_i, is defined by arrows \nu_i\colon X_i\to\Sigma X_I, i\in I. If for any arrows n_i\colon X_i\to Y there exists an arrow n\colon\Sigma X_I\to Y with n\nu_i = n_i, i\in I. The sum of X and Y is denoted X + Y.
It is trivial to verify that reversing all arrows in a category \mathbf{A} results in the opposite, or dual, category, \mathbf{A}^{op}.
A presheaf is a functor F\colon\mathbf{C}^{op}\to\mathbf{Set}. This embeds any abstract category \mathbf{C} in the concrete category \mathbf{Set}. It is similar to Cayley’s theorem that every group is a subgroup of all permutations of the group elements.
Not all Boolean algebras are isomorphic to a powerset. Stone’s theorem.
Pay homage to Frege, Russell, … Gentzen.
set <=> collection
element <=> item
A semigroup is a set with an associative binary operation, stu, s,t,u\in S is unambiguous.
A moniod is a semigroup with an identity element e, me = m = em. Every semigroup S can be turned into a monoid by adjoining an element e not in the semigroup and extending the binary operation by defining se = s = es for s\in S.
A precategory is a collection with an associative partially defined transitive binary operation.
A category is a precategory where every item has a left and a right identity. Every precategory \mathbf{C} can be turned into a category by adjoining elements e_c and {}_ce if c is an item of \mathbf{C} and extending the binary operation by defining e_c c = c and c{}_ce = e.
Opposite category: …
An F-algebra for category \mathbf{C} is an endofunctor F\colon\mathbf{C}\to\mathbf{C}, an object A, and an arrow α\colon F(A)\to A. If (B,β) is an F-algebra then f\colon A\to B is an F-algebra homomorphism if fα = βF(f).
A (small) category is a set \mathbf{C} and a binary partial operation \circ\colon\mathbf{C}\times\mathbf{C}\to\mathbf{C} that is associative when defined. If (f,g) is in the domain of \circ then there exists {}_f1_g in \mathbf{C} with f\circ{}_f1_g = f and g = {}_f1_g\circ g.