[FOM] A generalization of RIce`s theorem for logical theories
William Tait
williamtait at mac.com
Tue Oct 14 16:05:01 EDT 2008
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
More information about the FOM
mailing list