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

Question: For infinite sets $X$, is there an injective lattice homomorphism $f:\text{Cov}(X)\to \text{Part}(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$ You ask for a lattice homomorphism, but is the collection of coverings a lattice? $\endgroup$ – Joel David Hamkins Sep 22 '16 at 13:38
  • $\begingroup$ I updated my answer with an argument showing that Cov(X) is not generally a lattice. $\endgroup$ – Joel David Hamkins Sep 22 '16 at 14:20
3
$\begingroup$

The answer is no, because in general there can be more proper coverings than partitions, which will prevent any injective mapping from coverings to partitions.

For example, if $X$ is countably infinite, then there are only continuum many partitions, but I claim that there are $2^{\frak{c}}$ many proper coverings. So there can be no such injective map from coverings to partitions.

There are continuum many partitions of a countably infinite set $X$, since every partition is determined by a function $X\to\omega$.

To see that there are $2^{2^{\aleph_0}}$ many distinct proper coverings, let me identify $X$ with the nodes of the binary branching tree $2^{<\omega}$. Consider any collection of branches through the tree, which covers the tree. Any such collection is a proper covering, since no branch is contained in another, unless they are equal. How many proper coverings have this special form? Well, we can cover the tree with countably many branches, and then add any further set of branches. Since there are continuum many branches, this gives rise to $2^{\mathfrak{c}}$ many proper coverings.

Finally, although you asked for a lattice homomorphism from $\text{Cov}(X)$ to $\text{Part(X)}$, I claim that the collection of proper coverings is not generally a lattice. To see this, consider again the case where $X$ consists of the finite binary sequences, which can be arranged into the tree $2^{<\omega}$. Let $U_0$ be the covering consisting of all the eventually-0 branches, and let $U_1$ consist of the eventually-1 branches. These are both proper coverings of $X$. But I claim there is no greatest lower bound of $U_0$ and $U_1$. Suppose that $W$ is a proper covering that refines both $U_0$ and $U_1$. So every element of $W$ is contained in an eventually-0 branch and also contained within an eventually-1 branch. Thus, every element of $W$ must be finite and linearly ordered as in the tree. Now, there can be no largest such $W$ below $U_0$ and $U_1$, because I can glue together any two such finite sets, as long as they remain linearly ordered, and get a strictly larger covering (with respect to refinement) which remains below both $U_0$ and $U_1$. So it is not a lattice. The non-lattice counter-example can be generalized to any infinite set, simply by working on a countably infinite subset.

$\endgroup$
  • $\begingroup$ Another way to get $2^{\frak{c}}$ many proper covers: divide $X$ into pairs, and then consider any covering consisting of those pairs, plus any collection of sets that select exactly one from each pair. These are all proper coverings, and there are $2^{\frak{c}}$ many of them. $\endgroup$ – Joel David Hamkins Sep 22 '16 at 15:20
  • $\begingroup$ That construction shows in ZFC that for any infinite set $X$, the number of proper covers of $X$ is $2^{2^{|X|}}$, but the number of partitions of $X$ is merely $2^{|X|}$, so there is no injection from proper covers of $X$ to partitions of $X$. $\endgroup$ – Joel David Hamkins Sep 23 '16 at 0:34

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.