## 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α.

which easily implies that
• C(M) is a copy of Cα, with correspondence depending on e.
• (Mα,e) is an egg of |Cα|.
Equivalently, an egg 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}
For any object M of a category C, (M, 1M) is an egg of C(M).
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}.
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 co-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)

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

As introduced in 3.6, any object E of a category C defines there a co-action C(E), which is regular admitting (E, 1E) as co-egg; then any f∈Mor(E,F) defines by composition a meta-morphism f(C) from C(E) to C(F), which is injective when f is monic. We can then re-express the concept of subobject (E,f) of F as the sub-co-action Im f(C) of C(F) (also known as the trajectory of (E,f) there), which is meta-isomorphic to C(E). This makes the concept of subobject strictly independent of a choice of presentation (but ontologically more expensive). So, a subobject of F can finally be understood as a regular sub-co-action of C(F), whose co-eggs are its presentations. Indeed from definitions, if (E,f) is a co-egg of some sub-co-action of C(F) then f is monic from E to F.
This will let us define a subobject of F by the data of a sub-co-action of C(F), under the definiteness condition that this sub-co-action needs to be regular.

In particular, this can be used to define concepts of direct images and preimages of subobjects by morphisms, as given by the obviously expressible concepts of direct images and preimages of sub-co-actions. Its meaningfulness on subobjects, is precisely the question whether the result from a regular sub-co-action is also regular. This usually holds for preimages in categories of systems, as can be shown by explicitly describing the result as a subsystem.

But, the situation for direct images can more often be somewhat subtle, except for monomorphisms with which it is trivial (a presentation of the result is given by composition). The question of defining a direct image of a subobject (X,u) of E by an f∈Mor(E,F), comes down to defining an image of the morphism fu∈Mor(X,F) as a subobject of F (beyond the trivial case when fu is monic). Of course, like in all such constructions of subobjects, it is accepted as a subobject when the trajectory of (X,fu) in C(F) is regular. Yet, unlike for many other cases, a concept of image of a morphism may still be accepted beyond this case, because it comes naturally given by the explicit descriptions of this image as a subsystem (a simple example can be found in the category of relational systems with 2 unary relation symbols). Then it fits anyway the following wider abstract definition of the image of a morphism: the subobject it generates (the smallest of the subobjects which contain it).

### Embeddings in concrete categories

Let us generalize the concepts of embedding and pre-embedding from categories of relational systems 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) 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

We defined in 3.3 the equalizer Eq(f, g) ⊂ E of any two functions f,g with the same domain E, and found this subset of E to be more precisely a subalgebra when f,g are morphisms in a category of algebras. Let us generalize this to any category C, conceiving the equalizer Eq(f, g) of two morphisms f,g∈Mor(E,F) as a subobject of E, inspired by the above concept of quasi-embedding.
Namely, we first define the sub-co-action C(f=g) of C(E) by

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

(which is stable, as an equalizer of meta-morphisms for the meta-algebraic structure of co-action). Then we define the equalizer Eq(f, g) as the subobject of E presented by the co-eggs of this C(f=g) if it is regular.
In any concrete category, equalizers are particular quasi-embedded subobjects, namely the co-eggs of the C(A) for subsets A defined as equalizers of two morphisms seen as functions, since C(f=g) coincides with C(Eq(f, g)).

Any section is an equalizer. Namely, if f∈Mor(E,F), g∈Mor(F,E) and gf = 1E then the section f is an equalizer of (1F, fg).

### Submodules

Let X,Y,F be objects of a concrete category and b∈Mor(X,Y). A subset AF will be called b-stable if

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

In particular:
• In any category made of L-systems for some algebraic language L, if 〈Im bL = Y then any L-stable subset is b-stable.
• If b is surjective then all subsets of objects are b-stable.
Let us call b-submodule of an object F, any subobject (E,f) of F such that E is a b-module.
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).∎
This stability concept can be generalized from subsets to subobjects in abstract categories. To that case, the result 2. is easily extended : any b-stable subobject of a b-module is also a b-module. This is of special interest for equalizers, since any equalizer is stable by any epimorphism. The details are left as an easy exercise for the reader.
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