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 over logical sentences. Let’s get a few definitions out of the way:

**Definition 1 (Coherence).** * is a coherent distribution if for all proven and .*

**Definition 2 (Computable approximability).** * is said to be computably approximable if there exists some computable function such that .*

That is, I can compute successive approximations to the probability of . This is an interesting definition because any coherent probability distribution is necessarily uncomputable.

**Definition 3 (Arithmetical hierarchy).** *A predicate is and if it contains no quantifiers or only bounded quantifiers. It is (resp. ) if it’s of the form (resp. ) where is (resp. ).*

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

**Definition 4 (Gaifman Condition).** * is said to be Gaifman if for all true sentences .*

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

**Theorem 1.** *No coherent, computably approximable, Gaifman distribution gives nonzero probability to all true sentences.*

Or, in other words, if has the above properties, then there exists some true sentence with . To prove this, we’ll use the following lemma:

**Lemma.** *If is coherent and Gaifman, then all false sentences have probability 0.*

*Proof.* Suppose is a false sentence. Then its negation is true, and it’s of the form where is a predicate. Take to be the value that makes true. Then is a true sentence, and by the Gaifman Condition has probability 1. But if that’s so, then that’s a proof that 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 for all true sentences . The lemma implies then that for all sentences, . However, computable approximability says that , and this implies that . In other words:

Now, is and the formula on the right-hand side is , and for all , not all formulae are equivalent to a formula, therefore we got to a contradiction.

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

The right-hand side is a sentence, and it implies that by computable approximability. Therefore, the above is equivalent to . □

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

**Definition 5 (Computable -Approximability).** * is said to be computably -approximable if there exists some computable function such that .*

This definition seems to me to escape the two proofs of the problem.

Thoughts?

ETA:

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

**Theorem 2.** *Let be coherent, computably -approximable, and Gaifman. Then there exist true sentences that have probability less than .*

*Proof.* We’ll build one such sentence:

If is false, then , which by the lemma implies is true.

If is true, then , which implies that . □

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

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..

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.

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.

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?

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.

It gets them up-to-speed to

somerelevant 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.

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.

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

Pingback: What’s logical coherence for anyway? | An Aspiring Rationalist's Ramble