by Alex Mennen 548 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

[Note: This comment is three
 by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
 by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
 by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
 by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
 by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
 by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
 by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
 by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
 by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
 by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
 by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
 by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes