Leçons de niveau 14

Introduction aux mathématiques/Rudiments de combinatoire

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Rudiments de combinatoire
Icône de la faculté
Chapitre no 6
Leçon : Introduction aux mathématiques
Chap. préc. :Entiers naturels

Exercices :

Ensembles infinis
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Introduction aux mathématiques : Rudiments de combinatoire
Introduction aux mathématiques/Rudiments de combinatoire
 », n'a pu être restituée correctement ci-dessus.


Cette « relation binaire » (qui n'en n'est pas une car la classe de tous les ensembles n'est pas un ensemble) est clairement une « relation » d'équivalence.

Ensembles finis[modifier | modifier le wikicode]

Pour tout , on pose , en particulier .



On en déduit immédiatement :


Ceci permet de définir



Ainsi dans « l’ensemble » des ensembles finis, le cardinal caractérise les « classes d'équivalence » de la « relation » .

Propriétés des ensembles finis[modifier | modifier le wikicode]

Parties d'un ensemble fini[modifier | modifier le wikicode]

Début d'un lemme


Fin du lemme

Ce lemme sera complété par le corollaire 1 ci-dessous.

Union d'ensembles finis[modifier | modifier le wikicode]

Début d'un lemme


Fin du lemme



Remarque : ce résultat ne s'étend pas aux ensembles infinis : et sont équipotents bien que l'inclusion soit stricte.





Ce résultat s'étend à un produit fini ; en particulier, on a .






On peut déduire cette généralisation du corollaire 3 (par récurrence), ou la démontrer directement : voir Formule du crible.

Applications entre ensembles finis[modifier | modifier le wikicode]

Début d'un lemme


Fin du lemme




Quelques cardinaux usuels[modifier | modifier le wikicode]


Remarque : cela « justifie » un peu la notation .



Signalons enfin qu'à l'aide du corollaire 2 ci-dessus appliqué à des partitions en fibres (chap. 3), on démontre successivement les deux propriétés suivantes (cf. Combinatoire, chapitres « Arrangements sans répétition » et « Combinaisons sans répétition ») :



Les infinis[modifier | modifier le wikicode]

Wikipédia possède un article à propos de « Cardinalité ».
Wikipédia possède un article à propos de « Nombre cardinal ».

Généralités[modifier | modifier le wikicode]

L'ensemble des entiers naturels nous a servi à classer les ensembles finis suivant leur cardinal. Mais par exemple lui-même n’est pas fini, c’est un exemple d'ensemble infini. On souhaiterait quand même les classer. L’idée intuitive est que si l’on peut injecter un ensemble dans un autre, alors le premier est plus petit.

Cette « relation binaire » est réflexive (l'identité est injective) et transitive (la composée d'injections l'est aussi). C'est un « pré-ordre » et le théorème de Cantor-Bernstein montre que la « relation » d'équivalence associée est exactement l'équipotence.

La seconde question qui vient est : tous les ensembles infinis sont-ils équipotents entre eux ? La proposition suivante y répond par la négative, mais laisse entrevoir une théorie intéressante traitant des cardinaux infinis.

Début d’un théorème


Fin du théorème

Tout ensemble contenant un ensemble dénombrable est infini (pour plus de détails, voir l'exercice 1-3). En supposant une version faible de l'axiome du choix, la réciproque est vraie :


En quelque sorte, est le plus petit ensemble infini. On s'intéresse plus particulièrement à sa classe d'équipotence dans la section suivante.

Ensembles dénombrables[modifier | modifier le wikicode]



Outre l’intérêt purement théorique de cette notion, et des « cardinaux infinis », on peut citer quelques exemples d'application. On les mentionne pour culture, mais ils supposent une certaine familiarité avec des notions non encore introduites.

Voici d’abord quelques exemples classiques d'ensembles dénombrables :

  1. est dénombrable ;
  2. est dénombrable ;
  3. est dénombrable ;
  4. est dénombrable ;
  5. L'ensemble des suites finies non vides d'entiers relatifs est dénombrable ;
  6. L'ensemble des parties finies de est dénombrable ;
  7. L'ensemble des nombres algébriques, c.-à-d. des réels qui sont racines d'un polynôme non nul à coefficients entiers, est dénombrable.

Ensembles non dénombrables[modifier | modifier le wikicode]

La notion de cardinal d'un ensemble fini s'étend aux ensembles infinis ; par exemple :




En raisonnant par l'absurde, et en utilisant l'argument de la diagonale de Cantor, on peut démontrer que n'est pas dénombrable. Mais démontrons plutôt un énoncé qui, au vu du théorème de Cantor ci-dessus, est plus précis :

Début d’un théorème


Fin du théorème

Par conséquent, . On ne sait pas[2] si ou . On dit qu'un ensemble a la puissance du continu s'il est équipotent à . On fait souvent l'hypothèse du continu, qui consiste à admettre que .


Puisque l’ensemble des entiers naturels est compris dans celui des nombres réels, et que l’ensemble des nombres réels n’est pas dénombrable, est, au sens de injectabilité, « strictement plus grand » que . On en déduit un résultat important :

Début d’un théorème


Fin du théorème

A fortiori, l’ensemble des nombres irrationnels a la puissance du continu.

Notes[modifier | modifier le wikicode]

  1. Cette définition nécessite l'axiome du choix.
  2. Plus précisément, on ne peut pas décider avec le jeu d'axiomes usuel ZFC (Gödel 1938, Cohen 1963).