Let $\mathcal A$ be a family of infinite countable sets which is linearly ordered by inclusion and such that $\bigcup\mathcal A$ is uncountable. I have to prove that $|\bigcup\mathcal A|=\aleph_1.$

I think I can prove it when $\mathcal A$ is well ordered. Let $\kappa=\mathrm{type}(\mathcal A).$ Then we can index $\mathcal A$ with ordinal numbers $\iota<\kappa:$ $\mathcal A=\{A_\iota\}_{\iota<\kappa}.$ If $\kappa>\aleph_1,$ then there is $A_{\aleph_1}.$ But this is the union of all $A_\iota$ over $\iota<\aleph_1$. Since $A_\iota$ are pairwise distinct, $A_{\aleph_1}$ must be an uncountable set, a contradiction with $A_{\aleph_1}\in\mathcal A.$ Therefore the ordinal type of $\mathcal A$ is at most $\aleph_1.$ But if it were less than that, then $\bigcup\mathcal A$ wouldn't be uncountable.

But I can't see how I can do it for a linearly ordered $\mathcal A.$ Is there some kind of classification for linear orders like the one that ordinal numbers provide for well-orders? (Please, even if it's irrelevant, do answer this question, or tell me that I should ask it separately.)


Your idea of looking at well-ordered sets is the key. It is true that $\mathcal A$ needs not be well-ordered, but its cofinality is well-defined anyway.

Here, the cofinality of $\mathcal A$ is simply the least ordinal $\alpha$ such that there is a strictly increasing sequence of length $\alpha$ of elements of $\mathcal A$ that is cofinal in $\mathcal A$, that is, a sequence $\langle A_\beta\mid \beta<\alpha\rangle$ such that each $A_\beta\in\mathcal A$, if $\beta<\gamma<\alpha$, then $A_\beta\subset A_\gamma$, and for any $A\in\mathcal A$, we have $A\subset A_\beta$ for some $\beta<\alpha$ (and $\alpha$ is least possible).

Now note that this $\alpha$ is a cardinal, at most $\aleph_1$ (it could be $1$), and that $\bigcup A=\bigcup_{\beta<\alpha}A_\beta$, and the problem reduces to the well-ordered case.

In fact, we do not even need to talk of cofinalities here, all that matters is that there is such a sequence $\langle A_\beta\mid\beta<\alpha\rangle$, regardless of whether $\alpha$ is least or not. Now of course $\alpha$ is not necessarily a cardinal, but still $\alpha\le\aleph_1$, which is all that is needed.

| cite | improve this answer | |
  • $\begingroup$ Thank you. To show that there is such a sequence, do I need to use transfinite induction? I'm thinking I could define the sequence recursively and get one, but I think what I'm getting is exactly the shortest one, and you say it's simpler than that. I would prefer to use the simpler way because I'm not very comfortable with transfinite induction yet. $\endgroup$ – Bartek Mar 26 '13 at 21:22
  • $\begingroup$ Either way you would need transfinite recursion, but the argument is rather natural: Pick a point in $\mathcal A$. Are there points in $\mathcal A$ larger than it? If not, you are done. If so, pick one, and keep going. At limit stages, is the sequence you have so far cofinal? If so, you are done. If not, pick a point larger than all of the points in the sequence, and continue. $\endgroup$ – Andrés E. Caicedo Mar 26 '13 at 21:27
  • $\begingroup$ This is what I was thinking and I thought that gave me the shortest one, but now I'm not sure I understand linear orders well enough to say that. Does it? $\endgroup$ – Bartek Mar 26 '13 at 21:35
  • $\begingroup$ @AndresCaicedo: That sounds like a job for Zorn's lemma. (The result is not provable without some kind of choice principle anyway). $\endgroup$ – hmakholm left over Monica Mar 26 '13 at 21:43
  • $\begingroup$ @Henning Could you elaborate? Is your idea that such a cofinal sequence is in a sense the longest possible so it should be a maximal element of something? But what family do I need of to consider and with what order? $\endgroup$ – Bartek Mar 26 '13 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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