Recursive sets are not closed under
a) complementation
b) intersection
c) substitution
d) min
1
Expert's answer
2012-11-02T10:29:58-0400
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.
Numbers and figures are an essential part of our world, necessary for almost everything we do every day. As important…
APPROVED BY CLIENTS
Finding a professional expert in "partial differential equations" in the advanced level is difficult.
You can find this expert in "Assignmentexpert.com" with confidence.
Exceptional experts! I appreciate your help. God bless you!
Comments
Leave a comment