(This post was originally published on March 31st 2017, and has been brought forwarded as part of the AI Alignment Forum launch sequence on fixed points.)
In this post, I present a new formal open problem. A positive answer would be valuable for decision theory research. A negative answer would be helpful, mostly for figuring out what is the closest we can get to a positive answer. I also give some motivation for the problem, and some partial progress.
Open Problem: Does there exist a topological space X (in some convenient category of topological spaces) such that there exists a continuous surjection from X to the space [0,1]X (of continuous functions from X to [0,1])?
Motivation:
Topological Naturalized Agents: Consider an agent who makes some observations and then takes an action. For simplicity, we assume there are only two possible actions, A and B. We also assume that the agent can randomize, so we can think of this agent as outputting a real number in [0,1], representing its probability of taking action A.
Thus, we can think of an agent as having a policy which is a function from the space Y of possible observations to [0,1]. We will require that our agent behaves continuously as a function of its observations, so we will think of the space of all possible policies as the space of continuous functions from Y to [0,1], denoted [0,1]Y.
We will let X denote the space of all possible agents, and we will have a function f:X→[0,1]Y which takes in an agent, and outputs that agent’s policy.
Now, consider what happens when there are other agents in the environment. For simplicity, we will assume that our agent observes one other agent, and makes no other observations. Thus, we want to consider the case where Y=X, so f:X→[0,1]X.
We want f to be continuous, because we want a small change in an agent to correspond to a small change in the agent’s policy. This is particularly important since other agents will be implementing continuous functions on agents, and we would like any continuous function on policies to be able to be considered valid continuous function on agents.
We also want f to be surjective. This means that our space of agents is sufficiently rich that for any possible continuous policy, there is an agent in our space that implements that policy.
In order to meet all these criteria simultaneously, we need a space X of agents, and a continuous surjection f:X→[0,1]X.
Unifying Fixed Point Theorems: While we are primarily interested in the above motivation, there is another secondary motivation, which may be more compelling for those less interested in agent foundations.
There are (at least) two main clusters of fixed point theorems that have come up many times in decision theory, and mathematics in general.
First, there is the Lawvere cluster of theorems. This includes the Lawvere fixed point theorem, the diagonal lemma, and the existence of Quines and fixed point combinators. These are used to prove Gödel’s incompleteness Theorem, Cantor’s Theorem, Löb’s Theorem, and achieve robust cooperation in the Prisoner’s Dilemma in modal framework and bounded variants. All of these can be seen as corollaries of Lawvere’s fixed point theorem, which states that in a cartesian closed category, if there is a point-surjective map f:X→YX, then every morphism g:Y→Y has a fixed point.
Second, there is the Brouwer cluster of theorems. This includes Brouwer’s fixed point theorem, The Kakutani fixed point theorem, Poincaré–Miranda, and the intermediate value theorem. These are used to prove the existence of Nash Equilibria, Logical Inductors, and Reflective Oracles.
If we had a topological space and a continuous surjection X→[0,1]X, this would allow us to prove the one-dimensional Brouwer fixed point theorem directly using the Lawvere fixed point theorem, and thus unify these two important clusters.
Most Diagonalization Intuitions Do Not Apply: A common initial reaction to this question is to conjecture that such an X does not exist, due to cardinality or diagonalization intuitions. However, note that all of the diagonalization theorems pass through (some modification of) the same lemma: Lawvere’s fixed point theorem. However, this lemma does not apply here!
For example, in the category of sets, the reason that there is no surjection from any set X to the power set, {T,F}X, is because if there were such a surjection, Lawvere’s fixed point theorem would imply that every function from {T,F} to itself has a fixed point (which is clearly not the case, since there is a function that swaps T and F).
However, we already know by Brouwer’s fixed point theorem that every continuous function from the interval [0,1] to itself has a fixed point, so the standard diagonalization intuitions do not work here.
Impossible if You Replace [0,1] with e.g. S1: This also provides a quick sanity check on attempts to construct an X. Any construction that would not be meaningfully different if the interval [0,1] is replaced with the circle S1 is doomed from the start. This is because a continuous surjection X→(S1)X would violate Lawvere’s fixed point theorem, since there is a continuous map from S1 to itself without fixed points.
Impossible if you Require a Homeomorphism: When I first asked this question I asked for a homeomorphism between X and [0,1]X. Sam Eisenstat has given a very clever argument why this is impossible. You can read it here. In short, using a homeomorphism, you would be able to use Lawvere to construct a continuous map that send a function from [0,1] to itself to a fixed point of that function. However, no such continuous map exists.
Notes:
If you prefer not to think about the topology of [0,1]X, you can instead find a space X, and a continuous map h:X×X→[0,1], such that for every continuous function f:X→[0,1], there exists an xf∈X, such that for all x∈X, h(xf,x)=f(x).
Many of the details in the motivation could be different. I would like to see progress on similar questions. For example, you could add some computability condition to the space of functions. However, I am also very curious which way this specific question will go.
This post came out of many conversations, with many people, including: Sam, Qiaochu, Tsvi, Jessica, Patrick, Nate, Ryan, Marcello, Alex Mennen, Jack Gallagher, and James Cook.
This post was originally published on March 31st 2017, and has been brought forwarded as part of the AI Alignment Forum launch sequences.
Tomorrow’s AIAF sequences post will be ‘Iterated Amplification and Distillation’ by Ajeya Cotra, in the sequence on iterated amplification.
Formal Open Problem in Decision Theory
(This post was originally published on March 31st 2017, and has been brought forwarded as part of the AI Alignment Forum launch sequence on fixed points.)
In this post, I present a new formal open problem. A positive answer would be valuable for decision theory research. A negative answer would be helpful, mostly for figuring out what is the closest we can get to a positive answer. I also give some motivation for the problem, and some partial progress.
Open Problem: Does there exist a topological space X (in some convenient category of topological spaces) such that there exists a continuous surjection from X to the space [0,1]X (of continuous functions from X to [0,1])?
Motivation:
Topological Naturalized Agents: Consider an agent who makes some observations and then takes an action. For simplicity, we assume there are only two possible actions, A and B. We also assume that the agent can randomize, so we can think of this agent as outputting a real number in [0,1], representing its probability of taking action A.
Thus, we can think of an agent as having a policy which is a function from the space Y of possible observations to [0,1]. We will require that our agent behaves continuously as a function of its observations, so we will think of the space of all possible policies as the space of continuous functions from Y to [0,1], denoted [0,1]Y.
We will let X denote the space of all possible agents, and we will have a function f:X→[0,1]Y which takes in an agent, and outputs that agent’s policy.
Now, consider what happens when there are other agents in the environment. For simplicity, we will assume that our agent observes one other agent, and makes no other observations. Thus, we want to consider the case where Y=X, so f:X→[0,1]X.
We want f to be continuous, because we want a small change in an agent to correspond to a small change in the agent’s policy. This is particularly important since other agents will be implementing continuous functions on agents, and we would like any continuous function on policies to be able to be considered valid continuous function on agents.
We also want f to be surjective. This means that our space of agents is sufficiently rich that for any possible continuous policy, there is an agent in our space that implements that policy.
In order to meet all these criteria simultaneously, we need a space X of agents, and a continuous surjection f:X→[0,1]X.
Unifying Fixed Point Theorems: While we are primarily interested in the above motivation, there is another secondary motivation, which may be more compelling for those less interested in agent foundations.
There are (at least) two main clusters of fixed point theorems that have come up many times in decision theory, and mathematics in general.
First, there is the Lawvere cluster of theorems. This includes the Lawvere fixed point theorem, the diagonal lemma, and the existence of Quines and fixed point combinators. These are used to prove Gödel’s incompleteness Theorem, Cantor’s Theorem, Löb’s Theorem, and achieve robust cooperation in the Prisoner’s Dilemma in modal framework and bounded variants. All of these can be seen as corollaries of Lawvere’s fixed point theorem, which states that in a cartesian closed category, if there is a point-surjective map f:X→YX, then every morphism g:Y→Y has a fixed point.
Second, there is the Brouwer cluster of theorems. This includes Brouwer’s fixed point theorem, The Kakutani fixed point theorem, Poincaré–Miranda, and the intermediate value theorem. These are used to prove the existence of Nash Equilibria, Logical Inductors, and Reflective Oracles.
If we had a topological space and a continuous surjection X→[0,1]X, this would allow us to prove the one-dimensional Brouwer fixed point theorem directly using the Lawvere fixed point theorem, and thus unify these two important clusters.
Thanks to Qiaochu Yuan for pointing out the connection to Lawvere’s fixed point theorem (and actually asking this question three years ago).
Partial Progress:
Most Diagonalization Intuitions Do Not Apply: A common initial reaction to this question is to conjecture that such an X does not exist, due to cardinality or diagonalization intuitions. However, note that all of the diagonalization theorems pass through (some modification of) the same lemma: Lawvere’s fixed point theorem. However, this lemma does not apply here!
For example, in the category of sets, the reason that there is no surjection from any set X to the power set, {T,F}X, is because if there were such a surjection, Lawvere’s fixed point theorem would imply that every function from {T,F} to itself has a fixed point (which is clearly not the case, since there is a function that swaps T and F).
However, we already know by Brouwer’s fixed point theorem that every continuous function from the interval [0,1] to itself has a fixed point, so the standard diagonalization intuitions do not work here.
Impossible if You Replace [0,1] with e.g. S1: This also provides a quick sanity check on attempts to construct an X. Any construction that would not be meaningfully different if the interval [0,1] is replaced with the circle S1 is doomed from the start. This is because a continuous surjection X→(S1)X would violate Lawvere’s fixed point theorem, since there is a continuous map from S1 to itself without fixed points.
Impossible if you Require a Homeomorphism: When I first asked this question I asked for a homeomorphism between X and [0,1]X. Sam Eisenstat has given a very clever argument why this is impossible. You can read it here. In short, using a homeomorphism, you would be able to use Lawvere to construct a continuous map that send a function from [0,1] to itself to a fixed point of that function. However, no such continuous map exists.
Notes:
If you prefer not to think about the topology of [0,1]X, you can instead find a space X, and a continuous map h:X×X→[0,1], such that for every continuous function f:X→[0,1], there exists an xf∈X, such that for all x∈X, h(xf,x)=f(x).
Many of the details in the motivation could be different. I would like to see progress on similar questions. For example, you could add some computability condition to the space of functions. However, I am also very curious which way this specific question will go.
This post came out of many conversations, with many people, including: Sam, Qiaochu, Tsvi, Jessica, Patrick, Nate, Ryan, Marcello, Alex Mennen, Jack Gallagher, and James Cook.
This post was originally published on March 31st 2017, and has been brought forwarded as part of the AI Alignment Forum launch sequences.
Tomorrow’s AIAF sequences post will be ‘Iterated Amplification and Distillation’ by Ajeya Cotra, in the sequence on iterated amplification.