Index Set

A set is called an index set
if it is closed under weak equivalence
(i.e. if then )
Rice’s Theorem

Examples

• 
  The proof of Rice’s Theorem shows that and
  .

Proposition

Proposition

is neither nor .
Computability Hierarchy