The Gaifman Condition and the Π1-Π2 problem

So I’m at a MIRI workshop on Logical Uncertainty, and I’m gonna make a more complete post about it later, but I wanted to talk about a thing that has been on my mind.

So we’re trying to build a probability distribution $\mathbb P$ over logical sentences. Let’s get a few definitions out of the way:

Definition 1 (Coherence). $\mathbb P$ is a coherent distribution if $\mathbb P(\phi) = 1$ for all proven $\phi$ and $\forall \phi,\psi. \mathbb P(\phi) = \mathbb P(\phi \land \psi) + \mathbb P(\phi \land \neg \psi)$.

Definition 2 (Computable approximability). $\mathbb P$ is said to be computably approximable if there exists some computable function $f(x,n)$ such that $\lim\limits_{n\rightarrow +\infty}f('\phi', n) = \mathbb P(\phi)$.

That is, I can compute successive approximations to the probability of $\mathbb P(\phi)$. This is an interesting definition because any coherent probability distribution is necessarily uncomputable.

Definition 3 (Arithmetical hierarchy). A predicate $\phi$ is $\Pi_0$ and $\Sigma_0$ if it contains no quantifiers or only bounded quantifiers. It is $\Pi_n$ (resp. $\Sigma_n$) if it’s of the form $\forall x_0, x_1, x_2, ... \psi(x_0, x_1, x_2, ...)$ (resp. $\exists x_0, x_1, x_2, ... \psi(x_0, x_1, x_2, ...)$) where $\psi$ is $\Sigma_{n-1}$ (resp. $\Pi_{n-1}$).

So basically you should think of the position in the arithmetical hierarchy of formulae as alternating between existential and universal quantifiers $n$ times.

Definition 4 (Gaifman Condition). $\mathbb P$ is said to be Gaifman if $\mathbb P(\phi) = 1$ for all true $\Pi_1$ sentences $\phi$.

This is an interesting condition for a logical probability distribution to obey, but unfortunately…

Theorem 1. No coherent, computably approximable, Gaifman distribution $\mathbb P$ gives nonzero probability to all true $\Pi_2$ sentences.

Or, in other words, if $\mathbb P$ has the above properties, then there exists some true $\Pi_2$ sentence $\phi$ with $\mathbb P(\phi) = 0$. To prove this, we’ll use the following lemma:

Lemma. If $\mathbb P$ is coherent and Gaifman, then all false $\Pi_2$ sentences have probability 0.

Proof. Suppose $\phi$ is a false $\Pi_2$ sentence. Then its negation is true, and it’s of the form $\exists x_1, x_2, x_3... \psi(x_1, x_2, x_3, ...)$ where $\psi$ is a $\Pi_1$ predicate. Take $c = (c_1, c_2, c_3, ...)$ to be the value that makes $\psi$ true. Then $\psi( c)$ is a true $\Pi_1$ sentence, and by the Gaifman Condition has probability 1. But if that’s so, then that’s a proof that $\phi$ is false, and coherence implies that the probability of this sentence must be 0. □

So now we’re ready to prove the theorem.

Proof of the Theorem. Assume that $\mathbb P(\phi) > 0$ for all true $\Pi_2$ sentences $\phi$. The lemma implies then that for all $\Pi_2$ sentences, $\phi \leftrightarrow \mathbb P(\phi) > 0$. However, computable approximability says that $\mathbb P(\phi) > 0 \leftrightarrow \lim\limits_{n\rightarrow +\infty} f('\phi', n) >0$, and this implies that $\exists b,n_0. \forall n > n_0. f('\phi', n) > \frac 1 {2^b}$. In other words:

$\phi \leftrightarrow \exists b,n_0. \forall n > n_0. f('\phi', n)>\frac 1 {2^b}$

Now, $\phi$ is $\Pi_2$ and the formula on the right-hand side is $\Sigma_2$, and for all $n > 0$, not all $\Pi_n$ formulae are equivalent to a $\Sigma_n$ formula, therefore we got to a contradiction.

A clearer/more convincing proof is by diagonalisation. Define:

$\phi : \leftrightarrow \forall b, n_0. \exists n > n_0. f('\phi', n) < \frac 1 {2^b}$

The right-hand side is a $\Pi_2$ sentence, and it implies that $\mathbb P(\phi) = 0$ by computable approximability. Therefore, the above is equivalent to $\phi \leftrightarrow \mathbb P(\phi) = 0$. □

So we’re kinda screwed here. But then I thought of a weaker form of computable approximability:

Definition 5 (Computable $\varepsilon$-Approximability). $\mathbb P$ is said to be computably $\varepsilon$-approximable if there exists some computable function $f(x,n)$ such that $|\lim\limits_{n\rightarrow +\infty}f('\phi', n) - \mathbb P(\phi)| < \varepsilon$.

This definition seems to me to escape the two proofs of the $\Pi_1-\Pi_2$ problem.

Thoughts?

ETA:

raginrayguns talked about a sentence similar to the following and Benja Fallenstein proved the theorem:

Theorem 2. Let $\mathbb P$ be coherent, computably $\varepsilon$-approximable, and Gaifman. Then there exist true $\Pi_2$ sentences that have probability less than $2\varepsilon$.

Proof. We’ll build one such sentence:

$\phi : \leftrightarrow \forall n_0.\exists n > n_0. f('\phi', n) < \varepsilon$

If $\phi$ is false, then $\mathbb P(\phi) \geq \varepsilon$, which by the lemma implies $\phi$ is true.

If $\phi$ is true, then $\forall n_0. \exists n > n_0. f('\phi', n) < \varepsilon$, which implies that $\mathbb P(\phi) < 2\varepsilon$. □

So we didn’t escape the problem after all, just put it in the bound.

This entry was posted in Logic, Mathematics, Probability Theory and tagged , , , , , , , . Bookmark the permalink.

9 Responses to The Gaifman Condition and the Π1-Π2 problem

1. Will says:

Why is MIRI reinventing Gaifman/Gaifman and Snir? Did you guys just dive in without reading that work? All of this was done between the 60s and the 80s..

• pedromvilar says:

Reinventing? MIRI only presented the Π1-Π2 problem, and explicitly mentioned Gaifman’s work… I’m not sure what you’re talking about? They also talked about Hutter’s work.

• Will says:

Check out Gaifman and Snir and that whole thread of research up to Joseph Halpern. You guys should really review the old research before trying to work on these sort of problems.

• pedromvilar says:

As far as I know, MIRI has reviewed this old research. I’m not sure what you’re taking from this post, but I’m not a MIRI employee and the post itself reflected a thought I had at 5:20AM after being introduced to the Π1-Π2 problem the previous day. Maybe I should add the “This is not MIRI’s official position and I’m just some random person who went to a workshop.” disclaimer at the top of the post?

• Will says:

Having looked through their papers, it’s not clear they have read this research. Their “Definability of Truth” paper presents a construction that doesn’t obey Gaifman’s conditions (without mentioning it). But that said, I’m confused why they are doing workshops that don’t start by getting everyone up to speed on the relevant literature.

• pedromvilar says:

It gets them up-to-speed to some relevant literature, though not all… because there’s a whole lot of it and it’s just three days of workshop. It already took one whole day just to present the basic outline and to understand what the Benford test rigorously was and how an Asymptotic Logical Uncertainty algorithm followed this property and stuff… Basically, there wouldn’t be time to present literally everything that’s been done, and a lot of it is expected to come from the actual participants themselves, who would research stuff more deeply by themselves.

As for not obeying Gaifman’s conditions, are there any other conditions than the canonical Gaifman Condition it doesn’t obey? (And tbh imo the Gaifman Condition isn’t reasonable for philosophical reasons, so…) I myself haven’t looked into a lot of Gaifman’s work, the focus of the workshop was mostly on relaxing notions of coherence and seeing if we can draw something computable out of that.

And the “Definability of Truth” is a draft, not a proper paper, as you can see by the sheer number of typos and the structure 😛 Pretty sure it’s not finished, so I dunno if they plan on mentioning anything.

• Will says:

If you’ve had a “draft” on your website for 2 years without doing anything with it, then you might as well call it a “paper.” Otherwise you’ve produced nothing.

Gaifman did extensive work on assigning probability to logical propositions, probably the most complete summary is Gaifman and Snir (1982). But that thread of research has continued to this day. Halpern has done work on this as well, more recently.

Generally workshops are supposed to collect experts to work on specific problems, or barring that they are like REU workshops where it’s expected you’ll spend extensive time learning the prerequisites before diving in on problems. I guess I don’t understand what MIRI is trying to do. The first step to making any progress on anything is a very thorough literature search.

2. Will says:

Hutter has made more progress since then by actually building on the earlier work.