f ∈Mor(E,F) ∧ (f : E ↔ F) ∧ f^{ -1}∈Mor(F,E).
This will be later generalized to other (abstract) categories, where the following other concepts are directly applicable.
Two objects E, F 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 is a class of objects which
is the isomorphism class of some object in it (independently of the choice).
An endomorphism of an object E, is an element of Mor(E,E) = End(E). It is called non-trivial if it differs from Id_{E}.
An automorphism of E is an isomorphism of E to itself:
Automorphism ⇔ (Endomorphism ∧ Isomorphism)
∀x∈E^{nr}, x∈r_{E} ⇔ f⚬x∈r_{F}.
If f ∈ Mor_{L}(E,F) strongly preserves all structures (E = ^{L}f_{⋆}(F)), it will be called a pre-embedding. The construction of the order quotient of a preorder (2.9) forms a general example of pre-embedding.For any subset A⊂F of a relational system F, we define its structure by restriction : A = F ∩ ^{L}A. It is the only structure on A such that, equivalently
From Id_{A}∈Mor_{L}(A,F), we deduce for all systems N, Mor_{L}(A,N) ⊂ {g_{|A} | g∈Mor_{L}(F,N)} but generally without equality (details in 3.8).
Isomorphism ⇒ Elementary embedding ⇒ Embedding ⇒ Injective morphism
An elementary subsystem of a system F is an A⊂F such that Id_{A} : A ↪ F is an elementary embedding, i.e. the value of any formula with parameters in A is the same whether its quantifiers range all in F or all in A.
Elementary equivalence. Different systems are said to be elementarily equivalent,
if they have all the same properties.
The existence of an elementary embedding between systems implies that they
are elementarily equivalent.
Non-surjective elementary embeddings, and more generally the diversity of
elementarily equivalent but non-isomorphic systems, play special roles in high-level
studies of the foundations of mathematics, as we shall see with Skolem's paradox and
non-standard
models of arithmetic. However they are ignored by the most usual practice of
mathematics, because of how far-fetched (hard to find) they usually are.
Here is an aspect of such "difficulties" which is very easy to prove.
If an elementary embedding f : E ↪ E is invariant then it is surjective,
thus an automorphism :
∀M⊂E^{E}, ∀F⊂℘(E), M ⊂ End_{F}E ⇔ (∀f∈M, ∀A∈F, f[A] ⊂ A) ⇔ F ⊂ Sub_{M}E.
Gathering all arities forms the Galois connection (End, Inv) withInv = ⊓_{n∈ℕ} Inv^{(n)} : ℘(E^{E}) → ∏_{n∈ℕ} ℘(Rel_{E}^{(n)}) ⥬ ℘(Rel_{E}).
This concept of "invariance" is a priori distinct from the one previously introduced and used above (definability without parameters) ; yet both are related, and versions of these will be effectively linked by implications and even some equivalences, as will be seen later. This is basically because the concept of definability without parameters is a closure function, which to a given set of "primitive symbols" gives the set of all symbols generated by it through the definition process, and thus may be compared to other closure functions such as Inv ⚬ End.∀x∈^{L}E, ∀y∈F, (^{L}f(x),y) ∈ F ⇒ ∃z∈E, f(z) = y ∧ (x,z)∈E.
Equivalently, ∀A⊂^{L}E, f[E^{⋆}(A)] = F^{⋆}(^{L}f[A]) which implies ∀A⊂E, f[E^{⋆}(^{L}A)] = F^{⋆}(^{L}(f[A])).(φ_{F}⚬^{L}f = f⚬φ_{E} ∧ Inj f) ⇒ ∀(x,y)∈^{L}E×E, f(y) = φ_{F}(^{L}f(x)) ⇒ y = φ_{E}(x).
Similarly, one can directly check that any injective morphism from a serial system to a partial algebra, or from a surjective system to an injective one, is an embedding.
Conversely, if f is a pre-embedding and (E is surjective, or some
s_{E} is injective for one of its arguments) then f is injective.
Bijective morphisms between algebras are isomorphisms. This can also
be deduced by
(^{L}f)^{-1} = ^{L}(f^{ -1}) ∴ φ_{E} ⚬ ^{L}f^{ -1} = f^{ -1} ⚬ f ⚬ φ_{E} ⚬ ^{L}f^{ -1} = f^{ -1} ⚬ φ_{F} ⚬ ^{L}f ⚬ ^{L}f^{ -1} = f ^{-1} ⚬ φ_{F}.
∀A⊂E, E^{⋆}(^{L}A)
⊂ A ⇒ F^{⋆}(^{L}(f[A]))
⊂ f[A]
∀A∈ Sub_{L}E,
f[A] ∈ Sub_{L}F
Images of algebras. For any two L-algebras E,F, ∀f ∈Mor_{L}(E,F), Im f ∈ Sub_{L}F.
Proof : φ_{F}[^{L}Im f] = φ_{F}[Im ^{L}f] = Im (f⚬φ_{E}) ⊂ Im f ∎Preimages of stable subsets. ∀f∈Mor_{L}(E,F), ∀B∈ Sub_{L}F, f_{⋆}(B) ∈ Sub_{L} E.
Proof. Let A=f_{⋆}B.Proposition. For any L-systems E, F, ∀f ∈Mor_{L}(E,F),
Thus when f is full (in particular when E, F are algebras) we have equalities:
f [Min_{L}E] = Min_{L}F
∀A⊂E, f [〈A〉_{L}] =
〈f [A]〉_{L}.
3.1. Galois connections4. Arithmetic and first-order foundations
3.2. Relational systems and concrete categories
3.3. Algebras
3.4. Special morphisms
3.5. Monoids and categories
3.6. Actions of monoids and categories
3.7. Invertibility and groups
3.8. Properties in categories
3.9. Initial and final objects
3.10. Products of systems
3.11. Basis
3.12. The category of relations
Other languages:
FR :
Morphismes particuliers