Is this ordering on the set of all covers of $\omega$ a (complete) lattice?

Question

Let ${\frak C} \subseteq {\cal P}({\cal P}(\omega))$ be the collection of all covers of $\omega$ (that is, ${\cal C} \in {\frak C}$ iff $\bigcup {\cal C} = \omega$.)

We define the following binary relation on ${\frak C} = $: For ${\cal A}, {\cal B} \in {\frak R}$ we say ${\cal A} \leq_\text{r} {\cal B}$ if ${\cal A}$ is a refinement of ${\cal B}$, that is for all $A\in {\cal A}$ there is $B\in {\cal B}$ with $A\subseteq B$. The elements $\{\omega\}, \{\omega, \{0\}\}\in{\frak C}$ show that the relation $\leq_\text{r}$ is not anti-symmetric, so we set ${\cal A}\simeq_\text{r} {\cal B}$ if ${\cal A} \leq_\text{r}{\cal B}$ and ${\cal B} \leq_\text{r}{\cal A}$. So we get a poset $$({\frak C}/\simeq_\text{r},\leq_\text{r}),$$ where $\leq_\text{r}$ applies to equivalence classes in the usual way.

Question. Is the poset $({\frak C}/\simeq_\text{r},\leq_\text{r})$ a (complete) lattice?

Answer 1

Yes. The l.u.b. of $\mathcal A$ and $\mathcal B$ is $\mathcal A \cup \mathcal B$. The g.l.b. of $\mathcal A$ and $\mathcal B$ is $\{A\cap B: A\in\mathcal A , B\in\mathcal B\}$.

We can even generalize by replacing $\subseteq$ by an arbitrary meet-semilattice preordering, in which case

• The l.u.b. of $\mathcal A$ and $\mathcal B$ is still $\mathcal A \cup \mathcal B$.
• The g.l.b. of $\mathcal A$ and $\mathcal B$ is now the equivalence closure of $\{A\wedge B: A\in\mathcal A , B\in\mathcal B\}$ where $A\wedge B$ is a representative of the meet of $A$ and $B$.

One example of this is to replace $\subseteq$ by Turing reducibility. Then $A\wedge B$ can be a set encoding both the information in $A$ and $B$. The resulting structure is then called the Muchnik degrees (if we ignore the covering $\omega$ condition I guess).

Answer 2

A cover of $\omega$ is a subset $C\subseteq {\mathcal P}(\omega)$ satisfying $\bigcup C=\omega$. For any such $C$, let $\widehat{C}$ be the order ideal (=lower set) that it generates. $A\leq_r B$ iff $\widehat{A}\subseteq \widehat{B}$. Hence the map $C\mapsto \widehat{C}$ is an order preserving and reflecting map of the poset $\frak{C}$ to the lattice of order ideals of ${\mathcal P}(\omega)$. The kernel of the map is the relation $\simeq_r$.

There is a least element in the image of this map, which is the order ideal of ${\mathcal P}(\omega)$ generated by the singletons. Also, the image is closed upward in the lattice of order ideals of ${\mathcal P}(\omega)$. This shows that $\frak{C}$ is isomorphic to a principal filter of the lattice of order ideals of ${\mathcal P}(\omega)$.

The advantage from passing from covers to the order ideals they generate is that the order becomes containment and the lattice operations become union and intersection. This makes it clear that the resulting lattice is a complete (in fact algebraic) distributive lattice.