#### Supplement to Common Knowledge

## 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 *i*
∈ *N*,
_{i}(ω) ⊆
(ω),
which shows that
is a coarsening of the partitions
_{i},
*i*
∈ *N*.
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 *i*_{1},
*i*_{2},
… , *i*_{n} ∈ *N*

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

We will prove (1) by induction on *n*. By definition,
_{i}(ω)
⊆
(ω)
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 =
_{ik} (…
(_{i2}
(_{i1}(ω))).
By induction hypothesis, *A* ⊆
(ω).
Since
_{i}(*A*)
states that *i*_{1} thinks
that *i*_{2} thinks that …
*i*_{k} 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.

Peter Vanderschraaf <

*pvanderschraaf@gmail.com*>

Giacomo Sillari <

*gsillari@andrew.cmu.edu*>