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

Abstract

Swierczkowski's Lemma - as it is usually formulated - asserts that if f is an at least quaternary operation on a finite set A 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 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 on arbitrary finite sets A.

11 pages, proofs simplified, contents reorganized

References in corpus (3)

• Equivalence of operations with respect to discriminator clones
• On the lattice of equational classes of Boolean functions and its closed intervals
• On the effect of variable identification on the essential arity of functions

Cited by in corpus (10)

• Decompositions of functions based on arity gap
• The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
• Reconstructing multisets over commutative groupoids and affine functions over nonassociative semirings
• The arity gap of polynomial functions over bounded distributive lattices
• Set-reconstructibility of Post classes
• On finite functions with non-trivial arity gap
• Join-irreducible Boolean functions
• Additive decomposability of functions over abelian groups
• Irreducible Boolean Functions
• Minor complexities of finite operations