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

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

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 on each type t by Hom(t,u) : tEtF. These for all u and t define f : Mor(E,F) → FE, so that the system of these for all E, F respects identities and compositions (they form an action in a sense generalized from monoids to small categories). Let us prove that f : Mor(E,F) ↔ MorL(E,F).
Im f ⊂ MorL(E,F) by associativity (f commutes with the action of L).
The existence of an isomorphism ktE ensures that f is injective (as k is epic) and MorL(E,F) ⊂ Im f:
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 = f(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. Algebraic terms
3.10. Term algebras
3.11. Integers and recursion
3.12. Presburger Arithmetic
4. Model Theory