Computably enumerable closed under inverse image

Question

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a computable function and let $A \subseteq \mathbb{N}$ be computably enumerable. I'm trying to find a reason why the inverse image $f^{-1}(A)$ is also $c.e.$, but can't seem to work it out.

Also, are there any other nice properties of $c.e.$ sets (besides unions and intersections)?

Thanks in advance!

Answer 1

First, given $n$ there is an algorithm which will return True if $n\in f^{-1}(A)$ (although it may never return if $n\notin f^{-1}(A)$): Get the first element $a$ of $A$, check whether $f(n)=a$. If not get the next element $a$ of $A$ and check whether $f(n)=a$. If not...

(When I talk about the first element of $A$ and the next element I'm not talking about their numerical order; rather the order in which they're returned by the procedure that enumerates $A$.)

So now we have a sequence of tasks:

1. Try to decide whether $1\in f^{-1}(A)$.

2. Try to decide whether $2\in f^{-1}(A)$.

etc.

So do the usual thing: Spend one second on these tasks, in order 1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,... .