## 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), {gf, 1X} ⊂ Mor(X,X) ∴ gf = 1X.
Similarly, fg = 1Y. 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 multi-type 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×AB ;
• Mor((X,ϕ),(Y,ϕ') = {fYX | ∀xX,∀aA, ϕ(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 eMα, such that

CE, (Mor(M,E) ∋ ffα(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 xEα
• Mor((E,x),(F,y)) = {f∈Mor(E,F) | fα(x) = y}
Dually, a co-egg of a co-acting category Cβ is an egg of the opposite acting category, i.e. a final object of its category of co-elements (E,x) where xEβ and Mor((E,x),(F,y)) = {f∈Mor(E,F) | fβ(y) = x}.
Again, an action (resp.co-action) will be called regular if it has an egg (resp. a co-egg); 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, 1M) is an egg of C(M) and a co-egg 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 co-elements 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 meta-category of all (co-)actions of C.
Precisely, for any object M, any action β of C and any xMβ, the unique meta-morphism ϕ from C(M) to Cβ such that ϕM(1M) = x is defined by

CE, ∀yE(M), ϕE(y) = yβ(x)

Proof of (meta-morphism ⇒ defining formula): ϕE(y) = ϕE(y∘1M) = yβM(1M)) = yβ(x).
The proof of the converse is as easy and left to the reader.
When (M,x) is an egg, this gives a meta-isomorphism (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 co-action on these powersets by preimages (Set). Does it have a co-egg ?
Hint : use the numbers of elements of involved finite sets.

### Subobjects as sub-co-actions

Any f∈Mor(E,F) defines by composition a meta-morphism 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 co-egg of the sub-co-action Im f(C) of C(F).
Inversely, any sub-co-action of C(F) with a co-egg (E,f) is the trajectory of (E,f) and meta-isomorphic to C(E) by f(C), and f is monic from E to F.
So, the notion of subobject of F can be re-defined as that of a regular sub-co-action of C(F), whose co-eggs 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 sub-co-actions, then presenting the resulting sub-co-action 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 fu(C) of (X,fu) in C(F), and thus presented by fu 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 fu, i.e. the smallest regular sub-co-action which contains it.

### Embeddings in concrete categories

While the concepts of embedding and pre-embedding 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 pre-embedding if

CX, Mor(X,E) = {gEX | fg ∈ Mor(X,F)}

This formula actually implies f∈Mor(E,F).

In other words, while f∈Mor(E,F) makes (E, IdE) an element of the co-action giving to each X the set {gEX | fg ∈ Mor(X,F)} (sub-co-action of CE), f is a pre-embedding when (E, IdE) is a generator and thus also a co-egg of this co-action.

Then, an embedding is an injective pre-embedding, i.e. an f : EF such that, equivalently

CX, Mor(X,E) = {f -1h | h ∈ Mor(X,F) ∧ Im h ⊂ Im f}
CX, {h ∈ Mor(X,F) | Im h ⊂ Im f} = {fg | g∈Mor(X,E)}

Let us introduce a related concept. Any fixed subset AF defines a sub-co-action C(A) of C(F) by

CX, X(A) = {gX(F) | Im gA}

Now let us call quasi-embedding any f∈Mor(E,F) such that (E,f) is a co-egg of some C(A) and thus also of C(Im f) :

CX, ∀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 quasi-embeddings 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.
1. If Im fAF then
((E,f) is co-egg of C(A)) ⇔ (f is a quasi-embedding and ∀g∈Mor(E,F), Im gA ⇒ Im g ⊂ Im f)
2. Injection ⇒ (pre-embedding ⇔ quasi-embedding)
3. Quasi-embedding ⇒ monomorphism
4. (Monomorphism ∧ pre-embedding) ⇒ injection
5. Section ⇒ embedding
Proofs.
1. xE, ϕ = (Ey ↦ (f(y) = f(x) ? x : y)) ⇒ f ⚬ ϕ = f ⇒ (ϕ ∈ End E ∴ ϕ = IdE).
2. h∈Mor(F,E), hf = 1E ∴ ∀gEX, fg ∈ Mor(X,F) ⇒ g = hfg ∈ Mor(X,E).∎
Let f∈Mor(E,F) a quasi-embedding. If there exists a pre-embedding g∈Mor(X,F) with the same image Im g = Im f = AF and ACA holds then f is an embedding.

Proof.

hXA, gh = IdAghf = f ∈ Mor(E,F) ∴ hf ∈ Mor(E,X)
∃ϕ∈Mor(X,E), f⚬ϕ = gf⚬ϕ⚬hf = ghf = f ∴ ϕ⚬hf = IdE.∎
A subobject (X,u) of E will be qualified as embedded (resp. quasi-embedded) if u is an embedding (resp. a quasi-embedding) 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, IdA) ≡ (E,f). (For a quasi-embedding 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 sub-co-action C(f=g) of C(E) where

CX, X(f=g) = {hX(E) | fh = gh}

(if it is regular; it is anyway a sub-co-action by stability of equalizers)
In any concrete category, all equalizers are quasi-embedded 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 gf = 1E then f is an equalizer of (1F, fg).

### Submodules

For any b∈Mor(X,Y), let us call b-submodule of an object F, any subobject (E,f) of F such that E is a b-module. Equivalently,

h∈Mor(X,E), ∃!j∈Mor(Y,E), fjb = fh

When F is itself a b-module, ∃!g∈Mor(Y,F), gb = fh and the submodule condition becomes equivalent to each of
1. k∈ Im f(X), ∃g∈ Im f(Y), gb = k
2. g∈Mor(Y,F), gb∈ 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 b-module, 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 quasi-embedded subobjects in a concrete category: a subset A of an object F will be called b-stable if b(F)⋆(X(A)) ⊂ Y(A), or more explicitly

g∈Mor(Y,F), Im gbA ⇒ Im gA

In particular:
• In any category made of L-systems for some algebraic language L, for any b∈Mor(X,Y) such that 〈Im bL = Y,
• any L-stable subset is b-stable;
• in particular, any L-stable subset of a b-module is a b-module.
• If b is surjective then all subsets of objects are b-stable.
For any b-module F and f∈ Mor(E,F),
1. If f is a pre-embedding and b is bijective then E is a b-module;
2. If f is a quasi-embedding and Im f is b-stable then (E,f) is a b-submodule.
Proofs:
1. u∈Mor(X,E), fub-1 ∈ Mor(Y,F) ∴ ub-1∈Mor(Y,E).
2. u∈Mor(X,E), (∃!g∈Mor(Y,F), gb = fu ∴ Im g ⊂ Im f)
∴ (∃!h∈Mor(Y,E), fhb = fu) ∴ (∃!h∈Mor(Y,E), hb = u).∎

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 : 3.9. Objets initiaux et finaux