Nombre cardinal

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir Cardinal.

En mathématiques, la cardinalité est une notion de taille pour les ensembles. Les nombres cardinaux permettent donc de mesurer l'ampleur de tout ensemble, même infini, là où les entiers naturels ne comptent le nombre d'éléments que d'ensembles finis.

Sommaire

1 Définitions
- 1.1 Classe d'ensembles
- 1.2 Ordinal
2 Propriétés générales
- 2.1 Théorème fondamental
3 Cardinal fini
- 3.1 Propriétés
- 3.2 Opérations ensemblistes
4 Cardinal infini
- 4.1 Exemples
- 4.2 Propriétés
5 Cardinal inaccessible
6 Hypothèse du continu
7 Voir aussi

[modifier] Définitions

[modifier] Classe d'ensembles

Deux ensembles sont dits équipotents s'il existe une bijection de l'un sur l'autre. La relation étant réflexive, symétrique et transitive sur la classe des ensembles, chaque classe d'équivalence est appelé nombre cardinal ou simplement cardinal.

S'il existe une injection d'un ensemble A dans un ensemble B alors le cardinal de A est dit plus petit que le cardinal de B, ce qui se note $\mathrm{card}(A) \le \mathrm{card}(B)$ . Dans ce cas, il existe une injection de n'importe quel ensemble équipotent à A dans n'importe quel ensemble équipotent à B. En outre, le théorème de Cantor-Bernstein permet de montrer que si deux cardinaux sont tous les deux plus petits l'un que l'autre, alors ils sont égaux. Cette relation est donc une relation d'ordre sur les cardinaux.

L'ensemble vide et les ensembles d'entiers de la forme $\left\{1, \dots, n\right\}$ forment des ensembles de cardinaux deux à deux différents.
Un ensemble est dit fini s'il est équipotent à l'un de ces ensembles, infini dans le cas contraire. Tout cardinal fini est inférieur à tout cardinal infini.

On note $\mathrm{card}(\emptyset) = 0\$ et $\ \mathrm{card}\left(\left\{1, \dots, n\right\}\right) = n$ , de sorte que l'ordre sur les cardinaux prolonge l'ordre sur les entiers naturels.

[modifier] Ordinal

Dans la théorie axiomatique des ensembles de Zermelo-Fraenkel (ZF), l'adjonction de l'axiome du choix (donnant la théorie ZFC) permet de définir le cardinal d'un ensemble comme le plus petit nombre ordinal qui lui est équipotent. Un nombre cardinal est alors un ordinal qui n'est équipotent à aucun de ses éléments.

En dehors de l'hypothèse de l'axiome du choix, il peut être judicieux de se limiter aux ensembles pour lesquels un tel ordinal équipotent existe.

[modifier] Propriétés générales

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

[modifier] Théorème fondamental

Un ensemble E n'est jamais équipotent à l'ensemble de ses parties $\mathfrak P(E)$ , bien qu'il s'injecte dedans par l'ensemble des singletons de E, ce qui permet s'écrire :

$\mathrm{card}(E) < \mathrm{card}(\mathfrak P(E))$ .

C'est le théorème de Cantor.

Ce résultat justifie le fait qu'il existe des infinis de cardinaux différents. Il donne même un procédé de construction d'une infinité d'entre eux par itération.

Les cardinaux infinis sont représentés au moyen de la lettre hébraïque aleph $\ \aleph$ . Le plus petit cardinal infini 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.

[modifier] Cardinal fini

Le cardinal d'un ensemble fini correspond donc simplement au nombre d'éléments qu'il contient. Par exemple, $card({1,2,5}) = 3$ .

[modifier] Propriétés

Toute partie d'un ensemble fini est finie.
Si A et B sont deux parties d'un ensemble fini, alors $\mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B)$ .
Si A est une partie d'un ensemble fini E alors $\ \mathrm{card}(E-A) = \mathrm{card}(E) - \mathrm{card}(A)$

[modifier] Opérations ensemblistes

Soient E et F deux ensembles finis avec E de cardinal k et F de cardinal n.

La somme disjointe $E\sqcup F$ est fini de cardinal

$\mathrm{card}(E\sqcup F) = n+k$ .

Le produit cartésien $E\times F$ est fini de cardinal

$\mathrm{card}(E\times F) = nk$ .

L'ensemble des applications de E dans F, parfois noté $Appl(E, F)$ est fini de cardinal

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

avec la convention 0⁰=1 si E et F sont tous deux vides.

Cette propriété justifie la notation plus courante

F E

L'ensemble $\mathfrak P(E)$ des parties de E, qui s'identifie à l'ensemble des applications de E dans $\left\{0,1\right\}$ , est donc fini et de cardinal

$\mathrm{card}(\mathfrak P(E)) = 2^k$ .

L'ensemble des correspondances de E dans F, noté habituellement $Corr(E, F)$ , s'identifie à $\mathfrak P(E\times F)$ donc est fini de cardinal

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

L'ensemble des fonctions de E dans F, souvent noté $\mathcal{F}(E, F)$ , est un sous-ensemble du précédent, de cardinal

$\mathrm{card}(\mathcal{F}(E, F)) = (n+1)^k$ .

L'ensemble des injections de E dans F, noté habituellement $Inj(E, F)$ , est vide si $card(E) > card(F)$ . Dans le cas contraire,

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

L'ensemble des surjections de E dans F, noté habituellement $Surj(E, F)$ , est vide si $card(E) < card(F)$ . Dans le cas contraire,

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

L'ensemble des bijections de E dans F, noté habituellement $Bij(E, F)$ , est vide si $\mathrm{card}(E)\neq\mathrm{card}(F)$ . Dans le cas contraire :

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

[modifier] Cardinal infini

Si $A$ est infini alors $\mathrm{card}(\mathfrak P(A))$ est noté $2 card(A)$ par analogie avec le cas fini.

[modifier] Exemples

Le cardinal de l'ensemble des nombres réels est le même que celui de l'ensemble des parties de $\N$ :

$\mathrm{card}(\R) = 2^{\aleph_0} > \aleph_0 = \mathrm{card}(\N)$ .

Ce cardinal étant égal à celui de $\mathbb R$ , on le note également $\mathfrak c$ , dit cardinal du continu.

Cependant, contrairement à l'intuition première, les ensembles d'entiers naturels et des rationnels sont équipotents.

$\mathrm{card} (\mathbb{N}) = \mathrm{card} (\mathbb{Q})$ .

Article détaillé : Ensemble dénombrable.

De même que $\mathbb{N}^k$ s'injecte dans $\mathbb{N}$ pour tout entier $k$ , $\mathbb{R}^k$ s'injecte dans $\mathbb{R}$ , par conséquent le cardinal de $\mathbb{R}^k$ est égal à $\mathfrak c$ , cardinal de $\mathbb R$ . Démonstration succincte : on montre que $[0,1] 2$ s'injecte dans $[0,1]$ (d'où le fait que $\mathbb{R}^2$ puis $\mathbb{R}^k$ par récurrence s'injecte dans $\mathbb{R}$ , l'existence d'une bijection provenant du théorème de Cantor-Bernstein). Pour cela, il suffit d'écrire tout élément de $[0,1]$ comme suite de $0$ et de $1$ (développement binaire). L'image d'un élément de $[0,1] 2$ est formé en intercalant successivement chaque chiffre du développement binaire du premier et second nombre. On vérifie facilement que c'est une application injective (en prenant garde toutefois aux problèmes de non unicité du développement binaire). En utilisant un raisonnement similaire, on montre que l'ensemble des suites de réels est de cardinal $\mathfrak c$ .
Le cardinal de l'ensemble des fonctions continues de $\mathbb R$ dans $\mathbb R$ est égal à $\mathfrak c$ , cardinal de $\mathbb R$ . Ceci découle de la proposition précédente, car l'ensemble des fonctions réelles continues a au plus la puissance de $\mathbb{R}^\mathbb{Q}$ (et au moins celle du continu).
Le cardinal de l'ensemble des fonctions de $\mathbb R$ dans $\mathbb R$ est $2^{\mathfrak c} > \mathfrak c$ .

[modifier] Propriétés

Un ensemble A est infini si et seulement si $\mathrm{card}(A) = \mathrm{card}(A \cup \{A\})$ .
Si $A$ est infini et si $\mathfrak F(A)$ désigne l'ensemble des parties finies de $A$ , alors $\mathrm{card}(A) = \mathrm{card}(\mathfrak F(A))$ .
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 avec $card(B) < card(A)$ , alors $\ \mathrm{card}(A-B)=\mathrm{card}(A)$ .
Si $A$ est infini, alors $\mathrm{card}(A \times A) = \mathrm{card}(A)$
Si $A$ est infini et si $2 \le \mathrm{card}(B) \le \mathrm{card}(A)$ , alors $\ \mathrm{card}(B^A) = 2^{\mathrm{card}(A)}$ où $B A$ désigne l'ensemble des fonctions de $A$ dans $B$ .-->

[modifier] Cardinal inaccessible

L'accessibilité est la possibilité d'atteindre un ordinal ou un cardinal donné à partir des ordinaux plus petits.
Un ordinal $α$ est dit 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 :

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

Par exemple, $\aleph_0$ n'est cofinal avec aucun ordinal strictement 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. Le cardinal $\aleph_0$ est dit alors régulier, c'est le cas de tous les cardinaux successeurs.

Par contre, le cardinal $\aleph_{\omega}$ est cofinal avec $ω$ au moyen de l'application $f : n \in \omega \mapsto \aleph_n$ .
Ce cardinal $\aleph_{\omega}$ est dit alors singulier.

En notant $cf(α)$ le plus petit ordinal pour lequel $α$ est cofinal, on obtient $\mathrm{cf}(\omega) = \mathrm{cf}(\aleph_{\omega}) = \omega$ .

Les cardinaux se classent alors comme suit :

ceux de la forme $\aleph_{\alpha+1}$ , indicé par un ordinal $α + 1$ successeur d'un ordinal $α$ ;
ceux de la forme $\aleph_\alpha$ , indicés par un ordinal $α$ limite et qui sont singuliers ;
ceux de la forme $\aleph_\alpha$ , indicés par un ordinal $α$ limite et qui sont réguliers.

Ce dernier type de cardinal est qualifié de faiblement inaccessibles car ils ne peuvent être conçus à partir de cardinaux plus petits. On distingue parmi eux 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 ZFC.
Les deux premiers types de cardinaux sont qualifiés au contraire d'accessibles, car concevables à partir de cardinaux plus petits qu'eux.

[modifier] Hypothèse du continu

L'inégalité $\mathrm{card} (\mathbb{N}) = \aleph_0 < \mathrm{card} (\mathbb{R}) = 2^{\aleph_0}$ montrée ci-dessus permet d'écrire $\aleph_1 \le 2^{\aleph_0}$ puisque $\aleph_1$ est le plus petit cardinal strictement supérieur à $\aleph_0$ .

L'hypothèse du continu affirme l'égalité $\aleph_1 = 2^{\aleph_0}$ . On montre que cette propriété est indécidable dans ZFC. Par extension, l'hypothèse généralisée du continu énonce que, pour tout ordinal $α$ , on a $\aleph_{\alpha+1} = 2^{\aleph_{\alpha}}$ .

Les résultats suivants s'obtiennent en admettant comme axiome l'hypothèse généralisée du continu.

L'axiome du choix est démontrable.
Il y a équivalence entre les notions de cardinaux faiblement inaccessibles et fortement inaccessibles.
En notant l'ensemble des fonctions de dans , il vient
- $\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}$ .

[modifier] Voir aussi

Notion de nombre
Ensembles usuels		Extensions
ℕ ensemble des entiers naturels ℤ groupe des entiers relatifs D ensemble des décimaux ℚ corps des rationnels ℝ corps des réels ℂ corps des complexes		ℍ algèbre des quaternions O algèbre des octonions S algèbre des sédénions autres hypercomplexes ℚ_p corps des p-adiques hyperréels et superréels ordinaux et cardinaux surréels et pseudoréels
$\scriptstyle\mathbb{N}\ \sub\ \mathbb{Z}\ \sub\ \mathbb{D}\ \sub\ \mathbb{Q}\ \sub\ \mathbb{R}\ \sub\ \mathbb{C}$
Propriétés particulières
pair ou impair • premier ou composé • carré • parfait positif ou négatif • dyadique • irrationnel algébrique ou transcendant • imaginaire pur nombre de Liouville • normal • univers constructible • calculable • transfini • infiniment petit
Exemples d'importance historique
π : $\sqrt 2$ : φ : 0 : $i$ : e : ℵ₀ :	constante d'Archimède racine carrée de deux nombre d'or zéro unité imaginaire constante de Neper aleph-zéro	(≈ 3,141592654…) (≈ 1,414213562…) (≈ 1,618033989…) de carré valant −1 (≈ 2,718281828…) premier cardinal infini
autres constantes mathématiques
Notions connexes
chiffre • numération • fraction • opération • calcul • algèbre arithmétique • suite d'entiers • ∞ infini • chiffre significatif