by Alex Mennen 273 days ago | link | parent

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\times X\rightarrow[0,1]$$ such that every uniformly continuous function $$X\rightarrow[0,1]$$ is a fiber of $$f$$.

Theorem 2: There is no metric space $$X$$ and function $$f:X\times X\rightarrow[0,1]$$ that is uniformly continuous on bounded sets, such that every function $$X\rightarrow[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\times X\rightarrow[0,1]$$ such that every continuous function $$X\rightarrow[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\times X\rightarrow[0,1]$$, it is possible to construct a uniformly continuous function $$g:X\rightarrow[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\times X\rightarrow[0,1]$$ that is uniformly continuous on bounded sets and admits every uniformly continuous function $$X\rightarrow[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\rightarrow[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\times X\rightarrow[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\rightarrow[0,1]$$ that is not a fiber of $$f$$ by Cantor’s theorem.

So assume that $$X$$ is not uniformly discrete. Let $$(x_n,y_n)_{n\in\mathbb{N}}$$ be such that $$\forall k$$ $$d(x_{k+1},y_{k+1})\leq\frac{1}{6}d(x_k,y_k)$$. Note that for all $$k$$ and $$\ell>k$$, either (A) $$d(x_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)$$ and $$d(x_k,x_\ell)\geq\frac{1}{3}d(x_k,y_k)$$ or (B) $$d(y_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)$$ and $$d(y_k,x_\ell)\geq\frac{1}{3}d(x_k,y_k)$$. By extracting a subsequence we can assume that which of (A) or (B) holds depends only on $$k$$ and not on $$\ell$$. By swapping $$x_k$$ and $$y_k$$ if necessary we can assume that case (A) always holds.

For each $$z$$ there is at most one $$k$$ such that $$d(z,x_k)<\frac{1}{6}d(x_k,y_k)$$, because if $$d(z,x_k)<\frac{1}{6}d(x_k,y_k)$$ and $$d(z,x_\ell)<\frac{1}{6}d(x_\ell,y_\ell)$$ with $$\ell>k$$, then $$d(x_k,x_\ell)<\frac{1}{3}d(x_k,y_k)$$, a contradiction.

It follows that by extracting a further subsequence we can assume that $$d(y_k,x_\ell)\geq\frac{1}{6}d(x_\ell,y_\ell)$$ for all $$\ell>k$$.

Since $$f$$ is uniformly continuous, there is a function $$\delta:(0,\infty)\rightarrow(0,\infty)$$ such that $$\forall\varepsilon>0\;d((u,v),(w,z))<\delta(\varepsilon)\rightarrow|f(u,v)-f(w,z)|<\varepsilon$$. By extracting a further subsequence, we can assume that $$d(x_k,y_k)<\delta(2^{-k})$$ for all $$k$$. Let $$j:[0,\infty)\rightarrow[0,\infty)$$ be an increasing uniformly continuous function such that $$j(0)=0$$ and $$j(\frac{1}{6}d(x_k,y_k))>2^{-k}$$ for all $$k$$. Finally, let $$g(z):=\inf_kd(z,y_k)$$. Then for all $$k$$ we have $$g(y_k)=0$$. On the other hand, for all $$\ell>k$$ we have $$d(x_k,y_\ell)\geq\frac{1}{3}d(x_k,y_k)$$, for $$\ell=k$$ we have $$d(x_k,y_\ell)=d(x_k,y_k)$$, and for $$\ell<k$$ we have $$d(x_k,y_\ell)\geq\frac{1}{6}d(x_k,y_k)$$. Thus $$g(x_k)=\inf_\ell j(d(x_k,y_\ell))\geq j(\frac{1}{6}d(x_k,y_k))>2^{-k}$$. Clearly, $$g$$ cannot be a fiber of $$f$$. Moreover, since the functions $$j$$ and $$z\mapsto\inf_kd(z,y_k)$$ are both uniformly continuous, so is $$g$$. $$\square$$

Proof of theorem 2: Let $$X$$ be a metric space, and $$f:X\times X\rightarrow[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\rightarrow[0,1]$$ that is uniformly continuous on bounded sets but not a fiber of $$f$$ by Cantor’s theorem. Otherwise, let $$B\subseteq X$$ be a bounded set that is not uniformly discrete, take a sequence $$(x_n,y_n)_{n\in\mathbb{N}}$$ in $$B$$ as in the proof of theorem 1, and a function $$\delta:(0,\infty)\rightarrow(0,\infty)$$ such that $$\forall\varepsilon>0\;d((u,v),(w,z))<\delta(\varepsilon)\rightarrow|f(u,v)-f(w,z)|<\varepsilon$$ for $$(u,v),(w,z)\in B\times B$$, and define $$j$$ and $$g$$ as in the proof of theorem 1. $$g$$ is uniformly continuous, but not a fiber of $$f$$. $$\square$$

Proof of theorem 3: Let $$d$$ be a metric for $$X$$. Let $$f(x):=\sup\{r|B(x,r)\text{ 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):=\infty$$ otherwise. Next, let $$g(y):=\min_n[n+F(x_n,y)]$$, where $$(x_n)_{n\in\mathbb{N}}$$ enumerates a countable dense set. Then $$g$$ is continuous and everywhere finite. $$g^{-1}([0,N])\subseteq\bigcup_{n\leq N}B(x_n,(1-\frac{1}{N})f(x_n))$$, 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')$$. $$\square$$

### NEW DISCUSSION POSTS

[Delegative Reinforcement
 by Vadim Kosoy on Stable Pointers to Value II: Environmental Goals | 1 like

Intermediate update: The
 by Alex Appel on Further Progress on a Bayesian Version of Logical ... | 0 likes

Since Briggs [1] shows that
 by 258 on In memoryless Cartesian environments, every UDT po... | 2 likes

This doesn't quite work. The
 by Nisan Stiennon on Logical counterfactuals and differential privacy | 0 likes

I at first didn't understand
 by Sam Eisenstat on An Untrollable Mathematician | 1 like

This is somewhat related to
 by Vadim Kosoy on The set of Logical Inductors is not Convex | 0 likes

This uses logical inductors
 by Abram Demski on The set of Logical Inductors is not Convex | 0 likes

Nice writeup. Is one-boxing
 by Tom Everitt on Smoking Lesion Steelman II | 0 likes

Hi Alex! The definition of
 by Vadim Kosoy on Delegative Inverse Reinforcement Learning | 0 likes

A summary that might be
 by Alex Appel on Delegative Inverse Reinforcement Learning | 1 like

I don't believe that
 by Alex Appel on Delegative Inverse Reinforcement Learning | 0 likes

This is exactly the sort of
 by Stuart Armstrong on Being legible to other agents by committing to usi... | 0 likes

When considering an embedder
 by Jack Gallagher on Where does ADT Go Wrong? | 0 likes

The differences between this
 by Abram Demski on Policy Selection Solves Most Problems | 1 like

Looking "at the very
 by Abram Demski on Policy Selection Solves Most Problems | 0 likes