The Ricean objection: An analogue of Rice’s theorem for first-order theories. (English) Zbl 1159.03028

Oliveira, Igor Carboni; Carnielli, Walter

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\).

Reviewer: Victor V. Pambuccian (Phoenix)

MSC:

03D35

Undecidability and degrees of sets of sentences

Keywords:

Rice’s theorem; undecidable; Turing machine