On complete and independent sets of operations in finite algebras
Jean W. Butler · Pacific Journal of Mathematics · 1960
In [4] Post obtained a variety of results about truth functions in 2-valued sentential calculus.He studied sets of truth functions which could be used as primitive notions for various systems of 2-valued logics.In particular, he was interested in complete sets of truth functions, i.e., sets having the property that every truth function with an arbitrary finite number of arguments is definable in terms of the truth functions belonging to the set.Among other results Post established a computable criterion for a set of truth functions to be complete.Using this criterion he showed that there is a finite upper bound for the number of elements in any complete and independent set of primitive notions for the 2-valued sentential calculus (and that actually the number 4 is the least upper bound).Alfred Tarski has asked to what extent these results can be extended to ^-valued sentential calculus, for any finite n.It will be seen from this note that those results of Post concerning complete sets of truth functions can actually be extended.On the other hand it has been shown recently by A. Ehrenfeucht that the result concerning arbitrary sets of functions cannot be extended.Both the results of Post and those of this note can be formulated in terms of truth functions of the 2-valued (w-valued) sentential calculus or in terms of finitary operations in arbitrary 2 element (n element) algebras.We choose the second alternative since the many-valued sentential calculi have a rather restricted significance in logic and mathematics.Thus we shall concern ourselves with finitary operations under which a given set A with n elements is closed.For simplicity we restrict our attention to the case when A is the set N of all natural numbers less than n.This restriction implies no loss of generality, since all the results can be extended by isomorphism to any finite set with n elements.For convenience we will identify N with n f as is frequently done in modern set theory.For any given natural number fc, let n k be the set of all /c-termed sequences x = ζx 0 , x lf , x k -ϊ) with terms in n.Denote by F nιJC the set of all fc-ary operations on and to elements of n, i.e., of all function