This comment is to explain partial results obtained by David Simmons in this thread, since the results and their proofs are difficult to follow as a result of being distributed across multiple comments, with many errors and corrections. The proofs given here are due to David Simmons.
#Statements
Theorem 1: There is no metric space X and uniformly continuous function f:X×X→[0,1] such that every uniformly continuous function X→[0,1] is a fiber of f.
Theorem 2: There is no metric space X and function f:X×X→[0,1] that is uniformly continuous on bounded sets, such that every function X→[0,1] which is uniformly continuous on bounded sets is a fiber of f.
Theorem 3: There is no locally compact Polish space X and continuous function f:X×X→[0,1] such that every continuous function X→[0,1] is a fiber of f.
Commentary
Theorem 1 says that there is no solution to the version of Scott’s problem with continuity in topological spaces replaced with uniform continuity in metric spaces. A plausible reason that this version of the problem might be important is that if an agent has to be able to compute what its policy says to do to any desired precision using an amount of computational resources that does not depend on the input, then its policy must be uniformly continuous. The gist of the proof is that for any uniformly continuous f:X×X→[0,1], it is possible to construct a uniformly continuous function g:X→[0,1] that requires greater precision in its input than f does to determine the output to any desired precision. I suspect it might be possible to adapt the proof to work in uniform spaces rather than just metric spaces, but I have not studied uniform spaces.
Theorem 2 is similar to theorem 1, but with uniform continuity replaced with uniform continuity on bounded subsets. I was not convinced that this is an important notion in its own right, but theorem 2 is useful as a lemma for theorem 3. See the thread under David Simmons’s comment for more discussion about what sort of continuity assumption is appropriate. The gist of the proof is to apply the proof of theorem 1 on a bounded set. The function g constructed will be uniformly continuous everywhere, so the proof actually shows a stronger result that unifies both theorems 1 and 2: there is no f:X×X→[0,1] that is uniformly continuous on bounded sets and admits every uniformly continuous function X→[0,1] as a fiber.
Theorem 3 almost says that Scott’s problem cannot be solved with Polish spaces. It doesn’t quite say that, because there are Polish spaces that are not locally compact. However, non-locally-compact Polish spaces are not exponentiable, so in the version of the problem in which we want a surjection X→[0,1]X, it isn’t even clear whether there exists an exponential object [0,1]X, which may mean that non-exponentiable spaces are not promising, although I’m not sure. A reason to restrict attention to Polish spaces is that effective Polish spaces provide a topological setting in which there is a good notion of computability, so the nonexistence of a solution in Polish spaces would make it impossible to provide a computable solution in that sense. That said, there may be other notions of computability in topological spaces (domain theory?), which I am unfamiliar with. The gist of the proof is to find a metric in which bounded sets are compact, and apply theorem 2.
#Proofs
Proof of theorem 1: Let X be a metric space, and f:X×X→[0,1] be uniformly continuous. If X is uniformly discrete, then all functions from X are uniformly continuous, so there is a uniformly continuous function X→[0,1] that is not a fiber of f by Cantor’s theorem.
So assume that X is not uniformly discrete. Let (xn,yn)n∈N be such that ∀kd(xk+1,yk+1)≤16d(xk,yk). Note that for all k and ℓ>k, either (A) d(xk,yℓ)≥13d(xk,yk) and d(xk,xℓ)≥13d(xk,yk) or (B) d(yk,yℓ)≥13d(xk,yk) and d(yk,xℓ)≥13d(xk,yk). By extracting a subsequence we can assume that which of (A) or (B) holds depends only on k and not on ℓ. By swapping xk and yk if necessary we can assume that case (A) always holds.
For each z there is at most one k such that d(z,xk)<16d(xk,yk), because if d(z,xk)<16d(xk,yk) and d(z,xℓ)<16d(xℓ,yℓ) with ℓ>k, then d(xk,xℓ)<13d(xk,yk), a contradiction.
It follows that by extracting a further subsequence we can assume that d(yk,xℓ)≥16d(xℓ,yℓ) for all ℓ>k.
Since f is uniformly continuous, there is a function δ:(0,∞)→(0,∞) such that ∀ε>0d((u,v),(w,z))<δ(ε)→|f(u,v)−f(w,z)|<ε. By extracting a further subsequence, we can assume that d(xk,yk)<δ(2−k) for all k. Let j:[0,∞)→[0,∞) be an increasing uniformly continuous function such that j(0)=0 and j(16d(xk,yk))>2−k for all k. Finally, let g(z):=infkd(z,yk). Then for all k we have g(yk)=0. On the other hand, for all ℓ>k we have d(xk,yℓ)≥13d(xk,yk), for ℓ=k we have d(xk,yℓ)=d(xk,yk), and for ℓ<k we have d(xk,yℓ)≥16d(xk,yk). Thus g(xk)=infℓj(d(xk,yℓ))≥j(16d(xk,yk))>2−k. Clearly, g cannot be a fiber of f. Moreover, since the functions j and z↦infkd(z,yk) are both uniformly continuous, so is g. □
Proof of theorem 2: Let X be a metric space, and f:X×X→[0,1] be uniformly continuous on bounded sets. If all bounded subsets of X are uniformly discrete, then all functions from X are uniformly continuous on bounded sets, so there is a function X→[0,1] that is uniformly continuous on bounded sets but not a fiber of f by Cantor’s theorem. Otherwise, let B⊆X be a bounded set that is not uniformly discrete, take a sequence (xn,yn)n∈N in B as in the proof of theorem 1, and a function δ:(0,∞)→(0,∞) such that ∀ε>0d((u,v),(w,z))<δ(ε)→|f(u,v)−f(w,z)|<ε for (u,v),(w,z)∈B×B, and define j and g as in the proof of theorem 1.g is uniformly continuous, but not a fiber of f. □
Proof of theorem 3: Let d be a metric for X. Let f(x):=sup{r|B(x,r) is compact}, where B(x,r) is the closed ball around x of radius r. Let F(x,y):=f(x)/[f(x)−d(x,y)] if f(x)>d(x,y), and F(x,y):=∞ otherwise. Next, let g(y):=minn[n+F(xn,y)], where (xn)n∈N enumerates a countable dense set. Then g is continuous and everywhere finite. g−1([0,N])⊆⋃n≤NB(xn,(1−1N)f(xn)), and is thus compact. It follows that with the metric d′(x,y):=d(x,y)+|g(y)−g(x)|, which induces the same topology, bounded sets are compact. Thus theorem 3 follows from theorem 2 applied to (X,d′). □
This comment is to explain partial results obtained by David Simmons in this thread, since the results and their proofs are difficult to follow as a result of being distributed across multiple comments, with many errors and corrections. The proofs given here are due to David Simmons.
#Statements
Theorem 1: There is no metric space X and uniformly continuous function f:X×X→[0,1] such that every uniformly continuous function X→[0,1] is a fiber of f.
Theorem 2: There is no metric space X and function f:X×X→[0,1] that is uniformly continuous on bounded sets, such that every function X→[0,1] which is uniformly continuous on bounded sets is a fiber of f.
Theorem 3: There is no locally compact Polish space X and continuous function f:X×X→[0,1] such that every continuous function X→[0,1] is a fiber of f.
Commentary
Theorem 1 says that there is no solution to the version of Scott’s problem with continuity in topological spaces replaced with uniform continuity in metric spaces. A plausible reason that this version of the problem might be important is that if an agent has to be able to compute what its policy says to do to any desired precision using an amount of computational resources that does not depend on the input, then its policy must be uniformly continuous. The gist of the proof is that for any uniformly continuous f:X×X→[0,1], it is possible to construct a uniformly continuous function g:X→[0,1] that requires greater precision in its input than f does to determine the output to any desired precision. I suspect it might be possible to adapt the proof to work in uniform spaces rather than just metric spaces, but I have not studied uniform spaces.
Theorem 2 is similar to theorem 1, but with uniform continuity replaced with uniform continuity on bounded subsets. I was not convinced that this is an important notion in its own right, but theorem 2 is useful as a lemma for theorem 3. See the thread under David Simmons’s comment for more discussion about what sort of continuity assumption is appropriate. The gist of the proof is to apply the proof of theorem 1 on a bounded set. The function g constructed will be uniformly continuous everywhere, so the proof actually shows a stronger result that unifies both theorems 1 and 2: there is no f:X×X→[0,1] that is uniformly continuous on bounded sets and admits every uniformly continuous function X→[0,1] as a fiber.
Theorem 3 almost says that Scott’s problem cannot be solved with Polish spaces. It doesn’t quite say that, because there are Polish spaces that are not locally compact. However, non-locally-compact Polish spaces are not exponentiable, so in the version of the problem in which we want a surjection X→[0,1]X, it isn’t even clear whether there exists an exponential object [0,1]X, which may mean that non-exponentiable spaces are not promising, although I’m not sure. A reason to restrict attention to Polish spaces is that effective Polish spaces provide a topological setting in which there is a good notion of computability, so the nonexistence of a solution in Polish spaces would make it impossible to provide a computable solution in that sense. That said, there may be other notions of computability in topological spaces (domain theory?), which I am unfamiliar with. The gist of the proof is to find a metric in which bounded sets are compact, and apply theorem 2.
#Proofs
Proof of theorem 1: Let X be a metric space, and f:X×X→[0,1] be uniformly continuous. If X is uniformly discrete, then all functions from X are uniformly continuous, so there is a uniformly continuous function X→[0,1] that is not a fiber of f by Cantor’s theorem.
So assume that X is not uniformly discrete. Let (xn,yn)n∈N be such that ∀k d(xk+1,yk+1)≤16d(xk,yk). Note that for all k and ℓ>k, either (A) d(xk,yℓ)≥13d(xk,yk) and d(xk,xℓ)≥13d(xk,yk) or (B) d(yk,yℓ)≥13d(xk,yk) and d(yk,xℓ)≥13d(xk,yk). By extracting a subsequence we can assume that which of (A) or (B) holds depends only on k and not on ℓ. By swapping xk and yk if necessary we can assume that case (A) always holds.
For each z there is at most one k such that d(z,xk)<16d(xk,yk), because if d(z,xk)<16d(xk,yk) and d(z,xℓ)<16d(xℓ,yℓ) with ℓ>k, then d(xk,xℓ)<13d(xk,yk), a contradiction.
It follows that by extracting a further subsequence we can assume that d(yk,xℓ)≥16d(xℓ,yℓ) for all ℓ>k.
Since f is uniformly continuous, there is a function δ:(0,∞)→(0,∞) such that ∀ε>0d((u,v),(w,z))<δ(ε)→|f(u,v)−f(w,z)|<ε. By extracting a further subsequence, we can assume that d(xk,yk)<δ(2−k) for all k. Let j:[0,∞)→[0,∞) be an increasing uniformly continuous function such that j(0)=0 and j(16d(xk,yk))>2−k for all k. Finally, let g(z):=infkd(z,yk). Then for all k we have g(yk)=0. On the other hand, for all ℓ>k we have d(xk,yℓ)≥13d(xk,yk), for ℓ=k we have d(xk,yℓ)=d(xk,yk), and for ℓ<k we have d(xk,yℓ)≥16d(xk,yk). Thus g(xk)=infℓj(d(xk,yℓ))≥j(16d(xk,yk))>2−k. Clearly, g cannot be a fiber of f. Moreover, since the functions j and z↦infkd(z,yk) are both uniformly continuous, so is g. □
Proof of theorem 2: Let X be a metric space, and f:X×X→[0,1] be uniformly continuous on bounded sets. If all bounded subsets of X are uniformly discrete, then all functions from X are uniformly continuous on bounded sets, so there is a function X→[0,1] that is uniformly continuous on bounded sets but not a fiber of f by Cantor’s theorem. Otherwise, let B⊆X be a bounded set that is not uniformly discrete, take a sequence (xn,yn)n∈N in B as in the proof of theorem 1, and a function δ:(0,∞)→(0,∞) such that ∀ε>0d((u,v),(w,z))<δ(ε)→|f(u,v)−f(w,z)|<ε for (u,v),(w,z)∈B×B, and define j and g as in the proof of theorem 1.g is uniformly continuous, but not a fiber of f. □
Proof of theorem 3: Let d be a metric for X. Let f(x):=sup{r|B(x,r) is compact}, where B(x,r) is the closed ball around x of radius r. Let F(x,y):=f(x)/[f(x)−d(x,y)] if f(x)>d(x,y), and F(x,y):=∞ otherwise. Next, let g(y):=minn[n+F(xn,y)], where (xn)n∈N enumerates a countable dense set. Then g is continuous and everywhere finite. g−1([0,N])⊆⋃n≤NB(xn,(1−1N)f(xn)), and is thus compact. It follows that with the metric d′(x,y):=d(x,y)+|g(y)−g(x)|, which induces the same topology, bounded sets are compact. Thus theorem 3 follows from theorem 2 applied to (X,d′). □