Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Texto completo
Autor(es):
Oliveira, Igor Carboni [1] ; Carnielli, Walter [2]
Número total de Autores: 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
Número total de Afiliações: 2
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
Linha de fomento: Auxílio à Pesquisa - Temático