5
$\begingroup$

Let $X\neq \emptyset$ be a set. We say that $U\subseteq {\cal P}(X)\setminus \{\emptyset\}$ is a covering of $X$ if $\bigcup U = X$. We call a covering proper if for $a\neq b\in U$ we have $a\not\subseteq b$.

Let $\text{Cov}(X)$ denote the collection of all 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 pre-order on $\text{Cov}(X)$; it is easily seen that it is not anti-symmetric. However, the refinement relation is anti-symmetric on $\text{PropCov}(X)$, the set of proper coverings.

On $\text{Cov}(X)$ we set $A \simeq B$ if $A\leq B$ and $B\leq A$. It is easy to verify that the relation $\leq_q $ on $\text{Cov}(X)/\simeq$ defined by $$[A]_\simeq \leq_q [B]_\simeq \text{ if and only if } A \leq B \text{ in Cov}(X)$$ is a partially ordered set.

Are $(\text{Cov}(X)/\simeq, \leq_q)$ and $(\text{PropCov}(X),\leq)$ isomorphic as posets?

$\endgroup$

2 Answers 2

3
$\begingroup$

Are $(\text{Cov}(X)/\simeq, \leq_q)$ and $(\text{PropCov}(X),\leq)$ isomorphic as posets?

If $X$ is finite, then $(\text{Cov}(X)/\simeq, \leq_q)$ and $(\text{PropCov}(X),\leq)$ are isomorphic, but if $X$ is infinite they are not.

To see why they are isomorphic when $X$ is finite it is enough to note that, in the case of finite $X$, each $\simeq$-class of covers has the property that all members share the same maximal elements. Moreover, this common set of maximal elements constitutes a proper cover, and it is the unique proper cover in this $\simeq$-class. This bijection between $\simeq$-classes of covers and proper covers preserves and reflects order, hence establishes an isomorphism between $(\text{Cov}(X)/\simeq, \leq_q)$ and $(\text{PropCov}(X),\leq)$.

To see why $(\text{Cov}(X)/\simeq, \leq_q)$ and $(\text{PropCov}(X),\leq)$ are not isomorphic whene $X$ is infinite, it will suffice to point out that $(\text{Cov}(X)/\simeq, \leq_q)$ is a lattice while $(\text{PropCov}(X),\leq)$ is not.

I first argue the easy part: $(\text{Cov}(X)/\simeq, \leq_q)$ is a lattice.

Consider the following closure operator on the set of covers: given $B\in \text{Cov}(X)$, let $B^* = \bigcup_{A\leq B} A$. It is easy to see that $B^*$ is a cover of $X$, and that an alternative definition for it is $$ B^* = (\bigcup_{b\in B} {\mathcal P}(b))\setminus \{\emptyset\}. $$ Moreover, $A\leq B$ holds iff $A\subseteq B^*$ iff $A^*\subseteq B^*$, so $A\simeq B$ iff $A^*=B^*$.

Now, a subset $Z\subseteq {\mathcal P}(X)$ is of the form $Z=B^*$ iff (i) $\emptyset\notin Z$ and (ii) $Z\cup\{\emptyset\}$ is an order ideal of ${\mathcal P}(X)$ which contains all the singleton subsets of $X$. This is enough to show that $(\text{Cov}(X)/\simeq, \leq_q)$ is isomorphic to the interval of the lattice of order ideals of ${\mathcal P}(X)$ above the order ideal consisting of singleton sets. This is a distributive, algebraic lattice.

Now the less-easy part. I argue that $(\text{PropCov}(X),\leq)$ is not a lattice. In fact, I will write out only the case $X=\omega$, but afterwards I will explain how to extend the argument to any superset of $\omega$.

Let's name some subsets of $\omega$:
$E$: the set $\{0,2,4,\ldots\}$ of all even natural numbers.
$E_n$: the set $\{0,2,4,\ldots,2n\}$ of even numbers up to $2n$.
$E_n^*$: the set $\{0,2,4,\ldots,2n,2n+1\}$ of even numbers up to $2n$ along with one odd number $2n+1$.

Now let's name some proper covers of $\omega$:
$C_E$: the proper cover consisting of $E$ and all odd singletons.
$C_{E^*}$: The proper cover consisting of all $E_n^*$'s.
$C_n$: The proper cover including $E_n$ and all singletons of elements from $\omega \setminus E_n$.

It is not hard to see that
(1) $C_E$ and $C_{E^*}$ are incomparable under $\leq$.
(2) $C_n\leq C_E$ and $C_n\leq C_{E^*}$ for all $n$.

My goal is to show that $C_E$ and $C_{E^*}$ do not have a meet (= greatest lower bound) in $(\text{PropCov}(X),\leq)$.

Suppose that $D$ is a proper cover of $\omega$ that is a candidate for the meet of $C_E$ and $C_{E^*}$ in $(\text{PropCov}(X),\leq)$. Then $D\leq C_E$, $D\leq C_{E^*}$, and $D$ is above all other common lower bounds of $C_E$ and $C_{E^*}$, for example $C_n\leq D$ for all $n$.

Since $E_n=\{0,2,4,\ldots,2n\}\in C_n$, there must be a set $d_n\in D$ such that $E_n\subseteq d_n$. Since $D\leq C_E$, it follows that $d_n$ consists of even integers. Since $D\leq C_{E^*}$, it follows that $d_n$ is a finite set. Thus $d_n$ is properly contained in some $E_m=\{0,2,\ldots,2m\}$ for sufficiently large $m$. But now repeat this argument to find some $d_m\in D$ containing $E_m$. We now have $d_n\subsetneq E_m \subseteq d_m$, contradicting the properness of $D$. \\\\\

Finally, to extend the proof that $(\text{PropCov}(\omega),\leq)$ is not a lattice to a proof that $(\text{PropCov}(X),\leq)$ is not a lattice, for any superset $X\supseteq \omega$, repeat the argument above, but extend all the covers of $\omega$ which were used in the argument to covers of $X$ by adding to those covers all singletons $\{x\}$, $x\in X\setminus\omega$.

$\endgroup$
1
  • $\begingroup$ Thanks for putting in this effort to solve the question! $\endgroup$ Commented Oct 16, 2018 at 15:32
2
$\begingroup$

I don't think they are isomorphic. Let $X=\mathbb N$ and let $A$ be a covering consisting of the sets of the form $$ a_n = \{ 0, \dots, n \} $$ for every $n\in \mathbb N$.

Then, $A$ is not $\simeq$-equivalent to any proper covering.

$\endgroup$
3
  • $\begingroup$ Could you explain how you intend to use this to show that the partial orders are not isomorphic? $\endgroup$ Commented Jan 23, 2017 at 13:25
  • $\begingroup$ I see, your question is more general. My example explains why the embedding $\text{PropCov} \hookrightarrow \text{Cov}$, given by $A \mapsto [A]_\simeq$, is not an isomorphism. $\endgroup$ Commented Jan 23, 2017 at 15:57
  • $\begingroup$ OK - thanks Tomas, maybe a variant of your argument can be used to show there is no isomorphism in general? (Although my intuition was, the two posets are isomorphic, but intuitions in mathematics can of course be misleading.) $\endgroup$ Commented Jan 24, 2017 at 14:22

You must log in to answer this question.

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