Is it important to the analysis whether the probabilities converge as D tends to infinity? Do you rely on this at any point?
If you need to make sure the probabilities converge, then you could consider something like the following.
First, split the sentences in your system F into “positive” sentences (the ones which have no leading “not” symbol, ~, or else which have an even number of leading “not” symbols) and “negative” sentences (the ones with an odd number of leading “not” symbols). Sort the positive sentences by length, and then sort them lexicographically within all sentences of the same length. This will give a list s1, s2 etc.
We will now build a growing subset S of sentences, and ensure that in the limit, S is consistent and complete.
At stage 0, S is empty. Call this S0.
At stage n: Toss a fair coin, and if it lands heads then add sn to S. If it lands tails then add ~sn to S.
Next, systematically search through all proofs of length up to the length of sn to see if there are any inconsistencies in S. If a proof of inconsistency is found, then list the subset of positive and negative sentences which create the inconsistency e.g. {sa, ~sb, ~sc, …, sz}; let k be the largest index in this list (the largest value of a, b, …, z). If sk was in S, then remove it and add ~sk instead, or if ~sk was in S then replace it by sk. Restart the search for inconsistencies. When the search completes without finding any further inconsistencies we have the set Sn.
We now take the obvious limit Sw of the sets Sn as n tends to infinity: s will belong to Sw if and only if it belongs to all but a finite number of Sn. That limit Sw is guaranteed to exist, because for each m, the process will eventually find a consistent choice of sentences and negations from within {s1, … ,sm} and then stick with it (any contradictions found later will cause the replacement of sentences sk or ~sk with k > m). Further, Sw is guaranteed to be consistent (because any contradictions would have been discovered and removed in some Sn). Finally Sw is guaranteed to be complete, since it contains either sm or ~sm for each m.
We can now define probabilities PD(s) = P(s is a member of SD) and take P(s) as the limit of PD(s) as D tends to infinity. The limit is always defined since it is just the probability that s is a member of Sw.
Is it important to the analysis whether the probabilities converge as D tends to infinity? Do you rely on this at any point?
If you need to make sure the probabilities converge, then you could consider something like the following.
First, split the sentences in your system F into “positive” sentences (the ones which have no leading “not” symbol, ~, or else which have an even number of leading “not” symbols) and “negative” sentences (the ones with an odd number of leading “not” symbols). Sort the positive sentences by length, and then sort them lexicographically within all sentences of the same length. This will give a list s1, s2 etc.
We will now build a growing subset S of sentences, and ensure that in the limit, S is consistent and complete.
At stage 0, S is empty. Call this S0.
At stage n: Toss a fair coin, and if it lands heads then add sn to S. If it lands tails then add ~sn to S. Next, systematically search through all proofs of length up to the length of sn to see if there are any inconsistencies in S. If a proof of inconsistency is found, then list the subset of positive and negative sentences which create the inconsistency e.g. {sa, ~sb, ~sc, …, sz}; let k be the largest index in this list (the largest value of a, b, …, z). If sk was in S, then remove it and add ~sk instead, or if ~sk was in S then replace it by sk. Restart the search for inconsistencies. When the search completes without finding any further inconsistencies we have the set Sn.
We now take the obvious limit Sw of the sets Sn as n tends to infinity: s will belong to Sw if and only if it belongs to all but a finite number of Sn. That limit Sw is guaranteed to exist, because for each m, the process will eventually find a consistent choice of sentences and negations from within {s1, … ,sm} and then stick with it (any contradictions found later will cause the replacement of sentences sk or ~sk with k > m). Further, Sw is guaranteed to be consistent (because any contradictions would have been discovered and removed in some Sn). Finally Sw is guaranteed to be complete, since it contains either sm or ~sm for each m.
We can now define probabilities PD(s) = P(s is a member of SD) and take P(s) as the limit of PD(s) as D tends to infinity. The limit is always defined since it is just the probability that s is a member of Sw.
Convergence is not an issue as long as the utility function is computable.
Soon I’m going to write more about logical uncertainty in the context of the Loebian obstacle.