3.3. Special morphisms

Let us introduce diverse possible qualifications for morphisms between relational systems.

Quotient systems

For any relational language L, any L-system (E,E) and any equivalence relation R on E, the quotient set E/R has a natural L-structure E/R defined as RL[E].
It is the smallest L-structure on E/R such that R∈Mor(E, E/R). Indeed for any L-system (F,F) and any f : EF we have f∈Mor(E,F) ⇔ fL[E]⊂F.

Given an algebraic language L, an equivalence relation R on E is said to be compatible with an L'-structure E if the quotient structure is a functional graph. If E is an algebra structure then Dom(E/R) = L⋆(E/R) so that the compatibility condition means that the quotient is also an algebra.
For any L'-systems (E,E) and (F,F), any f : EF, BF and A= f*(B) we have
(f∈Mor(E,F) ∧ B∈SubLF) ⇒ A∈SubLE
(FfL[E] ∧ A∈SubLE) ⇒ B∈SubLF
fL[E]=F ⇒ (B∈SubLFA∈SubLE)

Embeddings and isomorphisms

Strong preservation. A relation symbol r interpreted as rE in E and rF in F is strongly preserved by a function fFE, if both r and ¬r are preserved :

xEnr, xrEfxrF.

Embeddings. An f ∈MorL(E,F) is called an L-embedding if it strongly preserves all structures : E = fL*(F).
Injectivity is usually added to the definition of the concept of embedding, 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.

Isomorphism. Between objects E and F of a concrete category, an isomorphism is a bijective morphism (f ∈Mor(E,F) ∧ f : EF) whose inverse is a morphism (f -1∈Mor(F,E)). In the case of relational systems, isomophisms are the bijective embeddings; injective embeddings are isomorphisms to their images.

Two objects E, F of a category 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 in a category, is a class of objects which is the isomorphism class of some object in it (independently of the choice).

Embeddings of algebras

Every injective morphism f between algebras is an embedding :

∀(s,x,y)∈L'E, f(y) = sF(fx) = f(sE(x)) ⇒ y=sE(x).

Any embedding between algebras f ∈ MorL(E,F), is injective whenever Im φE = E or some sE is injective for one of its arguments.
Bijective morphisms of algebras are isomorphisms. This can be deduced from the fact they are embeddings, or by

fL-1 = (f -1)L ∴ φEfL-1 = f -1f০φEfL-1 = f -1০φFfLfL-1 = f -1০φF.

Elementary embeddings

L-embeddings still strongly preserve structures defined with symbols in L and logical symbols ∧,∨,0,1,¬, and also = in the case of injective embeddings.
Thus, they also preserve invariant structures whose formula may use symbols of L and ∧,∨,¬,0,1,∃ but all occurrences of ∃ precede those of ¬.

Now the full use of first-order logic comes by removing this restriction on the order of use of logical symbols: an elementary embedding (or elementary L-embedding) is a morphism that (strongly) preserves all invariant structures (defined by first-order formulas with language L).
An elementary subsystem of a system E is an FE interpreting L by restriction, such that IdF is an elementary embedding from F to E, i.e. any formula with parameters in F takes the same Boolean value whether all its bound variables range in F or all range in E.

Isomorphism ⇒ Elementary embedding ⇒ Embedding ⇒ Injective morphism

Elementary equivalence. Different systems are said to be elementarily equivalent, if they have all the same true ground first-order formulas.

The existence of an elementary embedding between systems implies that they are elementarily equivalent.

The most usual practice of mathematics ignores the diversity of elementarily equivalent but non-isomorphic systems, as well as non-surjective elementary embeddings. However, they exist and play a special role in the foundations of mathematics, as we shall see with Skolem's paradox and non-standard models of arithmetic.

Endomorphisms, automorphisms.

An endomorphism of an object E in a category, is an element of Mor(E,E) = End(E).
For any set E, we have a Galois connection (Sub, End) between the powersets of EE and ℘(E):

GEE, ∀F⊂℘(E), G ⊂ EndFE ⇔ (∀fG, ∀AF, f[A] ⊂ A) ⇔ F ⊂ SubGE.

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

Automorphism ⇔ (Endomorphism ∧ Isomorphism)

An endomorphism f∈ End(E) may be an embedding but not an automorphism : just an isomorphism to a strict subset of E. But any endomorphism which is an invariant elementary embedding is an automorphism:
Im f is also invariant (defined by ∃yE, f(y)=x)
xE, x∈Im ff(x)∈ Im f
Im f = E. ∎

Set theory and foundations of mathematics
1.First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Relational systems and concrete categories
3.2. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Algebraic terms and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory