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

I am recently learning on these topics, and to help understand these things, it would be helpful if some examples of formula of various arithmetic hierarchies and analytical hierarchies are provided.

For example, $\Sigma_1^0$, $\Sigma_2^0$, $\Sigma_1^1$ and $\Sigma_2^1$ formula and what they mean in our daily language.

share|cite|improve this question
up vote 2 down vote accepted

Here are some examples. I couldn't think of a good one for $\Sigma^0_2$, so I threw in one for $\Pi^1_1$ instead.

  • A $\Sigma^0_1$ formula can say that a computer program eventually halts, or that a Diophantine equation has a solution.

  • A $\Sigma^1_1$ formula can say that a tree $T \subset \omega^{<\omega}$ has an infinite branch.

  • A $\Pi^1_1$ formula can say that a binary relation on $\omega$ is well-founded.

  • A $\Sigma^1_2$ formula can say that a real is in the constructible universe $L$.

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.