Supplement to Common Knowledge
Proof of Lemma 2.15
Lemma 2.15.ω′ ∈ M(ω) iff ω′ is reachable from ω.
Proof.
Pick an arbitrary world ω ∈ Ω, and let
R(ω) = ∞
∪
n=1
∪
i1,i2,…,in∈NHin (… (Hi2 (Hi1(ω)))
that is, R(ω) is the set of all worlds that are reachable from ω. Clearly, for each i ∈ N, Hi(ω) ⊆ R(ω), which shows that R is a coarsening of the partitions Hi, i ∈ N. 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, … , in ∈ N
(1) Hin (… (Hi2 (Hi1(ω)))
We will prove (1) by induction on n. By definition, Hi(ω) ⊆ M(ω) for each i ∈ N, proving (1) for n = 1. Suppose now that (1) obtains for n = k, and for a given i ∈ N, let ω* ∈ Hi(A) where A = Hik (… (Hi2 (Hi1(ω))). By induction hypothesis, A ⊆ M(ω). 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. □
Peter Vanderschraaf <pvanderschraaf@gmail.com>
Giacomo Sillari <gsillari@sas.upenn.edu>