I'm trying to prove the following theorem:
Let A be a set and let $\leq_A$ be a partial order over $A$. 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.
I sure think I understand the theorem and intuitively I see that this is true, but I have some difficulties in proving this. I think this is because I'm not sure exactly what I can assume about the sorted sequence. I'm not sure also how to negate the proposition, that the sequence is sorted. So what I tried to do:
- My first attempt was proving the first direction of implication by contradiction - assume that the sequence is sorted, but $\leq_a$ is not a total order. Then we know that there must be such $x, y \in A $ that $x \nleq_a y$ and $y \nleq_a x$. But this is where I got stuck, I can't come up with a contradiction, because I'm not sure if this $x \nleq_a y$ and $y \nleq_a x$ implies that sequence can't be sorted.
- The second attempt was a proof by contrapositive, but there is the same issue here. I'm not sure how to negate that the sequence is sorted.
I also know a bit about well-ordering relations, that every well-ordering relation is also a total order. So I think I could prove the first direction of implication if I showed that any subset of the set $A$ has a least element. Similarly, I could probably go this way in my first attempt (proof by contradiction) - show that if there are $x, y$, where $x \nleq_a y$ and $y \nleq_a x$ then any subset of $A$ doesn't have a least/greatest element. But in this case I doubt if it's obvious that the sequence is not sorted.
I'd be grateful for any hints and suggestions, especially about the definition of the sorting in this theorem, what can I assume about this, how to negate this.
If I understand correctly, to sort $x$ and $y$, you either write $x \le_a y$ or $y \le_a x$.
If you can write neither, $x$ and $y$ cannot be sorted.
This is the gist of the contrapositive proof (which you have shown)