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 r⊂E^m and n-ary operations s∈Op_E⁽ⁿ⁾ = E^Eⁿ is equivalently defined by

s ▷r ⇔ s∈Mor_r(Eⁿ,E) ⇔ r∈Sub_s(E^m).

which will be read «s preserves r», «s is a polymorphism of r», or «r is invariant by s».
Indeed both formulas s∈Mor_r(Eⁿ,E) and r∈Sub_s(E^m) express the same condition on any mn-tuple (x_ij)_{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 ∀(x₀₀ , x₁₀)∈r ,∀(x₀₁ , x₁₁)∈r , (s(x₀₀,x₀₁), s(x₁₀,x₁₁)) ∈r.

s(	x₀₀ ,	x₀₁	) =	y₀
s(	x₁₀ ,	x₁₁	) =	y₁
(	↳∈r∧	↳∈r	) ⇒	↳∈r

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

For any set S ⊂ Op_E of operations on E, we define its set of invariant relations, Inv S ⊂ Rel_E, by

Inv S = {r∈Rel_E|∀s∈S, s ▷r} = ⋃_m∈ℕ Sub_S(E^m)

For any set R⊂Rel_E, we define its set of polymorphisms, Pol R ⊂ Op_E, by

Pol R = {s∈Op_E|∀r∈R, s ▷r} = ⋃_n∈ℕ Mor_R(Eⁿ,E)

In particular

∀G⊂E^E, ∀F⊂℘(E), G ⊂ End_FE ⇔ (∀f∈G, ∀A∈F, f[A] ⊂ A) ⇔ F ⊂ Sub_GE.

Theorem. For any R-systems A,E and any S ⊂ Pol R_E ⊂ Op_E, we have Mor_R(A,E) ∈ Sub_S(E^A).

Proof 1:

∀ n∈ℕ, ∀s ∈ S∩Op_E⁽ⁿ⁾ ⊂ Mor_R(Eⁿ,E), ∀ x∈ Mor_R(A,E)ⁿ, ∏x∈ Mor_R(A,Eⁿ) ⇒ s_E^A(x) = s०(∏x)∈ Mor_R(A,E).

Proof 2:

Mor_R(A,E) = ⋂_r∈R ⋂_{x∈r_A} {f ∈E^A|f०x∈r_E }
Let g_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.

Was already proven for a category. Other proof, specific of relational systems R:

∀ S ⊂ Op_E, ∀m∈ℕ, ∀r∈Sub_S(E^m), ∀s ∈Cl(S), r∈Sub_s(E^m) : 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 Op_E to Rel_E, defined by representing each n-ary operation s∈E^Eⁿ by its graph Gr s ⊂ Eⁿ×E ≅ Eⁿ⁺¹.

Theorem. ∀ s,t ∈Op_E , s ▷ Gr t ⇔ t ▷ Gr s.

Proof 1. (s ▷ Gr t) ⇔ s∈Mor_t(Eⁿ,E) ⇔ Gr s ∈ Sub_t(Eⁿ×E) ⇔ t ▷ Gr s.

Proof 2. We can directly see the symmetry of this relation, for s∈Op_E⁽ⁿ⁾ and t∈Op_E^(m), by currying the matrix (tuple ∈E^nm) in both ways as x₀,...,x_m_-1∈Eⁿ, and y₀,...,y_n_-1∈E^m so that (x_j)_i = (y_i)_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(x₀),...,s(x_m_-1)) = s(t(y₀),...,t(y_n_-1)).

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

s(	x₀₀ ,	x₀₁	) =	y₀
s(	x₁₀ ,	x₁₁	) =	y₁
s(	t(↳),	t(↳)	) =	t(↳)

So, the graph functor defines an injection Gr_* from Op_E to Rel_E, and thus a Galois connection from Op_E to itself:

∀ 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