The n-Category Café

A warmup

Before describing logical induction, let me describe a different and more naive criterion you could ask for, but in fact don’t want to ask for because it’s too strong. Let $\varphi \mapsto \mathbb{P}(\varphi)$ be an assignment of probabilities to statements in some first-order language; for example, we might want to assign probabilities to statements in the language of Peano arithmetic (PA), conditioned on the axioms of PA being true (which means having probability $1$). Say that such an assignment $\varphi \mapsto \mathbb{P}(\varphi)$ is coherent if

• $\mathbb{P}(\top) = 1$.
• If $\varphi_1$ is equivalent to $\varphi_2$, then $\mathbb{P}(\varphi_1) = \mathbb{P}(\varphi_2)$.
• $\mathbb{P}(\varphi_1) = \mathbb{P}(\varphi_1 \wedge \varphi_2) + \mathbb{P}(\varphi_1 \wedge \neg \varphi_2)$.

These axioms together imply various other natural-looking conditions; for example, setting $\varphi_1 = \top$ in the third axiom, we get that $\mathbb{P}(\varphi_2) + \mathbb{P}(\neg \varphi_2) = 1$. Various other axiomatizations of coherence are possible.

Theorem: A probability assignment such that $\mathbb{P}(\varphi) = 1$ for all statements $\varphi$ in a first-order theory $T$ is coherent iff there is a probability measure on models of $T$ such that $\mathbb{P}(\varphi)$ is the probability that $\varphi$ is true in a random model.

This theorem is a logical counterpart of the Riesz-Markov-Kakutani representation theorem relating probability distributions to linear functionals on spaces of functions; I believe it is due to Gaifman.

For example, if $T$ is PA, then the sort of uncertainty that a coherent probability assignment conditioned on PA captures is uncertainty about which of the various first-order models of PA is the “true” natural numbers. However, coherent probability assignments are still logically omniscient: syntactically, every provable statement is assigned probability $1$ because they’re all equivalent to $\top$, and semantically, provable statements are true in every model. In particular, coherence is too strong to capture uncertainty about the digits of $\pi$.

Coherent probability assignments can update over time whenever they learn that some statement is true which they haven’t assigned probability $1$ to; for example, if you start by believing PA and then come to also believe that PA is consistent, then conditioning on that belief will cause your probability distribution over models to exclude models of PA where PA is inconsistent. But this doesn’t capture the kind of updating a non-logically omniscient reasoner like you or me actually does, where our beliefs about mathematics can change solely because we’ve thought a bit longer and proven some statements that we didn’t previously know (for example, about the values of more and more digits of $\pi$).

Logical induction

The framework of logical induction is for describing the above kind of updating, based solely on proving more statements. It takes as input a deductive process which is slowly producing proofs of statements over time (for example, of theorems in PA), and assigns probabilities to statements that haven’t been proven yet. Remarkably, it’s able to do this in a way that eventually outpaces the deductive process, assigning high probabilities to true statements long before they are proven (see Theorem 4.2.1).

So how does logical induction work? The coherence axioms above can be justified by Dutch book arguments, following Ramsey and de Finetti, which loosely say that a bookie can’t offer a coherent reasoner a bet about mathematical statements which they will take but which is in fact guaranteed to lose them money. But this is much too strong a requirement for a reasoner who is not logically omniscient. The logical induction criterion is a weaker version of this condition; we only require that an efficiently computable bookie can’t make arbitrarily large amounts of money by betting with a logical inductor about mathematical statements unless it’s willing to take on arbitrarily large amounts of risk (see Definition 3.0.1).

This turns out to be a surprisingly useful condition to require, loosely speaking because it corresponds to being able to “notice patterns” in mathematical statements even if we can’t prove anything about them yet. A logical inductor has to be able to notice patterns that could otherwise be used by an efficiently computable bookie to exploit the inductor; for example, a logical inductor eventually assigns probability about $\frac{1}{10}$ to claims that a very large digit of $\pi$ has a particular value, intuitively because otherwise a bookie could continue to bet with the logical inductor about more and more digits of $\pi$, making money each time (see Theorem 4.4.2).

Logical induction has many other desirable properties, some of which are described in this blog post. One of the more remarkable properties is that because logical inductors are computable, they can reason about themselves, and hence assign probabilities to statements about the probabilities they assign. Despite the possibility of running into self-referential paradoxes, logical inductors eventually have accurate beliefs about their own beliefs (see Theorem 4.11.1).

Overall I’m excited about this circle of ideas and hope that they get more attention from the mathematical community. Speaking very speculatively, it would be great if logical induction shed some light on the role of probability in mathematics more generally - for example, in the use of informal probabilistic arguments for or against difficult conjectures. A recent example is Boklan and Conway’s probabilistic arguments in favor of the conjecture that there are no Fermat primes beyond those currently known.

I’ve made several imprecise claims about the contents of the paper above, so please read it to get the precise claims!