Is there an algorithm which for a formula P of PA outputs (sum^0_m)/(prod^0_m) such that the output is the level P belongs to in Arithmetical hierarchy? If that's not computable is there an algorithm which outputs an upper bound on the level?
iescabroussexg
Answered question
2022-09-07
Answer & Explanation
Francis Blanchard
Beginner2022-09-08Added 12 answers
Getting an upper bound is pretty easy: just put the formula into prenex normal form and count the quantifier types and alternations. This is something a computer can do.
Of course, the answer this gives will sometimes be silly. For example,
"is" , but we shouldn't think of it that way. So what's really being calculated is in some sense the "trivial" level of the arithmetical hierarchy that a formula lies in - what we get by simply performing basic logical operations and nothing else.
This is the best we can do, in a precise sense. Say that the optimal level of a formula , which I'll call " ," is the least n such that is equivalent to a formula or to a formula. Then it's not hard to show that the map
is not computable - we can't computably tell whether a given sentence is equivalent to a sentence, for example.
(Here by "equivalent" I could mean either "provably equivalent over PA" or "equivalent in the structure " - in either case, the point is the same.)
New Questions in Upper Level Math
If two angles of two triangles are congruent to each other, then the third angles will be congruent to each other. Using the above statement, choose which two congruency criteria eventually becomes same.
A)SAS and ASA;
B)AAS and SAS;
C)AAS and ASA;
D) No two congruency criteria are sameEvaluate
Solve the following differential equation dx/dy=-[(4y2+6xy)/(3y2+2x)]
The velocity distribution for laminar flow between parallel plates is given by:
where h is the distance separating the plates and the origin is placed midway between the plates. Consider a flow of water at , with and . Calculate the shear stress on the upper plate and give its direction.
In August 2013, E*TRADE Financial was offering only 0.05% interest on its online checking accounts, with interest reinvested monthly. Find the associated exponential model for the value of a $5000 deposit after "t" years. Assuming that this rate of return continued for 7 years, how much would a deposit of $5000 in August 2013 be worth in August 2020? (Answer to the nearest $1. )
Write an equivalent first-order differential equation and initial condition for y
y=−1+∫x1(t−y(t))dt
Is {8} ∈ {{8}, {8}}?
