(Previous : products of
relational systems, in the series on algebra)

Indeed both formulas

For example with

s( |
x_{00} , |
x_{01} |
) = | y_{0} |

s( |
x_{10} , |
x_{11} |
) = |
y_{1} |

( |
↳∈r∧ |
↳∈r |
) ⇒ | ↳∈r |

We have a Galois connection between sets of operations and sets of relations in

For any set

Inv *S* = {*r*∈Rel_{E}|∀*s*∈*S*,
*s* ▷*r*} = ⋃_{m∈ℕ} Sub_{S}(*E*^{m})

For any set

Pol *R* = {*s*∈Op_{E}|∀*r*∈*R*,
*s* ▷*r*} = ⋃_{n∈ℕ} Mor_{R}(*E*^{n},*E*)

**Theorem.** For any *R*-systems *A*,*E* and
any *S* ⊂ Pol *R _{E}* ⊂ Op

Proof 1:

∀Proof 2:n∈ℕ, ∀s∈S∩Op_{E}^{(n)}⊂ Mor_{R}(E^{n},E), ∀x∈ Mor_{R}(A,E)^{n}, ∏x∈ Mor_{R}(A,E^{n}) ⇒s_{EA}(x) =s०(∏x)∈ Mor_{R}(A,E).

Mor_{R}(A,E) = ⋂_{r∈R}⋂_{x∈rA}{f∈E|^{A}f०x∈r}_{E}

Letg= (_{x}E∋^{A}f↦f०x) = ∏_{i<m}π_{x(i)}∈ Mor_{S}(E^{A},E^{m})

r_{E}∈ Sub_{S}(E^{m}) ⇒ {f∈E|^{A}f०x∈r} =_{E}g*(_{x}r_{E}) ∈ Sub_{S}(E^{A})

**Theorem.** The set Pol *R* of polymorphisms of any *R*
⊂ Rel_{E}, is a clone of operations, i.e. ∀*S*
⊂ Op_{E}, Cl(*S*) ⊂ Pol Inv *S.*

∀S⊂ Op_{E}, ∀m∈ℕ, ∀r∈Sub_{S}(E^{m}), ∀s∈Cl(S),r∈Sub_{s}(E^{m}) :ris stable by any operation defined by a term with languageS, that can be interpreted in theS-algebrar. Thus, Cl(S) ⊂ Pol InvS.

We have an injection from Op_{E} to Rel_{E},
defined by representing each *n*-ary operation *s*∈*E ^{En}*
by its graph Gr

**Theorem.** ∀ *s*,*t* ∈Op_{E} , *s*
▷ Gr *t* ⇔ *t* ▷ Gr *s*.

Proof 1. (*s* ▷ Gr *t*) ⇔ *s*∈Mor_{t}(*E*^{n},*E*)
⇔ Gr *s* ∈ Sub_{t}(*E*^{n}×*E*)
⇔ *t* ▷ Gr *s*.

To display this as a big table, for example if both operations are binary:

s( |
x_{00} , |
x_{01} |
) = | y_{0} |

s( |
x_{10} , |
x_{11} |
) = |
y_{1} |

s( |
t(↳), | t(↳) | ) = | t(↳) |

So, the graph functor defines an injection Gr

∀ *S*, *S*' ⊂ Op_{E},
*S*'⊂Pol(Gr_{*}(*S*)) ⇔ *S*⊂Pol(Gr_{*}(*S*'))
⇔ *S*'⊂Gr*(Inv *S*) ⇔ *S* ⊂Gr* (Inv *S*').

References of works by other authors on polymorphisms and clones:

Basics of clone theory

Old article

A gentle introduction to clones, their Galois theory, and applications (slides, published here with the permission of its author, Mike Behrisch)

Clones and Galois connections (with a list of Galois connections on page 20)

Next : Relational
clones - Abstract clones - Duality
systems and theories

Back to Set theory and
foundations of mathematics main page