Uniqueness of non-dominated two-dimensional points
For $n=1$ the statement is trivially true. Otherwise $n &gt; 1$.

Sort the points in each dimension in ascending order. Let $r^i_1, r^i_2$ be the rank of point $i$ in each dimension, rounding ties down. (Thus if there is a duplicate value (1,2,2,3) we take the index of the first appearance in the list). We use 0-based indexing.

First we note that for a point $p_i$ that $w_i = r^i_1 + r^i_2$ gives an upper bound on the number of points that can't dominate $p_i$. Therefore, by a counting argument, if $w_i &lt; n-1$ there must be a point that dominates $p_i$.

We will now assume that we have a set of points that doesn't have a dominated pair. For convenience, we rename all the points such that they are ordered in the first dimension, thus $p^0_1 \leq p^1_1 \leq \dots p^{n-1}_1$.

We will now prove that $r^i_1 = i$ and $r^i_2 = n - 1 - i$.

Clearly $r^0_1 = 0$. Therefore, $r^0_2 = n-1$, otherwise $w^0 &lt; n-1$, and there is a point dominating $p_0$. Since $r^0_2 = n-1$ there is no point having the same value in the second dimension (otherwise, $r^0_2 &lt; n-1$).

Assume that we have proved for the first $j$ points, we now prove for $j+1$. Note that since each of the first $j$ points have $r^i_2 = n-1 - i$, this means that there are no other points having those rankings. Since the points are in ascending order in the first dimension, $r^{j+1}_1 = j$ or $r^{j+1}_1 = {j+1}$. Let us assume by contradiction the former. Therefore, since there are no dominated pairs, we have that $r^{j+1}_2 \geq n - 1 - j$, which is a contradiction (to no other points having those rankings). Therefore, $r^{j+1}_1 = {j+1}$ and since there are no dominated pairs, $r^{j+1}_2 = n - 1 - {j+1}$, and no other point may have that value.