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

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {\prec, A}$ 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: \paren {x \prec y \implies x \in B}$.

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 \O$

Then:

\(\ds A \setminus B\) \(\ne\) \(\ds \O\)
\(\ds \leadsto \ \ \) \(\ds \exists x \in A \setminus B: \, \) \(\ds \paren {A \setminus B} \cap A_x\) \(=\) \(\ds \O\) Proper Well-Ordering Determines Smallest Elements
\(\ds \leadsto \ \ \) \(\ds \exists x \in A \setminus B: \, \) \(\ds A \cap A_x\) \(\subseteq\) \(\ds B\) Set Difference with Superset is Empty Set

One direction of inclusion is proven.


By the hypothesis:

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

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

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

Therefore:

$B \subseteq A_x$

and so

$B \subseteq A \cap A_x$

$\blacksquare$


Sources