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: 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).

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

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 X in a category, naturally defines an action of this category by giving to any object E the set XE = Mor(X,E), and for any f ∈ Mor(E,F) let us take as Xf the function traditionally written (following wikipedia) Hom(X, f) : Mor(X,E) → Mor(X,F) defined by currying composition with other morphisms from X: let us denote

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

The resulting concrete category 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