9.1 Hyperarithmetical sets and functions

Hyperarithmetical sets and functions extend beyond the arithmetical hierarchy, providing a powerful tool for classifying sets based on their complexity. They play a fundamental role in recursion theory, offering a finer-grained analysis of sets that go beyond traditional arithmetic.

The hyperarithmetical hierarchy is built by iterating the Turing jump operator through recursive ordinals. This process generates increasingly complex sets at each stage, starting with computable sets and progressing through transfinite levels. Hyperarithmetical functions preserve this hierarchy, analogous to computable functions in simpler contexts.

Definition of hyperarithmetical sets

• Hyperarithmetical sets are a class of sets of natural numbers that extend beyond the arithmetical hierarchy
• They play a fundamental role in recursion theory and provide a powerful tool for classifying sets based on their complexity
• The definition of hyperarithmetical sets can be approached inductively or through equivalent characterizations

Inductive definition

Top images from around the web for Inductive definition

• 

  QuantumMeasurementOperator | Wolfram Function Repository View original

  Is this image relevant?

• 

  High-throughput mathematical analysis identifies Turing networks for patterning with equally ... View original

  Is this image relevant?

• 

  QuantumMeasurementOperator | Wolfram Function Repository View original

  Is this image relevant?

• 

  High-throughput mathematical analysis identifies Turing networks for patterning with equally ... View original

  Is this image relevant?

1 of 2

Top images from around the web for Inductive definition

• 

  QuantumMeasurementOperator | Wolfram Function Repository View original

  Is this image relevant?

• 

  High-throughput mathematical analysis identifies Turing networks for patterning with equally ... View original

  Is this image relevant?

• 

  QuantumMeasurementOperator | Wolfram Function Repository View original

  Is this image relevant?

• 

  High-throughput mathematical analysis identifies Turing networks for patterning with equally ... View original

  Is this image relevant?

1 of 2

• Hyperarithmetical sets are defined inductively using recursive ordinals and the Turing jump operator
• The inductive definition starts with the empty set and the set of natural numbers as initial hyperarithmetical sets
• At each stage $\alpha$ of the inductive definition, a new set is added to the collection of hyperarithmetical sets if it is Turing reducible to the $\alpha$-th Turing jump of a previously defined hyperarithmetical set
  • This process continues through all recursive ordinals, generating increasingly complex sets at each stage

Equivalent definitions

• Hyperarithmetical sets can be characterized in terms of definability in certain fragments of second-order arithmetic
• They are precisely the sets definable by $\Sigma^1_1$ formulas in the language of second-order arithmetic
  • $\Sigma^1_1$ formulas allow for existential quantification over sets of natural numbers
• Hyperarithmetical sets can also be defined as the sets computable by Turing machines with oracles for the Turing jump of a computable set
  • This characterization highlights the close connection between hyperarithmetical sets and the Turing jump operator

Hyperarithmetical hierarchy

• The hyperarithmetical hierarchy is a transfinite extension of the arithmetical hierarchy that classifies sets based on their complexity
• It provides a finer-grained analysis of sets that go beyond the arithmetical hierarchy

Recursive ordinals

• Recursive ordinals play a crucial role in the construction of the hyperarithmetical hierarchy
• They are ordinals that can be represented by computable well-orderings of natural numbers
• Each recursive ordinal corresponds to a stage in the inductive definition of hyperarithmetical sets
  • The first recursive ordinal is $\omega$, representing the first non-arithmetical stage
  • Subsequent recursive ordinals, such as $\omega+1$, $\omega+2$, and so on, represent higher stages in the hierarchy

Stages of inductive definitions

• The hyperarithmetical hierarchy is built by iterating the Turing jump operator through the recursive ordinals
• At stage 0, the hyperarithmetical sets are the computable sets
• At stage $\alpha+1$, a set is added to the hierarchy if it is Turing reducible to the $\alpha$-th Turing jump of a set from the previous stage
  • For example, at stage $\omega$, the sets are those Turing reducible to the $\omega$-th Turing jump of a computable set
• At limit stages, such as $\omega$, the hyperarithmetical sets are the union of the sets from all previous stages

Hyperarithmetical sets vs arithmetical sets

• Hyperarithmetical sets extend beyond the arithmetical sets and provide a more comprehensive classification of sets
• While arithmetical sets are defined using first-order formulas, hyperarithmetical sets require second-order formulas

Closure properties

• Hyperarithmetical sets possess strong closure properties that distinguish them from arithmetical sets
• The collection of hyperarithmetical sets is closed under Turing reducibility
  • If a set is Turing reducible to a hyperarithmetical set, then it is also hyperarithmetical
• Hyperarithmetical sets are closed under complementation, union, and intersection
  • The complement, union, and intersection of hyperarithmetical sets are also hyperarithmetical
• However, hyperarithmetical sets are not closed under projection, unlike arithmetical sets
  • There exist hyperarithmetical sets whose projections are not hyperarithmetical

Relationship to analytical hierarchy

• The hyperarithmetical hierarchy is closely related to the analytical hierarchy, which classifies sets based on their definability in second-order arithmetic
• Hyperarithmetical sets correspond to the $\Delta^1_1$ level of the analytical hierarchy
  • $\Delta^1_1$ sets are those that are both $\Sigma^1_1$ and $\Pi^1_1$ definable
• The analytical hierarchy extends beyond the hyperarithmetical sets, with higher levels such as $\Sigma^1_2$ and $\Pi^1_2$ sets

Hyperarithmetical functions

• Hyperarithmetical functions are functions that preserve the hyperarithmetical hierarchy
• They are the analogues of computable functions in the context of hyperarithmetical sets

Definition and properties

• A function $f: \mathbb{N} \rightarrow \mathbb{N}$ is hyperarithmetical if its graph $\{(x, f(x)) : x \in \mathbb{N}\}$ is a hyperarithmetical set
• Hyperarithmetical functions are closed under composition, primitive recursion, and minimization
  • The composition, primitive recursive definition, and minimization of hyperarithmetical functions yield hyperarithmetical functions
• Hyperarithmetical functions are not closed under the $\mu$-operator (unbounded search)
  • There exist hyperarithmetical functions whose unbounded search is not hyperarithmetical

Relationship to hyperarithmetical sets

• Hyperarithmetical functions and hyperarithmetical sets are closely related
• The image and preimage of a hyperarithmetical set under a hyperarithmetical function are also hyperarithmetical
  • If $f$ is hyperarithmetical and $A$ is hyperarithmetical, then $f(A)$ and $f^{-1}(A)$ are hyperarithmetical
• The characteristic function of a hyperarithmetical set is hyperarithmetical
  • If $A$ is hyperarithmetical, then its characteristic function $\chi_A(x) = 1$ if $x \in A$ and $0$ otherwise is hyperarithmetical

Hyperarithmetical degrees

• Hyperarithmetical degrees provide a way to classify sets based on their hyperarithmetical complexity
• They extend the notion of Turing degrees to the hyperarithmetical hierarchy

Definition and structure

• Two sets $A$ and $B$ are said to have the same hyperarithmetical degree if they are hyperarithmetically equivalent
  • $A$ is hyperarithmetically reducible to $B$ and $B$ is hyperarithmetically reducible to $A$
• The hyperarithmetical degrees form a partially ordered structure under the hyperarithmetical reducibility relation
  • The least element is the degree of computable sets, denoted by $\mathbf{0}_h$
  • The greatest element is the degree of complete hyperarithmetical sets, denoted by $\mathbf{0}^{(\omega)}_h$

Relationship to Turing degrees

• The hyperarithmetical degrees provide a finer-grained analysis than Turing degrees
• Every Turing degree is contained in a hyperarithmetical degree
  • Sets that are Turing equivalent may have different hyperarithmetical degrees
• There are hyperarithmetical degrees that are not Turing degrees
  • Some hyperarithmetical sets are not Turing equivalent to any computable set

Complete hyperarithmetical sets

• Complete hyperarithmetical sets are sets that encode the entire hyperarithmetical hierarchy
• They are the most complex sets within the hyperarithmetical hierarchy

Existence and properties

• There exist complete hyperarithmetical sets, also known as $\Sigma^1_1$-complete sets
• A set $A$ is $\Sigma^1_1$-complete if every $\Sigma^1_1$ set is hyperarithmetically reducible to $A$
  • $\Sigma^1_1$-complete sets are at the top of the hyperarithmetical hierarchy
• $\Sigma^1_1$-complete sets are not hyperarithmetical themselves
  • They properly extend the hyperarithmetical hierarchy

Examples of complete sets

• The set of Gödel numbers of true $\Sigma^1_1$ sentences in second-order arithmetic is $\Sigma^1_1$-complete
  • This set encodes the truth of all $\Sigma^1_1$ statements
• The set of indices of computable well-orderings of $\omega_1^{CK}$, the first non-recursive ordinal, is $\Sigma^1_1$-complete
  • This set captures the complexity of computable well-orderings beyond the recursive ordinals

Hyperarithmetical forcing

• Hyperarithmetical forcing is a technique used to construct hyperarithmetical sets with specific properties
• It extends the notion of Cohen forcing from set theory to the hyperarithmetical hierarchy

Basic concepts and definitions

• Hyperarithmetical forcing uses conditions, which are finite approximations of hyperarithmetical sets
• A condition $p$ is stronger than a condition $q$ if $p$ extends $q$ with more information about the set being constructed
• A set $G$ is generic for a collection of conditions $\mathcal{P}$ if it meets every dense subset of $\mathcal{P}$
  • Dense subsets are collections of conditions that can always be extended to include more information

Applications in recursion theory

• Hyperarithmetical forcing can be used to construct hyperarithmetical sets with specific properties, such as:
  • Sets that are not Turing equivalent to any arithmetical set
  • Sets that are not Turing reducible to any hyperarithmetical set in a lower stage of the hierarchy
• Hyperarithmetical forcing provides a powerful tool for studying the structure and properties of the hyperarithmetical hierarchy
  • It allows for the construction of sets that exhibit certain independence or incomparability results

Hyperarithmetical reducibility

• Hyperarithmetical reducibility is a notion of reducibility that captures the relative complexity of sets within the hyperarithmetical hierarchy
• It extends Turing reducibility to the transfinite levels of the hyperarithmetical hierarchy

Definition and properties

• A set $A$ is hyperarithmetically reducible to a set $B$, denoted by $A \leq_h B$, if there exists a hyperarithmetical function $f$ such that $x \in A \Leftrightarrow f(x) \in B$
• Hyperarithmetical reducibility is reflexive, transitive, and well-founded
  • Every set is hyperarithmetically reducible to itself
  • If $A \leq_h B$ and $B \leq_h C$, then $A \leq_h C$
  • There are no infinite descending chains of sets under hyperarithmetical reducibility

Relationship to other reducibilities

• Hyperarithmetical reducibility is stronger than Turing reducibility
  • If $A$ is hyperarithmetically reducible to $B$, then $A$ is Turing reducible to $B$
  • The converse does not hold in general
• Hyperarithmetical reducibility is weaker than arithmetic reducibility
  • If $A$ is arithmetically reducible to $B$, then $A$ is hyperarithmetically reducible to $B$
  • The converse does not hold in general

Advanced topics in hyperarithmetical theory

• Hyperarithmetical theory leads to various advanced topics and generalizations in recursion theory
• These topics explore the limits of hyperarithmetical sets and their connections to other areas of logic and mathematics

Higher recursion theory

• Higher recursion theory studies the notions of computability and definability beyond the hyperarithmetical hierarchy
• It investigates the properties of sets and functions defined using higher-order recursion schemes
• Higher recursion theory includes the study of:
  • The analytical hierarchy and its extensions
  • Inductive definitions and fixed points in higher-order arithmetic
  • Generalized recursion theory and $\alpha$-recursion theory

Generalizations of hyperarithmetical sets

• Several generalizations of hyperarithmetical sets have been studied, extending the concepts to broader contexts:
  • $\Delta^1_1$ sets in the analytical hierarchy
  • Hyperprojective sets, which extend hyperarithmetical sets using projective determinacy
  • $\Sigma^1_1$ sets and the Borel hierarchy in descriptive set theory
• These generalizations provide a richer framework for studying the complexity and structure of sets beyond the hyperarithmetical hierarchy
  • They reveal connections between recursion theory, descriptive set theory, and proof theory