Tarski–Kuratowski algorithm
Encyclopedia
In computability theory
and mathematical logic
the Tarski–Kuratowski algorithm is a non-deterministic algorithm which provides an upper bound for the complexity of formulas in the arithmetical hierarchy
and analytical hierarchy
.
The algorithm is named after Alfred Tarski
and Kazimierz Kuratowski
.
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
and mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
the Tarski–Kuratowski algorithm is a non-deterministic algorithm which provides an upper bound for the complexity of formulas in the arithmetical hierarchy
Arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
and analytical hierarchy
Analytical hierarchy
In mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them.-The analytical hierarchy of formulas:...
.
The algorithm is named after Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
and Kazimierz Kuratowski
Kazimierz Kuratowski
Kazimierz Kuratowski was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics.-Biography and studies:...
.
Algorithm
The Tarski–Kuratowski algorithm for the arithmetical hierarchy:- Convert the formula to prenex normal formPrenex normal formA formula of the predicate calculus is in prenex normal form if it is written as a string of quantifiers followed by a quantifier-free part .Every formula in classical logic is equivalent to a formula in prenex normal form...
. - If the formula is quantifier-free, it is in
and 
. - Otherwise, count the number of alternations of quantifiers; call this k.
- If the first quantifier is
the formula is in 
. - If the first quantifier is
the formula is in 
.