3.7. Categories

Categories (also called abstract categories for insistence) differ from concrete categories, by forgetting that objects are sets (ordered by inclusion) and that morphisms are functions. The concept of monoid was the particular case of an abstract category with only one object. The general case of categories is similarly formalized as the data of: satisfying the axioms The concept of isomorphism in abstract categories generalizes both the one in concrete categories (as seen equivalent) and invertible elements in monoids : for any objects E to F, an isomorphism f from E to F is an f∈Mor(E,F) such that ∃g∈Mor(F,E), gf=1Efg=1F.

Like in monoids, the inverse of any isomorphism (= invertible morphism) is unique.

Representation theorem. Any small category can be interpreted as that of all morphisms in some given list of typed algebras.
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 to this bijective correspondence any special status).
Each object M is interpreted as a system where each type X' is interpreted as the set Mor(X',M).
As a language, let us take all morphisms between types: the set of function symbols from type X' to type Y' is defined as Mor(Y',X') (with reverse order, as symbols act on the right).
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)
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.

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: we say that 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).∎

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.

These dependencies between qualities of morphisms, can be mapped as follows:

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

Initial and final objects

In any category, an object X is called an initial object (resp. a final object) if for all objects Y the set Mor(X,Y) (resp. Mor(Y,X)) is a singleton.
Such objects have this remarkable property: when they exist, all such objects are isomorphic, by a unique isomorphism between any two of them.

Proof: For any initial objects X and Y, ∃f∈Mor(X,Y), ∃g∈Mor(Y,X), gf ∈Mor(X,X) ∧ fg ∈ Mor(Y,Y).
But 1X ∈ Mor(X,X) which is a singleton, thus 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. We say that an initial object is essentially unique.
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: Exercise. Given two fixed sets X and Y, consider the category whose objects are all (E,φ) where E is a set and φ: E×XY, and the morphisms from (E,φ) to (E',φ') are all f : EE' such that ∀aE,∀xX, φ(a,x) = φ'(f(a),x).
Does it have an initial object ? a final object ?

Categories of acts

From a concrete category C, let C' be the category where Then we have
  1. If C is the category of M-sets for a monoid (M,e, •) then (M, e) is an initial object of C' (when seen as acting on itself by •); initial objects are the (X,x) where x is a free and generating element of X.
  2. Conversely, if C' has an initial object (M, e) then we can use e to define a binary operation on M making it a monoid with neutral element e acting on all objects of C, and all morphisms of C are M-morphisms between these M-sets (but there may exist other M-morphisms from objects other than M)
These are direct consequences of the remark on monoid acts.
For 2., the composition in M is defined as the particular case of the M-algebra structure on M satisfying axioms of M-acts.
The monoid M can be seen as a transposed copy of the monoid End(M). Indeed for all a, bM, ha, hb∈End(M) and ha(hb(e))=ha(b)=ba.
The preservation of these interpreted function symbols, letting morphisms of C remain M-morphisms, is a particular case of preservation of relations defined by tuples.
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 and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory