In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets.
Each Borel set is assigned a unique countable ordinal number called the rank of the Borel set.
The Borel hierarchy is of particular interest in descriptive set theory.
One common use of the Borel hierarchy is to prove facts about the Borel sets using transfinite induction on rank.
Properties of sets of small finite ranks are important in measure theory and analysis.
The Borel algebra in an arbitrary topological space is the smallest collection of subsets of the space that contains the open sets and is closed under countable unions and complementation.
It can be shown that the Borel algebra is closed under countable intersections as well.
A short proof that the Borel algebra is well-defined proceeds by showing that the entire powerset of the space is closed under complements and countable unions, and thus the Borel algebra is the intersection of all families of subsets of the space that have these closure properties.
This proof does not give a simple procedure for determining whether a set is Borel.
The classes are defined inductively from the following rules: The motivation for the hierarchy is to follow the way in which a Borel set could be constructed from open sets using complementation and countable unions.
A Borel set is said to have finite rank if it is in
then the hierarchy can be shown to have the following properties: The classes of small rank are known by alternate names in classical descriptive set 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.
Each class consists of subsets of the space.
The classes, and codes for elements of the classes, are inductively defined as follows:[2] 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.
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 effective Borel hierarchy are the same as the classes
[1]p.168 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.
This tree describes how A is built from sets of smaller rank.
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.
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.