##
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