hierarchy a division of mathematical objects into subclasses in accordance with an ordering that reflects their complexity. Around the turn of the century, analysts interested in the ‘descriptive set theory’ of the real numbers defined and studied two systems of classification for sets of reals, the Borel (due to Emil Borel) and the G hierarchies. In the 1940s, logicians interested in recursion and definability (most importantly, Stephen Kleene) introduced and studied other hierarchies (the arithmetic, the hyperarithmetic, and the analytical hierarchies) of reals (identified with sets of natural numbers) and of sets of reals; the relations between this work and the earlier work were made explicit in the 1950s by J. Addison. Other sorts of hierarchies have been introduced in other corners of logic. All these so-called hierarchies have at least this in common: they divide a class of mathematical objects into subclasses subject to a natural well-founded ordering (e.g., by subsethood) that reflects the complexity (in a sense specific to the hierarchy under consideration) of the objects they contain. What follows describes several hierarchies from the study of definability. (For more historical and mathematical information see Descriptive Set Theory by Y. Moschovakis, North-Holland Publishing Co., 1980.) (1) Hierarchies of formulas. Consider a formal language L with quantifiers ‘E’ and ‘D’. Given a set B of formulas in L, we inductively define a hierarchy that treats the members of B as ‘basic.’ Set P0 % S0 % B. Suppose sets Pn and Sn of formulas have been defined. Let Pn!1 % the set of all formulas of the form Q1u1 . . . Qmumw when u1, . . . , um are distinct variables, Q1, . . . , Qm are all ‘E’, m M 1, and w 1 Sn. Let Sn+1 % the set of all formulas of that form for Q1, . . . , Qm all ‘D’, and w 1 Pn. Here are two such hierarchies for languages of arithmetic. Take the logical constants to be truthfunctions, ‘E’ and ‘D’. (i) Let L0 % the first-order language of arithmetic, based on ‘%’, a two-place predicate-constant ‘‹’, an individual-constant for 0, functionconstants for successor, addition, and multiplication; ‘first-order’ means that bound variables are all first-order (ranging over individuals); we’ll allow free second-order variables (ranging over properties or sets of individuals). Let B % the set of bounded formulas, i.e. those formed from atomic formulas using connectives and bounded quantification: if w is bounded so are Eu(u ‹ t / w) and Du(u ‹ t & w). (ii) Let L1 % the second-order language of arithmetic (formed from L0 by allowing bound second-order variables); let B % the set of formulas in which no second-order variable is bound, and take all u1, . . . , um as above to be second-order variables. (2) Hierarchies of definable sets. (i) The Arithmetic Hierarchy. For a set of natural numbers (call such a thing ‘a real’) A : A 1 P n0 [ or S0n ] if and only if A is defined over the standard model of arithmetic (i.e., with the constant for 0 assigned to 0, etc., and with the first-order variables ranging over the natural numbers) by a formula of L0 in Pn [respectively S ] as described in (1.i). Set D0n % P0n Thus: In fact, all these inclusions are proper. This hierarchy classifies the reals simple enough to be defined by arithmetic formulas. Example: ‘Dy x % y ! y’ defines the set even of even natural numbers; the formula 1 S1, so even 1 S01; even is also defined by a formula in P1; so even 1 P01, giving even 1 D01. In fact, S01 % the class of recursively enumerable reals, and D10 % the class of recursive reals. The classification of reals under the arithmetic hierarchy reflects complexity of defining formulas; it differs from classification in terms of a notion of degree of unsolvability, that reflecting a notion of comparative computational complexity; but there are connections between these classifications.
The Arithmetic Hierarchy extends to sets of reals (using a free second-order variable in defining sentences). Example: ‘Dx (Xx & Dy y % x ! x)’ 1 S1 and defines the set of those reals with an even number; so that set 1 S01. (ii) The Analytical Hierarchy. Given a real A : A 1 Pn1 [S 11] if and only if A is defined (over the standard model of arithmetic with second-order variables ranging over all sets of natural numbers) by a formula of L1 in Pn (respectively Sn) as described in (1.ii); D1n % Pn1 3 Sn1. Similarly for a set of reals. The inclusions pictured above carry over, replacing superscripted 0’s by 1’s. This classifies all reals and sets of reals simple enough to have analytical (i.e., second-order arithmetic) definitions.
The subscripted ‘n’ in ‘Pn0’, etc., ranged over natural numbers. But the Arithmetic Hierarchy is extended ‘upward’ into the transfinite by the ramified-analytical hierarchy. Let R0 % the class of all arithmetical reals. For an ordinal a let Ra!1 % the class of all sets of reals definable by formulas of L1 in which second-order variables range only over reals in Ra – this constraint imposes ramification. For a limit-ordinal l, let Rl % UaThe above hierarchies arise in arithmetic. Similar hierarchies arise in pure set theory; e.g. by transferring the ‘process’ that produced the ramified analytical hierarchy to pure set theory we obtain the constructible hierarchy, defined by Gödel in his 1939 monograph on the continuum hypothesis.
See also DEGREE OF UNSOLVABILITY, MATH- EMATICAL ANALYSIS , SET THEOR. H.T.H.