Borel Hierarchy - Lightface Hierarchy

Lightface Hierarchy

The lightface Borel hierarchy is an effective version of the boldface Borel hierarchy. It is important in effective descriptive set theory and recursion theory. The lightface Borel hierarchy extends the arithmetical hierarchy of subsets of an effective Polish space. It is closely related to the hyperarithmetical hierarchy.

The lightface Borel hierarchy can be defined on any effective Polish space. It consists of classes, and for each nonzero countable ordinal less than the Church-Kleene ordinal . Each class consists of subsets of the space. The classes, and codes for elements of the classes, are inductively defined as follows:

• A set is if and only if it is effectively open, that is, an open set which is the union of a computably enumerable sequence of basic open sets. A code for such a set is a pair (0,e), where e is the index of a program enumerating the sequence of basic open sets.
• A set is if and only if its complement is . A code for one of these sets is a pair (1,c) where c is a code for the complementary set.
• A set is if there is a computably enumerable sequence of codes for a sequence of sets such that each is for some and . A code for a set is a pair (2,e), where e is an index of a program enumerating the codes of the sequence .

A code for a lightface Borel set gives complete information about how to recover the set from sets of smaller rank. This contrasts with the boldface hierarchy, where no such effectivity is required. Each lightface Borel set has infinitely many distinct codes. Other coding systems are possible; the crucial idea is that a code must effectively distinguish between effectively open sets, complements of sets represented by previous codes, and computable enumerations of sequences of codes.

It can be shown that for each there are sets in, and thus the hierarchy does not collapse. No new sets would be added at stage, however.

A famous theorem due to Spector and Kleene states that a set is in the lightface Borel hierarchy if and only if it is at level of the analytical hierarchy. These sets are also called hyperarithmetic.

The code for a lightface Borel set A can be used to inductively define a tree whose nodes are labeled by codes. The root of the tree is labeled by the code for A. If a node is labeled by a code of the form (1,c) then it has a child node whose code is c. If a node is labeled by a code of the form (2,e) then it has one child for each code enumerated by the program with index e. If a node is labeled with a code of the form (0,e) then it has no children. This tree describes how A is built from sets of smaller rank. The ordinals used in the construction of A ensure that this tree has no infinite path, because any infinite path through the tree would have to include infinitely many codes starting with 2, and thus would give an infinite decreasing sequence of ordinals. Conversely, if an arbitrary subtree of has its nodes labeled by codes in a consistent way, and the tree has no infinite paths, then the code at the root of the tree is a code for a lightface Borel set. The rank of this set is bounded by the order type of the tree in the Kleene–Brouwer order. Because the tree is arithmetically definable, this rank must be less than . This is the origin of the Church-Kleene ordinal in the definition of the lightface hierarchy.