Rice's Theorem

A nontrivial Index Set cannot be computable.

Proof

Let be The Halting Problem.
For a fixed consider the following function

Note that is computable, as we can run
and if then it will diverge.
Otherwise, we run .

By The s-m-n Theorem we get a computable function
such that

If then .
If then
Let be an Index Set.
Fix some such that .
Then either or .

Case 1

If then find some .
We claim that is a reduction from to .
If then so .
If , then , so .
This proves so is not computable.

Case 2

If by similar arguments find
and prove that reduces to .
Then so is not computable.