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.

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|improve this question

1 Answer 1

up vote 1 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|improve this answer

Your Answer

 
discard

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.