The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories

Autor(es)

Oliveira, Igor Carboni ^[1] ; Carnielli, Walter ^[2]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, UNICAMP, Ctr Log Epistemol & Hist Sci CLE, BR-13083970 Campinas, SP - Brazil

^[2] Univ Estadual Campinas, UNICAMP, Dept Philosophy IFCH, BR-13083970 Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: LOGIC JOURNAL OF THE IGPL; v. 16, n. 6, p. 585-590, DEC 2008.
• Citações Web of Science: 1

Resumo

We propose here an extension of Rice's theorem to first-order logic, proven by totally elementary means. If P is any property defined over the collection of all first-order theories and P is non-tricial over the set of finitely axiomatizable theories (i.e., P holds for some, but not all theories), then P is undecidable. This not only means that the problem of deciding properties of first-order theories is as hard as the problem of deciding properties about languages accepted by Turing machines, but also offers a general setting for proving several undecidability results in first-order theories. (AU)

• Processo FAPESP: 04/14107-2 - Logical consequence and combinations of logics: fundaments and efficient applications
• Beneficiário: Walter Alexandre Carnielli
• Modalidade de apoio: Auxílio à Pesquisa - Temático