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$

2 Answers 2

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$ Commented Jul 5, 2016 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$ Commented Jul 6, 2016 at 0:43
  • $\begingroup$ Ops. You are right, of course. $\endgroup$ Commented Jul 6, 2016 at 6:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .