Transitive Set is Proper Subset of Ordinal iff Element of Ordinal

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$ be an ordinal.

Let $B$ be a transitive set.


Then:

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


Corollary

Let $A$ and $B$ be ordinals.


Then:

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


Proof

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.

$\Box$


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$

Therefore:

\(\displaystyle \O\) \(=\) \(\displaystyle \paren {A \setminus B} \cap x\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {A \cap x} \setminus B\) Intersection with Set Difference is Set Difference with Intersection
\(\displaystyle \) \(=\) \(\displaystyle x \setminus B\) Intersection with Subset is Subset
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\subseteq\) \(\displaystyle 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$

$\blacksquare$


Also see


Sources