On Vaughan Pratt's crossword problem
- Author(s): Bergman, GM
- Nielsen, PP
- et al.
Published Web Locationhttps://doi.org/10.1112/jlms/jdw011
© 2016 London Mathematical Society. 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 \emptyset and A, (ii) if C is a subset of A\times A such that for every a\in A, both (a,b) and b,a are members of W (a 'crossword' with all 'rows' and 'columns' in W then (b,b)\in C (the 'diagonal word') also belongs to W and (iii) for all distinct a,b 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.
Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.