So I didn’t mean to clarify what you meant by nth-order statements, but rather that BSS statements can decide them, because that seems way too strong to be true. I’m also a bit more skeptical because:
which then continues on the analytical hierarchy
is not true; the first level of the analytic hierarchy sits on top of the hyperarithmetic hierarchy. And my understanding is that finding a way to have an analagous picture of going from something like a “hyperanalytic hierarchy” to the bottom level of third order arithmetic is something highly non-trivial/impossible/ill-defined, but this isn’t my area of math. So I think it’s easier to ignore the hierarchy aspect and just consider nth-order statements that can be finitely expressed in the language of set theory involving the n-1st power set of N and lower. I would be very, very surprised if BSS machines could decide all such third-order statements but if you have a reference that implies it, I’d take a look.
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.
So I didn’t mean to clarify what you meant by nth-order statements, but rather that BSS statements can decide them, because that seems way too strong to be true. I’m also a bit more skeptical because:
is not true; the first level of the analytic hierarchy sits on top of the hyperarithmetic hierarchy. And my understanding is that finding a way to have an analagous picture of going from something like a “hyperanalytic hierarchy” to the bottom level of third order arithmetic is something highly non-trivial/impossible/ill-defined, but this isn’t my area of math. So I think it’s easier to ignore the hierarchy aspect and just consider nth-order statements that can be finitely expressed in the language of set theory involving the n-1st power set of N and lower. I would be very, very surprised if BSS machines could decide all such third-order statements but if you have a reference that implies it, I’d take a look.
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.
Alright, I’ll have to do homework today, so I can’t respond for now.