Generalizations of Świerczkowski’s lemma and the arity gap of finite functions

Świerczkowski’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 on 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 Świerczkowski’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 on arbitrary finite sets A .