Proper Well-Ordering determines Smallest Elements

From ProofWiki
Jump to navigation Jump to search


Theorem

Let $S$ be a class.

Let $\preceq$ be a proper well-ordering on $S$.

Let $B$ be a nonempty subclass of $S$.


Then $B$ has a $\preceq$-smallest element.


Proof

Because $B \ne \varnothing$ it follows that $B$ has an element $x$.

If $x$ is the smallest element of $B$ then the theorem holds.

Otherwise, there is an element $y \in B$ such that $x \npreceq y$.

By Well-Ordering is Total Ordering, $y \prec x$.

Thus $S_x$, the $\preceq$-initial segment of $x$, is not empty.

By the hypothesis, $S_x$ is a set.

By Intersection is Subset, $B \cap S_x \subseteq S_x$

Thus by the subset axiom, $B \cap S_x$ is a set.

Thus by the definition of proper well-ordering, $B \cap S_x$ has a smallest element $a$.

Let $z$ be any element of $B$.

Suppose for the sake of contradiction that $z \prec a$.

Then by Extended Transitivity, $z \prec x$, so $z \in B \cap S_x$.

But this contradicts the fact that $a$ is the smallest element of $B \cap S_x$.

Thus $z \nprec a$.

Since $\preceq$ is a total ordering, $a \preceq z$.

As this holds for all $z \in B$, $a$ is the smallest element of $B$.

$\blacksquare$


Sources