Union of Initial Segments is Initial Segment or All of Woset

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({X, \preccurlyeq}\right)$ be a well-ordered non-empty set.

Let $A \subseteq X$.

Let:

$\displaystyle 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 the 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 Subsets is Subset: Family of Sets, 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 = \left\{{b \in S: b \prec a}\right\}$, which by Axiom of Extension is equivalent to the claim that $z \in J \iff z \prec a$ for every $z \in X$.


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$, i.e. $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, so $a \in J$ by definition of 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$, so $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$

Sources