Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Skolemization requires some external set theory. If you want to work strictly inside PA, you want to be able to classify formulas and say something about that too. – Asaf Karagila Aug 3 '12 at 14:01
Asaf: 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.) – MikeC Aug 3 '12 at 20:49
up vote 5 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.