# Showing that well-ordered subsets of $P(\omega)$ are countable

I have the following problem:

Show that no uncountable subset of $P(\omega)$ is well-ordered by the inclusion relation.

I think they want me to do by embedding it in a separable complete dense linear order (like $\mathbb{R}$), which I have already proved cannot have any uncountable well-ordered subset.

Any hints or ideas are welcome.

-

## 2 Answers

Say $X$ is a well-ordered subset of $P(\omega)$. For each $x \in X$ which is not the biggest element of $X$, let $y$ be the smallest amongst the elements of $X$ which are strictly bigger than $x$, and choose $f(x) \in y \setminus x$. That way you get an injective ($x$ is the biggest element of $X$ not containing $f(x)$) map from $X$ (possibly minus one element) to $\omega$, which is countable.

-

I assume by "inclusion" that you mean the relation A ⊆ B.

Consider a well-ordered subset σ ⊆ P(ω). Clearly, with respect to inclusion, σ has some ordinal type; the question is whether this type is countable. For any a,b ∈ σ such that a ⊂ b, we have |b \ a| ≥ 1. Thus, the cardinality of V = [ ∪ σ ] ⊆ ω is at least that of the order type of σ, and at most that of ω.

-