Answer to Question #17505 in Abstract Algebra for Sujata Roy

Question

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

Answer 1

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.