Cardinalité (mathématiques)

Galilée avait déjà remarqué qu'il y a autant d'entiers que d'entier pairs[2] au sens où, dit en termes contemporains, il existe une fonction bijective entre ces deux ensembles, soit, pour exemple parmi une infinité, la fonction ${\displaystyle f:x\mapsto 2x}$.

Ainsi il est possible que deux ensembles, dont l'un est strictement inclus dans l'autre aient la même taille en termes de bijectabilité.

Cette propriété étonnante découverte par Galilée se généralise au point que ce devient une définition :

• Un ensemble est infini si et seulement si il a la même cardinalité qu'un de ses sous ensembles propre.

La grande découverte de Cantor est que tous les ensembles infinis n'ont pas la même taille, la même cardinalité au sens de la bijectabilité : l'ensemble des entiers ${\displaystyle \mathbb {N} }$ et l'ensemble des réels ${\displaystyle \mathbb {R} }$ ne sont pas bijectables.

Ainsi prend fin une querelle philosophique millénaire concernant la différence ou non entre l'infini potentiel et l'infini en acte ; la réponse étant que tous les infinis illimités (potentiels) ne donnent pas la même cardinalité (infini en acte).

Bien plus Cantor démontre qu'aucun ensemble n'est de même cardinal que l'ensemble de ses parties, ce qui entraîne qu'il y a une infinité de cardinalités infinies.

Cantor ayant découvert que ${\displaystyle \mathbb {N} }$ et ${\displaystyle \mathbb {R} }$ ne sont pas bijectables, via que ${\displaystyle \mathbb {R} }$ a une cardinalité supérieure à celle de ${\displaystyle \mathbb {N} }$, se pose la question de savoir s'il existe un ensemble (par exemple un sous ensemble de ${\displaystyle \mathbb {R} }$) dont la taille est intermédiaire (en termes de bijectabilité) entre ${\displaystyle \mathbb {N} }$ et ${\displaystyle \mathbb {R} }$.

La réponse à cette question disant qu'un tel ensemble intermédiaire n'existe pas est nommée hypothèse du continu, celle ci se généralise : l'hypothèse généralisée du continu dit que les cardinalités infinies correspondent exactement avec celles que l'on obtient à partir de ${\displaystyle \mathbb {N} }$ en utilisant l' axiome de l'ensemble des parties.

L'indécidabilité de l'hypothèse du continu dans la théorie des ensembles usuelle a été démontrée par Gödel et Cohen.

Un ensemble ${\displaystyle E}$ est dit fini s'il est vide ou s'il existe un entier naturel ${\displaystyle n}$ non nul et une suite finie ${\displaystyle (x_{1},\ldots ,x_{n})}$ d'éléments de ${\displaystyle E}$ dans laquelle chaque élément de ${\displaystyle E}$ apparait exactement une fois. Autrement dit, un ensemble non vide est fini s'il est en bijection avec un intervalle d'entiers ${\displaystyle \{1,\ldots ,n\}}$.

Dans ce cas, le cardinal de ${\displaystyle E}$ est ${\displaystyle n}$.

La propriété fondamentale pour bien définir le cardinal d'un ensemble fini est l'unicité de l'entier ${\displaystyle n}$ correspondant. En effet, si un ensemble est en bijection avec deux intervalles d'entiers ${\displaystyle \{1,\ldots ,n\}}$ et ${\displaystyle \{1,\ldots ,p\}}$, alors ${\displaystyle n=p}$.

Soit ${\displaystyle E}$ et ${\displaystyle F}$ deux ensembles finis de cardinaux respectifs ${\displaystyle k}$ et ${\displaystyle n}$.

• Si ${\displaystyle E}$ et ${\displaystyle F}$ peuvent être mis en bijection, alors ${\displaystyle k=n}$.

• Tout sous-ensemble de ${\displaystyle E}$ est fini et de cardinal inférieur à ${\displaystyle k}$.
• Tout sous-ensemble strict de ${\displaystyle E}$ est de cardinal strictement inférieur[3] à ${\displaystyle k}$.
• Si ${\displaystyle A}$ est un sous-ensemble de ${\displaystyle E}$ alors le cardinal de son complémentaire est donné par la formule :

  ${\displaystyle \mathrm {Card} (E\setminus A)=\mathrm {Card} (E)-\mathrm {Card} (A).}$

• L'union et l'intersection de deux parties ${\displaystyle A}$ et ${\displaystyle B}$ de ${\displaystyle E}$ sont reliées par la formule :

  ${\displaystyle \mathrm {Card} (A\cup B)=\mathrm {Card} (A)+\mathrm {Card} (B)-\mathrm {Card} (A\cap B).}$

• L'union disjointe de ${\displaystyle E}$ et ${\displaystyle F}$ est finie de cardinal la somme ${\displaystyle k+n}$.
• Le produit cartésien de ${\displaystyle E}$ et ${\displaystyle F}$ est fini de cardinal le produit ${\displaystyle k\times n}$.
• L'ensemble des applications de ${\displaystyle E}$ dans ${\displaystyle F}$ est fini et de cardinal la puissance ${\displaystyle n^{k}}$ (avec la convention ${\displaystyle 0^{0}=1}$ si les deux ensembles sont vides).
• L'ensemble des parties de ${\displaystyle E}$ est fini de cardinal ${\displaystyle 2^{k}}$.
• L'ensemble des injections de ${\displaystyle E}$ dans ${\displaystyle F}$ est vide si ${\displaystyle k>n}$ et de cardinal donné par le quotient de factorielles ${\displaystyle n!/(n-k)!}$ sinon.
• En particulier, l'ensemble des permutations de ${\displaystyle E}$ est de cardinal ${\displaystyle k!}$.
• Le cardinal de l'ensemble des surjections de ${\displaystyle E}$ dans ${\displaystyle F}$ est donné par la somme suivante (qui est nulle si ${\displaystyle k<n}$ ) :

  ${\displaystyle \sum _{i=0}^{n}(-1)^{i}{\frac {n!}{i!(n-i)!}}(n-i)^{k}.}$

D'autres constructions usuelles à partir d'ensembles finis ont des cardinaux décrits par des formules explicites.