Arithmetical hierarchy (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (cs) 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 , i en l'estudi de teories formals (com per exemple l'aritmètica de Peano). L' permet obtenir fàcilment una fita superior per a la classificació dels conjunts aritmètics. La i la són extensions de la jerarquia aritmètica que permeten classificar més conjunts. (ca) Die Arithmetische Hierarchie ist ein Konzept der mathematischen Logik. Sie klassifiziert Mengen von natürlichen Zahlen, die in der Sprache der Peano-Arithmetik definierbar sind, nach der Komplexität ihrer Definitionen. Die arithmetisch definierbaren Mengen werden auch als arithmetisch bezeichnet. Die arithmetische Hierarchie spielt eine wichtige Rolle in der Berechenbarkeitstheorie. Die und die erweitern die arithmetische Hierarchie nach oben. (de) 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 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) En matematika logiko, la aritmetika hierarkio aŭ kleene-a hierarkio klasifikas la arojn de aritmetikaj formuloj (aŭ aritmetikaj aroj) laŭ ilia grado de solvebleco. Markotoj en la hierarkio estas difinita tiujn formulojn, kiuj kontentigas propozicion (priskribon) de certa komplekseco. La provizas supera baron por la grado de solvebleco de aritmetika formulo. (eo) La jerarquía aritmética, o jerarquía de Kleene clasifica ciertos conjuntos basándose en la complejidad de las fórmulas que los definen. Todo conjunto que recibe una clasificación es llamado aritmético. La jerarquía aritmética es importante en la , , y el estudio de teorías formales tales como aritmética de Peano. El da una forma fácil de obtener un límite superior sobre las clasificaciones que se asignan a una fórmula y al conjunto que la misma define. La y la jerarquía analítica extienden la jerarquía aritmética clasificando fórmulas y conjuntos adicionales. (es) En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Stephen Cole 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 (Σ10) et à celle des ensembles dont le complémentaire est récursivement énumérable (Π10), leur intersection étant la classe des ensembles récursifs (Δ10). (fr) 算術的階層（さんじゅつてきかいそう、英: Arithmetical hierarchy）は、数理論理学において、集合を定義する式の複雑さに基づいて、その集合を分類した階層である。クリーネ階層（Kleene hierarchy）とも。このような分類が可能な集合は算術的である。 算術的階層は、再帰理論やペアノ算術のような形式理論の研究で重要である。 算術的階層での式や集合の分類の拡張として、やがある。 (ja) 수리 논리학에서 산술적 위계(영어: arithmetical hierarchy) 또는 클레이니-모스토프스키 위계(Kleene hierarchy)란, 그것을 정의하는 식의 복잡도에 근거하여 집합들을 분류한 위계이다. 그러한 분류가 가능한 집합을 산술적(arithmetical)이라 한다. 재귀 이론, 기술적 집합론, 페아노 산술 연구 등에 있어서 중요한 개념이다. (ko) Em Lógica matemática, a hierarquia aritmética, ou hierarquia de Kleene-Mostowski classifica certos conjuntos baseada na complexidade das formulas que o definem. Qualquer conjunto que recebe uma classificação é chamado aritmético. A hierarquia aritmética é importante em teoria da recursão, teoria descritiva efetiva de conjuntos, e no estudo de teorias formais como a aritmética de Peano. O fornece um caminho simples para obter um limite superior nas classificações atribuídas a uma fórmula e o conjunto que ela define. A e a estendem a hierarquia aritmética para classificar formulas e conjuntos adicionais. (pt) 算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Arithmetic_hierarchy.svg?width=300 |
| dbo:wikiPageID | 186475 (xsd:integer) |
| dbo:wikiPageLength | 24870 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116127068 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Primitive_recursive_function dbr:Lévy_hierarchy dbr:Peano_arithmetic dbr:Peano_axioms dbr:Interpretability_logic dbr:Universal_quantifier dbr:Complement_(set_theory) dbr:Computable_function dbr:Course-of-values_recursion dbr:Analytical_hierarchy dbc:Effective_descriptive_set_theory dbc:Hierarchy dbc:Mathematical_logic_hierarchies dbr:Mathematical_logic dbr:Oracle_machine dbr:Prenex_normal_form dbr:Bounded_quantifier dbr:Andrzej_Mostowski dbr:Arithmetical_hierarchy dbr:Stephen_Cole_Kleene dbr:Complexity dbr:Many-one_reduction dbr:Tuple dbr:E_(complexity) dbr:Pairing_function dbc:Complexity_classes dbr:Halting_problem dbr:Intersection_(set_theory) dbr:Baire_space_(set_theory) dbc:Computability_theory dbr:Effective_Polish_space dbr:Effective_descriptive_set_theory dbr:Hierarchy_(mathematics) dbr:Borel_hierarchy dbr:Borel_set dbr:Polynomial_hierarchy dbr:Indicator_function dbr:Cantor_space dbr:Recursive_set dbr:Recursively_enumerable_set dbr:Set_(mathematics) dbr:Second-order_arithmetic dbr:Union_(set_theory) dbr:Turing_jump dbr:Lightface dbr:Post's_theorem dbr:Tarski–Kuratowski_algorithm dbr:Turing_degree dbr:Turing_complete_set dbr:Turing_reducibility dbr:Cartesian_power dbr:Hyperarithmetic_reducibility dbr:Hyperarithmetical_hierarchy dbr:Recursion_theory dbr:Existential_quantifier dbr:File:Arithmetic_hierarchy.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Distinguish dbt:No_footnotes dbt:Refbegin dbt:Refend dbt:Reflist dbt:See_also dbt:Short_description dbt:Pointclasses dbt:ComplexityClasses |
| dct:subject | dbc:Effective_descriptive_set_theory dbc:Hierarchy dbc:Mathematical_logic_hierarchies dbc:Complexity_classes dbc:Computability_theory |
| rdf:type | owl:Thing yago:WikicatComplexityClasses yago:WikicatMathematicalLogicHierarchies yago:Abstraction100002137 yago:Arrangement107938773 yago:Class107997703 yago:Collection107951464 yago:Group100031264 yago:Hierarchy108377806 yago:Ordering108456993 yago:Series108457976 |
| rdfs:comment | 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. (cs) Die Arithmetische Hierarchie ist ein Konzept der mathematischen Logik. Sie klassifiziert Mengen von natürlichen Zahlen, die in der Sprache der Peano-Arithmetik definierbar sind, nach der Komplexität ihrer Definitionen. Die arithmetisch definierbaren Mengen werden auch als arithmetisch bezeichnet. Die arithmetische Hierarchie spielt eine wichtige Rolle in der Berechenbarkeitstheorie. Die und die erweitern die arithmetische Hierarchie nach oben. (de) En matematika logiko, la aritmetika hierarkio aŭ kleene-a hierarkio klasifikas la arojn de aritmetikaj formuloj (aŭ aritmetikaj aroj) laŭ ilia grado de solvebleco. Markotoj en la hierarkio estas difinita tiujn formulojn, kiuj kontentigas propozicion (priskribon) de certa komplekseco. La provizas supera baron por la grado de solvebleco de aritmetika formulo. (eo) La jerarquía aritmética, o jerarquía de Kleene clasifica ciertos conjuntos basándose en la complejidad de las fórmulas que los definen. Todo conjunto que recibe una clasificación es llamado aritmético. La jerarquía aritmética es importante en la , , y el estudio de teorías formales tales como aritmética de Peano. El da una forma fácil de obtener un límite superior sobre las clasificaciones que se asignan a una fórmula y al conjunto que la misma define. La y la jerarquía analítica extienden la jerarquía aritmética clasificando fórmulas y conjuntos adicionales. (es) 算術的階層（さんじゅつてきかいそう、英: Arithmetical hierarchy）は、数理論理学において、集合を定義する式の複雑さに基づいて、その集合を分類した階層である。クリーネ階層（Kleene hierarchy）とも。このような分類が可能な集合は算術的である。 算術的階層は、再帰理論やペアノ算術のような形式理論の研究で重要である。 算術的階層での式や集合の分類の拡張として、やがある。 (ja) 수리 논리학에서 산술적 위계(영어: arithmetical hierarchy) 또는 클레이니-모스토프스키 위계(Kleene hierarchy)란, 그것을 정의하는 식의 복잡도에 근거하여 집합들을 분류한 위계이다. 그러한 분류가 가능한 집합을 산술적(arithmetical)이라 한다. 재귀 이론, 기술적 집합론, 페아노 산술 연구 등에 있어서 중요한 개념이다. (ko) 算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。 (zh) 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 , i en l'estudi de teories formals (com per exemple l'aritmètica de Peano). L' permet obtenir fàcilment una fita superior per a la classificació dels conjunts aritmètics. (ca) 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 is important in recursion theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic. The hyperarithmetical hierarchy and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets. (en) En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Stephen Cole 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. (fr) Em Lógica matemática, a hierarquia aritmética, ou hierarquia de Kleene-Mostowski classifica certos conjuntos baseada na complexidade das formulas que o definem. Qualquer conjunto que recebe uma classificação é chamado aritmético. A hierarquia aritmética é importante em teoria da recursão, teoria descritiva efetiva de conjuntos, e no estudo de teorias formais como a aritmética de Peano. O fornece um caminho simples para obter um limite superior nas classificações atribuídas a uma fórmula e o conjunto que ela define. (pt) |
| rdfs:label | Jerarquia aritmètica (ca) Aritmetická hierarchie (cs) Arithmetische Hierarchie (de) Aritmetika hierarkio (eo) Arithmetical hierarchy (en) Jerarquía aritmética (es) Hiérarchie arithmétique (fr) 算術的階層 (ja) 산술적 위계 (ko) Hierarquia aritmética (pt) 算数阶层 (zh) |
| rdfs:seeAlso | dbr:Post's_theorem |
| owl:differentFrom | dbr:Levy_hierarchy |
| owl:sameAs | freebase:Arithmetical hierarchy yago-res:Arithmetical hierarchy wikidata:Arithmetical hierarchy dbpedia-ca:Arithmetical hierarchy dbpedia-cs:Arithmetical hierarchy dbpedia-de:Arithmetical hierarchy dbpedia-eo:Arithmetical hierarchy dbpedia-es:Arithmetical hierarchy dbpedia-fr:Arithmetical hierarchy dbpedia-ja:Arithmetical hierarchy dbpedia-ko:Arithmetical hierarchy dbpedia-pt:Arithmetical hierarchy dbpedia-sr:Arithmetical hierarchy dbpedia-zh:Arithmetical hierarchy https://global.dbpedia.org/id/4qmUr |
| prov:wasDerivedFrom | wikipedia-en:Arithmetical_hierarchy?oldid=1116127068&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Arithmetic_hierarchy.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Arithmetical_hierarchy |
| is dbo:knownFor of | dbr:Andrzej_Mostowski |
| is dbo:wikiPageRedirects of | dbr:Kleene-Mostowski_hierarchy dbr:Arithmetic_hierarchy dbr:Arithmetic_reducibility dbr:Arithmetical_reducibility dbr:Pi-0-1_sentence dbr:Pi-0-1_sentences dbr:Pi-0-2_sentence dbr:AH_(complexity) dbr:Kleene_hierarchy dbr:Kleene–Mostowski_hierarchy |
| is dbo:wikiPageWikiLink of | dbr:Enumeration_reducibility dbr:List_of_algorithms dbr:List_of_first-order_theories dbr:Lévy_hierarchy dbr:Decider_(Turing_machine) dbr:Dependence_logic dbr:Peano_axioms dbr:Reverse_mathematics dbr:Definable_real_number dbr:Definable_set dbr:Double-negation_translation dbr:Index_set_(computability) dbr:Indicator_vector dbr:Induction,_bounding_and_least_number_principles dbr:Kőnig's_lemma dbr:Limits_of_computation dbr:List_of_mathematical_logic_topics dbr:Computability_theory dbr:Computable_function dbr:Constructible_universe dbr:Analytical_hierarchy dbr:Anders_C._Hansen dbr:Mathematical_logic dbr:Oracle_machine dbr:Prenex_normal_form dbr:Collatz_conjecture dbr:Emil_Leon_Post dbr:Gisbert_Hasenjaeger dbr:Glossary_of_set_theory dbr:Bounded_quantifier dbr:Conservative_extension dbr:Constructive_set_theory dbr:Andrzej_Mostowski dbr:Arithmetical_hierarchy dbr:Arithmetical_set dbr:Basis_theorem_(computability) dbr:Computable_ordinal dbr:Computable_set dbr:Computably_enumerable_set dbr:Friedman_translation dbr:Low_basis_theorem dbr:Giorgi_Japaridze dbr:Gödel's_completeness_theorem dbr:K-trivial_set dbr:Large_countable_ordinal dbr:Wadge_hierarchy dbr:True_arithmetic dbr:Recursively_enumerable_language dbr:Algorithmically_random_sequence dbr:Delta dbr:Proof_theory dbr:Gödel's_incompleteness_theorems dbr:Halting_problem dbr:Hyperarithmetical_theory dbr:Effective_descriptive_set_theory dbr:Heyting_arithmetic dbr:Hierarchy_(mathematics) dbr:Termination_analysis dbr:Reduction_(computability_theory) dbr:Dieter_Rödding dbr:Borel_hierarchy dbr:Pi_(disambiguation) dbr:Polynomial_hierarchy dbr:Kleene-Mostowski_hierarchy dbr:Chaitin's_constant dbr:Kleene's_T_predicate dbr:Turing_machine dbr:Turing_jump dbr:Self-verifying_theories dbr:Pointclass dbr:Post's_theorem dbr:Tarski–Kuratowski_algorithm dbr:Super-recursive_algorithm dbr:Ω-consistent_theory dbr:Tarski's_undefinability_theorem dbr:Turing_degree dbr:Π01_class dbr:Arithmetic_hierarchy dbr:Arithmetic_reducibility dbr:Arithmetical_reducibility dbr:Pi-0-1_sentence dbr:Pi-0-1_sentences dbr:Pi-0-2_sentence dbr:AH_(complexity) dbr:Kleene_hierarchy dbr:Kleene–Mostowski_hierarchy |
| is dbp:knownFor of | dbr:Andrzej_Mostowski |
| is rdfs:seeAlso of | dbr:Post's_theorem |
| is foaf:primaryTopic of | wikipedia-en:Arithmetical_hierarchy |
