Supplement to Common Knowledge

Proof of Lemma 2.15

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

Pick an arbitrary world ω ∈ Ω, and let

R(ω) = 


Hin (… (Hi2 (Hi1(ω)))

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

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

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

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

Return to Common Knowledge

Copyright © 2013 by
Peter Vanderschraaf <>
Giacomo Sillari <>

Open access to the SEP is made possible by a world-wide funding initiative.
Please Read How You Can Help Keep the Encyclopedia Free

The SEP would like to congratulate the National Endowment for the Humanities on its 50th anniversary and express our indebtedness for the five generous grants it awarded our project from 1997 to 2007. Readers who have benefited from the SEP are encouraged to examine the NEH’s anniversary page and, if inspired to do so, send a testimonial to