Union of Initial Segments is Initial Segment or All of Woset/Proof 2
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
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$