Well-Ordered Transitive Subset is Equal or Equal to Initial Segment

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({\prec, A}\right)$ be a well-ordered set.

For every $x \in A$, let every $\prec$-initial segment $A_x$ be a set.

Let $B$ be a subclass of $A$ such that

$\forall x \in A: \forall y \in B: \left({x \prec y \implies x \in B}\right)$.

That is, $B$ must be $\prec$-transitive.

Then:

$A = B$

or:

$\exists x \in A: B = A_x$


Proof

Let $A \ne B$.

Then $B \subsetneq A$.

Therefore, by Set Difference with Proper Subset:

$A \setminus B \ne \varnothing$

Then:

\(\displaystyle A \setminus B \ne \varnothing\) \(\implies\) \(\displaystyle \exists x \in \left({A \setminus B}\right): \left({A \setminus B}\right) \cap A_x = \varnothing\) Proper Well-Ordering Determines Smallest Elements
\(\displaystyle \) \(\implies\) \(\displaystyle \exists x \in \left({A \setminus B}\right): \left({A \cap A_x}\right) \subseteq B\) Set Difference with Superset is Empty Set

One direction of inclusion is proven.


By the hypothesis:

\(\displaystyle x \in A \land x \prec y \land y \in B\) \(\implies\) \(\displaystyle x \in B\)

But $x \in A \land x \notin B$, so:

\(\displaystyle y \in B\) \(\implies\) \(\displaystyle \neg x \prec y\) Modus Tollendo Tollens and other propositional manipulations
\(\displaystyle \) \(\implies\) \(\displaystyle y \prec x\) $\prec$ is totally ordered and $y \ne x$

Therefore:

$B \subseteq A_x$

and so $B: \subseteq A \cap A_x$

$\blacksquare$


Sources