# 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
##### Keywords:
Rice’s theorem; undecidable; Turing machine
Full Text: