Fundamental Results
The fundamental results of hyperarithmetic theory show that the three definitions above define the same collection of sets of natural numbers. These equivalences are due to Kleene.
Completeness results are also fundamental to the theory. A set of natural numbers is complete if it is at level of the analytical hierarchy and every set of natural numbers is many-one reducible to it. The definition of a complete subset of Baire space is similar. Several sets associated with hyperarithmetic theory are complete:
- Kleene's, the set of natural numbers that are notations for ordinal numbers
- The set of natural numbers e such that the computable function computes the characteristic function of a well ordering of the natural numbers. These are the indices of recursive ordinals.
- The set of elements of Baire space that are the characteristic functions of a well ordering of the natural numbers (using an effective isomorphism .
Results known as bounding follow from these completeness results. For any set S of ordinal notations, there is an such that every element of S is a notation for an ordinal less than . For any subset T of Baire space consisting only of characteristic functions of well orderings, there is an such that each ordinal represented in T is less than .
Read more about this topic: Hyperarithmetical Theory
Famous quotes containing the words fundamental and/or results:
“What is wanted—whether this is admitted or not—is nothing less than a fundamental remolding, indeed weakening and abolition of the individual: one never tires of enumerating and indicting all that is evil and inimical, prodigal, costly, extravagant in the form individual existence has assumed hitherto, one hopes to manage more cheaply, more safely, more equitably, more uniformly if there exist only large bodies and their members.”
—Friedrich Nietzsche (1844–1900)
“We do not raise our children alone.... Our children are also raised by every peer, institution, and family with which they come in contact. Yet parents today expect to be blamed for whatever results occur with their children, and they expect to do their parenting alone.”
—Richard Louv (20th century)