Jump to ContentJump to Main Navigation
Knowledge and its Limits$

Timothy Williamson

Print publication date: 2002

Print ISBN-13: 9780199256563

Published to Oxford Scholarship Online: November 2003

DOI: 10.1093/019925656X.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 27 February 2017

(p.311) Appendix 4 Iterated Probabilities in Epistemic Logic (Proofs)

(p.311) Appendix 4 Iterated Probabilities in Epistemic Logic (Proofs)

Source:
Knowledge and its Limits
Publisher:
Oxford University Press

First some standard definitions. A frame is a pair <W,R>, where R is a binary relation on the set W. For w∈W, R(w)={x∈W: wR x}. R is serial on W just in case for every w∈W there is an x∈W such that wR x. <W,R> is serial (reflexive, symmetric, transitive) just in case R is serial (reflexive, symmetric, transitive) on W. A frame is partitional just in case it is reflexive, symmetric, and transitive. A probability distribution on W is a mapping P from all subsets of W to nonnegative real numbers such that P(W) = 1 and P(X∪Y) = P(X) + P(Y) whenever X and Y are disjoint subsets of W. If P(Y) > 0, P(X|Y) = P(X∩ Y)/P(Y); if P(Y) = 0, P(X|Y) is undefined. A probability distribution P on W is regular just in case P(X) > 0 whenever X is a non‐empty subset of W. A frame <W,R> is bland just in case it is serial and P(X) = w∈W P({w})P(X|R(w)) for every X ⊆ W and regular probability distribution P on W. R(w) is always non‐empty when <W,R> is serial, so P(R(w)) > 0 if P is regular, so P(X|R(w)) is defined; if <W,R> is not serial, R(w) is empty for some w∈W and P(X|R(w)) is undefined.

Proposition 1. Every bland finite frame is reflexive.

Proof. Let <W,R> be a bland finite frame and x∈W. Suppose that not xR x. Since <W,R> is serial, xR y for some yx. Thus W has n+2 members for some n≥0. There is a (unique) regular probability distribution P on W such that:

P ( { x } ) = 2 / 3 P ( { w } ) = 1 / 3 ( n + 1 ) for  w W { x } .
Now
Σ w W P ( { w } ) P ( W { x } | R ( w ) ) P ( { x } ) P ( W { x } | R ( x ) ) .
Since not xR x, R(x)⊆ W–{x}, so P(W–{x}|R(x)) = 1. Thus
Σ w W P ( { w } ) P ( W { x } | R ( w ) ) P ( { x } ) = 2 / 3 > 1 / 3 = P ( W { x } ) .
This contradicts the blandness of <W,R>. Thus xR x. ▪

Proposition 2. Every bland finite frame is symmetric.

Proof. Let <W,R> be a bland finite frame, and x, y∈W. Suppose that xR y but not yR x. Hence xy, so W has n+2 members for some n≥0. There is a (unique) regular probability distribution P on W such that: (p.312)

P ( { x } ) = 1 / 2 P ( { y } ) = ( n + 2 ) / 4 ( n + 1 ) P ( { w } ) = 1 / 4 ( n + 1 ) for  w W { x , y } .
Now
Σ w W P ( { w } ) P ( { y } | R ( w ) ) P ( { x } ) P ( { y } | R ( x ) ) + P ( { y } ) P ( { y } | R ( y ) ) = P ( { y } | R ( x ) ) / 2 + ( n + 2 ) P ( { y } | R ( y ) ) / 4 ( n + 1 ) > P ( { y } | R ( x ) ) / 2 + P ( { y } | R ( y ) ) / 4 .
Since xR y, {y} ⊆ R(x), so
P ( { y } | R ( x ) ) = P ( { y } ) / P ( R ( x ) ) P ( { y } ) .
But not yR x, so R(y) ⊆ W–{x}, so
P ( R ( y ) ) P ( W { x } ) = 1 P ( { x } ) = 1 / 2 .
Now yR y because R is reflexive by Proposition 1, so {y} ⊆ R(y), so
P ( { y } | R ( y ) ) = P ( { y } ) / P ( R ( y ) ) 2P ( { y } ) .
Thus
Σ w W P ( { w } ) P ( { y } | R ( w ) ) > P ( { y } ) / 2 + 2P ( { y } ) / 4 = P ( { y } ) .
This contradicts the blandness of <W,R>. Thus if xR y then yR x. ▪

Proposition 3. Every bland finite frame is transitive.

Proof. Let <W,R> be a bland finite frame, and x, y, z∈W. Suppose that xR y and yR z but not xR z. Hence xy and yz. By Proposition 1, xR x, so xz. Thus W has n+3 members for some n≥0. There is a (unique) regular probability distribution P on W such that:

P ( { x } ) = P ( { z } ) = 1 / 3 P ( { w } ) = 1 / 3 ( n + 1 ) for  w W { x , z } .
Now
Σ w W P ( { w } ) P ( { y } | R ( w ) ) P ( { x } ) P ( { y } | R ( x ) ) + P ( { y } ) P ( { y } | R ( y ) ) + P ( { z } ) P ( { y } | R ( z ) ) = P ( { y } | R ( x ) ) / 3 + P ( { y } | R ( y ) ) / 3 ( n + 1 ) + P ( { y } | R ( z ) ) / 3 .
Since xR y, {y} ⊆ R(x), so
P ( { y } | R ( x ) ) = P ( { y } ) / P ( R ( x ) ) .
Moreover, yR z and R is symmetric by Proposition 2, so zR y, so {y} ⊆ R(z), so
P ( { y } | R ( z ) ) = P ( { y } ) / P ( R ( z ) ) .
Finally, yR y since R is reflexive, so {y} ⊆ R(y), so
P ( { y } | R ( y ) ) = P ( { y } ) / P ( R ( y ) ) .
(p.313) Thus
Σ w W P ( { w } ) P ( { y } | R ( w ) ) P ( { y } ) / 3 P ( R ( x ) ) + P ( { y } ) / 3 ( n + 1 ) P ( R ( y ) ) + P ( { y } ) / 3 P ( R ( z ) ) > 1 / 3 P ( { y } ) ( 1 / P ( R ( x ) ) + 1 / P ( R ( z ) ) ) .
Since not xR z, R(x) ⊆ W–{z}, so
P ( R ( x ) ) P ( W { z } ) = 1 P ( { z } ) = 2 / 3 .
Similarly, not zR x because R is symmetric, so
P ( R ( z ) ) 2 / 3 .
Hence
1 / 3 P ( { y } ) ( 1 / P ( R ( x ) ) + 1 / P ( R ( z ) ) ) 1 / 3 P ( { y } ) ( 3 / 2 + 3 / 2 ) = P ( { y } ) .
Thus
Σ w W P ( { w } ) P ( { y } | R ( w ) ) > P ( { y } ) .
This contradicts the blandness of <W,R>, so if xR y and yR z then xR z. ▪

Proposition 4. Every finite partitional frame is bland.

Proof. Let <W,R> be a finite partitional frame and P a regular probability distribution on W. Since R is reflexive on W, <W,R> is serial. Let w, x∈W. If not w∈R(x) then not x∈R(w) because R is symmetric, so {x}∩ R(w) = {}, so

P ( { x } | R ( w ) ) = 0 .
If w∈R(x) then R(x) = R(w) and {x} ⊆ R(w), since <W,R> is partitional, so
P ( { x } | R ( w ) ) = P ( { x } ) / P ( R ( w ) ) = P ( { x } ) / P ( R ( x ) ) .
Hence
Σ w W P ( { w } ) P ( { x } | R ( w ) ) = Σ w R ( x ) P ( { w } ) P ( { x } | R ( w ) ) = Σ w R ( x ) P ( { w } ) P ( { x } ) / P ( R ( x ) ) = ( P ( { x } ) / P ( R ( x ) ) ) Σ w R ( x ) P ( { w } ) = ( P ( { x } ) / P ( R ( x ) ) ) / P ( R ( x ) ) = P ( { x } ) .
Hence, for any X ⊆ W, w∈W P({w})P(X|R(w)) = P(X). ▪

Proposition 5. A finite frame is bland if and only if it is partitional.

Proof. From Propositions 1‐4. ▪

Remark. The proofs of Propositions 1–3 and 5 use non‐uniform distributions: P({x}) ≠ P({y}) for some x, y∈W (for finite frames, uniformity entails regularity). This is essential, in the sense that if ‘bland’ had been defined with ‘uniform’ in place of ‘regular’ then the analogues of Propositions 1–3 would have been false. (p.314) A non‐partitional frame <W,R> can satisfy the equation P(X) = w∈W P({w})P(X|R(w)) for every X ⊆ W when P is the uniform distribution on W. To see this, let W = {0, 1, 2} and R = {<0,1>, <1,2>, <2,0>}. Thus R(0)={1}, R(1)={2}, R(2)={0}, and R is serial but neither reflexive, symmetric, nor transitive on W. Let P be the uniform distribution on W; P({0}) = P({1}) = P({2}) = 1/3. Nevertheless,

Σ w W P ( { w } ) P ( X | R ( w ) ) = Σ w W P ( X | R ( w ) ) / 3 = P ( X { 1 } ) / 3 P ( { 1 } ) + P ( X { 2 } ) / 3 P ( { 2 } ) + P ( X { 0 } ) / 3 P ( { 0 } ) = P ( X { 1 } ) + P ( X { 2 } ) + P ( X { 0 } ) = P ( X ) .
Of course, the examples in the main text show that not every finite serial frame is bland even in this weakened sense.

Now say that a frame <W,R> is banal just in case it is serial and P(X|{w∈W:P(X|R(w))=c}) = c for every real number c, subset X of W and regular probability distribution P on W such that the conditional probability is defined (i.e. P(X|R(w))=c for some w∈W). Banality is a form of Miller's Principle or the Principal Principle.

Proposition 6. A finite frame is banal if and only if it is partitional.

Proof. Suppose that <W,R> is a finite partitional frame, X ⊆ W and P is a regular probability distribution on W. If wR x then R(w)=R(x) since R is an equivalence relation, so P(X|R(x))=c if P(X|R(w))=c. Thus, if the conditional probability is defined,

{ w W : P ( X | R ( w ) ) = c } = R ( w 1 ) R ( w n )
where the R(w i ) are pairwise disjoint and P(X|R(w i ))=c for 1≤ in. Thus
P ( X R ( w i ) ) = cP ( R ( w i ) )
for 1≤ in. Hence
P ( X { w W : P ( X | R ( w ) ) = c } ) = P ( X ( R ( w 1 ) R ( w n ) ) = Σ 1 i n P ( X R ( w i ) ) = c Σ 1 i n P ( R ( w i ) ) = cP ( R ( w 1 ) R ( w n ) ) = cP ( { w W : P ( X | R ( w ) ) = c } ) .
Thus P(X|{w∈W:P(X|R(w))=c}) = c.

Conversely, suppose that <W,R> is a finite banal frame. Let W = {w 0,. . . , w m }. There is a regular probability distribution P on W such that:

P ( { w i } ) = 2 i / ( 2 m + 1 1 ) ( 1 i m )
Thus for all X,Y ⊆ W, P(X) = P(Y) only if X = Y. Suppose that xR y. Let c = P({y}|R(x)). Since y∈R(x), c>0 and P({y}) = cP(R(x)). Now suppose that P({y}|R(w)) = c. Since c>0, y∈R(w), so P({y}) = cP(R(w)). Hence cP(R(w)) = (p.315) cP(R(x)); since c>0, P(R(w)) = P(R(x)), so R(w)) = R(x). Conversely, if R(w) = R(x) then P({y}|R(w)) = P({y}|R(x)) = c. Thus:
{ w : P ( { y } | R ( w ) ) = c } = { w : R ( w ) = R ( x ) }
Hence:
P ( { y } | { w : R ( w ) = R ( x ) } = P ( { y } | { w : P ( { y } | R ( w ) ) = c } ) = c = P ( { y } | R ( x ) )
because <W,R> is banal. By reasoning as above, {w:R(w)=R(x)} = R(x). Since <W,R> is serial (because banal), this conclusion holds for all x∈W. Thus wR x if and only if R(w)=R(x); since the latter equation defines an equivalence relation, <W,R> is partitional. ▪