Union of Initial Segments is Initial Segment or All of Woset
Theorem
Let $\struct {X, \preccurlyeq}$ be a well-ordered non-empty set.
Let $A \subseteq X$.
Let:
- $\ds J = \bigcup_{x \mathop \in A} S_x$
be a union of initial segments defined by the elements of $A$.
Then either:
- $J = X$
or:
- $J$ is an initial segment of $X$.
Proof 1
Suppose the hypotheses of the theorem hold.
If $J = X$ then the theorem is satisfied.
Assume $J \ne X$.
Then $X \setminus J$ is non-empty.
By Subset of Well-Ordered Set is Well-Ordered, $X \setminus J$ is itself well-ordered.
Thus $X \setminus J$ has a smallest element; call it $b$.
We claim that $b \preccurlyeq y$ for every $y \in J$.
Aiming for a contradiction, suppose there exists a $y \in J$ with $b \preccurlyeq y$.
Then there exists some $x_0 \in A$ with $y$ in the initial segment $S_{x_0}$.
Thus $b \in S_{x_0}$ and so $b \in J$.
This contradicts the fact that $b \in X \setminus J$.
Thus there cannot exist a $y \in J$ with $b \preccurlyeq y$.
Any element strictly preceding $b$ is in $J$, by choice of $b$.
Also, $b \notin J$, because $b \in X \setminus J$.
From above, any element strictly succeeding $b$ is not in $J$.
Thus $J = S_b$ by definition of initial segment.
$\blacksquare$
Proof 2
Suppose the hypotheses of the theorem hold.
For every $x \in A$, we have $S_x \subseteq X$ by the definition of initial segment.
By Union of Family of Subsets is Subset, we have $J \subseteq X$.
Consider $X \setminus J$.
If $X \setminus J$ is empty, then $X \subseteq J$ by Set Difference with Superset is Empty Set, and hence $J = X$ by Subset Relation is Antisymmetric, so the theorem is satisfied.
So assume $X \setminus J$ is non-empty.
By Subset of Well-Ordered Set is Well-Ordered, $X \setminus J$ is itself well-ordered.
Thus $X \setminus J$ has a smallest element; call it $a$.
We will show that $J = S_a$, thus showing the veracity of the theorem.
We need to show that:
- $J = \set {b \in S: b \prec a}$
which by definition of set equality is equivalent to the claim that:
- $\forall z \in X: \in J \iff z \prec a$
For the forward direction, suppose $z \in J$.
We need to show that $z \prec a$.
By definition of union, there is $x \in A$ such that $z \in S_x$, that is:
- $z \prec x$
Aiming for a contradiction, suppose $a \preceq z$.
Then $a \prec x$, so $a \in S_x$ by the definition of initial segment
Hence $a \in J$ by definition of union.
This contradicts the fact that $a \in X \setminus J$.
Thus $z \prec a$.
For the backward direction, suppose $z \prec a$ where $z \in X$. We need to show that $z \in J$
Aiming for a contradiction, suppose $z \notin J$.
Then $z \in X \setminus J$.
Hence $a \preceq z$ by definition of smallest element.
This contradicts the fact that $z \prec a$.
Thus $z \in J$.
Since $z$ was arbitrary, we conclude that $J = S_a$ as required.
$\blacksquare$