Let A ≤m B denotes that language A is mapping reducible

Home » Theory of Computation » Theory of computation miscellaneous » Question

Let A ≤_m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B.
Which one of the following is FALSE?

1. If A ≤_m B and B is recursive then A is recursive.
2. If A ≤_m B and A is undecidable then B is undecidable.
3. If A ≤_m B and B is recursively enumerable then A is recursively enumerable.
4. If A ≤_m B and B is not recursively enumerable then A is not recursively enumerable.

Correct Option: D

If B is not recursively enumerable then A need not be recursively enumerable.