Introduction aux mathématiques/Rudiments de combinatoire

Modèle:Chapitre Modèle:Définition 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

Pour tout $n\in \mathbb{N}$, on pose ${\mathbb{N}}_n=\{0,1,\dots ,n-1\}$, en particulier ${\mathbb{N}}_0=\varnothing$.

Modèle:Proposition Modèle:Démonstration déroulante On en déduit immédiatement : Modèle:Corollaire Ceci permet de définir Modèle:Définition

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

Propriétés des ensembles finis

Parties d'un ensemble fini

Modèle:Lemme Modèle:Démonstration déroulante Ce lemme sera complété par le corollaire 1 ci-dessous.

Union d'ensembles finis

Modèle:Corollaire Modèle:Démonstration déroulante Remarque : ce résultat ne s'étend pas aux ensembles infinis : $\mathbb{N}$ et ${\mathbb{N}}^{*}$ sont équipotents bien que l'inclusion soit stricte.

Ce résultat s'étend à un produit fini ; en particulier, on a $\left|F^m\right|={\left|F\right|}^m$.

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

Quelques cardinaux usuels

Remarque : cela « justifie » un peu la notation $F^E$.

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 ») : Modèle:Proposition

Les infinis

Généralités

L'ensemble des entiers naturels nous a servi à classer les ensembles finis suivant leur cardinal. Mais par exemple $\mathbb{N}$ 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 [[../Relations binaires#Avec l’ordre|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.

Tout ensemble contenant un ensemble dénombrable est infini (pour plus de détails, voir l'[[../Exercices/Ensembles infinis#Exercice 1-3|exercice 1-3]]). En supposant une version faible de l'axiome du choix, la réciproque est vraie : Modèle:Proposition Modèle:Démonstration déroulante En quelque sorte, $\mathbb{N}$ est le plus petit ensemble infini. On s'intéresse plus particulièrement à sa classe d'équipotence dans la section suivante.

Ensembles dénombrables

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. ${\mathbb{N}}^{*}$ est dénombrable ;
2. $\mathbb{Z}$ est dénombrable ;
3. $\mathbb{N}\times \mathbb{N}$ est dénombrable ;
4. $\mathbb{Q}$ est dénombrable ;
5. L'ensemble ${\bigsqcup }_{n\in {\mathbb{N}}^{*}}{\mathbb{Z}}^n$ des suites finies non vides d'entiers relatifs est dénombrable ;
6. L'ensemble ${𝒫}_{\mathrm{f}}(\mathbb{N})$des parties finies de $\mathbb{N}$ est dénombrable ;
7. L'ensemble des nombres algébriques, c'est-à-dire des réels qui sont racines d'un polynôme non nul à coefficients entiers, est dénombrable.

Ensembles non dénombrables

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 : Modèle:Théorème Modèle:Démonstration déroulante

Par conséquent, $\left|ℝ\right|\ge {\mathrm{\aleph }}_1$. On ne sait pas si $\left|ℝ\right|>{\mathrm{\aleph }}_1$ ou $\left|ℝ\right|={\mathrm{\aleph }}_1$. 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 $\left|ℝ\right|={\mathrm{\aleph }}_1$.

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 l’injectabilité, « strictement plus grand » que $\mathbb{N}$. On en déduit un résultat important :

Modèle:Théorème Modèle:Démonstration déroulante A fortiori, l’ensemble $ℝ\setminus \mathbb{Q}$ des nombres irrationnels a la puissance du continu.