# Is $({\cal P}(\omega), \leq_{\text{inj}})$ a distributive lattice?

For $A, B \subseteq \omega$ we set $A \leq_{\text{inj}} B$ if there is an injective and order-preserving map $f:\omega\to \omega$ , such that $f(A)$ is a down-set of $B$. It is easy to see that $\leq_{\text{inj}}$ is an ordering relation on ${\cal P}(\omega)$.

Is $({\cal P}(\omega), \leq_{\text{inj}})$ a lattice? Is it distributive?

• What exactly do you mean by a down-set of $B$? At least three readings come to mind: (1) a subset $D$ of $B$ with $b\in B\ \&\ d\in D\ \&\ b<d$ implying $b\in D$; (2) a subset $D$ of $\omega$ with $d\in D$ implying existence of $b\in B$ with $d\leqslant b$; or (3) same as (2) and in addition $n\in\omega\ \&\ n<d\ \&\ d\in D$ implying $n\in D$. – მამუკა ჯიბლაძე Oct 25 '17 at 7:28

Let $$A=\{a_0<a_0+a_1<a_0+a_1+a_2<\dots\},\qquad B=\{b_0<b_0+b_1<\dots\},$$ so that the $a_i$ and $b_i$ are the gaps in $A$ and $B$. Then $A\le_{\mathrm{inj}}B$ iff $a_i\le b_i$ for each $i$. Thus $(\mathcal P(\omega),\le_{\mathrm{inj}})$ is indeed a distributive lattice, isomorphic to $\omega^\omega$ with the product order.
• Brilliant -- and thanks for the link to $\omega^\omega$! – Dominic van der Zypen Oct 25 '17 at 6:00
• Oh -- I just forgot about them...! So you get $\omega^\omega$ "with some countable stuff below"? – Dominic van der Zypen Oct 25 '17 at 6:04
• Yes, I think we can say finite sets have $a_i=-\infty$ for large $i$. So for instance $A=\emptyset$ has $a_i=-\infty$ for all $i$, and $A=\{0\}$ has $a_0=0$, $a_i=-\infty$ for $i>0$. – Bjørn Kjos-Hanssen Oct 25 '17 at 6:28