Thoughts off the top of my head. It’s very unclear to me what “huge swath” means or ought to mean. I’m going to describe some problems I think it would be good if you knew how to solve but not going to make strong claims about whether they’re necessary or sufficient to do MIRI research, which I think is the more relevant question than whether they certify a complete understanding of the topic. Some of them are exercises more than tests. I have more opinions about more standard stuff and fewer opinions about MIRI-specific stuff, much of which I’ll skip.
Also I don’t want to spend a ton of time on this so this is by no means exhaustive.
Also it’s confusing to mix in topics like “set theory” with topics like “logical uncertainty” because lots of people understand set theory but there’s an important sense in which nobody understands logical uncertainty.
Set theory
1. Prove Cantor’s theorem.
2. Explain the way in which the structure of the proof of Cantor’s theorem is identical to, roughly in increasing order of difficulty: Russell’s paradox, the proof of the undecidability of the halting problem, the large-scale structure of the proof of the incompleteness theorem. (See this blog post for a sequence of increasingly large hints.)
Probability, probabilistic inference, and statistics
1. Suppose you repeatedly flip a coin with unknown bias, that your prior over the bias is uniform, and that you update your beliefs about the bias via Bayes’ theorem. Prove that as the number of flips goes to infinity your beliefs about the bias converge to the true bias. Along the way, reinvent the concept of KL divergence for Bernoulli distributions.
2. Generalize the preceding result to an n-sided die. Along the way, reinvent the concept of KL divergence for distributions over finite sets. (Again, see this blog post for a sequence of increasingly large hints.)
1. Prove that there are countable models of ZFC set theory and uncountable models of (first-order) Peano arithmetic, assuming their consistency.
2. Prove that there exist “self-hating” models of ZFC in which the statement “ZFC is consistent” is false (and also explain what it even means that this is the case), again assuming that ZFC is in fact consistent.
Linear algebra
1. Compute the derivative of the function sending an invertible square matrix to its inverse. Also explain what sort of mathematical object this derivative is.
Topology
1. Suppose X is a connected topological space, Y is a topological space, and f:X→Y is a function. Prove that if f is continuous, then the graph {(x,f(x))∈X×Y} of f is connected. Is the converse true? (I picked this one sort of randomly so don’t take it too seriously, it’s tricky to do this for topology.)
2. (Also first-order logic) Explain what the compactness theorem has to do with topological compactness.
2. (Also type theory, kinda) Explain the way in which the proof of Lawvere’s fixed point theorem is identical to the construction of the Y combinator.
3. (Also linear algebra) Explain why a finite-dimensional vector space V is not naturally isomorphic to its dual V∗, but is naturally isomorphic to its double dual V∗∗.
Thoughts off the top of my head. It’s very unclear to me what “huge swath” means or ought to mean. I’m going to describe some problems I think it would be good if you knew how to solve but not going to make strong claims about whether they’re necessary or sufficient to do MIRI research, which I think is the more relevant question than whether they certify a complete understanding of the topic. Some of them are exercises more than tests. I have more opinions about more standard stuff and fewer opinions about MIRI-specific stuff, much of which I’ll skip.
Also I don’t want to spend a ton of time on this so this is by no means exhaustive.
Also it’s confusing to mix in topics like “set theory” with topics like “logical uncertainty” because lots of people understand set theory but there’s an important sense in which nobody understands logical uncertainty.
Set theory
1. Prove Cantor’s theorem.
2. Explain the way in which the structure of the proof of Cantor’s theorem is identical to, roughly in increasing order of difficulty: Russell’s paradox, the proof of the undecidability of the halting problem, the large-scale structure of the proof of the incompleteness theorem. (See this blog post for a sequence of increasingly large hints.)
Probability, probabilistic inference, and statistics
1. Suppose you repeatedly flip a coin with unknown bias, that your prior over the bias is uniform, and that you update your beliefs about the bias via Bayes’ theorem. Prove that as the number of flips goes to infinity your beliefs about the bias converge to the true bias. Along the way, reinvent the concept of KL divergence for Bernoulli distributions.
2. Generalize the preceding result to an n-sided die. Along the way, reinvent the concept of KL divergence for distributions over finite sets. (Again, see this blog post for a sequence of increasingly large hints.)
Machine learning
1. Prove the universal approximation theorem.
2. Explain why the universal approximation theorem is not a sufficient explanation for the power of neural networks in practice.
Solomonoff induction
1. Prove that Kolmogorov complexity is uncomputable.
2. Does this imply that Solomonoff induction is uncomputable?
VNM decision theory
1. Reconcile the VNM theorem and the St. Petersburg paradox.
First-order logic
1. Prove that there are countable models of ZFC set theory and uncountable models of (first-order) Peano arithmetic, assuming their consistency.
2. Prove that there exist “self-hating” models of ZFC in which the statement “ZFC is consistent” is false (and also explain what it even means that this is the case), again assuming that ZFC is in fact consistent.
Linear algebra
1. Compute the derivative of the function sending an invertible square matrix to its inverse. Also explain what sort of mathematical object this derivative is.
Topology
1. Suppose X is a connected topological space, Y is a topological space, and f:X→Y is a function. Prove that if f is continuous, then the graph {(x,f(x))∈X×Y} of f is connected. Is the converse true? (I picked this one sort of randomly so don’t take it too seriously, it’s tricky to do this for topology.)
2. (Also first-order logic) Explain what the compactness theorem has to do with topological compactness.
Category theory
1. (Also set theory) Prove Lawvere’s fixed point theorem, and use it to prove Cantor’s theorem.
2. (Also type theory, kinda) Explain the way in which the proof of Lawvere’s fixed point theorem is identical to the construction of the Y combinator.
3. (Also linear algebra) Explain why a finite-dimensional vector space V is not naturally isomorphic to its dual V∗, but is naturally isomorphic to its double dual V∗∗.
(Edit: nuts, what happened to LaTeX support?)
We moved the LaTeX editor to CTRL+4, because some people apparently wanted to use dollar signs to talk about money (damn capitalists).
I turned Qiaochu’s comment into LaTex. And fyi on my Mac, it’s now cmd-4, and block-level equations are cmd-M.