Asymptotic Logical Uncertainty: Uniform Coherence

EDIT: This post is out of date, the new, better definition is here.

This post is part of the Asymptotic Logical Uncertainty series. Here, I give a concrete proposal for a definition of Uniform Coherence, as mentioned here.

This is only a proposal for a definition. It may be that this definition is bad, and we would rather replace it with something else

Let be a Turing machine which on input runs for some amount of time then outputs a probability, representing the probability assigned to .

In the following definition, we fix a function (e.g. ). We say that a sequence is quickly computable if it is an increasing sequence and there exists a Turing machine which determines whether or not an input is of the form in time .

We say that is Uniformly Coherent if

  1. If is quickly computable and for all , then exists.

  2. If , , and are quickly computable and for all , then

Open Question 1: Does there exist a uniformly coherent logical predictor ?

Open Question 2: Does there exist a uniformly coherent logical predictor which also passes the Generalized Benford Test? (Here, we mean the generalization of the Benford Test to all irreducible patterns)

Theroem: If is uniformly coherent, then if we define , then is defined for all and is a computably approximable coherent probability assignment. (see here for definitions.)

Proof: Computable approximability is clear. For coherence, it suffices to show that is well defined, for provable , for disprovable , and .

The fact that is well defined comes from applying 2 to the sequence .

The fact that for provable , comes from applying 3 to , , and . The fact that for disprovable , comes from applying 3 to , , and , since we already know that .

The fact that comes from applying 3 to , , and then applying 3 again to , , and to get that .

Uniform Coherence is however much stronger than coherence. To see an example, consider an infinite sequence of sentences “PA is consistent on proofs of length up to .” Uniform coherence can be shown to imply that . (Each of the sentences is provable, so you can apply 3 to this sequence and a pair of sequences.)

Theorem: If we take a quickly computable sequence of mutually exclusive sentences, , then if is uniformly coherent, we have .

Proof: Let be the disjunction of all the for . Let . By 2, converges to some . Applying 3 to , and shows that converges to . Therefore, applying 3 to , , and shows that converges to 0.(Note that I assumed here that was reasonable enough that and ane also quickly computable)