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,…,inN
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 <pvanderschraaf@ucmerced.edu>
Giacomo Sillari <gsillari@sas.upenn.edu>

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