3.1. Morphisms of relational systems and concrete categories

For simplicity, let us focus the study on systems with only one type.

For any number n and any set E, let En abbreviate the product EVn = E×...×E (n times), that is the set of n-tuples of elements of E.
The sets of all n-ary relations and of all n-ary operations in E are defined as Languages. A language is a set L of "symbols", with the data of the intended arity ns∈ℕ of each symbol sL. It may be For any language L and any set E, let LE = ∐sL Ens
A relational language L, aims to be interpreted in a set E as a family of relations, which belongs to

sL ℘(Ens) ≅ ℘(LE)

Let us now conceive an L-system as a pair (E,E) made of a set E with an L-structure ELE.
Most often, we shall only use one L-structure on each set, so that E can be treated as implicit, determined by E. Precisely, let us take a class of L-systems where each E is the intersection of LE with a fixed class of (s,x), denoted as s(x) because the ns-ary relation sE interpreting each symbol sL in each system E is somehow independent of E:

E={(s,x)∈LE | s(x)}.
sE = {xEns | s(x)} = E(s)
E=∐sL sE.

Morphism. Between any 2 L-systems E,F, we define the set of L-morphisms from E to F as

MorL(E,F) = {fFE|∀sL,∀xEns, s(x)⇒ s(fx)}
= {fFE|∀(s,x)∈E, (r,fx)∈F}.

For any function f, let fL = (L⋆Domf ∋(s,x) ↦ (s,fx)). This gives shorter definitions for sets of morphisms
MorL(E,F) = {fFE| fL[E]⊂F} = {fFE| EfL*F}.

Concrete categories

The concept of concrete category is what remains of a kind of systems with their morphisms, when we forget which are the structures that the morphisms are preserving (as we saw that this structures list can be extended without affecting the sets of morphisms). Let us introduce a slightly different (more concrete) version of this concept than the one usually found elsewhere: here, a concrete category will be the data of
satisfying the following axioms
The last condition is easily verified for L-morphisms : ∀(s,x)∈E, (s,fx)∈F ∴ (s,gfx)∈G.
A relational symbol interpreted in a given concrete category is said to be preserved if all morphisms of the category are also morphisms for this symbol. According to definitions, each symbol in a language L is preserved in any category of L-systems.

A category is small if its class of objects is a set.

Rebuilding structures in a concrete category.

Starting now with any concrete category, its possible preserved families of relations (one relation in each object) can be produced from some sorts of "smallest building blocks" as follows.

Proposition. In any concrete category, for any choice of tuple t of elements of some object K, the relation defined in each object E as sE = {ft | f∈ Mor(K,E)} is preserved.

Proof : ∀g∈Mor(E,F), ∀xsE, ∃f∈ Mor(K,E), (x = ftgf∈ Mor(K,F)) ∴ gx = gftsF.∎

In a small concrete category, the preserved families of relations are precisely all choices of unions of those : each preserved s equals the union of those with t running over s (with variable K).
This can be easily deduced from the fact that any union of preserved structures in a concrete category is a preserved structure (not only finite unions but unions of families indexed by any set). Any intersection of a family of preserved structures is also a preserved structure.

However, even if we could take "all these structures" to turn these objects into relational systems (a possibility only ensured in small categories because of K ranging over all objects), the resulting category of relational systems may admit more morphisms than those we started with (like a closure).

Preservation of some defined structures

In any given category of L-systems, any further invariant structure whose defining formula only uses symbols in L and logical symbols ∧,∨,0,1,=,∃ is preserved (where 0, 1, ∨ and ∧ are particular cases of unions and intersections we just mentioned).
Indeed, for any L-morphism f∈MorL(E,F), Thus, for any f ∈MorL(E,F), if a ground formula with language L using the only logical symbols (=,∧,∨,0,1,∃), is true in E, then it is also true in F.

However morphisms may no more preserve structures defined with other symbols (¬,⇒,∀).

Categories of typed systems

While we introduced the notion of morphism in the case of systems with a single type, it may be extended to systems with several types as well. Between systems E,F with a common list τ of types (and interpretations of a common list of structure symbols), morphisms can equivalently be conceived in the following 2 ways, apart from having to preserve all structures:

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