Suppose we define a total order on pairs of integers where $(x_1, y_1) > (x_2, y_2)$ when $x_1 > x_2 \lor (x_1 = x_2 \land y_1 > y_2)$, i.e., first comparing the first element and then falling back to the second when the first elements are equal.
Does there exist a pairing function which preserves this ordering?
Best Answer
No - intuitively, the ordering on pairs you give is "too long."
Consider the pairs $(2,2)$, $(3,3)$. In the ordering on pairs, the interval between $(2,2)$ and $(3,3)$ is infinite and bounded both above and below. But $\mathbb{Z}$ has no infinite interval which is bounded both above and below. So there is no such pairing function.