Finite Non-Empty Subset of Ordered Set has Maximal and Minimal Elements/Corollary
< Finite Non-Empty Subset of Ordered Set has Maximal and Minimal Elements(Redirected from Element of Finite Ordered Set is Between Maximal and Minimal Elements)
Jump to navigation
Jump to search
Theorem
Let $\struct {S, \preceq}$ be a finite ordered set.
Let $x \in S$.
Then there exists a maximal element $M \in S$ and a minimal element $m \in S$ such that:
- $m \preceq x \preceq M$
Proof
Let $T = \set{y : x \preceq y}$.
By the reflexivity of the ordering $\preceq$:
- $x \preceq x$
So $x \in T$ and $T$ is non-empty.
From Finite Non-Empty Subset of Ordered Set has Maximal and Minimal Elements:
- $\struct {T, \preceq}$ has a maximal element $M \in T$
We now show that $M$ is a maximal element in $\struct{S, \preceq}$.
Let $y \in S$ such that:
- $M \preceq y$
By the transitiviy of the ordering $\preceq$:
- $x \prec y$
So $y \in T$.
By the definition of a maximal element:
- $y = M$
Similarly for $T' = \set {y : y \preceq x}$:
- $\struct {T', \preceq}$ has a minimal element $m \in T'$
and $m$ is a minimal element in $\struct {S, \preceq}$.
$\blacksquare$