[FOM] A generalization of RIce`s theorem for logical theories

[carniell@cle.unicamp.br]

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