A revision-theoretic analysis of the arithmetical hierarchy (Q1344437)

Let \(G(x_1, \dots, x_n, \varphi)\) be an arithmetical functional, and let \(\psi\) be a total function from \(\omega^n\) into \(\omega\). Define the \(\rho\)-revision of \(G\) under initial hypothesis \(\psi\) by induction on \(\rho\): \(G^\psi_0 (x_1, \dots, x_n) = \psi (x_1, \dots, x_n)\), \(G^\psi_{\rho + 1} (x_1, \dots, x_n) = G(x_1, \dots, x_n, G^\psi_\rho)\), and, for limit ordinals \(\lambda\), \[ G^\psi_\lambda (x_1, \dots, x_n) = \begin{cases} z \quad \text{if } (\exists \sigma < \lambda) (\forall \tau < \lambda) (\sigma < \tau \to G^\psi_\tau (x_1, \dots, x_n) = z); \\ \psi (x_1, \dots, x_n) \quad \text{otherwise.} \end{cases} \] For a non-successor ordinal \(\rho\), let \(G^\psi_{< \rho} (x) = y \Leftrightarrow (\exists \sigma < \rho) (\forall \tau < \rho) (\sigma \leq \tau \to G^\psi_\tau (x) = y)\). Given a fixed enumeration of the recursive functions, let \(\{c\}^A\) denote the recursive function whose code is \(c\) and whose oracle is \(A\). Let \(\text{Tot}^A = \{x : \{x\}^A\) is total\} and \(\text{Par}^A = \omega\)-\(\text{Tot}^A\). Finally, by induction, let \(\text{Par}^{(0)} = \emptyset\) and \(\text{Par}^{(n + 1)} = \text{Par}^{\text{Par}^{(n)}}\). The main result is that there are a recursive functional \(G\) and an arithmetical constraint \(P (\alpha)\) such that \(\forall n \forall \psi (P (\psi) \Rightarrow \text{Par}^{(n)} \leq_m G^\psi_{< \omega \cdot n})\), where \(\leq_m\) signifies many-one reducibility. Since \(G^\psi_{< \omega \cdot n}\) is \(\Sigma^0_{2n}\), this result is optimal. There is also a proof of the following strengthened result due to Anil Gupta. There is a recursive functional \(G\) such that \(\forall n \forall \psi [\text{Par}^{(n)} \leq_m G^\psi_{< \omega \cdot (n + 1)}]\).