:: wikimiki.org ::
| Cardinalité |
Cardinalité
catégorie:Théorie des ensemblescatégorie:Nombre
En théorie des ensembles, la cardinalité représente la taille d'un ensemble.
Définition
Cas des ensembles finis
Pour un ensemble fini la cardinalité est son nombre d'éléments (zéro, pour l'ensemble vide) :
:card () = 0 ;
:card () = 3.
Ainsi, card (ensemble des faces d'un dé cubique) = 6
Approche intuitive, pour les ensembles de taille infinie
Des résultats en mathématiques montrent que pour les ensembles infinis, il existe plusieurs tailles d'ensembles, donc plusieurs infinis. Ces différents infinis sont représentés par des nombres cardinaux transfinis.
En particulier :
:
Cependant, et cela ne semble pas intuitif au premier abord :
: (cf. ensemble dénombrable)
Voir aussi Théorie axiomatique des ensembles.
Propriété
Deux ensembles ayant la même cardinalité sont en bijection, on dit aussi qu'ils sont équipotents.
Propriétés pour les ensembles finis (ou même infinis)
# card( P ( E ) ) = 2 card( E )
# card( A ∪ B ) ≤ card( A ) + card( B ) = card( A + B )
# card( A ∩ B ) = card( A ) + card( B ) - card( A ∪ B )
Exemples de cardinaux
Si E et F sont deux ensembles donnés, alors :
- les correspondances de E dans F forment un ensemble, noté habituellement « Corr( E, F) ». Le nombre de ces correspondances est :
::
:Pour s'en convaincre, il suffit de se rappeler que les graphes sont les sous-ensembles de E×F.
- les fonctions de E dans F forment un sous-ensemble du précédent, qui peut être noté « Fnct( E, F) ». Le nombre de ces fonctions est :
::
- les applications de E dans F forment un sous-ensemble du précédent, qui peut être noté « Appl( E, F) ». Le nombre de ces applications est :
::
:Cette propriété explique pourquoi Appl( E, F) est le plus souvent noté « ».
- les injections de E dans F forment un sous-ensemble du précédent, noté habituellement « Inj( E, F) ». Cet ensemble est vide si CardE > CardF. Si CardE ≤ CardF, le nombre de ces injections est :
::
- les surjections de E dans F forment un sous-ensemble de l'ensemble des applications, noté habituellement « Surj( E, F) ». Cet ensemble est vide si CardE < CardF. Si CardE ≥ CardF, le nombre de ces surjections est :
::
- les bijections de E dans F forment un sous-ensemble des deux ensembles précédents, noté habituellement « Bij( E, F) ». Cet ensemble est vide si CardE ≠ CardF. Si CardE = CardF = n, le nombre de ces bijections est :
::.
Voir aussi
- Algèbre abstraite
- Correspondances et Relations
- Famille finie
- Théorie des ensembles
Catégorie:Nombrecatégorie:mathématiques
Les nombres et les ensembles de nombres sont parmi les objets les plus couramment manipulés en mathématiques. Dans cette catégorie se trouve tout ce qui s'y rapporte.
ja:Category:数
ko:분류:수
simple:Category:Numbers
th:Category:จำนวน
Ensemblecatégorie:Mathématiques
Dans la théorie naïve des ensembles, le point de départ est la notion d'ensemble, décrite comme une collection d’objets mathématiques appelés éléments ou points. Plus précisément, le créateur de cette théorie, le mathématicien Georg Cantor définissait les ensembles comme « a many that can be thought of as a one » -- une multitude qui peut être imaginée comme un tout.
Remarque : dans la théorie axiomatique des ensembles, le point de départ est plutôt la notion d’appartenance, qui est alors primitive, et ne se définit donc pas. La notion d’ensemble a alors un statut plus flou. Si dans la théorie ZF ( Zermelo-Fränkel ), c’est aussi une notion primitive, puisque tous les objets primitifs de cette théorie ne peuvent être que des ensembles, par contre, dans la théorie NGB ( Neumann - Gödel - Bernays ) par exemple, les objets primitifs sont des classes, et les ensembles y sont définis comme les classes pour lesquelles il existe des classes les contenant.
Ensembles, éléments et appartenance
Un ensemble est désigné en général par une lettre latine majuscule, par exemple l’ensemble « E ».
Il peut être vu comme une sorte de sac virtuel entourant ses éléments, ce que modélisent bien les diagrammes de Venn.
Les éléments peuvent être de n’importe quelle nature: nombres, gens, autres ensembles... Par exemple, lundi est un élément de l’ensemble des jours de la semaine, et 4 est un élément de l’ensemble des nombres pairs.
Ce dernier exemple montre que les ensembles peuvent être infinis ( c’est-à-dire avoir un nombre infini d’éléments ).
Le rapport entre un ensemble, noté par exemple A, et l’un quelconque de ses éléments, noté par exemple x, s’écrit :
:: x ∈ A
Cet énoncé peut se lire :
- « x appartient à A »,
- « x est élément de A »,
- « x est dans A »,
- « A a pour élément x »,
- « A possède x »,
- ou « A contient x ».
Le symbole « ∈ », introduit par Giuseppe Peano en 1888, dérive de la lettre grecque epsilon, « ε ».
Une variante de ce symbole décrit la non-appartenance d’un objet à un ensemble :
:« z A » signifie « z n’appartient pas à A ».
Egalité de deux ensembles
Nous définissons l’égalité de deux ensembles A et B, notée « A = B », en affirmant que deux ensembles sont égaux quand ils ont exactement les mêmes éléments :
:
où « ⇔ » désigne l'équivalence logique. Les deux ensembles sont alors identiques, c'est-à-dire que tout ce qui peut être dit de l'un peut être dit de l'autre ( voir Axiome d'extensionnalité ).
Si nous nous représentons les deux ensembles comme des sacs étiquetés chacun par leur nom, s’ils sont égaux, alors il s’agit en fait d’un seul et même sac avec deux étiquettes. En sens inverse, les propriétés d’un ensemble ne dépendent absolument pas de la nature ou de la forme du sac, seulement de son contenu.
Ainsi un ensemble est complètement déterminé par ses éléments. Il peut l’être aussi par la donnée d’une propriété caractéristique de cet ensemble. Par exemple, l’ensemble formé par les éléments 2, 3, et 5 est égal à l’ensemble de tous les nombres premiers inférieurs à 6.
Nous avons ainsi deux manières de définir un ensemble : donner la liste de ses éléments ou une propriété caractéristique. Commençons par le cas le plus simple.
Singletons et paires
Pour tout élément a, nous pouvons définir un ensemble S dont a est l’unique élément :
:
L’existence de cet ensemble est garantie par l’ Axiome de la paire, son unicité pour chaque a par l’ Axiome d'extensionnalité. Il est appelé singleton et est noté « » ( lire « singleton a » ).
Pour tout élément a et tout élément b, nous pouvons définir un ensemble P dont a et b sont les uniques éléments :
:
où « V » désigne le OU logique inclusif. L'existence de cet ensemble est garantie par l' Axiome de la paire, son unicité pour a et b donnés par l’ Axiome d'extensionnalité. Il est noté « » ( lire « ensemble a, b » ).
- si a et b sont égaux, nous constatons que, d’après la définition, n’est autre que le singleton ;
- si a et b sont distincts, est appelé paire de a et de b.
Par exemple, représente l’ensemble dont les éléments sont 1 et 2 ( voir l’article : « Paire » ).
Nous aurons besoin dans un autre article des deux lemmes d’égalité suivants :
SP1 : deux singletons sont égaux si et seulement s’ils partagent le même élément :
:
SP2 : deux paires et sont égales ssi a 1 est égal à b 1 et a 2 à b 2 , ou si a 1 est égal à b 2 et a 2 à b 1 :
:
::
Définition d'un ensemble en extension
La notation précédente entre accolades peut être généralisée. L'ensemble est alors défini en extension. Par exemple, l'ensemble des jours de la semaine peut être représenté par . L'existence de l'ensemble ainsi défini est garantie par les axiomes de la paire et de la réunion, et son unicité pour une liste d’éléments donnés par celui d’extensionnalité.
Notons les points suivants :
- Les éléments d’un ensemble ne sont pas obligés de partager un point commun : par exemple, nous pouvons créer l’ensemble , bien qu’il ne semble pas d’un grand intérêt pratique...
- L’ordre des éléments est sans importance; si nous reprenons l’exemple de la fin de la section précédente, = .
- La répétition d’éléments entre les accolades ne modifie pas l’ensemble :
: toujours avec le même exemple, = = .
Pour définir en extension un ensemble dont le « nombre » d’éléments est « infini », nous pouvons écrire quelques éléments de cet ensemble suivis de points de suspension. Par exemple, l’ensemble des entiers naturels se définit par : = .
Les points de suspension peuvent aussi être utilisés pour abréger l’écriture de la liste des éléments de certains ensembles « finis ». Par exemple l’ensemble s’écrit plus simplement .
Un abus de notation permet de définir un ensemble en plaçant entre accolades la nature des objets qui lui appartiennent. Par exemple la notation désigne l’ensemble de tous les chiens.
Un exemple limite de cette notation est « », que certains utilisent pour désigner l’ensemble vide.
Définition d’un ensemble en compréhension
On peut aussi définir un ensemble E par une propriété P caractéristique, c’est-à-dire telle que l’appartenance à E soit équivalente à la vérification de cette propriété.
En notation symbolique :
:
L’ensemble E est noté « » ( lire « l’ensemble des x tels que la condition P ( x ) soit vraie » ).
Par exemple :
- désigne l’ensemble des nombres réels,
- désigne l’ensemble de tous ceux qui ont des cheveux blonds,
- et note l’ensemble de tous les chiens.
L’ensemble est alors dit « défini en compréhension ».
La notation correspondante est appelée constructeur d’ensemble dans le contexte de la programmation fonctionnelle.
Cette notation permet certaines variantes :
- désigne l’ensemble des x déjà éléments de A qui vérifient la condition P. Par exemple, si est l’ensemble des nombre entiers, alors est l’ensemble de tous les entiers pairs ( voir Axiome de séparation ).
- désigne l’ensemble de tous les objets obtenus en mettant les membres de l’ensemble A dans la formule F. Ainsi, prolongeant l’exemple précédent, est encore l’ensemble de tous les entiers pairs ( voir Axiome de remplacement ).
- est la forme la plus générale de la définition en compréhension.
: Par exemple, est l’ensemble de tous les propriétaires de chiens.
Notons que s’il est toujours possible de définir un ensemble à partir d’une propriété caractéristique, rien ne garantit que l’ensemble ainsi défini puisse exister pour autant. Un contre-exemple célèbre est celui de l' « ensemble de tous les ensembles qui ne se contiennent pas eux-mêmes » ( voir le paragraphe « Paradoxe de Russell » dans l’article « Théorie naïve des ensembles » ).
Voir aussi
- Théorie des ensembles
- Théorie naïve des ensembles
- Théorie axiomatique des ensembles
- Sous-ensembles
- Opérations sur les ensembles
- Produit cartésien
- Correspondances et Relations
ja:集合
ko:집합
Nombre transfini
Transfini
Les nombres transfinis sont les nombres infinis découverts et explorés par le mathématicien Georg Cantor. Cantor a introduit une sorte de hiérarchie dans l'infini, en développant la théorie des ensembles.
Aspect épistémologique
Les travaux de Cantor sur la théorie des ensembles ont été à la source de nombreux paradoxes, et ont contribué à la crise des fondements qu'ont connue les mathématiques, entre la fin du XIX et le début du XX siècle. Kronecker, par exemple, a exprimé pourquoi ils ne considérait pas comme mathématiquement valides les démonstrations de Cantor faisant intervenir l'infini de deux façons différentes en considérant l'un comme achevé et l'autre comme en construction.
Une fameuse boutade de David Hilbert résume le choix de bon nombre de mathématiciens : « Cantor a créé pour les mathématiciens un paradis dont ils ne se laisseront pas expulser ».
Les nombres transfinis ont peu d'applications en dehors des mathématiques à l'heure actuelle (2005). Cela n'est pas nécessairement significatif, ainsi que le montrent quelques exemples historiques (nombres complexes en particulier). Toutefois au cours du siècle écoulé les physiciens ne se sont pas montrés demandeurs de ce genre de travaux.
Cette situation est à opposer à d'autres travaux mathématiques qui furent au contraire inspirés au départ par un souci de formaliser et généraliser de procédés employés empiriquement en physique : le calcul opérationnel avait été formalisé par la transformation de Laplace, et les fonctions de Dirac par la théorie des distributions de Laurent Schwartz.
Distinction importante
Un nombre entier naturel peut être utilisé pour décrire la taille d'un ensemble fini, ou pour désigner la position d'un élément dans une suite. Ces deux utilisations correspondent aux notions de cardinal et d'ordinal respectivement.
Bien que semblables en apparence, ces deux concepts cantoriens doivent être distingués lorsque l'on s'intéresse à des ensembles infinis.
Nombres ordinaux transfinis
En théorie des ensembles, les entiers naturels peuvent être construits avec des ensembles :
:0 = (ensemble vide)
:1 = =
:2 = =
:3 = =
:4 = =
etc. De cette manière, tout entier naturel est un ensemble bien ordonné, et l'inclusion des ensembles se traduit par un ordre sur les entiers naturels. Cela nous conduit à la définition d'un nombre ordinal par John von Neumann : un ensemble E est un ordinal si et seulement si E est totalement ordonné pour l'inclusion et tout élément de E est aussi un sous ensemble de E. Cette approche permet d'envisager les nombres ordinaux infinis.
L'existence des ordinaux infinis est assuré par L'axiome de l'infini.
Le premier nombre ordinal transfini est ω, cf. alphabet grec. Il correspond à l'ensemble des nombres entiers naturels .
L'addition des nombres entiers naturels, traduite en terme d'ensembles, permet de généraliser l'addition aux nombres ordinaux transfinis. Cette addition est associative mais pas commutative. Elle donne lieu à une arithmétique sur les nombres ordinaux transfinis. Ainsi , mais .
On montre qu'il existe une infinité de nombres ordinaux transfinis :
et
Il existe des nombres ordinaux transfinis qui ne peuvent pas être obtenus en effectuant un nombre fini d'opérations arithmétiques n'utilisant que les nombres ordinaux finis et . Le plus petit d'entre eux est appelé et vaut . Il est en outre solution de l'équation .
À noter que les ordinaux ne forment pas un ensemble, au sens des axiomes ZFC de la théorie axiomatique des ensembles habituelle, mais une classe propre. Ceci peut-être mis en évidence grâce au paradoxe de Burali-Forti : l'ensemble des ordinaux serait par définition un ordinal ... mais qui serait strictement plus grand (aussi par définition) que tous les ordinaux. Ceci est évidemment contradictoire.
Nombres cardinaux transfinis
À tout ensemble correspond un nombre cardinal. Le cardinal d'un ensemble fini à n éléments est n. Le cardinal de l'ensemble infini des nombres entiers naturels est noté (aleph-zéro), cf. alphabet hébreu.
est le plus petit nombre transfini cardinal. Il est plus grand que tout entier naturel. Deux ensembles ont le même cardinal lorsqu'ils sont en bijection. Ainsi, le cardinal de tout ensemble dénombrable infini est aussi , c'est le cas par exemple de l'ensemble des nombres algébriques. De manière plus générale, on montre que
les ensembles des types suivants sont infinis dénombrables
- l'union de avec un ensemble fini
- l'union d'une suite finie d'ensembles infinis dénombrables
- le produit d'une suite finie d'ensembles infinis dénombrables
Ces propriétés se traduisent sur le nombre transfini
par les formules suivantes
- pour tout entier naturel
-
- pour tout entier naturel
Mais l'infini ne se résume pas à . On montre à l'aide de l'argument diagonal de Cantor que l'ensemble des nombres réels n'est pas dénombrable. Si l'on note le nombre cardinal transfini associé à , on a donc
:.
est parfois noté par analogie avec les cardinaux finis car est en bijection avec l'ensemble des parties de . On a donc avec cette notation que
. De manière plus générale, on montre que
le cardinal de l'ensemble des parties d'un ensemble est toujours strictement plus gros que l'ensemble de départ. Ainsi,
:
Il existe donc une infinité de nombre cardinaux transfinis !
On a longtemps cherché à savoir s'il existait un nombre transfini strictement compris entre et , cf. hypothèse du continu. La réponse de Paul Cohen est plutôt surprenante, quoique présagée par Kurt Gödel.
Voir aussi
- Ensemble bien ordonné
- Récurrence transfinie
- Théorèmes de König
Ensemble dénombrableCatégorie:Nombre Catégorie:Théorie des ensembles
Un ensemble est dit dénombrable s'il est équipotent à l'ensemble des entiers naturels , c'est-à-dire s'il existe une bijection de sur (ou , voir plus bas) ; cela équivaut à l'existence d'une bijection de (ou ) sur .
Naïvement, dire qu'un ensemble E est dénombrable signifie qu'il est possible de compter un à un chacun de ses éléments, et de leur attribuer un rang : on peut numéroter les éléments de E sans omission ni répétition, en utilisant tous les entiers naturels.
L'ensemble des entiers naturels est dénombrable, car un ensemble est toujours équipotent à lui-même. Pour s'en convaincre, il suffit de remarquer que chaque élément de peut être associé à lui-même.
Tout ensemble équipotent à un ensemble dénombrable est lui-même dénombrable.
Un ensemble dénombrable est infini, car équipotent à , qui est infini. Mais la réciproque est fausse : il existe des ensembles infinis non dénombrables. Le mathématicien Cantor, qui introduisit la notion de dénombrabilité, démontra que l'ensemble des nombres réels, noté , n'est pas dénombrable.
Vocabulaire
L'expression ensemble dénombrable a deux définitions :
- Certaines publications emploient cette expression non seulement dans le sens vu ci-dessus mais aussi pour désigner un ensemble fini
- D'autres utilisent cette expression uniquement pour les ensembles satisfaisant la définition, et préfèrent employer l'expression ensemble au plus dénombrable pour désigner un ensemble soit fini, soit dénombrable.
Il faut donc prendre garde à la convention utilisée lors de la lecture d'une publication sur le sujet. Dans cet article, c'est la seconde acception qui sera utilisée.
Ensembles courants et dénombrabilité
- Par définition, l'ensemble des entiers naturels est dénombrable.
- L'ensemble des entiers naturels non nuls est dénombrable. En effet, l'application est bijective.
- L'ensemble des entiers naturels pairs, noté , est dénombrable. En effet, l'application est bijective.
- L'ensemble des carrés parfaits, noté ici , est dénombrable. En effet, l'application est bijective.
:On doit à Galilée la remarque qu'il y a "autant" de carrés parfaits que d'entiers naturels, mettant ainsi en défaut l'affirmation classique (qu'on trouve dans les Éléments d'Euclide): "le tout est plus grand que la partie".
- L'ensemble des entiers relatifs est dénombrable. En effet, l'application |
|
|
|
|