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