6
$\begingroup$

The motivation for this question is the startling fact that there is an order-preserving injective map (embedding) from $\mathbb{R}$ into ${\cal P}(\omega)$. (Think Dedekind cuts.) I am wondering how "large" a linear order can become and still be embeddable in ${\cal P}(\omega)$. To be able to formalize this, I would like to focus on well-orders.

Question. What is the smallest ordinal $\mu$ such that there is no injective order-preserving map $\varphi:\mu\to{\cal P}(\omega)$?

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ For an order-preserving injective map from $\mathcal P(\omega)$ into $\mathbb R$ think $X\mapsto\sum_{x\in X}3^{-x}$. $\endgroup$
    – bof
    Commented Feb 9, 2023 at 3:39

1 Answer 1

Reset to default
12
$\begingroup$

This is just $\omega_1$. The naive argument ("pick the least new thing") that no uncountable linear order embeds into $\mathcal{P}(\omega)$ actually establishes that no uncountable well-order embeds into $\mathcal{P}(\omega)$: if $f$ is an injection of an ordinal $\theta$ into $\mathcal{P}(\omega)$, the map $$\hat{f}:\theta\rightarrow \omega: \alpha\mapsto\min(f(\alpha+1)\setminus f(\alpha))$$ is an injection of $\theta$ into $\omega$. This doesn't contradict the injectibility of $\mathbb{R}$, since there is no injection from $\omega_1$ into $\mathbb{R}$ either.

(Interestingly, if we order $\mathcal{P}(\omega)$ by mod-finite containment instead of genuine containment, we can indeed inject $\omega_1$.)

EDIT: As bof pointed out below, we can improve the above drastically: there is an order preserving (but not reflecting of course) injection $\mathcal{P}(\omega)\rightarrow\mathbb{R}$, so the linear orders embeddable in $\mathcal{P}(\omega)$ are exactly those embeddable in $\mathbb{R}$. Of course that still leaves plenty of open questions (e.g. are any two $\aleph_1$-dense suborders of $\mathbb{R}$ order-isomorphic?) but I think it lets us stop thinking about $\mathcal{P}(\omega)$ as such.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ Also, since there are order-preserving maps ($x\lt y\implies f(x)\lt f(y)$) in both directions, $\mathbb R\to\mathcal P(\omega)$ and $\mathcal P(\omega)\to\mathbb R$, the linear orders embeddable in $\mathcal P(\omega)$ are just the same as the linear orders embeddable in $\mathbb R$. $\endgroup$
    – bof
    Commented Feb 9, 2023 at 3:35
  • $\begingroup$ @bof Good point, added! $\endgroup$
    – Noah Schweber
    Commented Feb 9, 2023 at 3:46
  • $\begingroup$ What does "reflecting" mean? And what's the significance of injectivity here? Non-injective order-preserving maps would be just as good here, right? $\endgroup$
    – bof
    Commented Feb 10, 2023 at 1:40
  • 1
    $\begingroup$ @bof "reflecting" is just the dual of "preserving" - $f(a)\le f(b)\rightarrow a\le b$. Meanwhile, I used injections because then it doesn't matter whether you're using "order-preserving" in the strict or weak sense. $\endgroup$
    – Noah Schweber
    Commented Feb 10, 2023 at 2:54
  • 1
    $\begingroup$ About the question of isomorphic $\aleph_1$-dense subsets, Sierpinski showed that it is possible that there exists $2^{\aleph_0}$-isomorphism classes of $\aleph_1$-dense subsets of reals (Sierpinski assumed CH, but one should get similar result with the failure of CH by adding Cohen reals), on the other hand Baumgartner showed that PFA implies that all $\aleph_1$-dense subsets of real are isomorphic $\endgroup$
    – Holo
    Commented Feb 20, 2023 at 14:39

You must log in to answer this question.

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