Which ordinals embed in $2^\omega$ ordered by inclusion?

Question

Which ordinals can be embedded in the power set of $\omega$ ordered by inclusion?

I see that $\omega\cdot\omega$ can (and therefore anything less than that): we can partition $\omega$ into $\omega$ countably infinite subsets $\{A_i\}_{i\in\omega}$, $A_i\cap A_j=\varnothing$ for $i\neq j$, $A_i\subseteq\omega$, $|A_i|=\aleph_0$.

We can endow each $A_i$ with a well-order $\leq_i$ of type $\omega$. Let $f_i:\omega\to A_i$ be a bijection and $\leq_i$ be the well-order on $A_i$ induced by it. We can denote $a_{i,j}:=f_i(j).$

We can define the family

• $B_{0,0}=\{a_{0,0}\},$
• $B_{m,n+1}=B_{m,n}\cup\{a_{m,n+1}\}$ for $m,n\in\omega,$
• $B_{m+1,0}=\bigcup_{k\in\omega} B_{m,k}$ for $m\in\omega$.

This family ordered by inclusion is, if I'm not mistaken, naturally isomorphic to $\omega\cdot\omega.$

I think by partitioning the partition, we can obtain $\omega^3$. I'm sure that we can find much larger countable ordinals in $(2^\omega,\subseteq)$, but I don't see how far we can go. Is every countable ordinal embeddable in this poset? Do any uncountable ordinals embed?

Answer 1

To fix Miha's argument: You can't order-embed any uncountable ordinal into $(\mathcal P(\omega),{\subseteq})$.

Suppose that $\beta$ is an ordinal that can be embedded into $\mathcal P(\omega)$. We can assume wlog that $\beta$ is not a successor ordinal, because every infinite successor ordinal is equipotent to a prefix of itself that is a limit ordinal.

Then for every $\alpha\in\beta$ the image of $\alpha+1$ must contain some member of $\omega$ that is not in the image of $\alpha$. If for each $\alpha$ we take the least such natural, this creates a bijection between $\beta$ and some subset of $\omega$ -- thus $\beta$ is at most countable.

This argument holds for any infinite (well-orderable) cardinality in place of $\omega$.

Answer 2

Let $\alpha$ be a countable ordinal and fix a bijection $f\colon\alpha\to\omega$. Then define $g\colon \alpha\to 2^\omega$ by $g(\beta)=f[\beta]$. This is easily shown to be an embedding of $\alpha$ into $2^\omega$.

Edit: Henning Makholm pointed out in the comments that my argument that uncountable ordinals don't embed into $2^\omega$ was wrong. His answer fixes my proof.

Answer 3

You could as well have asked which linear order types embed into $2^\omega$, it's just as easy to answer.

Proposition 1. A linear order is embeddable in $2^\omega$ if and only if it's embeddable in $R$.

Proof. If $\mathcal C$ is a linearly ordered subset of $2^\omega$, then $X\mapsto\sum\{2^{-n}:n\in X\}$ embeds $\mathcal C$ into $\mathbb R$. On the other hand, $x\mapsto\{r\in\mathbb Q:r<x\}$ embeds $\mathbb R$ into $2^{\mathbb Q}$ which is isomorphic to $2^\omega$.

Proposition 2. Every countable linear order is embeddable in $\mathbb R$ and therefore in $2^\omega$.

(Actually, by a famous theorem of Cantor, every countable linear order is embeddable in $\mathbb Q$, but that's a little harder to prove.)

Proof. Suppose $(L,<)$ is a countable linearly ordered set. Choose an injection $f:L\rightarrow\mathbb N$. Then $x\mapsto\sum\{2^{-f(y)}:y<x\}$ embeds $(L,<)$ into $\mathbb R$.

Proposition 3. An uncountable ordinal is embeddable neither in $\mathbb R$ nor in $2^\omega$.

Proof. It's enough to show that the ordinal $\omega_1$ is not embeddable in $\mathbb R$. Assume for a contradiction that $f:\omega_1\rightarrow\mathbb R$ is order-preserving. For each $\alpha\in\omega_1$ choose a rational number $g(\alpha)$ so that $f(\alpha)<g(\alpha)<f(\alpha+1)$. Then $g:\omega_1\rightarrow\mathbb Q$ is an injection, which is impossible.