| Full text | |
| Author(s): |
Total Authors: 2
|
| Affiliation: | [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
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | LOGIC JOURNAL OF THE IGPL; v. 16, n. 6, p. 585-590, DEC 2008. |
| Web of Science Citations: | 1 |
| Abstract | |
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) | |
| FAPESP's process: | 04/14107-2 - Logical consequence and combinations of logics: fundaments and efficient applications |
| Grantee: | Walter Alexandre Carnielli |
| Support Opportunities: | Research Projects - Thematic Grants |