3.3. Special morphisms

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

Isomorphism. In any concrete category, an isomorphism between objects E and F, is a morphism f ∈Mor(E,F) such that f : EF and f -1∈Mor(F,E). Or equivalently, ∃g∈Mor(F,E), gf= IdEfg= IdF, which will serve as definition in more general categories.
Two objects E, F are said to be isomorphic if there exists an isomorphism between them.

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

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.

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.
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.
Injective embeddings are isomorphisms to their images.
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:

Elementary embedding. 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

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

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.

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. Categories
3.7. Algebraic terms and term algebras
3.8. Integers and recursion
3.9. Arithmetic with addition
4. Model Theory