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

Computer Science Asked by se718 on January 2, 2022

Let $$Ain RE$$, and define$$f(A) = {y | y= f(x), xin 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 $$xin A$$, and $$f$$ is not necessarily injection so idk if you can get $$x$$.

Given that $$Ain 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 $$fin RE$$.

Any idea if this is true? if not, how can this be proved?