Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Grand ordinal dénombrable
Résumé
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. Cependant, il n'est pas possible en général de décider si une notation ordinale potentielle en est effectivement une, pour des raisons analogues à celles rendant insoluble le problème de l'arrêt.
Comme il ne peut exister qu'un nombre dénombrable de notations, l'ensemble des ordinaux qui en admettent une se termine bien avant le premier ordinal non dénombrable ω1 ; la borne supérieure de cet ensemble s'appelle l'ordinal ω1 de Church–Kleene, noté ω1CK (cet ordinal est dénombrable, et ne doit pas être confondu avec ω1). Les ordinaux inférieurs à ω1CK sont les ordinaux récursifs. Il est possible de définir des ordinaux supérieurs, mais ils ne possèderont pas de notations.
L'étude des ordinaux dénombrables non récursifs est délicate, la difficulté principale venant de ce qu'on ne sait pas, en général, comparer deux grands ordinaux définis par des méthodes différentes, et parfois même, qu'on ne sait pas démontrer qu'un ordre donné est un bon ordre.
Les ordinaux récursifs (ou calculables) sont les ordinaux dénombrables qu'on peut représenter par une fonction calculable. On peut en donner plusieurs définitions rigoureuses équivalentes ; la plus simple consiste à dire qu'un ordinal est récursif s'il est le type d'ordre d'un bon ordre calculable sur les entiers, c'est-à-dire qu'il existe une machine de Turing qui, ayant pour entrée deux entiers, décide lequel est le plus petit pour cet ordre.
Une autre définition des ordinaux récursifs utilise les notations ordinales de Kleene.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.