(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})

**Clone of operations****.** For any set *S* ⊂ Op_{E}
of operations in a set *E*, the *clone of operations
generated by S*, is the set Cl(*S*)⊂ Op_{E}
of operations equivalently described as

- defined by terms with variables (arguments, no parameter)
ranging over
*E*, and operation symbols in*S*. - ∀
*n*∈ℕ, Cl(*S*)^{(n)}= 〈{π_{i}}_{i<n}〉_{S}⊂ Op_{E}^{(n)}, i.e. the*n*-ary operations in Cl(*S*) form the*S*-subalgebra of*E*generated by the^{En}*n*projections π_{i}:*E*→^{n}*E*(operations defined by each of the*n*free variables).

This is a closure, whose closed elements (the elements of Im Cl)
are called the *clones of operations*:

S∈Im Cl ⇔ ∀*n*∈ℕ, {π_{i}}_{i<n}
⊂ *S*^{(n)} ∈ Sub_{S}(Op_{E}^{(n)})

The unary part *S*^{(1)} of a clone of operation,
is a transformation
monoid. Precisely, the unary part of the clone of operations
generated by a given set of transformations, equals the
transformation monoid generated by this set. Thus, the concept of
clone of operations is an extension of that of transformation
monoid.

**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.*

∀Proof 2:R⊂ Rel_{E}, ∀n∈ℕ, {π_{i}}_{i<n}⊂ Mor_{R}(E^{n},E) ∈ Sub_{(Pol R)}(Op_{E}^{(n)})

Thus PolR= ⋃_{n∈ℕ}Mor_{R}(E^{n},E) is a clone of operations.

∀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