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 LR[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) ⇔ Lf[E]⊂F.
We shall call projection from E to F any surjective morphism f giving to F a role of quotient of E, namely Lf[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
Lf[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 = Lf*(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).

For any relational system E and any subset AE, defining the structure of A by restricting that of E to A,

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

(Lf)-1 = L(f -1) ∴ φELf -1 = f -1f০φELf -1 = f -1০φFLfLf -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). It is nontrivial if it differs from IdE.
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. ∎

The Galois connection (End, Inv)

For any set E and any n∈ℕ, the preservation relation (∀xR, fxR) between fEE 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 MEE. In particular, Inv(1) M = SubM :

MEE, ∀F⊂℘(E), M ⊂ EndFE ⇔ (∀fM, ∀AF, f[A] ⊂ A) ⇔ F ⊂ SubME.

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

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

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. Initial and final objects
3.9. Algebraic terms
3.10. Term algebras
3.11. Integers and recursion
3.12. Presburger Arithmetic
4. Model Theory