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.