Decidability and structure
Paweł Idziak · Banach Center Publications · 1999
An important and fundamental area of research in Mathematical Logic has been an attempt to classify and understand those structures or collections of structures that have decidable theories. A structure is said to be decidable if there is an algorithm to decide precisely which sentences (taken from a language appropriate for the structure) are true of the structure. The study of the decision problem for various classes of structures began in the 1930’s when Church gave the first undecidability result. In Algebra one primarily studies collections of algebras known as varieties (that is classes of algebras closed under subalgebras, products and homomorphic images, or equivalently classes defined by a set of equations). Over past few decades there has been a systematic attempt to classify decidable varieties. Soon after the appearance of the undecidability result of A. Church and J. B. Rosser, namely that Peano’s arithmetic is undecidable, A. Tarski took over and developed in 1938–39 a general framework for proving the undecidability of first-order theories. The method was used by himself and many others to obtain a wide spectrum of undecidable varieties, including