DIAMONDS AND DOMINOES: IMPOSSIBILITY RESULTS FOR ASSOCIATIVE MODAL LOGICS

Abstract We show that for any class of Boolean algebras with an associative operator, if it contains the complex algebra of ( P ( N ) , ∪ ) $(\mathcal {P}(\mathbb {N}), \cup )$ left parenthesis script upper P left parenthesis double struck upper N right parenthesis comma union right parenthesis , its equational theory is undecidable. Equivalently, any associative normal modal logic valid over the frame ( P ( N ) , ∪ ) $(\mathcal {P}(\mathbb {N}), \cup )$ left parenthesis script upper P left parenthesis double struck upper N right parenthesis comma union right parenthesis is undecidable. This settles a long-open question on the decidability of hyperboolean modal logic [16], and addresses several related problems.