- Borel hierarchy
In
mathematical logic , the Borel hierarchy is a stratification of theBorel algebra generated by the open subsets of aPolish space ; elements of this algebra are called Borel sets. Each Borel set is assigned a uniquecountable ordinal number called the rank of the Borel set. The Borel hierarchy is of particular interest indescriptive 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.Borel sets
:"Main article:
Borel algebra "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. A motivation for the Borel hierarchy is to provide a more explicit characterization of the Borel sets.
Boldface hierarchy
The Borel hierarchy or boldface Borel hierarchy on a space "X" consists of classes mathbf{Sigma}^0_alpha, mathbf{Pi}^0_alpha, and mathbf{Delta}^0_alpha for every countable ordinal alpha greater than zero. Each of these classes consists of subsets of "X". The classes are defined inductively from the following rules:
* A set is mathbf{Sigma}^0_1 if and only if it is open.
* A set is mathbf{Pi}^0_alpha if and only if its complement is mathbf{Sigma}^0_alpha.
* A set is mathbf{Sigma}^0_alpha for alpha > 1 if and only if there is a sequence of sets A_1,A_2,ldots such that each A_i is mathbf{Pi}^0_{alpha_i} for some alpha_i < alpha and A = igcup A_i.
* A set is mathbf{Delta}^0_alpha if and only if it is both mathbf{Sigma}^0_alpha and mathbf{Pi}^0_alpha.It can be shown that igcup_{alpha < omega_1} mathbf{Sigma}^0_alpha = igcup_{alpha < omega_1} mathbf{Pi}^0_alpha = igcup_{alpha < omega_1} mathbf{Delta}^0_alpha and a set is in this union if and only if it is Borel.
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 mathbf{Sigma}^0_alpha for some finite ordinal α; otherwise it has infinite rank.
If X is an uncountable Polish space, it can be shown that mathbf{Sigma}^0_alpha is not contained in mathbf{Pi}^0_alpha for any alpha < omega_1, and thus the hierarchy does not collapse.
Borel sets of small rank
The classes of small rank are known by alternate names in classical descriptive set theory.
* The mathbf{Sigma}^0_1 sets are the open sets. The mathbf{Pi}^0_1 sets are the closed sets.
* The mathbf{Sigma}^0_2 sets are countable unions of closed sets, and are called Fσ sets. The mathbf{Pi}^0_2 sets are the dual class, and can be written as a countable intersection of open sets. These sets are called Gδ sets.Lightface hierarchy
The lightface Borel hierarchy is an effective version of the boldface Borel hierarchy. It is important in
effective descriptive set theory andrecursion theory . The lightface Borel hierarchy extends thearithmetical hierarchy of subsets of aneffective Polish space . It is closely related to thehyperarithmetical hierarchy .The lightface Borel hierarchy can be defined on any effective Polish space. It consists of classes Sigma^0_alpha, Pi^0_alpha and Delta^0_alpha for each nonzero countable ordinal alpha less than the Church-Kleene ordinal omega^{mathrm{CK_1. 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 Sigma^0_1 if and only if it is effectively open, that is, an open set which is the union of acomputably 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 Pi^0_alpha if and only if its complement is Sigma^0_alpha. A code for one of these sets is a pair "(1,c)" where "c" is a code for the complementary set.
* A set is Sigma^0_{alpha} if there is acomputably enumerable sequence of codes for a sequence A_1,A_2,ldots of sets such that each A_i is Pi^0_{alpha_i} for some alpha_i < alpha and A = igcup A_i. A code for a Sigma^0_alpha set is a pair "(2,e)", where "e" is an index of a program enumerating the codes of the sequence A_i.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 alpha < omega^{mathrm{CK_1 there are sets in Sigma^0_alpha setminus Pi^0_{alpha}, and thus the hierarchy does not collapse. No new sets would be added at stage omega^{mathrm{CK_1, 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 Delta^1_1 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 omega^{
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 omega^{mathrm{CK_1. This is the origin of the Church-Kleene ordinal in the definition of the lightface hierarchy.References
* Kechris, Alexander. "Classical Descriptive Set Theory". Graduate Texts in Mathematics v. 156, Springer-Verlag, 1995. ISBN 3-540-94374-9.
* Jech, Thomas. "Set Theory", 3rd edition. Springer, 2003. ISBN 3-540-44085-2.See also
*
Wadge hierarchy
* Veblen hierarchy
Wikimedia Foundation. 2010.