Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $A$ be a countable set equipped with a partial order $\prec$. We all know that there are subsets $C\subset A$ with the property that the order $\prec$ in $C$ is total. In other words, any two elements $a$ and $b$ in $C$ are comparable.

Let $\mathscr{C}$ be the collection of all subsets $C$ of $A$ that are totally ordered.

Question 1: Is it true $A=\displaystyle\bigcup_{C\in\mathscr{C}}C$?

Denote by $\mathscr{D}$ a any subcolection $\mathscr{D}\subset \mathscr{C}$ such that for all $C_1,C_2\in\mathscr{D}$ we have empty intersection $C_1\cap C_2=\emptyset$.

Question 2: There is a subcollection $\mathscr{D}$ as described above such that $A=\displaystyle\bigcup_{C\in\mathscr{D}}C$?

I know these questions seem intuitive but I'd be happy with some demonstration of elementary set theory either by reduction to absurdity or not


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

They answer to the first question is trivially yes, since every singleton is linearly ordered.

Revised to match edited question:

The answer to the second question is also trivially yes: let $\mathscr{D}=\{\{a\}:a\in A\}$.

share|cite|improve this answer
If $\mathscr{D}$ consist of just one singleton were is the contradiction? Can you give an another counter example? – MathOverview Nov 9 '12 at 21:36
@Elias: Suppose that $A=\{0,1\}$ with either of the two possible partial orders, and $\mathscr{D}=\{\{0\}\}$. Clearly $A\ne\biguplus_{C\in\mathscr{D}}$. – Brian M. Scott Nov 9 '12 at 21:40
Sorry it was a mistake of mine. I've edited my question. Thank's. – MathOverview Nov 9 '12 at 21:49
@Elias: I’ve updated my answer to match. – Brian M. Scott Nov 9 '12 at 21:54
@Elias: It’s not always true if you make that further assumption. Remember, the relation of equality is a partial order, so it may be that the only subsets of $A$ that are linearly ordered are the singletons. – Brian M. Scott Nov 9 '12 at 22:18

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.