[FOM] A generalization of RIce`s theorem for logical theories
carniell@cle.unicamp.br
carniell at cle.unicamp.br
Sun Oct 12 20:32:23 EDT 2008
Rice's theorem (sometimes called Rice-Shapiro) proves that any
property defined over the set of languages accepted by Turing
machines is either trivial or undecidable
While dealing with the question on how to classify properties of
fist -order theories as decidable or not, we (my student Igor
Carboni and I) found the following simple (but useful) result:
A property P defined over the collection of all first-order
theories is said to be "non-trivial" if it holds for some, but
not all theories. Then any non-trivial property P is undecidable.
This result may simplify (or unify) some undecidability results
in first-order theories.
For example. it implies directly that there is no algorithm that
is able to decide if two sets of axioms give rise to the same
theory.
Does anyone knows if a similar result is already known, or
folklore?
Regards
Walter Carnielli
+++++++++++++++++++++++++++++++++++
Centre for Logic, Epistemology and the History of Science – CLE
State University of Campinas –UNICAMP
and
ICR- Dept. of Computer Science and Communications
University of Luxembourg,
Campus Kirchberg
Luxembourg
Phones (+352) 46 66 44 6892/ 5646
http://icr.uni.lu/
http://www.cle.unicamp.br/prof/carniell
More information about the FOM
mailing list