5
$\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)$. (This is different from the lexicographic ordering discussed in another post.)

Let us compare the two posets $({\cal P}(\omega), \subseteq)$ and $({\cal P}(\omega), \leq_{\text{inj}})$: Are there surjective order-preserving maps between them, in either direction?

EDITED: Where down-set is printed above, I had the weaker (and confusing) condition $f(A)\subseteq B$ which doesn't make sense, as Andreas Blass pointed out.

$\endgroup$
4
  • $\begingroup$ Dominic, Andreas Blass points out that every infinite subset is $\leq_{inj}$ every other infinite subset. Surely you meant what I read it as, with $f(A) = B$, not $f(A) \subseteq B$? $\endgroup$
    – Nik Weaver
    Oct 24, 2017 at 1:10
  • $\begingroup$ I want $f(A)$ to be a down-set inside $B$... does that make any sense, and I'm still not 100% sure the resulting relation is anti-symmetric (pretty sure though, for what it's worth) $\endgroup$ Oct 24, 2017 at 8:12
  • $\begingroup$ Oh, good. So if $A$ and $B$ are both infinite, that is the same as $A=B$ and thus the order is as I described. So I think my solution is still correct. $\endgroup$
    – Nik Weaver
    Oct 24, 2017 at 11:24
  • $\begingroup$ Right - now that I had a look at it again, I agree! I'll accept it $\endgroup$ Oct 24, 2017 at 12:32

1 Answer 1

5
$\begingroup$

Yes there is a surjective order-preserving map from $\leq_{inj}$ to $\subseteq$, no in the reverse direction.

If you restrict the $\leq_{inj}$ order to the family of all infinite subsets of $\omega$ the result is isomorphic to the set of all functions from $\omega$ to $\omega$ with the coordinatewise order ($f \leq g$ if $f(n) \leq g(n)$ for all $n$). Namely, if $(a_n)$ is an infinite subset of $\omega$ given in increasing order, map it to the sequence $(a_{n+1} - a_n - 1)$. I.e. map an infinite set to the sequence of gaps.

It's easy to see that there is an order-preserving surjection from this space to $\mathcal{P}(\omega)$. (Identify the latter with the set of functions from $\omega$ to ${0,1}$.) Any finite subset corresponds to a function from an initial segment of $\omega$ to $\omega$; fill it out with a sequence of zeros and map it to the image of that sequence. That gives you one direction.

For the nonexistence of a map with the desired properties in the other direction, just note that the standard order had a greatest element (namely, $\omega$) but the inj order does not. So any map has to take $\omega$ somewhere and then nothing could consistently map to any greater element.

$\endgroup$
3
  • 1
    $\begingroup$ Maybe I'm just confused, but it seems to me that your isomorphism between $\leq_{\text{inj}}$ and the coordinatewise order on functions $\omega\to\omega$ involves $\leq_{\text{inj}}$ defined as "there is an injective order-preserving $f:\omega\to\omega$ with $f(A)=B$", whereas the definition in the question ends with $f(A)\subseteq B$. With the $\subseteq$ version of the definition, it seems that every subset of $\omega$ is $\leq_{\text{inj}}$ every infinite subset of $\omega$. $\endgroup$ Oct 23, 2017 at 22:28
  • $\begingroup$ Comments that begin "Maybe I'm just confused" are the most dangerous ones, aren't they? Well, you are right, I totally misread the question. Though I wonder if the definition I used was actually the intended one, since otherwise the problem is trivial. $\endgroup$
    – Nik Weaver
    Oct 24, 2017 at 1:09
  • $\begingroup$ Right - sorry for the buggy definition! That's a nuisance if the OP doesn't get it right -- I apologise $\endgroup$ Oct 24, 2017 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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