UNDECIDABILITY OF THE THEORIES OF CLASSES OF STRUCTURES. (12th December 2014)

• Record Type: Journal Article
• Authors: KACH, ASHER M.; MONTALBÁN, ANTONIO
• Is Part Of: Journal of symbolic logic. Volume 79:Number 4(2014)
• Page Start: 1001
• Page End: 1019
• Publication Date: 2014-12-12
• Subjects: bi-interpretability, -- second-order arithmetic, -- Tarski's Cube Problem, -- classes of structures; Logic, Symbolic and mathematical -- Periodicals; 511.3
• DOI: 10.1017/jsl.2014.54
• Languages: English
• ISSNs: 0022-4812

Abstract

Abstract: Many classes of structures have natural functions and relations on them: concatenation of linear orders, direct product of groups, disjoint union of equivalence structures, and so on. Here, we study the (un)decidability of the theory of several natural classes of structures with appropriate functions and relations. For some of these classes of structures, the resulting theory is decidable; for some of these classes of structures, the resulting theory is bi-interpretable with second-order arithmetic.