We are given that $ A \leq_m B $ denotes mapping reducibility (also called many-to-one reducibility) from language $ A $ to language $ B $. This means there exists a computable function $ f $ such that for all $ x $:
$$
x \in A \iff f(x) \in B.
$$
Option A: If $ A \leq_m B $ and $ B $ is recursive, then $ A $ is recursive.
This is TRUE.
If $ B $ is recursive, there exists a decider $ M_B $ for $ B $. To decide $ A $, construct a machine $ M_A $ that on input $ x $:
- Computes $ f(x) $ (since $ f $ is computable).
- Runs $ M_B $ on $ f(x) $.
- Accepts if $ M_B $ accepts; rejects otherwise.
Since both steps halt, $ M_A $ halts on all inputs and correctly decides $ A $. Hence, $ A $ is recursive.
Option B: If $ A \leq_m B $ and $ A $ is undecidable, then $ B $ is undecidable.
This is TRUE.
We prove the contrapositive: if $ B $ is decidable, then $ A $ is decidable which we just proved in Option A. Therefore, if $ A $ is undecidable, $ B $ cannot be decidable so $ B $ must be undecidable.
Option C: If $ A \leq_m B $ and $ B $ is recursively enumerable, then $ A $ is recursively enumerable.
This is TRUE.
If $ B $ is r.e., there exists a Turing machine $ M_B $ that accepts exactly the strings in $ B $. To recognize $ A $, construct a machine $ M_A $ that on input $ x $:
- Computes $ f(x) $.
- Simulates $ M_B $ on $ f(x) $.
- Accepts if $ M_B $ accepts.
If $ x \in A $, then $ f(x) \in B $, so $ M_B $ will eventually accept, and thus $ M_A $ accepts. If $ x \notin A $, then $ f(x) \notin B $, so $ M_B $ may loop or reject but since we only require recognition (not rejection), this is acceptable for r.e. languages.
Hence, $ A $ is recursively enumerable.
Option D: If $ A \leq_m B $ and $ B $ is not recursively enumerable, then $ A $ is not recursively enumerable.
This is FALSE.
Counterexample:
Let $ A = \emptyset $ (which is recursive, hence r.e.). Let $ B $ be any non-recursively enumerable language (e.g., the complement of the acceptance problem $ \overline{A_{\text{TM}}} $).
Define $ f(x) = w_0 $, where $ w_0 \notin B $ (possible because $ B \neq \Sigma^* $, as it’s not r.e.).
Then:
- $ x \in A \iff f(x) \in B $ becomes:
- False $ \iff $ False → always true.
So $ A \leq_m B $ holds.
But $ A = \emptyset $ is recursively enumerable (in fact, recursive), while $ B $ is not r.e.Thus, even though $ B $ is not r.e., $ A $ can still be r.e. so the implication fails.
Therefore, Option D is false.
$$
\color{lime} \boxed{\text{Answer: D}}
$$
