×

On subalgebras of an algebra of predicates. (English) Zbl 0578.03033

This paper deals with (composition) closed sets of operations on finite sets. For the general theory see the monograph of S. V. Yablonskij, G. P. Gavrilov and V. B. Kudryavtsev: Functions of the algebra of logic and Post classes (Russian) (1966; Zbl 0171.277). Specifically the algebra \(P_{k,2}\) of all two-valued operations on the set \(E_ k=\{0,1,...,k-1\}\) (k\(\geq 3)\) is investigated. A tool the Authors employ is the ”projection” pr from \(P_{k,2}\) to \(P_ 2:\) \(prf=g\) iff f, g are of the same arity and take the same value on arguments in \(E_ 2\). Sample of results: (i) The inverse image (under pr) of a closed set of Boolean functions containing \(0_ 1\) is finitely generated. (ii) If A is closed and contains \(0_ 1\), then \(pr^{-1}(A)\) contains a Sheffer function for \(pr^{-1}(A)\) iff A contains a Sheffer function for A. (iii) There is an infinite chain of closed sets between \(P_ k\) and \(P_{k,2}\). They also give (without proofs) the cardinalities of the sets of all closed subsets of \(P_{3,2}\) whose projection is a given \(A\subseteq P_ 2\), for various A, as well as the Hasse diagram depicting some fragments of the lattice of closed sets in \(P_{3,2}\).
Reviewer: A.Ursini

MSC:

03G25 Other algebras related to logic
08A40 Operations and polynomials in algebraic structures, primal algebras

Citations:

Zbl 0171.277