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∈N

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

that is, R(ω) is the set of all worlds that are reachable from ω. Clearly, for each i ∈ N, H_i(ω) ⊆ R(ω), which shows that R is a coarsening of the partitions H_i, i ∈ N. Hence M(ω) ⊆ R(ω), as M is the finest common coarsening of the H_i’s.

We need to show that R(ω) ⊆ M(ω) to complete the proof. To do this, it suffices to show that for any sequence i₁, i₂, … , i_n ∈ N

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

We will prove (1) by induction on n. By definition, H_i(ω) ⊆ 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 ω* ∈ H_i(A) where A = H_ik (… (H_i2 (H_i1(ω))). By induction hypothesis, A ⊆ M(ω). Since H_i(A) states that i₁ thinks that i₂ thinks that … i_k thinks that i thinks that ω* is possible, A and H_i(ω*) must overlap, that is, H_i(ω*) ∩ A ≠ ∅. If ω* ∉ M(ω), then H_i(ω*) ⊈ M(ω), which implies that M is not a common coarsening of the H_i’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