Prove this sequence is finite Given pairs $(x, y)$ for which both $x$ and $y$ are natural numbers, in which we say $$(x, y) < (d, e) \iff x < d \space \vee \space (x == d \space \wedge \space y < e)$$
Prove that any decreasing sequence of these pairs, where decreasing is described above, is finite.
Here is the layout of the solution I have in mind, but I do now know whether it is true.
Given any set $U$ of decreasing set of these pairs, let $V$ be the unique $x$ values that exist in $U$ to form a decreasing set. Also, let $Z$ be the values of $y$ within this set. Since $x$ and $y$ are both always natural numbers, by well-ordering principle $V$ and $Z$ must have a smallest number, let these be represented by $s$ and $q$ respectively. This means this set is bounded from below by $(s, q)$. Therefore, $W$ must contain a smallest element. This combined with the fact that it is a decreasing means it takes a finite number of steps to get to this smallest pair, which means $W$ is finite.
Is this valid reasoning? If not how can I change it to make it a better/more accurate proof?  
 A: Think of these as points in the 2D plane.  
If you started with the point $(x_0,y_{0,1})$ then after at most $y_{0,1}$ steps you will have to decrease the x-coordinate $x_0$ to $x_0-1$ or to $x_0-2$ or to some other value which is strictly smaller than $x_0$.   
Say at that step you jumped from $(x_0,y_{0,m})$ to $(x_1, y_{1,1})$ (where $x_1 < x_0$). Then after at most $y_{1,1}$ steps you have to again decrease the x-coordinate which is now $x_1$ to $x_1-1$ or $x_1-2$ or something else. We denote this new value of the $x$ coordinate as $x_2$. And so on... 
Continuing this way it's obvious that after each "jump" which decreases your x-coordinate, you can do only a finite number of steps before you are forced to decrease the x-coordinate (if you want to proceed with your sequence).   
Think of the steps you take before you decrease the x as a set.
The union of these finite sets is also finite.   
So overall... after finite number of steps you will arrive at (1,1) and at that point you will be unable to decrease neither the x, nor the y coordinate.   
Side note: just draw some sample sequence in 2D, from there on you should be able to easily formalize your proof in whatever particular theory you need it. 
A: You're on the right track, but I think you got a little lost in the details.  In particular, you want to consider the two coordinates separately.
Let $S$ be an infinite decreasing sequence of pairs.  Let $S_1$ be the (possibly repeating) sequence of first coordinates of elements of $S$. Then $S_1$ is an infinite non-increasing sequence of natural numbers, so it must have a least element $x_0$, and once you reach that least element, all subsequent elements of $S$ must have $x_0$ as their first coordinate.
But now the sequence $S_2 = (y \mid (x_0, y) \in S)$ is an infinite strictly decreasing sequence of natural numbers, and that can't exist.
