Common Knowledge > Proof of Lemma 2.15 (Stanford Encyclopedia of Philosophy/Winter 2006)

Supplement to Common Knowledge

Proof of Lemma 2.15

Lemma 2.15.
ω′ ∈ calligraphic-M

(ω) iff ω′ is reachable from ω.

Proof.
Pick an arbitrary world ω ∈ Ω, and let

(ω) = ∞
∪
ⁿ⁼¹
∪
^{i₁,i₂,…,i_n∈N} _{i_n} (… (_i₂ (_i₁(ω)))

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

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

(1) _{i_n} (… (_i₂ (_i₁(ω)))

We will prove (1) by induction on n. By definition, calligraphic-H _i(ω) ⊆ calligraphic-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 ω* ∈ _i(A) where A = _{i_k} (… (_i₂ (_i₁(ω))). By induction hypothesis, A ⊆ (ω). Since _i(A) states that i₁ thinks that i₂ thinks that … i_k thinks that i thinks that ω* is possible, A and calligraphic-H _i(ω*) must overlap, that is, _i(ω*) ∩ A ≠ Ø. If ω* not in calligraphic-M (ω), then _i(ω*) not in (ω), 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. QED

Return to Common Knowledge