3.1. Relational systems and concrete categories

*E*=^{n}*E*×...×*E*=*E*^{Vn}, set of all*n*-tuples of elements of*E*(*n*-ary product or exponentiation).- Rel
_{E}^{(n)}= ℘(*E*), set of all^{n}*n*-ary relations in*E* - Op
_{E}^{(n)}=*E*, set of all^{En}*n*-ary operations in*E*.

^{L}*E* = ∐_{s∈L}
*E ^{ns}*

∏_{s∈L} ℘(*E ^{ns}*)
≅ ℘(

The case of an *algebraic language*, whose symbols aim to represent operations,
will be studied in 3.2.

*s _{E}* =
{

Im

∀

*f* ∈ Mor_{L}(*E*,*F*) ⇔
∀(*s*,*x*)∈**E**, (*r*,*f*০*x*)∈**F**

⇔ (∀*s*∈*L*,∀*x*∈*E*^{ns},
*s*(*x*) ⇒ *s*(*f*০*x*))

⇔
* ^{L}f*[

- a class of sets called
*objects*; - a class of functions called
*morphisms*; then for any objects*E*,*F*, we define

Mor(*E*,*F*) = {*f*∈*F*|^{E}*f*is a morphism}

- 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*, Id_{E}∈ 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*),*g*০*f*∈ Mor(*E*,*G*).

A relational symbol

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

Indeed, for any

- Substituting arguments of a
*s*∈*L*by a map σ to*n*' other variables (∀*E*,∀*x*∈*E*^{n'},*s'*(*x*)⇔*s*(*x*০σ)), works :*s'*(*x*) ⇒*s*(*x*০σ) ⇒*s*(*f*০*x*০σ) ⇒*s'*(*f*০*x*). - ∀
*s*,*s*'∈*L*,*n*=_{s}*n*⇒ ∀_{s'}*x*∈*E*^{ns}, (*s*(*x*)∧*s'*(*x*)) ⇒ (*s*(*f*০*x*)∧*s'*(*f*০*x*)) - ∀
*s*,*s*'∈*L*,*n*=_{s}*n*⇒ ∀_{s'}*x*∈*E*^{ns}, (*s*(*x*)∨*s'*(*x*)) ⇒ (*s*(*f*০*x*)∨*s'*(*f*০*x*)) - For 0 and 1 it is trivial

- ∀
*x*,*y*∈*E*,*x*=*y*⇒*f*(*x*)=*f*(*y*) - ∀
*x*∈*E*^{ns},(∃*y*∈*E*,*s*(*x*,*y*)) ⇒ (∃*z*=*f*(*y*)∈*F*,*s*(*f*০*x*,*z*))

The above cases of 0, 1, ∨ and ∧ are mere particular cases (the nullary and binary cases) of the following:

- Any union of a family of preserved structures in a concrete category is a preserved structure.
- Any intersection of a family of preserved structures is also a preserved structure.

**Proposition**. In any concrete category, for any choice of *n*-tuple *t*
of elements of some object *K*, the relation *s* defined in each object *E* as
*s _{E}* = {

From these definitions it might happen between objects

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*
ranging over *s* (with *K* ranging over all objects).

- A tuple (or family) of functions (
*f*)_{t}_{t∈τ}, where ∀*t*∈τ,*f*:_{t}*E*→_{t}*F*where_{t}*E*⊂_{t}*E*,*F*⊂_{t}*F*are the interpretations of type*t*in*E*and*F* - A function
*f*:*E*→*F*that is a τ-morphism seeing τ as a list of unary relation symbols (like for the use of classes as notions in set theory), i.e. such that*h*০_{F}*f*=*h*where_{E}*h*:_{E}*E*→τ,*h*:_{F}*F*→τ are the functions giving the type of each element.

Set theory and foundations of mathematics

1. First foundations of mathematics

2. Set theory (continued)

3.1.4. Model TheoryRelational 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. Initial and final objects

3.9. Algebraic terms

3.10. Term algebras

3.11. Integers and recursion

3.12. Presburger Arithmetic