Negative solution of the decision problem for sentences true in every subalgebra of 〈N, +〉

Publisher Website
Google Scholar
Abstract
It was shown by Taiclin [6], and independently announced by Tarski [7], that the elementary theory of commutative cancellation semigroups is hereditarily undecidable. In his proof Tarski exhibited a subsemigroup of 〈N, ·〉, the natural numbers with multiplication, whose theory is both hereditarily and essentially undecidable. (The details of his construction were published by V. H. Dyson [1].) In connection with these results, Tarski suggested to the author that it would be of interest to solve the decision problem for the theory K which consists of all elementary sentences which are true in every subalgebra (i.e. every subsemigroup) of 〈N, +〉. The object of this note is to prove that the theory K is hereditarily undecidable.

This publication has 2 references indexed in Scilit: