# 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?

## Related Questions

### What is Big O of a loop with square root inside?

0  Asked on October 21, 2021 by lukasz-dynowski

### Help understanding a theorem Kleinberg proves related to sequence alignment

0  Asked on October 21, 2021 by mooglin

### Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree

0  Asked on October 21, 2021 by thunderat

### can it be said that NL^NL = NL?

2  Asked on October 21, 2021 by yankovs

### How does computer memory store the file name?

1  Asked on October 21, 2021 by shane-studio

### Why do we should not to use simple count instead of cumulative count in Counting Sort?

1  Asked on October 21, 2021 by alihaydar-gubatov

### Factoring algorithms after number field sieves

1  Asked on October 21, 2021 by zirui-wang

### How to calculate the dimension of a convex polyhedron?

1  Asked on October 21, 2021

### Difficulty in few steps in proof of “Amortized cost of $text{Find-Set}$ operation is $Theta(alpha(n))$”assuming union by rank, path compression

1  Asked on October 21, 2021

### How to determine the maximum valued play in Rummikub?

2  Asked on October 21, 2021

### Clique vs Complete Graph

2  Asked on October 21, 2021 by ninja-bug

### Why does the GS1 DataMatrix encode diagonally instead of vertically or horizontally?

1  Asked on October 21, 2021 by kittendestroyer-9000

### How to design a formal grammar to convert EBNF description to a list of CFG production rules

1  Asked on October 21, 2021 by phamsodiep

### Is protein folding really NP-hard and how to show that?

1  Asked on October 21, 2021

### Enumerator for Word and Halting Problem

1  Asked on October 21, 2021 by felixouttaspace

### Is there a way to simplify redundant conditionals?

0  Asked on October 21, 2021

### algorithm to find shortest path connecting EVERY node

1  Asked on October 21, 2021 by peter-s

### Range search in a max-heap

1  Asked on February 27, 2021

### Is deletion and insertion easier in B+ trees compared to B trees?

0  Asked on February 26, 2021 by ayush