# Formal Open Problem in Decision Theory

(This post was origi­nally pub­lished on March 31st 2017, and has been brought for­warded as part of the AI Align­ment Fo­rum launch se­quence on fixed points.)

In this post, I pre­sent a new for­mal open prob­lem. A pos­i­tive an­swer would be valuable for de­ci­sion the­ory re­search. A nega­tive an­swer would be helpful, mostly for figur­ing out what is the clos­est we can get to a pos­i­tive an­swer. I also give some mo­ti­va­tion for the prob­lem, and some par­tial progress.

Open Prob­lem: Does there ex­ist a topolog­i­cal space (in some con­ve­nient cat­e­gory of topolog­i­cal spaces) such that there ex­ists a con­tin­u­ous sur­jec­tion from to the space (of con­tin­u­ous func­tions from to )?

Mo­ti­va­tion:

Topolog­i­cal Nat­u­ral­ized Agents: Con­sider an agent who makes some ob­ser­va­tions and then takes an ac­tion. For sim­plic­ity, we as­sume there are only two pos­si­ble ac­tions, and . We also as­sume that the agent can ran­dom­ize, so we can think of this agent as out­putting a real num­ber in , rep­re­sent­ing its prob­a­bil­ity of tak­ing ac­tion .

Thus, we can think of an agent as hav­ing a policy which is a func­tion from the space of pos­si­ble ob­ser­va­tions to . We will re­quire that our agent be­haves con­tin­u­ously as a func­tion of its ob­ser­va­tions, so we will think of the space of all pos­si­ble poli­cies as the space of con­tin­u­ous func­tions from to , de­noted .

We will let de­note the space of all pos­si­ble agents, and we will have a func­tion which takes in an agent, and out­puts that agent’s policy.

Now, con­sider what hap­pens when there are other agents in the en­vi­ron­ment. For sim­plic­ity, we will as­sume that our agent ob­serves one other agent, and makes no other ob­ser­va­tions. Thus, we want to con­sider the case where , so .

We want to be con­tin­u­ous, be­cause we want a small change in an agent to cor­re­spond to a small change in the agent’s policy. This is par­tic­u­larly im­por­tant since other agents will be im­ple­ment­ing con­tin­u­ous func­tions on agents, and we would like any con­tin­u­ous func­tion on poli­cies to be able to be con­sid­ered valid con­tin­u­ous func­tion on agents.

We also want to be sur­jec­tive. This means that our space of agents is suffi­ciently rich that for any pos­si­ble con­tin­u­ous policy, there is an agent in our space that im­ple­ments that policy.

In or­der to meet all these crite­ria si­mul­ta­neously, we need a space of agents, and a con­tin­u­ous sur­jec­tion .

Unify­ing Fixed Point The­o­rems: While we are pri­mar­ily in­ter­ested in the above mo­ti­va­tion, there is an­other sec­ondary mo­ti­va­tion, which may be more com­pel­ling for those less in­ter­ested in agent foun­da­tions.

There are (at least) two main clusters of fixed point the­o­rems that have come up many times in de­ci­sion the­ory, and math­e­mat­ics in gen­eral.

First, there is the Law­vere cluster of the­o­rems. This in­cludes the Law­vere fixed point the­o­rem, the di­ag­o­nal lemma, and the ex­is­tence of Quines and fixed point com­bi­na­tors. Th­ese are used to prove Gödel’s in­com­plete­ness The­o­rem, Can­tor’s The­o­rem, Löb’s The­o­rem, and achieve ro­bust co­op­er­a­tion in the Pri­soner’s Dilemma in modal frame­work and bounded var­i­ants. All of these can be seen as corol­laries of Law­vere’s fixed point the­o­rem, which states that in a carte­sian closed cat­e­gory, if there is a point-sur­jec­tive map , then ev­ery mor­phism has a fixed point.

Se­cond, there is the Brouwer cluster of the­o­rems. This in­cludes Brouwer’s fixed point the­o­rem, The Kaku­tani fixed point the­o­rem, Poin­caré–Miranda, and the in­ter­me­di­ate value the­o­rem. Th­ese are used to prove the ex­is­tence of Nash Equil­ibria, Log­i­cal In­duc­tors, and Reflec­tive Or­a­cles.

If we had a topolog­i­cal space and a con­tin­u­ous sur­jec­tion , this would al­low us to prove the one-di­men­sional Brouwer fixed point the­o­rem di­rectly us­ing the Law­vere fixed point the­o­rem, and thus unify these two im­por­tant clusters.

Thanks to Qiaochu Yuan for point­ing out the con­nec­tion to Law­vere’s fixed point the­o­rem (and ac­tu­ally ask­ing this ques­tion three years ago).

Par­tial Progress:

Most Di­ag­o­nal­iza­tion In­tu­itions Do Not Ap­ply: A com­mon ini­tial re­ac­tion to this ques­tion is to con­jec­ture that such an does not ex­ist, due to car­di­nal­ity or di­ag­o­nal­iza­tion in­tu­itions. How­ever, note that all of the di­ag­o­nal­iza­tion the­o­rems pass through (some mod­ifi­ca­tion of) the same lemma: Law­vere’s fixed point the­o­rem. How­ever, this lemma does not ap­ply here!

For ex­am­ple, in the cat­e­gory of sets, the rea­son that there is no sur­jec­tion from any set to the power set, , is be­cause if there were such a sur­jec­tion, Law­vere’s fixed point the­o­rem would im­ply that ev­ery func­tion from to it­self has a fixed point (which is clearly not the case, since there is a func­tion that swaps and ).

How­ever, we already know by Brouwer’s fixed point the­o­rem that ev­ery con­tin­u­ous func­tion from the in­ter­val to it­self has a fixed point, so the stan­dard di­ag­o­nal­iza­tion in­tu­itions do not work here.

Im­pos­si­ble if You Re­place with e.g. : This also pro­vides a quick san­ity check on at­tempts to con­struct an . Any con­struc­tion that would not be mean­ingfully differ­ent if the in­ter­val is re­placed with the cir­cle is doomed from the start. This is be­cause a con­tin­u­ous sur­jec­tion would vi­o­late Law­vere’s fixed point the­o­rem, since there is a con­tin­u­ous map from to it­self with­out fixed points.

Im­pos­si­ble if you Re­quire a Homeo­mor­phism: When I first asked this ques­tion I asked for a home­o­mor­phism be­tween and . Sam Eisen­stat has given a very clever ar­gu­ment why this is im­pos­si­ble. You can read it here. In short, us­ing a home­o­mor­phism, you would be able to use Law­vere to con­struct a con­tin­u­ous map that send a func­tion from to it­self to a fixed point of that func­tion. How­ever, no such con­tin­u­ous map ex­ists.

Notes:

If you pre­fer not to think about the topol­ogy of , you can in­stead find a space , and a con­tin­u­ous map , such that for ev­ery con­tin­u­ous func­tion , there ex­ists an , such that for all , .

Many of the de­tails in the mo­ti­va­tion could be differ­ent. I would like to see progress on similar ques­tions. For ex­am­ple, you could add some com­putabil­ity con­di­tion to the space of func­tions. How­ever, I am also very cu­ri­ous which way this spe­cific ques­tion will go.

This post came out of many con­ver­sa­tions, with many peo­ple, in­clud­ing: Sam, Qiaochu, Tsvi, Jes­sica, Pa­trick, Nate, Ryan, Mar­cello, Alex Men­nen, Jack Gal­lagher, and James Cook.

This post was origi­nally pub­lished on March 31st 2017, and has been brought for­warded as part of the AI Align­ment Fo­rum launch se­quences.

To­mor­row’s AIAF se­quences post will be ‘Iter­ated Am­plifi­ca­tion and Distil­la­tion’ by Ajeya Co­tra, in the se­quence on iter­ated am­plifi­ca­tion.

• When think­ing about agents, the first mo­ti­va­tion might not quite work out. Small changes in ob­ser­va­tion might in­tro­duce dis­con­tin­u­ous changes in policy—e.g. in the Match­ing Pen­nies game. Sup­pose there are agents (func­tions) in that out­put a fixed , no mat­ter their in­put. If you can con­tin­u­ously vary by mov­ing in , then Match­ing Pen­nies play will be dis­con­tin­u­ous at . So right away you’ve com­mit­ted to some un­usual be­hav­ior for the agents in by ask­ing for con­ti­nu­ity—they can’t play perfect Match­ing Pen­nies at the very least.

• A small note: it’s not hard to con­struct spaces that are a bit too big, or a bit too small (rais­ing the pos­si­bil­ity that a true lies be­tween them).

For in­stance, if is the unit in­ter­val, then we can map onto the countable hy­per­cube ( https://​​en.wikipe­dia.org/​​wiki/​​Space-filling_curve#The_Hahn.E2.80.93Mazurk­iewicz_the­o­rem ). Then if we pick an or­der­ing of the di­men­sions of the hy­per­cube and an or­der­ing of , we can see any el­e­ment of - hence any el­e­ment of - as a func­tion from to .

Let be the space of con­tin­u­ous func­tions . Then any el­e­ment of defines a unique func­tion (the con­verse is not true—most func­tions do not cor­re­spond to con­tin­u­ous func­tions ). Pul­ling back to via we define the set .

Thus maps sur­jec­tively onto . How­ever, though maps into by re­stric­tion (any func­tion from is a func­tion from ), this map is not onto (for ex­am­ple, there are more con­tin­u­ous func­tions from than there are from , be­cause of the po­ten­tial dis­con­ti­nu­ity at ).

Now, there are el­e­ments of that map to func­tions in but not in . So there’s a hope that there may ex­ist an with , , and map­ping onto . Ba­si­cally, as `gets big­ger’, its image in grows, while it­self shrinks, and hope­fully they’ll meet.

• I think you made a mis­take here

The Hahn–Mazurk­iewicz the­o­rem states that

A non-empty Haus­dorff topolog­i­cal space is a con­tin­u­ous image of the unit in­ter­val if and only if it is a com­pact, con­nected, lo­cally con­nected sec­ond-countable space.

I will agree that is con­nected and lo­cally con­nected. I’m not sure if its sec­ond countable. It is not com­pact.

Just to be clear Now let . Clearly each is open. Let And . Now clearly this fam­ily cov­ers all of . How­ever, re­move any from and is no longer cov­ered. So is a fam­ily of open sets, which cover and don’t have any finite sub­cover.

• Hum, should be com­pact by Ty­chonoff’s the­o­rem (see also the Hilbert Cube, which is home­o­mor­phic to ).

For your proof, I think that is not open in the product topol­ogy. The product topol­ogy is the coars­est topol­ogy where all the pro­jec­tion maps are con­tin­u­ous.

To make all the pro­jec­tion maps con­tin­u­ous we need all sets in to be open, where we define iff there ex­ists an , such that is open in and .

Let be the set of finite in­ter­sec­tion of these sets. For any , there ex­ists a finite set such that if and for , then as well.

If we take to be the ar­bi­trary union of , this con­di­tion will be pre­served. Thus is not con­tained in the ar­bi­trary unions and finite in­ter­sec­tions of , so it seems it is not an open sent.

Also, is sec­ond-countable. From the wikipe­dia ar­ti­cle on sec­ond-countable:

Any countable product of a sec­ond-countable space is sec­ond-countable

• I’ve figured out the differ­ence, I was us­ing the box topol­ogy https://​​en.wikipe­dia.org/​​wiki/​​Box_topol­ogy , while you were us­ing the https://​​en.wikipe­dia.org/​​wiki/​​Product_topol­ogy.

You are cor­rect. I knew about finite topolog­i­cal prod­ucts and made a nat­u­ral gen­er­al­iza­tion, but it turns out not to be the stan­dard mean­ing of .

• Thanks for in­tro­duc­ing me to the box topol­ogy—see­ing it defined so ex­plic­itly, and see­ing what prop­er­ties it fails, cleared up a few of my in­tu­itions.

• If I were study­ing this, I would be look­ing at do­main the­ory, in which (among other things) there has been found a topolog­i­cal space home­o­mor­phic with . The page I linked links to some notes at the bot­tom. (h/​t Qiaochu for point­ing out do­main the­ory)

• From dis­cus­sions I had with Sam, Scott, and Jack:

To solve the prob­lem, it would suffice to find a re­flex­ive do­main with a re­tract onto .

This is be­cause if you have a re­flex­ive do­main , that is, an with a con­tin­u­ous sur­jec­tive map , and is a re­tract of , then there’s also a con­tin­u­ous sur­jec­tive map .

Proof: If is a re­tract of then we have a re­trac­tion and a sec­tion with . Con­struct . To show that is a sur­jec­tion con­sider an ar­bi­trary . Thus, . Since is a sur­jec­tion there must be some with . It fol­lows that . Since was ar­bi­trary, is also a sur­jec­tion.

• Ok, here’s an idea for con­struct­ing such a map, with a few key de­tails left un­proven; let me know if peo­ple see any im­me­di­ate flaws in the ap­proach, be­fore I spend time filling in the holes.

Let be a countable col­lec­tion of open in­ter­vals (eg ), given the usual topol­ogy. Let be the closed unit in­ter­val, and the set of con­tin­u­ous func­tions from to . Give the com­pact-open topol­ogy.

By the prop­er­ties of the com­pact-open topol­ogy, since is (Ty­chonoff), then so is . I’m hop­ing that the proof can be ex­tended, at least in this case, to show that is (nor­mal Hauss­dorff).

It seems clear that is sec­ond-countable: let con­sist of all func­tions that map into , where is the in­ter­sec­tion of with a closed in­ter­val with ra­tio­nal end­points, and is an open in­ter­val with ra­tio­nal end­points. The set of all such is countable, and forms a sub­ba­sis of . A countable sub­ba­sis means a countable ba­sis, as the set of finite sub­sets of countable set, is it­self countable.

If is and sec­ond countable, then it is home­o­mor­phic to a sub­set of the Hilbert Cube. To sim­plify no­ta­tion, we will iden­tify with its image in the Hilbert Cube.

Take the clo­sure of within the Hilbert Cube. This clo­sure is com­pact and sec­ond countable (since the Hilbert Cube it­self is both). It seems clear that is con­nected and lo­cally con­nected; con­nected will ex­tend to the clo­sure, we’ll need to prove that lo­cally con­nected does as well.

Then we can ap­ply the Hahn-Mazurk­iewicz the­o­rem:

• A non-empty Haus­dorff topolog­i­cal space is a con­tin­u­ous image of the unit in­ter­val if and only if it is a com­pact, con­nected, lo­cally con­nected sec­ond-countable space.

So there is a con­tin­u­ous sur­jec­tion . Pull back , defin­ing . If is open in (with the sub­space topol­ogy), then is open in . Even if is not open, we can hope that, at worst, it con­sists of a countable col­lec­tion of points, open in­ter­vals, half-closed in­ter­vals, and closed in­ter­vals (this is not a gen­eral prop­erty of sub­sets of the in­ter­val, cf the Can­tor set, but it feels very likely that it will ap­ply here).

In that case, these is a con­tin­u­ous sur­jec­tion from to , map­ping each open in­ter­val to one of the points or in­ter­vals (“fold­ing” over the ends when map­ping to those with closed end-points).

Then is the con­tin­u­ous sur­jec­tion we are look­ing for.

Note: I’m think­ing now that might not be con­nected, but this would not be a prob­lem as long as it has a countable num­ber of con­nected com­po­nents.

• I am go­ing to take some li­cense with your ques­tion be­cause I think you are ask­ing the wrong ques­tion. Ar­bi­trary topolog­i­cal spaces and ab­stract con­ti­nu­ity are rarely the right no­tions in real-world situ­a­tions. Rather, uniform con­ti­nu­ity on bounded sets usu­ally bet­ter cor­re­sponds to the in­tu­itive no­tion of “a small change in in­put pro­duces a small change in out­put”.

Thus, sup­pose that is a com­plete sep­a­rable met­ric space and that is uniformly con­tin­u­ous on bounded sets. Then we can show that there ex­ists a func­tion which is uniformly con­tin­u­ous on bounded sets but not a fiber of (i.e. there is no such that for all ). In­deed, con­sider two cases:

1. is uniformly dis­crete. Then ev­ery map from to is uniformly con­tin­u­ous, so we get a con­tra­dic­tion from car­di­nal­ity con­sid­er­a­tions.

2. is not uniformly dis­crete. Then for each n, since f is uniformly con­tin­u­ous on it has a mod­u­lus of con­ti­nu­ity on this set, i.e. a con­tin­u­ous in­creas­ing func­tion such that for all . Since is not uniformly dis­crete, there is a func­tion such that for in­finitely many , there ex­ist such that . (To con­struct it, take pairs with , ex­tract a sub­se­quence that be­haves ge­o­met­ri­cally nicely, and then find a func­tion such that for all in the sub­se­quence.) Clearly, can­not be a fiber of .

• can be a fiber of , since for each , and could be dis­tance greater than from the base­point.

Ex­am­ple: let , with for and . Let be the base­point (so that is the point you were call­ing “”). Let , , , and .

I also don’t see how to even con­struct the func­tion , or, re­lat­edly, what you mean by “ge­o­met­ri­cally nicely”, but I guess it doesn’t mat­ter.

Also, I’m not con­vinced that met­ric spaces with uniform con­ti­nu­ity on bounded sub­sets is a bet­ter frame­work than topolog­i­cal spaces with con­ti­nu­ity.

• This is in­tended as a re­ply to David Sim­mons’s com­ment, which for some rea­son I can’t re­ply to di­rectly.

In the new ver­sion of your proof, how do we know isn’t too close to for some ? And how do we know that is uniformly con­tin­u­ous on bounded sub­sets?

About con­ti­nu­ity ver­sus uniform con­ti­nu­ity on bounded sets:

It seems to me that your point 1 is just a pithier ver­sion of your point 4, and that these points sup­port pay­ing at­ten­tion to uniform con­ti­nu­ity, rather than uniform con­ti­nu­ity re­stricted to bounded sets. This ver­sion of the prob­lem seems like it would be a less messy ver­sion of the “fixed mod­u­lus of con­ti­nu­ity” ver­sion of the prob­lem you men­tioned (which I did not un­der­stand your solu­tion to, but will look again later).

I’m not sure what you’re get­ting at about sin­gu­lar­i­ties in point 3. I wouldn’t have asked why you were con­sid­er­ing uniform con­ti­nu­ity on bounded sets in­stead of uniform con­ti­nu­ity away from sin­gu­lar­i­ties (in fact, I don’t know what that means). I would ask, though, why uniform con­ti­nu­ity on bounded sets in­stead of uniform con­ti­nu­ity on com­pact sets? As you point out, the lat­ter is the same as con­ti­nu­ity.

Your point 2 is com­pletely wrong, and in fact this is the pri­mary rea­son I was con­vinced that con­ti­nu­ity is a bet­ter thing to pay at­ten­tion to than uniform con­ti­nu­ity on bounded sets. The type of ob­ject you are de­scribing is an effec­tive Pol­ish space that re­mem­bers its met­ric. Typ­i­cally, de­scrip­tive set the­o­rists for­get the met­ric, and the iso­mor­phisms be­tween Pol­ish spaces are home­o­mor­phisms (and the iso­mor­phisms be­tween effec­tive Pol­ish spaces are com­putable home­o­mor­phisms). Chang­ing the met­ric in a com­putably home­o­mor­phic way does not change what can be done when points are rep­re­sented as de­scend­ing chains of ba­sic open sets with sin­gle­ton in­ter­sec­tion. So the thing you de­scribed was re­ally topolog­i­cal rather than met­ric in na­ture, even though it in­volves in­tro­duc­ing a met­ric in the setup. I am not aware of any no­tions of com­putabil­ity in met­ric spaces in which the met­ric mat­ters in the way you are sug­gest­ing. It is not true that uniform con­ti­nu­ity gives you an al­gorithm for com­put­ing the func­tion. As a coun­terex­am­ple, let be an un­com­putable num­ber, and let be given by for ev­ery . is clearly uniformly con­tin­u­ous, but not com­putable. It is also not true that uniform con­ti­nu­ity is nec­es­sary in or­der for the func­tion to be com­putable. For in­stance, is com­putable on . Of course, is not com­plete, but for an­other ex­am­ple, con­sider an effec­tive in­finite-di­men­sional Hilbert space, and let be an effec­tive or­thonor­mal ba­sis. Let . This se­quence of func­tions is com­putable, they have dis­joint sup­port, and for any point, a suffi­ciently small neigh­bor­hood around it will be dis­joint from the sup­ports of all but at most one of these func­tions. Thus is com­putable, but of course it is not uniformly con­tin­u­ous on the unit ball, which is bounded. How­ever, it is true that ev­ery com­putable func­tion is con­tin­u­ous, and con­versely, ev­ery con­tin­u­ous func­tion is com­putable with re­spect to some or­a­cle. Of course, we re­ally want com­putabil­ity, not com­putabil­ity with re­spect to some or­a­cle, but this still seems to show that con­ti­nu­ity is at least a good metaphor for com­putabil­ity, whereas uniform con­ti­nu­ity on bounded sets doesn’t seem so to me.

Of course, all this about con­ti­nu­ity as a metaphor for com­putabil­ity makes the most sense in the con­text of Pol­ish spaces, and we can only talk about ac­tual com­putabil­ity in the con­text of effec­tive Pol­ish spaces. Scott’s prob­lem in­volves a space and the ex­po­nen­tial . If is a lo­cally com­pact Pol­ish space, then is also Pol­ish. I think that this might be nec­es­sary (that is, if and are Pol­ish, then is lo­cally com­pact), al­though I’m not sure. If so, and if your proof is cor­rect, it seems plau­si­ble that your proof could be adapted to show that there is no lo­cally com­pact Pol­ish space with the prop­erty that Scott was look­ing for, and that would show that there is no solu­tion to the prob­lem in which and are both Pol­ish spaces, and hence no com­putable solu­tion, if com­putabil­ity is for­mal­ized as in effec­tive de­scrip­tive set the­ory.

• I don’t know why my com­ment doesn’t have a re­ply but­ton. Maybe it is re­lated to the fact that my com­ment shows up as “deleted” when I am not logged in.

Sorry, I seem to be get­ting a lit­tle lazy with these proofs. Hope­fully I haven’t missed any­thing this time.

New proof: … We can ex­tract a sub­se­quence such that if and , then for all , and for all and , ei­ther (A) and or (B) and . By ex­tract­ing a fur­ther sub­se­quence we can as­sume that which of (A) or (B) holds de­pends only on and not on . By swap­ping and if nec­es­sary we can as­sume that case (A) always holds.

Lemma: For each there is at most one such that .

Proof: Sup­pose and , with . Then , a con­tra­dic­tion.

It fol­lows that by ex­tract­ing a fur­ther sub­se­quence we can as­sume that for all .

Now let be an in­creas­ing uniformly con­tin­u­ous func­tion such that and for all . Fi­nally, let . Then for all we have . On the other hand, for all we have , for we have , and for we have . Thus . Clearly, can­not be a fiber of . More­over, since the func­tions and are both uniformly con­tin­u­ous, so is .

Re­gard­ing your re­sponses to my points:

I guess I don’t dis­agree with what you write re­gard­ing my points 1 and 4.

It seems to be harder than ex­pected to ex­plain my in­tu­itions re­gard­ing sin­gu­lar­i­ties in point 3. Ba­si­cally, I think the rea­sons that ab­stract con­ti­nu­ity came to be con­sid­ered stan­dard are mostly the fact that in con­crete ap­pli­ca­tions you have to worry about sin­gu­lar­i­ties, and this makes uniform con­ti­nu­ity a lit­tle more tech­ni­cally an­noy­ing. But in the kind of prob­lem we are con­sid­er­ing here, it seems that con­ti­nu­ity is re­ally more an­noy­ing to deal with than uniform con­ti­nu­ity, with lit­tle added benefit. I guess it also de­pends on what kinds of func­tions you ex­pect to ac­tu­ally come up, which is a heuris­tic judge­ment. Any­way it might not be pro­duc­tive to con­tinue this line of rea­son­ing fur­ther as maybe our dis­agree­ments just come down to in­tu­itions.

Re­gard­ing my point 2, I wasn’t very clear when I said that uniform con­ti­nu­ity gives you an al­gorithm, what I meant was that if you have an al­gorithm for com­put­ing the images of points in the dense se­quence and for com­put­ing the mod­u­lus of con­ti­nu­ity func­tion, then uniform con­ti­nu­ity gives you an al­gorithm. The func­tion would be the kind of thing I would han­dle with uniform con­ti­nu­ity away from sin­gu­lar­i­ties (to fix a defi­ni­tion for this, let us say that you are uniformly con­tin­u­ous away from sin­gu­lar­i­ties if you are uniformly con­tin­u­ous on sets of the form , where is some set of sin­gu­lar­i­ties).

In your defi­ni­tion of , I think you mean to write max in­stead of min. But I see your point, though the ex­am­ple seems a lit­tle patholog­i­cal to me.

Any­way, it seems that you agree that it makes sense to re­strict to Pol­ish spaces based on com­putabil­ity con­sid­er­a­tions, which is part of what I was try­ing to say in 2.

If you have a lo­cally com­pact Pol­ish space, then you can find a met­ric with re­spect to which the space is proper (i.e. bounded sub­sets are com­pact): let , where is com­pact. With re­spect to this met­ric, con­ti­nu­ity is the same as uniform con­ti­nu­ity on bounded sets, so my proof should work then.

Propo­si­tion: Let be a Pol­ish space that is not lo­cally com­pact. Then (with the com­pact-open topol­ogy) is not first countable.

Proof: Sup­pose oth­er­wise. Then the func­tion has a countable neigh­bor­hood ba­sis of sets of the form where is com­pact and is open. Since is not lo­cally com­pact, there ex­ists a point such that is not com­pact for any . For each , we can choose . Let , and note that is com­pact. Then is a neigh­bor­hood of . But then for some . This con­tra­dicts the fact that , since we can find a bump func­tion which is on but at .

It does still seem to me that most of the use­ful in­tu­ition comes from point 4 of my pre­vi­ous com­ment, though.

• It ap­pears that com­ments from new users are col­lapsed by de­fault, and can­not be replied to with­out a “Like”. Th­ese seem like bad fea­tures.

Your proof that there’s no uniformly con­tin­u­ous on bounded sets func­tion ad­mit­ting all uniformly con­tin­u­ous on bounded sets func­tions as fibers looks cor­rect now. It also looks like it can be eas­ily adapted to show that there is no uniformly con­tin­u­ous ad­mit­ting all uniformly con­tin­u­ous func­tions as fibers. Come to think of it, your proof works for ar­bi­trary met­ric spaces , not just com­plete sep­a­rable met­ric spaces, though those are nicer.

I see what you mean now about uniform con­ti­nu­ity giv­ing you an al­gorithm, but I still don’t think that’s spe­cific to uniform con­ti­nu­ity in an im­por­tant way. After all, if you have an al­gorithm for com­put­ing images of points in the countable dense set, and a com­putable “lo­cal mod­u­lus of con­ti­nu­ity” in the sense of a com­putable func­tion with and , then is com­putable, and this does not re­quire to be uniformly con­tin­u­ous. Although I sup­pose you could ob­ject that this is a bit cir­cu­lar, in that I’m as­sum­ing the “lo­cal mod­u­lus of con­ti­nu­ity” is com­putable only in the stan­dard sense, which does not re­quire uniform con­ti­nu­ity.

I’m not sure why you would al­low sin­gu­lar­i­ties at some points (pre­sum­ably a uniformly dis­crete set, or some­thing like that) while still in­sist­ing on uniform con­ti­nu­ity el­se­where. It still seems to me that the ar­gu­ments for uniform con­ti­nu­ity rather than con­ti­nu­ity all point to want­ing uniform con­ti­nu­ity en­tirely, rather than some sense of lo­cal uniform con­ti­nu­ity in most places.

Thanks for point­ing out the er­ror in my defi­ni­tion of ; I’ve fixed it.

In your ar­gu­ment that lo­cally com­pact Pol­ish spaces can be given met­rics with re­spect to which they are proper, it isn’t true that is nec­es­sar­ily a proper met­ric. For in­stance, con­sider a countably in­finite set with for . This is a lo­cally com­pact Pol­ish space, but for ev­ery , so , and the space is not proper.

Your last propo­si­tion looks cor­rect (though with a typo: last in the proof should be ). How­ever, if is not lo­cally com­pact, then the com­pact-open topol­ogy isn’t nec­es­sar­ily the right topol­ogy to con­sider on . We want a topol­ogy mak­ing into an ex­po­nen­tial ob­ject, and it isn’t clear that such a topol­ogy even ex­ists, or that it is the com­pact-open topol­ogy if it does ex­ist (though it must be a re­fine­ment of the com­pact-open topol­ogy if it does ex­ist). Maybe ask­ing about non-lo­cally com­pact Pol­ish spaces with a Pol­ish ex­po­nen­tial space is a kind of weird ques­tion, though, and if we’re even con­sid­er­ing non-lo­cally com­pact Pol­ish spaces, we should turn to the ver­sion of the ques­tion where we just want a con­tin­u­ous func­tion ad­mit­ting all con­tin­u­ous func­tions as fibers.

• I will have to think more about the is­sue of con­ti­nu­ity vs uniform con­ti­nu­ity. I sup­pose my last re­main­ing ar­gu­ment would be the fact that Bishop—Bridges’ clas­sic book on con­struc­tive anal­y­sis uses uniform con­ti­nu­ity on bounded sets rather than con­ti­nu­ity, which sug­gests that it is prob­a­bly bet­ter for con­struc­tive anal­y­sis at least. But maybe they did not an­a­lyze the is­sue care­fully enough, or maybe the rele­vant is­sues here are for some rea­son differ­ent.

To fix the ar­gu­ment that ev­ery lo­cally com­pact Pol­ish space ad­mits a proper met­ric, let be as be­fore and let if and if . Next, let , where is a countable dense se­quence. Then is con­tin­u­ous and ev­ery­where finite. More­over, if , then and thus is com­pact. It fol­lows that the met­ric is proper.

Any­way I have fixed the typo in my pre­vi­ous post.

• Hm, per­haps I should figure out what the sig­nifi­cance of uniform con­ti­nu­ity on bounded sets is in con­struc­tive anal­y­sis be­fore dis­miss­ing it, even though I don’t see the ap­peal my­self, since con­struc­tive anal­y­sis is not a field I know much about, but could po­ten­tially be rele­vant here.

is the re­cip­ro­cal of what it was be­fore, but yes, this looks good. I am happy with this proof.

• Ah, you’re right. The proof can be fixed by chang­ing the di­vi­sion be­tween the two cases. So here is the new proof, with more de­tails added re­gard­ing the con­struc­tion of :

1. is uniformly dis­crete for all . Then ev­ery map from to is uniformly con­tin­u­ous on bounded sets, so we get a con­tra­dic­tion from car­di­nal­ity con­sid­er­a­tions.

2. is not uniformly dis­crete for some . Then for each , since f is uniformly con­tin­u­ous on it has a mod­u­lus of con­ti­nu­ity on this set, i.e. a con­tin­u­ous in­creas­ing func­tion such that for all . Since is not uniformly dis­crete, there ex­ist such that and . We can ex­tract a sub­se­quence such that if and , then for all , and for all and , ei­ther (A) or (B) . By ex­tract­ing a fur­ther sub­se­quence we can as­sume that which of (A) or (B) holds de­pends only on and not on . By swap­ping and if nec­es­sary we can as­sume that case (A) always holds. Now let be an in­creas­ing con­tin­u­ous func­tion such that for all . Fi­nally, let . Then for all we have but . Clearly, can­not be a fiber of .

Re­gard­ing the ap­pro­pri­ate­ness of met­ric spaces /​ uniform con­ti­nu­ity rather than topolog­i­cal spaces /​ ab­stract con­ti­nu­ity, here are some of the rea­sons be­hind my in­tu­ition here (de­vel­oped work­ing in math­e­mat­i­cal anal­y­sis, speci­fi­cally Dio­phan­tine ap­prox­i­ma­tion, and also con­struc­tive math­e­mat­ics):

1. The ob­vi­ous: met­ric spaces are ex­plic­itly meant to rep­re­sent the in­tu­itive no­tion of al­ike­ness as a quan­ti­ta­tive con­cept (i.e. dis­tance), whereas topolog­i­cal spaces have no ex­plicit no­tion of al­ike­ness.

2. In com­putabil­ity the­ory, one is in­ter­ested in the ques­tion of how to com­pu­ta­tion­ally rep­re­sent a point or an ap­prox­i­ma­tion to a point in a space. The stan­dard way to do this is via re­strict­ing to the class of com­plete sep­a­rable met­ric spaces, fix­ing a countable dense se­quence (as­sumed to be rep­re­sen­ta­tive of the struc­ture of the met­ric space), and defin­ing a com­pu­ta­tional ap­prox­i­ma­tion to a point to be an ex­pres­sion of the form . Since and are in­te­gers this ex­pres­sion can be coded as finite data. One then defines a com­pu­ta­tional en­cod­ing of a point to be an in­finite bit­stream con­sist­ing of com­pu­ta­tional ap­prox­i­ma­tions that con­verge to the point.

In prac­ti­cal ap­pli­ca­tions, in the end you will want ev­ery­thing to be com­putable. So it makes sense to work in a frame­work where there are nat­u­ral no­tions of com­putabil­ity. I am not aware of any such no­tions for gen­eral topolog­i­cal spaces.

3. Re­gard­ing con­ti­nu­ity vs uniform con­ti­nu­ity in met­ric spaces, both are say­ing that if two points are close in the do­main, their images are also close. But the lat­ter gives you a straight­for­ward es­ti­mate as to how close, whereas the former says that the de­gree of close­ness may de­pend on one of the points. Now, there are good rea­sons to con­sider such de­pen­dence, since even nat­u­ral func­tions on the real num­bers (such as or ) have “sin­gu­lar­i­ties” where they are not uniformly con­tin­u­ous.

So the ques­tion is whether to mod­ify the no­tion of uniform con­ti­nu­ity to di­rectly ac­count for sin­gu­lar­i­ties, or to use the stan­dard defi­ni­tion of con­ti­nu­ity in­stead. But if one works with the stan­dard defi­ni­tion, then most of the time one is re­ally look­ing for ways to sneak back to uniform con­ti­nu­ity, e.g. by us­ing the fact that a con­tin­u­ous func­tion on a com­pact set is uniformly con­tin­u­ous.

An in­tu­itive way of think­ing about the fact that a con­tin­u­ous func­tion on a com­pact set is uniformly con­tin­u­ous is that the no­tion of com­pact­ness means that there are no sin­gu­lar­i­ties pre­sent “within the space”. For ex­am­ple, if we go back to the func­tions or , then the sin­gu­lar­ity of the first oc­curs at in­finity, while the sin­gu­lar­ity of the lat­ter oc­curs at . If we take a com­pact sub­set of the do­main of ei­ther func­tion, then what it re­ally means is that we are avoid­ing the sin­gu­lar­ity.

By con­trast, non-com­pact­ness should mean that there are sin­gu­lar­i­ties. In some cases like it is easy to iden­tify what the sin­gu­lar­i­ties are. But if we are deal­ing with spaces that are not lo­cally com­pact like or an in­finite-di­men­sional Hilbert space, then it is not as clear what the sin­gu­lar­i­ties are, there is just a gen­eral sense that they are dis­persed “through­out the space” (be­cause the space is not not lo­cally com­pact).

But you have to ask your­self, are these sin­gu­lar­i­ties real or just imag­ined? In many cases, imag­ined. For ex­am­ple, in the the­ory of Banach spaces con­tin­u­ous lin­ear maps are always uniformly con­tin­u­ous.

What about a map that is not uniformly con­tin­u­ous, like the in­ver­sion map in in­finite-di­men­sional Hilbert space? In this case, there is still a sin­gu­lar­ity—at -- and the defi­ni­tion of con­ti­nu­ity needs to re­flect that. But it doesn’t help to imag­ine all sorts of other sin­gu­lar­i­ties dis­persed through­out the space, be­cause that pre­vents you from mak­ing use­ful state­ments like: if are at least away from and , then , where is an ab­solute con­stant.

Now the ex­am­ple in the pre­vi­ous para­graph is an ex­am­ple of quan­ti­ta­tive con­ti­nu­ity, which is stronger than uniform con­ti­nu­ity away from sin­gu­lar­i­ties. But the point is that it can be seen as an ex­ten­sion of uniform con­ti­nu­ity away from sin­gu­lar­i­ties.

4. Maybe my last rea­son will be the most rele­vant from a nat­u­ral­ized agent per­spec­tive. The no­tion of uniform con­ti­nu­ity is im­por­tant be­cause it in­tro­duces the mod­u­lus of con­ti­nu­ity, which can be viewed as a mea­sure of how con­tin­u­ous a func­tion is. The re­stric­tion that an agent must be uniformly con­tin­u­ous can be then thought of in a quan­ti­ta­tive sense, with “bet­ter” agents less hav­ing to fol­low this re­stric­tion. So a more pow­er­ful agent may have a looser (larger) mod­u­lus of con­ti­nu­ity, be­cause it can re­act more pre­cisely to differ­ent pos­si­ble in­puts.

In this ter­minol­ogy, my proof can be thought of as giv­ing an in­tu­itive rea­son for why the agent can­not im­ple­ment ev­ery pos­si­ble policy: the agent has limited re­sources to dis­t­in­guish differ­ent in­puts, so it can only im­ple­ment those poli­cies that can be im­ple­mented with these limited re­sources.

The ob­vi­ous fol­lowup ques­tion would be whether if you re­strict your at­ten­tion to the poli­cies that the agent isn’t pre­vented from im­ple­ment­ing due to its limited re­sources, then can it im­ple­ment ev­ery pos­si­ble policy? Or in other words, if you fix a mod­u­lus of con­ti­nu­ity from the out­set, can you in­clude all func­tions with that mod­u­lus of con­ti­nu­ity as fibers?

If you al­low the ev­ery-policy func­tion to have an ar­bi­trary mod­u­lus of con­ti­nu­ity un­re­lated to the mod­u­lus of con­ti­nu­ity you are try­ing to imi­tate, then it is not hard to see that this is pos­si­ble at least for some spaces. (By Arzela-As­coli the space of func­tions with a fixed mod­u­lus of con­ti­nu­ity is com­pact, so there ex­ists a con­tin­u­ous sur­jec­tion from to this space.) But this may re­quire greatly in­creas­ing the re­sources that the agent must spend to differ­en­ti­ate in­puts. On the other hand, re­quiring the ex­act same mod­u­lus of con­ti­nu­ity seems like too rigid an as­sump­tion. So the right ques­tion is prob­a­bly to ask how close can the mod­u­lus of con­ti­nu­ity of the ev­ery-policy func­tion be to the mod­u­lus it is try­ing to imi­tate.

For this kind of ques­tion it is prob­a­bly bet­ter to work with a con­crete ex­am­ple rather than try­ing to prove some­thing in gen­er­al­ity, so I will work with the Can­tor space with the met­ric . Sup­pose we want to imi­tate all func­tions such that im­plies . (I know this is not quite the same as the origi­nal ques­tion, but I think it is close enough.) If then there are such func­tions. So if we have a sin­gle func­tion that has all of them as fibers, then by the pi­geon­hole prin­ci­ple there is some ball of the form that con­tains two such fibers. But then if and are the two fibers, then there ex­ists such that . It fol­lows that if we want to choose such that im­plies (i.e. the analogue of the as­sump­tion on but with re­placed by ) then we need .

In con­clu­sion, the re­quired ac­cu­racy of is dou­bly ex­po­nen­tial with re­spect to the re­quired ac­cu­racy of . Thus, it is not fea­si­ble to im­ple­ment such a func­tion.

• I give a stronger ver­sion of this prob­lem here.

• “Self-Refer­ence and Fixed Points: A Dis­cus­sion and an Ex­ten­sion of Law­vere’s The­o­rem” by Jorge Soto-An­drade and Fran­cisco J. Varela seems like a po­ten­tially rele­vant re­sult. In par­tic­u­lar, they prove a con­verse Law­vere re­sult in the cat­e­gory of posets (though they men­tion do­ing this for in an un­solved prob­lem.) I’m cur­rently read­ing through this and re­lated pa­pers with an eye to adapt­ing their con­struc­tion to (I think you can’t just use it straight-for­wardly be­cause even though you can build a re­flex­ive do­main with a re­tract to an ar­bi­trary poset, the pa­per uses a differ­ent no­tion of con­ti­nu­ity for posets.)

• Can you ar­gue that must have a semi-met­ric com­pat­i­ble with the topol­ogy by us­ing ?

I’m won­der­ing if you can gen­er­al­ise this to some sort of ar­gu­ment that goes like this. Us­ing X, pro­ject down via from to . Let be our ini­tial sur­jec­tion; it’s now a bi­jec­tion be­tween and maps from to .

If the pro­jec­tion is con­tin­u­ous, then ev­ery map from to lifts to a map from to . Restrict­ing to the sub­set of maps that are lifts like this, and ap­ply­ing , gives a sub­set . We now have a new equiv­alence re­la­tion­ship, maps from that are equal to each other on . Pro­ject down from by this re­la­tion­ship, to gen­er­ate . Con­tinue this trans­finitely of­ten (?) to gen­er­ate a space where is a home­o­mor­phism, and find a con­tra­dic­tion?

This feels du­bi­ous, but maybe worth men­tion­ing...

• I haven’t checked that ar­gu­ment care­fully, but that sounds like it should give you with a con­tin­u­ous bi­jec­tion , which might not nec­es­sar­ily be a home­o­mor­phism.

• Yes, you’re right.

• This com­ment is to ex­plain par­tial re­sults ob­tained by David Sim­mons in this thread, since the re­sults and their proofs are difficult to fol­low as a re­sult of be­ing dis­tributed across mul­ti­ple com­ments, with many er­rors and cor­rec­tions. The proofs given here are due to David Sim­mons.

#Statements

The­o­rem 1: There is no met­ric space and uniformly con­tin­u­ous func­tion such that ev­ery uniformly con­tin­u­ous func­tion is a fiber of .

The­o­rem 2: There is no met­ric space and func­tion that is uniformly con­tin­u­ous on bounded sets, such that ev­ery func­tion which is uniformly con­tin­u­ous on bounded sets is a fiber of .

The­o­rem 3: There is no lo­cally com­pact Pol­ish space and con­tin­u­ous func­tion such that ev­ery con­tin­u­ous func­tion is a fiber of .

# Commentary

The­o­rem 1 says that there is no solu­tion to the ver­sion of Scott’s prob­lem with con­ti­nu­ity in topolog­i­cal spaces re­placed with uniform con­ti­nu­ity in met­ric spaces. A plau­si­ble rea­son that this ver­sion of the prob­lem might be im­por­tant is that if an agent has to be able to com­pute what its policy says to do to any de­sired pre­ci­sion us­ing an amount of com­pu­ta­tional re­sources that does not de­pend on the in­put, then its policy must be uniformly con­tin­u­ous. The gist of the proof is that for any uniformly con­tin­u­ous , it is pos­si­ble to con­struct a uniformly con­tin­u­ous func­tion that re­quires greater pre­ci­sion in its in­put than does to de­ter­mine the out­put to any de­sired pre­ci­sion. I sus­pect it might be pos­si­ble to adapt the proof to work in uniform spaces rather than just met­ric spaces, but I have not stud­ied uniform spaces.

The­o­rem 2 is similar to the­o­rem 1, but with uniform con­ti­nu­ity re­placed with uniform con­ti­nu­ity on bounded sub­sets. I was not con­vinced that this is an im­por­tant no­tion in its own right, but the­o­rem 2 is use­ful as a lemma for the­o­rem 3. See the thread un­der David Sim­mons’s com­ment for more dis­cus­sion about what sort of con­ti­nu­ity as­sump­tion is ap­pro­pri­ate. The gist of the proof is to ap­ply the proof of the­o­rem 1 on a bounded set. The func­tion con­structed will be uniformly con­tin­u­ous ev­ery­where, so the proof ac­tu­ally shows a stronger re­sult that unifies both the­o­rems 1 and 2: there is no that is uniformly con­tin­u­ous on bounded sets and ad­mits ev­ery uniformly con­tin­u­ous func­tion as a fiber.

The­o­rem 3 al­most says that Scott’s prob­lem can­not be solved with Pol­ish spaces. It doesn’t quite say that, be­cause there are Pol­ish spaces that are not lo­cally com­pact. How­ever, non-lo­cally-com­pact Pol­ish spaces are not ex­po­nen­tiable, so in the ver­sion of the prob­lem in which we want a sur­jec­tion , it isn’t even clear whether there ex­ists an ex­po­nen­tial ob­ject , which may mean that non-ex­po­nen­tiable spaces are not promis­ing, al­though I’m not sure. A rea­son to re­strict at­ten­tion to Pol­ish spaces is that effec­tive Pol­ish spaces provide a topolog­i­cal set­ting in which there is a good no­tion of com­putabil­ity, so the nonex­is­tence of a solu­tion in Pol­ish spaces would make it im­pos­si­ble to provide a com­putable solu­tion in that sense. That said, there may be other no­tions of com­putabil­ity in topolog­i­cal spaces (do­main the­ory?), which I am un­fa­mil­iar with. The gist of the proof is to find a met­ric in which bounded sets are com­pact, and ap­ply the­o­rem 2.

#Proofs

Proof of the­o­rem 1: Let