3.9. Initial and final objects
In any category, an object X is called an initial object if all
Mor(X,Y) are singletons. While isomorphic objects have all the same
properties, here is a small converse : any 2 initial objects are isomorphic, by a unique
isomorphism (so, initial objects form either a single isomorphism class, or none):
For any initial objects X, Y, ∃f∈Mor(X,Y),
∃g∈Mor(Y,X), {g∘f, 1_{X}} ⊂ Mor(X,X)
∴ g∘f = 1_{X}.
Similarly, f∘g = 1_{Y}.
Thus f is an isomorphism, unique as ∃!:Mor(X,Y). ∎
By this unique isomorphism, X and Y may be treated as identical to
each other. Initial objects are said to be essentially unique.
Dually, an object X is called a final object if all Mor(Y,X) are
singletons.
For example, in any category of relational systems with a given language
where every isomorphism class of possible systems has representatives :
 The empty set where Boolean constants are false is the initial system ;
 Final systems (with a single type) are the singletons where all relations are constantly true;
 Final multitype systems are made of one singleton per type.
Exercise. Given two fixed sets A and B, consider the category where
 Objects are all (X,ϕ) where X is a set and ϕ: X×A→B ;
 Mor((X,ϕ),(Y,ϕ') = {f∈Y^{X} 
∀x∈X,∀a∈A, ϕ(x,a) = ϕ'(f(x),a)}.
Does it have an initial object ? a final object ?
Eggs
(This is called universal element
in the literature; I use the name "egg" to fit with that of clone.)
Generalizing the concept of regular
element, let us call egg of an acting category C^{α}, any
(M,e) where M is an object and e ∈ M^{α}, such that
∀_{C}E, (Mor(M,E) ∋ f ↦
f^{α}(e)) : E^{(M)} ↔ E^{α}.
Equivalently, it is an initial object of the category of elements of C^{α} where
 Objects are all data (E,x) of
an object E of C and x ∈ E^{α}
 Mor((E,x),(F,y)) =
{f∈Mor(E,F)  f^{α}(x) = y}
Dually, a coegg of a coacting category C_{β} is an egg of the
opposite acting category, i.e. a final object of its category of coelements (E,x)
where x ∈ E_{β} and Mor((E,x),(F,y)) =
{f∈Mor(E,F)  f_{β}(y) = x}.
Again, an action (resp.coaction) will be called regular if it has an egg (resp. a coegg); it
is called representable elsewhere
in the literature.
If (M,e) is an egg of C^{α} then (M^{α},e)
is an egg of C^{α}.
For any object M of C, (M, 1_{M}) is an egg of
C^{(M)} and a coegg of C_{(M)}.
In the literature (wikipedia), a category
of elements of some C^{(M)} is called an undercategory and denoted
M/C, while a category of coelements of some C_{(M)}
is called an overcategory and denoted C/M.
Yoneda's lemma
can be expressed in our terminology as follows : if (M,x) is a (co)egg of a
(co)action α of a category C, then (α,x) is an egg of the action on M
of the metacategory of all (co)actions of C.
Precisely, for any object M, any action β of C and any
x∈M^{β}, the unique metamorphism ϕ from
C^{(M)} to C^{β} such that
ϕ_{M}(1_{M}) = x is defined by
∀_{C}E,
∀y∈E^{(M)},
ϕ_{E}(y) = y^{β}(x)
Proof of (metamorphism ⇒ defining formula): ϕ_{E}(y) =
ϕ_{E}(y∘1_{M})
= y^{β}(ϕ_{M}(1_{M}))
= y^{β}(x).
The proof of the converse is as easy and left to the reader.
When (M,x) is an egg, this gives a metaisomorphism
(like any bijective morphism between algebras is an isomorphism). ∎
Obviously, the image of ϕ is the trajectory of x in C^{β}.
Exercise. Consider the category of sets and their functions
acting by direct images on the powersets of its objects (Set^{⋆}). Does it have an egg ?
Similarly, consider its coaction on these powersets by preimages (Set_{⋆}). Does it have a coegg ?
Hint : use the numbers of elements of involved finite sets.
Subobjects as subcoactions
Any f∈Mor(E,F) defines by composition a metamorphism
f^{(C)} from C_{(E)} to
C_{(F)}, which is injective precisely when f is monic.
Any presentation (E,f) of a subobject of F is also a coegg of the
subcoaction Im f^{(C)} of C_{(F)}.
Inversely, any subcoaction of C_{(F)} with a coegg
(E,f) is the trajectory of (E,f) and metaisomorphic to
C_{(E)} by f^{(C)}, and f is monic
from E to F.
So, the notion of subobject of F can be redefined as that of a regular
subcoaction of C_{(F)}, whose coeggs are its presentations.
So conceived, it becomes strictly independent of a choice of presentation (but
ontologically more expensive).
Diverse operations usually involving subsets, such as direct images and preimages by
morphisms, can be extended to subobjects, by literally applying them to subcoactions,
then presenting the resulting subcoaction as a subobject if it is regular. This regularity
condition often holds depending on the category, and can be verified in diverse kinds of
categories, especially categories of systems, by explicitly describing the result as a subsystem.
Things especially works like this for the operation of preimage.
Strictly applying this method, the direct image of a subobject of E with
presentation (X,u) by an f∈Mor(E,F), would be
given by the trajectory Im f∘u^{(C)} of
(X,f∘u) in C_{(F)},
and thus presented by f∘u if it is monic. In particular, this holds when
f is itself monic.
However, many categories of systems have a construction of direct images of subsystems
which remains naturally applicable even when that image trajectory fails to be regular (a simple
example can be found in the category of relational systems with 2 unary relation symbols).
Such a direct image can still be characterized in terms of pure categories, as the subobject
generated by f∘u, i.e. the smallest regular subcoaction which contains it.
Embeddings in concrete categories
While the concepts of embedding
and preembedding were introduced for
categories of relational systems, let us generalize them to any concrete category C.
A morphism f ∈ Mor(E,F) will be called a preembedding
if ∀_{C}X, Mor(X,E) =
{g∈E^{X}  f⚬g ∈ Mor(X,F)}
This formula actually implies f∈Mor(E,F).
In other words, while f∈Mor(E,F) makes (E, Id_{E})
an element of the coaction giving to
each X the set {g∈E^{X}  f⚬g ∈ Mor(X,F)} (subcoaction of C_{E}),
f is a preembedding when (E, Id_{E}) is a generator and thus
also a coegg of this coaction.
Then, an embedding is an injective preembedding, i.e. an
f : E ↪ F such that, equivalently
∀_{C}X, Mor(X,E) =
{f^{ 1}⚬h  h ∈ Mor(X,F) ∧
Im h ⊂ Im f}
∀_{C}X,
{h ∈ Mor(X,F) 
Im h ⊂ Im f} = {f⚬g  g∈Mor(X,E)}
Let us introduce a related concept.
Any fixed subset A ⊂ F defines a subcoaction
C_{(A)} of C_{(F)} by
∀_{C}X, X_{(A)} =
{g∈X_{(F)}  Im g ⊂ A}
Now let us call quasiembedding any f∈Mor(E,F) such that
(E,f) is a coegg of some C_{(A)} and thus also of C_{(Im f)} :
∀_{C}X, ∀g∈Mor(X,F), Im g ⊂ Im f ⇒
∃!ϕ∈Mor(X,E), f ⚬ ϕ = g
(Inj f implies one side of this condition: ∀g∈Mor(X,F),
!ϕ∈Mor(X,E), f ⚬ ϕ = g)
In most
useful concrete categories, all quasiembeddings will be
embeddings ; exceptions are easy to build in other categories designed for this purpose.
Dependencies between some properties of morphisms
The diverse properties of a morphism f∈Mor(E,F) in a concrete category
C, are related as follows.
 If Im f ⊂ A ⊂ F then
((E,f) is coegg of C_{(A)}) ⇔ (f is a quasiembedding and
∀g∈Mor(E,F), Im g ⊂ A ⇒ Im g ⊂ Im f)
 Injection ⇒ (preembedding ⇔ quasiembedding)
 Quasiembedding ⇒ monomorphism
 (Monomorphism ∧ preembedding) ⇒ injection
 Section ⇒ embedding
Proofs. ∀x∈E, ϕ = (E∋y ↦ (f(y) = f(x) ?
x : y)) ⇒ f ⚬ ϕ = f ⇒ (ϕ ∈ End E ∴ ϕ = Id_{E}).

∃h∈Mor(F,E), h ⚬ f = 1_{E} ∴
∀g∈E^{X}, f ⚬ g ∈ Mor(X,F) ⇒
g = h ⚬ f ⚬ g ∈ Mor(X,E).∎
Let f∈Mor(E,F) a quasiembedding.
If there exists a preembedding g∈Mor(X,F) with the same image Im g = Im
f = A ⊂ F and
AC_{A} holds then f is an embedding.
Proof.
∃h∈X^{A}, g⚬h = Id_{A} ∴
g⚬h⚬f = f ∈ Mor(E,F) ∴ h⚬f
∈ Mor(E,X)
∃ϕ∈Mor(X,E), f⚬ϕ = g ∴ f⚬ϕ⚬h⚬f
= g⚬h⚬f = f ∴ ϕ⚬h⚬f = Id_{E}.∎
A subobject (X,u) of E will be qualified as embedded
(resp. quasiembedded) if u is an
embedding (resp. a quasiembedding) from X to E. This does not depend
on the choice of presentation of a given subobject.
If a subset A of an object F is the image of an embedding f∈Mor(E,F), this gives
A the status of an embedded subobject (A, Id_{A}) ≡ (E,f).
(For a quasiembedding we can do similarly with a copy of E attached to A and thought of
as independent of E).
Then for any object X, we can define Mor(X,A) from Mor(X,F)
directly as X_{(A)}, while Mor(A,X) is only directly defined
from Mor(F,X) if f is a section, as {g_{A} 
g∈Mor(F,X)}.
Equalizers
The equalizer
Eq(f, g) ⊂ E of any two functions f,g with domain
E, was defined in 3.3; it was noticed to be a subalgebra when f,g
are morphisms in a category of algebras.
The more general concept of equalizer Eq(f, g) of
f,g∈Mor(E,F) in any category C, means the subobject
of E defined by the subcoaction C_{(f=g)} of
C_{(E)} where
∀_{C}X, X_{(f=g)} =
{h∈X_{(E)}  f∘h = g∘h}
(if it is regular; it is anyway a subcoaction by stability of equalizers)
In any concrete category, all equalizers are quasiembedded subobjects,
since X_{(f=g)} = X_{(Eq(f, g))}
where Eq(f, g) ⊂ E is the equalizer of the functions
f, g in the category of sets.
Any section f∈Mor(E,F) is an equalizer: if
g∈Mor(F,E) and g∘f = 1_{E}
then f is an equalizer of (1_{F}, f∘g).
Submodules
For any b∈Mor(X,Y), let us call bsubmodule of an
object F, any subobject (E,f) of F such that E
is a bmodule.
Equivalently, ∀h∈Mor(X,E),
∃!j∈Mor(Y,E), f∘j∘b = f∘h
When F is itself a bmodule, ∃!g∈Mor(Y,F),
g∘b = f∘h
and the submodule condition becomes equivalent to each of
 ∀k∈ Im f^{(X)}, ∃g∈
Im f^{(Y)}, g∘b = k

∀g∈Mor(Y,F), g∘b∈ Im f^{(X)}
⇒ g∈Im f^{(Y)}
This is a stability condition on Im f^{(C)}, namely
b_{(F)}^{1}[Im
f^{(X)}] ⊂ Im f^{(Y)}.
Even if F is not a bmodule, the formula 2.
(no more equivalent to other conditions) is still a stability condition on
Im f^{(C)}, namely by the transpose of Gr
b_{(F)}.
It holds in particular if b is epic and f is an equalizer (precisely, when
f is an equalizer of a pair in Mor(F,G) and
b_{(G)} :
Y_{(G)} ↪ X_{(G)}).
Let us apply this stability concept to the case of quasiembedded subobjects in a concrete category:
a subset A of an object F will be called
bstable if b_{(F)⋆}(X_{(A)})
⊂ Y_{(A)}, or more explicitly
∀g∈Mor(Y,F), Im g⚬b ⊂ A ⇒
Im g ⊂ A
In particular:  In any category made of Lsystems for some algebraic language L,
for any b∈Mor(X,Y) such that 〈Im b〉_{L} = Y,
 any Lstable subset is bstable;
 in particular, any Lstable subset of a bmodule is a bmodule.
 If b is surjective then all subsets of objects are bstable.
For any bmodule F and f∈ Mor(E,F),
 If f is a preembedding and b is bijective then E is a bmodule;
 If f is a quasiembedding and Im f is bstable then
(E,f) is a bsubmodule.
Proofs:
 ∀u∈Mor(X,E), f⚬u⚬b^{1} ∈
Mor(Y,F) ∴ u⚬b^{1}∈Mor(Y,E).
 ∀u∈Mor(X,E), (∃!g∈Mor(Y,F),
g⚬b = f⚬u ∴ Im g ⊂ Im f)
∴ (∃!h∈Mor(Y,E), f⚬h⚬b = f⚬u)
∴ (∃!h∈Mor(Y,E), h⚬b = u).∎
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and firstorder foundations
5. Secondorder foundations
6. Foundations of Geometry
Other languages:
FR : 3.9.
Objets initiaux et finaux