If $R$ is a total order over set $A$, then all subsets of $A$ can be sorted

Question

I'm working on the proof of this theorem:

Let A be a set and let $\leq_A$ be a partial order over . We say that a sequence $x_1,...,x_n$ is sorted if $x_1 \leq_A x_2 \leq_A ... \leq_A x_n$. Prove that any subset of $n$ elements of $A$ can be sorted iff $A$ is a total order.

Since this is bidirectional, I need to prove both directions of implication. I've actually already proved the first direction (I asked a question about this) - if any subset of $A$ can be sorted, then $\leq_A$ is total. Now I'm trying to prove the second direction, namely if $\leq_A$ is total, then any subset of $A$ can be sorted.

I tried different techniques (direct, contradiction, contrapositive) and the best results I achieved was when I tried to prove by induction, but I can't complete the proof. Here is it:

Assume that $P(n)$ is true iff any set $S \subseteq A$ with $n$ elements can be sorted.

1. Then $P(0)$ is true, since all empty sets are sorted.
2. So assuming that for any $n \in \mathbb{N}$ if $P(n)$ is true, then we prove that $P(n + 1)$ is also true. Consider any set $S \subseteq A$ with exactly $n$ elements and consider element $y \in A$ which is also $y \not\in S$. Since $\leq_A$ is total order we have that $y$ is either the least element in $S \cup \{y\}$, or the greatest element in $S \cup \{y\}$, or there are some $x_l \in S$, where $x_l \leq_A y$, and there are some $x_g \in S$, where $y \leq_A x_g$. In the first and the second cases we are done, because $S \cup \{y\}$ is sorted...

I don't actually know how to prove that the set is also sorted in the third case. Moreover I'm not even sure that my assumptions about the first and the second cases are correct.

Could someone please provide any hints and suggestions for where to go next? Or if you know another way (simplier/without induction) to prove this, please give me a hint.

Answer 1

Hint: Try to prove a Lemma: If $\le_A$ is a total order, then for every nonempty finite subset $\{x_1,x_2,\ldots,x_n\}\subset A$ there exists a minimum, i.e. one $x_i$ such that $x_i\le_A x_1$, $x_i\le_A x_2$,..., $x_i\le_A x_n$. Use induction for that.

Then use the Lemma in the inductive step of your overall proof.