Kleene–Brouwer order

Tree interpretation

A tree, in descriptive set theory, is defined as a set of finite sequences that is closed under prefix operations. The parent in the tree of any sequence is the shorter sequence formed by removing its final element. Thus, any set of finite sequences can be augmented to form a tree, and the Kleene–Brouwer order is a natural ordering that may be given to this tree. It is a generalization to potentially-infinite trees of the postorder traversal of a finite tree: at every node of the tree, the child subtrees are given their left to right ordering, and the node itself comes after all its children. The fact that the Kleene–Brouwer order is a linear ordering (that is, that it is transitive as well as being total) follows immediately from this, as any three sequences on which transitivity is to be tested form (with their prefixes) a finite tree on which the Kleene–Brouwer order coincides with the postorder.

The significance of the Kleene–Brouwer ordering comes from the fact that if ${\displaystyle X}$ is well-ordered, then a tree over ${\displaystyle X}$ is well-founded (having no infinitely long branches) if and only if the Kleene–Brouwer ordering is a well-ordering of the elements of the tree.

Recursion theory

In recursion theory, the Kleene–Brouwer order may be applied to the computation trees of implementations of total recursive functionals. A computation tree is well-founded if and only if the computation performed by it is total recursive. Each state ${\displaystyle x}$ in a computation tree may be assigned an ordinal number ${\displaystyle ||x||}$, the supremum of the ordinal numbers ${\displaystyle 1+||y||}$ where ${\displaystyle y}$ ranges over the children of ${\displaystyle x}$ in the tree. In this way, the total recursive functionals themselves can be classified into a hierarchy, according to the minimum value of the ordinal at the root of a computation tree, minimized over all computation trees that implement the functional. The Kleene–Brouwer order of a well-founded computation tree is itself a recursive well-ordering, and at least as large as the ordinal assigned to the tree, from which it follows that the levels of this hierarchy are indexed by recursive ordinals.

History

This ordering was used by Lusin & Sierpinski (1923), and then again by Brouwer (1924). Brouwer does not cite any references, but Moschovakis argues that he may either have seen Lusin & Sierpinski (1923), or have been influenced by earlier work of the same authors leading to this work. Much later, Kleene (1955) studied the same ordering, and credited it to Brouwer.