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 Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View