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