Proving that there exists no subsequence of 3 numbers that is not monotonically increasing or decreasing in a sequence of 5 distinct numbers I've been studying discrete math on MIT OCW and came across this problem.

Define a 3-chain to be a (not necessarily contiguous) subsequence
  of three integers, which is either monotonically increasing or monotonically decreasing. We
  will show here that any sequence of five distinct integers will contain a 3-chain. Write
  the sequence as $a_1, a_2, a_3, a_4, a_5$. Note that a monotonically increasing sequence is one in
  which each term is greater than or equal to the previous term. Similarly, a monotonically
  decreasing sequence is one in which each term is less than or equal to the previous term.
  Lastly, a subsequence is a sequence derived from the original sequence by deleting some
  elements without changing the location of the remaining elements.

This problem has multiple parts, each guiding the way to a final solution. I will share my progress and then explain where I'm lost.

(a) Assume that $a_1 < a_2$. Show that if there is no 3-chain in our sequence, then $a_3$ must be less than $a_1$.

My answer: Suppose $a_3>a_1$. If $a_3>a_2,$ $\ a_1<a_2<a_3$ is a 3-chain. If $a_3<a_2$ and $a_4<a_3$, then  $ a_2>a_3>a_4$ is a 3-chain. If $a_4>a_3$, then $a_1<a_3<a_4$ is a 3-chain. Thus $a_3$ must be less than $a_1$.

(b) Using the previous part, show that if $a_1<a_2$ and there is no 3-chain in our sequence, then $a_3<a_4<a_2$.

My answer: If $a_3>a_4$, then $a_1>a_3>a_4$ is a 3-chain. Thus $a_4>a_3$. If $a_4>a_2$, then $a_1<a_2<a_4$ is a 3-chain. Thus $a_3<a_4<a_2$.

(c) Assuming that $a_1<a_2$ and $a_3<a_4<a_2$, show that any value of $a_5$ must result in a 3-chain.

My answer: If $a_5>a_4$, then $a_3<a_4<a_5$ is a 3-chain. If $a_5<a_4$, then $a_3<a_4<a_5$ is a 3-chain. Thus, any value of $a_5$ results in a 3-chain.

(d) Using the previous parts, prove by contradiction that any sequence of 5 distinct integers must contain a 3-chain.

This is where I got lost. Doesn't all this just prove that $a_1>a_2$ since we initially assumed that $a_1<a_2$? 
 A: The assumption for the contradiction is that there exists a sequence of 5 distinct integers $a_1,\cdots,a_5$ which do not contain a 3-chain.
There are two possibilities since $a_i$ are assumed to be distinct, either $a_1<a_2$ or $a_1>a_2$. If $a_1<a_2$, then by the symmetry of the arguments, we still have the same result with a reversal of direction but still monotone. As @BrianM.Scott has pointed out, we can apply an identical argument to $-a_1,\cdots,-a_5$ which is monotone if and only if the original sequence is monotone.
So assume WLOG that $a_1<a_2$.
Then our assumption that there is no 3-chain (and WLOG that $a<1<a_2$) allow us to use part a to justify using part b and then using part b to justify using part c, as you have proven. Thus our assumption gives that for any possible value of $a_5$, ie in all cases, we have a 3-chain. So the assumption that there IS a 3-chain implies that there NOT a 3-chain. This is a contradiction. Since we could have chosen $a_1>a_2$ and reached the same contradiction, then we always have a contradiction for any sequence of 5 distinct integers, thus the original assumption that there is not a 3-chain is false.
