Skip to main content
deleted 256 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

I findlike your concept to be very interesting. I don't know any name for ita lot, but Iand have been able to make some observations that lead tofind 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 yourthe 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.

Since these functions can be viewed as trivial in a sense, perhaps this characterization is a somewhat negative result. But still I like your motivation and find the class interesting.

I find your concept to be very interesting. I don't know any name for it, but I have been able to make some observations that lead to a characterization.

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

First, 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 your 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.

Since these functions can be viewed as trivial in a sense, perhaps this characterization is a somewhat negative result. But still I like your motivation and find the class interesting.

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.

Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

I find your concept to be very interesting. I don't know any name for it, but I have been able to make some observations that lead to a characterization.

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

First, 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 your 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.

Since these functions can be viewed as trivial in a sense, perhaps this characterization is a somewhat negative result. But still I like your motivation and find the class interesting.