2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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$
    – მამუკა ჯიბლაძე
    Commented Oct 25, 2017 at 7:28

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Brilliant -- and thanks for the link to $\omega^\omega$! $\endgroup$
    – Dominic van der Zypen
    Commented Oct 25, 2017 at 6:00
  • $\begingroup$ Well... also have to say something about the finite sets $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Oct 25, 2017 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
    Commented Oct 25, 2017 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
    Commented Oct 25, 2017 at 6:28
  • $\begingroup$ Brilliant workaround! $\endgroup$
    – Dominic van der Zypen
    Commented Oct 25, 2017 at 8:14

You must log in to answer this question.

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