Recursive Enumerable Language Doubt

Question

We know, Recursive Enumerable Language is not closed under complement. 

a) So, let's say Y is a R.E language and recursive, then what would be Y' (Y complement)?

b) Again Y is a R.E language, but this time Y is not recursive then what would be Y' (Y complement)?

Thank you! 

P.S - I get that answer for b) is Y' (Y complement) is not R.E, but why? and also please explain option a)

Answer 1

a)If $Y=\text{Recursive Enumerable and also recursive }$

Then $Y^{'}$ will be Recursive  Enumerable as well as recursive.

Explanation-:

$Y$ is recursive and recursive are closed under complementation, so $Y^{'}$ is also Recursive and so is Recursive enumerable.

---

b)$Y^{'}=\text{Not a  Recursive Enumerable }$

Explanation-:

Recursive enumerable languages are not closed under complementation.It signifies that $Y^{'}$ may/may not  be recursive enumerable.But the answer will be $Y^{'}$ is not recursive Enumerable.

Why?

Because if $Y^{'}$ will be recursive Enumerable then, we have got a theorem that states-:

If a language and its complement are both recursively enumerable, then both are recursive.
 

So According to theorem ,$Y$ will be recursive then which contradicts your answer.

Hence $Y^{'}$ is non-recursive language.

Comments

@  :sourav
Little confused with you A part althought B is correct as per my understanding.
Reason being :
If Y is both RE and REC then its partial decidable but if Y` is also RE then both are recursive which is not the case so i think Y` should be REC only.
please correct me.!

---

@ sourav.  isn't R.E not closed under complementation means, it may or may not be R.E i.e it's a maybe case.

---

@saxena: $Y^{'}$ will be recursive , i have aleady written it.

Any recursive language will be indeed recursive enumerable too

@iarnav  see the updated answer

---

@saxena :i am not getting your abbreviations for recursive and recursive enumerable.so i am misunderstanding your question

Answer 2

Any language that is regular is also CFL , CSL , recursive and recursively enumerable

So if a language is regular it can also be recursively enumerable

regular languages are closed under complement

but can u say if a language is recursively enumerable as well as regular then it shouldnt be closed under complement

it is regular first ..thats why it is recursively enumerable

similarly in your doubt ,,,,it is recursive first and thats why it is recursively enumerable

so u apply the case with recursive

It works upwards

all regular languages are DCFL , CFL , CSL ,recursive and recursively enumerable

all cfl are csl , recursive and recursively enumerable

similarly all recursive are recursively enumerable

hope am clear enuff