Ê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 GraphSearch.
Concept
Théorème de Cantor
Résumé
vignette|Georg Cantor
Le théorème de Cantor est un théorème mathématique, dans le domaine de la théorie des ensembles. Il énonce que le cardinal d'un ensemble E est toujours strictement inférieur au cardinal de l'ensemble de ses parties P(E), c'est-à-dire essentiellement qu'il n'existe pas de bijection entre E et P(E).
Combiné avec l'axiome de l'ensemble des parties et l'axiome de l'infini de la théorie des ensembles usuelle, ce théorème implique qu'il existe une hiérarchie infinie d'ensembles infinis en termes de cardinalité.
Le théorème a été démontré en 1891 par Georg Cantor à l'aide d'un raisonnement astucieux mais simple, l'argument diagonal.
Le résultat est connu de longue date pour les ensembles finis. En effet supposons que E possède n éléments, on démontre facilement que l'ensemble des parties de E contient 2n éléments. Il est alors aisé de vérifier (par exemple par récurrence) que, pour tout entier n, n < 2n, et l'on sait alors — c'est le principe des tiroirs — qu'il n'existe pas d'injection de P(E) dans E, donc pas de bijection. Mais l'argument de Cantor qui suit et qu'il a développé pour les ensembles infinis est en fait tout à fait valable également pour les ensembles finis.
On se contente pour ce théorème d'une approche de la cardinalité, en particulier des ensembles infinis, par l'équipotence. Dire d'un ensemble A qu'il a un cardinal strictement inférieur à celui d'un ensemble B, c'est dire qu'il existe une injection de A dans B, mais pas de bijection entre ces deux ensembles. De façon équivalente (par le théorème de Cantor-Bernstein), c'est également dire qu'il existe une injection de A dans B mais pas d'injection de B dans A. L'existence d'une injection de E dans P(E) est immédiate (associer à un élément son singleton).
Pour montrer qu'il n'existe pas de bijection, l'argument de Cantor, dit argument diagonal, est le suivant. Soit f une application d'un ensemble E dans son ensemble des parties P(E). Alors le sous-ensemble des éléments de E qui n'appartiennent pas à leur par f :
n'a pas d'antécédent, c'est-à-dire n'est l'image par f d'aucun élément de E.
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.
Concepts associés (33)
New Foundations
En logique mathématique, New Foundations (NF) est une théorie des ensembles axiomatique introduite par Willard Van Orman Quine en 1937, dans un article intitulé « New Foundations for Mathematical Logic », et qui a connu un certain nombre de variantes. Pour éviter le paradoxe de Russell, le principe de compréhension est restreint aux formules stratifiées, une restriction inspirée de la théorie des types, mais où la notion de type est implicite.
Puissance du continu
En mathématiques, plus précisément en théorie des ensembles, on dit qu'un ensemble E a la puissance du continu (ou parfois le cardinal du continu) s'il est équipotent à l'ensemble R des nombres réels, c'est-à-dire s'il existe une bijection de E dans R. Le cardinal de R est parfois noté , en référence au , nom donné à l'ensemble ordonné (R, ≤). Cet ordre (et a fortiori le cardinal de l'ensemble sous-jacent) est entièrement déterminé (à isomorphisme près) par quelques propriétés classiques.
Théorème de Cantor
vignette|Georg Cantor Le théorème de Cantor est un théorème mathématique, dans le domaine de la théorie des ensembles. Il énonce que le cardinal d'un ensemble E est toujours strictement inférieur au cardinal de l'ensemble de ses parties P(E), c'est-à-dire essentiellement qu'il n'existe pas de bijection entre E et P(E). Combiné avec l'axiome de l'ensemble des parties et l'axiome de l'infini de la théorie des ensembles usuelle, ce théorème implique qu'il existe une hiérarchie infinie d'ensembles infinis en termes de cardinalité.
Cours associés (2)
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
MATH-205: Analysis IV
Learn the basis of Lebesgue integration and Fourier analysis
Séances de cours associées (21)
Relations, séquences, sommationCS-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.
Argument diagonal de CantorCS-101: Advanced information, computation, communication I
Explore l'argument Diagonal de Cantor et le concept de l'incomptabilité à travers des séquences binaires à chiffres.
Intégration de Lebesgue : Cantor SetMATH-205: Analysis IV
Explore la construction de la fonction Lebesgue sur l'ensemble Cantor et ses propriétés uniques.