Again, we shall usually consider a class of

*s _{E}* :

φ

These form a concrete category with the following concept of morphism.

**Morphisms of algebras. **For any *L*-algebras *E*,
*F*,

Such categories can be seen as particular categories of relational systems, as follows.

Let the relational languageL'be a copy ofLwhere the copys'∈L'of eachs∈Lhas increased arityn=_{s'}n+1, so that_{s}Each L'⋆E≡ ∐_{s∈L}E^{ns}×E≡ (L⋆E)×E≡ {(s,x,y) |s∈L∧x∈E∧^{ns}y∈E}.n-ary operation_{s}sdefines an_{E}n-ary relation_{s'}s'Gr_{E}≡s. These are packed as an_{E}L'-structure

The resulting condition for anE= Gr φ_{E}≡ ∐_{s∈L}s'._{E}f∈Fto be a morphism is equivalent :^{E}(∀( x,y)∈E, (f(_{L}x),f(y))∈F) ⇔ (∀x∈L⋆E, φ_{F}(f(_{L}x))=f(φ_{E}(x))).

**Subalgebras**. A subset *A*⊂*E* of an *L*-algebra *E* is
called *stable by L* or an *L-subalgebra* of *E* if
φ_{E}[*L*⋆*A*]⊂*A*. It is also an *L*-algebra,
with structure φ_{A} restriction of φ_{E} to
*L*⋆*A*. The set of *L*-subalgebras of
*E* is written _{L} *E* = {*A*⊂*E* |
φ_{E}[*L*⋆*A*]⊂*A*}.

**Images of algebras**. For any two *L*-algebras *E*,*F*,
∀*f* ∈Mor_{L}(*E*,*F*), Im *f* ∈ Sub_{L}*F*.

Let us generalize these concepts to categories of relational *L'*-systems
(*E*,**E**) whose structure **E** ⊂ (*L*⋆*E*)×*E*
no more needs to be functional:

*A* ∈ Sub_{L} *E* ⇔ (**E**_{*}(*L*⋆*A*)
⊂*A*) ⇔ (∀(*s*,*x*,*y*)∈**E**,
Im *x*⊂*A* ⇒ *y*∈*A*).

**Preimages of stable subsets.** ∀*f*∈Mor_{L}(*E*,*F*),
∀*B*∈Sub_{L}*F*, *f* *(*B*) ∈ Sub_{L}
*E*.

For

For

**Proposition.** For any *L'*-system *E* and any
*L*-algebra *F*,

∀*f*,*g*∈Mor* _{L}*(

**Intersections of stable subsets.** ∀*X* ⊂ Sub_{L}*E,*
∩*X* ∈ Sub_{L} *E* where ∩*X *≝
{*x*∈*E*|∀*B*∈*X*, *x*∈*B*}.

Other way:
**E**_{*}(*L*⋆∩*X*) =
**E**_{*}(∩_{B∈X} *L*⋆*B*)
⊂∩_{B∈X}
**E**_{*}(*L*⋆*B*) ⊂∩*X*.

**Subalgebra generated by a subset.** ∀*A* ⊂ *E*, we denote
〈*A*〉_{L,E} or simply 〈*A*〉_{L}, the
smallest *L*-stable subset of *E* including *A*
(called *L-subalgebra of E generated by A* if *E* is an algebra):

For fixed

We say that

Min

An *L*-algebra *E* is * minimal* when *E* = Min_{L}
*E*, or equivalently Sub_{L}*E*
= {*E*}.

- ∀
*B*⊂*A*,*B*∈Sub_{L}*E*⇔*B*∈Sub_{L}*A* - Min
_{L}*A*= Min_{L}*E* *A*= Min_{L}*E*⇔*A*is minimal.

Min

Among subsets of *E*, other minimal *L'*-systems are included
in Min_{L} *E* but are not stable.

The stable subset generated by *A* is the minimal one for the extended language
with *A* seen as a set of constants:
〈*A*〉_{L,E}= Min_{L∪A} *E*.

**Injective, surjective algebras.** An *L*-algebra (*E*,φ_{E})
will be called injective if φ_{E} is injective, and surjective if
Im φ_{E} = *E*.

**Proposition.** For any *L*-algebras *E*, *F*,

- ∀
*A*⊂*E*, Im φ_{E}⊂*A*⇒*A*∈Sub_{L}*E*. - Any minimal
*L*-algebra is surjective. - Min
_{L}*E*= φ_{E}[*L*⋆Min_{L}*E*] ⊂ Im φ_{E} - ∀
*A*⊂*E*, ⋃_{x∈A}〈{*x*}〉_{L}⊂ 〈*A*〉_{L}=*A*∪φ_{E}[*L*⋆〈*A*〉_{L}] ⊂*A*∪Im φ_{E} -
∀
*f*∈Mor_{L}(*E*,*F*),*f*[Min_{L}*E*] = Min_{L}*F*∧ ∀*A*⊂*E*,*f*[〈*A*〉_{L}] = 〈*f*[*A*]〉_{L}

- φ
_{E}[*L*⋆*A*] ⊂ Im φ_{E}⊂*A*⇒*A*∈Sub_{L}*E* - Im φ
_{E}∈ Sub_{L}*E* - Min
_{L}*E*is surjective *A*∪φ_{E}[*L*⋆〈*A*〉_{L}] ∈ Sub_{L}〈*A*〉_{L}- ∀
*B*∈ Sub_{L}*F*,*f**(*B*)∈Sub_{L}*E*∴ Min_{L}*E*⊂*f**(*B*) ∴*f*[Min_{L}*E*]⊂*B*.∎

**Injectivity lemma.** If *E* is a surjective algebra and
*F* is an injective one then ∀*f* ∈Mor_{L}(*E*,*F*),

*A*= {*x*∈*E*| ∀*y*∈*E*,*f*(*x*) =*f*(*y*) ⇒*x*=*y*} ∈ Sub_{L}*E*.- For each uniqueness quantifier
*Q*(either ∃! or !),*B*= {*y*∈*F*|*Q**x*∈*E*,*y*=*f*(*x*)} ∈ Sub_{L}*F*

- ∀(
*s*,*x*)∈*L*⋆*A*, ∀*y*∈*E*,*f*(*s*(_{E}*x*)) =*f*(*y*) ⇒ (∃(*t*,*z*)∈φ_{E}^{•}(*y*),*s*(_{F}*f*০*x*) =*f*(*s*(_{E}*x*)) =*f*(*y*) =*f*(*t*(_{E}*z*)) =*t*(_{F}*f*০*z*) ∴ (*s*=*t*∧*f*০*x*=*f*০*z*) ∴*x*=*z*) ⇒*s*(_{E}*x*)=*y*. - As φ
_{F}is injective, ∀*y*∈φ_{F}[*L*⋆*B*], ∃!: φ_{F}^{•}(*y*) ⊂*L*⋆*B*∴*Q**z*∈*L*⋆*E*, φ_{F}(*f*(_{L}*z*)) =*y*.

As φ_{F}০*f*=_{L}*f*০φ_{E}and φ_{E}is surjective, we conclude*Q**x*∈*E*,*y*=*f*(*x*). ∎

**Schröder–Bernstein theorem**.
If there exist injections *f*: *E* → *F* and
*g*: *F*→ *E* then there exists a bijection between *E* and *F*.

Then a bijection from

Set theory and foundations of mathematics

1. First foundations of mathematics

2. Set theory (continued)

3.1. Relational systems and concrete categories4. Model Theory

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. Algebraic terms

3.9. Term algebras

3.10. Integers and recursion

3.11. Presburger Arithmetic