In
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
, the Borel hierarchy is a stratification of the
Borel algebra
In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are name ...
generated by the open subsets of a
Polish space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named be ...
; elements of this algebra are called Borel sets. Each Borel set is assigned a unique
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the leas ...
called the rank of the Borel set. The Borel hierarchy is of particular interest in
descriptive set theory
In mathematical logic, descriptive set theory (DST) is the study of certain classes of " well-behaved" subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to ot ...
.
One common use of the Borel hierarchy is to prove facts about the Borel sets using
transfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC.
Induction by cases
Let P(\alpha) be a property defined for ...
on rank. Properties of sets of small finite ranks are important in
measure theory
In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simila ...
and
analysis
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (3 ...
.
Borel sets
The Borel algebra in an arbitrary
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
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 Borel hierarchy
The Borel hierarchy or boldface Borel hierarchy on a space ''X'' consists of classes
,
, and
for every countable ordinal
greater than zero. Each of these classes consists of subsets of ''X''. The classes are defined inductively from the following rules:
* A set is in
if and only if it is open.
* A set is in
if and only if its complement is in
.
* A set
is in
for
if and only if there is a sequence of sets
such that each
is in
for some
and
.
* A set is in
if and only if it is both in
and in
.
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
for some finite ordinal
; otherwise it has infinite rank.
If
then the hierarchy can be shown to have the following properties:
* For every ''α'',
. Thus, once a set is in
or
, that set will be in all classes in the hierarchy corresponding to ordinals greater than ''α''
*
. Moreover, a set is in this union if and only if it is Borel.
* If
is an uncountable Polish space, it can be shown that
is not contained in
for any
, 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
sets are the open sets. The
sets are the closed sets.
* The
sets are countable unions of closed sets, and are called
Fσ sets. The
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
Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptiv ...
and
recursion theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has sinc ...
. The lightface Borel hierarchy extends the
arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
of subsets of an
effective Polish space In mathematical logic, an effective Polish space is a complete separable metric space that has a computable presentation. Such spaces are studied in effective descriptive set theory and in constructive analysis. In particular, standard examples ...
. 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
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
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
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
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
In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers ...
. 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.
Relation to other hierarchies
References
*
Kechris, Alexander. ''Classical Descriptive Set Theory''. Graduate Texts in Mathematics v. 156, Springer-Verlag, 1995. .
*
Jech, Thomas. ''Set Theory'', 3rd edition. Springer, 2003. {{ISBN, 3-540-44085-2.
See also
*
Wadge hierarchy
*
Veblen hierarchy
Descriptive set theory
Mathematical logic hierarchies