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?

  • $\begingroup$ 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$. $\endgroup$ – მამუკა ჯიბლაძე 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.

  • $\begingroup$ Brilliant -- and thanks for the link to $\omega^\omega$! $\endgroup$ – Dominic van der Zypen Oct 25 '17 at 6:00
  • $\begingroup$ Well... also have to say something about the finite sets $\endgroup$ – Bjørn Kjos-Hanssen Oct 25 '17 at 6:01
  • $\begingroup$ Oh -- I just forgot about them...! So you get $\omega^\omega$ "with some countable stuff below"? $\endgroup$ – Dominic van der Zypen Oct 25 '17 at 6:04
  • $\begingroup$ 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$. $\endgroup$ – Bjørn Kjos-Hanssen Oct 25 '17 at 6:28
  • $\begingroup$ Brilliant workaround! $\endgroup$ – Dominic van der Zypen Oct 25 '17 at 8:14

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.