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 In an abstract category, for any objects E and F, an isomorphism f from E to F is an f∈Mor(E,F) such that ∃g∈Mor(F,E), gf=1Efg=1F. This g is unique, called the inverse of f. (This generalizes both isomorphisms in concrete categories, and invertible elements in monoids)

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.
When they exist, all such objects 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. 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 K and B, consider the category where 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, 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. see properties of acts as algebraic structures and inverses.
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 results from IdM∈Mor(M,M) 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, ha, hb∈End(M) and ha(hb(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 and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory