P_D(s) := P_0(s | there are no contradictions of length ⇐ D).
You have not actually defined what P_0(a | b) means. The usual definition would be P_0(a | b) = P_0(a & b) / P_0(b). But then, by definition of P_0, P_0(a & b) = 0.5 and P_0(b) = 0.5, so P_0(a | b) = 1. Also, the statement “there are no contradictions of length ⇐ D” is not even a statement in F.
“there are no contradictions of length ⇐ D” is not a statement in F, it is a statement about truth assignments. I’m evaluating the probability that s is assigned “true” by the random truth assignment under the condition that this truth assignment is free of short contradictions.
Right, but P_0(s) is defined for statements s in F. Then suddenly you talk about P_0(s | there is no contradiction of length <= D), but the thing between parentheses is not a statement in F. So, what is the real definition of P_D? And how would I compute it?
I’m probably explaining it poorly in the post. P0 is not just a function of statements in F. P0 is a probability measure on the space of truth assignments i.e. functions {statement in F} → {truth, false}. This probability measure is defined by making the truth value of each statement an independent random variable with 50⁄50 distribution.
PD is produced from P0 by imposing the condition “there is no contradiction of length ⇐ D” on the truth assignment, i.e. we set the probability of all truth assignments that violate the condition to 0 and renormalize the probabilities of all other assignments. In other words P_D(s) = # {D-consistent truth assignments in which s is assigned true} / # {D-consistent truth assignments}.
Technicality: There is an infinite number of statements so there is an infinite number of truth assignments. However there is only a finite number of statements that can figure in contradictions of length ⇐ D. Therefore all the other statements can be ignored (i.e. assumed to have independent probabilities of 1⁄2 like in P_0). More formally, the sigma-algebra of measurable sets on the space of truth assignments is generated by sets of the form {truth assignment T | T(s) = true} and {truth assignment T | T(s) = false}. The set of D-consistent truth assignments is in this sigma algebra and has positive probability w.r.t. our measure (as long as F is D-consistent) so we can use this set to form a conditional probability measure.
It may not be clear what you meant by “length” of contradiction. Is it the number of deductive steps to reach a contradiction, or the total number of symbols in a proof of contradiction?
Consider for instance two sentences X and ~X where X contains a billion symbols … Is that a contradiction of length 1, or a contradiction of length about 2 billion? I think you mean about 2 billion. In which case, you will always have PD(s) = 0.5 for sentences s of length greater than D. Right?
At first I thought he meant P_D(s) is defined to be 0 if there is a proof in F of s implies false of length ⇐ D, and 1⁄2 otherwise, but then he says P_D(s) == 1 later for some s, so that’s not right.
You have not actually defined what
P_0(a | b)means. The usual definition would beP_0(a | b) = P_0(a & b) / P_0(b). But then, by definition of P_0,P_0(a & b) = 0.5andP_0(b) = 0.5, soP_0(a | b) = 1. Also, the statement “there are no contradictions of length ⇐ D” is not even a statement in F.“there are no contradictions of length ⇐ D” is not a statement in F, it is a statement about truth assignments. I’m evaluating the probability that s is assigned “true” by the random truth assignment under the condition that this truth assignment is free of short contradictions.
Right, but
P_0(s)is defined for statementssinF. Then suddenly you talk aboutP_0(s | there is no contradiction of length <= D), but the thing between parentheses is not a statement inF. So, what is the real definition ofP_D? And how would I compute it?I’m probably explaining it poorly in the post. P0 is not just a function of statements in F. P0 is a probability measure on the space of truth assignments i.e. functions {statement in F} → {truth, false}. This probability measure is defined by making the truth value of each statement an independent random variable with 50⁄50 distribution.
PD is produced from P0 by imposing the condition “there is no contradiction of length ⇐ D” on the truth assignment, i.e. we set the probability of all truth assignments that violate the condition to 0 and renormalize the probabilities of all other assignments. In other words P_D(s) = # {D-consistent truth assignments in which s is assigned true} / # {D-consistent truth assignments}.
Technicality: There is an infinite number of statements so there is an infinite number of truth assignments. However there is only a finite number of statements that can figure in contradictions of length ⇐ D. Therefore all the other statements can be ignored (i.e. assumed to have independent probabilities of 1⁄2 like in P_0). More formally, the sigma-algebra of measurable sets on the space of truth assignments is generated by sets of the form {truth assignment T | T(s) = true} and {truth assignment T | T(s) = false}. The set of D-consistent truth assignments is in this sigma algebra and has positive probability w.r.t. our measure (as long as F is D-consistent) so we can use this set to form a conditional probability measure.
It may not be clear what you meant by “length” of contradiction. Is it the number of deductive steps to reach a contradiction, or the total number of symbols in a proof of contradiction?
Consider for instance two sentences X and ~X where X contains a billion symbols … Is that a contradiction of length 1, or a contradiction of length about 2 billion? I think you mean about 2 billion. In which case, you will always have PD(s) = 0.5 for sentences s of length greater than D. Right?
Thanks, that cleared things up.
At first I thought he meant P_D(s) is defined to be 0 if there is a proof in F of s implies false of length ⇐ D, and 1⁄2 otherwise, but then he says P_D(s) == 1 later for some s, so that’s not right.