Generalizations of Swierczkowski's lemma and the arity gap of finite functions

摘要

Swierczkowski's lemma - as it is usually formulated - asserts that if f . A(n) -> A is an operation on a finite set A, n >= 4, and every operation obtained from f by identifying a pair of variables is a projection. then f is a semiprojection We generalize this lemma in various ways. First. it is extended to B-valued functions on A instead of operations oil A and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Swierczkowski's lemma. Moreover, we explicitly classify all pseudo-Boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of B-valued functions oil arbitrary finite sets A (C) 2009 Elsevier E.V. All rights reserved.