Every finite subset of a non-empty totally ordered set has both upper and lower bounds

Question

Prove Every finite subset of a non-empty totally ordered set has both upper and lower bounds.

By completeness axiom every nonempty subset of real numbers that is bounded from above (respectively from below) has a supremum (respectively infimum) , a finite totally ordered set has finitely many elements and it's always possible to find a supremum or infimum of that set , and even upper or lower bounds, but I don't know how to prove that, because even completeness axiom consider the special case of a totally ordered set which is the set of real numbers, but what about the case where our totally ordered set is the power set of a specific set?

Can someone prove this statement?

Answer 1

Let $X$ be your finite set, say with $n$ elements. The total order of the ambient space induces a total order on $X$. Thus you can order the elents $x_i$ of $X$ so that $x_1< x_2<\dots< x_n$. Then $x_1$ is the minimum (hence a lower bound) and $x_n$ is the maximum (hence an upper bound).

In order to sort the elements of $X$ in an oredered way you can use the following algorithm:

Step $(1)$ Number the elements of $X$ as $x_1,\dots,x_n$ and go to next step.

Step $(2)$ Compare $x_1$ with $x_2$.

If $x_1>x_2$ then switch them and restart from Step $(2)$.

If $x_1<x_2$ go to next step.

Step $(3)$ Compare $x_2$ with $x_3$.

If $x_2>x_3$ then switch them and restart from Step $(2)$.

If $x_2<x_3$ go to next step.

...

Step $(n)$ Compare $x_{n-1}$ with $x_n$. If $x_{n-1}>x_n$ then switch them and restart from Step $(2)$.

If $x_{n-1}<x_n$ STOP.

The numbering you get when you stop is exactly that given by the order. Indeed, when you stop, then you passed all the checks of any Step $(i)$, and thus $x_{i}<x_{i+1}$.

Answer 2

Proof: (by induction on the cardinality of your finite set)

Let $P(n)$: any set with $n$ elements has a sup and an inf that both belong to your set.

P(1) is true: indeed if $A=\{a\}$ then $a=\sup A = \inf A$, and $a \in A$.

P(2) is true (I will need this later!): If $A = \{a,b\}$ then assume WLG that $a\leq b$. Then $\inf A = a$ and $\sup A = b$, and both are in $A$.

Assume $P(n)$ holds, that is, every set with $n$ elements has a min and a max. Take a $B$ with $n+1$ elements. Pick $a \in B$, and define $A = B \backslash \{a\}$. By induction hypothesis $A$ has a max and a min from $A$. Now, $$ \inf B = \inf\{a,\inf A\}, \quad and \quad \sup B = \sup \{a,\sup A\} \, $$ which by $P(2)$ exist. These sup and inf belong to $B$: Let me do $\sup B$ case only. Either $\sup B = a$, or, $\sup B = \sup A$. In the former case, $a \in B$, and we are done. In the latter case, by step $P(n)$ we know that $\sup A \in A$. But $A \subset B$, thus, $\sup A \in B$. This proves $P(n+1)$, and ends the induction. $\Box $