What's the point of classifying statements in an arithmetical hierarchy if you can use skolemization to construct equisatisfiable $\Pi^0_1$ formulas for any non-$\Pi^0_1$ formula?
Arithmetical hierarchy and skolemization
-
0Asaf: is there a set-theoretical analogue to cosatisfiability? I have no idea what it is. If there isn't one, doesn't working strictly inside PA tell us something we wouldn't know otherwise? (Ok, I'm confused. But I think it's related to the original question.) – 2012-08-03
1 Answers
An arithmetic set is a set of natural numbers definable by a first-order formula in the language of arithmetic, i.e. $(+,\cdot,0,1,=, \leq)$ (over the standard model of natural numbers).
People may add some other symbols to these using the definitional extension theorem and still call it arithmetic because the class of formulas are still equivalent (e.g. every $\Sigma_1$ formulas in the new language is equivalent to a $\Sigma_1$ formula in the original language). So what they really mean is that the new language is equivalent to the original language of arithmetic. Note that these are not arbitrary function symbols, they are defined by formulas with low logical complexity (e.g. by a $\Delta_1$ formula in the original language).
A $\Sigma_1$ formula in an extended language is denoted by adding the new symbols of the language as a post-fix, e.g. if we include the exponentiation function we use $\Sigma_1(\exp)$.
Skolemization changes the language by introducing new function symbols, and a $\Sigma_1$ formula in the new language is not the same as a $\Sigma_1$ formula in arithmetic. A $\Sigma_1$ formula in an arbitrary language doesn't necessarily define an arithmetic set.