[Math] Every not empty finite subset of a totally ordered set has a maximum and minimum

elementary-set-theoryinductionorder-theorysolution-verification

Theorem

Let be $(X,\le)$ a totally ordered set: then for any not empty finite subset $A$ of $X$ there exist the maximum element and minimum element.

proof. Let be $(X,\le)$ a totally ordered set and we prove by induction that any not empty finite subset $A$ of $X$ has a minimum element. Since $X$ is a totally ordered set, previously we observe that any its subset $Y$ (finite or infinite) is a chain.

Obviously any subset $A$ of one element $a$ has trivially a minimum.
So we suppose that any subset of $n$ elements has a minimum element and then we consider a subset $A$ of $n+1$ elements: since $A$ is finite there exists a bijection $\phi$ from $A$ onto some natural number $m$, that is the successor of $n$, and so we can organize the elements of $A$ in a finite succession, that is $A=\{a_1,…,a_{n+1}\}$. Now we consider the subset $B=\{a_h\in A:h\le n\}$: obviously $X$ is a subset of $A$ that has $n$ element and so it has a minimum element $b$; so since $A=B\cup\{a_{n+1}\}$ and since $A$ is a chain (remember what before we observed), it must be or $a_{n+1}\le b$ or $b<a_{n+1}$ and so for the transitivity property of the order relation $\le$ in any case $A$ has a minimum element.

So now we only have to prove that any not empty finite subset $A$ of $X$ has a maximum element. So we consider the inverse relation $\preccurlyeq$ defined as $x\preccurlyeq y\iff y\le x$ for any $x,y\in X$: clearly $\preccurlyeq$ is a total order, since indeed $\le$ is a total order, and any minimum in $\preccurlyeq$ is a maximum in $\le$ and so since any not empty finite subset $A$ has a minimum in $\preccurlyeq$ it follows that any not empty finite subset in $\le$ has a maximum element. So we concluded the proof.

Is my proof correct? If not how prove the theorem?

Could someone help me, please?

Best Answer

I would write it thusly:

We proceed by induction on $n$, the number of elements of $A$.

If $n=1$, $A=\{x\}$ for some $x \in X$ and $x=\min(A)=\max(A)$ and we're done.

Now assume that any set with $n$ elements has a maximum and a minimum. Let $A$ be a set with $n+1$ elements, and pick any $p \in A$. Then $A':=A\setminus \{p\}$ has $n$ elements and so by the induction hypothesis $m:=\min(A') \in A'$ and $M:=\max(A')\in A'$ both exist.

There are three cases:

  1. $p < m$. Then $p=\min(A)$ (if $a \in A$ and $a \neq p$ then $a \in A'$ so $m \le a$ and so $p \le a$ as well, and if $a=p$, $p \le a$ trivially; but always $p \le a$) and $M=\max(A)$ (if $a \in A$, if $a=p$ then $a < m \le M$; if $a \neq p$, $a \in A'$ so $a \le M$ by definition; always $a \le M$).

  2. $p > M$. Then $m=\min(A)$ and $p=\max(A)$ via entirely analogous reasoning as in case 1.

  3. $m \le p \le M$ (this is the only remaining option as the order is a linear one!) and then $p$ lies within the same bounds as $A\setminus\{p\}$ so clearly $m=\min(A)$,$M=\max(A)$.

This finishes the inductive step.

The only prerequisite is that you know that if a set has $n+1$ elements and you remove one, the remainder has $n$ elements. But you seem to be able to use that fact by your own attempt.

Related Question