Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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