Ensemble fini

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

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.

On note alors le nombre d'éléments de E, ou la cardinalité de E :

Card(E) = n

#E = n

|E| = n

Par convention, l'ensemble vide a pour cardinal 0.

E est fini au sens de Dedekind s’il n'est pas infini, c'est-à-dire si et seulement s'il ne peut pas être mis en bijection avec l'une de ses parties strictes (ou encore : toute injection de E dans lui-même est surjective). E fini implique E fini au sens de Dedekind, mais la réciproque nécessite l'axiome du choix.

[modifier] Caractérisation

Nous noterons $| [a; b] |$ l'ensemble $[a ; b] \cap \mathbb{Z}$ .

Si F est en bijection avec E, un ensemble fini non vide, alors F est non vide, et card(E) = card(F).

En effet, E est fini, donc en notant

n

son cardinal, il existe $f : |[ 1 ; n ]| \rightarrow E$ une bijection, et par hypothèse, il existe $g : E \rightarrow F$ .

La composée de bijections est une bijection, donc $g \circ f : \rightarrow F$ est bijective.

Donc F est fini car en bijection avec les n premiers entiers naturels, et card(F) = n.

[modifier] Parties

Soit $n \in \mathbb{N*}$ , E un ensemble fini de cardinal n, a un élément de E (qui existe car E non vide). $E \backslash \{a\}$ est fini de cardinal n - 1.

n = 1

, alors

E = {a}

, donc $E \backslash \{a\} = \varnothing$ qui est fini, et $Card( \varnothing ) = 0 = 1-1$ .

Si $n \ge 2$ , alors il existe $h : |[1 ; n ]| \rightarrow E$ une bijection.

h (n) = a

, alors $\tilde h : |[1 ; n-1 ]| \rightarrow E \backslash \{a\}$ est encore bijective, donc $E \backslash \{a\}$ est fini de cardinal

n - 1

Si $h(n) \ne a$ , alors par bijectivité de h, il existe un unique

l

tel que $h(l) = a \,$ .

On considère $\begin{matrix} \sigma : & |[1 ; n]| \rightarrow |[1 ; n ]| & \ \\ \ & \sigma(k) = k & \forall k \in |[1 ; n ]| \backslash \{l ; n \} \\ \ & \sigma(l) = n & \ \\ \ & \sigma(n) = l & \ \end{matrix}$

$\sigma \circ \sigma = \operatorname{id}_{|[1 ; n ]|}$ , donc

σ

est bijective.

$h \circ \sigma : |[1 ; n]| \rightarrow E$ est bijective comme composée, et $h \circ \sigma (n) = a$ . On s'est ramené au cas précédent, et $E \backslash \{a\}$ est fini de cardinal

n - 1

Toute partie d'un ensemble fini est finie.

La démonstration se fait par récurrence avec ce qui précède.

[modifier] Opérations

La réunion d'ensembles finis est finie. Plus précisément, si A et B sont deux ensembles finis, alors $A \cup B$ et $A \cap B$ sont finis, et $\operatorname{card} (A \cup B) = \operatorname{card} A + \operatorname{card} B - \operatorname{card} (A \cap B)$ .