Undecidable semiassociative relation algebras
Roger D. Maddux · Journal of Symbolic Logic · 1994
Abstract If K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism ℒw× is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in ℒw× forms a hereditarily undecidable theory in ℒw×. These results generalize similar theorems, due to Tarski, concerning relation algebras and the formalism ℒ×.