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

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?

• Did you try induction on the number of elements? Feb 9 '20 at 16:01
• @I did not , seems a good way, but I guess there should be another way. indeed I don't know how to use induction here since I don't have any specific totally ordered set
– user715522
Feb 9 '20 at 16:03
• The power set is not totally ordered, although the statement is true for the powerset. Try proving it for pairs and using induction on the size of the set. Feb 9 '20 at 17:52

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

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 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 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} 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}.

• And I thought BubbleSort was inefficient! At least it doesn't require you start over at the top with every exchange. (Of course, efficiency has nothing to do with your purpose here: as long at the algorithm will eventually work, it proves the result.) Feb 22 '20 at 21:15