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: satisfying both axioms, of identity and associativity: The set End(E) = Mor(E,E) of endomorphisms of any object E, is a monoid.
An isomorphism between objects E and F is a morphism f∈Mor(E,F) that is invertible (∃g∈Mor(F,E), gf=1Efg=1F). This g is unique, called the inverse of f and written f -1.

A groupoid is a category where all morphisms are invertible. Groups are the groupoids with only one object, and the monoid of endomorphisms of any object of a groupoid is a group.
Generalizing from monoids, the core of a category is the groupoid with the same objects and only accepting isomorphisms as morphisms.
An automorphism of an object E, is an isomorphism from E to itself. Their set Aut(E), core of End(E), is a group called the automorphism group of E.

The concept of opposite category is defined similarly to opposite monoids, as re-reading the category with sides reversed, the Mor(A,B) of the one serving as the Mor(B,A) of the other.

Actions of categories

The concept of action is naturally generalized from monoids to categories: an action k gives for each object X a set kX, and for each f ∈ Mor(X,Y) a function kf : kXkY, preserving identities and compositions.
This gives back the concept of concrete category as a category with a chosen effective action (where effectiveness is defined by the injectivity of this function from Mor(X, Y), for all X, Y), to let Mor(X, Y) be identifiable with its image as a set of functions from kX to kY. Otherwise it defines a concrete category anyway, by

Mor(kX, kY) = {kf | f∈Mor(X,Y)}

Any object M in a category, naturally defines an action of this category by giving to any object E the set ME = Mor(M,E), and for any f ∈ Mor(E,F) let us take as Mf the function traditionally written (following wikipedia) Hom(M, f) : Mor(M,E) → Mor(M,F) defined by currying composition with other morphisms from X: let us denote

Hom(M, f) = (Mor(M,E)∋gfg), with target Mor(M,F) for any target F of f.

We get a concrete category MC image of C by Mor(MX, MY) = {Hom(M, f) | f∈Mor(X,Y)}. It involves quotienting each set of morphisms by the equivalence relation

f,g∈Mor(X,Y), Hom(M,f) = Hom(M,g) ⇔ ∀hMX, fh = gh.

Similarly we define a co-action by

Hom(f,X) = (Mor(F,X)∋ggf)

with target Mor(E, X). If we started from a concrete category as we initially conceived it, we may have to write it HomF(f, X) as f may not suffice to determine F.
The composition axioms satisfied by these actions and co-actions, are written: 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)

Qualities of morphisms

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.

Proof: if gf=1E then for all objects X, HomF(f,X) ০ HomE(g,X) = HomE(1E,X) = IdMor(E,X), thus 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).∎

A morphism f is an isomorphism if and only if Hom(X,f) : Mor(X,E) ↔ Mor(X,F); its inverse is then Hom(X, f -1).

In any category, Isomorphism ⇔ (Retraction ∧ Monomorphism) ⇔ (Section ∧ Epimorphism)
In concrete categories, Section ⇒ Injective morphism ⇒ Monomorphism
In categories of relational systems, Retraction ⇒ Quotient ⇒ Surjective morphism ⇒ Epimorphism

Representation theorem

Theorem. Any small category is isomorphic to that of all morphisms in a family of typed algebras.

The proof essentially repeats the formulas on acts as algebraic structures, transposed. From the given small category, a family of typed algebras is formed as follows. Each u ∈ Mor(E,F) acts as functions on each type i by Hom(i,u) : iEiF. These for all u and i define ψ : Mor(E,F) → FE, so that the system of these for all E, F respects identities and compositions (they form an action). Let us prove that ψ : Mor(E,F) ↔ MorL(E,F).
Im ψ ⊂ MorL(E,F) by associativity (ψ commutes with the action of L).
The existence of an isomorphism kiE ensures that ψ is injective (as k is epic) and MorL(E,F) ⊂ Im ψ:
g∈MorL(E,F), u = g(k)•k-1 ∈ Mor(E,F) ⇒ (∀xE, ∃sL, ks = xg(x) = g(ks) = g(k)•s = uks = ux) ⇒ g = ψ(u) ∎

In particular for any monoid M there is a language L of function symbols and an L-algebra X such that EndL X is isomorphic to M.
Any group is isomorphic to a permutation group, namely the group of automorphisms of an algebra.


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. Initial and final objects
3.9. Eggs, basis, clones and varieties
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry