Computability Hierarchy

sets

A set is called if there is a Computable such that for all we have

Theorem

A set is if and only if it is Computably Enumerable.

Proof

By the previous definition, search for such that . If it exists, we will find it. If it doesn’t, the program diverges. Suppose is Computably Enumerable. Let be a machine that lists all members of . Construct the set such that iff lists in step . Then is Computable, so is .

Proposition

The class of sets is not closed under complementation.

Proof

The Halting Problem

sets

A set is called if it is a complement of a set.

Proposition

A set is if and only if there is a Computable such that for all we have

sets

A set is called if it is both and .

Proposition

A set is Computable if and only if it is a set.

Proof

A set is iff it is Computably Enumerable. It is easy to see that for a Computable set, it is computably enumerable. It’s complement is also computable, so computably enumerable. To go the other way, list all the elements of and in alternating order, because both and are computably enumerable. But this will list all elements of input space so will be Computable.