[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

Does anyone knows if a  similar result is  already known, or


Walter Carnielli

Centre for Logic, Epistemology and the History of Science – CLE
State University of Campinas –UNICAMP
ICR- Dept. of Computer Science and Communications
University of Luxembourg,
Campus Kirchberg
Phones  (+352) 46 66 44   6892/ 5646

More information about the FOM mailing list