Transitive Set is Proper Subset of Ordinal iff Element of Ordinal

From ProofWiki
Jump to navigation Jump to search


Let $A$ be an ordinal.

Let $B$ be a transitive set.


$B \subsetneq A \iff B \in A$


Let $A$ and $B$ be ordinals.


$A \subsetneq B \iff A \in B$


Necessary Condition

Suppose that $B \in A$.

From Ordinal is Transitive, it follows that $B \subseteq A$.

Also, $B \ne A$ by Ordinal is not Element of Itself.

Therefore, $B \subsetneq A$, as desired.


Sufficient Condition

Suppose that $B \subsetneq A$.

By the definition of set equality, the set difference $A \setminus B$ is non-empty.

By the definition of a strict well-ordering, there exists a minimal element $x$ of $A \setminus B$.

As $x \in A$, it follows from Ordinal is Transitive that $x \subseteq A$.

Next, since the strict well-ordering on $A$ is given by the epsilon restriction $\Epsilon \! \restriction_A$, it follows by the definition of a minimal element that:

$\forall y \in A \setminus B: y \notin x$


\(\ds \O\) \(=\) \(\ds \paren {A \setminus B} \cap x\)
\(\ds \) \(=\) \(\ds \paren {A \cap x} \setminus B\) Intersection with Set Difference is Set Difference with Intersection
\(\ds \) \(=\) \(\ds x \setminus B\) Intersection with Subset is Subset
\(\ds \leadsto \ \ \) \(\ds x\) \(\subseteq\) \(\ds B\) by Set Difference with Superset is Empty Set

Suppose that $z \in B$.

Since $B \subset A$, it follows that $z \in A$.

Recall that the strict well-ordering on $A$ is given by the epsilon restriction $\Epsilon \! \restriction_A$.

From the Trichotomy Law (Ordering), it follows that $z \in x$ or $x = z$ or $x \in z$.

If $x = z$ or $x \in z$, then it follows by the transitivity of $B$ that $x \in B$.

This contradicts the definition of $x$.

Hence, $z \in x$.

That is, $B \subseteq x$.

We have shown that $x \subseteq B$ and $B \subseteq x$.

By definition of set equality:

$B = x \in A$


Also see