Characterization of Minimal Element

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $C$ be a class.

Let $\prec$ be a relation on $C$.

Let $B$ be a subclass of $C$.

Let $x \in B$.

Let $S_x = \left\{ {y \in C: y \prec x \text{ and } y \ne x}\right\}$ be the initial segment of $x$ in $C$.

Then $x$ is a minimal element of $B$ if and only if $B \cap S_x = \varnothing$.


Proof

Necessary Condition

Suppose $x$ is a minimal element of $B$.

Then for each $z \in B$ such that $z \ne x$, $z \not \prec x$.

Thus $S_x \cap B = \varnothing$.

$\Box$


Sufficient Condition

Suppose that $x$ is not a minimal element of $B$.

Then for some $z \in B$, $z \prec x$ and $z \ne x$.

Thus $z \in S_x$.

Since $z \in B$, $B \cap S_x \ne \varnothing$.

$\blacksquare$