3.3. Special morphisms

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

Embeddings and isomorphisms

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 :

xEnrxrEfxrF.
Embeddings. An f ∈MorL(E,F) is called an L-embedding if it strongly preserves all structures : ∀rL,∀xEnrxrEfxrF.

Isomorphism. An isomophism between algebras is a bijective embedding. Generally, an isomorphism between objects E and F of a concrete category, is a morphism (f ∈Mor(E,F)) that is bijective (f : EF) and whose inverse is a morphism (f -1∈Mor(F,E)).
Two objects E, F are said to be isomorphic if there exists an isomorphism between them. This is an equivalence predicate, i.e. it works as an equivalence relation on the universe.
The isomorphism class of an object in a category, is the class of all objects (in this category) 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 any object in it (independently of the choice).
Injective embeddings are isomorphisms to their images.

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.

More generally for relational systems, 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.

Elementary embeddings

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 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

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).

For any set E, ∀fEE, ∀AE, A ∈ Sub{f} Ef ∈ End{A}E.

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

So we have: Automorphism ⇔ (Endomorphism ∧ Isomorphism)
However an endomorphism of E which is an isomorphism to a strict subset of E, is not an automorphism.

If f∈ End(E) 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. ∎

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 defined as  RL[E].
It is the smallest L-structure on E/R such that R∈ Mor(E, E/R).
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. 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