0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.