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$
3
  • $\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
    Commented Jul 5, 2016 at 15:20
  • $\begingroup$ @Thorsten Almost surely not, since those sets need not be disjoint, which you need for a partition. $\endgroup$ Commented Jul 5, 2016 at 15:33
  • $\begingroup$ @Todd Trimble, Oh Right. it is not even a proper covering… $\endgroup$
    – Thorsten
    Commented Jul 5, 2016 at 15:42

1 Answer 1

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$
2
  • $\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$ Commented Jul 5, 2016 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$ Commented Jul 5, 2016 at 19:35

You must log in to answer this question.

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