I've recently been interested in the following type of functions. A total computable function *f*:**N**→**N** is *effectively closed* if there is a computable function *p* such that *f*[**N** \ We] = **N** \ W*p*(e), where We is the e-th c.e. set.



> 
> Have effectively closed functions been studied? If so, what are they normally called?
> 
> 
> 


I would also appreciate pointers to some uses and/or alternative characterizations of effectively closed functions.


**Motivation.** It is well-known that there is a near-perfect analogy between the adjectives *computable* and *continuous*. For example, a total function *f*:**N**→**N** is computable if and only if it is effectively continuous, i.e. there is a computable function *p* such that *f*-1[We] = W*p*(e). [For the backward implication, let *q* be a computable function such that W*q*(n) = {n} and use the composite *p*∘*q* to enumerate the graph of *f*.] A similar trick shows that a total function is effectively open if and only if it is computable. However, a total computable function is not necessarily effectively closed since that entails that the range of *f* is computable and, indeed, that *f* maps every computable set onto a computable set. Also, the notion is nontrivial since non-constant polynomials and increasing functions are effectively closed.




---


**Update.** Joel David Hamkins gave the following characterization of effectively closed computable functions: they are the computable functions *f*:**N**→**N** for which there is a computable *b*:**N**→**N** such that *f*-1(n) ⊆ {0,1,...,b(n)} for every n ∈ **N**. Although I accepted Joel's answer, the main question is still open.



Effectively closed computable functions
I like your concept a lot, and have been able to find a characterization.


Suppose that $f:N\to N$ is effectively closed in your sense.


First, as you mentioned, it is easy to see that $\text{ran}(f)$ is
computable, since by taking $W\_e$ to be empty your equation shows that
$\text{ran}(f)$ is both c.e. and co-c.e.


Second, I claim that $f$ is finite-to-one. To see this,
 suppose that $f^{-1}(k)$ is infinite for some $k$. Define
 a c.e. set $W\_e$ as follows: At stage $s$, if we see that
 $k$ is still not in $W\_{\rho(e),s}$, the state-$s$ approximation
 to $W\_{\rho(e)}$, then enumerate the next element of
 $f^{-1}(k)$ into $W\_e$. (Although this definition may look
 circular, since I am defining $W\_e$ by reference to
 $W\_{\rho(e)}$, the definition is legitimate by an
 application of the Recursion Theorem. That is, I really
 define $W\_{r(e)}$, and then find $e$ such that $W\_e=W\_{r(e)}$.)
 Note that if $k$ is never enumerated into $W\_{\rho(e)}$,
 then I will eventually put all of $f^{-1}(k)$ into $W\_e$,
 which will result in $k\notin f[N-W\_e]$, but $k\in
 N-W\_{\rho(e)}$, a contradiction. Alternatively, if $k\in
 W\_{\rho(e),s}$, then $f^{-1}(k)\cap W\_e$ has at most
 $s$ members, and so there are $a\in N-W\_e$ with $f(a)=k$,
 placing $k$ into $f[N-W\_e]$ but not in $N-W\_{\rho(e)}$,
 again a contradiction.


A similar argument shows actually that the
 function $k\mapsto f^{-1}(k)$ is computable. Namely,
 define the set $W\_e$ by the following procedure. At stage
 $s$, look at every $k\leq s$, and if $k\notin
 W\_{\rho(e),s}$, then enumerate all of $f^{-1}(k)\cap s$ into
 $W\_e$. (Again, appeal to Recursion Theorem to get such an
 $e$.) In other words, as long as $k$ is not in
 $W\_{\rho(e),s}$, then we put all elements of $f^{-1}(k)$
 below $s$ into $W\_e$.


If $k\notin W\_{\rho(e)}$, then $f^{-1}(k)\subset W\_e$, and
 so $k\notin f[N-W\_e]$, contradicting $k\in N-W\_{\rho(e)}$.
 Thus, $W\_{\rho(e)}=N$. From this, it follows that $W\_e=N$.
 Now, note that $k\in W\_{\rho(e)}$ implies $k\in W\_{\rho(e),s\_k}$
 for some stage $s\_k$, and so $f^{-1}(k)$ is a subset of $s\_k$.
 By applying $f$ to each value below $s\_k$, we see that the
 map $k\mapsto f^{-1}(k)$ is a computable function.


This means that $f$ has a particularly simple form.
 Namely, there is a computable partition $N=\bigsqcup\_k
 B\_k$, with each $B\_k$ finite, such that $f$ maps elements of
 $B\_k$ to $k$. (Note that some $B\_k$ may be empty.)


Conversely, every function with such a form is
 computably closed in your sense. Suppose that $f$ arises
 from such a computable partition of $N$ into finite sets
 $B\_k$. Given any program $e$, enumerate $k$ into $W\_{\rho(e)}$ when
 all of $B\_k$ gets enumerated into $W\_e$. It follows that
 $f[N-W\_e]=N-W\_{\rho(e)}$, as desired.


This provides a characterization of the effectively closed
computable functions:


**Theorem.** A computable function $f:N\to N$ is
effectively closed if and only if $f$ is finite-to-one and
the map $k\mapsto f^{-1}(k)$ is computable.


