#### 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

∪

i_{1},i_{2},…,i_{n}_{}∈NH _{in}(… (H_{i2}(H_{i1}(ω)))

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*_{1},
*i*_{2},
… , *i*_{n} ∈ *N*

(1) H _{in}(… (H_{i2}(H_{i1}(ω)))

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*_{1} thinks
that *i*_{2} 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.
□

Peter Vanderschraaf <

*pvanderschraaf@gmail.com*>

Giacomo Sillari <

*gsillari@sas.upenn.edu*>