Operations on Finite Sets, Functional Composition, and Ordered Sets

doctoral dissertation, Tampere University of Technology, Publication 680, Tampere, 2007
http://urn.fi/URN:NBN:fi:tty-200810021063

The unifying theme of this research work is functional composition. We study operations on a nonempty set A, an important particular case being that of Boolean functions when A = {0, 1}. A class of operations is a subset of the set of all operations on A. A clone on A is a class of operations on A that contains all projection maps and is closed under functional composition.

The first part of this thesis is a study of compositions of the clones of Boolean functions. The clone of all Boolean functions can be decomposed in various ways into minimal clones, and we observe that such decompositions correspond to different normal form systems: the disjunctive normal form (DNF), conjunctive normal form (CNF), Zhegalkin polynomial, dual Zhegalkin polynomial, and so-called median normal form. These normal form systems are compared in terms of efficiency, and we establish that the median normal form system provides in a certain sense more efficient representations than the other four normal form systems mentioned above.

The second part of this thesis is a study of certain order relations on the set of all operations on A. For a fixed class C of operations on A, we say that f is a C-subfunction of g, if f can be obtained by composing g from inside with operations from C. We say that f and g are C-equivalent, if f and g are C-subfunctions of each other. The C-subfunction relation is a quasiorder (a reflexive and transitive relation) on the set of all operations on A if and only if the parametrizing class C is a clone.

The simplest example of C-subfunction relations is obtained when C is the smallest clone I of projections on A. Forming I-subfunctions corresponds to simple manipulation of variables, namely addition and deletion of dummy variables, permutation of variables, and identification of variables. None of these operations increases the number of essential variables, and only variable identification may decrease this number. We study more carefully the effect of variable identification on the number of essential variables of operations on finite base sets. We then study certain order-theoretical properties of various C-subfunction partial orders defined by larger clones C on finite base sets A. We are mostly concerned about the descending chain condition and the existence of infinite antichains, and as it turns out, these properties on the defining clone C.

Homomorphisms of labeled posets (or k-posets) are applied in our analysis of subfunction relations defined by clones of monotone functions. The third part of this thesis is a study of the homomorphicity order of finite k-posets on its own right. We establish that this order is a distributive lattice, and furthermore, it is universal in the sense that every countable poset can be embedded into it. This result implies universality of the subfunction partial orders defined by clones of monotone functions on finite sets of more than two elements. In this way, we also obtain a new proof for the well-known universality of the homomorphicity order of graphs.