Finite Non-Empty Subset of Ordered Set has Maximal and Minimal Elements

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S, \preceq}\right)$ be an ordered set.

Let $T \subseteq S$ be a finite, non-empty subset of $S$.


Then $T$ has a maximal element and a minimal element.


Proof

We will show that each finite subset of $S$ has a minimal element.

The existence of a maximal element then follows from duality.


Proof by induction:

For all $n \in \Z_{\ge 1}$, let $P \left({n}\right)$ be the proposition:

Every set with $n$ elements has a minimal element.


Basis for the Induction

Let $T$ have exactly one element $x$.

Since $x \not \prec x$ it follows that $x$ is minimal.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $P \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k + 1}\right)$ is true.


So this is the induction hypothesis:

Every set with $k$ elements has a minimal element.


from which it is to be shown that:

Every set with $k + 1$ elements has a minimal element.


Induction Step

Suppose that every subset of $S$ with $k$ elements has a minimal element.

Let $T$ have $k + 1$ elements.

Then:

$T = T_0 \cup \left\{{x}\right\}$

where $T_0$ has $k$ elements and $x \in T \setminus T_0$.

Then $T_0$ has a minimal element $m_0$.

If $m_0$ is not a minimal element of $T$, then:

$x \prec m_0$

Thus $x$ is a minimal element of $T$.

Thus either $m_0$ or $x$ is a minimal element of $T$.


So $P \left({k}\right) \implies P \left({k + 1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

For every finite, non-empty subset $T$ of $S$, $T$ has a maximal element and a minimal element

The result follows by the Principle of Mathematical Induction.

$\blacksquare$


Sources