Computable functionComputable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.
Théorie de la calculabilitéLa théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique. La calculabilité (parfois appelée « computationnalité », de l'anglais computability) cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.
Nombre epsilonEn mathématiques, les nombres epsilon sont une collection de nombres transfinis définis par la propriété d'être des points fixes d'une application exponentielle. Ils ne peuvent donc pas être atteints à partir de 0 et d'un nombre fini d'exponentiations (et d'opérations « plus faibles », comme l'addition et la multiplication). La forme de base fut introduite par Georg Cantor dans le contexte du calcul sur les ordinaux comme étant les ordinaux ε satisfaisant l'équation où ω est le plus petit ordinal infini ; une extension aux nombres surréels a été découverte par John Horton Conway.
Grand ordinal dénombrableEn 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.
Ordinal arithmeticIn the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.
Hiérarchie de croissance rapideEn théorie de la calculabilité et en théorie de la démonstration, une hiérarchie de croissance rapide (parfois appelée une hiérarchie de Grzegorczyk étendue) est une famille, indexée par les ordinaux, de fonctions rapidement croissantes fα : N → N (où N est l'ensemble des entiers naturels {0, 1, ...}, et α est un ordinal inférieur à un certain ordinal dénombrable généralement très grand). Un exemple fondamental est la hiérarchie de Wainer, s'étendant à tous les α < ε0.
Kruskal's tree theoremIn mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding. The theorem was conjectured by Andrew Vázsonyi and proved by ; a short proof was given by . It has since become a prominent example in reverse mathematics as a statement that cannot be proved in ATR0 (a second-order arithmetic theory with a form of arithmetical transfinite recursion).
TétrationLa tétration (ou encore nappe exponentielle, hyperpuissance, tour de puissances, super-exponentiation ou hyper4) est une « exponentiation itérée ». C'est le premier hyperopérateur après l'exponentiation. Le mot-valise tétration a été forgé par Reuben Goodstein sur la base du préfixe tétra- (quatre) et itération. La tétration est utilisée pour l'écriture des grands nombres. Elle suit l'addition, la multiplication et l'exponentiation comme indiqué ci-après : addition multiplication exponentiation tétration avec chaque fois b apparitions de la lettre a.
Modèle non standard de l'arithmétiqueEn logique mathématique, un modèle non standard de l'arithmétique est un modèle non standard de l'arithmétique de Peano, qui contient des nombres non standards. Le modèle standard de l'arithmétique contient exactement les nombres naturels 0, 1, 2, etc. Les éléments du domaine de tout modèle de l'arithmétique de Peano sont ordonnés linéairement et possèdent un segment initial isomorphe aux nombres naturels standards. Un modèle non standard est un modèle qui contient également des éléments en dehors de ce segment initial.
Gentzen's consistency proofGentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936. It shows that the Peano axioms of first-order arithmetic do not contain a contradiction (i.e. are "consistent"), as long as a certain other system used in the proof does not contain any contradictions either. This other system, today called "primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal ε0", is neither weaker nor stronger than the system of Peano axioms.
