Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've recently been interested in the following type of functions. A total computable function f:NN is effectively closed if there is a computable function p such that f[N \ We] = N \ Wp(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:NN is computable if and only if it is effectively continuous, i.e. there is a computable function p such that f-1[We] = Wp(e). [For the backward implication, let q be a computable function such that Wq(n) = {n} and use the composite pq 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:NN for which there is a computable b:NN 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.

share|improve this question
    
François, it's a great problem! –  Joel David Hamkins May 22 '10 at 2:40

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
This is great! I had gotten the finite-to-one part using a completely different argument, but not the computable bound on $f^{-1}(k)$. –  François G. Dorais May 23 '10 at 4:04
    
This doesn't answer the main question, but I'm accepting it anyway since the argument is so beautiful! –  François G. Dorais May 23 '10 at 4:10
    
Thanks, François, you are very kind. –  Joel David Hamkins May 23 '10 at 11:59
    
I think there's a minor error in the 6th paragraph: "that $W_e=N$" should be "that $W_e = ran(f)$." –  François G. Dorais May 23 '10 at 15:30
    
I think $W_e=N$ is correct. The point is that once you know $W_{\rho(e)}=N$, then $N-W_{\rho(e)}$ is empty, so it had better be that $W_e=N$ or else $f[N-W_e]$ won't be empty. Or have I misunderstood? –  Joel David Hamkins May 23 '10 at 16:47

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

share|improve this answer
1  
Is there a particular reason you are citing this reference? Most of us don't have this book, so perhaps you could supply a relevant sentence or two -- otherwise such a comment is not very useful. –  András Salamon Aug 14 '10 at 15:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.