Now that the original comment has changed, I’m more unsure about what you exactly you mean. Can you be more precise about what you mean by being able to compute arbitrary nth-order arithmetical statements? Is there a BSS machine that halts if and only if CH is true? Is there a BSS machine that halts if and only if there’s a choice function on the set of non-empty subsets of R?
I admit, I haven’t found any such explicit examples yet.
I wish this was more of a common practice to give explicit examples of these mathematical statements in more computational terms.
For the Nth order arithmetical statement issue, what I’m talking about is essentially a generalization of the arithmetical hierarchy, where there’s 0 1, 0 2, 0 3 and so on defined here, until it stops at 0^w, which then continues on the analytical hierarchy from 1 1, 1 2, 1 3, until it too stops at 1^w, which can go on essentially forever.
Essentially, I’m talking about this in a generalized form:
The formal reason why a BSS machine can compute all of this comes down, in the end to the fact that it can compute every function from the natural numbers to the natural numbers, which as a set is always larger than any arithmetical hierarchy, which means that the claim that we can always compute nth order arithmetic for any N follows easily.
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.
Now that the original comment has changed, I’m more unsure about what you exactly you mean. Can you be more precise about what you mean by being able to compute arbitrary nth-order arithmetical statements? Is there a BSS machine that halts if and only if CH is true? Is there a BSS machine that halts if and only if there’s a choice function on the set of non-empty subsets of R?
I admit, I haven’t found any such explicit examples yet.
I wish this was more of a common practice to give explicit examples of these mathematical statements in more computational terms.
For the Nth order arithmetical statement issue, what I’m talking about is essentially a generalization of the arithmetical hierarchy, where there’s 0 1, 0 2, 0 3 and so on defined here, until it stops at 0^w, which then continues on the analytical hierarchy from 1 1, 1 2, 1 3, until it too stops at 1^w, which can go on essentially forever.
Essentially, I’m talking about this in a generalized form:
https://en.wikipedia.org/wiki/Arithmetical_hierarchy
The formal reason why a BSS machine can compute all of this comes down, in the end to the fact that it can compute every function from the natural numbers to the natural numbers, which as a set is always larger than any arithmetical hierarchy, which means that the claim that we can always compute nth order arithmetic for any N follows easily.
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.