Tarski–Kuratowski algorithm

The Tarski–Kuratowski algorithm for the arithmetical hierarchy consists of the following steps:

1. Convert the formula to prenex normal form. (This is the non-deterministic part of the algorithm, as there may be more than one valid prenex normal form for the given formula.)
2. If the formula is quantifier-free, it is in ${\displaystyle \Sigma _{0}^{0}}$ and ${\displaystyle \Pi _{0}^{0}}$ .
3. Otherwise, count the number of alternations of quantifiers; call this k.
4. If the first quantifier is ∃, the formula is in ${\displaystyle \Sigma _{k+1}^{0}}$ .
5. If the first quantifier is ∀, the formula is in ${\displaystyle \Pi _{k+1}^{0}}$ .

• Rogers, Hartley The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1