Isn’t the hyperarithmetic hierarchy just contained in 1 1 statements, or equivalently 0^w statements, where you decide the truth of all first-order arithmetic statements?
I will for now retract the claim that BSS machines can decide all third order statements, mostly because I don’t have a reference to the specific fact, but I would be very surprised if BSS machines couldn’t decide all third order arithmetic statements, or any order of arithmetic that can be finitely expressed in the language of set theory, because ZFC can define a truth predicate that works for all arithmetical statements, no matter which order of arithmetic you are considering, for the reason shown below, and all finitely expressible statements in the language of arithmetic or set theory are countable, while the amount of problems they can decide and the amount of functions they can solve are uncountable, so the BSS machine is larger than any formal theory of arithmetic or set theory that is finitary.
Isn’t the hyperarithmetic hierarchy just contained in 1 1 statements, or equivalently 0^w statements, where you decide the truth of all first-order arithmetic statements?
I think you have some significant gaps in your understanding. The 0ω statements contain all first-order arithmetic statements yes. But that’s just the beginning of the hyperarithmetic hierarchy. You can then discuss sentences that have a quantifier over 0ω statements, which are 0ω+1, and iterate this to to get 02ω . Then you can iterate again. Etc. Abstracting that process gets you to 0ω2. And you keep going again and again. This is still very low in the hyperarithmetic hierarchy.
My understanding (again, this is not my area) is that given any computable ordinal (i.e. any well-ordering of the naturals that can be encoded by the outputs of some Turing machine), you can construct a corresponding level of the hyperarithmetic hierarchy. So how do you discuss an arbitrary hyperarithmetical statement? You need to be able to quantify over the Turing machines that spit out well-orderings. Verifying that an ordering is a well-ordering requires quantifying over all subsequences—a second order statement. That’s why the abstraction of the hyperarithemic hierarchy is called the first level of the analytic hierarchy, the 1 1 statements as you said.
Isn’t the hyperarithmetic hierarchy just contained in 1 1 statements, or equivalently 0^w statements, where you decide the truth of all first-order arithmetic statements?
I will for now retract the claim that BSS machines can decide all third order statements, mostly because I don’t have a reference to the specific fact, but I would be very surprised if BSS machines couldn’t decide all third order arithmetic statements, or any order of arithmetic that can be finitely expressed in the language of set theory, because ZFC can define a truth predicate that works for all arithmetical statements, no matter which order of arithmetic you are considering, for the reason shown below, and all finitely expressible statements in the language of arithmetic or set theory are countable, while the amount of problems they can decide and the amount of functions they can solve are uncountable, so the BSS machine is larger than any formal theory of arithmetic or set theory that is finitary.
I think you have some significant gaps in your understanding. The 0ω statements contain all first-order arithmetic statements yes. But that’s just the beginning of the hyperarithmetic hierarchy. You can then discuss sentences that have a quantifier over 0ω statements, which are 0ω+1, and iterate this to to get 02ω . Then you can iterate again. Etc. Abstracting that process gets you to 0ω2. And you keep going again and again. This is still very low in the hyperarithmetic hierarchy.
My understanding (again, this is not my area) is that given any computable ordinal (i.e. any well-ordering of the naturals that can be encoded by the outputs of some Turing machine), you can construct a corresponding level of the hyperarithmetic hierarchy. So how do you discuss an arbitrary hyperarithmetical statement? You need to be able to quantify over the Turing machines that spit out well-orderings. Verifying that an ordering is a well-ordering requires quantifying over all subsequences—a second order statement. That’s why the abstraction of the hyperarithemic hierarchy is called the first level of the analytic hierarchy, the 1 1 statements as you said.