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

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?

-

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$.

-
Thank you. What does equipotent mean? – Bartek Jun 11 '13 at 19:33
Having the same cardinality, i.e. there exists a bijection between them. – Henning Makholm Jun 11 '13 at 19:34
Oh, thanks. I'd only known the term "equinumerous". – Bartek Jun 11 '13 at 19:35

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.

-
Thank you. I don't understand the first proof. In $\mathcal C$, the order is inclusion, right? In binary terms, $X\leq Y$ when $Y$ has all the ones that $X$ has, and maybe more. But when we pass to $\Bbb R$ (or rather $[0,1)$), the binary sequences are compared in a different way, aren't they? We have $0.0100\ldots\leq0.1000\ldots,$ but $\{2\}\not\subseteq\{1\}...$ – Bartek Jun 11 '13 at 21:32
Thank you, I understand. It's very nice; I wonder why I've never seen it. – Bartek Jun 11 '13 at 21:52

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.

-
Since $\omega$ is in bijection with $\mathbb Q$, the set of Dedekind cuts corresponds to an uncountable chain in $\mathcal P(\omega)$ ordered by inclusion. (It's not a well-ordered chain and so doesn't embed an uncountable ordinal, but it's still a counterexample to your argument in the second paragraph). – Henning Makholm Jun 11 '13 at 18:46
Thank you. I understand the first paragraph, but not the second one. I mean I understand of course that the embedding would give an uncountable chain, but I don't see why a countable set can't have an uncountable chain of subsets. It can have an uncountable linearly ordered family of subsets ($\Bbb R\subseteq 2^{\Bbb Q}$), and, in particular, I would like to understand why adding the minimum principle to what we require of the family makes the existence impossible. – Bartek Jun 11 '13 at 18:47
@Henning Oh, we posted the same thing. :) I'll ask another question about this example because something is bothering me in it. – Bartek Jun 11 '13 at 18:48