Hierarchy

A classification of certain mathematical objects according to the complexity of their definitions.

The first hierarchies were constructed in descriptive set theory (see [3]). In these hierarchies, the transition to a more complicated class of sets is effected by applying set-theoretical and topological operations to the elements of the simpler classes. The most important hierarchies in descriptive set theory are defined as follows. If $ T $ is some family of subsets of a set $ X $, then $ CT $ denotes the family of all complements in $ X $ of the elements of $ T $, $ T _ \sigma $ denotes the family of all countable unions of elements of $ T $ and $ T _ \delta $ denotes the family of all countable intersections of elements of $ T $. For a fixed topological space $ X $, let $ F $ denote the family of all closed subsets of $ X $ and $ G $ the family of all open subsets of $ X $. The sequence $ F, F _ \sigma , F _ {\sigma \delta } , F _ {\sigma \delta \sigma } \dots $ of classes is defined by transfinite induction; at each limit ordinal there stands the result of applying the operation $ \delta $ to the union of the preceding classes. Similarly, interchanging $ \sigma $ and $ \delta $ everywhere, one gets the sequence $ G, G _ \delta , G _ {\delta \sigma } , G _ {\delta \sigma \delta } \dots $ of classes. Here $ G = CF $, $ G _ \delta = CF _ \sigma $, etc. The sequences so constructed form the Borel hierarchy of subsets of $ X $. The union of the classes in this hierarchy is called the class of Borel subsets of $ X $, and is denoted by $ B $. If $ T $ is some family of subsets of a topological space $ X $, then $ PT $ denotes the family of all images of elements of $ T $ under continuous mappings from $ X $ to $ X $. The classes $ B, PB, CPB, PCPB $, etc., form the projective hierarchy of subsets of $ X $. In this connection, the analytic sets (the $ {\mathcal A} $- sets, cf. Analytic set) contain the class $ PB $, and their complements (the $ C {\mathcal A} $- sets) contain $ CPB $, etc.

In mathematical logic, hierarchies of sets and relations given by the formulas of logical languages are considered (see [1], [2], [5]). The most important examples of such hierarchies are those based on representing a relation $ P ( x _ {1} \dots x _ {k} ) $ in the form

$$ \tag{* } P ( x _ {1} \dots x _ {k} ) \iff $$

$$ \iff \ Q _ {1} y _ {1} \dots Q _ {n} y _ {n} R ( x _ {1} \dots x _ {k} , y _ {1} \dots y _ {n} ). $$

Here $ x _ {1} \dots x _ {k} , y _ {1} \dots y _ {n} $ are variables, some of which run over the set of natural numbers (numerical variables), and others over the set of all subsets of the natural numbers (set variables); $ Q _ {1} y _ {1} \dots Q _ {n} y _ {n} $ is a sequence of quantifiers in which universal and existential quantifiers alternate, that is, of any pair of consecutive quantifiers one is universal and one is existential; $ R ( x _ {1} \dots x _ {k} , y _ {1} \dots y _ {n} ) $ is an arbitrary recursive relation between the numerical and the set variables. The class $ \Sigma _ {n} ^ {0} $( $ \Pi _ {n} ^ {0} $, respectively) consists of all relations $ P ( x _ {1} \dots x _ {k} ) $ representable in the form (*), where $ y _ {1} \dots y _ {n} $ are numerical variables and the symbol $ Q _ {1} $ is $ \exists $( $ \forall $, respectively). The classes $ \Sigma _ {n} ^ {0} $ and $ \Pi _ {n} ^ {0} $, $ n = 0, 1 \dots $ form the Kleene–Mostowski arithmetic hierarchy (see Kleene–Mostowski classification). The union of these classes is called the class of arithmetic relations. The classes $ \Sigma _ {n - 1 } ^ {1} $( $ \Pi _ {n - 1 } ^ {1} $, respectively), $ n > 1 $, consist of the relations $ P ( x _ {1} \dots x _ {k} ) $ representable in the form (*), where all the variables $ y _ {1} \dots y _ {n - 1 } $ are set variables while $ y _ {n} $ is a numerical variable, and $ Q _ {1} $ is $ \exists $( $ \forall $, respectively). The class of arithmetic relations is denoted by $ \Sigma _ {0} ^ {1} $ and $ \Pi _ {0} ^ {1} $, respectively. The classes $ \Sigma _ {n} ^ {1} $, $ \Pi _ {n} ^ {1} $, $ n = 0, 1 \dots $ form the Kleene analytic hierarchy. The elements of $ \Delta _ {1} ^ {1} = \Sigma _ {1} ^ {1} \cap \Pi _ {1} ^ {1} $ are called hyper-arithmetic (see [2], [5]); they can be put in a hierarchy of their own, which can be regarded as an extension of the Kleene–Mostowski hierarchy.

The various hierarchies can be regarded in a uniform way from the point of view of definability in logical languages. In particular, the elementary classes of the Borel hierarchy can be defined in a way similar to the classes in the Kleene–Mostowski hierarchy, and the analytic hierarchy in a way similar to the projective hierarchy. In this way a number of assertions concerning the structure of classes of hierarchies gets a common formulation, and often similar proofs (see [1]). An example of such an assertion is the reduction principle, which goes as follows. Let $ U $ be a class in some hierarchy, and let $ X $ and $ Y $ be elements of it; then there exist an $ X _ {1} $ and a $ Y _ {1} $ in $ U $ such that $ X _ {1} \subseteq X $, $ Y _ {1} \subseteq Y $, $ X \cup Y = X _ {1} \cup Y _ {1} $, and $ X _ {1} \cap Y _ {1} = \emptyset $. This principle holds, for example, when $ U $ is $ \Pi _ {1} ^ {1} $, $ \Sigma _ {2} ^ {1} $, or $ CPB $, $ PCPB $. In model theory, hierarchies of classes of models are constructed by means of the form of the formulas giving the classes; there are analogies between these hierarchies and those mentioned above (see [1]).

The construction of hierarchies of recursive functions (cf. Recursive function) is realized in the theory of algorithms. One of the general methods for constructing such hierarchies is based on defining recursive functions by using some initial functions and operations on them (substitution, primitive recursion, etc.). The transition to a more complicated class in some hierarchy can be brought about, for example, as a result of adding to the preceding class the elements of some fixed sequence of recursive functions, and taking the closure of the set so obtained under the operations of substitution and bounded recursion. To obtain a more complicated class, in addition to closure with respect to certain operations (as in the preceding example), single applications of the operation of primitive recursion (for instance) to the elements of the simpler class can be used (see [4]). Another method for constructing hierarchies of recursive functions is based on classification by the complexity of computation (see [4]). Consideration of the characteristic functions of sets enables one to construct the hierarchy of decidable sets, starting from the hierarchy of recursive functions.

References

[1]	J. Addison, "Mathematical logic and its applications" , Moscow (1965) (In Russian; translated from English)
[2]	P. Hinman, "Recursion-theoretic hierarchies" , Springer (1978)
[3]	K. Kuratowski, A. Mostowski, "Set theory" , North-Holland (1968)
[4]	, Problems of mathematical logic. Complexity of algorithms and of classes of computable functions , Moscow (1970) (In Russian; translated from English)
[5]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165

References

[a1]	J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) ((especially the article of D.A. Martin on Descriptive set theory))
[a2]	Y.N. Moschovakis, "Descriptive set theory" , North-Holland (1980)