0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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