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

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.

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

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.

share|cite|improve this answer

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

share|cite|improve this answer

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.