[Math] Prove that every non-empty finite subset of an ordered set, has maximal and minimal elements.

elementary-set-theory

Assume that $(X,<)$ is a totally ordered set. Prove that if $S$ is a non-empty finite subset of $X$, then $S$ has maximal and minimal elements. Prove this by induction!

Note: Intuitively, what we want to prove is obvious; because if $S$ doesn't have maximal and minimal elements, then trichotomy tells us that $S$ doesn't have maximum and minimum elements either. So size of S would be infinite. My problem is showing this infinity with an induction on "w".

Best Answer

For a single-element set, the element is maximal and minimal.

Assume that all $n$-element subsets have a maximal and a minimal element. Let $A$ sub a subset with $n+1$ elements and $x$ one of its elements. Then $B=A\setminus\{x\}$ has $n$ elements. Let $M,m$ be maximal and minimal elements of $B$. Then $\max(x,M)$ is maximal and $\min(x,m)$ is minimal. In fact, if $y\in A$ and $y\geq \max(M,x)$, then either $y\in B$ or $y=x$. In the first case, it follows that $y=M$ and $M\geq x$. Therefore, $y=\max(M,x)$. In the second case, it follows that $y=x\geq M$ and therefore $y=\max(M,x)$. The argument for $\min(m,x)$ is similar but with the inequalities reversed.

Note that the argument actually shows the existence of maximum and minimum, since the set is assumed to be totally ordered.

Note that although the question includes the condition of totally ordered, the argument can be adapted to also work in this case. What is needed is to replace $\max(M,x)$ and $\min(m,x)$ for $M$ and $n$, in the case that $M$ and $x$ are not comparable and the case that $m$ and $x$ are not comparable, respectively. In this case, one only gets the existence of maximal and minimal elements, but not necessarily maximum and minimum.