Metraipolis › archive › dc_ee1cb80e64bf

Arithmetical hierarchy — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Arithmetical_hierarchy
License (as archived): CC-BY-SA-4.0
Archived: 2026-11-09T21:27:01.854Z
SHA-256 of the archived text: b345970208b17bea1207bc2289cf2bda9848a693bd0780b08d24dc94e595178b
Stable URL of this page: https://metraipolis.com/documento/dc_ee1cb80e64bf

How to cite

Arithmetical hierarchy — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Arithmetical_hierarchy (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ee1cb80e64bf (Metraipolis archive dc_ee1cb80e64bf, sha256 b345970208b17bea1207bc2289cf2bda9848a693bd0780b08d24dc94e595178b)

BibTeX

@misc{dcee1cb80e64bf,
  title = {Arithmetical hierarchy — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Arithmetical_hierarchy},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ee1cb80e64bf; sha256 b345970208b17bea1207bc2289cf2bda9848a693bd0780b08d24dc94e595178b},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Arithmetical_hierarchy. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The arithmetical hierarchy was invented independently by Kleene (1943) and Mostowski (1946). The arithmetical hierarchy is important in computability 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.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico).
Fonte: Wikipedia in inglese, voce «Arithmetical hierarchy» — https://en.wikipedia.org/wiki/Arithmetical_hierarchy
Wikidata Q669094: «hierarchy which classifies certain sets based on the complexity of formulas that define them» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q669094
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Arithmetical_hierarchy?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1384658823, consultata il 2026-11-09T21:23:54.008Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 3d7c234bc70ff25d8d8099c3410d204e09a9268aa126b85f6964a14a48514705