# 3.7. Categories

Monoids were introduced as an abstraction of transformation monoids, which are concrete categories with one object. Generalizing this to pluralities of objects, a category (also called abstract category for insistence) differs from a concrete category, by forgetting that objects are sets and that morphisms are functions. It is made of:
• A class of "objects" of that category (which need not be sets); the category is small if this class is a set;
• to any objects A,B is given a set Mor(A,B) of «morphisms from A to B»; these are usually regarded as pairwise disjoint;
• to any object A is given 1A ∈ Mor(A,A);
• to any 3 objects A,B,C is given a composition operation we shall abusively denote by the same symbol • : Mor(B,C)×Mor(A,B)→Mor(A,C) ;
such that
• For any objects A,B, ∀x∈Mor(A,B), x•1A = x = 1Bx
• For any objects A,B,C,D, x∈Mor(A,B), ∀y∈Mor(B,C),∀z∈Mor(C,D), (zy)•x = z•(yx)
Generalizing isomorphisms in concrete categories, an isomorphism f between objects E and F in an abstract category, is an f∈Mor(E,F) such that ∃g∈Mor(F,E), gf=1Efg=1F. This g is unique, called the inverse of f and written f-1.

Again, an automorphism of an object E, is an isomorphism from E to itself. Their set Aut(E) is the group of invertible elements of the monoid End(E)=Mor(E,E).

Representation of small categories. Any small category has an interpretation as a family of typed algebras, with all morphisms between them.

Proof. Let us fix the set of types as a copy of the set of objects : from each object X we make a type X' (not giving any special status to this bijection).
See each object M as a system interpreting each type X' as the set Mor(X',M).
Take the language of function symbols where the set of those from type X' to type Y' is Mor(Y',X').
The proof goes on just like with monoids.∎

### Functions defined by composition

In any category, any f ∈ Mor(E,F) defines functions by currying composition with other morphisms to or from another object X: let us denote (almost following wikipedia but adapted to our concept of concrete category)
• Hom(X, f) = (Mor(X,E)∋gfg), with target Mor(X,F) for any target F of f.
• HomF(f, X) = (Mor(F,X)∋ggf), with target Mor(E, X). Simplified as Hom(f,X) in abstract categories where f determines F.
The former respects composition, while the latter reverses it: for any 4 objects E,F,G,X , ∀f ∈Mor(E,F), ∀g∈Mor(F,G),

Hom(X, g) ০ Hom(X, f) = Hom(X, gf)
HomF(f, X) ০ HomG(g, X) = HomG(gf, X)

The concepts of cancellativity and invertibility are generalized to categories as follows.

Monomorphism. In a category, a morphism f∈Mor(E,F) is called monic, or a monomorphism, if Hom(X,f) is injective for all objects X:

g,h∈Mor(X,E), fg = fhg = h.

Epimorphism. In an abstract category, a morphism f∈Mor(E,F) is called epic, or an epimorphism, if Hom(f,X) is injective for all objects X:

g,h∈Mor(F,X), gf = hfg = h.

In our concept of concrete category, we must specify F, saying f∈Mor(E,F) is F-epic, or an F-epimorphism, if all HomF(f,X) are injective.

In any concrete category, all injective morphisms are monic, and any morphism with image F is F-epic. However, the converses may not hold, and exceptions may be uneasy to classify, especially as the condition depends on the whole category.

Sections, retractions. When gf = 1E we say that f is a section of g, and that g is a retraction of f.

• A morphism f∈Mor(E,F) is a section (or section in F if the category is concrete), if 1E∈Im(HomF(f,E)), i.e. ∃g∈Mor(F,E), gf=1E.
Then f is monic and for all objects X we have Im(HomF(f,X)) = Mor(E,X).
• A morphism g∈Mor(F,E) is a retraction (or retraction on E if the category is concrete), if 1E∈Im(Hom(E,g)), i.e. ∃f∈Mor(E,F), gf=1E.
Then g is epic and for all objects X we have Im(Hom(X, g)) = Mor(X,F).
Proof: if gf=1E then for all objects X, HomF(f,X) ০ HomE(g,X) = HomE(1E,X) = IdMor(E,X), thus
• HomE(g,X) is injective (g is epic)
• h∈Mor(E,X), h = hgf = HomF(f,X)(hg).
Similarly, Hom(X,g) ০ Hom(X,f) = Hom(X,1E) = IdMor(X,E) thus f is monic and Im(Hom(X,g)) = Mor(X,F).∎

If f is an isomorphism then Hom(X,f) and Hom(X,g) are bijections, inverse of each other, between Mor(X,E) and Mor(X,F).

Any epic section is an isomorphism. Any monic retraction is an isomorphism.

### Initial and final objects

In any category, an object X is called an initial object if all sets Mor(X,Y) are singletons. Of course any object isomorphic to an initial object is also an initial object, as all isomorphic objects have the same properties. But conversely all initial objects (if they exist) are isomorphic, by a unique isomorphism between any two of them:
For any initial objects X, Y, ∃f∈Mor(X,Y), ∃g∈Mor(Y,X), gf ∈ Mor(X,X) ∧ 1X ∈ Mor(X,X) ∴ gf = 1X.
Similarly, fg = 1Y. Thus f is an isomorphism, unique because Mor(X,Y) is a singleton.∎
By this unique isomorphism, X and Y may be treated as identical to each other. Initial objects are said to be essentially unique.
Similarly, an object X is called a final object if all sets Mor(Y,X)) are singletons.
Such objects exist in many categories, but are not always interesting. For example, in any category of relational systems containing representatives (copies) of all possible ones with a given language:
• Singletons where relations are constantly true, are final objects in categories of one-type systems or algebras; for multi-type systems, final objects are made of one singleton per type.
• The empty set where Boolean constants are false is the initial object.
Exercise. Given two fixed sets K and B, consider the category where
• Objects are all (X,φ) where X is a set and φ: X×KB ;
• Mor((X,φ),(Y,φ') = {fYX | ∀aX,∀kK, φ(a,k) = φ'(f(a),k)}.
Does it have an initial object ? a final object ?

### Embeddings

In a concrete category C, let us pick an object E and any subset AE. If A is not given as an object of C (say, if objects were given as pairwise disjoint, "forgetting" the inclusion relations and the canonical injections between objects), can we add it there with its morphisms with other objects of C without modifying the rest of C ? In categories of relational systems, defining the structure of A by restricting to A the structures of E, we had
• IdA∈Mor(A,E)
• For any object N, Mor(N,A) = {h∈Mor(N,E) | Im hA}
• An f∈Mor(N,E) is an isomorphism to A when it is an embedding to E and Im f = A.
The category simply generated by the first two of these conditions would let Mor(A,N) be defined as {g|A | g∈Mor(E,N)}. However then, the last condition would make "embedding" equivalent to "section". Indeed, any section is an embedding in this sense, and for a given A, the existence of a section with image A implies the converse for other morphisms into A the equivalence between these conditions are equivalent if there, but otherwise they are not, in which case the {g|A | g∈Mor(E,N)} do not fit the concept of morphisms for any relational structure on A. Moreover only a restricted range of axioms on E were ensured to still hold on A in this way, while for example the property of being an algebra, was only satisfied by sub-algebras. So we need another definition of the concept of embedding to generalize it from categories of relational systems to any concrete category. For this, let us set as definitions the above properties found with relational systems.
namely copying that of K (to see A as isomorphic to K), first f needs to be injective (thus monic), then we need to specify A as a space. Problem : depending on the geometry, two injective morphisms f and g with Im f = Im g = A may disagree on the morphisms they give between A and other spaces in the sense of making both f and g isomorphisms.
Such disagreements could already occur in categories of relational systems.

Then let an injective f ∈ Mor(K,M) be called an embedding if it is a final object in the category defined as you can guess using A = Im f, so that its essential uniquess makes it coherent to declare f an isomorphism to A: for any space N,

{fg | g∈Mor(N,K)} = Mor(N,A).

Then the sets Mor(A,N) can be defined by transport of Mor(K,N) by this f. But in some geometries and choices of A, these might differ from {g|A|g∈Mor(M,N)}. For these to coincide, f has to be a section. Any section is an injective embedding. An advantage of the concept of section over that of embedding, is that its definition does not need checking the whole category.

From this, consider the category where

• Objects are all morphisms of C into A, we may conceive as (F, f) where F is an object of C, f∈Mor(F,E) and Im fA ;
• Mor((F, f),(G, g)) = {h∈Mor(F,G) | f = gh}
Final objects (F, f) of this category are called the embeddings of F onto A, as this characterizes embeddings as we defined them when C is a category of relational systems.

Dependencies between qualities of morphisms, can be mapped as follows:

Isomorphism ⇔ (Retraction ∧ Monomorphism) ⇔ (Section ∧ Epimorphism)
Retraction ⇒ Quotient ⇒ Surjective morphism ⇒ Epimorphism
Section ⇒ Embedding ⇒ Injective morphism ⇒ Monomorphism

### Categories of acts

From a concrete category C, let C' be the category where
• Objects are all (X,x) where X is an object of C and xX
• Mor((X,x),(Y,y)) = {f∈Mor(X,Y) | f(x)=y}.
Then we have
1. If C is the category of M-sets for a monoid (M,e, •) then, seeing M as an M-set interpreting • as left action, (M, e) is an initial object of C' ; initial objects are the (X,x) where x is a free and generating element of X.
2. Conversely, for any initial object (M,e) of C' (if that exists), there is a unique monoid structure (M,e,•) with an action on every other object X of C (beyond • on M itself), such that for all objects X, Y of C we have Mor(X,Y) ⊂ MorM(X,Y) and Mor(M,X) = MorM(M,X).
Proof. 1. by properties of acts as algebraic structures and inverses, as x is free and generating in X if and only if (X,x) is isomorphic to (M, e).
2. Defining ∀xX, hx ∈ Mor(M,X) ∧ hx(e) = x, provides an M-structure on each X which interprets each aM in X as defined by the tuple (e,a). So they are preserved: Mor(X,Y) ⊂ MorM(X,Y), which implies the axioms of M-acts.
The composition in M coming as this M-structure for M = X, satisfies the same axioms.
The last axiom of monoid, he = IdM comes from the uniqueness of he obeying its definition, and ensures the reverse inclusion:
g∈MorM(M,X), g = hg(e)g ∈ Mor(M,X). ∎
This monoid (M,e,•) is essentially the opposite of the monoid End(M). Indeed for all a, bM we have ha ∈ End(M), hb ∈ End(M) and hahb(e) = ha(b) = ba.

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Morphisms of relational systems and concrete categories
3.2. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Algebraic terms
3.9. Term algebras
3.10. Integers and recursion
3.11. Presburger Arithmetic
4. Model Theory