In Halmos's Naive Set Theory about well-ordering set, it states that if a collecton $\mathbb{C}$ of well-ordered set is a chain w.r.t continuation, then the union of these sets is a well-ordered set. However, I can't why it is well-ordered, i.e. I can'n see any subset of it has a smallest element.


You have to re-read all the passage from page 67-on :

We shall say that a well ordered set $A$ is a continuation of a well ordered set $B$, if, in the first place, $B$ is a subset of $A$, if, in fact, $B$ is an initial segment of $A$, and if, finally, the ordering of the elements in $B$ is the same as their ordering in $A$.

Thus if $X$ is a well ordered set and if $a$ and $b$ are elements of $X$ with $b < a$, then $s(a)$ is a continuation of $s(b)$, and, of course, $X$ is a continuation of both $s(a)$ and $s(b)$.

If $\mathcal C$ is an arbitrary collection of initial segments of a well ordered set, then $\mathcal C$ is a chain [see page 54 : "a totally ordered set"] with respect to continuation; this means that $\mathcal C$ is a collection of well ordered sets with the property that of any two distinct members of the collection one is a continuation of the other.

A sort of converse of this comment is also true and is frequently useful. If a collection $\mathcal C$ of well ordered sets is a chain with respect to continuation, and if $U$ is the union of the sets of $\mathcal C$, then there is a unique well ordering of $U$ such that $U$ is a continuation of each set (distinct from $U$ itself) in the collection $\mathcal C$.

Roughly speaking, the union of a chain of well ordered sets is well ordered. This abbreviated formulation is dangerous because it does not explain that "chain" is meant with respect to continuation. If the ordering implied by the word "chain" is taken to be simply order-preserving inclusion, then the conclusion is not valid.

The relevant fact is : the collection $\mathcal C$ of well-ordered set is a chain w.r.t continuation.

A collection $\mathcal C$ is a chain when, for all $A,B \in \mathcal C$ : $A \subseteq B$ or $B \subseteq A$.

If a collection $\mathcal C$ is a chain w.r.t continuation, it has "something more" : in addition to the property (common to all chains) that for all $A,B \in \mathcal C$ : $A \subseteq B$ or $B \subseteq A$, we have also that (supposing : $B \subseteq A$) $B$ is an initial segment of $A$, and the ordering of the elements in $B$ is the same as their ordering in $A$.

Thus, when we "merge" all the members of the collection $\mathcal C$ into the "mega-set" $U$ every subset "preserve" its "original" minimal-element.

I hope it may help ...

I'm not able to "manufacture" an example different from the "trivial" one built from $\mathbb N$.

If you consider a collection $\mathcal C = \{ X_n \}$ where all $X_i$ form a chain w.r.t continuation, we have that $X_n = \{ 0,1,2, \ldots n \} = n+1$.

Thus the union $U$ of the collection is $\omega$ itself.

  • $\begingroup$ I still have no idea from your answer,my question is why the subset of $U$ has smallest element $\endgroup$ – 89085731 Jun 30 '14 at 7:40
  • $\begingroup$ @89085731: Perhaps it would be wise to have the definition of "chain with respect to continuation" open in front of you, so you can refer to it when needed (e.g. now). $\endgroup$ – Asaf Karagila Jun 30 '14 at 7:42

Note that in general, the union of a $\subseteq$-chain of well-ordered sets is not necessarily a well-ordered set. For example, write $\Bbb Q$ as $\{q_n\mid n\in\Bbb N\}$, then it is the increasing union of $Q_n=\{q_i\mid i<n\}$, with the linear order induced by $\Bbb Q$. Then $\{Q_n\mid n\in\Bbb N\}$ is a chain of well-ordered sets whose union is the furthest thing from a well-ordered set.

But here we require more. We require that this is not a chain in the inclusion relation, but rather in the continuation relation. So as you progress along the chain, you don't add new information "below" information that you already had.

What do I mean by that? Note that in the case of the $Q_n$'s at some point you have added an element which lies below $q_0$ in the order of the rational numbers; later on you have added an element which lies between $q_0$ and $q_1$, and so on and so forth.

If that would have been a continuation relation, then whenever $m<n$ and $a,b\in Q_m$, and $c\in Q_n$ such that $a<c<b$ then it is necessarily the case that $c\in Q_m$.

So why is the union of such a chain well-ordered? Well, if $U$ is a non-empty set, then it is necessarily the case that it meets one of the ordered sets in the chain on a non-empty set. That non-empty intersection has a least element $u$. Here we use the continuation of the orders, and we conclude that it was impossible that $U$ has elements below $u$.

(I have given you an outline, but you should sit down and work out the details yourself.)

  • $\begingroup$ In the last line, you meant that $U$ cannot have elements below $u$, right? $\endgroup$ – Mad Hatter Nov 7 '16 at 8:57
  • $\begingroup$ Yes, of course. Thank you. $\endgroup$ – Asaf Karagila Nov 7 '16 at 9:33
  • $\begingroup$ I can't understand the sets in the example, would you please explain them to me. I'm trying to understand it literally, so $\Bbb Q$ is just an arbitrary symbol that you introduce for some set, and you construct it as $\{q_n\mid n\in\Bbb N\}$, so it is exactly $\{q_0, q_1, q_2, ...\}$ where each of $q_n \text{for } n \in \Bbb N$ stands for just some object. Then $Q_0 = \varnothing, Q_1 = \{q_0\}, Q_2 = \{q_0, q_1\}, \dots$ Then the collection $\{Q_n \mid n \in \Bbb N\}$ is a $\subseteq$-chain, but from what follows in your answer, I think you meant something else. $\endgroup$ – Andrey Surovtsev Jul 16 at 12:01
  • $\begingroup$ I tried to understand it as some sets constructed from rational numbers but I failed, that's why I have put such a literal interpretation here. $\endgroup$ – Andrey Surovtsev Jul 16 at 12:02
  • 1
    $\begingroup$ @AndreySurovtsev: No, it is the set of all rational numbers. $\endgroup$ – Asaf Karagila Jul 16 at 12:31

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.