2
$\begingroup$

I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them):

{0, 1, 2} < {0, 1, 3}
          < {0, 2, 3}
          < {1, 2, 3}
          < {0, 1, 4}
          < {0, 2, 4}
          < {1, 2, 4}
          < {0, 3, 4}
          < {1, 3, 4}
          < {2, 3, 4}
          < {0, 1, 5}
          < ...

The sets are generated recursively: increase the highest number and reset all the other elements to the lowest possible numbers, then apply this algorithm recursively to the remaining numbers.

The position within this ordering is given by:

C(x[1], 1) + C(x[2], 2) + C(x[3], 3) + ...

where x[i] is the i-th element in the sorted set and C(n, k) is the binomial coefficient.

Does anyone know of a name for this kind of total ordering? Furthermore, what other common ways are there to order sets containing a fixed number of totally ordered elements?

Improve this question
$\endgroup$
1
  • $\begingroup$ In recursion theory and Peano arithmetic there is an ordering of unordered pairs $(x,y) \mapsto ((x+y)^2+3x+y)/2$ (here all of $x<y$, $x=y$, $x>y$ could be possible). $\endgroup$
    – Yuval Filmus
    Commented Feb 13, 2014 at 2:18

1 Answer 1

Reset to default
6
$\begingroup$

This is just lexicographical order, but left to right (not right to left as usual).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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