Stanford Encyclopedia of Philosophy

Supplement to Common Knowledge

Proof of Lemma 2.15

Lemma 2.15.
ω′ ∈ calligraphic-M(ω) iff ω′ is reachable from ω.

Pick an arbitrary world ω ∈ Ω, and let

calligraphic-R(ω) =


calligraphic-Hin (… (calligraphic-Hi2 (calligraphic-Hi1(ω)))

that is, calligraphic-R(ω) is the set of all worlds that are reachable from ω. Clearly, for each iN, calligraphic-Hi(ω) ⊆ calligraphic-R(ω), which shows that calligraphic-R is a coarsening of the partitions calligraphic-Hi, iN. Hence calligraphic-M(ω) ⊆ calligraphic-R(ω), as calligraphic-M is the finest common coarsening of the calligraphic-Hi's.

We need to show that calligraphic-R(ω) ⊆ calligraphic-M(ω) to complete the proof. To do this, it suffices to show that for any sequence i1, i2, … , inN

(1) calligraphic-Hin (… (calligraphic-Hi2 (calligraphic-Hi1(ω)))

We will prove (1) by induction on n. By definition, calligraphic-Hi(ω) ⊆ calligraphic-M(ω) for each iN, proving (1) for n = 1. Suppose now that (1) obtains for n = k, and for a given iN, let ω* ∈ calligraphic-Hi(A) where A = calligraphic-Hik (… (calligraphic-Hi2 (calligraphic-Hi1(ω))). By induction hypothesis, Acalligraphic-M(ω). Since calligraphic-Hi(A) states that i1 thinks that i2 thinks that … ik thinks that i thinks that ω* is possible, A and calligraphic-Hi(ω*) must overlap, that is, calligraphic-Hi(ω*) ∩ A ≠ Ø. If ω* not in calligraphic-M(ω), then calligraphic-Hi(ω*) not in calligraphic-M(ω), which implies that calligraphic-M is not a common coarsening of the calligraphic-Hi's, a contradiction. Hence ω* ∈ calligraphic-M(ω), and since i was chosen arbitrarily from N, this shows that (1) obtains for n = k + 1. QED

Return to Common Knowledge