## 3.1. Morphisms of relational systems and concrete categories

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

Languages. A language is a set L of "symbols", with the data of the intended arity ns∈ℕ of each symbol sL. It may be
• A relational language if its symbols aim to represent relations
• An algebraic language if its symbols aim to represent operations.
For any language L and any set E, let

LE = ∐sL Ens

For a relational language L, an L-system is any 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 (r,x), denoted as r(x) because the nr-ary relation rE interpreting each symbol rL in each system E is somehow independent of E:

E={(r,x)∈LE | r(x)}.
rE = {xEnr | r(x)} = E(r)
E=∐rL rE.

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

MorL(E,F) = {fFE|∀rL,∀xEnr, r(x)⇒ r(fx)}
= {fFE|∀(r,x)∈E, (r,fx)∈F}.

Introducing for any function f the function fL = (L⋆Domf ∋(r,x) ↦ (r,fx)), we get the shorter definitions for sets of morphisms,
MorL(E,F) = {fFE| fL[E]⊂F} = {fFE| EfL*F}.

### Quotient systems

Let us introduce the general concept of quotient of a relational system, before using it in a particular case.
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).

### 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
• A class of sets called objects
• A class of functions called morphisms; for any objects E,F we have a set Mor(E,F)⊂FE of morphisms from E to F, that is the set of all functions from E to F which are morphisms
satisfying the following axioms
• Every morphism belongs to some Mor(E,F), i.e. its domain is an object and its image is included in an object (in practice, images of morphisms will be objects too);
• For any object E, IdE ∈ Mor(E,E) ;
• Any composite of morphisms is a morphism: for any 3 objects E,F,G , ∀f ∈ Mor(E,F), ∀g∈Mor(F,G), gf ∈Mor(E,G).
The last condition is easily verified for L-morphisms : ∀(r,x)∈E, (r,fx)∈F ∴ (r,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.

### Other concepts of category

Categories (also called abstract categories for insistence) differ from concrete categories, by forgetting that objects are sets (ordered by inclusion) and that morphisms are functions; what remains is
• the class of objects, regarded as pure elements (ignoring any inclusion order);
• the sets Mor(E,F) between any two objects E,F, and regarded as pairwise disjoint;
• the composition operations, Mor(F,G)×Mor(E,F)→Mor(E,G).
A category (either concrete or abstract) is small if its class of objects is a set.

### Rebuilding structures in a concrete category.

Starting now with any concrete category, how can we find or describe its possible preserved interpretations of relations ? Any tuple t of elements of some object K defines a relation in each object E which is naturally preserved, by

rE = {ft | f∈ Mor(K,E)}

The structures so defined are the "smallest building blocks" among preserved structures: the preserved interpreted relations in a small concrete category are precisely all the possible unions of such ones (namely, each preserved r equals the union of those with t running over the union r of the rK for all 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

For any given category of L-systems, any further structure defined by a formula (without parameters) using 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),
• Substituting arguments of a rL by a map σ to n' other variables (∀E,∀xEn', r'(x)⇔r(x०σ)), works :
r'(x) ⇒ r(x०σ) ⇒ r(fx०σ) ⇒ r'(fx).
• r,r'∈L,nr=nr' ⇒ ∀xEnr, (r(x)∧r'(x)) ⇒ (r(fx)∧r'(fx))
• r,r'∈L,nr=nr'⇒∀xEnr , (r(x)∨r'(x)) ⇒ (r(fx)∨r'(fx))
• For 0 and 1 it is trivial
• x,yE, x=yf(x)=f(y)
• xEnr,(∃yE, r(x,y)) ⇒ (∃z=f(y)∈F, r(fx, z))
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 (¬,⇒,∀).

### Morphisms between systems with several types

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:
• A tuple (or family) of functions (ft)tτ, where ∀t∈τ, ft:EtFt where EtE, FtF are the interpretations of type t in E anf F
• A function f:EF that is a morphism when regarding τ as a list of unary relation symbols (by the same idea as the use of classes instead of types in set theory); or equivalently, such that hFf=hE where  hE:E→τ, hF :F→τ are the functions giving the type of each object.

More texts on algebra

Back to homepage : 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. Special morphisms
3.3. Algebras
3.4. Algebraic terms and term algebras
3.5. Integers and recursion