# Bodnarchuk, Kaluzhnin, Kotov, Romov’s Theorem on inclusion of Polymorphism ($Pol \rho \subseteq Pol \sigma$)

Bodnarchuk, Kaluzhnin, Kotov, Romov’s paper [1] is well-known. Anne Fearnley [2] infered from it the following theroem and used it to prove the inclusion of polymorphisms.

Theorem (Bodnarchuk, Kaluzhnin, Kotov, Romov). Let $A$ be a finite set. Let $\rho \subseteq A^{h}$ , and let $\sigma \subseteq A^{l}$ be a relation without repetitions. Then $Pol \rho \subseteq Pol \sigma$ if and only if there exist $m \geq l, n < m^{h}$ and an $n \times h$ matrix $X = (x_{ij})$ with $x_{ij} \in \{1, \dots, m\}$ such that $(a_1 ,\dots , a_l) \in \sigma$ iff there exist $a_{l+1} , \dots , a_{m}$ such that for all $i = 1, \dots , n$, $(a_{x_{i,1}}, a_{x_{i,2}}, \dots , a_{x_{i,h}}) \in \rho$.

My questions are:

1. I have read [1] several times and am unable to find the proof for necessity part. Could you tell me how is the matrix $X$ constructed for the necessity part? Or could you recommend another resource for a complete proof?

2. Anne Fearnley ([2], page 8) used the matrix $X$ = $\begin{pmatrix} 3 & 4 & 1\\ 5 & 3 & 2\\ \end{pmatrix}$ in the above theorem to prove the following

$Pol\{(0, 0, 0), (1, 1, 1), (0, 1, 2)\} \subset Pol\{(0, 0), (1, 1), (1, 2), (2, 0)\}$,

but how was this matrix $X$ constructed? Is this just by trial? Or is there a general way to construct such a matrix given two relations?

[1] V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras I–II, Kibernetika, 3 (1969), pp. 1–10 and 5 (1969), pp. 1–9 (in Russian); Cybernetics, (1969), pp. 243–252, 531–539 (English version), 1969.

[2] Anne Fearnley, The monoidal interval for the monoid generated by two constants, Journal of Multiple-Valued Logic and Soft Computing, 15(5–6), pp. 597–609, 2009, http://www3.sympatico.ca/anathia/Anne_Fearnley/2-const.pdf‎.

[3] David Geiger, Closed systems of functions and predicates, Pacific J. Math. Volume 27, Number 1 (1968), 95–100.

-
Bondarchuk (Бондарчук), actually... – Sergei Akbarov Aug 11 '13 at 21:49
@SergeiAkbarov: I don’t think so. I can’t access the original article as such, but the contents at kibernetika.org/ContentsUA.html spell the authors as Боднарчук В.Т., Калужнин Л. А., Котов В. Н., Ромов Б. А., and so do most Cyrillic citations. The English version of the paper also transliterates the name as Bodnarchuk (link.springer.com/article/10.1007%2FBF01070906 , link.springer.com/article/10.1007%2FBF01787700), and this form is nearly universally used in Latin citations. – Emil Jeřábek Sep 18 '14 at 14:43
Sorry, wrong link. link.springer.com/article/10.1007/BF01267873 – Emil Jeřábek Sep 18 '14 at 15:28

$\DeclareMathOperator\Pol{Pol}$In model-theoretic terms, if $A$ is a finite set, and $\rho,\sigma$ relations on $A$, then $\Pol\rho\subseteq\Pol\sigma$ iff $\sigma$ is definable in the structure $(A,\rho)$ by a positive primitive (pp) formula, that is, $$\tag{*}\sigma(x_1,\dots,x_l)\iff\exists y_1,\dots,y_k\,\bigwedge_{i\le n}\theta_i(x_1,\dots,x_l,y_1,\dots,y_k),$$ where each $\theta_i$ is an atomic formula (i.e., $\rho$ or $=$ applied to some of the variables $x_j,y_j$).
Notice that identities of the form $y_i=y_j$ or $y_i=x_j$ can be eliminated from $(*)$ by substituting $y_j$ (resp. $x_j$) for $y_i$ and removing the $y_i$ variable. Thus, we can write $\sigma$ as a conjunction of an $=$-free pp formula and some equalities of the form $x_i=x_j$ for $i\ne j$. However, if $\sigma$ is without repetitions, it cannot imply any equality of the latter form, hence we can in fact express $\sigma$ by an $=$-free pp formula, and this is the conclusion of the theorem you quote.
Now, the nontrivial direction of the characterization above can be proved as follows. Let $\sigma^+$ be the intersection of all (finitely many) pp-definable relations that include $\sigma$. Then $\sigma^+$ is itself pp-definable, hence it suffices to show that $\sigma=\sigma^+$. Assume for contradiction that $\sigma^+(\vec c)$ and $\neg\sigma(\vec c)$ for some $\vec c\in A^l$, and let $I$ be the set of all pp-definable relations $\tau\subseteq A^l$ such that $\neg\tau(\vec c)$. For every $\tau\in I$, we have $\sigma^+\nsubseteq\tau$, hence $\sigma\nsubseteq\tau$ by the definition of $\sigma^+$. Thus, we can fix $a_1^\tau,\dots,a_l^\tau\in A$ such that $\sigma(\vec a^\tau)$ and $\neg\tau(\vec a^\tau)$.
For each $i=1,\dots,l$, let $a_i$ be the element of the cartesian product $A^I$ whose $\tau$-coordinate is $a^\tau_i$ for every $\tau\in I$. By construction, we have $$\tag{**}A^I\models\phi(a_1,\dots,a_l)\implies A\models\phi(c_1,\dots,c_l)$$ for every pp formula $\phi$. Enumerate $A^I=\{u_j:j=1,\dots,r\}$, and put $$\phi(x_1,\dots,x_l)=\exists y_1,\dots,y_r\bigwedge\{\theta(x_1,\dots,x_l,y_1,\dots,y_r):A^I\models\theta(a_1,\dots,a_l,u_1,\dots,u_r)\},$$ where $\theta$ runs over all atomic formulas. Since $A^I\models\phi(\vec a)$ and $\phi$ is pp, we have $A\models\phi(\vec c)$ by $(**)$, hence we can fix $v_1,\dots,v_r\in A$ that witness the existential quantifiers in $\phi$. Then $f(u_i):=v_i$ defines a homomorphism $f\colon(A,\rho)^I\to(A,\rho)$ such that $f(a_i)=c_i$. In clone-theoretic terminology, this means that $f$ is a polymorphism of $\rho$, but since $\sigma(\vec a^\tau)$ and $\neg\sigma(\vec c)$, it is not a polymorphism of $\sigma$, which contradicts the assumption.