Ensemble fini - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
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 n = E (notation originelle de Georg Cantor).
Cette définition fait référence aux entiers, mais certains mathématiciens et 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 le caractère fini d'ensemble par la négation du fait d'être infini : 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. Cette façon de procéder sera vivement contestée. De plus, pour montrer qu'un ensemble fini au sens de Dedekind est fini au sens usuel, il faut l'axiome du choix.
Les développements de la théorie des ensembles, après sa première axiomatisation par Ernst Zermelo, ont permis ensuite de montrer qu'il était possible de définir les entiers dans celle-ci, et donc la définition donnée en termes d'entier peut se voir finalement comme une définition purement ensembliste. Par ailleurs 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.
Cardinal d'un ensemble fini
Définition du cardinal
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} (N désigne l'ensemble des entiers naturels), ou encore quand E est en bijection avec les n premiers entiers naturels non nuls {1, … , n}. On dit que E est équipotent à chacun de 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.
L'objet du paragraphe suivant est donc de montrer certaines de ces propriétés, à commencer par l'unicité du cardinal. La définition d'ensemble fini choisie présuppose l'existence (ou la définition ensembliste) des entiers, et on utilisera dans la suite, en plus des propriétés fondamentales comme la récurrence, quelques propriétés arithmétiques élémentaires, à commencer par celles de la relation d'ordre usuelle.
Comparaison des cardinaux et unicité
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 Nn = {0, … , n-1}.
Lemme. — S'il existe une injection d'un ensemble E dans Nn = {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, Nn est vide et E forcément vide aussi (le graphe de l'injection est vide).
On suppose le résultat pour Nn. Soit E un ensemble et i une injection de E dans Nn + 1. Le résultat est évident par hypothèse de récurrence si n, le plus grand élément de Nn + 1, n'est pas atteint par l'injection. On suppose donc dans ce qui suit qu'il l'est, et on nomme a l'antécédent de n par i. La restriction de i à E - {a} est une injection de cet ensemble dans Nn, donc, par hypothèse de récurrence, E - {a} est fini, c'est-à-dire en bijection avec un certain Nq, et donc en complétant la bijection en associant q à a, E est fini. Supposons maintenant que E soit de cardinal p, c'est-à-dire qu'il y a une bijection j de Np dans E. On doit montrer que p ≤ n + 1. Si l'image par j du plus grand élément p -1 de Np est a, le résultat suit par hypothèse de récurrence : j définit par restriction à Np -1 une injection de cet ensemble dans E - {a} qui, par choix de a, s'injecte dans Nn, donc par hypothèse de récurrence p - 1 ≤ n. 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 Nn et Np, et donc d'après le lemme p ≤ 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é :
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.
Cardinal de l'image d'un ensemble fini
Une conséquence de la propriété précédente est que :
Proposition. — L'image d'un ensemble fini par une application est un ensemble fini de cardinal inférieur ou égal à celui de l'ensemble de départ.
En effet, on peut se restreindre sans perte de généralité au cas où l'ensemble image est l'ensemble d'arrivée, soit F, qui est donc l'image d'un ensemble fini par une application surjective ; F est alors l'image d'un certain Nn par une application f surjective par composition. On construit une réciproque à droite de f, en associant à tout élément de F son plus petit antécédent (ce sont des entiers). On a ainsi une injection de F dans Nn, d'où le résultat, d'après la proposition précédente.
On peut reformuler ce résultat ainsi :
