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),
f∘g = f∘h ⇒ g = 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),
g∘f = h∘f ⇒ g = 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
- ∃f∈Mor(E,F), f;g = 1E
- For any action α of C, gα is surjective
(Im gα = Eα).
- g(E) is surjective, i.e.
Im g(E) = End(E).
Proof.
1. ⇒ 2. : ∀x∈Eα,
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,
- ∃g∈Mor(F,E), f;g = 1E.
- For any co-action β of C, fβ is surjective
(Im fβ = Eβ).
- 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 = 1X ∴
b;g;b = 1X;b = b;1Y
∴ g;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 b〉L = 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 = X
∪ Z.
For example, given a binary symbol r∈L, 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(g∘f, 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 :
S ↪ E 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 = ϕ∘h ⇒ u∘g = v∘ϕ∘g = v∘ϕ∘h = u∘h
⇒ g = 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 ∐t∈T
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) = ∐t∈T
jt ⚬ u(t) :
∐t∈T E(t) →
∐t∈TF(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 k ∈ E(t) ensures that
ψ is injective (as k is epic) and
MorL(E,F) ⊂ Im ψ:
∀g∈MorL(E,F),
(∀x∈E, g(x) = g(k∘k-1∘x) =
g(k)∘k-1∘x)
∴ 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