Proof of Lemma 2.15

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

Proof.
Pick an arbitrary world ω ∈ Ω, and let (ω) = ∞ ∪ n=1 ∪ i1,i2,…,in∈N in (… ( i2 ( i1(ω)))

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

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

 (1) in (… ( i2 ( i1(ω)))

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