Formula of hierarchies - arithmetic hierarchy and analytical hierarchy

515 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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