Question #17505

Recursive sets are not closed under
a) complementation
b) intersection
c) substitution
d) min

Expert's answer

Lemma 6.3.5

For any indexing of the partial recursive functions, the complement K of the set K={x∈N| ϕx(x)converges}is notrecursively enumerable.

Proof. If K was recursively enumerable, since K is also recursively enumerable, by Lemma 6.3.2, the set K would be recursive, a contradiction.

The sets K and K0 are examples of sets that are not r.e.This shows that the r.e. sets are not closed under complementation. However, we

leave it as an exercise to prove that the r.e. sets are closed under union and intersection.

For any indexing of the partial recursive functions, the complement K of the set K={x∈N| ϕx(x)converges}is notrecursively enumerable.

Proof. If K was recursively enumerable, since K is also recursively enumerable, by Lemma 6.3.2, the set K would be recursive, a contradiction.

The sets K and K0 are examples of sets that are not r.e.This shows that the r.e. sets are not closed under complementation. However, we

leave it as an exercise to prove that the r.e. sets are closed under union and intersection.

## Comments

## Leave a comment