Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

According to Wikipedia (and it seems intuitive from the definition itself), $\Omega$ is Turing equivalent to the halting problem and thus at level $\Delta_2^0$ of the arithmetical hierarchy. Do this mean that we can compute all digits of $\Omega$ if we had a $\Sigma_1$-Oracle? (or should it be a $\Sigma_2$-Oracle to include all $\Pi_2$ statements, which are equivalent to $\Sigma_3$ statements, I am still confused about this detail).

If so, the claim that the number of known digits of $\Omega$ gives some measure of the strength of a theory doesn't make sense. The number of known digits of $\Omega$ could only discriminate among the strengths of different theories of the kind T=PA+$\Psi$, where $\Psi$ is a subset of all possible $\Sigma_2$ statements, but cannot measure anything if the theory include axioms of complexity $\Sigma_3^0$ and above. Which is very low in theory strength (not to mention if we include higher levels, entering the analytical hierarchy). Is this correct?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Yes, $\Omega$ is computable from $0'$. The set $0'$ is $\Sigma^0_1$, so if you have access any other $\Sigma^0_1$ complete set you can also compute all the digits of $\Omega$. Thus the set of numbers coded by the digits of $\Omega$ is $\Delta^0_2$. However, this set is not $\Sigma^0_1$ - that distinction can be a point of confusion.

Each true, effective theory of arithmetic can only prove the values of a certain finite number of digits of $\Omega$, and the number of digits for which a theory can prove the values is a measure of the strength of the theory. But even though $\Omega$ is $\Delta^0_2$, a theory can get information about the digits of $\Omega$ from axioms of arbitrarily high complexity.

For comparison, a more common way to measure the strength of a theory $T$ is to determine a collection of effective theories $T'$ such that $T$ proves $\text{Con}(T')$. Now each statement $\text{Con}(T')$ is a $\Sigma^0_1$ question, so the oracle $0'$ is able to answer all of these questions correctly. But a given theory $T$ will not be able to prove the consistency of arbitrary consistent theories, by Gödel's incompleteness theorems. And it can be that adding an axiom of high complexity to $T$ can affect the $\Sigma^0_1$ consequences of $T$.

This measure of strength is not intended to distinguish theories that have the same $\Sigma^0_1$ consequences. The set of $\Sigma^0_1$ consequences turns out to be an interesting measure of strength because of its connection to consistency statements. Of course it only gives one viewpoint on the strength of a theory.

There are three common ways to measure the strength of a theory:

  • Its set of logical consequences
  • The collection of effective theories that it can prove consistent
  • The collection of computable well orderings that it can prove to be well ordered

These three give different information about a theory, although in practice there is a close connection between the second and third. One problem with the first is that it is very sensitive to the language of the theory. For example, the language of Peano arithmetic does not include any nontrivial formulas in the analytical hierarchy, so PA cannot prove them. But there are some effective theories in the language of second-order arithmetic that are weaker than PA in the second and third senses even though they are able to prove statements arbitrarily high in the analytical hierarchy.

share|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.