76 972
Assignments Done
Successfully Done
In June 2019

Answer to Question #17505 in Abstract Algebra for Sujata Roy

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.

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!


No comments. Be first!

Leave a comment

Ask Your question

Privacy policy Terms and Conditions