Hyperarithmetical is Effectively (co)-Analytic
The purpose of this blog post is to explain why hyperarithmetic definability exactly agrees with definability at the \(\Delta^1_1\) level of the analytical hierarchy. We follow the steps laid out in Computable Structure Theory: Beyond the arithmetic by Antonio Montalbán (the Draft form from September 23, 2022). This topic sits within Descriptive Set Theory and Computable Structure Theory.
The first approach is via computable versions of infinitary formulas of arithmetic: any set definable by such a formula will be referred to as hyperarithmetic. The second approach follows the second order arithmetic equivalent of the arithmetical hierarchy. The analogy goes that just as the computable sets occupy the \(\Delta^0_1\) level of the arithmetical hierarchy [see Post’s Theorem identifying c.e.-ness and \(\Sigma^0_1\)], the sets definable by computable infinitary formulas will occupy the \(\Delta^1_1\) level of the analytical hierarchy.
The Hierarchies
Arithmetical Hierarchy
Sets definable in terms of arithmetic predicates and quantifiers in first-order Peano arithmetic. The hierarchy classifies sets based on their definability using these formulas.
These are the lightface \(\Sigma^0_n, \Pi^0_n, \Delta^0_n\) with no set parameters, with the lowest level being those first-order formulas with bounded quantifiers or quantifier free in the language of arithmetic; and the next highest level \(\Delta^0_1\) being the recursive sets, the intersection of c.e. (effectively open) and co-c.e. (effectively closed) sets. The quantifiers \(\exists\) and \(\forall\) are what bring us up the hierarchy according to prenex form.
Recall that sets like the iterated Turing jumps \(\varnothing^{(n)}\) of the empty set are each \(\Sigma^0_n\)-complete by Post’s Theorem (every \(\Sigma^0_n\) set is many-one reducible to \(\varnothing^{(n)}\)).
There is a boldface version corresponding to relativizations of these classes to include access to a membership predicate to a given subset of \(\N\) as part of the language; these form the Borel hierarchy denoted \(\mathbf{\Sigma}^0_n, ...\) or \(\underset{\sim}{\Sigma}^0_n\)… The Borel hierarchy emerged to categorize (Borel) sets based on their topological complexity using open and closed sets, which are the \(\mathbf{\Sigma}^0_1\) and \(\mathbf{\Pi}^0_1\) levels of the Borel hierarchy, respectively. We equivalently view the arithmetical hierarchy as the effectivization or lightface version of the Borel hierarchy.
Analytical Hierarchy
Expanding beyond arithmetic, analytical sets classify sets based on their complexity in second order arithmetic, of course placing the entire (first-order) arithmetic hierarchy at the level of \(\Sigma^1_0\)… The most basic yet nontrivial level of the analytical hierarchy would then be its \(\Delta^1_1\) which has been shown to have some nice properties according to our last few talks.
There is also a boldface version of the analytical hierarchy also obtained by relativization to subsets of \(\N\), called the projective hierarchy and denoted by \(\mathbf{\Sigma}^1_n\)… with most basic sets being the Borel sets (of the entire Borel hierarchy) at the \(\mathbf{\Sigma^1_0}\) level, the intersection of analytic and co-analytic sets. Steps up involve projections of simpler sets onto one component, a sort of stronger \(\exists\) quantification.
We’ll then view our main result as an effective analogy of the statement that the first nontrivial level \(\mathbf{\Delta}^1_1\) of the projective hierarchy are the Borel sets: the first nontrivial level \(\Delta^1_1\) of the analytical hierarchy is the hyperarithmetic sets.
In Chapter III of the reference, it is explained why Kleene’s \(\mathcal{O}\), which is the set of indices \(\{ e \in \N : \Phi_e(x,y) \text{ computes the characteristic function of a W.O. on } \N \}\), is \(\Pi^1_1\)-complete, or complete amongst the lightface co-analytic subsets of \(\N\).
Another key result is \(\Sigma^1_1\)-bounding, which says that any \(\Sigma^1_1\) set of indices of well-orders of \(\N\) has a bounding computable ordinal \(\alpha < \omega_1^{\texttt{CK}}\) satisfying \(\mathcal{L}_e \preceq \alpha\); i.e., is a W.O. of order type strictly less than \(\alpha\), i.e., the set is a subset of \(\mathcal{O}_{\texttt{wo}\leq \alpha}\). Each \(\mathcal{O}_{\texttt{wo}\leq \alpha}\) is \(\Delta^1_1\) because we can define it in both \(\Sigma^1_1\) and \(\Pi^1_1\) ways.
A corollary of \(\Sigma^1_1\)-bounding generalizing this fact is \(\Sigma^1_1\)-separation, which implies for us that any \(\Delta^1_1\) set is many-to-one reducible to some \(\mathcal{O}_{\texttt{wo}\leq \alpha}\) using the same bounding \(\alpha < \omega_1^{\texttt{CK}}\) which depends on the set. So this is a sort of finer, bounded version of \(\Pi^1_1\) completeness of \(\mathcal{O}_{\texttt{wo}}\).
\(\mathcal{L}{\omega_1, \omega}\) Hierarchy and its Computable Sub-Hierarchy
Already introduced by this point would be a way to work within the language of infinitary formulas, not just finitary ones, as a means to study the computational properties of structures syntactically. Given a vocabulary \(\tau\), it is defined \(\mathcal{L}_{\omega_1, \omega}\) over \(\tau\) to be comprised of formulas built from normal finitary language of quantifiers plus countable conjunctions and disjunctions of infinite sets of formulas which further maintain a finite number of free variables. There is a process for judging the quantifier complexity of such infinitary formulas where \(\bigwedge\mkern-13mu\bigwedge\) acts like \(\forall\) and \(\bigvee\mkern-13mu\bigvee\) acts like \(\exists\) in terms of formula complexity. These complexity classes are denoted \(\Sigma^{\texttt{in}}_\alpha\), with the lowest level being the finitary QF formulas.
Infinitary formulas can be represented by well-founded trees which branch by the introduction of quantifiers \(\forall, \exists, \bigvee\mkern-13mu\bigvee, \bigwedge\mkern-13mu\bigwedge\), plus a function keeping track of the free variables at each node. One may attempt to (necessarily uniquely) evaluate these formulas following obvious rules of (infinitary) logic, specifying precisely what we mean by the satisfiability relation \(\mathcal{A} \models \varphi(\bar{a})\) for any structure \(\mathcal{A}\), tuple \(\bar{a}\) in \(\operatorname{dom}(\mathcal{A})\), and formula \(\varphi(\bar{x})\). It follows that deciding \(\mathcal{A} \models \varphi(\bar{a})\) is a \(\Sigma^1_1\) property for we would need to 2nd order existentially quantify to make sure there exists a valid valuation of \(\mathcal{A}\), while checking validity is already an arithmetical property. (It’s \(\Pi^1_1\) too by uniqueness of valuations).
We will only focus on the subset of \(\mathcal{L}_{\omega_1, \omega}\) consisting of infinitary formulas with computable tree representations, called \(\mathcal{L}_{\texttt{c}, \omega}\), althought maybe it should be notated \(\mathcal{L}_{\omega_1^{\texttt{CK}}, \omega}\). So we think of the subset \(\Sigma^{\texttt{c}}_\alpha\) within the complexity class \(\Sigma^{\texttt{in}}_\alpha\) as the collection of computable infinitary \(\Sigma_\alpha\) formulas, meaning there is a computable ranking function assigning \(\Sigma^\texttt{c}_\alpha\) to the root of the tree.
Hyperarithmetical Hierarchy
Our definition of hyperarithmetic sets will arise by extending the arithmetical hierarchy to computable ordinals just shy of \(\omega_1^{\texttt{CK}}\) using computable infinitary formulas.
Call \(\mathcal{N} := (\N; +, \times, 0, 1, \leq)\) whose elements are always denoted by \(\underline{\mathbf{n}}\).
Arithmetic Set \(A \subseteq \N\): there exists a 1st order formula in the vocabulary of arithmetic (\(\mathcal{N}\)) defining \(A\).
Hyperarithmetic Set \(A \subseteq \N\): there exists a computable infinitary formula in the vocabulary of arithmetic (\(\mathcal{N}\)) defining \(A\).
Trivially, \(\text{Arithmetic} \subseteq \text{Hyperarithmetic} =: \mathsf{HYP}\), and we find a separating example in \(\varnothing^{(\omega)}\):
where \(\in \varnothing^{(k)}\) has a \(\Sigma^0_k\) \(\mathcal{N}\)-formula which is certainly computable infinitary.
The entire formula I wrote is \(\Sigma^\texttt{c}_\omega\), which we’ll define as making the set \(\Sigma^0_\omega\), which is a subset of \(\mathsf{HYP}\).
Hyperarithmetic sets were introduced independently in the early 1950s by Martin Davis, Andrej Mostowski, and Stephen Cole Kleene.
We notice three important properties of the class of hyperarithmetic sets:
if we let \(\varphi\) be a computable infinitary formula defining \(X \in \mathsf{HYP}\), and if we let “\(\sigma \prec X\)” abbreviate \(\displaystyle \bigwedge_{i < \mid \sigma \mid,\ \sigma(i) = 1} \varphi(i) \ \wedge \ \bigwedge_{i < \mid \sigma \mid,\ \sigma(i) = 0} \neg \varphi(i)\), meaning finite binary string \(\sigma\) logically agrees with \(\varphi\) across its bits, then
You can’t escape \(\mathsf{HYP}\) by Turing jumps:
\(\mathsf{HYP}\) has downward closure w.r.t. Turing reducibility
Any computable infinitary formula can be expressed using just number symbols, the logical connectives, infinitary conjuncts/disjuncts, and \(=\). I.e., being hyperarithmetic is equivalent to there being a computable list of computable infinitary sentences \((\varphi_n)\) in the “empty” vocabulary such that \(n \in X \iff \varphi_n\) holds. I.e., \(A\) definable by comp inf formula \(\longleftrightarrow\) definable by \((\varphi_n)\) infinitary propositional sentences. Actually, \(A\) definable by \(\Sigma^\texttt{c}_\alpha\) formula \(\longleftrightarrow\) definable by \(\Sigma^\texttt{c}_\alpha\) \((\varphi_n)\) infinitary propositional sentences.
Such a list of propositional sentences produces a computable infinitary formula of arithmetic for \(X\): \(\displaystyle \varphi(x) \equiv \bigwedge\mkern-17mu\bigwedge_{n \in \N} \left((x=\underline{\mathbf{n}}) \rightarrow \varphi_n \right)\), because \(\varphi(x)\) holds iff \(x\)-th sentence holds iff \(x \in X\) by assumption.
\((\Rightarrow)\)
Remove \(+, \times, \leq\):
Any formula \(\varphi\) over \(\mathcal{N}\) can have its operation and relation symbols \(+, \times, \leq\) removed through the simple trick of replacing in any sub-formula of the form \(x +y=z\), \(x \times y = z\), \(x \leq y\) in the following manner: \(\displaystyle \bigvee\mkern-25mu\bigvee_{\substack{a, b, c \in \N\\a + b = c}} [x = \underline{\mathbf{a}} \ \wedge \ y = \underline{\mathbf{b}} \ \wedge \ z = \underline{\mathbf{c}}]\). The infinitary conjunction/disjunction is able to iterate only over the desired tuples (computable to detect these tuples), removing the need for the formula to perform operations or check the \(\leq\) relation.
Remove \(\forall, \exists\):
A similar strategy works to remove quantification: \(\forall x\ \psi(x)\) would be replaced by \(\displaystyle \bigwedge\mkern-17mu\bigwedge_{n \in \N} \psi(\underline{\mathbf{m}})\); opposite for \(\exists\).
Formulas to Sentences:
These conversions leave us only to consider those formulas \(\varphi(x)\) with a single free number variable an no relation, operation, or quantifications symbols: simply produce the computable infinitary sentence \(\varphi_n := \varphi(\underline{\mathbf{n}})\) for each \(n\), having no variables. The only atomic sub-formulas we should find will be of the form \(\underline{\mathbf{a}} = \underline{\mathbf{b}}\) for some \(a, b \in \N\), which can be replaced with stand-ins for True and False, say, \(\displaystyle \bigwedge\mkern-17mu\bigwedge_{x \in \varnothing} \underline{\mathbf{x}}\) and \(\displaystyle \bigvee\mkern-17mu\bigvee_{x \in \varnothing} \underline{\mathbf{x}}\), respectively. These \(\varphi_n\) hold iff \(n \in X\) because all of our replacements maintained truth.
Note: Also notice that each of these conversions maintains the complexity of the formula in the infinitary formulas hierarchy, so we could edit the statement to say for any \(\alpha > 0\), \(A\) can be defined by a \(\Sigma^{\texttt{c}}_\alpha\) formula of arithmetic (i.e., is hyperarithmetic) iff there is a computable sequence of \(\Sigma^{\texttt{c}}_\alpha\) sentences over the empty language satisfying the same holding property.
Let us define the levels of the hyperarithmetic hierarchy by their definability by computable infinitary formulas of arithmetic:
We say \(A \subseteq \N\) is \(\Sigma^0_\alpha\) if it is definable by a \(\Sigma^{\texttt{c}}_\alpha\) formula of arithmetic (i.e., an \(\mathcal{N}\)-formula). So \(\mathsf{HYP}\) is comprised of all of the \(\Sigma^0_{\alpha}\) for \(\alpha < \omega_1^{\texttt{CK}}\).
Note: when \(\alpha\) is finite, this definition agrees with the usual arithmetical hierarchy by checking definitions.
Results on the Hyperarithmetical Hierarchy
\(\mathcal{A}\) is a computable \(\omega\)-presentation of a \(\tau\)-structure and \(\varphi^\tau(\bar{x})\) is a \(\Sigma^{\texttt{c}}_\alpha\) \(\tau\)-formula, \(\alpha \geq 1\).
Lemma 1 [Easy to find the satisfying arguments of formula]: \(\set{\bar{a} : \mathcal{A} \models \varphi^\tau(\bar{a})}\) is \(\Sigma^0_\alpha\)
We’ll do the \(\Sigma^{\texttt{c}}_1\) case (\(\alpha = 1\)). Re-express \(\mathcal{A} \models\) by \(\mathcal{N} \models\) to show this set of satisfying tuples is \(\Sigma^0_1\). Surely any atomic formula of computable \(\mathcal{A}\) is replaceable by a computable (\(\Delta^\texttt{0}_1\)) version in \(\mathcal{N}\) which can be expressed in either a \(\Sigma^{\texttt{0}}_1\) or \(\Pi^{\texttt{0}}_1\) way according to our needs.
E.g., for the \(\Sigma^c_1\) \(\tau\)-formula \(\displaystyle \varphi^\tau(\bar{x}) = \bigvee\mkern-17mu\bigvee_{i \in \N} \exists \bar{y} \left[\psi_i^\tau(\bar{x}, \bar{y}) \ \wedge\ \theta^\tau_i(\bar{x}, \bar{y}) \right]\), where each \(\psi_i^\tau\) stands for a conjunction of atomic formulas and each \(\theta^\tau_i\) stands for the conjunction of negations of atomic formulas, replacing each atomic formula in \(\psi_i^\tau\) with \(\Sigma^{\texttt{0}}_1\) \(\mathcal{N}\)-formulas and each atomic formula in \(\theta^\tau_i\) with \(\Pi^{\texttt{0}}_1\) to write a new \(\mathcal{N}\)-formula \(\varphi^{\mathcal{N}}(\bar{x})\) still of complexity \(\Sigma^{\texttt{c}}_1\) and conserving \(\mathcal{A} \models \varphi^\tau(\bar{a})\) iff \(\mathcal{N} \models \varphi^{\mathcal{N}}(\bar{a})\), defining \(\set{\bar{a} : \mathcal{A} \models \varphi^\tau(\bar{a})}\) by the \(\Sigma^c_1\) formula:
\(\displaystyle \psi^{\mathcal{N}}(\bar{x}) := \bigvee\mkern-35mu\bigvee_{\bar{a} \subset \operatorname{dom}(\mathcal{A})} \left[(\bar{x} = \underline{\mathbf{\bar{a}}})\ \wedge\ \varphi^{\mathcal{N}}(\bar{a}) \right]\), making this set \(\Sigma^0_\alpha\) by definition.
The other cases for \(\alpha > 1\) follow by applying the same procedure to maximal \(\Sigma^\texttt{c}_1\), \(\Pi^\texttt{c}_1\) sub-formulas of \(\varphi\), transfinite induction.
Lemma 2 [Easy to find the satisfying indices for a sentence]: Given \(e\) an index of \(\mathcal{A}_e\), if \(\varphi^\tau\) is just a sentence, deciding the statement “\(\mathcal{A}_e \models \varphi^\tau\)” is \(\Sigma^0_\alpha\).
Lemma 1’s procedure shows how, along with \(\varphi^\tau\), we can perform \(e \mapsto D(\mathcal{A}_e) \equiv \Phi_e\) — total computable \(\mapsto\) a \(\Sigma^\texttt{c}_\alpha\) \(\mathcal{N}\)-sentence \(\varphi^{\mathcal{N}, e}\) such that \(\mathcal{A}_e \models \varphi^\tau\) iff \(\mathcal{N} \models \varphi^{\mathcal{N}, e}\).
Now \(\set{e: \mathcal{A}_e \models \varphi^\tau} = \set{e: \mathcal{N} \models \varphi^{\mathcal{N}, e}}\) definable by the still \(\Sigma^{\texttt{c}}_\alpha\) \(\mathcal{N}\)-formula \(\displaystyle \psi^{\mathcal{N}}(x) := \bigvee\mkern-17mu\bigvee_{e \in \N} \left[(x = \underline{\mathbf{e}})\ \wedge\ \varphi^{\mathcal{N}, e} \right]\). So membership in this set (i.e., the decision problem in the prompt) is a \(\Sigma^0_\alpha\) decision problem by definition.
Lemma 3 [Key Claim]: \(\mathcal{O}_{\texttt{wo} \leq \alpha}\) is hyperarithmetic for any computable ordinal \(\alpha\).
This holds because it is possible to write a computable infinitary \(\mathcal{N}\)-formula for a linear order to be a well order and of order type less than \(\alpha\), which is no more complex than \(\Sigma^{\texttt{c}}_{2 \beta}\), where \(\alpha \leq \omega^\beta\) [see Chapter II of the reference for the specific formula]. By Lemma 2, the set of such indices to these well orders of bounded order type is therefore no more complex than \(\Sigma^0_{2\beta}\), and, in particular, hyperarithmetic.
Theorem [Spector and Kleene’s \(\mathsf{HYP} = \Delta^1_1\)]: For any \(A \subset \N\), the following are equivalent:
(\(\textsf{HYP}\)) \(A\) is hyperarithmetic;
(\(\Delta^1_1\)) \(A\) is \(\Delta^1_1\);
(\(\leq_\texttt{m} \mathcal{O}_{\texttt{wo} \leq \alpha}\)) \(A \leq_\texttt{m} \mathcal{O}_{\texttt{wo} \leq \alpha}\) for some \(\alpha < \omega_1^{\texttt{CK}}\).
(\(\textsf{HYP}\)) \(\implies\)(\(\Delta^1_1\)): Suffices to show \(\mathsf{HYP} \implies \Sigma^1_1\) because the complement of a hyperarithmetic set is still hyperarithmetic. Recall that deciding whether an \(\omega\)-presentation of a structure satisfies some infinitary sentence is a \(\Sigma^1_1\) property. So from the point of view of the analytical hierarchy, deciding membership in a hyperarithmetic set is definable by a \(\Sigma^1_1\) formula applied to a computable infinitary formula, certainly \(\Sigma^1_1\).
(\(\Delta^1_1\)) \(\implies\)(\(\leq_\texttt{m} \mathcal{O}_{\texttt{wo}\leq\alpha}\)): This is a corollary of \(\Sigma^1_1\)-separation.
(\(\leq_\texttt{m} \mathcal{O}_{\texttt{wo}\leq\alpha}\))\(\implies\)(\(\textsf{HYP}\)): Follows because \(\mathcal{O}_{\texttt{wo}\leq\alpha}\) is hyperarithmetic (Lemma 3), \(\leq_\texttt{m}\) is stronger than \(\leq_\texttt{T}\), and \(\mathsf{HYP}\) is closed under \(\leq_\texttt{T}\).