Prove that every non-empty finite subset of an ordered set, has maximal and minimal elements. 
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".
 A: Let's induct on the size of $S$.
Base Case: $|S|=1$
Then, $S = \{a\}$ where $a \in X$, so clearly $S$ has both maximal and minimal element, $a$ being both.
Inductive Step: Assume this is true for all sets of size $n$, and let $S = \{a_i\}_{i=0}^n$. Then note that $T = S\setminus \{a_0\}$ has size $n$, and thus has both minimal and maximal elements.
Can you compare both of those to $x_0$ and finish?
A: 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.
A: I don't know if I'm understanding you correctly, but if you ment $w=|S|$ I think this is easy.
First of all, if $|S|=1$ (or $|S|=0$, it does not matter), the first inductive step is trivial.
Now, if we assume it true for $|S|=n-1,$ let $|S|=n$. We chose a subset of $S$ of order $n-1$ (we have $n$ subsets like that) so we know that it have maximal and minimal elements, $M$ and $m.$ We just need to check wether the element leftover is greater than $M$ or smaller than $m,$ and we can do this because $X$ is a totally ordered set, then so is $S.$
A: May I propose to you a broader perspective from which you can deduce your result as a particular case. 
We say an ordered set $(A, R)$ is noetherian if any nonempty subset of $A$ admits at least a maximal element; with this definition in place your quest becomes that of showing that any finite ordered set is noetherian (from this it will immediately follow by duality that a finite ordered set is also artinian, which is the notion dual to noetherianity, said to hold for an ordered set in which every nonempty subset admits at least a minimal element).
Let us briefly mention the fundamental recursion theorem (itself a special case of a more general theorem of transfinite recursion):

Given set $A$, element $a \in A$ and map $f: A \to A$ there will exist a unique sequence $u \in A^{\mathbb{N}}$ satisfying the following conditions:
1) $u_0=a$
2) $u_{n+1}=f(u_n)$ for any $n \in \mathbb{N}$.

and state the following:

Proposition. For arbitrary ordered set $(A, R)$ the following statements are equivalent:
1) $(A, R)$ is noetherian
2) there exists no strictly increasing (with respect to the order $R$) sequence in $A^{\mathbb{N}}$.

Proof:  Arguing by contradiction immediately establishes the implication $1) \Rightarrow 2)$; indeed if under the hypothesis of noetherianity a strictly increasing sequence $a \in A^{\mathbb{N}}$  did exist then the set of all its terms $$a_{\mathbb{N}}=\{a_n\}_{n \in \mathbb{N}}$$
were on the one hand nonempty yet on the other hand clearly not containing any maximal element (since for any $n \in \mathbb{N}$ we have $a_n <_R a_{n+1}$).
As for the converse implication, once again we argue by contradiction, assuming that $(A, R)$ were not noetherian; this means that there must exist a nonempty $B \subseteq A$ not containing any maximal element, in other words it must be the case that for any $x \in B$ there will exist $y \in B$ such that $x <_R y$ or equivalently for any $x \in B$ we must have 
$$B \cap (x, \to)_R \neq \varnothing$$
(where I am using the notation $(t, \to)_R=\{x \in A|\ t<_R x\}$).
Therefore, by employing the axiom of choice we can infer the existence of a map $f: B \to B$ such that $f(x) \in B \cap (x, \to)_R$ for any $x \in B$; furthermore, since $B$ is nonempty we can fix a certain $a \in B$.
By applying the fundamental theorem of recursion to the triplet $(B, a, f)$ we obtain a sequence $c \in B^{\mathbb{N}} \subseteq A^{\mathbb{N}}$ such that $c_{n+1}=f(c_n)$ for any natural $n$; however, this will entail that $c_n<_R c_{n+1}$ for any $n \in \mathbb{N}$ which means that $c$ is strictly increasing, amounting to a contradiction. $\Box$
In the particular case of a finite ordered set $A$, property $2)$ is clearly satisfied (otherwise the existence of a strictly monotonic sequence would entail the existence of an injection from $\mathbb{N}$ to $A$, which is prohibited by finiteness).
