Well-Ordered Transitive Subset is Equal or Equal to Initial Segment
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
- 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory: $\S 7.45$