A <many-one reduction> $A\leq_mB$ is a <total computable function> $f:\mathbb N\to\mathbb N$ with $x\in A\iff f(x)\in B$. If $B$ is <recursively enumerable>, compute $f(x)$ and run a semidecision procedure for $B$ on that value. It halts exactly when $x\in A$, so \b[$A$ is <recursively enumerable>]. Totality of $f$ is essential to this argument.

Solution

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 11H / a / Solution

 Solution (source code)