\documentclass{amsart}
\usepackage{amsmath,amsfonts,amsthm,amssymb,indentfirst,epic,url,graphics}
\usepackage{hyperref}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.00in}
\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{-.5in}
\sloppy
\setlength{\mathsurround}{.167em}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}[theorem]{Question}
\newcommand{\strt}[1][1.7]{\vrule width0pt height0pt depth#1pt}% ^ strut
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\r}{\mathrm}
\newcommand{\card}{\r{card}}
\raggedbottom
\begin{document}
\vspace{-19em}
\begin{center}
\texttt{
This is the final preprint version of a paper which appeared at \\[.3em]
J.~Lond.~Math.~Soc.~(2) {\bf 93} (2016) 825-845.\\[.3em]
The published version is accessible to subscribers at\\[.3em]
\ http://dx.doi.org/10.1112/jlms/jdw011 .}
\end{center}
\vspace{3em}
\title%
{On Vaughan Pratt's crossword problem}
\thanks{%
After publication, any updates, errata, related references,
etc., found will be recorded at
\url{http://math.berkeley.edu/~gbergman/papers/}
and at \url{http://math.byu.edu/~pace/}.\\
\hspace*{1.05em}
Archived at \url{http://arXiv.org/abs/1504.07310}\,.\\
%
\hspace*{1.05em}
This work was partially supported by a grant from the
Simons Foundation (\#315828 to Pace Nielsen).
}
\subjclass[2010]{Primary: 08A99, 68R15,
% alg-strs:other cmbntrcs_on_wds
Secondary: 03E10, 03G10, 06A11, 06D05, 54A05, 68Q65.}
% ord+card alg_strs pos_alg~ lat_str top_sp& abstr.data.types
% in submission, only 5 allowed, dropped 06D05
\keywords{$\!T_1\!$ comonoid in $\!\mathbf{chu}_2,\!$
``crossword puzzle'', cardinality, distributive lattice%
}
\author{George M. Bergman}
\address{University of California\\
Berkeley, CA 94720-3840, USA}
\email{gbergman@math.berkeley.edu}
\author{Pace P.\ Nielsen}
\address{Brigham Young University\\
Provo, UT 84602-1231, USA}
\email{pace@math.byu.edu}
\begin{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 $\emptyset$ and $A,$
(ii)~if $C$ is a subset of $A\times A$ such that
for every $a\in A,$ both $\{b\mid (a,b)\in C\}$
and $\{b\mid (b,a)\in C\}$ are members of $W$ (a ``crossword'' with
all ``rows'' and ``columns'' in $W),$
then $\{b\mid (b,b)\in C\}$ (the ``diagonal word'')
also belongs to $W,$ and
(iii)~for all distinct $a,b\in 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 {\em 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.
\end{abstract}
\maketitle
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\section{Definitions and conventions}\label{S.defs}
We begin by defining the type of structures we will be considering.
These are called ``$\!\mathbf{chu}_2\!$ comonoids'' by Vaughan Pratt;
we shall call them {\em Pratt comonoids}.
The category-theoretic background of Pratt's terminology
is not a prerequisite for reading
this note; we sketch that background in an appendix,~\S\ref{S.chu}.
\begin{definition}\label{D.chu_cm}
By a {\em Pratt comonoid} we shall mean a pair $(A,W),$ where
$A$ is a set, and $W$ a set of subsets of $A$ such that
\textup{(i)} $\emptyset$ and $A$ are members of $W,$ and
\textup{(ii)} whenever $C$ is a subset of $A\times A$ such that
for every $a\in A,$ both $\{b\mid (a,b)\in C\}$
and $\{b\mid (b,a)\in C\}$ are members of $W,$ we also have
$\{b\mid (b,b)\in C\}\in W.$
In this situation, we will call $A$ the {\em base-set} of
the Pratt comonoid $(A,W),$ and $W$ the {\em Pratt
comonoid structure} on $A.$
A set $W$ of subsets of a set $A$ will be called $\!T_1\!$
if it satisfies
\textup{(iii)} for all $a,b\in A$ with $a\neq 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 {\em discrete} if
$W=2^A,$ the full power set of $A.$
\end{definition}
We shall generally identify subsets of $A$ or $A\times A$ with
$\!\{0,1\}\!$-valued functions on those sets.
In particular, we may call subsets of $A$ ``words''
on $A,$ and a subset $C\subseteq A\times 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\vee y$ and $x\wedge 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 $\leq$ and $\geq$ for inclusion, and
$<$ and $>$ for strict inclusion between words.
For $C\subseteq A\times A$ and $a\in A,$ we shall follow
the matrix-theoretic convention of calling $\{b\mid (a,b)\in C\}$
the $\!a\!$-th row, and $\{b\mid (b,a)\in 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).
This note was inspired by the following question, which will be
answered in the negative in~\S\ref{S.answer}.
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.VPq}
(V.\,Pratt \cite{puzzle}, \cite[pp.\,27--28]{chu_online}, \cite{chu})
\ Is every $\!T_1\!$ Pratt comonoid discrete?
\end{minipage}\end{equation}
Though~\eqref{d.VPq} concerns the $\!T_1\!$
case, many of the general results we prove will
concern arbitrary Pratt comonoids, with the $\!T_1\!$ condition
only brought in for the {\em coups de grace} of our main results.
Likewise, since our only known example of a $\!T_1\!$ Pratt comonoid
that is not discrete is quite complicated, examples showing the
obstructions to one or another approach
will in general be non-$\!T_1.$
We shall use set-theorists' notation for ordinals; in
particular, the set of natural numbers (nonnegative integers)
will be denoted $\omega.$
We shall write relative complements of sets as
$x-y=\{a\in x\mid a\notin y\}.$
When subsets of a given set $A$ are under consideration,
we shall often write $\neg x$ for the relative complement $A-x$
of a subset $x$ of $A.$
The next two sections mainly summarize known material.
\section{Some quick examples and immediate results}\label{S.quick}
The easiest examples of Pratt comonoids other than discrete
ones are gotten by taking a preorder $\preccurlyeq$ on a set $A,$
and defining $W$ to be the set of all {\em down-sets} of $A,$
that is, sets $x$ such that $a\preccurlyeq b\in x\implies a\in x$
\cite[Proposition~2.1]{comonoid}.
The reader can easily verify that
such pairs $(A,W)$ satisfy the definition.
For an example that deviates slightly from this form,
let $A$ consist of the set $\omega$ of natural numbers together
with one additional element $\infty,$ greater than every natural
number; and let
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.*w&infty}
$W\ =\ \{$down-sets of $A$ other than $\omega\,\}.$
\end{minipage}\end{equation}
%
In other words, $W$ consists of
those down-sets which, if they contain all natural
numbers, also contain $\infty.$
Since by the preceding paragraph, the set of {\em all} down-sets of $A$
yields a Pratt comonoid, to show that the $W$ we have just described
also determines one, we just have to show that any crossword over
$W$ whose diagonal contains all pairs $(n,n)$ $(n\in\omega)$ must
contain $(\infty,\infty).$
Now moving upward or to the left from the diagonal in such
a crossword $C$ (i.e., decreasing one or the other coordinate),
we see that every pair $(m,n)$ with $m,n\in\omega$
belongs to $C.$
Hence the word in $W$ given by each
natural-number-indexed row contains all natural numbers, hence,
by definition of $W,$ also contains $\infty.$
This says the
element of $W$ corresponding to the {\em column} indexed by $\infty$
contains all natural numbers, hence, again, contains $\infty;$ so
$(\infty,\infty)\in C,$ as required.
(The above example, essentially \cite[Proposition~2.4]{comonoid},
is an instance of the more general result
\cite[Proposition~2.2]{comonoid}, which says that what is called the
{\em Scott topology}
on a directed-complete partial order yields a Pratt comonoid.)
Here are some easy ways of getting new Pratt comonoids from old.
\begin{lemma}\label{L.new_fr_old}
\textup{(i)} If $(A,W)$ is a Pratt comonoid, then
so is $(A,W^\neg),$ where $W^\neg=\{\neg w\mid w\in W\},$ the set of
complements in $A$ of members of $W.$
If $(A,W)$ is $\!T_1,\!$ then so is $(A,W^\neg).$
\textup{(ii)} If $\{(A,W_i)\mid i\in I\}$ is a
\textup{(}finite or infinite\textup{)} set of Pratt comonoids
with the same base-set $A,$ then $(A,\,\bigcap_{i\in I} W_i)$
is a Pratt comonoid.
\textup{(iii)} If $f: A\to A'$ is a set map and $(A,W)$ a
Pratt comonoid, and we let $W'=\{w\subseteq A'\mid f^{-1}(w)\in W\},$
then $(A',W')$ is a Pratt comonoid.
\textup{(iv)} If $(A,W)$ is a Pratt comonoid, and $u\leq v$
are elements of $W,$ then the pair $(A_{u,v},W_{u,v}),$
where $A_{u,v} = v-u\subseteq A,$ and
$W_{u,v}=\{x-u\mid x\in W$ with $u\leq x\leq v\},$
is also a Pratt comonoid.
\end{lemma}
\begin{proof}[Sketch of proof]
We get (i)~by interchanging $\!0\!$'s and $\!1\!$'s in the conditions
defining a Pratt comonoid, and likewise in the $\!T_1\!$ condition.
Statement (ii)~holds because the condition for $(A,W)$ to be a
Pratt comonoid is a closure condition on $W,$ and for any
closure operator, an intersection of closed subsets is closed.
To see (iii), note that given any crossword $C'$ over $W',$ its
inverse image under $f\times f$ will be a crossword $C$ over $W,$
hence the diagonal thereof lies in $W,$ and that diagonal is the
inverse image of the diagonal of $C',$ which therefore lies in $W'.$
Finally, to see (iv), note that if $C\subseteq A_{u,v}\times A_{u,v}$
is a crossword over $W_{u,v},$ then $(u\times v)\vee(v\times u)\vee C$
will be a crossword over $W,$ hence its diagonal belongs
to $W,$ which translates to say
that the diagonal of $C$ belongs to $W_{u,v},$ as required.
\end{proof}
Part~(i) of the above lemma shows that when we prove a result
about Pratt comonoids, we can immediately get a dual statement
by applying that result to complements of words.
Likewise,~(iv) allows us to ``relativize'' any general result
about Pratt comonoids to yield a result about the set
of words $x\in W$ such that $u\leq x\leq v$
for given $u\leq v$ in~$W.$
Next, we note two easy ways of getting new words from old
within a given Pratt comonoid.
\begin{lemma}[{\cite[Proposition~2.5]{comonoid}}]\label{L.vee_wedge}
Let $(A,W)$ be a Pratt comonoid.
Then $W$ is closed under \textup{(}pairwise, hence finite\textup{)}
meets and joins.
That is, if $x,y\in W,$ then $x\wedge y$ and $x\vee y$ also
belong to $W.$
\end{lemma}
\begin{proof}
Given $x,y\in W,$ we find that $x\times y$ is a crossword
on $W$ (every row gives either the word $\emptyset$ or
the word $y;$ every column gives either $\emptyset$ or
$x),$ and its diagonal gives the word $x\wedge y,$
so $W$ is closed under intersections.
That it is also closed under unions follows by dualization,
i.e., applying the above result to the comonoid $(A,W^\neg)$
constructed as in Lemma~\ref{L.new_fr_old}(i).
Alternatively, one can verify directly that $(x\times A)\vee(A\times y)$
is a crossword on $W$ having $x\vee y$ as diagonal.
\end{proof}
Some observations on the above results:
Though we have seen that any intersection of Pratt comonoid
structures on a set $A$ is again a Pratt comonoid structure,
the same is not true of unions, even pairwise unions.
For instance, if $A=\{0,1,2\},$ and we let $W_\leq$ be the set of all
down-subsets of $A,$ and $W_\geq$ the set of up-subsets of $A,$ then
each of these is a Pratt comonoid structure, but their union
is not, since it contains both $\{0,1\}$ and $\{1,2\},$ but
not $\{0,1\}\cap\{1,2\}.$
Of course, since the condition of being a Pratt comonoid structure
on $A$ is a closure condition, there is a least such
structure containing the union of two given structures.
But the resulting
closure operation can expand the given union enormously.
For instance, suppose we let $A=\Z,$ the set of integers, again let
$W_\leq$ and $W_\geq$ be the systems of down-subsets and up-subsets
of $A,$ and let $W$ be the least Pratt comonoid structure
containing $W_\leq\cup W_\geq.$
By taking intersections, we see that $W$ contains all
singletons $\{i\}$ $(i\in\Z).$
Hence for any subset $x\subseteq\Z,$
the set $\{(i,i)\mid i\in x\}\subseteq\Z\times\Z$ is a
crossword over $W,$ since every row or column is either empty
or a singleton.
So $W$ consists of all subsets $x\subseteq \Z.$
Thus, closing under taking diagonals of crosswords has carried the
countable set $W_\leq\cup W_\geq$ to a set of continuum cardinality.
We saw in Lemma~\ref{L.vee_wedge} that each
Pratt comonoid structure on a set $A$ is closed under
pairwise unions and intersections.
However, such structures need not be closed under infinite unions
and intersections, as may be seen from the
example~\eqref{d.*w&infty} above, where $W$ contains
all the finite down-subsets of $\omega,$ but not their union,
$\omega$ itself.
Though we do not in general get all infinite unions and intersections,
everything we do get can be expressed in terms of such operations:
\begin{lemma}\label{L.diag_is_veewedge}
Let $A$ be any set, and $C:A\times A\to 2$ any map.
Then the subset $z\subseteq A$ corresponding to the diagonal of $C$
can be written as a \textup{(}possibly infinite\textup{)}
union of \textup{(}possibly infinite\textup{)} intersections
of subsets of $A$ corresponding to rows and columns of $C.$
\end{lemma}
\begin{proof}
For each $a\in A$ that occurs as a member of at least one row
or column of $C,$ let $x_a\subseteq A$ be the intersection of all
the rows and columns of $C$ that contain $a.$
Clearly, $a\in x_a.$
We claim that, in fact, $z=\bigvee_{a\in z} x_a.$
This will clearly imply the desired conclusion.
Indeed, for every $a\in z,$ the element $a$ lies in the above union,
namely, in the joinand indexed by $a.$
Conversely, if $b$ is in that union, this says it
lies in $x_a$ for some $a\in z.$
Looking at the $\!a\!$-th row of $C$ we conclude from the
definition of $x_a$ that since $C(a,a)=1,$ we have
$C(a,b)=1;$ and looking at the $\!b\!$-th column,
$C(a,b)=1$ similarly implies $C(b,b)=1.$
So $b\in z$ as required.
\end{proof}
The following easily verified observation (which does not
refer to diagonal words) will also be useful.
\begin{lemma}\label{L.2^*a}
If $A$ and $A'$ are sets, and $C$ a subset of $A\times A'$
which has precisely $\kappa$ distinct rows
\textup{(}resp.\ columns\textup{)} then it has at most $2^\kappa$
distinct columns \textup{(}resp.\ rows\textup{)}.
In particular, if $C$ has only finitely many distinct
rows \textup{(}columns\textup{)}, it has only finitely many
distinct columns \textup{(}rows\textup{)}.\qed
\end{lemma}
\section{The case where \texorpdfstring{$A$}{A} is countable}\label{S.countable}
We sketch below the proof of the known result that every $\!T_1\!$
Pratt comonoid $(A,W)$ with countable base-set $A$ is discrete.
First, a general observation.
\begin{lemma}\label{L.finite}
If $(A,W)$ is a $\!T_1\!$ Pratt comonoid and $A_0$
a finite subset of $A,$ then for any subset $y$ of $A_0$
there exists an $x\in W$ with $x\cap A_0 = y.$
\end{lemma}
\begin{proof}
For all $a,b\in A_0$ with $a\neq b,$ the $\!T_1\!$ condition
allows us to choose an $x_{a,b}\in W$ containing $a$ but not $b.$
By Lemma~\ref{L.vee_wedge}, the set
$x_a=\bigwedge_{b\in A_0-\{a\}} x_{a,b}$ is a member of $W$
containing $a$ but no other member of $A_0.$
We see that $x=\bigvee_{a\in y} x_a$ has the desired property.
\end{proof}
We can now get:
\begin{theorem}[V.\,Pratt {\cite[2nd exercise on p.\,28]{chu}}]\label{T.countable}
If $(A,W)$ is a $\!T_1\!$ Pratt comonoid, and $A$ is countable,
then $(A,W)$ is discrete.
\end{theorem}
\begin{proof}[Sketch of proof \textup{(after Mark G.\ Pleszkoch $\!=\!$ ``Mark Aujus'' \cite[Solution to puzzle 1.4]{puzzle})}]
Assume without loss of generality that $A=\omega.$
Take any $z\subseteq A,$ and assume inductively that for some $n$
we have found $x_0,\dots,x_{n-1},\,y_0,\dots,y_{n-1}\in W$
which are possible candidates for
the first $n$ rows and $n$ columns of a crossword having $z$ as
diagonal; i.e., such that the partial crossword formed by using the
$\!x_m\!$'s as its first $n$ rows and
the partial crossword formed by using the
$\!y_m\!$'s as its first $n$ columns agree
on their $n\times n$ intersection,
and the diagonal of that intersection yields the first
$n$ entries of $z.$
Now using the preceding lemma, with $A_0=\{0,\dots,n\},$
we can find $x_n,y_n\in W$ which extend our partial crossword;
i.e., such that the first $n$ entries
of $x_n$ are the entries of $y_0,\dots,y_{n-1}$ in the position
indexed by $n,$ while its next entry is the entry of $z$ needed in the
corresponding position on the diagonal;
and such that $y_n$ has the symmetric property.
This construction, continued recursively, leads to a full
crossword over $W$ with $z$ as diagonal.
\end{proof}
Now, on to new results.
\section{The complement-closed case}\label{S.complemented}
We shall prove in this section that if $(A,W)$ is a $\!T_1\!$ Pratt
comonoid, and $W$ is closed under complements, then
$(A,W)$ is discrete.
We begin with some observations on not
necessarily $\!T_1\!$ Pratt comonoids.
Though we have seen that for $(A,W)$ a Pratt comonoid,
$W$ need not be closed under infinite unions,
we claim that it is closed under unions
of families of subsets that are pairwise disjoint.
Here is a still more general statement.
\begin{lemma}\label{L.near_disjoint}
Suppose $(A,W)$ is a Pratt comonoid, and $x_i$ $(i\in I)$
are elements of $W$ such that for each $a\in A,$
only finitely many of the $x_i$ contain $a.$
Then $\bigvee_{i\in I} x_i\in W.$
\end{lemma}
\begin{proof}
Let $u=\bigvee_{i\in I}(x_i\times x_i)\subseteq A\times A.$
For each $a\in A,$ the $\!a\!$-th row (respectively,
the $\!a\!$-th column)
of $u$ is the union of finitely many of the $x_i,$ namely,
those that contain $a.$
Hence, since $W$ is closed under finite
unions, $u$ is a crossword over $W,$ hence its diagonal,
$\bigvee_{i\in I} x_i,$ indeed lies in $W.$
\end{proof}
\begin{corollary}\label{C.disjoint}
If $(A,W)$ is a Pratt comonoid, then $W$ is closed under
forming unions of disjoint families \textup{(}of arbitrary
cardinality\textup{)}.\qed
\end{corollary}
\begin{corollary}\label{C.complemented}
If $(A,W)$ is a Pratt comonoid such that $W$ is closed under
complementation, then $W$ is closed under
forming arbitrary unions.
Hence by duality, $W$ is also closed under
forming arbitrary intersections.
\end{corollary}
\begin{proof}
By Lemma~\ref{L.vee_wedge},
$W$ is closed under forming unions of finite families.
Let $\kappa$ be an infinite cardinal, assume inductively that
$W$ is closed under unions of families indexed
by sets of cardinality $<\kappa,$ and let $x_\beta$ $(\beta\in\kappa)$
be a $\!\kappa\!$-indexed family of members of $W.$
For each $\beta\in\kappa,$ our inductive hypothesis tells
us that $\bigvee_{\gamma<\beta} x_\gamma\in W,$ hence
since $W$ is closed under complementation,
the set $y_\beta=x_\beta-\bigvee_{\gamma<\beta} x_\gamma$
belongs to $W.$
The $y_\beta$ are easily seen to be pairwise disjoint and
to have union $\bigvee_{\beta\in\kappa} x_\beta.$
(Namely, each $a\in\bigvee_{\beta\in\kappa} x_\beta$
belongs to $y_\beta$ for $\beta$ the least ordinal
with $a\in x_\beta.)$
So by Corollary~\ref{C.disjoint}, that union belongs to $W.$
\end{proof}
We now get:
\begin{theorem}\label{T.complemented}
If $(A,W)$ is a $\!T_1\!$ Pratt comonoid such that $W$ is closed
under forming complements, then $(A,W)$ is discrete
\textup{(}i.e., $W$ is the set of all subsets of $A).$
\end{theorem}
\begin{proof}
Because $(A,W)$ is $\!T_1,\!$ for each $a\in A$ the intersection of
all members of $W$ that contain $a$ is $\{a\},$
so by the final assertion of
Corollary~\ref{C.complemented}, $W$ contains every singleton.
Since every subset of $A$ is a union of singletons, another application
of that corollary shows that $W$ contains every subset of $A.$
\end{proof}
\section{An interesting non-\texorpdfstring{$\!T_1\!$}{T1} Pratt comonoid structure on \texorpdfstring{$2^\omega$}{2\string^omega}}\label{S.2^*w}
In the first paragraph of \S\ref{S.quick}, we noted that easy
examples of Pratt comonoids $(A,W)$ in which $W$ was not the
set of all subsets of $A$ could be gotten by starting
with any partially ordered set $A,$ and letting $W$ be the
set of all its down-sets; and
in the next paragraph, we noted a case where such an $A$
admitted a slightly smaller comonoid structure $W,$ determined
by a sort of ``continuity'' condition.
Below, we construct another example of a sub-comonoid
of the Pratt comonoid arising from a partially ordered set,
which differs from it much more strikingly: The partially
ordered set $A$ we start with will be $2^\omega,$ ordered
by inclusion; the partially
ordered set of {\em all} its down-sets can be shown to
have cardinality $2^{2^{\aleph_0}},$ but our $W$ will be countable.
This example will be a key ingredient in our construction,
in the next section, of a non-discrete $\!T_1\!$ example.
Actually, we will construct the Pratt comonoid of this
section as a sub-comonoid
of the comonoid of all {\em up-sets} of $2^\omega,$ i.e., families of
subsets closed under enlargement.
The up-sets of any partially ordered set $A$ form a
Pratt comonoid structure on $A$ for the same
reason that the down-sets do,
and since the partially ordered set $2^\omega$ is isomorphic
to its opposite, the two comonoids are isomorphic
(cf.\ Lemma~\ref{L.new_fr_old}(i)).
We will use up-sets because it will be conceptually simpler to
take for the building blocks of our construction the
up-sets $e_n$ $(n\in\omega)$ consisting of all subsets of $\omega$
that contain $n,$ rather than the down-sets given by their complements.
Recall that for every set $A,$ the set $2^A$ of all subsets of $A,$
regarded as a direct product of copies of the discrete topological
space $2,$ is a compact Hausdorff space (compact by
Tychonoff's Theorem).
A subbasis for its open sets
is given by the sets $\{x\in 2^A\mid a\in x\}$ for $a\in A,$
and their complements, $\{x\in 2^A\mid a\notin x\}.$
We shall call this topology the {\em natural topology} on $2^A.$
In particular, both $2^\omega$ and $2^{2^\omega}$ have such topologies;
note that the definition of the topology on the latter set uses
only the set-structure of the former, and ignores its topology.
(But a relation between the topologies of these two sets
will be key to the proof of the final result of this section.)
We start with some observations on a general partially
ordered set $A.$
Recall that if $(A,\preccurlyeq)$ is a partially ordered set
and $a\in A,$ then ${\uparrow}(a)=\{b\in A\mid b\succcurlyeq a\}$
is called the {\em principal up-set} determined by $a.$
Likewise ${\downarrow}(a)=\{b\in A\mid b\preccurlyeq a\}$
is called the {\em principal down-set} determined by $a.$
(One normally calls these the principal up-set and principal down-set
{\em generated} by $a,$ but we will use ``determined'' to
avoid confusion with comonoids generated by sets of subsets.)
\begin{lemma}\label{L.isolated}
Let $A$ be a set given with a partial ordering $\preccurlyeq,$
and let $U_\preccurlyeq(A)\subseteq 2^A$ denote the set of up-sets
of $A,$ with the topology induced by the natural topology on $2^A.$
Then the following conditions on an element $x\in U_\preccurlyeq(A)$
are equivalent.
\textup{(i)} $x$ is an isolated point of the topological
space $U_\preccurlyeq(A);$
i.e., $x$ is not in the closure of $U_\preccurlyeq(A)-\{x\}.$
\textup{(ii)} $x$ is both the union of a finite \textup{(}possibly
empty\textup{)} family of principal up-sets, and
the intersection of a finite \textup{(}possibly
empty\textup{)} family of complements of principal down-sets.
\end{lemma}
\begin{proof}
To prove (ii)$\implies$(i), note that
if $x$ is a union ${\uparrow}(a_0)\vee\dots\vee{\uparrow}(a_{m-1}),$
then it is the smallest (under inclusion) element of
$U_\preccurlyeq(A)$ containing all of $a_0,\dots,a_{m-1}.$
Likewise, if it is an intersection
$\neg{\downarrow}(b_0)\wedge\dots\wedge\linebreak[1]
\neg{\downarrow}(b_{n-1}),$ then it is the largest element of
$U_\preccurlyeq(A)$ not containing any of $b_0,\dots,b_{n-1}.$
These conditions together make it the {\em unique} element of
$U_\preccurlyeq(A)$ containing each of the $a_i$ and none of the $b_j.$
Now the property of containing or not containing a specified
element of $A$ defines an open subset of $2^A,$ hence
of $U_\preccurlyeq(A).$
Thus, intersecting the $m+n$ open sets arising
from the above description, we get an open subset of $U_\preccurlyeq(A)$
having $x$ as its only point; so $x$ is isolated.
Conversely, since the subsets of $U_\preccurlyeq(A)$ defined by the
conditions of containing or not containing a given element of $A$ form
a subbasis of its open sets, if $x$ is isolated it must be
the unique point in a finite intersection of such sets;
i.e., the unique up-set that contains all
members of a finite family of points $a_0,\dots,a_{m-1}$
and no members of another finite family $b_0,\dots,b_{n-1}.$
It is easy to see that there is a least up-set containing
$a_0,\dots,a_{m-1}$ (namely,
${\uparrow}(a_0)\vee\dots\vee{\uparrow}(a_{m-1}))$
and a greatest containing none of $b_0,\dots,b_{n-1}$ (namely,
$\neg{\downarrow}(b_0)\wedge\dots\wedge\neg{\downarrow}(b_{n-1})).$
Given that the families of up-sets defined by these two properties
have nonempty intersection, if the least member of one family
and the greatest member of the other did not coincide,
then the intersection of the two families would not be a singleton.
So they do coincide, giving a description of $x$ as in~(ii).
\end{proof}
(M.\,Ern\'{e} has kindly pointed out to us that the above result
can be deduced from the general theory of continuous
lattices \cite{GHKLMS1980}, \cite{GHKLMS2003}.
Namely, in any lattice which is {\em bicontinuous}
in the sense of \cite[Chapter~VII]{GHKLMS2003}, the points
that are isolated in the bi-Scott topology
are those that are both {\em isolated from above} and
{\em isolated from below} in the sense of \cite[Chapter~I]{GHKLMS2003}.
A subclass of the bicontinuous lattices are the
{\em superalgebraic} lattices \cite{abc} \cite{ME}, which are,
up to isomorphism, the up-set lattices of partially
ordered sets $A;$ and in these, the elements isolated
from below are the finitely generated upsets,
those isolated from above are the complements
of finitely generated down-sets, and the bi-Scott topology
agrees with the topology induced by the natural topology on $2^A,$
yielding the statement of the lemma.)
We now apply the above lemma to the case where $A$ is
the set $2^\omega,$ partially ordered by inclusion.
(We could allow any set in place of $\omega,$ but we shall
see in \S\ref{S.*P_Pi} that this example can be generalized in other
ways; so we will just consider here the case we are about to use.)
Conditions~(i) and~(ii) below are as in the lemma;~(iii) is what is new.
\begin{corollary}\label{C.isolated}
Let $A=2^\omega,$ partially ordered by inclusion, $\subseteq,$
and $U_\subseteq(A)\subseteq 2^A$ its set of up-sets.
For each natural number $n,$ let $e_n\in U_\subseteq(A)$
denote the set of all subsets of $\omega$ containing $n.$
Then the following conditions on an element $x\in U_\subseteq(A)$
are equivalent.
\textup{(i)} $x$ is an isolated point of $U_\subseteq(A)$
under the natural topology.
\textup{(ii)} $x$ is both the union of a finite \textup{(}possibly
empty\textup{)} family of principal up-sets, and
the intersection of a finite \textup{(}possibly
empty\textup{)} family of complements of principal down-sets of $A.$
\textup{(iii)} $x$ lies in the lattice generated
by $\{e_n\mid n\in\omega\}\cup\{\emptyset,A\};$ i.e., the closure of
that set under pairwise unions and intersections.
\end{corollary}
\begin{proof}
By Lemma~\ref{L.isolated}, (i)$\iff$(ii), so it will suffice
to show that (iii)$\implies$(ii), and that
(i)$\wedge$(ii)$\implies$(iii).
Assume~(iii).
If $x=\emptyset,$ it is both the union of the empty
family of principal up-sets and the intersection of
a $\!1\!$-element family of complements of principal
down-sets, namely $\{\neg{\downarrow}(A)\},$ so it satisfies~(ii).
The case $x=A$ is seen similarly.
If $x$ is neither $\emptyset$ nor $A,$ it can be
written as a lattice-theoretic expression in the $e_n,$
and using distributivity, we can express it both as a
finite join of finite meets of these elements, and as
a finite meet of finite joins thereof.
Using the former expression, we note that each finite meet
$e_{n_0} \wedge\dots\wedge e_{n_{i-1}}$ is
the principal up-set determined by $\{n_0,\dots,n_{i-1}\},$
so we have the first condition of~(ii).
On the other hand, when we express $x$ as a finite meet
of finite joins of the $e_n,$ each of those finite joins
can be looked at as the complement of a finite meet
of complements of the $e_n;$ and we see that such a meet
$\neg e_{n_0}\wedge\dots\wedge\neg e_{n_{i-1}}$ is
a principal down-set, the set of elements of $A$ that
are $\leq\neg\{n_0,\dots,n_{i-1}\}.$
So $x$ is a finite meet of complements
of principal down-sets, giving the second condition of~(ii).
Conversely, assume (i)$\wedge$(ii).
By~(ii), $x$ can be written as a finite join
of principal up-sets,
$x={\uparrow}(s_0)\vee\dots\vee{\uparrow}(s_{n-1})$
$(s_0,\dots,s_{n-1}\subseteq\omega).$
Without loss of generality we may assume that none of the $s_i$
contains any of the others.
Suppose one of them, $s_i,$ were infinite.
Then ${\uparrow}(s_i)$ is the intersection of the
downward-directed set of up-sets ${\uparrow}(s)$ as $s$ ranges over the
finite subsets of $s_i,$ and we see that it will be the
limit of those up-sets under the topology on $U_\subseteq(A).$
Now holding the other $s_j$ in our expression for $x$ fixed, and
letting $s\to s_i$ as above, we get a family of up-sets approaching $x.$
Moreover, if one of these up-sets by which we are
approaching $x$ coincided with $x,$ say the one
constructed from a finite subset $s\subseteq s_i,$
then $x$ would have $s$ as a member, which it does not,
since none of the other $\!s_j\!$'s is contained in $s_i.$
Thus $x$ is a limit of points distinct from $x,$ contradicting~(i).
So all $s_i$ are finite, hence each ${\uparrow}(s_i)$ is a
finite (possibly empty) meet of the $e_n,$ so $x$ is a finite
(possibly empty) join of such finite meets, proving~(iii).
\end{proof}
We can now prove:
\begin{theorem}\label{T.2^*w}
Let $A=2^\omega;$ for each natural number $n$
let $e_n\subseteq A$ be the set of subsets of $\omega$ containing $n,$
and let $W\subseteq 2^A$ be the closure of
$\{e_n\mid n\in\omega\}\cup\{\emptyset,A\}$ under pairwise unions and
intersections.
Then $(A,W)$ is a Pratt comonoid.
\end{theorem}
\begin{proof}
We first note that every $x\in W,$ regarded as a
function $A\to 2,$ is continuous with respect to the
product topology on $A=2^\omega$ and the discrete topology on $2.$
Indeed, the generators $e_n$ and their
complements are the characteristic functions of
the open-closed generating sets for the topology on $A,$
hence are continuous, as are the constant functions $\emptyset$ and $A;$
and the general member of $W$ is obtained from the $e_n,$
$\emptyset,$ and $A$ using the
operations $\wedge$ and $\vee$ on $2,$ which are necessarily
continuous in the discrete topology on $2.$
Thus, if $C:A\times A\to 2$ is any crossword whose {\em rows}
are given by elements of $W,$ then each row represents a
continuous map $A\to 2.$
Hence the whole crossword, thought of as a map taking each element
of $A$ to the column it indexes, is a continuous function $A\to 2^A.$
Suppose now that $C$ as above has infinitely many distinct columns.
Let $B$ be an infinite subset of $A$ whose
members index distinct columns of $C.$
Since $A$ is compact, we can find some limit-point
$b\in A$ of $B.$
By continuity, the column of $C$ indexed by $b$ is
a limit-point of columns indexed by the elements of $B.$
Hence, since elements of $W$ are isolated points, the
$\!b\!$-th column of $C$ cannot be a member of $W.$
It follows that if all rows {\em and} columns of $C$ belong
to $W,$ then $C$ can have only finitely many distinct columns,
and thus by Lemma~\ref{L.2^*a}, also only finitely many distinct rows.
Hence we can apply Lemma~\ref{L.diag_is_veewedge} (with its
qualifier ``{\em possibly infinite}\/'' irrelevant because of the above
finiteness results), and the fact that $W$ is closed under
pairwise unions and intersections, to conclude that the diagonal of $C$
is a member of $W;$ proving that $(A,W)$ is a Pratt comonoid.
\end{proof}
We will have further use for the technique of the last sentence
of the above proof; so let us record what that argument gives us.
\begin{corollary}[to Lemmas~\ref{L.vee_wedge} and~\ref{L.diag_is_veewedge}]\label{C.fin_many}
Suppose $A$ is a set and $W$ a set of subsets of $A$ which
is closed under pairwise unions and intersections,
and contains $\emptyset$ and $A.$
Suppose, moreover, that no crossword $C: A\times A\to 2$ with
all rows and columns in $W$ has infinitely many distinct rows
\textup{(}equivalently, by Lemma~\ref{L.2^*a},
has infinitely many distinct columns\textup{)}.
Then $(A,W)$ is a Pratt comonoid.\qed
\end{corollary}
\section{A non-discrete \texorpdfstring{$\!T_1\!$}{T1} Pratt comonoid}\label{S.answer}
We are now ready to construct a Pratt comonoid $(A,W)$
that answers the question~\eqref{d.VPq} in the negative.
Intuitively, the idea will be to make our base-set $A$ the
union of many ``islands'', and take
$W$ to be generated by an uncountable family of
subsets $w_{n,\gamma}$ of $A,$ such that each generator, when
restricted to certain of the islands,
looks like one of the generators in the example of
Theorem~\ref{T.2^*w} above, while everywhere else, it
looks like one of a countable family of generators $u_n$ of a discrete
Pratt comonoid structure on $A.$
The fact that the $w_{n,\gamma}$ look ``in most places'' like the $u_n$
will make our structure $\!T_1.\!$
On the other hand, the system of ``islands'' will be
set up so that given any {\em countable} family of the $w_{n,\gamma},$
there is some island on which that
family acts precisely like our generating set for the
construction of Theorem~\ref{T.2^*w}.
We will use this property to show that, as in that theorem, no
crossword formed from lattice expressions in our generators
can have infinitely many distinct rows or columns; whence those
lattice expressions will in fact form a Pratt comonoid structure on $A,$
which we shall see is $\!T_1\!$ but not discrete.
We begin with an easy general observation.
\begin{lemma}\label{L.ctb_T1}
If $A$ is a set of continuum cardinality, then there is a countable
$\!T_1\!$ family $\{u_0,u_1,\dots\}$ of subsets of $A.$
\end{lemma}
\begin{proof}
It suffices to construct such a family for $A=2^\omega.$
To do this, let us define each even-indexed
set $u_{2n}$ to be the set $e_n$ of subsets of $\omega$ which
contain $n,$ and each odd-indexed set $u_{2n+1}$ to be
the set $\neg e_n$ of subsets of $\omega$ which do not contain $n.$
The $\!T_1\!$ property is immediate.
\end{proof}
Recalling that $\omega_1$ denotes the first uncountable ordinal,
we now define the base-set $A$ of our example:
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.ceg_A}
$A\ =\ A'\times A'',$ where
\hspace*{1em}$A'\ =$ the set of all one-to-one maps
$\omega\to\omega\times\omega_1,$
\hspace*{1em}$A''\ =\ 2^\omega.$
\end{minipage}\end{equation}
The typical element of $A$ will be written $(a',a''),$
with $a'\in A',$ $a''\in A''.$
The ``islands'' referred to in the above sketch
will be the sets $\{a'\}\times A''.$
Observe that $A$ has the cardinality of the continuum.
Indeed, since $A''$ has that cardinality, it suffices to show
that $A'$ has at most that cardinality.
Now $A'$ is contained in the set of {\em all} maps
$\omega\to\omega\times\omega_1,$ and the cardinality of that
set is bounded above
by the result of replacing $\omega\times\omega_1$ in that
description by $2^\omega,$ i.e., by the cardinality of
the set of maps $\omega\to 2^\omega,$ which
is $(2^{\aleph_0})^{\aleph_0}=
2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0},$ as required.
Hence by Lemma~\ref{L.ctb_T1}, we can
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.u_n}
let $\{u_n\mid n\in\omega\}$ be a countable $\!T_1\!$ family of subsets
of $A.$
\end{minipage}\end{equation}
We now define the family of subsets of $A$ (which we will
express as $\!\{0,1\}\!$-valued functions) that we will take as the
generators of our Pratt comonoid.
Namely, for each $(n,\gamma)\in\omega\times\omega_1,$
we let $w_{n,\gamma}:A\to 2$ be defined by
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.wn*m}
$w_{n,\gamma}(a',a'')\ = \left\{ \begin{array}{ll}
u_n(a',a'') & \mbox{if $(n,\gamma)$ is not among the
elements $a'(i)$ for $i\in\omega$ (cf.~\eqref{d.ceg_A}),}\\[.2em]
a''(i) & \mbox{if $i\in\omega$ satisfies $a'(i)=(n,\gamma).$}
\end{array}\right.$
\end{minipage}\end{equation}
Thus, for each ``island'' $\{a'\}\times A'',$
the coordinate $a'$ specifies a countable
sequence of ordered pairs $(n,\gamma)$ such that the corresponding
generators, $w_{n,\gamma},$ act on the $\!A''\!$-components
of members of that island
like the generating functions $e_i$ of the example of
Theorem~\ref{T.2^*w}; namely, if $(n,\gamma)=a'(i),$
then $w_{n,\gamma}$ selects the $\!i\!$-th coordinate of $a''.$
Now let
%
\begin{equation}\begin{minipage}[c]{29pc}\label{d.W_frm_wn*m}
\hspace*{-2.48pc}$W=$ the lattice of subsets
of $A$ generated by
$\{w_{n,\gamma}\mid n\in\omega,\,\gamma\in\omega_1\}\cup\{\emptyset,A\}$
under pairwise unions and intersections.
\end{minipage}\end{equation}
Most of our work will go into showing that $(A,W)$ is a Pratt comonoid.
Turning back to the definition~\eqref{d.ceg_A} of $A,$
observe that each $a'\in A'$ has countable image; hence the set
of second coordinates of elements of that image will be
bounded within $\omega_1.$
Hence defining, for each $\beta<\omega_1,$
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.A*l}
$A_\beta\ =\ \{(a',a'')\in A\mid$ the second coordinates of all
elements of the image of $a'$ are $<\beta\},$
%
\end{minipage}\end{equation}
%
we have
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.A=bigcup}
$A$ is the union of the chain of subsets
$A_\beta$ $(\beta\in\omega_1),$
\end{minipage}\end{equation}
%
and we see from the first line of~\eqref{d.wn*m} that
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.like_un}
for $\beta\in\omega_1,$ every $w_{n,\gamma}$ with $\gamma\geq\beta$
acts on $A_\beta$ by $u_n.$
\end{minipage}\end{equation}
We can now deduce that
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.wn*mT1}
$W$ is $\!T_1\!$ on $A.$
\end{minipage}\end{equation}
%
Namely, given $a_1,\ a_2\in A,$ the $\!T_1\!$ property
of the $u_n$ lets us choose an $n$ such that $u_n(a_1)=1,$ $u_n(a_2)=0,$
and~\eqref{d.A=bigcup} allows us to choose a $\beta$ such
that $a_1,\,a_2\in A_\beta;$
so by~\eqref{d.like_un}, $w_{n,\beta}(a_1)=u_n(a_1)=1,$
$w_{n,\beta}(a_2)=u_n(a_2)=0,$ as required.
Let us show next that
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.ctbl_on_A*l}
for every $\beta\in\omega_1,$ the restrictions to
$A_\beta\subseteq A$ of the
elements of $W\subseteq 2^A$ are countable in number.
\end{minipage}\end{equation}
%
By~\eqref{d.W_frm_wn*m} it suffices to show
that the restrictions to $A_\beta$ of the
generating elements $w_{n,\gamma}$ are countable in number.
By~\eqref{d.like_un}, those $w_{n,\gamma}$ with $\gamma\geq\beta$
have restrictions given by the countably many elements $u_n.$
By definition of $\omega_1,$
there are only countably many $\gamma<\beta,$ and hence only countably
many $w_{n,\gamma}$ with such $\gamma,$ completing the proof
of~\eqref{d.ctbl_on_A*l}.
We need, next, a combinatorial lemma (which we will apply
to occurrences of the $w_{n,\gamma}$ appearing as arguments in a
$\!j\!$-variable lattice term).
\begin{lemma}\label{L.all_or_1}
Let $X$ be a set, $j$ a positive integer, and $S$ an infinite
set of ordered $\!j\!$-tuples of elements of $X,$ such
that in each member of $S,$ the $j$ entries are distinct.
Then there exist an infinite subset $S'\subseteq S$ and an
$i0,$ we can find distinct
elements $x_\ell\in X$ $(\ell\in\omega)$ such that $S'$
consists of the $\!j\!$-tuples
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.j-tuples}
$(x_0,\dots,x_{i-1},\,x_{i+hk},\dots,x_{i+(h+1)k-1})$\quad
for $h\in\omega.$
\end{minipage}\end{equation}
%
\end{lemma}
\begin{proof}
Let $i0,$ we get the desired conclusion.
\end{proof}
The next result is somewhat more complicated to state, so for
simplicity we will only formulate the conclusion under one of the
two dual hypotheses.
But we remark that if both conditions
$\bigwedge_{m\in\omega} x_m =\emptyset$ and
$\bigvee_{n\in\omega} y_n =A$ hold, then the final hypothesis
says that although the sequence of $\!x\!$'s gets small, and the
sequence of $\!y\!$'s gets large, no $y_n$ contains any $x_m.$
The form shown is the modification of that condition needed
when $\bigvee_{n\in\omega} y_n$ is not necessarily everything.
When we refer to $W$ containing a complete
sublattice, we mean a subset closed in $2^A$ under
(possibly infinite) unions and intersections,
but not necessarily containing $\emptyset$ or $A.$
\begin{proposition}\label{P.continuum}
Again let $(A,W)$ be a Pratt comonoid, $x_0\geq x_1\geq\dots$ an
$\!\omega\!$-indexed descending chain of elements of $W,$
and $y_0\leq y_1\leq\dots$ an $\!\omega\!$-indexed ascending chain
of elements of $W,$ and
suppose that $\bigwedge_{m\in\omega} x_m =\emptyset.$
Suppose moreover that for no pair $(m,n)\in\omega\times\omega$
does $y_n$ contain $x_m\wedge\bigvee_{i\in\omega} y_i.$
Then $W$ has at least continuum cardinality;
in fact, it contains a complete sublattice isomorphic to the
lattice of all subsets of $\omega.$
\end{proposition}
\begin{proof}
Let us show, first, that we can construct sequences of integers
$m(0) n(j)$
such that $a\in y_{n(j+1)};$ moreover, since
$\bigwedge_{m\in\omega} x_m =\emptyset,$ we can find $m(j{+}1) > m(j)$
such that $a\notin x_{m(j+1)}.$
With $a,$ $n(j{+}1),$ and
$m(j{+}1)$ so chosen we see that~\eqref{d.mi_ni} also holds for $i=j.$
Thus we get sequences $m(i)$ and $n(i)$
satisfying~\eqref{d.mi_ni} for all $i\in\omega.$
Now let
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.z=}
$z\ =\ \bigvee_{i\in\omega}\,x_{m(i)} \wedge y_{n(i)}.$
\end{minipage}\end{equation}
%
Since $\{m(i)\}$ is a cofinal subsequence of $\omega,$ we
have $\bigwedge_{i\in\omega} x_{m(i)} = \emptyset,$ hence
by Lemma~\ref{L.x_i,y_i}, $z\in W.$
We claim that if for all $i\in\omega$ we define
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.zi=}
$z_i\ =\ z\vee (x_{m(i)}\wedge y_{n(i+1)})$
\end{minipage}\end{equation}
%
(again an element of $W),$ then
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.zi>}
for all $i,$ $z_i>z,$
\end{minipage}\end{equation}
%
but
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.zizj}
for $i\neq j,$ $z_i\wedge z_j = z.$
\end{minipage}\end{equation}
%
To see~\eqref{d.zi>}, apply~\eqref{d.mi_ni} to get an element
$a\in x_{m(i)}\wedge y_{n(i+1)}$ that is not in
$x_{m(i)}\wedge y_{n(i)}$ or $x_{m(i+1)}\wedge y_{n(i+1)}.$
Thus, $a\in (x_{m(i)} - x_{m(i+1)}) \wedge (y_{n(i+1)} - y_{n(i)}).$
The fact that $a$ is in the first of these two difference-sets
tells us that for $j>i, $ $a\notin x_{m(j)},$
while the fact that it is in
the second set tells us that for $j\leq i,$ $a\notin y_{n(j)},$ so
in each case, $a\notin x_{m(j)}\wedge y_{n(j)}.$
Hence $a\in z_i$ does not lie
in any of the joinands of~\eqref{d.z=}, giving~\eqref{d.zi>}.
To get~\eqref{d.zizj}, note that ``$\geq$'' holds
by~\eqref{d.zi>}, so it suffices to prove ``$\leq$''.
Assume without loss of generality that $i < j.$
Then
%
\begin{equation}\begin{minipage}[c]{28pc}\label{d.=>zizj}
\hspace*{-3.25pc}$z_i\ \wedge z_j\ =
\ z\vee((x_{m(i)}\wedge y_{n(i+1)})\wedge(x_{m(j)}\wedge y_{n(j+1)}))$
\quad (by~\eqref{d.zi=} and distributivity)\\
$=\ z \vee (x_{m(j)} \wedge y_{n(i+1)})$\hspace{1.1em}
(because $x_{m(j)}\leq x_{m(i)}$ and $y_{n(i+1)}\leq y_{n(j+1)})\\
\leq\ z \vee (x_{m(j)} \wedge y_{n(j)})$\hspace{2em}
(because $i{+}1\leq j,$ so $y_{n(i+1)}\leq y_{n(j)})$\\
$=\ z$ \hspace{9.05em}
(by~\eqref{d.z=}, in particular, the term indexed by $j).$
\end{minipage}\end{equation}
Statements~\eqref{d.zi>} and~\eqref{d.zizj} together say that the $z_i$
are sets properly containing $z,$ which on removing $z$ give
pairwise disjoint sets.
By Lemma~\ref{L.new_fr_old}(iv), the results of removing $z$
from all elements of $W$ which contain it form a
Pratt comonoid on $A-z;$ so the $z_i$ yield pairwise disjoint nonempty
elements of that Pratt comonoid, hence by
Corollary~\ref{C.disjoint}, the
unions of arbitrary subsets of these sets are members of that
Pratt comonoid.
The corresponding elements of $W$ give a complete
lattice of subsets of the asserted form.
\end{proof}
A problem with finding applications of
the above proposition is that it is often hard to
find natural hypotheses on a Pratt comonoid that lead to
a countable descending chain with empty intersection,
or, if we have such a chain, that lead to an ascending chain
which does not eventually ``swallow up'' the descending chain.
However in the next result we get both of these, using
the $\!T_1\!$ assumption together with the condition that $(A,W)$
be generated by the sort of family discussed
following Question~\ref{Q.ctbl_W} above.
When we speak of $(A,W)$ being ``generated by'' a family
$S$ of subsets of $A,$ we mean, of course, that $W$ is the least
Pratt comonoid structure on $A$ which contains $S.$
\begin{theorem}\label{T.continuum}
Suppose $(A,W)$ is a $\!T_1\!$ Pratt comonoid which can
be generated by a countably infinite family $S$ of subsets of
$A$ that satisfy no nontrivial distributive lattice relations
\textup{(}i.e., which form a set of free generators of a free
distributive lattice\textup{)}.
Then $W$ has at least continuum cardinality, and in fact contains a
complete sublattice isomorphic to the lattice of subsets of $\omega.$
\end{theorem}
\begin{proof}
If $A$ is countable, Theorem~\ref{T.countable} gives the desired
conclusion, so assume $A$ uncountable.
Now if we associate to
each $a\in A$ the set of members of $S$ which contain it, then to
distinct elements of $A$ we will associate distinct subsets of $S$
(because $W$ is $\!T_1,\!$ so $S$ must also be).
Hence only countably many
elements of $A$ can yield cofinite subsets of $S,$ so
let $a\in A$ be an element such that
the associated set is non-cofinite in $S.$
Let us now write $S$ as a disjoint union of two infinite sets: a set
$S_1$ which {\em properly} contains the set of elements of $S$
containing $a,$ but is still
non-cofinite; and its complement, $S_2=S-S_1.$
Since $S_1$ properly contains the
set of elements of $S$ containing $a,$ it includes
some element not containing $a,$ so the intersection of the
members of $S_1$ does not contain $a.$
On the other hand, for any $b\neq a,$ the $\!T_1\!$ condition tells us
that some $s\in S$ which contains $a$ (and hence belongs
to $S_1)$ does not contain $b;$ so the intersection of the members
of $S_1$ is empty.
Let us now index each of $S_1$ and $S_2$ by $\omega,$ and for each
$i\in\omega,$ let $x_i$ be the intersection of the first $i$ elements
of $S_1,$ and $y_i$ the union of the first $i$ elements of $S_2.$
We claim that for all $m$ and $n$ we have
$y_n \not\geq x_m\wedge (\bigvee_{i\in\omega} y_i).$
For if $y_n \geq x_m\wedge (\bigvee_{i\in\omega} y_i),$
then in particular, $y_n \geq x_m\wedge y_{n+1},$
which is a nontrivial lattice relation
among the first $m$ elements of $S_1$ and the first $n{+}1$ elements of
$S_2,$ contradicting the assumption on $S.$
So no such relation holds, hence
Proposition~\ref{P.continuum} gives the conclusion of the theorem.
\end{proof}
Did the above proof use the full strength of our hypothesis
that the elements of $S$ satisfy no nontrivial distributive
lattice relations?
If we write $S_1$ as $\{s_{1,i}\mid i\in\omega\}$
and $S_2$ as $\{s_{2,i}\mid i\in\omega\},$
then we find that the condition used at the end of the proof
reduces to the statement $s_{2,0}\vee\dots\vee s_{2,n-1}\not\geq
s_{1,0}\wedge\dots\wedge s_{1,m-1}\wedge s_{2,n}.$
Now the condition that the elements of $S$
satisfy no nontrivial distributive lattice relations
is indeed equivalent to saying that
for no two disjoint finite families of elements of $S$ does the join
of one majorize the meet of the other.
(To see this, note that any lattice word in a set of
elements of a distributive lattice can be reduced to a join
of meets, and also, dually, to a meet of joins.
Hence every relation on a family of elements of such a lattice is
equivalent to the statement that some meet of joins majorize
some join of meets.
But a meet majorizes an element if and only if each meetand
majorizes it; and a join is majorized by an element if and
only if each joinand is majorized by it; so every such relation
reduces to a family of relations each of which says that a join
of elements of our given set majorizes a meet of elements of that set;
hence freeness says that no such nontrivial relation,
i.e., no such relations in which no generator appears
as both a meetand and a joinand, holds.)
However, looking at the quantifications involved in the
proof of the theorem, one finds that one can slightly
restrict the set of relations that one needs to assume do not hold.
\begin{corollary}[to the proof of Theorem~\ref{T.continuum}]\label{C.continuum}
In the situation of Theorem~\ref{T.continuum}, the condition
that $S$ generate a free distributive lattice can be weakened
to say that there exists a partition of $S$ into finitely
many disjoint subsets, $S^{(0)},\dots,\,S^{(k-1)}$ such that no
relation $t_0\vee\dots\vee t_{n-1}\geq s_0\wedge\dots\wedge s_{m-1}$
holding in $W$ with every $t_j$ distinct from
every $s_i$ has all but at most
one of the $s_i$ belonging to the same set $S^{(i)}.$
\end{corollary}
\begin{proof}
Assume $S$ has the above weakened property.
In the proof of Theorem~\ref{T.continuum}, after choosing
$S_1$ to properly contain the set of elements of $S$ containing $a,$
and to have infinite complement, note that this complement
must contain infinitely many members of one of our sets,
say $S^{(i)}.$
So rather than taking $S_2$ to be the full complement of $S_1$
in $S,$ let us take it to consist of the members of that complement
which belong to $S^{(i)}.$
We can now complete the proof as before.
At the last step, if we have a relation
$s_{2,0}\vee\dots\vee s_{2,n-1}\geq
s_{1,0}\wedge\dots\wedge s_{1,m-1}\wedge s_{2,n},$
we note that
the meetands on the right satisfy $s_{1,0},\dots,s_{1,m-1}\in S^{(i)},$
with at most the last meetand $s_{2,n}$ not in $S^{(i)},$
contradicting the hypothesis on $S.$
\end{proof}
We do not know how one might make use of this weaker hypothesis in
studying Question~\ref{Q.ctbl_W}.
\section{Further results on Pratt comonoids with \texorpdfstring{$W$}{W} smaller than the continuum}\label{S.filters}
The arguments in the preceding section used
the fact that if $(A,W)$ is a Pratt comonoid such that
$W$ has cardinality less than the continuum, then $W$ cannot contain
infinitely many pairwise disjoint sets
(by Corollary~\ref{C.disjoint}).
This fact restricts the structure of such comonoids in other
ways as well.
The next lemma seems likely to be known,
but since we do not know a reference, we will give the proof.
We will be applying it to a lattice, the $W$ of a Pratt comonoid
$(A,W),$ but since it only involves the operation $\wedge,$ the
natural context for stating it is that of a $\!\wedge\!$-semilattice.
Recall that this means a
set $L$ with a single idempotent commutative associative
operation $\wedge;$ one then
regards $L$ as partially ordered by taking $x\leq y$ if $x\wedge y=x.$
Let us make:
\begin{definition}\label{D.str_indec}
If $L$ is a $\!\wedge\!$-semilattice with least element $0,$ we
shall call two elements of $L$ {\em disjoint} if their meet is $0,$ and
we will call a nonzero element $x\in L$ {\em strongly indecomposable}
if there do not exist two disjoint nonzero elements $0$ does not.
In particular, $x$ is not itself strongly indecomposable, so there
exist disjoint nonzero elements $x_0,\,y_0x$ in the obvious way.
Then the above observations give:
\begin{corollary}\label{C.str_indec}
Suppose $(A,W)$ is a Pratt comonoid such that $W$ has less
than continuum cardinality.
Then for every $w\in W$ \textup{(}including $\emptyset),$
the set of equivalence classes of elements
strongly indecomposable relative to $w$ is finite, and every
element $>w$ majorizes at least one such element.
Likewise, the set of equivalence classes of elements
{\em dually} strongly indecomposable relative to $w$ is finite, and
every element $x_1>\dots$ downward cofinal in $E,$
and so in particular, having empty intersection.
Given the countability of $W,$ Proposition~\ref{P.continuum}
implies that for any ascending chain $y_0\ x_m\wedge\bigvee_{i\in\omega} y_i.$
\end{minipage}\end{equation}
%
But in fact, we had enough information to see that
without calling on Proposition~\ref{P.continuum}.
On the one hand,~\eqref{d.geq} holds for all $m$ and $n$
if $x_0\wedge\bigvee_{i\in\omega} y_i=\emptyset.$
On the other hand, if this intersection is nonempty, that means
some $y_n$ has nonempty intersection with $x_0.$
That intersection belongs to $E,$
hence will majorize some $x_m,$ and the relation $y_n>x_m$
then implies~\eqref{d.geq}.
Though such increasing and decreasing chains do not have the
properties that would allow us to call on
Proposition~\ref{P.continuum} and get a contradiction, they
do lead to the following result, which
contrasts with the behavior of the examples of
Theorems~\ref{T.2^*w} and~\ref{T.T1_nondiscrete}.
\begin{proposition}\label{P.inf_crswd}
If $(A,W)$ is a $\!T_1\!$ Pratt comonoid with $W$ countably infinite,
then there exist crosswords over $W$ with infinitely many
distinct rows and columns.
\end{proposition}
\begin{proof}
As noted above, we can construct an infinite descending
chain $(x_m)$ with empty intersection, and by duality,
an infinite ascending chain $(y_n)$ with union $A.$
Without loss of generality, let us take these chains
to be strictly decreasing and strictly increasing respectively.
Then $C=\bigvee_n x_n\times y_n$ will be the desired crossword.
Indeed, given $a\in A,$ let $m$ be the greatest integer
such that $a\in x_m;$ then we see that the row of $C$ indexed
by $a$ will be given by $y_m\in W,$ and a dual statement applies
to columns; so the rows and columns of $C$ comprise precisely
$\{x_m\}\cup\{y_n\},$ an infinite subset of $W.$
\end{proof}
Here is another sort of chain that we can
construct in any infinite $\!T_1\!$ Pratt comonoid with $W$ countable,
or more generally, with $\card(W)$ both less than the
continuum and less than $\card(A).$
The relativized version of Lemma~\ref{L.a,E} shows that
for every $w\in W$ there are
only finitely many elements $a\notin w$ which
dominate equivalence classes relative to $w$ that have
intersection strictly larger than $w.$
Since $\card(W)<\card(A),$ there must be an $a$ which, relative to
every $w$ not containing it, dominates no such equivalence classes.
Now starting a recursion with $y_0=\emptyset,$ assume we have
elements $y_0<\dots