Scott Garrabrant's problem on recovering Brouwer as a corollary of Lawvere

post by Rupert · 2020-05-04T10:01:56.305Z · LW · GW · 2 comments

Edit: Pre-print available here https://arxiv.org/abs/2005.01563

Also link to earlier post here https://www.alignmentforum.org/posts/5bd75cc58225bf06703753a9/formal-open-problem-in-decision-theory?fbclid=IwAR2u-8RVfnfRtEo51vag5vYWAcfkoHDJAr6aydVGqYVmEq0oxnjwR0Ee34E [AF · GW]

Scott Garrabrant has raised the question of whether there is any topological space $A$ for which the exponential topology on $[0,1{]}^A$ exists and such that there is a continuous surjection $g:A\to [0,1{]}^A$. In cited pre-print above I claim to resolve this question negatively in ZFC (using techniques of inner model theory, Skolem hull arguments, and some Reverse Mathematics results presented by Stephen Simpson in "Subsystems of Second Order Arithmetic") but also to give an example of a pair of spaces $A^{\prime },A^{\prime \prime }$ with the same carrier set, topology on $A^{\prime }$ finer than that on $A^{\prime \prime }$, and a continuous surjection $g:A^{\prime }\to [0,1{]}^{A^{\prime \prime }}$ with the following properties. Take an open subset of $[0,1]$, take pre-image in $[0,1{]}^{A^{\prime \prime }}\times A^{\prime \prime }$ under evaluation map, take projection onto first factor and then pre-image under surjection $g$, and view this both as a subset of $A^{\prime }$ and $A^{\prime \prime }$ (which have the same carrier set), this is required to be always open relative to both topologies. If this can be achieved then Brouwer fixed point theorem is recoverable as a corollary with "same method of proof" as Lawvere. Results along these lines appear to be essentially "the best one can do".

My first example of such a pair of spaces are spaces of cardinality $2^{{\aleph }_1}$ which may lead one to think that practical applications are doubtful. But there are techniques to produce a broad class of related examples by refining things both along the hierarchy of descriptive complexity and indeed even computational complexity. The details of this are outlined in the final section of the paper.

One example of a result that can be obtained is as follows. Let $\alpha$ be the least countable ordinal such that there is no polynomial-time computable recursive well-ordering of length $\alpha$. (I think it's probably ${\omega }^2$ or something, not sure, but this could be figured out. EDIT: Alex Mennen has clarified I was mistaken about this and the ordinal is in fact ${\omega }_1^{CK}$, which perhaps makes this particular result of less interest.) Let $A$ be a space of agents indexed by recursive well-ordered bit-strings of length $\alpha$ with some fixed upper bound on the computation complexity if you wish (but we'll see we can't organise it so that they're all polynomial-time computable).

Then you do indeed have a continuous surjection from $A$ onto the space of all polynomial-time-computable policies, but you can't organise things so that every element of $A$ is polynomial-time computable, or so that the surjection itself is polynomial-time computable. (Edit: By placing an upper bound on complexity of bit-strings that can occur in $A$ that means $A$ ends up being countable, that's probably a bit confusing, but it's possible to expand $A$ so that arbitrary bit-strings can occur in its carrier set and the same result stated at the start of this paragraph still holds.) Similar results can be obtained throughout the entire computational complexity hierarchy or descriptive complexity hierarchy. This may be of some interest from the point of view of the type of application that Scott Garrabrant originally had in mind when posing the problem in the first place.

2 comments

Comments sorted by top scores.