3.3. Special morphisms

Let us introduce diverse possible qualifications for morphisms of 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 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.

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, ∀fEE, ∀AE, A ∈ Sub{f}Ef ∈ End{A}E.

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 if it is an invariant elementary embedding then it 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