Kleene–Brouwer order

In descriptive set theory, the Kleene–Brouwer order or Lusin–Sierpiński order is a linear order on finite sequences over some linearly ordered set ${\displaystyle (X,<)}$, that differs from the more commonly used lexicographic order in how it handles the case when one sequence is a prefix of the other. In the Kleene–Brouwer order, the prefix is later than the longer sequence containing it, rather than earlier.

The Kleene–Brouwer order generalizes the notion of a postorder traversal from finite trees to trees that are not necessarily finite. For trees over a well-ordered set, the Kleene–Brouwer order is itself a well-ordering if and only if the tree has no infinite branch. It is named after Stephen Cole Kleene, Luitzen Egbertus Jan Brouwer, Nikolai Luzin, and Wacław Sierpiński.