This is intended as a reply to David Simmons’s comment, which for some reason I can’t reply to directly.
In the new version of your proof, how do we know Yk isn’t too close to Xl for some l>k? And how do we know that g is uniformly continuous on bounded subsets?
About continuity versus uniform continuity on bounded sets:
It seems to me that your point 1 is just a pithier version of your point 4, and that these points support paying attention to uniform continuity, rather than uniform continuity restricted to bounded sets. This version of the problem seems like it would be a less messy version of the “fixed modulus of continuity” version of the problem you mentioned (which I did not understand your solution to, but will look again later).
I’m not sure what you’re getting at about singularities in point 3. I wouldn’t have asked why you were considering uniform continuity on bounded sets instead of uniform continuity away from singularities (in fact, I don’t know what that means). I would ask, though, why uniform continuity on bounded sets instead of uniform continuity on compact sets? As you point out, the latter is the same as continuity.
Your point 2 is completely wrong, and in fact this is the primary reason I was convinced that continuity is a better thing to pay attention to than uniform continuity on bounded sets. The type of object you are describing is an effective Polish space that remembers its metric. Typically, descriptive set theorists forget the metric, and the isomorphisms between Polish spaces are homeomorphisms (and the isomorphisms between effective Polish spaces are computable homeomorphisms). Changing the metric in a computably homeomorphic way does not change what can be done when points are represented as descending chains of basic open sets with singleton intersection. So the thing you described was really topological rather than metric in nature, even though it involves introducing a metric in the setup. I am not aware of any notions of computability in metric spaces in which the metric matters in the way you are suggesting. It is not true that uniform continuity gives you an algorithm for computing the function. As a counterexample, let a be an uncomputable number, and let f:R→R be given by f(x)=a for every x. f is clearly uniformly continuous, but not computable. It is also not true that uniform continuity is necessary in order for the function to be computable. For instance, sin(1/x) is computable on (0,1]. Of course, (0,1] is not complete, but for another example, consider an effective infinite-dimensional Hilbert space, and let {en|n∈N} be an effective orthonormal basis. Let fn(x):=max(0,12−∥x−en∥). This sequence of functions is computable, they have disjoint support, and for any point, a sufficiently small neighborhood around it will be disjoint from the supports of all but at most one of these functions. Thus f(x):=∑nnfn(x) is computable, but of course it is not uniformly continuous on the unit ball, which is bounded. However, it is true that every computable function is continuous, and conversely, every continuous function is computable with respect to some oracle. Of course, we really want computability, not computability with respect to some oracle, but this still seems to show that continuity is at least a good metaphor for computability, whereas uniform continuity on bounded sets doesn’t seem so to me.
Of course, all this about continuity as a metaphor for computability makes the most sense in the context of Polish spaces, and we can only talk about actual computability in the context of effective Polish spaces. Scott’s problem involves a space X and the exponential [0,1]X. If X is a locally compact Polish space, then [0,1]X is also Polish. I think that this might be necessary (that is, if X and [0,1]X are Polish, then X is locally compact), although I’m not sure. If so, and if your proof is correct, it seems plausible that your proof could be adapted to show that there is no locally compact Polish space with the property that Scott was looking for, and that would show that there is no solution to the problem in which X and [0,1]X are both Polish spaces, and hence no computable solution, if computability is formalized as in effective descriptive set theory.
I don’t know why my comment doesn’t have a reply button. Maybe it is related to the fact that my comment shows up as “deleted” when I am not logged in.
Sorry, I seem to be getting a little lazy with these proofs. Hopefully I haven’t missed anything this time.
New proof: … We can extract a subsequence (nk) such that if Xk=xnk and Yk=ynk, then d(Xk+1,Yk+1)≤(1/6)d(Xk,Yk) for all k, and for all k and l>k, either (A) d(Xk,Yl)≥(1/3)d(Xk,Yk) and d(Xk,Xl)≥(1/3)d(Xk,Yk) or (B) d(Yk,Xl)≥(1/3)d(Xk,Yk) and d(Yk,Yl)≥(1/3)d(Xk,Yk). By extracting a further subsequence we can assume that which of (A) or (B) holds depends only on k and not on l. By swapping Xk and Yk if necessary we can assume that case (A) always holds.
Lemma: For each z there is at most one k such that d(z,Xk)≤(1/6)d(Xk,Yk).
Proof: Suppose d(z,Xk)≤(1/6)d(Xk,Yk) and d(z,Xl)≤(1/6)d(Xl,Yl), with k<l. Then d(Xk,Xl)<(1/3)d(Xk,Yk), a contradiction.
It follows that by extracting a further subsequence we can assume that d(Yk,Xl)≥(1/6)d(Xl,Yl) for all l>k.
Now let j:[0,∞)→[0,∞) be an increasing uniformly continuous function such that j(0)=0 and j((1/6)d(Xk,Yk))>2−nk for all k. Finally, let g(x)=infkj(d(x,Yk)). Then for all k we have g(Yk)=0. On the other hand, for all k<l we have d(Xk,Yl)≥(1/3)d(Xk,Yk), for k=l we have d(Xk,Yl)=d(Xk,Yk), and for k>l we have d(Xk,Yl)≥(1/6)d(Xk,Yk). Thus g(Xk)=inflj(d(Xk,Yl))≥j((1/6)d(Xk,Yk))>2−nk. Clearly, g cannot be a fiber of f. Moreover, since the functions j and x↦infkd(x,Yk) are both uniformly continuous, so is g.
Regarding your responses to my points:
I guess I don’t disagree with what you write regarding my points 1 and 4.
It seems to be harder than expected to explain my intuitions regarding singularities in point 3. Basically, I think the reasons that abstract continuity came to be considered standard are mostly the fact that in concrete applications you have to worry about singularities, and this makes uniform continuity a little more technically annoying. But in the kind of problem we are considering here, it seems that continuity is really more annoying to deal with than uniform continuity, with little added benefit. I guess it also depends on what kinds of functions you expect to actually come up, which is a heuristic judgement. Anyway it might not be productive to continue this line of reasoning further as maybe our disagreements just come down to intuitions.
Regarding my point 2, I wasn’t very clear when I said that uniform continuity gives you an algorithm, what I meant was that if you have an algorithm for computing the images of points in the dense sequence and for computing the modulus of continuity function, then uniform continuity gives you an algorithm. The function x↦sin(1/x) would be the kind of thing I would handle with uniform continuity away from singularities (to fix a definition for this, let us say that you are uniformly continuous away from singularities if you are uniformly continuous on sets of the form B(0,n)∖B(S,1/n), where S is some set of singularities).
In your definition of fn, I think you mean to write max instead of min. But I see your point, though the example seems a little pathological to me.
Anyway, it seems that you agree that it makes sense to restrict to Polish spaces based on computability considerations, which is part of what I was trying to say in 2.
If you have a locally compact Polish space, then you can find a metric with respect to which the space is proper (i.e. bounded subsets are compact): let d′(x,y)=d(x,y)+|f(x)−f(y)|, where f(x)=1/sup{r:B(x,r) is compact}. With respect to this metric, continuity is the same as uniform continuity on bounded sets, so my proof should work then.
Proposition: Let X be a Polish space that is not locally compact. Then [0,1]X (with the compact-open topology) is not first countable.
Proof: Suppose otherwise. Then the function f0≡0 has a countable neighborhood basis of sets of the form F(Kn,Un)={f:f(Kn)⊆Un} where Kn⊆X is compact and Un⊆[0,1] is open. Since X is not locally compact, there exists a point x such that B(x,r) is not compact for any x. For each n, we can choose xn∈B(x,1/n)∖⋃i≤nKi. Let K={xn:n}∪{x}, and note that K is compact. Then F(K,[0,1/2)) is a neighborhood of f0. But then F(K,[0,1/2))⊇⋂i≤nF(Ki,Ui) for some n. This contradicts the fact that xn∈K∖⋃i≤nKi, since we can find a bump function which is 0 on ⋃i≤nKi but 1 at x.
It does still seem to me that most of the useful intuition comes from point 4 of my previous comment, though.
It appears that comments from new users are collapsed by default, and cannot be replied to without a “Like”. These seem like bad features.
Your proof that there’s no uniformly continuous on bounded sets function f:X×X→[0,1] admitting all uniformly continuous on bounded sets functions X→[0,1] as fibers looks correct now. It also looks like it can be easily adapted to show that there is no uniformly continuous f:X×X→[0,1] admitting all uniformly continuous functions X→[0,1] as fibers. Come to think of it, your proof works for arbitrary metric spaces X, not just complete separable metric spaces, though those are nicer.
I see what you mean now about uniform continuity giving you an algorithm, but I still don’t think that’s specific to uniform continuity in an important way. After all, if you have an algorithm for computing images of points in the countable dense set, and a computable “local modulus of continuity” in the sense of a computable function h:X×[0,∞)→[0,∞) with h(x,0)=0 and d(x,y)<r⟹|f(y)−f(x)|<h(x,r), then f is computable, and this does not require f to be uniformly continuous. Although I suppose you could object that this is a bit circular, in that I’m assuming the “local modulus of continuity” is computable only in the standard sense, which does not require uniform continuity.
I’m not sure why you would allow singularities at some points (presumably a uniformly discrete set, or something like that) while still insisting on uniform continuity elsewhere. It still seems to me that the arguments for uniform continuity rather than continuity all point to wanting uniform continuity entirely, rather than some sense of local uniform continuity in most places.
Thanks for pointing out the error in my definition of fn; I’ve fixed it.
In your argument that locally compact Polish spaces can be given metrics with respect to which they are proper, it isn’t true that d′ is necessarily a proper metric. For instance, consider a countably infinite set with d(x,y)=1 for x≠y. This is a locally compact Polish space, but f(x)=1 for every x, so d′=d, and the space is not proper.
Your last proposition looks correct (though with a typo: last ⊆ in the proof should be ⊇). However, if X is not locally compact, then the compact-open topology isn’t necessarily the right topology to consider on [0,1]X. We want a topology making [0,1]X into an exponential object, and it isn’t clear that such a topology even exists, or that it is the compact-open topology if it does exist (though it must be a refinement of the compact-open topology if it does exist). Maybe asking about non-locally compact Polish spaces X with a Polish exponential space [0,1]X is a kind of weird question, though, and if we’re even considering non-locally compact Polish spaces, we should turn to the version of the question where we just want a continuous function X×X→[0,1] admitting all continuous functions X→[0,1] as fibers.
I will have to think more about the issue of continuity vs uniform continuity. I suppose my last remaining argument would be the fact that Bishop—Bridges’ classic book on constructive analysis uses uniform continuity on bounded sets rather than continuity, which suggests that it is probably better for constructive analysis at least. But maybe they did not analyze the issue carefully enough, or maybe the relevant issues here are for some reason different.
To fix the argument that every locally compact Polish space admits a proper metric, let f be as before and let F(x,y)=∞ if d(x,y)≥f(x) and F(x,y)=f(x)/[f(x)−d(x,y)] if d(x,y)<f(x). Next, let g(y)=minn[n+F(xn,y)], where (xn) is a countable dense sequence. Then g is continuous and everywhere finite. Moreover, if S=g−1([0,N]), then S⊆⋃n≤NB(xn,(1−1/N)f(xn)) and thus S is compact. It follows that the metric d′(x,y)=d(x,y)+|g(y)−g(x)| is proper.
Hm, perhaps I should figure out what the significance of uniform continuity on bounded sets is in constructive analysis before dismissing it, even though I don’t see the appeal myself, since constructive analysis is not a field I know much about, but could potentially be relevant here.
f is the reciprocal of what it was before, but yes, this looks good. I am happy with this proof.
This is intended as a reply to David Simmons’s comment, which for some reason I can’t reply to directly.
In the new version of your proof, how do we know Yk isn’t too close to Xl for some l>k? And how do we know that g is uniformly continuous on bounded subsets?
About continuity versus uniform continuity on bounded sets:
It seems to me that your point 1 is just a pithier version of your point 4, and that these points support paying attention to uniform continuity, rather than uniform continuity restricted to bounded sets. This version of the problem seems like it would be a less messy version of the “fixed modulus of continuity” version of the problem you mentioned (which I did not understand your solution to, but will look again later).
I’m not sure what you’re getting at about singularities in point 3. I wouldn’t have asked why you were considering uniform continuity on bounded sets instead of uniform continuity away from singularities (in fact, I don’t know what that means). I would ask, though, why uniform continuity on bounded sets instead of uniform continuity on compact sets? As you point out, the latter is the same as continuity.
Your point 2 is completely wrong, and in fact this is the primary reason I was convinced that continuity is a better thing to pay attention to than uniform continuity on bounded sets. The type of object you are describing is an effective Polish space that remembers its metric. Typically, descriptive set theorists forget the metric, and the isomorphisms between Polish spaces are homeomorphisms (and the isomorphisms between effective Polish spaces are computable homeomorphisms). Changing the metric in a computably homeomorphic way does not change what can be done when points are represented as descending chains of basic open sets with singleton intersection. So the thing you described was really topological rather than metric in nature, even though it involves introducing a metric in the setup. I am not aware of any notions of computability in metric spaces in which the metric matters in the way you are suggesting. It is not true that uniform continuity gives you an algorithm for computing the function. As a counterexample, let a be an uncomputable number, and let f:R→R be given by f(x)=a for every x. f is clearly uniformly continuous, but not computable. It is also not true that uniform continuity is necessary in order for the function to be computable. For instance, sin(1/x) is computable on (0,1]. Of course, (0,1] is not complete, but for another example, consider an effective infinite-dimensional Hilbert space, and let {en|n∈N} be an effective orthonormal basis. Let fn(x):=max(0,12−∥x−en∥). This sequence of functions is computable, they have disjoint support, and for any point, a sufficiently small neighborhood around it will be disjoint from the supports of all but at most one of these functions. Thus f(x):=∑nnfn(x) is computable, but of course it is not uniformly continuous on the unit ball, which is bounded. However, it is true that every computable function is continuous, and conversely, every continuous function is computable with respect to some oracle. Of course, we really want computability, not computability with respect to some oracle, but this still seems to show that continuity is at least a good metaphor for computability, whereas uniform continuity on bounded sets doesn’t seem so to me.
Of course, all this about continuity as a metaphor for computability makes the most sense in the context of Polish spaces, and we can only talk about actual computability in the context of effective Polish spaces. Scott’s problem involves a space X and the exponential [0,1]X. If X is a locally compact Polish space, then [0,1]X is also Polish. I think that this might be necessary (that is, if X and [0,1]X are Polish, then X is locally compact), although I’m not sure. If so, and if your proof is correct, it seems plausible that your proof could be adapted to show that there is no locally compact Polish space with the property that Scott was looking for, and that would show that there is no solution to the problem in which X and [0,1]X are both Polish spaces, and hence no computable solution, if computability is formalized as in effective descriptive set theory.
I don’t know why my comment doesn’t have a reply button. Maybe it is related to the fact that my comment shows up as “deleted” when I am not logged in.
Sorry, I seem to be getting a little lazy with these proofs. Hopefully I haven’t missed anything this time.
New proof: … We can extract a subsequence (nk) such that if Xk=xnk and Yk=ynk, then d(Xk+1,Yk+1)≤(1/6)d(Xk,Yk) for all k, and for all k and l>k, either (A) d(Xk,Yl)≥(1/3)d(Xk,Yk) and d(Xk,Xl)≥(1/3)d(Xk,Yk) or (B) d(Yk,Xl)≥(1/3)d(Xk,Yk) and d(Yk,Yl)≥(1/3)d(Xk,Yk). By extracting a further subsequence we can assume that which of (A) or (B) holds depends only on k and not on l. By swapping Xk and Yk if necessary we can assume that case (A) always holds.
Lemma: For each z there is at most one k such that d(z,Xk)≤(1/6)d(Xk,Yk).
Proof: Suppose d(z,Xk)≤(1/6)d(Xk,Yk) and d(z,Xl)≤(1/6)d(Xl,Yl), with k<l. Then d(Xk,Xl)<(1/3)d(Xk,Yk), a contradiction.
It follows that by extracting a further subsequence we can assume that d(Yk,Xl)≥(1/6)d(Xl,Yl) for all l>k.
Now let j:[0,∞)→[0,∞) be an increasing uniformly continuous function such that j(0)=0 and j((1/6)d(Xk,Yk))>2−nk for all k. Finally, let g(x)=infkj(d(x,Yk)). Then for all k we have g(Yk)=0. On the other hand, for all k<l we have d(Xk,Yl)≥(1/3)d(Xk,Yk), for k=l we have d(Xk,Yl)=d(Xk,Yk), and for k>l we have d(Xk,Yl)≥(1/6)d(Xk,Yk). Thus g(Xk)=inflj(d(Xk,Yl))≥j((1/6)d(Xk,Yk))>2−nk. Clearly, g cannot be a fiber of f. Moreover, since the functions j and x↦infkd(x,Yk) are both uniformly continuous, so is g.
Regarding your responses to my points:
I guess I don’t disagree with what you write regarding my points 1 and 4.
It seems to be harder than expected to explain my intuitions regarding singularities in point 3. Basically, I think the reasons that abstract continuity came to be considered standard are mostly the fact that in concrete applications you have to worry about singularities, and this makes uniform continuity a little more technically annoying. But in the kind of problem we are considering here, it seems that continuity is really more annoying to deal with than uniform continuity, with little added benefit. I guess it also depends on what kinds of functions you expect to actually come up, which is a heuristic judgement. Anyway it might not be productive to continue this line of reasoning further as maybe our disagreements just come down to intuitions.
Regarding my point 2, I wasn’t very clear when I said that uniform continuity gives you an algorithm, what I meant was that if you have an algorithm for computing the images of points in the dense sequence and for computing the modulus of continuity function, then uniform continuity gives you an algorithm. The function x↦sin(1/x) would be the kind of thing I would handle with uniform continuity away from singularities (to fix a definition for this, let us say that you are uniformly continuous away from singularities if you are uniformly continuous on sets of the form B(0,n)∖B(S,1/n), where S is some set of singularities).
In your definition of fn, I think you mean to write max instead of min. But I see your point, though the example seems a little pathological to me.
Anyway, it seems that you agree that it makes sense to restrict to Polish spaces based on computability considerations, which is part of what I was trying to say in 2.
If you have a locally compact Polish space, then you can find a metric with respect to which the space is proper (i.e. bounded subsets are compact): let d′(x,y)=d(x,y)+|f(x)−f(y)|, where f(x)=1/sup{r:B(x,r) is compact}. With respect to this metric, continuity is the same as uniform continuity on bounded sets, so my proof should work then.
Proposition: Let X be a Polish space that is not locally compact. Then [0,1]X (with the compact-open topology) is not first countable.
Proof: Suppose otherwise. Then the function f0≡0 has a countable neighborhood basis of sets of the form F(Kn,Un)={f:f(Kn)⊆Un} where Kn⊆X is compact and Un⊆[0,1] is open. Since X is not locally compact, there exists a point x such that B(x,r) is not compact for any x. For each n, we can choose xn∈B(x,1/n)∖⋃i≤nKi. Let K={xn:n}∪{x}, and note that K is compact. Then F(K,[0,1/2)) is a neighborhood of f0. But then F(K,[0,1/2))⊇⋂i≤nF(Ki,Ui) for some n. This contradicts the fact that xn∈K∖⋃i≤nKi, since we can find a bump function which is 0 on ⋃i≤nKi but 1 at x.
It does still seem to me that most of the useful intuition comes from point 4 of my previous comment, though.
It appears that comments from new users are collapsed by default, and cannot be replied to without a “Like”. These seem like bad features.
Your proof that there’s no uniformly continuous on bounded sets function f:X×X→[0,1] admitting all uniformly continuous on bounded sets functions X→[0,1] as fibers looks correct now. It also looks like it can be easily adapted to show that there is no uniformly continuous f:X×X→[0,1] admitting all uniformly continuous functions X→[0,1] as fibers. Come to think of it, your proof works for arbitrary metric spaces X, not just complete separable metric spaces, though those are nicer.
I see what you mean now about uniform continuity giving you an algorithm, but I still don’t think that’s specific to uniform continuity in an important way. After all, if you have an algorithm for computing images of points in the countable dense set, and a computable “local modulus of continuity” in the sense of a computable function h:X×[0,∞)→[0,∞) with h(x,0)=0 and d(x,y)<r⟹|f(y)−f(x)|<h(x,r), then f is computable, and this does not require f to be uniformly continuous. Although I suppose you could object that this is a bit circular, in that I’m assuming the “local modulus of continuity” is computable only in the standard sense, which does not require uniform continuity.
I’m not sure why you would allow singularities at some points (presumably a uniformly discrete set, or something like that) while still insisting on uniform continuity elsewhere. It still seems to me that the arguments for uniform continuity rather than continuity all point to wanting uniform continuity entirely, rather than some sense of local uniform continuity in most places.
Thanks for pointing out the error in my definition of fn; I’ve fixed it.
In your argument that locally compact Polish spaces can be given metrics with respect to which they are proper, it isn’t true that d′ is necessarily a proper metric. For instance, consider a countably infinite set with d(x,y)=1 for x≠y. This is a locally compact Polish space, but f(x)=1 for every x, so d′=d, and the space is not proper.
Your last proposition looks correct (though with a typo: last ⊆ in the proof should be ⊇). However, if X is not locally compact, then the compact-open topology isn’t necessarily the right topology to consider on [0,1]X. We want a topology making [0,1]X into an exponential object, and it isn’t clear that such a topology even exists, or that it is the compact-open topology if it does exist (though it must be a refinement of the compact-open topology if it does exist). Maybe asking about non-locally compact Polish spaces X with a Polish exponential space [0,1]X is a kind of weird question, though, and if we’re even considering non-locally compact Polish spaces, we should turn to the version of the question where we just want a continuous function X×X→[0,1] admitting all continuous functions X→[0,1] as fibers.
I will have to think more about the issue of continuity vs uniform continuity. I suppose my last remaining argument would be the fact that Bishop—Bridges’ classic book on constructive analysis uses uniform continuity on bounded sets rather than continuity, which suggests that it is probably better for constructive analysis at least. But maybe they did not analyze the issue carefully enough, or maybe the relevant issues here are for some reason different.
To fix the argument that every locally compact Polish space admits a proper metric, let f be as before and let F(x,y)=∞ if d(x,y)≥f(x) and F(x,y)=f(x)/[f(x)−d(x,y)] if d(x,y)<f(x). Next, let g(y)=minn[n+F(xn,y)], where (xn) is a countable dense sequence. Then g is continuous and everywhere finite. Moreover, if S=g−1([0,N]), then S⊆⋃n≤NB(xn,(1−1/N)f(xn)) and thus S is compact. It follows that the metric d′(x,y)=d(x,y)+|g(y)−g(x)| is proper.
Anyway I have fixed the typo in my previous post.
Hm, perhaps I should figure out what the significance of uniform continuity on bounded sets is in constructive analysis before dismissing it, even though I don’t see the appeal myself, since constructive analysis is not a field I know much about, but could potentially be relevant here.
f is the reciprocal of what it was before, but yes, this looks good. I am happy with this proof.