This is the final preprint version of a paper which appeared at J. Lond. Math. Soc. (2) 93 (2016) 825-845. The published version is accessible to subscribers at https://dx.doi.org/10.1112/jlms/jdw011 . ON VAUGHAN PRATT’S CROSSWORD PROBLEM GEORGE M. BERGMAN AND PACE P. NIELSEN Abstract. 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. 1. Definitions and conventions We begin by defining the type of structures we will be considering. These are called “chu_{2} comonoids” by Vaughan Pratt; we shall call them Pratt comonoids. The category-theoretic background of Pratt’s termi- nology is not a prerequisite for reading this note; we sketch that background in an appendix, §10. Definition 1. By a Pratt comonoid we shall mean a pair (A, W), where A is a set, and W a set of subsets of A such that (i) ∅ and A are members of W, and (ii) whenever 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, we also have {b | (b, b) ∈ C} ∈ W. In this situation, we will call A the base-set of the Pratt comonoid (A, W), and W the Pratt comonoid structure on A. A set W of subsets of a set A will be called T_{1} if it satisfies (iii) for all a, b ∈ A with a ≠ b, the set W has an element which contains a but not b. A Pratt comonoid (A, W) will be called T_{1} if W is T_{1} as a set of subsets of A. It will be called discrete if W = 2^{A}, the full power set of A. We shall generally identify subsets of A or A×A with {0, 1}-valued functions on those sets. In particular, we may call subsets of A “words” on A, and a subset C ⊆ A × A satisfying the hypotheses of (ii) a “crossword” over W, since its rows and columns are words lying in W. We will use the notation x ∨ y and x ∧ y for the union and intersection (or from the {0, 1} point of view, pointwise sup and pointwise inf) of words x and y, and likewise ≤ and ≥ for inclusion, and < and > for strict inclusion between words. For C ⊆ A × A and a ∈ A, we shall follow the matrix-theoretic convention of calling {b | (a, b) ∈ C} the a-th row, and {b | (b, a) ∈ C} the a-th column (rather than the convention of the cartesian plane, where the first member of an ordered pair is the horizontal and the second the vertical coordinate). 2010 Mathematics Subject Classification. Primary: 08A99, 68R15, Secondary: 03E10, 03G10, 06A11, 06D05, 54A05, 68Q65. Key words and phrases. T_{1} comonoid in chu_{2}, “crossword puzzle”, cardinality, distributive lattice. After publication, any updates, errata, related references, etc., found will be recorded at /~gbergman/papers/ ict␣begin␣H.S␣end https://math.byu.edu/~pace/d.

Archived at https://arXiv.org/abs/1504.07310 d .

This work was partially supported by a grant from the Simons Foundation (#315828 to Pace Nielsen).

1