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

## Contents

## 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

- 1967: Garrett Birkhoff:
*Lattice Theory*(3rd ed.): $\S\text I.3$: Theorem $3$