Question

Consider the following statements:
S1] If a language is decidable then every proper subset of that language is decidable.
S2] If A≤_m B and B is a regular language then A is regular.
Which of the following statement/s is/are true

1.   Only S1 is true
2.   Only S2 is true
3.   Both S1 and S2 is true
4.   None of these

Comments

S₁ is False for sure

Don't know about S₂ (false mostly, not sure)

What is answer?

---

how can you be sure about S1?ANY EXAMPLE?

and by reduction property,A should also be regular..right??

Answer 1

S2 means Language A is mapping reducible to language to B
But here it is asking for a regular langauge So,if B is regular then A is not always regular...

S1 is false we can take example as A= Σ∗ which is regular and hence decidable and we can take any proper subset of A which is undecidable (like R.E language)

Comments

by R,do you mean regular?

so reduction theorem only works for recurswive and r.e..?bot for others??

---

@bad_engineer,what is meant by mapping reducible..??are there diff kinds of reduction?

---

@Akriti

There are two types of reductions : 1] Many to one reduction (Mapping reductions) and 2] Turing reductions

I'd suggest not to dig deeper as complexity classes are not in syllabus now.