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:
- A class of "objects" of that category, regarded as pure elements (ignoring any inclusion order); the category is
called small if this class is a set;
- Between any two objects A,B is given a set Mor(A,B); these are regarded
as pairwise disjoint sets of pure elements;
- To any object A is given an element 1A∈Mor(A,A)
- To any 3 objects A,B,C is given a
composition operation we shall abusively denote by the same
symbol • : Mor(B,C)×Mor(A,B)→Mor(A,C)
satisfying the axioms
Representation theorem. Any small category can be interpreted
as that of all morphisms in some given list of typed algebras.
- For any objects A,B, ∀x ∈Mor(A,B),
x •1A = x = 1B•x
- For any objects A,B,C,D, ∀x∈Mor(A,B),∀y∈Mor(B,C),∀z
∈Mor(C,D), (z•y)•x = z•(y•x)
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, f) = (Mor(X, Dom
with target Mor(X,F) for any target F of f.
- HomF(f, X) = (Mor(F,
X)∋g↦ g০f), with target
Mor(E, X). Simplified as Hom(f,X) in abstract
categories where f determines F.
Hom(X, g) ০ Hom(X, f) =
HomF(f, X) ০
HomG(g, X) =
Monomorphism. In a category, a morphism
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০f=h০f ⇒ g=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
The following 2 concepts may be considered cleaner as they admit
a local characterization:
Sections, retractions. When g০f=IdE we say that f
is a section of g, and that g is a retraction of f.
Proof: if g০f=IdE then for all objects X,
HomF(f,X) ০ HomE(g,X)
= IdMor(E,X), thus
- A morphism f∈Mor(E,F) is a section
(or section in F if the category is concrete), if
i.e. ∃g∈Mor(F,E), g০f=IdE.
Then f is monic and for all objects X we have
Im(HomF(f,X)) = Mor(E,X).
A morphism g∈Mor(F,E)
is a retraction (or retraction on E if the
category is concrete), if IdE∈Im(Hom(E,g)),
i.e. ∃f∈Mor(E,F), g০f=IdE.
Then g is epic and for all objects X we have
Im(Hom(X, g)) = Mor(X, F).
Similarly, Hom(X,g) ০ Hom(X,f) =
Hom(X,IdE) = IdMor(X,E) thus
f is monic and Im(Hom(X,g)) = Mor(X,F).∎
- HomE(g,X) is injective (g is epic)
- ∀h∈Mor(E,X), h =
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 f∈Mor(E,F) is an isomorphism
: g০f=IdE ⇒ f০g০f
= IdF০f ⇒ f০g=IdF
Similarly, 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
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
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), g০f ∈Mor(X,X)
∧ f০g ∈Mor(Y,Y).
By this unique isomorphism, X and Y may be treated as identical to
each other. We say that an initial object is essentially unique.
But IdX ∈ Mor(X,X) which is a
singleton, thus g০f= IdX.
Thus f is an isomorphism, unique because Mor(X,Y)
is a singleton.∎
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×X→Y, and the morphisms from (E,φ) to (E',φ')
are all f : E→E' such that ∀a∈E,∀x∈X,
φ(a,x) = φ'(f(a),x).
- Singletons are final objects (where all relations are
constantly true); and also in any category of algebras
with a fixed language where they are admitted as objects. In the case of multi-type systems, final
objects are made of one singleton per type.
- The only initial object is the empty set (where any nullary
relation, i.e. boolean constant, is false).
Does it have an initial object ? a final object ?
Set theory and foundations
1. First foundations of
2. Set theory (continued)
3. Algebra 1
of relational systems and concrete categories
4. Model Theory
3.3. Special morphisms
3.5. Actions of monoids
3.7. Algebraic terms and term algebras
3.8. Integers and recursion
3.9. Arithmetic with addition