Effectively closed computable functions

Question

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 \ W_e] = N \ W_p(e), where W_e 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[W_e] = 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.

Answer 1

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.

Answer 2

I think that this is probably studied in Russian/Markov School of Constructivism. A good starting point might be the chapters on Russian Constructivism in Michael Beeson's book:

Michael Beeson, "Foundations of Constructive Mathematics: Metamathematical Studies", Springer, 1985