Polymorphisms, invariants and clones of operations

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

The Galois connection Inv-Pol between sets of operations and relations

The preservation relation.m,n∈ℕ, the preservation relation between m-ary relations rEm and n-ary operations s∈OpE(n) = EEn is equivalently defined by
sr s∈Morr(En,E) ⇔ r∈Subs(Em).
which will be read «s preserves r», «s is a polymorphism of r», or «r is invariant by s».
Indeed both formulas s∈Morr(En,E) and r∈Subs(Em) express the same condition on any mn-tuple (xij)i<m, j<n of elements of E (let us see it as a table with m lines and n columns).
For example with m=n=2, it reads ∀(x00 , x10)∈r ,∀(x01 , x11)∈r , (s(x00,x01), s(x10,x11)) ∈r.

s(
x00 x01 ) = y0
s(
x10 , x11 ) =
y1
(
↳∈r ↳∈r ) ⇒ ↳∈r

We have a Galois connection between sets of operations and sets of relations in E, as follows:

For any set S ⊂ OpE of operations on E, we define its set of invariant relations, Inv S ⊂ RelE, by
Inv S = {r∈RelE|∀sS, sr} = ⋃m∈ℕ SubS(Em)

For any set R⊂RelE, we define its set of polymorphisms, Pol R ⊂ OpE, by
Pol R = {s∈OpE|∀rR, sr} = ⋃n∈ℕ MorR(En,E)

Theorem. For any R-systems A,E and any S ⊂ Pol RE ⊂ OpE, we have MorR(A,E) ∈ SubS(EA).

Proof 1:

n∈ℕ, ∀sS∩OpE(n) ⊂ MorR(En,E), ∀ x∈ MorR(A,E)n, ∏x∈ MorR(A,En) ⇒ sEA(x) = s०(∏x)∈ MorR(A,E).
Proof 2:
MorR(A,E) = rR xrA {fEA|fxrE }
Let gx= (EAffx) = ∏i<m πx(i) ∈ MorS(EA,Em)
rE ∈ SubS(Em) ⇒ {fEA|fxrE } = gx*(rE)  ∈ SubS(EA)

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

This is a closure, whose closed elements (the elements of Im Cl) are called the clones of operations:
S∈Im Cl ⇔ ∀n∈ℕ, {πi}i<nS(n) ∈ SubS(OpE(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 ⊂ RelE, is a clone of operations, i.e. ∀S ⊂ OpE, Cl(S) ⊂ Pol Inv S.

Proof 1:
R ⊂ RelE, ∀n∈ℕ, {πi}i<n ⊂ MorR(En,E) ∈ Sub(Pol R)(OpE(n))
Thus Pol R = ⋃n∈ℕ MorR(En,E) is a clone of operations.
Proof 2:
S ⊂ OpE, ∀m∈ℕ, ∀r∈SubS(Em), ∀s ∈Cl(S),  r∈Subs(Em) : r is stable by any operation defined by a term with language S, that can be interpreted in the S-algebra r. Thus, Cl(S) ⊂ Pol Inv S.

The Galois connection Pol-Pol between sets of operations

We have an injection from OpE to RelE, defined by representing each n-ary operation sEEn by its graph Gr s En×EEn+1.

Theorem.s,t ∈OpE , s ▷ Gr tt ▷ Gr s.

Proof 1. (s ▷ Gr t) ⇔ s∈Mort(En,E) ⇔ Gr s ∈ Subt(En×E) ⇔ t ▷ Gr s.

Proof 2. We can directly see the symmetry of this relation, for s∈OpE(n) and t∈OpE(m), by currying the matrix (tuple ∈Enm) in both ways as x0,...,xm-1En, and  y0,...,yn-1Em so that (xj)i = (yi)j. Then, the relation s ▷ Gr t says that for any such matrix we have equality between results after applying s and t in either order:
t(s(x0),...,s(xm-1)) = s(t(y0),...,t(yn-1)).

To display this as a big table, for example if both operations are binary:
s( x00 x01 ) = y0
s( x10 , x11 ) =
y1
s( t(↳), t(↳) ) = t(↳)

So, the graph functor defines an injection Gr* from OpE to RelE, and thus a Galois connection from OpE to itself:
S, S' ⊂ OpE, 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