Generalizations of Świerczkowski's lemma and the arity gap of finite functions (Q1045078): Difference between revisions

Świerczkowski's lemma asserts that if \(f:A^n\rightarrow A\) is an \(n\)-ary operation on a finite set \(A\), where \(n\geq 4\), and if every operation obtained from \(f\) by identifying a pair of variables is a projection, then \(f\) is a semiprojection, i.e., there exists a projection \(p:A^n\rightarrow A\) such that \(p\) and \(f\) agree on all tuples that have at least two equal entries. The authors present the following generalization of this lemma: If \(f:A^n\rightarrow B\) is an \(n\)-ary function from a finite set \(A\) to a set \(B\), where \(n=2\) or \(n\geq 4\), and if every operation obtained from \(f\) by identifying a pair of variables depends on exactly one variable, then there exists a function \(g: A^n\rightarrow A\) which depends on exactly one variable such that \(g\) and \(f\) agree on all tuples that have at least two equal entries. A result due to \textit{R. Willard} [``Essential arities of term operations in finite algebras'', Discrete Math. 149, No.~1--3, 239--259 (1996; Zbl 0840.08005)] states that if \(f: A^n\rightarrow B\) depends on all of its variables, and \(n>|A|\), then there is a function obtained from \(f\) by identifying two variables which depends on at least \(n-2\) of its variables. In the present paper, this result is generalized. Finally, the authors classify functions \(f: A^n\rightarrow B\) according to their arity gap, i.e., the minimal drop in essential arity that occurs when two variables of \(f\) are identified.