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

[William Tait]

In reply to  Carniell:

> 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.
> Does anyone knows if a  similar result is  already known, or
> folklore?


on Oct 13, 2008, at 4:54 PM, Richard Zach wrote:

> I'm curious how exactly your result goes.  Surely what's undecidable  
> is
> not if a theory has property P but if some representation (e.g., a
> Turing machine enumerating theorems, a finite axiom system)  
> generates a
> theory that has P?

Yes, this is right;  but in his original statement, Carniell  
restricted P to re theories:

> 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

This is right. Let R be a set of numbers such that, if a is in R and   
a and b are re indices of the same re set (W_a = W_b), then b is in R.  
Then, by Rice,  R is null, the set of all numbers, or is undecidable.

Bill