2
votes
2answers
78 views

Why does undecidability of arithmetic not follow from that of first-order logic?

As far as I understand, first-order arithmetic incorporates first-order logic. It is a fact that a first-order logic with at least two binary predicates is undecidable. Doesn't this imply immediately ...
4
votes
1answer
151 views

Is every φ above the second level of the arithmetical hierarchy independent of PA?

If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a ...
1
vote
3answers
187 views

What is it wrong in this argument about the interpretability hierarchy?

This is a question that I fully reedited to make it more precise. Many thanks to the people that answered the previous version to get this distilled one. Background: (from ...
1
vote
1answer
75 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n? This is a follow up from a previous question: Given a φ independent of PA which is true ...
9
votes
1answer
188 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent? Does it mean that every such ¬φ can be used to prove that a Turing machine halts on a given C ...
4
votes
1answer
155 views

Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$?

There is a recursive definition of the set of squares which uses only addition: $CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x \lt z) \wedge (z \lt y)⇒\neg IS(z)$ $IS(x)⇔ x=0 ...