3.4. Special morphisms

Let us introduce diverse qualifications for morphisms between objects of diverse concrete categories.

Isomorphisms, endomorphisms, automorphisms.

Between objects E and F of a concrete category, an isomorphism is a bijective morphism f whose inverse is also a morphism :

f ∈Mor(E,F) ∧ (f : E ↔ F) ∧ f -1∈Mor(F,E).

This will be later generalized to other (abstract) categories, where the following other concepts are directly applicable.

Two objects E, F are said to be isomorphic (to each other) if there exists an isomorphism between them. This is an equivalence predicate, i.e. it works as an equivalence relation on the class of objects in this category.
The isomorphism class of an object in a category, is the class of all objects which are isomorphic to it. Then an isomorphism class of objects is a class of objects which is the isomorphism class of some object in it (independently of the choice).

An endomorphism of an object E, is an element of Mor(E,E) = End(E). It is called non-trivial if it differs from IdE.

An automorphism of E is an isomorphism of E to itself:

Automorphism ⇔ (Endomorphism ∧ Isomorphism)

Embeddings

Let L a relational language, and two L-systems E and F.
A relation symbol r interpreted as rE in E and rF in F is called strongly preserved by a function f ∈ FE, if both r and ¬r are preserved :

∀x∈Enr, x∈rE ⇔ f⚬x∈rF.

If f ∈ MorL(E,F) strongly preserves all structures (E = Lf⋆(F)), it will be called a pre-embedding. The construction of the order quotient of a preorder (2.9) forms a general example of pre-embedding.
An embedding is an injective pre-embedding. Injectivity can be made a consequence of the pre-embedding condition by adding = to the language (as injectivity means strongly preserving =). Yet if this = symbol is not required to keep its standard interpretation, but may be interpreted as any relation fitting the axioms of equality, then any pre-embedding can still fit the condition, only playing a role of embedding relatively to the use of this symbol in guise of equality, which reflects that it becomes a true embedding after quotienting the systems by this equivalence relation (this quotient reduces the interpretation of = to the standard one, and strongly preserves other structures).

For any subset A⊂F of a relational system F, we define its structure by restriction : A = F ∩ LA. It is the only structure on A such that, equivalently

Thus any f ∈ MorL(E,F) is the composite of 2 morphisms IdA⚬f where A = Im f and f ∈ MorL(E,A).
Then f is an embedding into F if and only if it is an isomorphism to A. In particular, isomophisms are the bijective embeddings.

From IdA∈MorL(A,F), we deduce for all systems N, MorL(A,N) ⊂ {g|A | g∈MorL(F,N)} but generally without equality (details in 3.8).

Elementary embeddings

Pre-embeddings also strongly preserve structures defined with symbols in L and logical symbols ∧,∨,0,1,¬, and also = in the case of embeddings.
Thus, they also preserve invariant structures defined using symbols of L and ∧,∨,0,1,¬,∃ but where all occurrences of ∃ precede those of ¬.
Removing this restriction on the order of logical symbols, gives the full use of first-order logic. Then a morphism that (strongly) preserves all invariant structures, is called an elementary embedding.

Isomorphism ⇒ Elementary embedding ⇒ Embedding ⇒ Injective morphism

An elementary subsystem of a system F is an A⊂F such that IdA : A ↪ F is an elementary embedding, i.e. the value of any formula with parameters in A is the same whether its quantifiers range all in F or all in A.

Elementary equivalence. Different systems are said to be elementarily equivalent, if they have all the same properties.
The existence of an elementary embedding between systems implies that they are elementarily equivalent.

Non-surjective elementary embeddings, and more generally the diversity of elementarily equivalent but non-isomorphic systems, play special roles in high-level studies of the foundations of mathematics, as we shall see with Skolem's paradox and non-standard models of arithmetic. However they are ignored by the most usual practice of mathematics, because of how far-fetched (hard to find) they usually are.
Here is an aspect of such "difficulties" which is very easy to prove. If an elementary embedding f : E ↪ E is invariant then it is surjective, thus an automorphism :

The Galois connection (End, Inv)

For any set E and any n∈ℕ, the preservation relation (∀x∈R, f⚬x∈R) between f∈EE and R∈RelE(n) gives a Galois connection (End, Inv(n)) between their powersets, where Inv(n)(M) is the set of n-ary relations invariant by M ⊂ EE. In particular, Inv(1) M = SubM :

∀M⊂EE, ∀F⊂℘(E), M ⊂ EndFE ⇔ (∀f∈M, ∀A∈F, f[A] ⊂ A) ⇔ F ⊂ SubME.

Gathering all arities forms the Galois connection (End, Inv) with

Inv = ⊓n∈ℕ Inv(n) : ℘(EE) → ∏n∈ℕ ℘(RelE(n)) ⥬ ℘(RelE).

This concept of "invariance" is a priori distinct from the one previously introduced and used above (definability without parameters) ; yet both are related, and versions of these will be effectively linked by implications and even some equivalences, as will be seen later. This is basically because the concept of definability without parameters is a closure function, which to a given set of "primitive symbols" gives the set of all symbols generated by it through the definition process, and thus may be compared to other closure functions such as Inv ⚬ End.

Morphisms of algebras

For an algebraic language L, let us qualify a morphism f ∈ MorL(E,F) between L-systems as full if

∀x∈LE, ∀y∈F, (Lf(x),y) ∈ F ⇒ ∃z∈E, f(z) = y ∧ (x,z)∈E.

Equivalently, ∀A⊂LE, f[E⋆(A)] = F⋆(Lf[A]) which implies ∀A⊂E, f[E⋆(LA)] = F⋆(L(f[A])).
Any morphism from a serial system to a partial algebra is full. In particular, any morphism between algebras is full.
Any injective full morphism is an embedding.
There is a more direct way to check that any injective morphism between algebras is an embedding :

(φF⚬Lf = f⚬φE ∧ Inj f) ⇒ ∀(x,y)∈LE×E, f(y) = φF(Lf(x)) ⇒ y = φE(x).

Similarly, one can directly check that any injective morphism from a serial system to a partial algebra, or from a surjective system to an injective one, is an embedding.

Conversely, if f is a pre-embedding and (E is surjective, or some sE is injective for one of its arguments) then f is injective.
Bijective morphisms between algebras are isomorphisms. This can also be deduced by

(Lf)-1 = L(f -1) ∴ φE ⚬ Lf -1 = f -1 ⚬ f ⚬ φE ⚬ Lf -1 = f -1 ⚬ φF ⚬ Lf ⚬ Lf -1 = f -1 ⚬ φF.

Images and preimages with algebraic languages

The direct image of a stable subset by a full morphism is stable:

∀A⊂E, E⋆(LA) ⊂ A ⇒ F⋆(L(f[A])) ⊂ f[A]
∀A∈ SubLE, f[A] ∈ SubLF

In particular,

Images of algebras. For any two L-algebras E,F, ∀f ∈MorL(E,F), Im f ∈ SubLF.

Proof : φF[LIm f] = φF[Im Lf] = Im (f⚬φE) ⊂ Im f ∎
Also, the image of a morphism from an algebra to a partial algebra is stable and an algebra.

Preimages of stable subsets. ∀f∈MorL(E,F), ∀B∈ SubLF, f⋆(B) ∈ SubL E.

Proof. Let A=f⋆B.
For L-algebras, ∀(s,x)∈LA, f⚬x ∈ Bns∴ f(sE(x)) = sF(f⚬x) ∈B ∴ sE(x)∈A.
For L-systems, ∀(x,y)∈E, (Lf(x),f(y))∈F∴ (x∈LA ⇒ Lf(x)∈LB ⇒ f(y)∈B ⇒ y∈A).∎

Proposition. For any L-systems E, F, ∀f ∈MorL(E,F),

  1. f [MinLE] is minimal (thus f [MinLE] ⊂ MinLF).
  2. ∀A⊂E, f[〈A〉L] = 〈f[A]〉L,f[〈A〉L] ⊂ 〈f[A]〉L
Proof of 1. M = MinLE ⇒ ∀B ∈ SubL f[M], f⋆(B) ∈ SubL M ∴ f⋆(B) = M ∴ B = f[M].
1. ⇒ 2. by adding A as a set of constants into L.∎

Thus when f is full (in particular when E, F are algebras) we have equalities:

f [MinLE] = MinLF
∀A⊂E, f [〈A〉L] = 〈f [A]〉L.

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
3.1. Galois connections
3.2. Relational systems and concrete categories
3.3. Algebras
3.4. Special morphisms
3.5. Monoids and categories
3.6. Actions of monoids and categories
3.7. Invertibility and groups
3.8. Properties in categories
3.9. Initial and final objects
3.10. Products of systems
3.11. Basis
3.12. The category of relations
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry

Other languages:
FR : Morphismes particuliers