Return to 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.

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.

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). [Let q be a computable function such that W_q(n) = {n}. 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 computable map 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 polynomials and increasing functions are effectively closed.

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.

I've recently been interested in the following type of functions. A (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 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). [Let q be a computable function such that W_q(n) = {n}. Use the composite p∘q to enumerate the graph of f.] A similar trick shows that a function is effectively open if and only if it is computable. However, a computable map 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 polynomials and increasing functions are effectively closed.

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). [Let q be a computable function such that W_q(n) = {n}. 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 computable map 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 polynomials and increasing functions are effectively closed.