# If $A\in RE$ then $f(A)\in RE$

Let $$A\in RE$$, and define$$f(A) = \{y |\ y= f(x),\ x\in A\}$$ for some computable function $$f$$. Then $$f(A)\in RE$$.

I can't figure out why this is true.

Since $$f$$ is computable there is a Turing machine that computes it, denote it by $$M_f$$.

Since $$A \in RE$$, we get another machine that accepts $$A$$, and obviously $$f(A)$$ is reducible from $$A$$, but given only that an input $$f(x)$$ for $$f(A)$$, is accepted iff $$x\in A$$, and $$f$$ is not necessarily injection so idk if you can get $$x$$.

Given that $$A\in RE$$, there is a counter machine for it, and since $$f$$ is computable then there is a Turing machine that prints $$f(x)$$ for a given $$x \in A$$, so what we could do is count each word in $$A$$ one by one, and for each one simulate $$f$$ on that word and that would result in a counter machine for $$f$$, i.e. $$f$$ is recursively enumerable, so we get $$f\in RE$$.
• For convenience apply two equivalent definitions of RE. To prove that $f(A)$ is RE use the definition that there is a Turing machine that halts exactly for the elements of $f(A)$. However, translate that $A$ is RE using the equivalent definition that there is a Turing machine that lists $A$. To construct the machine that halts at the elements of $f(A)$, you can do the following: Given a $y$, run the machine that lists the elements of $A$. For each output $x_i\in A$ give them to the machine that computes $f(x_i)$ and check if $f(x_i)=y$. If it is true, halt. If not, continue to the next $x_i$.
• That’s exactly what I did I think, only difference was that I called that machine that lists $A$ a counter. Commented Jul 24, 2020 at 18:47