Successor Set of Transitive Set is Transitive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a transitive set.

Then its successor set $S^+ = S \cup \set S$ is also transitive.


Proof

Recall that $S$ is transitive if and only if:

$x \in S \implies x \subseteq S$

Hence:

\(\ds \forall x \in S^+: \, \) \(\ds x\) \(\in\) \(\ds S\)
\(\, \ds \lor \, \) \(\ds x\) \(=\) \(\ds S\)
\(\ds \leadsto \ \ \) \(\ds x\) \(\subseteq\) \(\ds S\) Definition of Transitive Set: $x \in S \implies x \subseteq S$
\(\, \ds \lor \, \) \(\ds x\) \(\subseteq\) \(\ds S\) Set is Subset of Itself: $x = S \implies x \subseteq S$
\(\ds \leadsto \ \ \) \(\ds x\) \(\subseteq\) \(\ds S\) Proof by Cases: both $x \in S$ and $x = S$ lead to $x \subseteq S$

Then:

\(\ds \forall S: \, \) \(\ds S\) \(\subseteq\) \(\ds S^+\) Set is Subset of Union
\(\ds \leadsto \ \ \) \(\ds x\) \(\subseteq\) \(\ds S^+\)


Thus we have:

$x \in S \implies x \subseteq S$

Hence the result.

$\blacksquare$


Sources