structural:reformatting, linguistic:paraphrasing
Rice's theorem and the arithmetical hierarchy

Rice showed that for every nontrivial class C (which contains some but not all c.e. sets) the index set E = { e: the e th c.e. set W is in C } has the property that either the halting problem or its complement is many-one reducible to E, that is, can be mapped using a many-one reduction to E (see Rice's theorem for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the arithmetical hierarchy. For example, the index set FIN of the class of all finite sets is on the level Σ, the index set REC of the class of all recursive sets is on the level Σ, the index set COFIN of all cofinite sets is also on the level Σ and the index set COMP of the class of all Turing-complete sets Σ. These hierarchy levels are defined inductively, Σ contains just all sets which are computably enumerable relative to Σ; Σ contains the computably enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.