Skip to main content
eScholarship
Open Access Publications from the University of California

On Vaughan Pratt's crossword problem

  • Author(s): Bergman, GM
  • Nielsen, PP
  • et al.
Abstract

© 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's open access policies. Let us know how this access is important for you.

Main Content
Current View