Arithmetical hierarchy explained
Arithmetical hierarchy should not be confused with Levy 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 them. Any set that receives a classification is called arithmetical. The arithmetical hierarchy was invented independently by Kleene (1943) and Mostowski (1946).[1]
The arithmetical hierarchy is important in computability theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic.
The Tarski–Kuratowski algorithm provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines.
The hyperarithmetical hierarchy and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets.
The arithmetical hierarchy of formulas
The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted
and
for
natural numbers
n (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters.
If a formula
is
logically equivalent to a formula having no unbounded quantifiers, i.e. in which all quantifiers are bounded quantifiers then
is assigned the classifications
and
.
The classifications
and
are defined inductively for every natural number
n using the following rules:
is logically equivalent to a formula of the form
\existsm1\existsm2 … \existsmk\psi
, where
is
, then
is assigned the classification
.
is logically equivalent to a formula of the form
\forallm1\forallm2 … \forallmk\psi
, where
is
, then
is assigned the classification
.
A
formula is equivalent to a formula that begins with some
existential quantifiers and alternates
times between series of existential and
universal quantifiers; while a
formula is equivalent to a formula that begins with some universal quantifiers and alternates analogously.
Because every first-order formula has a prenex normal form, every formula is assigned at least one classification. Because redundant quantifiers can be added to any formula, once a formula is assigned the classification
or
it will be assigned the classifications
and
for every
m >
n. The only relevant classification assigned to a formula is thus the one with the least
n; all the other classifications can be determined from it.
Meaning of the notation
The following meanings can be attached to the notation for the arithmetical hierarchy on formulas.
The subscript
in the symbols
and
indicates the number of alternations of blocks of universal and existential first-order quantifiers that are used in a formula. Moreover, the outermost block is existential in
formulas and universal in
formulas.
The superscript
in the symbols
,
, and
indicates the type of the objects being quantified over. Type 0 objects are natural numbers, and objects of type
are functions that map the set of objects of type
to the natural numbers. Quantification over higher type objects, such as functions from natural numbers to natural numbers, is described by a superscript greater than 0, as in the
analytical hierarchy. The superscript 0 indicates quantifiers over numbers, the superscript 1 would indicate quantification over functions from numbers to numbers (type 1 objects), the superscript 2 would correspond to quantification over functions that take a type 1 object and return a number, and so on.
Examples
sets of numbers are those definable by a formula of the form
\existsn1 … \existsnk\psi(n1,\ldots,nk,m)
where
has only bounded quantifiers. These are exactly the
recursively enumerable sets.
- The set of natural numbers that are indices for Turing machines that compute total functions is
. Intuitively, an index
falls into this set if and only if for every
"there is an
such that the Turing machine with index
halts on input
after
steps". A complete proof would show that the property displayed in quotes in the previous sentence is definable in the language of
Peano arithmetic by a
formula.
subset of
Baire space or
Cantor space is an
open set in the usual
topology on the space. Moreover, for any such set there is a computable enumeration of
Gödel numbers of basic open sets whose union is the original set. For this reason,
sets are sometimes called
effectively open. Similarly, every
set is closed and the
sets are sometimes called
effectively closed.
- Every arithmetical subset of Cantor space or Baire space is a Borel set. The lightface Borel hierarchy extends the arithmetical hierarchy to include additional Borel sets. For example, every
subset of Cantor or Baire space is
a
set, that is, a set that equals the intersection of countably many open sets. Moreover, each of these open sets is
and the list of Gödel numbers of these open sets has a computable enumeration. If
is a
formula with a free set variable
and free number variables
then the
set
\{X\mid\foralln\existsm\phi(X,n,m)\}
is the intersection of the
sets of the form
\{X\mid\existsm\phi(X,n,m)\}
as
ranges over the set of natural numbers.
formulas can be checked by going over all cases one by one, which is possible because all their quantifiers are bounded. The time for this is polynomial in their arguments (e.g. polynomial in
for
); thus their corresponding decision problems are included in
E (as
is exponential in its number of bits). This no longer holds under alternative definitions of
that allow the use of
primitive recursive functions, as now the quantifiers may be bound by any primitive recursive function of the arguments.
formulas under an alternative definition, that allows the use of
primitive recursive functions with bounded quantifiers, correspond to sets of natural numbers of the form
for a primitive recursive function
. This is because allowing bounded quantifier adds nothing to the definition: for a primitive recursive
,
is the same as
, and
is the same as
f(0) ⋅ f(1) ⋅ \ldots ⋅ f(n)=0
; with
course-of-values recursion each of these can be defined by a single primitive recursive function.
The arithmetical hierarchy of sets of natural numbers
A set X of natural numbers is defined by a formula φ in the language of Peano arithmetic (the first-order language with symbols "0" for zero, "S" for the successor function, "+" for addition, "×" for multiplication, and "=" for equality), if the elements of X are exactly the numbers that satisfy φ. That is, for all natural numbers n,
n\inX\LeftrightarrowN\models\varphi(\underlinen),
where
is the numeral in the language of arithmetic corresponding to
. A set is definable in first-order arithmetic if it is defined by some formula in the language of Peano arithmetic.
Each set X of natural numbers that is definable in first-order arithmetic is assigned classifications of the form
,
, and
, where
is a natural number, as follows. If
X is definable by a
formula then
X is assigned the classification
. If
X is definable by a
formula then
X is assigned the classification
. If
X is both
and
then
is assigned the additional classification
.
Note that it rarely makes sense to speak of
formulas; the first quantifier of a formula is either existential or universal. So a
set is not necessarily defined by a
formula in the sense of a formula that is both
and
; rather, there are both
and
formulas that define the set. For example, the set of odd natural numbers
is definable by either
or
.
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the set of natural numbers. Instead of formulas with one free variable, formulas with k free first-order variables are used to define the arithmetical hierarchy on sets of k-tuples of natural numbers. These are in fact related by the use of a pairing function.
Relativized arithmetical hierarchies
Just as we can define what it means for a set X to be recursive relative to another set Y by allowing the computation defining X to consult Y as an oracle we can extend this notion to the whole arithmetic hierarchy and define what it means for X to be
,
or
in
Y, denoted respectively
,
and
. To do so, fix a set of natural numbers
Y and add a
predicate for membership of
Y to the language of Peano arithmetic. We then say that
X is in
if it is defined by a
formula in this expanded language. In other words,
X is
if it is defined by a
formula allowed to ask questions about membership of
Y. Alternatively one can view the
sets as those sets that can be built starting with sets recursive in
Y and alternately taking
unions and
intersections of these sets up to
n times.
For example, let Y be a set of natural numbers. Let X be the set of numbers divisible by an element of Y. Then X is defined by the formula
\phi(n)=\existsm\existst(Y(m)\landm x t=n)
so
X is in
(actually it is in
as well, since we could bound both quantifiers by
n).
Arithmetic reducibility and degrees
Arithmetical reducibility is an intermediate notion between Turing reducibility and hyperarithmetic reducibility.
A set is arithmetical (also arithmetic and arithmetically definable) if it is defined by some formula in the language of Peano arithmetic. Equivalently X is arithmetical if X is
or
for some natural number
n. A set
X is arithmetical in a set
Y, denoted
, if
X is definable as some formula in the language of Peano arithmetic extended by a predicate for membership of
Y. Equivalently,
X is arithmetical in
Y if
X is in
or
for some natural number
n. A synonym for
is:
X is
arithmetically reducible to
Y.
The relation
is
reflexive and
transitive, and thus the relation
defined by the rule
X\equivAY\iffX\leqAY\landY\leqAX
is an
equivalence relation. The
equivalence classes of this relation are called the
arithmetic degrees; they are
partially ordered under
.
The arithmetical hierarchy of subsets of Cantor and Baire space
The Cantor space, denoted
, is the set of all infinite sequences of 0s and 1s; the
Baire space, denoted
or
, is the set of all infinite sequences of natural numbers. Note that elements of the Cantor space can be identified with sets of natural numbers and elements of the Baire space with functions from natural numbers to natural numbers.
The ordinary axiomatization of second-order arithmetic uses a set-based language in which the set quantifiers can naturally be viewed as quantifying over Cantor space. A subset of Cantor space is assigned the classification
if it is definable by a
formula. The set is assigned the classification
if it is definable by a
formula. If the set is both
and
then it is given the additional classification
. For example, let
be the set of all infinite binary strings that aren't all 0 (or equivalently the set of all non-empty sets of natural numbers). As
O=\{X\in2\omega|\existsn(X(n)=1)\}
we see that
is defined by a
formula and hence is a
set.
Note that while both the elements of the Cantor space (regarded as sets of natural numbers) and subsets of the Cantor space are classified in arithmetic hierarchies, these are not the same hierarchy. In fact the relationship between the two hierarchies is interesting and non-trivial. For instance the
elements of the Cantor space are not (in general) the same as the elements
of the Cantor space so that
is a
subset of the Cantor space. However, many interesting results relate the two hierarchies.
There are two ways that a subset of Baire space can be classified in the arithmetical hierarchy.
- A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from
to
to the
characteristic function of its graph. A subset of Baire space is given the classification
,
, or
if and only if the corresponding subset of Cantor space has the same classification.
- An equivalent definition of the arithmetical hierarchy on Baire space is given by defining the arithmetical hierarchy of formulas using a functional version of second-order arithmetic; then the arithmetical hierarchy on subsets of Cantor space can be defined from the hierarchy on Baire space. This alternate definition gives exactly the same classifications as the first definition.
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of Baire space or Cantor space, using formulas with several free variables. The arithmetical hierarchy can be defined on any effective Polish space; the definition is particularly simple for Cantor space and Baire space because they fit with the language of ordinary second-order arithmetic.
Note that we can also define the arithmetic hierarchy of subsets of the Cantor and Baire spaces relative to some set of natural numbers. In fact boldface
is just the union of
for all sets of natural numbers
Y. Note that the boldface hierarchy is just the standard hierarchy of
Borel sets.
Extensions and variations
It is possible to define the arithmetical hierarchy of formulas using a language extended with a function symbol for each primitive recursive function. This variation slightly changes the classification of
, since using primitive recursive functions in first-order Peano arithmetic requires, in general, an unbounded existential quantifier, and thus some sets that are in
by this definition are strictly in
by the definition given in the beginning of this article. The class
and thus all higher classes in the hierarchy remain unaffected.
A more semantic variation of the hierarchy can be defined on all finitary relations on the natural numbers; the following definition is used. Every computable relation is defined to be
. The classifications
and
are defined inductively with the following rules.
R(n1,\ldots,nl,m1,\ldots,mk)
is
then the relation
S(n1,\ldots,nl)=\forallm1 … \forallmkR(n1,\ldots,nl,m1,\ldots,mk)
is defined to be
R(n1,\ldots,nl,m1,\ldots,mk)
is
then the relation
S(n1,\ldots,nl)=\existsm1 … \existsmkR(n1,\ldots,nl,m1,\ldots,mk)
is defined to be
This variation slightly changes the classification of some sets. In particular,
, as a class of sets (definable by the relations in the class), is identical to
as the latter was formerly defined. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.
Properties
The following properties hold for the arithmetical hierarchy of sets of natural numbers and the arithmetical hierarchy of subsets of Cantor or Baire space.
and
are closed under finite
unions and finite
intersections of their respective elements.
if and only if its complement is
. A set is
if and only if the set is both
and
, in which case its complement will also be
.
and
hold for all
. Thus the hierarchy does not collapse. This is a direct consequence of
Post's theorem.
,
and
hold for
.
(being computable with an oracle to the halting problem) but not in
.
. The inclusion is strict by the definition given in this article, but an identity with
holds under one of the variations of the definition given above.
Relation to Turing machines
See also: Post's theorem.
Computable sets
If S is a Turing computable set, then both S and its complement are recursively enumerable (if T is a Turing machine giving 1 for inputs in S and 0 otherwise, we may build a Turing machine halting only on the former, and another halting only on the latter).
By Post's theorem, both S and its complement are in
. This means that
S is both in
and in
, and hence it is in
.
Similarly, for every set S in
, both
S and its complement are in
and are therefore (by
Post's theorem) recursively enumerable by some Turing machines
T1 and
T2, respectively. For every number
n, exactly one of these halts. We may therefore construct a Turing machine
T that alternates between
T1 and
T2, halting and returning 1 when the former halts or halting and returning 0 when the latter halts. Thus
T halts on every
n and returns whether it is in
S; so
S is computable.
Summary of main results
The Turing computable sets of natural numbers are exactly the sets at level
of the arithmetical hierarchy. The recursively enumerable sets are exactly the sets at level
.
No oracle machine is capable of solving its own halting problem (a variation of Turing's proof applies). The halting problem for a
oracle in fact sits in
.
Post's theorem establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the Turing degrees. In particular, it establishes the following facts for all n ≥ 1:
(the
nth
Turing jump of the empty set) is
many-one complete in
.
is many-one complete in
.
is
Turing complete in
.
The polynomial hierarchy is a "feasible resource-bounded" version of the arithmetical hierarchy in which polynomial length bounds are placed on the numbers involved (or, equivalently, polynomial time bounds are placed on the Turing machines involved). It gives a finer classification of some sets of natural numbers that are at level
of the arithmetical hierarchy.
See also
References
Notes and References
- P. G. Hinman, Recursion-Theoretic Hierarchies (p.89), Perspectives in Logic, 1978. Springer-Verlag Berlin Heidelberg, ISBN 3-540-07904-1.