Centre for Discrete and Applicable Mathematics |
|
CDAM Research Report, LSE-CDAM-2006-19December 2006 |
The Common Knowledge of Formula Exclusion
Robert Samuel Simon
A multi-partition with evaluations is defined by two sets S and X, a collection P1, . . . ,Pn of partitions of S and a function ψ: S → {0, 1}X. To each partition Pj corresponds a person j who cannot distinguish between any two points belonging to the same member of Pj but can distinguish between different members of Pj. A cell of a multi-partition is a minimal subset C such that for all j the properties P ∈ Pj and P ∩ C ≠ ∅ imply that P ⊆ C. Construct a sequence R0,R1, . . . of partitions of S by R0 = { ψ-1(a) | a ∈ {0, 1}X} and x and y belong to the same member of Ri if and only if x and y belong to the same member of Ri-1 and for every person i the members Px and Py of Pj containing x and y respectively intersect the same members of Ri-1. Let R∞ be the limit of the Ri, namely x and y belong to the same member of R∞ if and only if x and y belong to the same member of Ri for every i. For any set X and number n of persons there is a canonical multi-partition with evaluations defined on a set Ω such that from any multi-partition with evaluations (using the same X and n) there is a canonical map to Ω with the property that x and y are mapped to the same point of Ω if and only if x and y share the same member of R∞. We define a cell of Ω to be surjective if every multi-partition with evaluations that maps to it does so surjectively. A cell of a multi-partition with evaluations has finite fanout if every P ∈ Pj in the cell has finitely many elements. All cells of Ω with finite fanout are surjective, but the converse does not hold.A PDF file (121 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2006-19, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. |
||
Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk |
Introduction to the CDAM Research Report Series. | ||
CDAM Homepage. |