Skip to main content
4 of 4
fix spelling of Bodnarchuk
Emil Jeřábek
  • 47.3k
  • 4
  • 150
  • 209

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.