Nombre cardinal - Définition
En linguistique, les nombres entiers naturels zéro, un, deux, trois, etc. s'appellent des adjectifs numéraux cardinaux. En mathématiques, un nombre cardinal est une extension de cette notion pour dénombrer les ensembles, y compris des ensembles infinis.
Définition
Ensembles finis
Pour un ensemble fini, son cardinal est son nombre d'éléments (zéro, pour l'ensemble vide) :
- card({1,2,5}) = 3
Voici d'autres exemples, relatifs aux fonctions et relations.
Soient E et F deux ensembles finis, E de cardinal p et F de cardinal n. 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 finis, 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 :
-
.
Ensembles infinis
On dit que deux ensembles infinis ont même cardinal s'il existe une bijection de l'un sur l'autre. On dit aussi qu'ils sont équipotents. On montre qu'il n'existe aucune bijection entre un ensemble E et l'ensemble de ses parties 
et donc qu'il existe plusieurs tailles d'ensembles infinis. Ces différents infinis sont représentés par des nombres cardinaux transfinis : le cardinal d'un ensemble E est alors défini comme étant le plus petit nombre ordinal équipotent à E. De manière plus formelle, on définit un cardinal comme étant un ordinal qui n'est équipotent à aucun de ses éléments.
Dans la théorie axiomatique des ensembles de Zermelo-Fraenkel (ZF), l'existence d'un ordinal équipotent à un ensemble quelconque n'est pas assurée. Dans ce cas, il est judicieux de se limiter aux ensembles pour lesquels un tel ordinal existe. Par contre, si on ajoute l'axiome du choix à ZF, donnant la théorie ZFC, on peut montrer que tout ensemble est équipotent à un cardinal.
Les cardinaux infinis sont représentés au moyen de la lettre hébraïque aleph 
. Le plus petit cardinal infini est 
. C'est le cardinal de l'ensemble 
des entiers naturels, qui est également désigné en tant que nombre ordinal par ω. Le cardinal immédiatement supérieur est 
, etc. D'une manière générale, un cardinal quelconque s'écrit 
où α est un ordinal.
S'il existe une injection d'un ensemble A dans un ensemble B, on note 
. S'il existe une injection de A dans B mais pas de bijection, on note card(A) < card(B).
Exemples :
où l'on note 
le cardinal de l'ensemble des fonctions de dans {0,1}, équipotent à 
. Ce cardinal étant égal à celui de 
, on le note également 
, dit cardinal du continu.
- Cependant, et cela ne semble pas intuitif au premier abord :
-
(cf. ensemble dénombrable)
- Le cardinal de l'ensemble des fonctions continues de dans est égal à , cardinal de .
- Le cardinal de l'ensemble des fonctions de de est
\mathfrak c" />.
Propriétés
. Si E est infini et si 
désigne l'ensemble des parties finies de E, alors 
- si les ensembles sont finis,
- si A est infini et B non vide, alors
- Si B est inclus dans A infini et si card(B) < card(A), alors card(A − B) = card(A)
- Si A est infini et si
, alors card(BA) = 2card(A) où BA désigne l'ensemble des fonctions de A dans B
- si f est une fonction de A dans B, alors
- si A est infini, alors
Les cardinaux inaccessibles
On s'intéresse maintenant aux possibilités d'atteindre un ordinal ou un cardinal donné à partir des ordinaux plus petits. On dit qu'un ordinal α est cofinal avec un ordinal β inférieur à α s'il existe une application strictement croissante f de β dans α tel que α soit la limite de f au sens suivant :
Par exemple, n'est cofinal avec aucun ordinal plus petit, puisqu'un ordinal inférieur à est un entier n = {0,1,...,n − 1} et qu'une application strictement croissante définie sur {0,1,...,n − 1} est bornée. On dit que est régulier, c'est le cas de tous les cardinaux successeurs.
Par contre, 
est cofinal avec ω au moyen de l'application 
. On dit que est singulier.
Si on note cf(α) le plus petit ordinal avec lequel α est cofinal, on a cf(ω) = ω et 
.
On peut classer alors les cardinaux comme suit :
- Les cardinaux de la forme
, indicé par un ordinal α + 1 successeur d'un ordinal α. - Les cardinaux de la forme , indicé par un ordinal α limite, et qui sont singuliers. Ces deux types de cardinaux sont qualifiés d'accessibles, car concevables à partir de cardinaux plus petits qu'eux.
- Les cardinaux de la forme , indicé par un ordinal α limite, et qui sont réguliers. Ce type de cardinal est qualifié de faiblement inaccessibles car ils ne peuvent être conçus à partir de cardinaux plus petits. Parmi ces derniers, on distingue les cardinaux fortement inaccessibles qui vérifient de plus
. L'existence de tels cardinaux ne peut se déduire des axiomes de la théorie des ensembles ZFC.
L'hypothèse du continu
Nous avons énoncé que 
. Or est le plus petit cardinal strictement supérieur à . On a donc 
et l'hypothèse du continu pose la question de savoir si 
. On montre que cette propriété est indécidable dans ZFC. Plus généralement, l'hypothèse généralisée du continu énonce que, pour tout ordinal α, on a 
.
Si on admet comme axiome l'hypothèse généralisée du continu alors :
- l'axiome du choix est démontrable.
- Il y a équivalence entre les notions de cardinaux faiblement inaccessibles et fortement inaccessibles.
Notons 
l'ensemble des fonctions de 
dans 
. Alors :
si 
si 
si 