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

Supplement to Common Knowledge

() 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.

*First published: August 27, 2001*

*Content last modified: August 27, 2001*