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