3.2. Special morphisms

Let us introduce diverse possible qualifications for morphisms of relational systems, and show them related by the following dependencies (without converses in general):

Automorphism ⇔ (Endomorphism ∧ Isomorphism)
Isomorphism ⇔ (Retraction ∧ Monomorphism) ⇔ (Section ∧ Epimorphism)
Retraction ⇒ Surjective morphism ⇒ Epimorphism
Section ⇒ Embedding ⇒ Injective morphism ⇒ Monomorphism
Isomorphism ⇒ Elementary embedding ⇒ Embedding

Functions defined by composition. In any category (whether concrete or not), any f ∈ Mor(E,F) defines functions by currying the operation of composition with other morphisms to or from another object X: let us denote (following wikipedia)
The first one respects composition, while the second one reverses it: for any 4 objects E,F,G,X , ∀f ∈Mor(E,F), ∀g∈Mor(F,G),
Hom(X,g) ০ Hom(X,f) = Hom(X,gf)
HomF(f,X) ০ HomG(g,X) = HomG(gf,X)

Monomorphism. In a category, a morphism f∈Mor(E,F) is called monic, or a monomorphism, if Hom(X,f) is injective for all objects X.

Epimorphism. In an abstract category, a morphism f∈Mor(E,F) is called epic, or an epimorphism, if Hom(f,X) is injective for all objects X:
g,h∈Mor(F,X), gf=hfg=h.
In our concept of concrete category, we must specify F: we say that f∈Mor(E,F) is F-epic, or an F-epimorphism, if all HomF(f,X) are injective.

In any concrete category, all injective morphisms are monic, and any morphism with image F is F-epic. However, the converses may not hold, and exceptions may be uneasy to classify, especially as the condition depends on the whole category and not just the morphism at hand.

The following 2 concepts may be considered cleaner as they admit a local characterization:

Sections. A morphism f∈Mor(E,F) is called a section (or section in F if the category is concrete), if IdE∈Im(HomF(f,E)), i.e. ∃g∈Mor(F,E),gf=IdE. Then f is monic and for all objects X we have Im(HomF(f,X)) = Mor(E,X).

Retraction. A morphism g∈Mor(F,E) is called a retraction (or retraction on E if the category is concrete), if IdE∈Im(Hom(E,g)), i.e. ∃f∈Mor(E,F),gf=IdE. Then g is epic and for all objects X we have Im(Hom(X,g)) = Mor(X,F).
When gf=IdE we also say that f is a section of g, and that g is a retraction of f.

Proof: if gf=IdE then for all objects X, HomF(f,X) ০ HomE(g,X) = HomE(IdE,X) = IdMor(E,X), thus Similarly, Hom(X,g) ০ Hom(X,f) = Hom(X,IdE) = IdMor(X,E) thus

Isomorphism. In a concrete category, an isomorphism between objects E,F , is a bijection f : EF such that f ∈Mor(E,F) and f -1∈Mor(F,E).
In any category, an isomorphism is an f ∈Mor(E,F) such that ∃g∈Mor(F,E), gf= IdEfg= IdF (this inverse g of f is unique).

In this case, Hom(X,f) and Hom(X,g) are bijections, inverse of each other, between Mor(X,E) and Mor(X,F).

Any epic section f∈Mor(E,F) is an isomorphism : gf=IdEfgf = IdFffg=IdF
Similarly, any monic retraction is an isomorphism.
Two objects E, F are said to be isomorphic if there exists an isomorphism between them.  

Endomorphisms. An endomorphism of an object E in a category, is a morphism from E to itself. Their set is written End(E)=Mor(E,E).

Automorphisms. An automorphism of an object E is an isomorphism of E to itself.

Thus it is both an endomorphism and an isomorphism. However an endomorphism of E which is an isomorphism to a strict subset of E, is not an automorphism.

Strong preservation. A function fFE is said to strongly preserve a relation symbol or formula r interpreted in each of E and F, if it preserves both r and ¬r :
Embeddings. An f ∈MorL(E,F) is called an L-embedding if it strongly preserves all structures : ∀rL,∀xEnrxrEfxrF.

Embeddings will usually be supposed injective, as it means strongly preserving the equality relation. Things can come down to this case by replacing equality in the concept of injectivity by a properly defined equivalence relation, or replacing systems by their quotient by this relation, where the canonical surjections would be non-injective embeddings.
Injective embeddings are isomorphisms to their images.
Embeddings still strongly preserve structures defined using the symbols in L and the logical symbols ∧,∨,0,1,¬, and also = in the case of injective embeddings.
Thus, they also preserve invariant structures defined using symbols of L and ∧,∨,¬,0,1,∃ where any occurrence of ¬ comes after (inside) any occurrence of ∃.

Now removing this order restriction on the use of logical symbols provides the full use of first-order logic:

Elementary embedding. An f ∈ MorL(E,F) is called an elementary embedding (or elementary L-embedding) if it (strongly) preserves all invariant structures (defined by first-order formulas with language L).

Every isomorphism is an elementary embedding.
If f∈ End(E) is an invariant elementary embedding then it is an automorphism:

Im f is also invariant (as a unary relation ∃y, f(y)=x)
∴ ∀xE, x∈Im ff(x)∈Im f
∴ Im f = E. ∎

The existence of an elementary embedding f ∈MorL(E,F) implies that E and F are elementarily equivalent:

Elementary equivalence. 2 systems are said to be elementarily equivalent, if every ground first-order formula true in the one is true in the other.

The most usual practice of mathematics focuses on systems where all elementarily equivalent ones are connected by isomorphisms, which are the only elementary embeddings. However, non-surjective elementary embeddings exist and play a special role in foundational issues, such as Skolem's paradox and non-standard models of arithmetic.

Initial and final objects

In any category, an object X is called an initial object (resp. a final object) if for all objects Y the set Mor(X,Y) (resp. Mor(Y,X)) is a singleton.
Such objects have this remarkable property: when they exist, all such objects are isomorphic, by a unique isomorphism between any two of them.

Proof: For any initial objects X and Y, ∃f∈Mor(X,Y), ∃g∈Mor(Y,X), gf ∈Mor(X,X) ∧ fg ∈Mor(Y,Y).
But IdX ∈ Mor(X,X) which is a singleton, thus gf= IdX. Similarly, fg=IdY.
Thus f is an isomorphism, unique because Mor(X,Y) is a singleton.∎

By this isomorphism X and Y may be treated as identical to each other. We may say that an initial object is essentially unique.
Such objects exist in many categories, but are not always interesting. For example, in any category of relational systems containing representatives (copies) of all possible ones with a given language: Exercise. Given two fixed sets X and Y, consider the category whose objects are all (E,φ) where E is a set and φ: E×XY, and the morphisms from (E,φ) to (E',φ') are all f : EE' such that ∀aE,∀xX, φ(a,x) = φ'(f(a),x).
Does it have an initial object ? a final object ?
More texts on algebra

Back to homepage : Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Morphisms of relational systems and concrete categories
3.2. Special morphisms
3.3. Algebras
3.4. Algebraic terms and term algebras
3.5. Integers and recursion
3.6. Arithmetic with addition
4. Model Theory
4.1. Finiteness and countability
4.2. The Completeness Theorem
4.3. Infinity and the axiom of choice
4.4. Non-standard models of Arithmetic
4.5. How theories develop
4.6. The Incompleteness Theorem