Cheap and Secure Web Hosting Provider : See Now

# Can a $k$-ary relation have polymorphisms of arity greater than $k$?

, ,
Problem Detail:

To quote Hubie Chen's A Rendezvous of Logic, Complexity, and Algebra (2009) on constraint satisfaction and complexity,

An operation $f : D^m \to D$ is a polymorphism of a relation $R \subseteq D^k$ if, for any choice of $m$ tuples $(t_{11}, ... , t_{1k}), ... , (t_{m1}, ... , t_{mk})$ from $R$, it holds that the tuple obtained from these $m$ tuples by applying $f$ coordinate-wise, $( f (t_{11}, ... , t_{m1}), ... , f (t_{1k}, ... , t_{mk}))$, is in $R$.

Two examples follow, but neither answers this question. Let's say that there's a relation $R$ and function $f$ such that $m > k$. Is $f$ a polymorphism of $R$?

Concrete example: Assuming an $\wedge$ relation $\{ (1,1) \}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

###### Answered By : David Richerby

Let's say that there's a [$k$-ary] relation $R$ and [$m$-ary] function $f$ such that $m>k$. Is $f$ a polymorphism of $R$?

Maybe, maybe not: it depends on the function and the relation. A given $k$-ary relation may have polymorphisms of arity arity less than, equal to, and/or greater than $k$. In fact, every relation has polymorphisms of all arities. For example, the ($1$-ary) identity function is a polymorphism of every relation, as are the projection functions $f_\ell(x_1, \dots, x_m) = x_\ell$ for all $1\leq \ell\leq m$. (Exercise: check these examples.) Notice that the identity function is just the case $\ell=m=1$.

Concrete example: Assuming an $\wedge$ relation $\{ (1,1) \}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

Check the definition! $f$ is a polymorphism of $R_\land = \{(1,1)\}$ if, and only if, for all $(x_1,x_2),(y_1,y_2),(z_1,z_2)\in R_\land$, we have $(f(x_1,y_1,z_1),f(x_2,y_2,z_2))\in R_\land$. Well, the only tuple in $R_\land$ is $(1,1)$, so we only care about the case $x_1=y_1=z_1=x_2=y_2=z_2=1$. And we see that $f(1,1,1)=1$, so $(f(1,1,1),f(1,1,1))\in R_\land$, so $f$ is, indeed, a polymorphism of $R_\land$. Further, by exactly the same argument, any function such that $f(1, \dots, 1) = 1$ is a polymorphism of $R_\land$.

The polymorphism property is often represented as a table: given a $k$-ary relation $R$ and an $m$-ary function $f$, we can write

$$\begin{matrix} (t_{1,1} & t_{1,2} & \cdots & t_{1,k}) & \in R\\ (t_{2,1} & t_{2,2} & \cdots & t_{2,k}) & \in R\\ \vdots & \vdots & \ddots & \vdots & \\ (t_{m,1} & t_{m,2} & \cdots & t_{m,k}) & \in R\\ \hline (f(t_{1,1}, \dots, t_{m,1}) & f(t_{1,2}, \dots, t_{m,2}) &\cdots & f(t_{1,k}, \dots, t_{m,k})) &\in R \end{matrix}$$

The meaning is that we require that, whenever the tuples above the line are in $R$, the tuple below the line must also be in $R$. Notice that nothing in the structure of the table requires any relation between $k$ and $m$: the property could hold (or not hold) for a relation of any arity and a function of any arity. It's just required that, whenever we write a collection of tuples in $R$ and "apply $f$ to each column", the resulting tuple is always still in $R$.