3
$\begingroup$

This is a follow-up question to this question, prompted by a comment in Todd Trimble's answer.

Let $X\neq \emptyset$ be a set. We say that $U\subseteq {\cal P}(X)\setminus \{\emptyset\}$ is a proper covering if

  • $\bigcup U = X$, and
  • for $a\neq b\in U$ we have $a\not\subseteq b$.

Let $\text{Cov}(X)$ denote the collection of all (proper) coverings of $X$. For $A, B\in \text{Cov}(X)$ we set $A\leq B$ if $A$ refines $B$, that is for all $a\in A$ there is $b\in B$ such that $a\subseteq b$. (Note that if we consider all coverings instead of just the proper ones, we may lose anti-symmetry.)

Is $\text{Cov}(X)$ with the ordering defined above a lattice? Is it complete?

$\endgroup$
5
$\begingroup$

If there are only finitely many points, it is a lattice, and it is always an upper semi-lattice. But in the infinite case, it is not a lattice.

François's comment on Fedor's answer shows that is it always at least an upper semi-lattice, since the join of two covers $A$ and $B$ consists precisely of the inclusion maximal elements of $A\cup B$. It follows from this observation that there can be no finite counterexample to the original question. This is because there is always a least cover, the cover consisting of the singletons, and any finite upper semi-lattice with a least element is a lattice: the meet of any two objects is the join of their (finitely many) lower bounds. So if there are only finitely many points, then indeed it is a lattice.

Meanwhile, there are counterexamples in the case of infinitely many points. Consider the disjoint union of two copies of the integers $\newcommand\Z{\mathbb{Z}}\Z\sqcup \Z$, red and blue, and let $A$ consist of sets of the form $\{r\mid r<k\}\sqcup\{b\mid b>k\}$, where $r$ is red and $b$ is blue and $k\in\Z$. And let $B$ consist of the sets of the form $\{r\mid r>k\}\sqcup\{b\mid b<k\}$. So each of these are proper covers of $\Z\sqcup\Z$.

I claim that there is no greatest lower bound of $A$ and $B$. If $C$ is a cover that is a lower bound, then every member of $C$ will have to have all red elements below all blue elements (if any), because it refines $A$; and similarly, it will have to have all blue elements below all red elements (if any), because it refines $B$. So every element of $C$ will be monochromatic. Furthermore, the elements of $C$ must be bounded above in the red component and below in the blue component, because it refines $A$, and bounded below in the red component and above in the blue component, because it refines $B$. So every member of $C$ is a finite monochromatic set. Furthermore, it is easy to see that any proper cover consisting entirely of finite monochromatic sets is a lower bound to both $A$ and $B$ under refinement.

Thus, there can be no greatest lower bound for $A$ and $B$, because for any such lower bound, we can make a strictly coarser lower bound by simply merging two sets of the same color (and omitting any subsets of the merger).

A similar example can be made with any infinite set, simply by finding two copies of $\Z$ inside the set. So on an infinite set, it is not a lattice.

$\endgroup$
0
2
$\begingroup$

(Completely wrong answer, saved for saving the comments.)

It is not a lattice in general. Consider four corners of the square and two coverings by parallel sides. They do not have unique supremum.

$\endgroup$
3
  • 3
    $\begingroup$ It seems to me that the unique supremum in this case is the cover consisting of all four sides. In fact, I think that if $A$ and $B$ are two covers, then the supremum is the proper cover that consists of all inclusion maximal elements of $A \cup B$. $\endgroup$ – François G. Dorais Jul 5 '16 at 23:33
  • $\begingroup$ It follows that in general, it is an upper semi-lattice. And therefore, if there are only finitely many points, it is a lattice. Namely, there is a least cover, consisting of the singletons, and any finite upper semi-lattice with a least element is a lattice: the meet of any two elements is the join of their lower bounds. So any counterexample must be infinite. $\endgroup$ – Joel David Hamkins Jul 6 '16 at 0:43
  • $\begingroup$ Ops. You are right, of course. $\endgroup$ – Fedor Petrov Jul 6 '16 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.