3.8. Properties in categories

Monomorphisms, Epimorphisms

The concepts of cancellativity are generalized to any category C as follows.

A morphism f∈Mor(E,F) is called monic, or a monomorphism, if all f(X) are injective:

CX, ∀g,h∈Mor(X,E), fg = fhg = h.

In the category of sets, monomorphisms are the injections.

Dually, a morphism f∈Mor(E,F) is called epic, or an epimorphism, if all f(X) are injective :

CX, ∀g,h∈Mor(F,X), gf = hfg = h
CX, f(X) : F(X)E(X)
f(C) : C(F)C(E).

As actions by composition on opposite sides commute, an epimorphism f defines a meta-embedding between acting categories C(F) and C(E), seen as C-typed Mor-algebras. In particular, f is a free element of the End(F)-set F(E).
In the category of sets, epimorphisms are the surjections.

Sections, retractions

The concepts of invertibility are generalized to any category C as follows. For any f∈Mor(E,F) and g∈Mor(F,E), the condition f;g = 1E is read: "f is a section of g", or "g is a retraction of f".
Then a g∈Mor(F,E) is called a retraction (or retraction on E if the category is concrete), if, equivalently
1. f∈Mor(E,F), f;g = 1E
2. For any action α of C, gα is surjective (Im gα = Eα).
3. g(E) is surjective, i.e. Im g(E) = End(E).
Proof.
1. ⇒ 2. : ∀xEα, x = gα(fα(x)), i.e. right invertible functions are surjective.
2. ⇒ 3. obvious;
3. ⇒ 1. as 1E ∈ Im g(E).∎

Dually, f∈Mor(E,F) is a section (or section in F if the category is concrete), if, equivalently,

1. g∈Mor(F,E), f;g = 1E.
2. For any co-action β of C, fβ is surjective (Im fβ = Eβ).
3. f(E) is surjective, i.e. Im f(E) = End(E).
Since left invertible functions are injective,
• All actions of sections are injective; thus, all sections are monic;
• All co-actions of retractions are injective; thus, all retractions are epic.
Gathering the results, the qualities of morphisms in concrete categories are ordered as

Section ⇒ Injective morphism ⇒ Monomorphism
Retraction ⇒ Surjective morphism ⇒ Epimorphism

Modules

For any b∈Mor(X,Y), an object M will be called a b-module if b(M) : Y(M)X(M).

If b is an isomorphism then all objects are b-modules, i.e. b is an epic section, and

CX, (b(M)-1 = b-1(M)) ∧ (b(M) -1 = b-1 (M)).

Conversely, if b is a section and b(Y) is injective then b is an isomorphism.
Proof : ∃g∈Mor(Y,X), b;g = 1Xb;g;b = 1X;b = b;1Yg;b = 1Y.∎

Thus :

• If both X,Y are b-modules then all other objects are also b-modules ;
• Epic section ⇔ Isomorphism ⇔ Monic retraction ;
• If an element of a monoid is both left invertible and right cancellative, then it is invertible.
To say Y is a b-module, is another way of saying b is a regular element of the End(Y)-set X(Y). Yet b(Y) being an End(Y)-isomorphism from Y(Y) to X(Y), does not ensure its inverse to come as g(Y) for some g∈Mor(Y,X), such as an inverse of b if it was an isomorphism in C.

Examples of modules

The concept of b-module will be more often used when b is epic, thus distinguishing the M such that the injection b(M) is also surjective (while not all objects are b-modules, i.e. b is not a section, i.e. X is not a b-module). In particular, for any algebraic language L, if 〈Im bL = Y then b is epic in any category included in that of partial L-algebras.

An important kind of examples is when b is bijective (and thus epic), in the category of relational systems for a given language L. To simplify, let b be the identity IdX into Y with larger structure Y = XZ.

For example, given a binary symbol rL, the properties of reflexivity, symmetry and transitivity of the interpretation of r in a system M, are respectively expressible as M being a Re-module, a Sy-module and a Tr-module, where the morphisms Re, Sy and Tr are respectively defined by

• (Re) : X = {0}, X = ∅, Z = {(r,(0,0))}
• (Sy) : X = {0,1}, X = {(r,(0,1))}, Z = {(r,(1,0))}
• (Tr) : X = {0,1,2}, X = {(r,(0,1)), (r,(1,2))}, Z = {(r,(0,2))}
Similarly, antisymmetry is expressible as being a module by a non-injective morphism.

So formalized, this general case of a bijective b can be thought of as giving Z the role of a set of L-typed X-ary algebraic symbols, which for every set M gives to LM the Z-structure {((s,Lu|X),Lu(s)) | (s,u) ∈ Z×MX}, so that

(M, M) is a b-module ⇔ M ∈ SubZ LM.

More examples will be given in 3.11.

Subobjects

With our initial concept of concrete category allowing for inclusion between objects, we need to write HomY(f, X) as f may not suffice to determine Y. From there, more concepts also need this parameter:
• The anti-preservation of ⚬ by C(X) is written HomF(f, X) ⚬ HomG(g, X) = HomG(gf, X).
• f∈Mor(E,F) is F-epic, or an F-epimorphism, if all HomF(f,X) are injective.
In any concrete category, any injective morphism is monic, and any morphism with image F is F-epic. The converses may hold or not depending the considered concrete category.

Let us analyze the concept of an object S being included in an object E of a concrete category, to re-express it as a separate object X with an isomorphism to S (by which references to target sets of morphisms could be omitted). This concept has 2 variants.

The "weak" version is the concept of subobject (by the standard terminology), applicable to any abstract category. It amounts to only requiring the inclusion morphism of the subobject S in E (usually IdS : SE in concrete categories) to be monic, and not even necessarily injective.

Namely, a subobject of E is formalized by a presentation in the form (X,u) where u ∈ Mor(X,E) is monic (indirect description of Im u seen as isomorphic to X, thus defining the morphisms to and from Im u as copied from those X, but this direct meaning is lost in abstract categories).
The class of presentations (X,u) of subobjects of an object E, is meta-preordered by

(X, u) ⊆ (Y, v) ⇔ ∃ϕ∈Mor(X,Y), u = v∘ϕ

while (!ϕ∈Mor(X,Y), u = v∘ϕ) because v is monic.
Then, ϕ is also monic because u is :

g,h∈Mor(Z,X), ϕ∘g = ϕ∘hug = v∘ϕ∘g = v∘ϕ∘h = uhg = h.

Such (X, u) and (Y, v) are said to present the same subobject if they are equivalent for this meta-preorder :

(X, u) ≡ (Y, v) ⇔ ((X, u) ⊆ (Y, v) ∧ (Y, v) ⊆ (X, u)) ⇔ (∃ϕ∈Iso(X,Y) | u = v∘ϕ).

Between subobjects of a given object, the order ⊆/≡ is called inclusion.

The "strong" version requires u to be an embedding. This concept of embedding, first introduced for relational systems in 3.4, will be generalized to any concrete category in 3.9 (while expressible classes of monomorphisms in abstract categories which may play a similar role are not equivalent).

Representation theorem

Theorem. Any small category is isomorphic to one made of a family of typed algebras with all morphisms between them.

Its precise construction forms the small category version of Yoneda’s embedding (which expresses it at the meta level: any category is isomorphic to a category of typed meta-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.
• As a set T of types, we can take a copy of the set of objects, but one type per isomorphism class suffices.
• Each object E is interpreted as a typed set ∐tT E(t).
• L = ∐t,t'T Mor(t',t) seeing Mor(t',t) as a set of functions symbols from t to t', co-acting on each E.
Each u ∈ Mor(E,F) acts as ψ(u) = ∐tT jtu(t) : ∐tT E(t) → ∐tTF(t).
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 kE(t) ensures that ψ is injective (as k is epic) and MorL(E,F) ⊂ Im ψ:
g∈MorL(E,F), (∀xE, g(x) = g(kk-1x) = g(k)∘k-1x) ∴ g = ψ(g(k)∘k-1).∎

In particular,

• any monoid is isomorphic to the monoid of endomorphisms of an algebra on a language of function symbols;
• any group is isomorphic to an automorphism group of such an algebra.
Yet, not all categories can be concrete.

Notice the symmetry of roles (called duality) between sides, which not only switches the orientation of morphisms between two objects, but also lets a category be somehow reworded as a special kind of mathematical theory (so viewing category theory as a weak version of one-theory theory, despite contextual differences):

• "Objects" in categories become "types",
• "Morphisms" become "invariant functions", implicitly generated by a language of function symbols only.
The weakness of that kind of "theory" is balanced by the development of concepts at a meta level above it. This symmetry leads to diverse insights:
• An epimorphism b ∈ Mor(X,Y) gives to Y a role of sub-type of X, so that a b-module is an object whose component of type X is filled by Y.
• To link both concepts of invariance : for any monoid M (resp. small category) generated by a set thought of as a language of (typed) function symbols (so M is made of functions expressible as terms in this language), there exists a (set I of) algebraic interpretation(s), i.e. actions, where M coincides with the category M' of all functions (resp. interpreted function symbols) which are invariant by all endomorphisms (resp. by all morphisms between interpretations in I). Anyway in any interpretation, the concrete image of M is included in the corresponding M', because the set M' of invariant functions by any given set of functions is (Id, ⚬)-stable (this can be dually rephrased by qualifying M' as the set of morphisms there).
A reference of book chapter by George M. Bergman presenting such concepts of category theory in more traditional terms: an old version; the new version is chapter 8 of his book.
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry

Other languages:
FR : Propriétés dans les catégories