Ensemble fini

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

En mathématiques, un ensemble E est dit fini si et seulement s'il existe un entier n et une bijection de E sur l'ensemble des entiers naturels strictement plus petits que n, en particulier, si n = 0, E est l'ensemble vide qui est donc bien fini. On montre l'unicité d'un tel entier n, et on appelle celui-ci nombre d'éléments de E, ou cardinal de E, en particulier l'ensemble vide a pour cardinal 0. La notation pour le cardinal varie suivant les ouvrages, on trouve n = card(E), n = #E, n = |E|, ou encore E (notation originelle de Cantor).

Cette définition fait référence aux entiers, mais certains mathématiciens ou logiciens ont souhaité fonder les mathématiques sur la notion d'ensemble qui leur semblait plus primitive. Des définitions d'ensemble fini ont été proposées, qui ne faisaient pas référence aux entiers. La plus célèbre est probablement celle de Dedekind, elle caractérise les ensembles finis par le principe des tiroirs : un ensemble est fini au sens de Dedekind si et seulement s'il ne peut pas être mis en bijection avec l'une de ses parties propres. Mais pour montrer qu'un ensemble fini au sens de Dedekind est fini au sens usuel, il faut l'axiome du choix. D'autres caractérisations d'ensemble fini ont été données, comme celle d'Alfred Tarski, dont l'équivalence avec la définition usuelle n'utilise pas l'axiome du choix.

Sommaire

1 Définitions et propriétés élémentaires
- 1.1 ensemble fini d'un cardinal donné
- 1.2 Premières propriétés
2 Clôture sous les opérations usuelles
3 Autres caractérisations des ensembles finis
- 3.1 Tarski
- 3.2 Dedekind
4 Notes et références

[modifier] Définitions et propriétés élémentaires

[modifier] ensemble fini d'un cardinal donné

On précise un peu la définition. Soit n un entier naturel, alors E est un ensemble fini de cardinal n, quand E est en bijection avec les n premiers entiers naturels, soit {x ∈ N | x < n} = {0, … , n -1}, ou de façon équivalente à {1, … , n} (avec la convention que cet ensemble est vide si n = 0). On dit que E est équipotent à ces deux ensembles.

Cette notion de cardinal est évidemment stable par équipotence : un ensemble en bijection avec un ensemble fini de cardinal n est lui même fini de cardinal n, la composée de deux bijections étant une bijection.

Par définition, un ensemble E est alors fini s'il existe un entier naturel n tel que E soit fini de cardinal n. Un ensemble qui n'est pas fini, est dit infini. On va voir que la classe des ensembles finis est stable par les opérations usuelles de la théorie des ensembles : on ne peut introduire d'ensemble infini par ces opérations, sauf à utiliser un ensemble dont on sait déjà qu'il est infini.

Mais tout d'abord il est nécessaire de montrer les propriétés les plus évidentes des ensembles finis et de leurs cardinaux, à commencer par l'unicité du cardinal, c'est-à-dire, pour un ensemble E fini, l'unicité de l'entier n tel que E est en bijection avec {x ∈ N | x < n}, qui permet de parler du cardinal d'un ensemble fini E. Les démonstrations de ces propriétés n'ont pas tant pour but de convaincre que celles-ci sont justes^[1], que de ce que la formalisation choisie pour la notion d'ensemble fini est correcte.

L'objet du paragraphe suivant est donc de montrer certaines de ces propriétés, à commencer par l'unicité du cardinal. La défiition d'ensemble fini choisie présuppose l'existence des entiers, et on utilisera dans la suite quelques propriétés arithmétiques élémentaires, à commencer par celles de la relation d'ordre usuelle.

[modifier] Premières propriétés

Le premier objectif est de montrer l'unicité du cardinal. Pour cela on énonce le lemme suivant dont l'énoncé peut sembler un peu contourné car il ne présuppose pas l'unicité du cardinal de l'ensemble E. On va noter dans ce paragraphe et les suivants N_n = {0, … , n-1}.

Lemme. — S'il existe une injection d'un ensemble E dans N_n = {0, … , n-1}, alors E est fini, de plus si cet ensemble E est de cardinal p, alors p ≤ n.

On procède par récurrence sur n. Si n = 0, N_n est vide et E forcément vide aussi (le graphe de l'injection est vide).

On suppose le résultat pour N_n. Soit E un ensemble et i une injection de E dans N_{n +1} . Le résultat est évident par hypothèse de récurrence si n n'est pas atteint par l'injection. S'il l'est, soit a son antécédant par i. La restriction de i à E - {a} est une injection de cet ensemble dans N_n, donc, par hypothèse de récurrence, E - {a} est fini, et donc E est fini (compléter la bijection). Supposons que E soit de cardinal p, c'est-à-dire qu'il y a une bijection j de N_p dans E. Si l'image de p -1 par j est a le résultat suit par hypothèse de récurrence (j définit par restriction à N_{p -1} une injection de cet ensemble dans E - {a} qui s'injecte dans N_n, donc par hypothèse de récurrence p -1 ≤ n -1). Sinon on se ramène à ce cas en composant j avec la transposition qui échange a et l'image de p -1 et laisse tous les autres points de E fixes.

On en déduit immédiatement l'unicité du cardinal. en effet si un ensemble E est de cardinal n et p, alors il existe par composition une bijection entre N_n et N_p, et donc d'après le lemme N_n et n ≤ p.

Proposition. — Si E est un ensemble fini, alors il existe un unique entier naturel n tel que E soit de cardinal n.

Cet entier est appelé le cardinal de E, (ou son nombre d'éléments), et on le note dans la suite de cet article Card E (d'autres notations existent voir le résumé introductif).

On peut maintenant réénoncer le lemme de façon plus directe.

Proposition. — S'il existe une injection d'un ensemble E dans un ensemble fini de cardinal n, alors E est fini de cardinal p ≤ n. En particulier un sous-ensemble fini d’un ensemble fini est fini de cardinal inférieur ou égal à celui de l'ensemble qui le contient.

Il peut être vu aussi comme une formulation du principe des tiroirs de Dirichlet, dont l'énoncé usuel est plutôt l'énoncé contraposé :

Il n'existe pas d'injection d'un ensemble fini de cardinal p éléments dans un ensemble fini de cardinal n si p > n,

dit autrement,

toute application d'un ensemble de cardinal p dans un ensemble de cardinal n est telle qu'un élément de l'ensemble d'arrivée a au moins deux antécédents si p > n.

Article détaillé : principe des tiroirs.

[modifier] Clôture sous les opérations usuelles

[modifier] Intersection

Si $\quad E$ est fini, quel que soit $\quad F$ fini ou infini, $\quad E \cap F$ est fini.

On sait que $E \cap F \subset E$ donc d'après ce qui précède cette intersection est finie.

[modifier] Union

Si $\quad E$ et $\quad F$ sont finis, de même $E \cup F :$

(i) Cas où $E \cap F = \varnothing$ :

si $\quad E = \varnothing$ , $\varnothing \cup F = F$ , le théorème est vrai ; s'il est démontré pour $\operatorname{card} E = n$ , soit $\quad E_1$ de cardinal $\quad n+1$ ; si $\operatorname{card} F = b$ , on peut poser :

$E_1 = \big\{ x_1,x_2,......,x_{n+1} \big\}$ et $F = \big\{ y_1,y_2,......,y_b \big\}$

D'après l'hypothèse de récurrence il existe un entier $\quad p$ et une bijection $\quad f$ de $\big(E_1 - \big\{x_{n+1}\big\}\big) \cup F$ sur $\quad[1,p]$ ; il existe une application $\quad g$ de $E_1 \cup F$ sur $\quad [1,p+1]$ définie par :

$\forall z \in \big(E_1 - \big\{x_{n+1}\big\}\big) \cup F$ $\quad g(z) = f(z)$ ; et $g\big(x_{n+1}\big) = p+1$

C'est une bijection, donc $E_1 \cup F$ est fini.

(ii) Cas où $E \cap F \ne \; \varnothing$ : $E \cup F = E \cup (F-E)$ , $\quad F-E$ est fini, et $E \cap (F-E)=\varnothing$ : le cas précédent s'applique.

On démontre que $\operatorname{card} (E \cup F) = \operatorname{card} E + \operatorname{card} F - \operatorname{card} (E \cap F)$ .

[modifier] Transformation par une application

Si E est un ensemble fini, et f une fonction définie sur E, alors f(E) est fini et Card f(E) ≤ Card E.

Pour y élément de f(E) choisissons un x unique dans chaque sous-ensemble f^-1 ({y}) ; soit A la partie de E décrite par ces éléments x ; la restriction de f à A est une bijection, donc f(E) a même cardinal que A, ^[2] alors Card f(E) ≤ Card E.

[modifier] Ensemble des parties

Les sous-ensembles d'un ensemble fini $\quad E$ forment un ensemble fini $\mathcal P(E)$ .

C'est vrai pour l'ensemble vide, l'ensemble cherché est $\big\{ \varnothing \big\} = 1$ .

Si c'est vrai pour tout ensemble $\quad E$ à $\quad n$ éléments, soit $\quad E_1$ = $E \cup \big\{ e \big\}$ un ensemble à $\quad n+1$ éléments ; si $X \subset E_1$ :

-ou bien $X \subset E$ ;

-ou bien $X = Y \cup \big\{ e \big\}$ , où $\quad Y$ est un sous-ensemble de $\quad E$ .

Pour tout $Y_i \subset E$ il y a un et un seul $\quad X_i$ tel que $X_i = Y_i \cup \big\{ e \big\}$ , les $\quad X_i$ forment un ensemble $\quad B$ , qui d'après la section précédente est fini.

Finalement $\mathcal P(E) \cup B$ est fini, c'est $\mathcal P(E_1)$ .

La propriété, étant vraie pour l'ensemble vide, et étant vraie pour les ensembles de cardinal $\quad n+1$ dès qu'elle l'est pour les ensembles de cardinal $\quad n$ , est vraie pour tout ensemble fini.

On aura remarqué que $Card \quad \mathcal P(E)= Card \quad B$ et qu'en conséquence $Card \quad \mathcal P(E_1) = 2.Card \quad \mathcal P(E)$ ; d'où l'on déduit via un raisonnement par récurrence que $Card \quad \mathcal P(E) = 2^{Card \quad E}$ .

[modifier] Produit cartésien

Si E et F sont finis, de cardinaux respectifs a et b, ExF est fini de cardinal ab.

C'est vrai si F=Ø et Card F = 0; si c'est vrai pour F de cardinal b, soit F' = F U {e} de cardinal b+1 ; ExF' = (ExF) U (Ex{e}) ; ExF est fini de par l'hypothèse de récurrence, et Ex{e} est clairement équipotent à E donc fini ; alors ExF' est fini de cardinal ab + a = a.(b+1).

[modifier] Autres caractérisations des ensembles finis

[modifier] Tarski

Une définition équivalente, qui ne se référe pas à une définition préalable d'entiers, est la condition de Tarski : un ensemble E est fini si et seulement si toute famille non vide de parties de E admet un élément minimal pour l'inclusion.^[3]^,^[4]^,^[5]

[modifier] Dedekind

Un ensemble E est fini au sens de Dedekind 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 au sens ci-dessus implique E fini au sens de Dedekind, mais la réciproque nécessite l'axiome du choix.

[modifier] Notes et références

↑ Ainsi l'unicité du cardinal fini fait fortement penser à la conservation des quantités discrètes, préalable elle même à l'acquisition de cette notion suivant Piaget (voir construction du nombre chez l'enfant).
↑ Michel Queysanne, Algèbre, Armand Colin Paris 1964-1971 pp. 69-70
↑ Alfred Tarski Sur les ensembles finis 1924 Fund. Math. t.6 p.45, p.95
↑ Patrick Suppes Axiomatic set theory Van Nostrand 265 p.
↑ Roland Fraïssé Logique mathématique, t.1 Gauthier-Villars Paris 1971, p. 12-13-14