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.

x00 x01 ) = y0
x10 , x11 ) =
↳∈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)
In particular

GEE, ∀F⊂℘(E), G ⊂ EndFE ⇔ (∀fG, ∀AF, f[A] ⊂ A) ⇔ F ⊂ SubGE.

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)

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.

Was already proven for a category. Other proof, specific of relational systems R:
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 ) =
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