Concept
Hyperarithmetical theory
Concepts associés (16)
Saut de Turing
En théorie de la calculabilité, le saut de Turing, du nom d'Alan Turing, est une opération qui attribue à chaque problème de décision un problème de décision plus difficile avec la propriété que n'est pas décidable par une machine à oracle relative à . Le saut est appelé opérateur de saut car il augmente le degré de Turing du problème . Autrement dit, le problème n'est pas à . Le théorème de Post établit une relation entre l'opérateur de saut de Turing et la hiérarchie arithmétique des ensembles de nombres naturels.
Effective descriptive set theory
Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptive set theory combines descriptive set theory with recursion theory. Effective Polish space An effective Polish space is a complete separable metric space that has a computable presentation. Such spaces are studied in both effective descriptive set theory and in constructive analysis.
Ordinal récursif
En mathématiques, en particulier en calculabilité et en théorie des ensembles, un ordinal est dit calculable ou récursif s'il existe un bon ordre calculable d'un sous-ensemble calculable des nombres naturels ayant le type d'ordre . Il est facile de vérifier que est calculable. On montre également que le successeur d'un ordinal calculable est calculable, et que l'ensemble de tous les ordinaux calculables est fermé vers le bas. La borne supérieure de tous les ordinaux calculables est appelé l'ordinal de Church-Kleene, le premier ordinal non récursif, et noté .
Ordinal notation
In mathematical logic and set theory, an ordinal notation is a partial function mapping the set of all finite sequences of symbols, themselves members of a finite alphabet, to a countable set of ordinals. A Gödel numbering is a function mapping the set of well-formed formulae (a finite sequence of symbols on which the ordinal notation function is defined) of some formal language to the natural numbers. This associates each well-formed formula with a unique natural number, called its Gödel number.
Pointclass
In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a point is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by some sort of definability property; for example, the collection of all open sets in some fixed collection of Polish spaces is a pointclass. (An open set may be seen as in some sense definable because it cannot be a purely arbitrary collection of points; for any point in the set, all points sufficiently close to that point must also be in the set.
Arithmétique du second ordre
En logique mathématique, l'arithmétique du second ordre est une théorie des entiers naturels et des ensembles d'entiers naturels. Elle a été introduite par David Hilbert et Paul Bernays dans leur livre Grundlagen der Mathematik. L'axiomatisation usuelle de l'arithmétique du second ordre est notée Z2. L'arithmétique de second ordre a pour conséquence les théorèmes de l'arithmétique de Peano (du premier ordre), mais elle est à la fois plus forte et plus expressive que celle-ci.
Hiérarchie arithmétique
thumb|Illustration de la hiérarchie arithmétique. 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.
Hiérarchie analytique
In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers over both the set of natural numbers, , and over functions from to . The analytical hierarchy of sets classifies sets by the formulas that can be used to define them; it is the lightface version of the projective hierarchy.
Grand ordinal dénombrable
En mathématiques, et plus particulièrement en théorie des ensembles, il existe de nombreuses méthodes de description des ordinaux dénombrables. Les plus petits (jusqu'à ε0) peuvent être exprimés (de façon utile et non circulaire) à l'aide de leur forme normale de Cantor. Au-delà, on parle de grands ordinaux dénombrables ; de nombreux grands ordinaux (le plus souvent en rapport avec la théorie de la démonstration) possèdent des notations ordinales calculables.
Degré de Turing
En informatique et en logique mathématique, le degré de Turing (nommé d'après Alan Turing) ou le degré d'insolubilité d'un ensemble d'entiers naturels mesure le niveau d'insolubilité algorithmique de l'ensemble. Le concept de degré de Turing est fondamental dans la théorie de la calculabilité, où des ensembles d'entiers naturels sont souvent considérés comme des problèmes de décision. Le degré de Turing d'un ensemble révèle combien il est difficile de résoudre le problème de décision associé à cet ensemble, à savoir, déterminer si un nombre arbitraire est dans l'ensemble donné.