1

Let $A\neq \emptyset$ be arbitrary set. Let us define a relation on $A$ in the following way: $R=\{(a;b;c)\in A^3| a=b \lor b=c\}$. Show that the clone of polymorphisms of $R$ denoted as $Pol(\{R\})$ is the clone of all operations of the form $(x_1;…;x_n)\mapsto g(x_i):A^n \rightarrow A$ for some $i \in \{1;2;…;n\}$ and some $g:A \rightarrow A$.

It is a routine exercise to show that such set of operation infact is a clone and any function of the form specified above is compatible with $R$. However, I struggle to show that any function $f:A^k \rightarrow A$ that is compatible with $R$ is of the form $f(x_1;…;x_n)=g(x_i)$ for some $i \in \{1;2;…;n\}$ and some $g:A \rightarrow A$.

My approach:

Firstly, choose $f$ compatible with $R$ of arity $k \in \mathbb{N}$. Pick $a$ from the set $A$ and define $g:A\rightarrow A; g(a):=f(a;a;…;a)$. Now I would like to show that $\exists i \in \{1;2;…;k\} \forall x_1,…,x_k \in A: f(x_1;…;x_{i-1};x_i;x_{i+1};…;x_k)=g(x_i)$.

If $A=\{a\}$, then it holds. However, I have no idea what to do if $|A|\geq 2$.

I was trying to deduce something by applying $f$ row-wise onto the matrices of the form (and other similar forms)

\begin{align} f\begin{bmatrix} a&a& \ldots &a& \ldots & a & a\\ a&a& \ldots &a&\ldots & a & a\\ a&a& \ldots & b & \ldots & a& a\end{bmatrix}=\begin{bmatrix}g(a)\\g(a)\\f(a;a;…;b;…;a;a)\end{bmatrix} \in R \end{align} but I have failed so far. (the row-wise application of $f$ is from the definition of compatibility - the columns are in $R$) Since I’ve been stuck on this for quite some time now, it is entirely possible that the function $g$ doesn’t work, but I have no better ideas.

Björn
  • 140

1 Answers1

2

Your goal is to prove that an operation on $A$ is compatible with $R=\{(a,b,c)\in A^3\;|\;(a=b)\vee(b=c)\}$ if and only if the operation is essentially unary. I would prove the equivalence of the following three conditions concerning an operation $f\colon A^n\to A$:

(1) $f$ is essentially unary.

(2) $f$ is compatible with the $3$-ary relation $R=\{(a,b,c)\in A^3\;|\;(a=b)\vee(b=c)\}$.

(3) $f$ is compatible with the $4$-ary relation $T=\{(a,b,c,d)\in A^4\;|\;(a=b)\vee (c=d)\}$.

You have already said that you have proved that (1)$\Rightarrow$(2).

To show that (2)$\Rightarrow$(3), assume that $f$ is compatible with $R$. Then $f$ is compatible with $$S = \{(a,b,c,d)\in A^4\;|\;(\exists y)((a,b,y)\in R\wedge (y,c,d)\in R)\}\\ = \{(a,b,c,d)\in A^4\;|\;(a=b)\vee(b=c)\vee(c=d)\}.$$ Therefore $f$ is compatible with $$\{(a,b,c,d)\in A^4\;|\;(a,b,c,d)\in S\wedge (b,a,c,d)\in S\} \\ = \{(a,b,c,d)\in A^4\;|\;(a=b)\vee(c=d)\vee(a=b=c)\} \\ =T.$$

To show that (3)$\Rightarrow$(1), argue the contrapositive. Assume that $f$ is not essentially unary, e.g., assume that $f$ has arity $>1$ and that it depends on its first and last variable. There must exist elements $a_i, b_j, p,q,r,s \in A$ such that $p=f(a_1,a_2,\ldots,a_{n-1},a_n)\neq f(a_1',a_2,\ldots,a_{n-1},a_n)=q$ (since $f$ depends on its first variable) and $r=f(b_1,b_2,\ldots,b_{n-1},b_n)\neq f(b_1,b_2,\ldots,b_{n-1},b_n')=s$ (since $f$ depends on its last variable). Notice that $$ f\begin{bmatrix} a_1 & a_2 & \cdots & a_{n-1} & a_n\\ a_1' & a_2 & \cdots & a_{n-1} & a_n\\ b_1 & b_2 & \cdots & b_{n-1} & b_n\\ b_1 & b_2 & \cdots & b_{n-1} & b_n'\\ \end{bmatrix} = \begin{bmatrix} p\\ q\\ r\\ s\\ \end{bmatrix} $$ is a witness to the fact that $f$ is not compatible with $T$. \\\

Keith Kearnes
  • 13,798