Reports on Mathematical Logic

No. 29 (1995)


Jerzy HANUSEK

DECIDABILITY OF FINITE BOOLEAN ALGEBRAS WITH A DISTINGUISHED SUBSET CLOSED UNDER SOME OPERATIONS

A b s t r a c t. In 1920 Emil Post classified all possible clones of functions on the set 2={0,1}, and gave a set of generating functions for each of them (see [1], [2]). For a clone C we define a class of structures ${\bf\cal B}_{C} = \{ \langle 2^{X},\cap, \cup, \neg, A_{C}\rangle: X$ is finite }, where $\langle 2^{X}, \cap, \cup,\neg \rangle $ is a Boolean algebra and $A_{C}$ is a unary relation distinguishing a subset closed under operations from $C$. Let $Th(B_{C})$ be the first order theory of ${\bf\cal B}_{C}$. In the present paper we show that the theory $Th(B_{C})$ is decidable iff a clone $C$ contains the ternary discriminator.


Back to Main Menu