Undecidable Semiassociative Relation Algebras
Maddux, Roger D.
J. Symbolic Logic, Tome 59 (1994) no. 1, p. 398-418 / Harvested from Project Euclid
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 $\mathscr{L}w^x$ is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in $\mathscr{L}w^x$ forms a hereditarily undecidable theory in $\mathscr{L}w^x$. These results generalize similar theorems, due to Tarski, concerning relation algebras and the formalism $\mathscr{L}^x$.
Publié le : 1994-06-14
Classification: 
@article{1183744487,
     author = {Maddux, Roger D.},
     title = {Undecidable Semiassociative Relation Algebras},
     journal = {J. Symbolic Logic},
     volume = {59},
     number = {1},
     year = {1994},
     pages = { 398-418},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744487}
}
Maddux, Roger D. Undecidable Semiassociative Relation Algebras. J. Symbolic Logic, Tome 59 (1994) no. 1, pp.  398-418. http://gdmltest.u-ga.fr/item/1183744487/