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. 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.

À 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.

Publications associées (4)

Concepts associés (8)

Cours associés (2)

Séances de cours associées (8)

Topological Structures on DMC spaces

Rajai Nasser

Two channels are said to be equivalent if they are degraded from each other. The space of equivalent channels with input alphabet X and output alphabet Y can be naturally endowed with the quotient of the Euclidean topology by the equivalence relation. We s ...

2017

Numerical Approximation of Flows in Random Porous Media

Francesco Tesei

The objective of this thesis is to develop efficient numerical schemes to successfully tackle problems arising from the study of groundwater flows in a porous saturated medium; we deal therefore with partial differential equations(PDE) having random coeffi ...

EPFL2016

Moyennabilité et courbure

Martin Anderegg

As Avez showed (in 1970), the fundamental group of a compact Riemannian manifold of nonpositive sectional curvature has exponential growth if and only if it is not flat. After several generalizations from Gromov, Zimmer, Anderson, Burger and Shroeder, the ...

EPFL2010

Ordinal analysis

In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory. The field of ordinal analysis was formed when Gerhard Gentzen in 1934 used cut elimination to prove, in modern terms, that the proof-theoretic ordinal of Peano arithmetic is ε0.

Théorème de Goodstein

En mathématiques, et plus précisément en logique mathématique, le 'théorème de Goodstein' est un énoncé arithmétique portant sur des suites, dites suites de Goodstein. Les suites de Goodstein sont des suites d'entiers à la croissance initiale extrêmement rapide, et le théorème établit que (en dépit des apparences) toute suite de Goodstein se termine par 0. Il doit son nom à son auteur, le mathématicien et logicien Reuben Goodstein.

Gentzen's consistency proof

Gentzen'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.

MATH-318: Set theory

Set Theory as a foundational system for mathematics. ZF, ZFC and ZF with atoms. Relative consistency of the Axiom of Choice, the Continuum Hypothesis, the reals as a countable union of countable sets,

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Relations, séquences, sommation CS-101: Advanced information, computation, communication I

Couvre les progressions arithmétiques, les treillis, la vérification formelle, les chaînes, les formules explicites, les relations de récurrence, les formules fermées et l'argument Diagonal de Cantor.

Filtrage adaptatif: LMS Algorithm COM-500: Statistical signal and data processing through applications

Couvre le filtrage adaptatif à l'aide de l'algorithme LMS pour les scénarios d'enregistrement immobile, en mettant l'accent sur la mise en œuvre pratique dans MATLAB.

Relations, séquences et sommations CS-101: Advanced information, computation, communication I

Couvre les chaînes, les ensembles dénombrables, la cardinalité et le concept de dénombrabilité, explorant la dénombrabilité de divers ensembles et la diagonalisation de Cantor.