1
$\begingroup$

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$.

This relation defines a lattice structure on the collection of all partitions of $X$ (which we denote by $\text {Part}(X)$). Interestingly, every lattice can be embedded into $\text{Part}(X)$ for some set $X$ (will provide reference when I find it).

Question: Is $\text{Part}(X)$ a quotient of the bigger lattice $\text{Cov}(X)$?

PS: The reason we only consider proper coverings, and not all coverings, is that the refinement relation is not anti-symmetric for all coverings.

$\endgroup$
  • $\begingroup$ Is this the quotient you are looking for? $$ q: \text{Cov}(X) \longrightarrow \text{Part}(X) \\ q(U) = \{ \bigcup_{a\in U, x\in A} a \ \mid x \in X\} $$ $\endgroup$ – Thorsten Jul 5 '16 at 15:20
  • $\begingroup$ @Thorsten Almost surely not, since those sets need not be disjoint, which you need for a partition. $\endgroup$ – Todd Trimble Jul 5 '16 at 15:33
  • $\begingroup$ @Todd Trimble, Oh Right. it is not even a proper covering… $\endgroup$ – Thorsten Jul 5 '16 at 15:42
4
$\begingroup$

We can at least say there is a poset quotient map $q: \text{Cov}(X) \to \text{Part}(X)$ that preserves joins. (The discussion at Does the collection of coverings on a set $X$ form a lattice when ordered by refinement? indicates that $\text{Cov}(X)$ is at least a join-semilattice, and of course so is $\text{Part}(X)$, but $\text{Cov}(X)$ does not admit all meets if $X$ is infinite.)

So we want a reasonable way to extract a partition $\pi(U)$ from a covering $U$, and a way to do that is to let one's intuition be guided by Venn diagram pictures. With Venn diagrams, one imagines a covering by blobs and then one closes up under Boolean operations to pass to a blob refinement, which in turn induces a partition.

So, given a covering $U$, let $B(U)$ be the intersection of all Boolean subalgebras of $P(X)$ that contain $U$. Define a partition $\pi(U)$ (a set of equivalence classes for an equivalence relation) where the equivalence class of an element $x \in X$ is $[x] := \bigcap \{C \in B(U): x \in C\}$. Equivalently: $y \in [x]$ iff $\forall_{C \in B(U)} \; x \in C \Rightarrow y \in C$.

Let's check that we do have an equivalence relation. Clearly we have reflexivity, i.e., $x \in [x]$. If $y \in [x]$, then also $x \in [y]$. Else there exists $D \in B(U)$ such that $y \in D$ but $x \notin D$. Then $x \in \neg D$, whence $y \in [x] \subseteq \neg D$ (the inclusion holds since $\neg D \in B(U)$), and this contradicts $y \in D$. Thus we have symmetry. Finally, if $y \in [x]$ and $z \in [y]$, then $z \in [x]$ by exploiting the equivalent formulation stated at the end of he previous paragraph. So we have transitivity.

Since we have an equivalence relation, the set $\pi(U)$ of equivalence classes $[x]$ forms a partition. It should be clear that if $C \leq D$ in $\text{Cov}(X)$, then $\pi(C) \leq \pi(D)$, i.e., $\pi$ is order-preserving. Also notice that for each $U \in \text{Cov}(X)$, the partition $\pi(U)$ refines $U$: any $C \in U$ is nonempty, and then for any $x \in C$ we have $[x] \subseteq C$ by construction. So in the lattice $\text{Cov}(X)$, we have $U \leq \pi(U)$. Finally, notice $\pi (U) = U$ if $U$ is a partition (since in that case each $C \in U$ is an atom in $B(U)$), so that in particular $\pi\pi(U) = \pi(U)$.

Thus $\pi: \text{Cov}(X) \to \text{Cov}(X)$ forms a Moore closure operator whose fixed points are exactly the partitions of $X$. This defines a poset quotient map $q: \text{Cov}(X) \to \text{Part}(X)$ sending $U \mapsto \pi(U)$, and it is a general fact that this quotient map preserves joins (a category theorist would see this in a more general context where $q \dashv i: \text{Part}(X) \hookrightarrow \text{Cov}(X)$ is a monadic adjunction whose monad is $\pi = i q$, and a left adjoint like $q$ always preserves coproducts, which in posets are simply joins).

$\endgroup$
  • $\begingroup$ Very nice -- I actually noticed I made an error in my proof sketch (which I had jotted down sloppily by hand) that $\text{Cov}(X)$ is a lattice. Since I don't know that I'm going to ask it in a separate question (and will accept your answer to this question here). $\endgroup$ – Dominic van der Zypen Jul 5 '16 at 19:08
  • $\begingroup$ @DominicvanderZypen If your drop the requirement of "properness", and think of possibly non-proper coverings as forming a preorder under the refinement relation, then I think it's easy to see that this preorder as a category has products (meets) and coproducts (joins). I could return to considering your question under that relaxation if you are interested; I don't have an answer right away to the question of meet-preservation, but it might not be difficult. $\endgroup$ – Todd Trimble Jul 5 '16 at 19:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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