In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene 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.

PropertyValue
dbpprop:abstract
  • In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene 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.
  • En lògica matemàtica, la jerarquia aritmètica o jerarquia de Kleene és una classificació de conjunts de nombres naturals (i per extensió de qualsevol tipus d'elements que es codifiquin en nombres naturals) segons la complexitat de les fórmules que els defineixen. Els conjunts classificats s'anomenen aritmètics. La jerarquia aritmètica és important en la teoria de la recursió, en la teoria descriptiva de conjunts efectiva, i en l'estudi de teories formals (com per exemple l'aritmètica de Peano). L'algorisme de Tarski-Kuratowski permet obtenir fàcilment una fita superior per a la classificació dels conjunts aritmètics. La jerarquia hiperaritmètica i la jerarquia analítica són extensions de la jerarquia aritmètica que permeten classificar més conjunts.
  • Aritmetická hierarchie (také Kleeneova hierarchie) je v matematické logice způsob klasifikace podmnožin přirozených čísel s ohledem na složitost formulí, které je definují. Studium aritmetické hierarchie hraje důležitou roli v teorii rekurze a studiu formálních aritmetických teorií jako je například Peanova aritmetika. Aritmetickou hierarchii lze také použít pro elegantní důkaz silnější varianty první Gödelovy věty.
  • En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Kleene est une hiérarchie des sous-ensembles de l'ensemble N des entiers naturels définissables dans le langage du premier ordre de l'arithmétique de Peano. Un ensemble d'entiers est classé suivant les alternances de quantificateurs d'une formule sous forme prénexe qui permet de le définir. Les premiers niveaux de la hiérarchie correspondent à la classe des ensembles récursivement énumérables (Σ1) et à celle des ensembles dont le complémentaire est récursivement énumérable (Π1), leur intersection étant la classe des ensembles récursifs (Δ1).
  • 算術的階層（さんじゅつてきかいそう、英: Arithmetical hierarchy）は、数理論理学において、集合を定義する式の複雑さに基づいて、その集合を分類した階層である。クリーネ階層（Kleene hierarchy）とも。このような分類が可能な集合は算術的である。 算術的階層は、再帰理論やペアノ算術のような形式理論の研究で重要である。 算術的階層での式や集合の分類の拡張として、超算術的階層や解析的階層がある。
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene 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.
  • En lògica matemàtica, la jerarquia aritmètica o jerarquia de Kleene és una classificació de conjunts de nombres naturals (i per extensió de qualsevol tipus d'elements que es codifiquin en nombres naturals) segons la complexitat de les fórmules que els defineixen. Els conjunts classificats s'anomenen aritmètics.
  • Aritmetická hierarchie (také Kleeneova hierarchie) je v matematické logice způsob klasifikace podmnožin přirozených čísel s ohledem na složitost formulí, které je definují. Studium aritmetické hierarchie hraje důležitou roli v teorii rekurze a studiu formálních aritmetických teorií jako je například Peanova aritmetika. Aritmetickou hierarchii lze také použít pro elegantní důkaz silnější varianty první Gödelovy věty.
  • En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Kleene est une hiérarchie des sous-ensembles de l'ensemble N des entiers naturels définissables dans le langage du premier ordre de l'arithmétique de Peano. Un ensemble d'entiers est classé suivant les alternances de quantificateurs d'une formule sous forme prénexe qui permet de le définir.
rdfs:label
  • Arithmetical hierarchy
  • Jerarquia aritmètica
  • Aritmetická hierarchie
  • Hiérarchie arithmétique
  • 算術的階層
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of