🔎 Nombre cardinal : définition et explications

Nombre cardinal

théorie axiomatique des ensembles théorie des ensembles mathématiques

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.)

Ensembles finis

Pour un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.), son cardinal est son nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'éléments (zéro, pour l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui...) vide) :

$\mathrm{card}(\varnothing) = 0$

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 :

$\mathrm{card \,Corr}\,( E, F) = 2^{np}$

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 (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du sur-ensemble B. Il peut par contre y avoir des...) du précédent, qui peut être noté " Fnct( E, F) ". Le nombre de ces fonctions est :

$\mathrm{card\, Fnct}\,( E, F) = (n+1)^p$

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 :

$\mathrm{card \,Appl}\,( E, F) = n^p$

Cette propriété explique pourquoi Appl( E, F) est le plus souvent noté " $F^E \,$ ".

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 :

$\mathrm{card \,Inj}\,( E, F) = \frac{n! }{ (n-p)! }$

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 :

$\mathrm{card\, Surj}\,( E, F) = \sum_{i = 0}^{n} (-1)^{i} \frac{ n! }{ i! (n - i)! } (n - i)^{p}$

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 :

$\mathrm{card \,Bij}( E, F) = n!$ .

Ensembles infinis

On dit que deux ensembles infinis ont même cardinal s'il existe une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans l’ensemble de définition X tel que...) 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 $\mathfrak P(E)$ 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 (En linguistique, les mots premier, deuxième, troisième, quatrième, etc. s'appellent des adjectifs numéraux ordinaux. En mathématiques, cette notion...) é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 (Il existe plusieurs versions formelles de la théorie des ensembles, mais quand on parle de « la » théorie axiomatique des ensembles, on désigne habituellement sous ce nom la théorie ZFC. Au XXIe siècle, c'est la théorie sur...) 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 (Un axiome (du grec ancien αξιωμα/axioma, « considéré comme digne, convenable, évident en soi ») désigne une...) du choix à ZF, donnant la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent...) ZFC (En mathématiques, l'abréviation ZF désigne la théorie de Zermelo-Fraenkel, ZFC quand elle comprend l'axiome du choix, théorie axiomatique des...), on peut montrer que tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) ensemble est équipotent à un cardinal.

Les cardinaux infinis sont représentés au moyen de la lettre hébraïque aleph $\aleph$ . Le plus petit cardinal infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en nombre ou en taille.) est $\aleph_0$ . C'est le cardinal de l'ensemble $\mathbb N$ des entiers naturels, qui est également désigné en tant que nombre ordinal par $ω$ . Le cardinal immédiatement supérieur est $\aleph_1$ , etc. D'une manière générale, un cardinal quelconque s'écrit $\aleph_\alpha$ où $α$ est un ordinal.

S'il existe une injection (Le mot injection peut avoir plusieurs significations :) d'un ensemble $A$ dans un ensemble $B$ , on note $\mathrm{card}(A) \leq \mathrm{card}(B)$ . S'il existe une injection de $A$ dans $B$ mais pas de bijection, on note $card(A) < card(B)$ .

Exemples :

$\mathrm{card} (\mathbb{N}) = \aleph_0 < \mathrm{card} (\mathbb{R}) = 2^{\aleph_0}$

où l'on note $2^{\aleph_0}$ le cardinal de l'ensemble des fonctions de $\aleph_0$ dans ${0,1}$ , équipotent à $\mathfrak P(\mathbb{N})$ . Ce cardinal étant égal à celui de $\mathbb R$ , on le note également $\mathfrak c$ , dit cardinal du continu.

Cependant, et cela ne semble pas intuitif au premier abord :

$\mathrm{card} (\mathbb{N}) = \mathrm{card} (\mathbb{Q})$ (cf. ensemble dénombrable)

Le cardinal de l'ensemble des fonctions continues de $\mathbb R$ dans $\mathbb R$ est égal à $\mathfrak c$ , cardinal de $\mathbb R$ .

Le cardinal de l'ensemble des fonctions de $\mathbb R$ de $\mathbb R$ est $2^{\mathfrak c} > \mathfrak c$ .

Propriétés

$A \subset B \Longrightarrow \mathrm{card}(A) \le \mathrm{card}(B)$

$A \;{\rm infini} \iff \mathrm{card}(A) = \mathrm{card}(A \cup \{A\})$

$\mathrm{card}(E) < \mathrm{card}(\mathfrak P(E)) = 2^{\mathrm{card}(E)}$ . Si $E$ est infini et si $\mathfrak F(E)$ désigne l'ensemble des parties finies de $E$ , alors $\mathrm{card}(E) = \mathrm{card}(\mathfrak F(E))$

si les ensembles sont finis, $\mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B)$

si $A$ est infini et $B$ non vide, alors $\mathrm{card}(A \cup B) = \mathrm{card}(A \times B) = \max(\mathrm{card}(A), \mathrm{card}(B))$

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 $2 \le \mathrm{card}(B) \le \mathrm{card}(A)$ , alors $card(B A) = 2 card(A)$ où $B A$ désigne l'ensemble des fonctions de $A$ dans $B$

si $f$ est une fonction de $A$ dans $B$ , alors $\mathrm{card}(f(A)) \le \mathrm{card}(A)$

si $A$ est infini, alors $\mathrm{card}(A \times A) = \mathrm{card}(A)$

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 (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par...) suivant :

$\forall \gamma \in \alpha, \exists \delta \in \beta, \gamma \le f(\delta)$

Par exemple, $\aleph_0$ n'est cofinal avec aucun ordinal plus petit, puisqu'un ordinal inférieur à $\aleph_0$ 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 $\aleph_0$ est régulier, c'est le cas de tous les cardinaux successeurs.

Par contre, $\aleph_{\omega}$ est cofinal avec $ω$ au moyen de l'application $f : n \in \omega \to \aleph_n$ . On dit que $\aleph_{\omega}$ est singulier.

Si on note $cf(α)$ le plus petit ordinal avec lequel $α$ est cofinal, on a $cf(ω) = ω$ et ${\rm cf}(\aleph_{\omega}) = \omega$ .

On peut classer alors les cardinaux comme suit :

Les cardinaux de la forme $\aleph_{\alpha+1}$ , indicé par un ordinal $α + 1$ successeur d'un ordinal $α$ .
Les cardinaux de la forme $\aleph_\alpha$ , 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 $\aleph_\alpha$ , 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 $\mathrm{card}(x) < \aleph_{\alpha} \Longrightarrow 2^{\mathrm{card}(x)} < \aleph_{\alpha}$ . L'existence de tels cardinaux ne peut se déduire des axiomes de la théorie des ensembles (La théorie des ensembles est une branche des mathématiques créée initialement par le mathématicien allemand Georg Cantor à la fin du XIXe siècle.) ZFC.

L'hypothèse du continu

Nous avons énoncé que $\mathrm{card} (\mathbb{N}) = \aleph_0 < \mathrm{card} (\mathbb{R}) = 2^{\aleph_0}$ . Or $\aleph_1$ est le plus petit cardinal strictement supérieur à $\aleph_0$ . On a donc $\aleph_1 \le 2^{\aleph_0}$ et l'hypothèse du continu pose la question de savoir si $\aleph_1 = 2^{\aleph_0}$ . 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 $\aleph_{\alpha+1} = 2^{\aleph_{\alpha}}$ .

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 $\aleph_{\alpha}^{\aleph_{\beta}}$ l'ensemble des fonctions de $\aleph_{\beta}$ dans $\aleph_{\alpha}$ . Alors :

$\mathrm{card}(\aleph_{\alpha}^{\aleph_{\beta}}) = \aleph_{\alpha}$ si $\aleph_{\beta} < {\rm cf}(\aleph_{\alpha})$
$\mathrm{card}(\aleph_{\alpha}^{\aleph_{\beta}}) = \aleph_{\alpha+1}$ si ${\rm cf}(\aleph_{\alpha}) \le \aleph_{\beta} \le \aleph_{\alpha}$
$\mathrm{card}(\aleph_{\alpha}^{\aleph_{\beta}}) = \aleph_{\beta+1}$ si $\aleph_{\alpha} \le \aleph_{\beta}$

Voir aussi

Une nouvelle méthode pour multiplier les très grands nombres

Un seul bit vous manque, et ça ne compresse plus

L'agriculture croît dans les mathématiques

Analyse multivariée d'algorithmes: au-delà des problèmes NP-difficiles

Page générée en 0.107 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique