×

zbMATH — the first resource for mathematics

The Ricean objection: An analogue of Rice’s theorem for first-order theories. (English) Zbl 1159.03028
Log. J. IGPL 16, No. 6, 585-590 (2008); erratum ibid. 17, No. 6, 803-804 (2009).
H. G. Rice [Trans. Am. Math. Soc. 74, 358–366 (1953; Zbl 0053.00301)] proved that any property defined over the set of languages accepted by a Turing machine is either trivial or undecidable. The authors prove an analogue of Rice’s theorem for first-order theories expressed in the language \(\{0, s, +, \cdot\}\) (\(0\) being a constant, \(s\) a unary operation, and \(+\) and \(\cdot\) binary operations), stating that, for any nontrivial property of first-order theories, it is undecidable whether the theory axiomatized by a given finite set of axioms has that property. The short proof uses Robinson’s \(Q\).

MSC:
03D35 Undecidability and degrees of sets of sentences
PDF BibTeX XML Cite
Full Text: DOI