Return to Answer

Without certain additional assumptions, the two characterizations of computability in topological spaces are not equivalent also in the case when uniformity is required in the second characterization. Indeed, the following property follows then from computability in the second sense: a partial recursive function $\iota$ exists such that, whenever $O$ is a basic open set of $Y$, $j$ is an index of $O$ in the given surjection of $\mathbb{N}$ onto the basis of $Y$, and $f^{-1}(O)$ is non-empty, then the number $j$ belongs to the domain of $\iota$, and the set with index $\iota(j)$ in the given surjection of $\mathbb{N}$ onto the basis of $X$ is a subset of $f^{-1}(O)$. On the other hand, computability in the first sense can be present without having this property. To construct an example for this, we can proceed as follows. We first construct such a partition of $\mathbb{N}$ into disjoint two-elements sets of the form {$n_0,n_0+1$},{$n_1,n_1+2$},{$n_2,n_2+3$},{$n_3,n_3+4$},$\ldots$ that no recursive function exists whose value at $j$ belongs to {$n_j,n_j+j+1$} for all $j$ in $\mathbb{N}$. Then we take $X=Y=\mathbb{N}$ with the discrete topology, its basis consisting of all singletons in $\mathbb{N}$, but with different surjections of $\mathbb{N}$ onto this basis. For the space $X$, let both numbers $n_i$ and $n_i+i+1$ be indices of the basic set {$i$}, and in the case of $Y$, let $j$ be the only index of {$j$}. Let $f(x)=x$ for all $x$ in $\mathbb{N}$. Then $f$ is computable in the first sense, since, given any enumeration $k_0,k_1,k_2,\ldots$ of the set {$n_x,n_x+x+1$}, we have the equality $x=|k_l-k_{l+1}|-1$, where $l$ is the first $m$ such that $k_m\ne k_{m+1}$. However, $f$ has not the above-formulated property.

For assumptions which guarantee the equivalence of the two characterizations, cf. Theorem 3.3 in M. Korovina's and O. Kudinov's paper "Towards Computability over Effectively Enumerable Topological Spaces", Electron. Notes Theor. Comput. Sci., 221 (2008) 115--125, http://dx.doi.org/10.1016/j.entcs.2008.12.011 (Unfortunately, the formulation of the theorem needs a correction. For the validity of its conclusion some additional assumption is needed. For instance, it is sufficient to add the assumption that $\alpha i$ is empty for some $i$).

Remark. A partition of $\mathbb{N}$ with the properties used in the above counter-example can be made as follows. We take a sequence $k_0,k_1,k_2,\ldots\,$ of natural numbers which is dominated by no recursive function and satisfies $k_{l+1}>k_l+2l+1$ for all $l$ in $\mathbb{N}$. Then we form subsets $C_0,C_1,C_2,\ldots$ of $\mathbb{N}^2$ so that $C_0$ consists of the pairs $(k_l,k_l+2l+1)$ for $l=0,1,2,3,\ldots$, and, for all $r$ in $\mathbb{N}$, $C_{r+1}$ is obtained from $C_r$ by adding a pair $(\bar{n},\bar{m})$ of natural numbers such that $\bar{n}<\bar{m}$ and next three conditions are satisfied:
1. The numbers $\bar{n}$ and $\bar{m}$ occur in no pair from $C_r$.
2. Whenever $(n,m)\in C_r$, the inequality $\bar{m}-\bar{n}\ne m-n$ holds.
3. If $r$ is even then $\bar{n}$ is the least natural number which occurs in no pair from $C_r$, otherwise $\bar{m}-\bar{n}$ is the least positive integer different from all differences $m-n$, where $(n,m)\in C_r$.
Let $C$ be the union of the sets $C_0,C_1,C_2,\ldots$ Then, for any $j$ in $\mathbb{N}$, exactly one pair $(n,m)$ in $C$ exists such that $m-n=j+1$. We set $n_j=n$ for this pair.

Without certain additional assumptions, the two characterizations of computability in topological spaces are not equivalent also in the case when uniformity is required in the second characterization. Indeed, the following property follows then from computability in the second sense: a partial recursive function $\iota$ exists such that, whenever $O$ is a basic open set of $Y$, $j$ is an index of $O$ in the given surjection of $\mathbb{N}$ onto the basis of $Y$, and $f^{-1}(O)$ is non-empty, then the number $j$ belongs to the domain of $\iota$, and the set with index $\iota(j)$ in the given surjection of $\mathbb{N}$ onto the basis of $X$ is a subset of $f^{-1}(O)$. On the other hand, computability in the first sense can be present without having this property. To construct an example for this, we can proceed as follows. We first construct such a partition of $\mathbb{N}$ into disjoint two-elements sets of the form {$n_0,n_0+1$},{$n_1,n_1+2$},{$n_2,n_2+3$},{$n_3,n_3+4$},$\ldots$ that no recursive function exists whose value at $j$ belongs to {$n_j,n_j+j+1$} for all $j$ in $\mathbb{N}$. Then we take $X=Y=\mathbb{N}$ with the discrete topology, its basis consisting of all singletons in $\mathbb{N}$, but with different surjections of $\mathbb{N}$ onto this basis. For the space $X$, let both numbers $n_i$ and $n_i+i+1$ be indices of the basic set {$i$}, and in the case of $Y$, let $j$ be the only index of {$j$}. Let $f(x)=x$ for all $x$ in $\mathbb{N}$. Then $f$ is computable in the first sense, since, given any enumeration $k_0,k_1,k_2,\ldots$ of the set {$n_x,n_x+x+1$}, we have the equality $x=|k_l-k_{l+1}|-1$, where $l$ is the first $m$ such that $k_m\ne k_{m+1}$. However, $f$ has not the above-formulated property.

For assumptions which guarantee the equivalence of the two characterizations, cf. Theorem 3.3 in M. Korovina's and O. Kudinov's paper "Towards Computability over Effectively Enumerable Topological Spaces", Electron. Notes Theor. Comput. Sci., 221 (2008) 115--125, https://doi.org/10.1016/j.entcs.2008.12.011 (Unfortunately, the formulation of the theorem needs a correction. For the validity of its conclusion some additional assumption is needed. For instance, it is sufficient to add the assumption that $\alpha i$ is empty for some $i$).

Remark. A partition of $\mathbb{N}$ with the properties used in the above counter-example can be made as follows. We take a sequence $k_0,k_1,k_2,\ldots\,$ of natural numbers which is dominated by no recursive function and satisfies $k_{l+1}>k_l+2l+1$ for all $l$ in $\mathbb{N}$. Then we form subsets $C_0,C_1,C_2,\ldots$ of $\mathbb{N}^2$ so that $C_0$ consists of the pairs $(k_l,k_l+2l+1)$ for $l=0,1,2,3,\ldots$, and, for all $r$ in $\mathbb{N}$, $C_{r+1}$ is obtained from $C_r$ by adding a pair $(\bar{n},\bar{m})$ of natural numbers such that $\bar{n}<\bar{m}$ and next three conditions are satisfied:
1. The numbers $\bar{n}$ and $\bar{m}$ occur in no pair from $C_r$.
2. Whenever $(n,m)\in C_r$, the inequality $\bar{m}-\bar{n}\ne m-n$ holds.
3. If $r$ is even then $\bar{n}$ is the least natural number which occurs in no pair from $C_r$, otherwise $\bar{m}-\bar{n}$ is the least positive integer different from all differences $m-n$, where $(n,m)\in C_r$.
Let $C$ be the union of the sets $C_0,C_1,C_2,\ldots$ Then, for any $j$ in $\mathbb{N}$, exactly one pair $(n,m)$ in $C$ exists such that $m-n=j+1$. We set $n_j=n$ for this pair.

Without certain additional assumptions, the two characterizations of computability in topological spaces are not equivalent also in the case when uniformity is required in the second characterization. Indeed, the following property follows then from computability in the second sense: a partial recursive function $\iota$ exists such that, whenever $O$ is a basic open set of $Y$, $j$ is an index of $O$ in the given surjection of $\mathbb{N}$ onto the basis of $Y$, and $f^{-1}(O)$ is non-empty, then the number $j$ belongs to the domain of $\iota$, and the set with index $\iota(j)$ in the given surjection of $\mathbb{N}$ onto the basis of $X$ is a subset of $f^{-1}(O)$. On the other hand, computability in the first sense can be present without having this property. To construct an example for this, we can proceed as follows. We first construct such a partition of $\mathbb{N}$ into disjoint two-elements sets of the form {$n_0,n_0+1$},{$n_1,n_1+2$},{$n_2,n_2+3$},{$n_3,n_3+4$},$\ldots$ that no recursive function exists whose value at $j$ belongs to {$n_j,n_j+j+1$} for all $j$ in $\mathbb{N}$. Then we take $X=Y=\mathbb{N}$ with the discrete topology, its basis consisting of all singletons in $\mathbb{N}$, but with different surjections of $\mathbb{N}$ onto this basis. For the space $X$, let both numbers $n_i$ and $n_i+i+1$ be indices of the basic set {$i$}, and in the case of $Y$, let $j$ be the only index of {$j$}. Let $f(x)=x$ for all $x$ in $\mathbb{N}$. Then $f$ is computable in the first sense, since, given any enumeration $k_0,k_1,k_2,\ldots$ of the set {$n_x,n_x+x+1$}, we have the equality $x=|k_l-k_{l+1}|-1$, where $l$ is the first $m$ such that $k_m\ne k_{m+1}$. However, $f$ has not the above-formulated property.

For assumptions which guarantee the equivalence of the two characterizations, cf. Theorem 3.3 in M. Korovina's and O. Kudinov's paper "Towards Computability over Effectively Enumerable Topological Spaces", Electron. Notes Theor. Comput. Sci., 221 (2008) 115--125, http://dx.doi.org/10.1016/j.entcs.2008.12.011

Remark. A partition of $\mathbb{N}$ with the properties used in the above counter-example can be made as follows. We take a sequence $k_0,k_1,k_2,\ldots\,$ of natural numbers which is dominated by no recursive function and satisfies $k_{l+1}>k_l+2l+1$ for all $l$ in $\mathbb{N}$. Then we form subsets $C_0,C_1,C_2,\ldots$ of $\mathbb{N}^2$ so that $C_0$ consists of the pairs $(k_l,k_l+2l+1)$ for $l=0,1,2,3,\ldots$, and, for all $r$ in $\mathbb{N}$, $C_{r+1}$ is obtained from $C_r$ by adding a pair $(\bar{n},\bar{m})$ of natural numbers such that $\bar{n}<\bar{m}$ and next three conditions are satisfied:
1. The numbers $\bar{n}$ and $\bar{m}$ occur in no pair from $C_r$.
2. Whenever $(n,m)\in C_r$, the inequality $\bar{m}-\bar{n}\ne m-n$ holds.
3. If $r$ is even then $\bar{n}$ is the least natural number which occurs in no pair from $C_r$, otherwise $\bar{m}-\bar{n}$ is the least positive integer different from all differences $m-n$, where $(n,m)\in C_r$.
Let $C$ be the union of the sets $C_0,C_1,C_2,\ldots$ Then, for any $j$ in $\mathbb{N}$, exactly one pair $(n,m)$ in $C$ exists such that $m-n=j+1$. We set $n_j=n$ for this pair.

Without certain additional assumptions, the two characterizations of computability in topological spaces are not equivalent also in the case when uniformity is required in the second characterization. Indeed, the following property follows then from computability in the second sense: a partial recursive function $\iota$ exists such that, whenever $O$ is a basic open set of $Y$, $j$ is an index of $O$ in the given surjection of $\mathbb{N}$ onto the basis of $Y$, and $f^{-1}(O)$ is non-empty, then the number $j$ belongs to the domain of $\iota$, and the set with index $\iota(j)$ in the given surjection of $\mathbb{N}$ onto the basis of $X$ is a subset of $f^{-1}(O)$. On the other hand, computability in the first sense can be present without having this property. To construct an example for this, we can proceed as follows. We first construct such a partition of $\mathbb{N}$ into disjoint two-elements sets of the form {$n_0,n_0+1$},{$n_1,n_1+2$},{$n_2,n_2+3$},{$n_3,n_3+4$},$\ldots$ that no recursive function exists whose value at $j$ belongs to {$n_j,n_j+j+1$} for all $j$ in $\mathbb{N}$. Then we take $X=Y=\mathbb{N}$ with the discrete topology, its basis consisting of all singletons in $\mathbb{N}$, but with different surjections of $\mathbb{N}$ onto this basis. For the space $X$, let both numbers $n_i$ and $n_i+i+1$ be indices of the basic set {$i$}, and in the case of $Y$, let $j$ be the only index of {$j$}. Let $f(x)=x$ for all $x$ in $\mathbb{N}$. Then $f$ is computable in the first sense, since, given any enumeration $k_0,k_1,k_2,\ldots$ of the set {$n_x,n_x+x+1$}, we have the equality $x=|k_l-k_{l+1}|-1$, where $l$ is the first $m$ such that $k_m\ne k_{m+1}$. However, $f$ has not the above-formulated property.

For assumptions which guarantee the equivalence of the two characterizations, cf. Theorem 3.3 in M. Korovina's and O. Kudinov's paper "Towards Computability over Effectively Enumerable Topological Spaces", Electron. Notes Theor. Comput. Sci., 221 (2008) 115--125, http://dx.doi.org/10.1016/j.entcs.2008.12.011 (Unfortunately, the formulation of the theorem needs a correction. For the validity of its conclusion some additional assumption is needed. For instance, it is sufficient to add the assumption that $\alpha i$ is empty for some $i$).

Remark. A partition of $\mathbb{N}$ with the properties used in the above counter-example can be made as follows. We take a sequence $k_0,k_1,k_2,\ldots\,$ of natural numbers which is dominated by no recursive function and satisfies $k_{l+1}>k_l+2l+1$ for all $l$ in $\mathbb{N}$. Then we form subsets $C_0,C_1,C_2,\ldots$ of $\mathbb{N}^2$ so that $C_0$ consists of the pairs $(k_l,k_l+2l+1)$ for $l=0,1,2,3,\ldots$, and, for all $r$ in $\mathbb{N}$, $C_{r+1}$ is obtained from $C_r$ by adding a pair $(\bar{n},\bar{m})$ of natural numbers such that $\bar{n}<\bar{m}$ and next three conditions are satisfied:
1. The numbers $\bar{n}$ and $\bar{m}$ occur in no pair from $C_r$.
2. Whenever $(n,m)\in C_r$, the inequality $\bar{m}-\bar{n}\ne m-n$ holds.
3. If $r$ is even then $\bar{n}$ is the least natural number which occurs in no pair from $C_r$, otherwise $\bar{m}-\bar{n}$ is the least positive integer different from all differences $m-n$, where $(n,m)\in C_r$.
Let $C$ be the union of the sets $C_0,C_1,C_2,\ldots$ Then, for any $j$ in $\mathbb{N}$, exactly one pair $(n,m)$ in $C$ exists such that $m-n=j+1$. We set $n_j=n$ for this pair.

Without certain additional assumptions, the two characterizations of computability in topological spaces are not equivalent also in the case when uniformity is required in the second characterization. Indeed, the following property follows then from computability in the second sense: a partial recursive function $\iota$ exists such that, whenever $O$ is a basic open set of $Y$, $j$ is an index of $O$ in the given surjection of $\mathbb{N}$ onto the basis of $Y$, and $f^{-1}(O)$ is non-empty, then the number $j$ belongs to the domain of $\iota$, and the set with index $\iota(j)$ in the given surjection of $\mathbb{N}$ onto the basis of $X$ is a subset of $f^{-1}(O)$. On the other hand, computability in the first sense can be present without having this property. To construct an example for this, we can proceed as follows. We first construct such a partition of $\mathbb{N}$ into disjoint two-elements sets of the form {$n_0,n_0+1$},{$n_1,n_1+2$},{$n_2,n_2+3$},{$n_3,n_3+4$},$\ldots$ that no recursive function exists whose value at $j$ belongs to {$n_j,n_j+j+1$} for all $j$ in $\mathbb{N}$. Then we take $X=Y=\mathbb{N}$ with the discrete topology, its basis consisting of all singletons in $\mathbb{N}$, but with different surjections of $\mathbb{N}$ onto this basis. For the space $X$, let both numbers $n_i$ and $n_i+i+1$ be indices of the basic set {$i$}, and in the case of $Y$, let $j$ be the only index of {$j$}. Let $f(x)=x$ for all $x$ in $\mathbb{N}$. Then $f$ is computable in the first sense, since, given any enumeration $k_0,k_1,k_2,\ldots$ of the set {$n_x,n_x+x+1$}, we have the equality $x=|k_l-k_{l+1}|-1$, where $l$ is the first $m$ such that $k_m\ne k_{m+1}$. However, $f$ has not the above-formulated property.

For assumptions which guarantee the equivalence of the two characterizations, cf. Theorem 3.3 in M. Korovina's and O. Kudinov's paper "Towards Computability over Effectively Enumerable Topological Spaces", Electron. Notes Theor. Comput. Sci., 221 (2008) 115--125, http://dx.doi.org/10.1016/j.entcs.2008.12.011

Remark. A partition of $\mathbb{N}$ with the properties used ib the above counter-example can be made as follows. We take a sequence $k_0,k_1,k_2,\ldots\,$ of natural numbers which is dominated by no recursive function and satisfies $k_{l+1}>k_l+2l+1$ for all $l$ in $\mathbb{N}$. Then we form subsets $C_0,C_1,C_2,\ldots$ of $\mathbb{N}^2$ so that $C_0$ consists of the pairs $(k_l,k_l+2l+1)$ for $l=0,1,2,3,\ldots$, and, for all $r$ in $\mathbb{N}$, $C_{r+1}$ is obtained from $C_r$ by adding a pair $(\bar{n},\bar{m})$ of natural numbers such that $\bar{n}<\bar{m}$ and next three conditions are satisfied:
1. The numbers $\bar{n}$ and $\bar{m}$ occur in no pair from $C_r$.
2. Whenever $(n,m)\in C_r$, the inequality $\bar{m}-\bar{n}\ne m-n$ holds.
3. If $r$ is even then $\bar{n}$ is the least natural number which occurs in no pair from $C_r$, otherwise $\bar{m}-\bar{n}$ is the least positive integer different from all differences $m-n$, where $(n,m)\in C_r$.
Let $C$ be the union of the sets $C_0,C_1,C_2,\ldots$ Then, for any $j$ in $\mathbb{N}$, exactly one pair $(n,m)$ in $C$ exists such that $m-n=j+1$. We set $n_j=n$ for this pair.

Without certain additional assumptions, the two characterizations of computability in topological spaces are not equivalent also in the case when uniformity is required in the second characterization. Indeed, the following property follows then from computability in the second sense: a partial recursive function $\iota$ exists such that, whenever $O$ is a basic open set of $Y$, $j$ is an index of $O$ in the given surjection of $\mathbb{N}$ onto the basis of $Y$, and $f^{-1}(O)$ is non-empty, then the number $j$ belongs to the domain of $\iota$, and the set with index $\iota(j)$ in the given surjection of $\mathbb{N}$ onto the basis of $X$ is a subset of $f^{-1}(O)$. On the other hand, computability in the first sense can be present without having this property. To construct an example for this, we can proceed as follows. We first construct such a partition of $\mathbb{N}$ into disjoint two-elements sets of the form {$n_0,n_0+1$},{$n_1,n_1+2$},{$n_2,n_2+3$},{$n_3,n_3+4$},$\ldots$ that no recursive function exists whose value at $j$ belongs to {$n_j,n_j+j+1$} for all $j$ in $\mathbb{N}$. Then we take $X=Y=\mathbb{N}$ with the discrete topology, its basis consisting of all singletons in $\mathbb{N}$, but with different surjections of $\mathbb{N}$ onto this basis. For the space $X$, let both numbers $n_i$ and $n_i+i+1$ be indices of the basic set {$i$}, and in the case of $Y$, let $j$ be the only index of {$j$}. Let $f(x)=x$ for all $x$ in $\mathbb{N}$. Then $f$ is computable in the first sense, since, given any enumeration $k_0,k_1,k_2,\ldots$ of the set {$n_x,n_x+x+1$}, we have the equality $x=|k_l-k_{l+1}|-1$, where $l$ is the first $m$ such that $k_m\ne k_{m+1}$. However, $f$ has not the above-formulated property.

For assumptions which guarantee the equivalence of the two characterizations, cf. Theorem 3.3 in M. Korovina's and O. Kudinov's paper "Towards Computability over Effectively Enumerable Topological Spaces", Electron. Notes Theor. Comput. Sci., 221 (2008) 115--125, http://dx.doi.org/10.1016/j.entcs.2008.12.011

Remark. A partition of $\mathbb{N}$ with the properties used in the above counter-example can be made as follows. We take a sequence $k_0,k_1,k_2,\ldots\,$ of natural numbers which is dominated by no recursive function and satisfies $k_{l+1}>k_l+2l+1$ for all $l$ in $\mathbb{N}$. Then we form subsets $C_0,C_1,C_2,\ldots$ of $\mathbb{N}^2$ so that $C_0$ consists of the pairs $(k_l,k_l+2l+1)$ for $l=0,1,2,3,\ldots$, and, for all $r$ in $\mathbb{N}$, $C_{r+1}$ is obtained from $C_r$ by adding a pair $(\bar{n},\bar{m})$ of natural numbers such that $\bar{n}<\bar{m}$ and next three conditions are satisfied:
1. The numbers $\bar{n}$ and $\bar{m}$ occur in no pair from $C_r$.
2. Whenever $(n,m)\in C_r$, the inequality $\bar{m}-\bar{n}\ne m-n$ holds.
3. If $r$ is even then $\bar{n}$ is the least natural number which occurs in no pair from $C_r$, otherwise $\bar{m}-\bar{n}$ is the least positive integer different from all differences $m-n$, where $(n,m)\in C_r$.
Let $C$ be the union of the sets $C_0,C_1,C_2,\ldots$ Then, for any $j$ in $\mathbb{N}$, exactly one pair $(n,m)$ in $C$ exists such that $m-n=j+1$. We set $n_j=n$ for this pair.