Arithmetical hierarchy (nonfiction): Difference between revisions

From Gnomon Chronicles
Jump to navigation Jump to search
(Created page with "In mathematical logic, the '''arithmetical hierarchy''', '''arithmetic hierarchy''', or '''Kleene–Mostowski hierarchy''' classifies certain sets based on the complexity of f...")
 
No edit summary
 
(One intermediate revision by the same user not shown)
Line 11: Line 11:
== Nonfiction cross-reference ==
== Nonfiction cross-reference ==


* [[Mathematics (fiction)]]
* [[Mathematics (nonfiction)]]
* [[Set theory (nonfiction)]]


External links:
External links:
Line 18: Line 19:


[[Category:Nonfiction (nonfiction)]]
[[Category:Nonfiction (nonfiction)]]
[[Category:Complexity (nonfiction)]]
[[Category:Mathematics (nonfiction)]]
[[Category:Mathematics (nonfiction)]]
[[Category:Set theory (nonfiction)]]

Latest revision as of 20:20, 17 April 2017

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy, or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical.

The arithmetical hierarchy is important in recursion theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic.

The Tarski-Kuratowski algorithm provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines.

The hyperarithmetical hierarchy and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets.

Fiction cross-reference

Nonfiction cross-reference

External links: