This is a file in the archives of the Stanford Encyclopedia of Philosophy.

## Proof of Lemma 2.11

Lemma 2.11.    ( ) iff  is reachable from .

Proof.
Pick an arbitrary world   , and let ( ) =  n = 1 i 1, i 2, . . . , i n N i n ( . . . ( i 2 ( i 1 ( ) ) )

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 ) i n ( . . . ( i 2 ( i 1( ) ) )

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 = i k ( . . . ( i 2 ( i 1 ( ) ) ). 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. 