On Vaughan Pratt's crossword problem
George M. Bergman, Pace P. Nielsen · Journal of the London Mathematical Society · 2016
Vaughan Pratt has introduced objects consisting of pairs (A,W) where A is a set and W a set of subsets of A, such that (i) W contains ∅ and A, (ii) if C is a subset of A×A such that for every a∈A, both {b∣(a,b)∈C} and {b∣(b,a)∈C} are members of W (a ‘crossword’ with all ‘rows’ and ‘columns’ in W), then {b∣(b,b)∈C} (the ‘diagonal word’) also belongs to W, and (iii) for all distinct a,b∈A, the set W has an element which contains a but not b. He has asked whether for every A, the only such W is the set of all subsets of A. We answer that question in the negative. We also obtain several positive results, in particular, a positive answer to the above question if W is closed under complementation. We obtain partial results on whether there can exist counterexamples to Pratt's question with W countable.