Voir la source de Introduction aux mathématiques/Rudiments de combinatoire

{{Chapitre
  | idfaculté = mathématiques
  | numéro    = 6
  | précédent = [[../Entiers naturels/]]
  | suivant   =[[../|Sommaire]] 
  | niveau    = 14
  | page_liée = Exercices/Ensembles infinis
}}
{{Définition
  | titre   = Définition
  | contenu =
On dit que deux ensembles <math>X</math> et <math>Y</math> sont équipotents, ou qu'ils ont même cardinal, s'il existe une bijection de <math>X</math> dans <math>Y</math>. On note alors : <math>X\sim Y</math>.
}}
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 <math>n\in\N</math>, on pose <math>\N_n=\{0,1,\dots,n-1\}</math>, en particulier <math>\N_0=\varnothing</math>.

{{Proposition
  | contenu =
Soit <math>p,n\in\N</math>.
S'il existe une injection de <math>\N_p</math> dans <math>\N_n</math>, alors <math>p\le n</math>.
}}
{{Démonstration déroulante|contenu=
On procède par récurrence sur ''n''. Si ''n'' = 0, le résultat se déduit du fait qu'il n'existe aucune application d'un ensemble non vide dans l'ensemble vide. On suppose le résultat pour N{{ind|''n''}}. Soit ''j'' une injection de N{{ind|''p''}} dans N{{ind|''n''+1}}. On doit montrer que ''p'' ≤ ''n'' + 1, ce qui est immédiat si ''p'' = 0. Supposons donc ''p'' ≠ 0. Si ''j''(''p'' – 1) = ''n'', ''j'' définit par restriction une injection de N{{ind|''p''–1}} dans N{{ind|''n''}} donc, par hypothèse de récurrence, ''p'' – 1 ≤ ''n''. Sinon, on se ramène à ce cas en composant ''j'' avec la [[Théorie des groupes/Groupes symétriques finis#Transpositions|transposition]] de N{{ind|''n''+1}} qui échange ''n'' et ''j''(''p'' – 1).
}}
On en déduit immédiatement :
{{Corollaire
  | contenu =
Soit <math>p,n\in\N</math>.
<math>\N_p\sim\N_n</math> (si et) seulement si <math>p=n</math>.
}}
Ceci permet de définir
{{Définition
  | titre   = Définition : ensembles finis, cardinal
  | contenu ={{Wikipédia|Ensemble fini}}
On dit d'un ensemble <math>E</math> qu’il est '''fini''' s'il existe <math>n\in\N</math> tel que <math>E</math> soit en bijection avec <math>\N_n</math>.

Dans ce cas cet entier est unique, et appelé '''cardinal''' de <math>E</math>, noté <math>\#E</math>, ou <math>\operatorname{card}(E)</math>, ou <math>|E|</math>.
}}

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

== Propriétés des ensembles finis ==
=== Parties d'un ensemble fini ===

{{Lemme
  | contenu =
Soient ''E'' un ensemble fini et ''A'' une partie de ''E'', alors ''A'' est fini et card(''A'') ≤ card(''E'').
}}
{{Démonstration déroulante|contenu=
Il suffit (à bijection près) de démontrer que toute partie de N{{ind|''n''}} est finie (son cardinal sera nécessairement inférieur ou égal à ''n'', d'après la proposition ci-dessus). On procède par récurrence sur ''n''. Si ''n'' = 0, c'est-à-dire si N{{ind|''n''}} = ∅, le résultat est immédiat. On suppose le résultat pour N{{ind|''n''}}. Soient ''F'' une partie de N{{ind|''n''+1}} et ''G'' = ''F''\{''n''}. Par hypothèse de récurrence, ''G'' est fini. Si ''n'' ∉ ''F'' alors ''F = G''. Si ''n'' ∈ ''F'', soit ''q'' le cardinal de ''G''. On complète une bijection de ''G'' dans N{{ind|''q''}} en une bijection de ''F'' = ''G''∪{''n''} dans N{{ind|''q''+1}} en associant à ''n'' l'entier ''q''.
}}
Ce lemme sera complété par le corollaire 1 ci-dessous.

=== Union d'ensembles finis  ===
{{Lemme
  | contenu =
#Si ''E'' et ''F'' sont deux ensembles finis ''disjoints'' alors ''E''∪''F'' est fini et card(''E''∪''F'') = card(''E'') + card(''F'').
#Si ''E'' est un ensemble fini et ''F'' un ensemble quelconque, alors les ensembles ''E''∩''F'' et ''E''\''F'' sont finis et card(''E'') = card (''E'' ∩ ''F'') + card (''E''\''F'').
}}
{{Démonstration déroulante|contenu=
#On note ''n'' = card(''E'') et ''p'' = card(''F'') et l'on fixe <math>f:E\to\N_n</math> et <math>g:F\to\N_p</math> deux bijections. On définit <math>\phi:E\cup F\to\N_{n+p},\,x\mapsto
\begin{cases} f(x)&\text{si }x\in E\\ g(x) +n&\text{si } x\in F,\end{cases}
</math> bien définie car <math>E\cap F=\varnothing</math> ; on définit également <math>\psi:\N_{n+p}\to E\cup F,\,k \mapsto
\begin{cases} f^{-1}(k)&\text{si }k\le n\\ g^{-1}(k-n)&\text{si }k>n.\end{cases}
</math><br />On vérifie qu’il s'agit de deux bijections réciproques l'une de l'autre, ce qui donne bien card(''E''∪''F'') = ''n + p'' = card(''E'') + card(''F'').
#Si ''E'' est fini alors ''E''∩''F'' et ''E''\''F'' aussi {{supra|Parties d'un ensemble fini}}. Comme ils sont disjoints, on peut leur appliquer ce qui précède. On conclut en utilisant que leur réunion est ''E''.
}}

{{Corollaire|titre=Corollaire 1|contenu=
Soient ''E'' un ensemble fini et ''A'' une partie de ''E''. Si card(''A'') = card(''E''), alors ''A'' = ''E''.
}}
{{Démonstration déroulante|contenu=Soit ''B'' = ''E''\''A''. D'après le lemme, ''B'' est fini et card(''E'') = card(''A'') + card(''B''), donc si card(''A'') = card(''E''), alors card(''B'') = 0 c'est-à-dire ''B'' = ∅, d'où ''A'' = ''E''.
}}
Remarque : ce résultat ne s'étend pas aux ensembles infinis : <math>\N</math> et <math>\N^*</math> sont équipotents bien que l'inclusion soit stricte.

{{Corollaire|titre=Corollaire 2 : cardinal d'une partition|contenu=
Soient <math>n\in\N</math> et <math>F_1,F_2,\dots,F_n</math> des ensembles finis deux à deux disjoints.

Alors l'ensemble <math>\bigsqcup_{i=1}^n F_i</math> est fini, de cardinal <math>\sum_{i=1}^n\left|F_i\right|</math>.
}}
{{Démonstration déroulante|contenu=
Par récurrence, grâce au point 1 du lemme (avec la convention, pour le cas ''n'' = 0, qu'une union indexée par ∅ est vide et qu'une somme indexée par ∅ est nulle).
}}

{{Corollaire|titre=Cas particulier d'une partition en parties équipotentes|contenu={{Wikipédia|Lemme des bergers}}
Soient <math>E</math> et <math>F</math> deux ensembles finis. Alors <math>E\times F</math> est fini, de cardinal <math>\left|E\right|\times\left|F\right|</math>.
}}
{{Démonstration déroulante|contenu=
On écrit la partition <math>E\times F=\bigsqcup_{x\in E}\{x\}\times F</math>, et on justifie que <math>\left|\{x\}\times F\right|=\left|F\right|</math> par la bijection <math>\{x\}\times F \rightarrow F, (x,y)\mapsto y</math>. Il suffit alors d'appliquer le corollaire 2.

Une variante plus directe consiste à supposer ([[Application (mathématiques)/Exercices/Bijections canoniques#Exercice 1|sans perte de généralité]]) que <math>E=\N_m</math> et <math>F=\N_n</math> et à vérifier que l'application <math>\N_m\times\N_n\to\N_{mn},\,(x,y)\mapsto x+my</math> est bijective.
}}

Ce résultat s'étend à un produit fini ; en particulier, on a <math>\left|F^m\right|=\left|F\right|^m</math>.

{{Corollaire|titre=Corollaire 3
  | contenu =Si ''E'' et ''F'' sont deux ensembles finis alors ''E''∪''F'' est fini et card(''E''∪''F'') = card(''E'') + card(''F'') – card(''E''∩''F'').
}}
{{Démonstration déroulante|contenu=
On applique le lemme à ''E''∪''F'' = (''E''\''F'')∪(''F''\''E'')∪(''F''∩''E'')   , ''E'' = (''E''\''F'')∪(''E''∩''F'') et ''F'' = (''F''\''E'')∪(''E''∩''F'').
}}

{{Corollaire
  | titre   = Généralisation : formule du crible
  | contenu =
Soient <math>n\in\N</math> et <math>F_1,F_2,\dots,F_n</math> des ensembles finis.

Alors l'ensemble <math>\bigcup_{i=1}^n F_i</math> est fini, de cardinal <math>\sum_{\varnothing\ne I\subset\N_n} (-1)^{\left|I\right|-1}\left|\cap_{i\in I}F_i\right|</math>.
}}

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 ===
{{Lemme
  | contenu =
Soit <math>E</math> un ensemble fini.
*Si <math>g:F\to E</math> est une injection, alors <math>F</math> est fini et <math>\left|F\right|\le\left|E\right|</math>, avec égalité si et seulement si <math>g</math> est bijective.
*Si <math>f:E\rightarrow F</math> est une surjection, alors <math>F</math> est fini et <math>\left|F\right|\le\left|E\right|</math>, avec égalité si et seulement si <math>f</math> est bijective.
}}
{{Démonstration déroulante|contenu=
*Si <math>g:F\to E</math> est une injection, alors son image est d'une part équipotente à <math>F</math> et d'autre part {{supra|Parties d'un ensemble fini}} finie, de cardinal inférieur ou égal à celui de <math>E</math>, avec égalité si et seulement si <math>g</math> est surjective.
*Sans perte de généralité, on peut supposer que <math>E=\N_n</math>. Si <math>f:\N_n\rightarrow F</math> est une surjection, l'application <math>g:F\to E, y\mapsto\min\left(f^{-1}(y)\right)</math> est injective, puisque <math>f\circ g=\operatorname{Id}_F</math>. D'après le point précédent, <math>F</math> est donc fini, de cardinal inférieur ou égal à celui de <math>E</math>, avec égalité si et seulement si <math>g</math> est bijective, c'est-à-dire (puisque <math>f\circ g=\operatorname{Id}_F</math>) si et seulement si <math>f</math> est bijective.
}}

{{Corollaire
  | contenu =
Soient <math>E</math>, <math>F</math> deux ensembles finis de même cardinal et <math>f:E\rightarrow F</math>.

Alors, <math>f</math> injective <math>\Leftrightarrow \;f</math> surjective <math>\Leftrightarrow \;f</math> bijective.
}}

== Quelques cardinaux usuels ==

{{Proposition
  | contenu =
Soient <math>E</math> et <math>F</math> deux ensembles finis. Alors, l'ensemble <math>F^E</math> des applications de <math>E</math> dans <math>F</math> est fini, de cardinal <math>\left|F\right|^{\left|E\right|}</math>.
}}
{{Démonstration déroulante|contenu=
Si <math>E</math> est vide, il n'y a en effet qu'une application partant du vide et la convention <math>n^0=1</math> valide la formule.

Si <math>F</math> est vide sans que <math>E</math> le soit, il n'existe aucune application de <math>E</math> dans <math>F</math>, ce qui donne bien <math>0=0</math>.

Traitons le cas plus significatif de deux ensembles non vides et supposons [[Application (mathématiques)/Exercices/Bijections canoniques#Exercice 1|sans perte de généralité]] que <math>E=\N_m</math>. L'application <math>F^{\N^m}\to F^m,\,f\mapsto (f(i-1))_{1\leq i\le m}</math> est une bijection, donc la proposition se déduit du corollaire vu précédemment sur le cardinal d'un produit de deux ensembles finis, via sa conséquence sur le cardinal d'une puissance finie d'ensemble fini.

;Variantes
:*Une variante s'appuie sur la définition par récurrence de la fonction exponentielle sur les entiers naturels : <math>n^0=1</math> et <math>n^{m+1}=n^m\times n</math>. On procède donc par récurrence sur <math>\left|E\right|</math>, en utilisant, pour l'hérédité, que pour <math>e\in E</math> fixé et <math>G=E\setminus\{e\}</math>, l'application <math>F^E\to F^G\times F,\,f\mapsto\left(f_{|G},f(e)\right)</math> est bijective.
:*Si <math>\left|F\right|=n\ge2</math>, une méthode plus directe, en supposant sans perte de généralité que <math>E=\N_m</math> et <math>F=\N_n</math>, consiste à remarquer que l'application <math>\N_n^{\N_m}\to\N_{n^m},\,f\mapsto\sum_{i=0}^{m-1}n^if(i)</math> est bijective (la bijection réciproque associe, à tout entier de <math>\N_{n^m}</math>, sa représentation en base <math>n</math>).
}}

Remarque : cela « justifie » un peu la notation <math>F^E</math>.

{{Corollaire
  | contenu =
Si <math>E</math> est fini alors l'ensemble <math>\mathcal P(E)</math> des parties de <math>E</math> est fini, de cardinal <math>2^{\left|E\right|}</math>.
}}
{{Démonstration déroulante|contenu=
L’application <math>\chi:\mathcal P(E)\rightarrow \{0,1\}^E,\,A\mapsto\chi_A</math>, où <math>\chi_A</math> désigne la fonction indicatrice de <math>A</math>, est bijective : cf. [[Application (mathématiques)/Application caractéristique]].
}}

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 ») :
{{Proposition
  | contenu =
*Le nombre d'injections d'un ensemble à ''k'' éléments dans un ensemble à ''n'' éléments est :
*:<math>A_n^k=\begin{cases}\frac{n!}{(n-k)!}&\text{ si }0\le k\le n\\0&\text{ sinon.}\end{cases}</math>
*Le nombre de parties à ''k'' éléments d'un ensemble à ''n'' éléments est :
*:<math>\binom nk=\begin{cases}\frac{n!}{k!\,(n-k)!}&\text{ si }0\le k\le n\\0&\text{ sinon.}\end{cases}</math>
}}

== Les infinis ==
{{Wikipédia|Cardinalité (mathématiques)|Cardinalité}}
{{Wikipédia|Nombre cardinal}}
=== Généralités ===

L'ensemble des entiers naturels nous a servi à classer les ensembles finis suivant leur cardinal. Mais par exemple <math>\N</math> 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.

{{Théorème|titre=Théorème de [[Histoire des mathématiques/Quelques mathématiciens célèbres|Cantor]]
  | contenu ={{Wikipédia|Théorème de Cantor}}
Soit <math>E</math> un ensemble. Alors il n'existe pas de surjection, et ''a fortiori'' pas de bijection, de <math>E</math> sur <math>\mathcal P(E)</math>.
}}
{{Démonstration déroulante|contenu=
Fixons une application <math>f:E\to\mathcal P(E)</math>. Pour montrer qu'elle n'est pas surjective, on s'intéresse à la partie <math>A</math> de <math>E</math> définie par <math>A:=\{x\in E\mid x\notin f(x)\}</math> et l'on constate que pour tout <math>a\in E</math>, <math>f(a)\ne A</math>, puisque <math>a\in A\Leftrightarrow a\notin f(a)</math>.
}}

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'[[w:Axiome du choix|axiome du choix]], la réciproque est vraie :
{{Proposition
  | contenu ={{Wikipédia|Ensemble infini}}
Si un ensemble <math>E</math> est infini, il existe une injection de <math>\N</math> dans <math>E</math>.
}}
{{Démonstration déroulante|contenu=
À l'aide de l'[[w:Axiome du choix dépendant|axiome du choix dépendant]], on peut construire par récurrence une suite d'injections <math>\phi_n:\N_n\rightarrow E</math>, de telle façon que <math>\phi_{n+1}</math> prolonge <math>\phi_n</math>. On pose alors <math>\phi:\N\rightarrow E,n\mapsto \phi_{n+1}(n)</math>, qui est bien injective : si <math>m<n</math> alors <math>\phi(m)\ne\phi(n)</math> car <math>\phi_{m+1}(m)=\phi_{n+1}(m)\ne\phi_{n+1}(n)</math>.

Pour des preuves n'utilisant que l'axiome du choix dénombrable, voir les articles de Wikipédia « Ensemble infini » et « [[w:Axiome du choix dénombrable|Axiome du choix dénombrable]] ».
}}
En quelque sorte, <math>\N</math> est le plus petit ensemble infini. On s'intéresse plus particulièrement à sa classe d'équipotence dans la section suivante.

=== Ensembles dénombrables ===
{{Définition
  | titre   = Définition : ensembles dénombrables
  | contenu ={{Wikipédia|Ensemble dénombrable}}
Un ensemble est dit '''dénombrable''' s'il est équipotent à <math>\N</math>. Il est dit '''au plus dénombrable''' s'il est fini ou dénombrable.
}}

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 :
# <math>\N^*</math> est dénombrable ;
# <math>\Z</math> est dénombrable ;
# <math>\N \times \N</math> est dénombrable ;
# <math>\Q</math> est dénombrable ;
# L'ensemble <math>\sqcup_{n\in\N^*}\Z^n</math> des suites finies non vides d'entiers relatifs est dénombrable ;
# L'ensemble <math>\mathcal P_{\mathrm f}(\N)</math>des parties finies de <math>\N</math> est dénombrable ;
#L'ensemble des [[Théorie des groupes/Caractères complexes des groupes finis, 1 : relations d'orthogonalité#Rappels sur les nombres algébriques|nombres algébriques]], c'est-à-dire des réels qui sont racines d'un polynôme non nul à coefficients entiers, est dénombrable.
{{Démonstration déroulante|contenu=
[[Image:Pairing natural.svg|thumb|La fonction de couplage de Cantor est une bijection de <math>\N</math> dans <math>\N\times\N</math>.]]
#L'application <math>n\mapsto n+1</math> est une bijection de <math>\N</math> dans <math>\N^*</math>.
#L'application <math>0\mapsto0</math>, <math>1\mapsto1</math>, <math>2\mapsto-1</math>, <math>3\mapsto2</math>, <math>4\mapsto-2</math>… est une bijection de <math>\N</math> dans <math>\Z</math>.
#La fonction de couplage de Cantor (illustration ci-contre) : <math>0\mapsto(0,0)</math>, <math>1\mapsto(1,0)</math>, <math>2\mapsto(0,1)</math>, <math>3\mapsto(2,0)</math>, <math>4\mapsto(1,1)</math>, <math>5\mapsto(0,2)</math>… est une bijection de <math>\N</math> dans <math>\N\times\N</math>.
#D'après les trois points précédents, <math>\Z\times\N^*</math> est dénombrable. À partir d'une bijection <math>\N\to\Z\times\N^*,\,n\mapsto(p_n,q_n)</math>, on définit par récurrence une bijection <math>f:\N\to\Q</math> en posant : <math>f(n):=p_m/q_m</math>, où <math>m</math> est le plus petit entier tel que <math>p_m/q_m\notin\{f(k)\mid k<n\}</math>.
#Soit, pour tout <math>n\in\N^*</math>, une bijection <math>f_n:\N\to\Z^n</math> obtenue grâce aux points 2 et 3. L'application <math>\N\times\N^*\to\sqcup_{n\in\N^*}\Z^n,\,(m,n)\mapsto f_n(m)</math> est bijective, or <math>\N\times\N^*</math> est dénombrable d'après les points 1 et 3.
#À partir d'une bijection <math>\N\to\sqcup_{n\in\N}\N^n,\,n\mapsto\left(x^n_1,\dots,x^n_{k_n}\right)</math> (construite comme au point précédent), on définit par récurrence une bijection <math>f:\N\to\mathcal P_{\mathrm f}(\N)</math> en posant : <math>f(n):=\left\{x^m_1,\dots,x^m_{k_m}\right\}</math>, où <math>m</math> est le plus petit entier tel que <math>\left\{x^m_1,\dots,x^m_{k_m}\right\}\notin\{f(k)\mid k<n\}</math>.
#
#* L'ensemble <math>\Z[X]</math> des polynômes à coefficients entiers est dénombrable.
#* Le nombre de racines réelles d'un polynôme non nul est fini.
}}

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

{{définition|contenu={{Wikipédia|Aleph (nombre)|Aleph}}
On dit qu'un ensemble a pour cardinal <math>\aleph_0</math> (lire « aleph-0 ») s'il est dénombrable.

On note <math>\aleph_1</math> le plus petit cardinal infini non dénombrable<ref>Cette définition nécessite l'axiome du choix.</ref>.
}}

En raisonnant par l'absurde, et en utilisant l'[[w:Argument de la diagonale de Cantor|argument de la diagonale de Cantor]], on peut démontrer que <math>\R</math> 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 :
{{Théorème|contenu={{Wikipédia|Puissance du continu}}
<math>\R</math> est équipotent à l'ensemble des parties de <math>\N</math>.
}}
{{Démonstration déroulante|contenu=
Il revient au même — en identifiant chaque partie de <math>\N</math> à sa [[Application (mathématiques)/Définitions#Exemples d’applications|fonction indicatrice]] — d'affirmer que <math>\R</math> est équipotent à l'ensemble <math>\{0,1\}^{\N}</math> des suites de zéros et de uns. Parmi ces suites, notons ''N'' l'ensemble (dénombrable) constitué de la suite nulle et des suites qui se terminent par une infinité de uns, et ''X'' son complémentaire, qui contient un ensemble dénombrable (par exemple : les suites non nulles se terminant par une infinité de zéros). Alors (cf. [[../Exercices/Ensembles infinis#Exercice 1-4|exercice 1-4]]), <math>\{0,1\}^{\N}=X\cup N</math> est équipotent à ''X'', qui est en bijection (via les développements propres en base 2) avec l'intervalle réel ]0, 1[. Enfin, l'application <math>\left]0,1\right[\to\R,\,x\mapsto\frac1x+\frac1{x-1}</math> est bijective.
}}

Par conséquent, <math>\left|\R\right|\ge\aleph_1</math>. On ne sait pas<ref>Plus précisément, on ne peut pas décider avec le jeu d'axiomes usuel [[w:Théorie des ensembles de Zermelo-Fraenkel|ZFC]] ([[w:Kurt Gödel|Gödel]] 1938, [[w:Paul Cohen|Cohen]] 1963).</ref> si <math>\left|\R\right|>\aleph_1</math> ou <math>\left|\R\right|=\aleph_1</math>. On dit qu'un ensemble a la puissance du continu s'il est équipotent à <math>\R</math>. On fait souvent l'''[[w:Hypothèse du continu|hypothèse du continu]]'', qui consiste à admettre que <math>\left|\R\right|=\aleph_1</math>.


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, <math>\R</math> est, au sens de l’injectabilité, « strictement plus grand » que <math>\N</math>. On en déduit un résultat important :

{{Théorème
  | contenu ={{Wikipédia|Nombre transcendant}}
L'ensemble des nombres réels transcendants, c'est-à-dire non algébriques, a la puissance du continu.
}}
{{Démonstration déroulante|contenu=
L'ensemble Alg des réels algébriques est dénombrable {{supra|Ensembles dénombrables}} donc n'est pas égal à <math>\R</math> tout entier. L'ensemble Trans des réels transcendants est donc non vide ; il contient même un ensemble dénombrable (par exemple <math>\{t^n\mid n\in\N^*\}</math>, où <math>t</math> est un réel transcendant arbitraire). Par conséquent ([[../Exercices/Ensembles infinis#Exercice 1-4|exercice 1-4]]), Trans est équipotent à Trans ∪ Alg = <math>\R</math>.
}}
A fortiori, l’ensemble <math>\R\setminus\Q</math> des nombres irrationnels a la puissance du continu.

== Notes ==
{{Références}}

{{Bas de page
  | idfaculté = mathématiques
  | précédent = [[../Entiers naturels/]]
  | suivant   =[[../|Sommaire]] 
}}