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

Logic Journal of the IGPL 16 (6):585-590 (2008)

Walter Carnielli
University of Campinas
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-trivial over the set of finitely axiomatizable 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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1093/jigpal/jzn023
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,330
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
A Topological Analog to the Rice-Shapiro Index Theorem.Louise Hay & Douglas Miller - 1982 - Journal of Symbolic Logic 47 (4):824-832.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Local Order Property in Nonelementary Classes.Rami Grossberg & Olivier Lessmann - 2000 - Archive for Mathematical Logic 39 (6):439-457.
Proof-Theoretical Analysis of Order Relations.Sara Negri, Jan von Plato & Thierry Coquand - 2004 - Archive for Mathematical Logic 43 (3):297-309.
Unidimensional Theories Are Superstable.Ehud Hrushovski - 1990 - Annals of Pure and Applied Logic 50 (2):117-137.
On Translations of Complete First Order Theories.Seyed Mohammad Bagheri - 2003 - Mathematical Logic Quarterly 49 (1):87-91.
Fregean Extensions of First‐Order Theories.John L. Bell - 1994 - Mathematical Logic Quarterly 40 (1):27-30.
A Completeness Theorem for Higher Order Logics.Gábor Sági - 2000 - Journal of Symbolic Logic 65 (2):857-884.


Added to PP index

Total views
6 ( #998,144 of 2,286,097 )

Recent downloads (6 months)
4 ( #319,399 of 2,286,097 )

How can I increase my downloads?


My notes

Sign in to use this feature