Enmathématiques, unensemble fini est unensemble qui possède un nombre fini d'éléments, c'est-à-dire qu'il est possible de compter ses éléments, le résultat étant un nombre entier. Unensemble infini est un ensemble qui n'est pas fini.
Ainsi l'ensemble deschiffres usuels (en base dix)
qui possède 10 éléments, est fini. De même l'ensemble des lettres de l'alphabet qui possède 26 éléments.
L'ensemble de tous les nombresentiers naturels
est, lui, infini : on peut toujours aller au-delà d'un nombre entier. De même, l'ensemble de tous les mots que l'on peut former avec les 26 lettres de l'alphabet, sans se préoccuper de leur signification, et sans restreindre leur longueur, est lui aussi infini.
Plus formellement, un ensemble est ditfini s'il existe un entier naturel et unebijection entre et l'ensemble des entiers naturels strictement plus petits que. Cet entier, qui est alors unique, est appelé lenombre d'éléments, oucardinal, de l'ensemble fini. Établir une telle bijection revient à étiqueter les éléments de avec les entiers de à ou, ce qui revient au même, avec les entiers de à.
Une propriété importante des ensembles finis est donnée par leprincipe des tiroirs deDirichlet : une fonction d'un ensemble fini dans un ensemble fini de cardinal strictement inférieur ne peut êtreinjective. Cette propriété est utile en particulier encombinatoire, qui plus généralement étudie les structures finies.
La définition d'ensemble fini fait référence aux entiers naturels, 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 ou d'ensemble infini ont été proposées, qui ne faisaient pas référence aux entiers. La première d'entre elles est celle deDedekind[1], qui s'appuie sur le principe des tiroirs : un ensemble est fini au sens de Dedekind s'il ne peut pas être mis en bijection avec l'une de sesparties propres. Mais les ensembles finis au sens de Dedekind ne sont finis au sens usuel que dans unethéorie des ensembles munie d'une forme faible de l'axiome du choix.
Les développements de la théorie des ensembles, après sa première axiomatisation parErnst Zermelo, ont permis ensuite de définir les entiers dans celle-ci, et donc la définition donnée en termes d'entiers 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.
Pour tout entier naturel, on va noter, dans ce paragraphe et les suivants, l'ensemble des premiers entiers naturels ( désigne l'ensemble des entiers naturels).On[2] dit que
est un ensemble fini de cardinal, quand estéquipotent à, c'est-à-dire enbijection avec cet ensemble.
En particulier, l'ensemble vide est l'unique ensemble fini de cardinal 0. Pour non nul, il est équivalent de dire que est équipotent à l'ensemble des premiers entiers naturels non nuls.
On dit aussi de que c'est le nombre des éléments de, ou (enstatistique, endémographie, etc.) soneffectif, ou encore, encombinatoire et en informatique, sataille.
Cette notion est stable par équipotence : un ensemble en bijection avec un ensemble fini de cardinal est lui-même fini de cardinal, la composée de deux bijections étant une bijection.
On dit alors que
est un ensemble fini quand il existe un entier naturel tel que soit fini de cardinal.
Un ensemble qui n'est pas fini est ditinfini. On va voir que la classe des ensembles finis est stable par les opérations usuelles de lathé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 il est plus commode de montrer d'abord les propriétés les plus évidentes des ensembles finis et de leurs cardinaux, en particulier l'unicité du cardinal c'est-à-dire, pour un ensemble fini, l'unicité de l'entiern tel que est équipotent à. Cette unicité, qui permet de parlerducardinal d'un ensemble fini, est l'objet du paragraphe suivant.
La définition d'ensemble fini choisie présuppose l'existence (ou la définition ensembliste) des entiers, et l'on utilise dans la suite, en plus des propriétés fondamentales comme larécurrence, quelques propriétés arithmétiques élémentaires, à commencer par celles de larelation d'ordre usuelle.
Le premier objectif est de montrer l'unicité du cardinal d'un ensemble fini. Pour cela, on démontre le lemme suivant, dont l'énoncé ne présuppose pas cette unicité.
Lemme. —S'il existe uneinjection d'un ensemble fini de cardinal dans un ensemble fini de cardinal alors.
À bijection près, il s'agit simplement de démontrer que s'il existe une injection de dans alors. On peut le prouver par récurrence sur[3].
Ce lemme peut être vu comme une formulation duprincipe des tiroirs deDirichlet, dont l'énoncé usuel est plutôt lacontraposée :
On en déduit immédiatement l'unicité du cardinal. En effet, si un ensemble est à la fois de cardinal et alors, d'après le lemme, et.
Proposition. —Si est un ensemble fini, alors il existe un unique entier naturel tel que soit de cardinal.
Cet entier est appelé lecardinal de (ou sonnombre d'éléments), et on le note dans la suite de cet article (la notation pour le cardinal varie suivant les ouvrages, on trouve,,, ou même la notation originelle deGeorg Cantor).
Si est un ensemble fini de cardinal, alors toute partie de et touteimage de (par une application) est un ensemble fini, de cardinal inférieur ou égal à. Ou, ce qui est équivalent :
Proposition[3]. —Soient un ensemble fini et un ensemble quelconque. S'il existe une injection de dans ou unesurjection de dans, alors est fini et.
Une première remarque est que, comme tout sous-ensemble d'un ensemble fini est fini, on obtient directement la clôture par toute opération qui conduit à construire un sous-ensemble d'un des ensembles d'origine, comme l'intersection, ou la différence ensembliste.
Laréunion de deux ensembles finis et est finie, et
On en déduit par récurrence qu'une réunion finie d'ensembles finis est finie. La formule obtenue pour le cardinal de la réunion se généralise.
Si et sont finis, de cardinaux respectifs et, leurproduit cartésien est fini de cardinal[3].
On déduit de la propriété précédente[3] que l'ensemble desapplications d'un ensemble fini de cardinaln dans un ensemble fini de cardinalp, est un ensemble fini de cardinalpn.
L'ensemble des parties d'un ensemble fini de cardinal est un ensemble fini de cardinal.
C'est le cas particulier de la propriété précédente, via la bijection entre l'ensemble des parties de et l'ensemble des applications de dans qui associe à chaque partie de safonction caractéristique[3].
Si l'on reprend la définition d'ensemble fini enthéorie des ensembles d'un point de vue plus axiomatique, elle repose sur la définition qu'on y donne des entiers. Dans la théorie de Zermelo ou deZermelo-Fraenkel, l'ensemble des entiers naturels, noté ω, est le plus petit ensemble auquel appartient 0 et clos par successeur, où 0 est l'ensemble vide et le successeur d'un ensemblex est l'ensemble obtenu en lui ajoutantx comme élément : le successeur dex estx ∪ {x}. On montre que l'ensemble des entiers naturels est bien ordonné par l'appartenance (comme ordre strict), et donc ses éléments, qui sont aussi des sous-ensembles, le sont aussi. L'ordre large correspondant est l'inclusion ensembliste.
Une caractérisation plus directe, et qui ne nécessite pas l'axiome de l'infini, est de définir les entiers comme lesordinaux finis :
ou, ce qui est équivalent[5], quand toute partie non vide de cet ordinal admet un plus grand élément, autrement dit :
On appellera dans la suiteentiers de von Neumann les ordinaux finis. En présence de l'axiome de l'infini (déjà dans la théorie de Zermelo),ce sont les éléments de ω.
Tout ensemble fini, c'est-à-dire en bijection avec un entier de von Neumann, est muni, en transférant l'ordre par la bijection, d'un bon ordre dont l'opposé est un bon ordre. Réciproquement, tout ensemble muni d'un tel ordre est fini, car tout bon ordre estisomorphe à un ordinal. Par conséquent :
Tous lesordres totaux sur un ensemble fini étant isomorphes, on en déduit :
Alfred Tarski a donné en 1924[7] une définition des ensembles finis (reprise dans certains ouvrages plus récents[8],[9]) qui ne réfère pas à une définition préalable des entiers et qui s'avère équivalente à la précédente dans une théorie des ensembles sansaxiome du choix[10],[11] :
« Un ensemble E estfini au sens de Tarski quand toutefamille nonvide departies de E admet unélément minimal pour l'inclusion »
— Patrick Suppes (en), 1972p. 149[12]
, ou encore (par passage auxcomplémentaires) quand toute famille non vide de parties deE admet unélément maximal pour l'inclusion[7],[12].
Cette définition est équivalente à une caractérisation inductive des ensembles finis, donnée parRussell etWhitehead dans le volume II (1912) desPrincipia Mathematica[13],[14] :
On montre l'équivalence entre les trois définitions données d'ensemble fini : en bijection avec un entier de von Neumann, fini au sens de Tarski, fini au sens de Russell-Whitehead, et ceci dans une théorie des ensembles faible (la théorie de Zermelo sans l'axiome de l'infini), en particulier sans l'axiome du choix.
Montrons d'abord,par récurrence, que tout entier de von Neumannn — donc aussi tout ensemble en bijection avecn — est fini au sens de Tarski. L'entier 0 (l'ensemble vide) est évidemment fini au sens de Tarski. Supposons maintenant quen = m ∪ {m} avecm fini au sens de Tarski, et soitS une famille de parties den. NotonsS' la sous-famille constituée des parties dem qui appartiennent àS, etS" la famille des partiesE dem telles queE ∪ {m} appartient àS. SiS est non vide alorsS' ouS" est non vide. Dans le premier cas,S' admet un élément minimal, qui est aussi minimal dansS. Dans le second cas,S" admet un élément minimalE, etE ∪ {m} est un élément minimal deS.
Montrons maintenant que siE est fini au sens de Tarski, alorsE est fini au sens de Russell-Whitehead. SoitS une partie deE vérifiant les deux conditions de Russell-Whitehead. Comme ∅ ∈S,S est non vide ; elle a donc un élément maximalI. D'après la seconde condition de Russell-Whitehead,I =E, c'est-à-dire queE appartient àS.
Enfin, pour tout ensembleE, l'ensembleS des parties finies deE (ses partieséquipotentes à un entier de von Neumann) satisfait les deux conditions de Russell-Whitehead, donc siE est fini au sens de Russell-Whitehead alors il est équipotent à un entier de von Neumann.
Un ensembleE est ditfini au sens de Dedekind (en) s'il ne peut pas être mis enbijection avec l'une de sesparties propres (ou encore : touteinjection deE dans lui-même estsurjective).Dedekind est le premier à donner une définition des ensembles infinis, en 1888 dansWas sind und was sollen die Zahlen, et celle-ci revient à prendre leprincipe des tiroirs de Dirichlet comme caractérisation des ensembles finis[15].
SiE est fini (au sens utilisé précédemment, devenu le sens usuel), alorsE est fini au sens de Dedekind, mais la réciproque n'est pas démontrable dans lathéorie des ensembles de Zermelo-Fraenkel sansaxiome du choix[16]. L'axiome du choix dénombrable suffit pour démontrer l'équivalence entre la définition usuelle d'ensemble fini et celle de Dedekind, équivalence qui est cependant plus faible que l'axiome du choix dénombrable (il existe des modèles de la théorie de Zermelo-Fraenkel qui satisfont l'équivalence entre la définition de Dedekind et la définition usuelle mais pas l'axiome du choix dénombrable)[16].
On peut réinterpréter et étendre les propriétés de clôture de la classe des ensembles finis au regard des axiomes de lathéorie des ensembles. Pour obtenir des propriétés vraiment satisfaisantes, il faut considérer la classe des ensembleshéréditairement finis, c'est-à-dire les ensembles qui sont non seulement finis, mais dont les éléments sont aussi des ensembles finis et ainsi de suite.
En dehors de l'axiome d'extensionnalité et de l'axiome de fondation, les axiomes de la théorie des ensemblesZFC peuvent s'interpréter comme des propriétés d'existence d'ensembles, ou de clôture sous certaines constructions.
Les ensembles finis satisfont leschéma d'axiomes de compréhension, puisque tout sous-ensemble d'un ensemble fini est fini (en particulier l'ensemble vide), l'axiome de la paire, puisqu'une paire de deux ensembles quelconques est finie, l'axiome de l'ensemble des parties, comme vu ci-dessus, mais pas l'axiome de la réunion, puisqu'il n'y a pas de raison que les éléments d'un ensemble fini soient des ensembles finis. Si cette condition est satisfaite on a vu que l'axiome est réalisé.
L'image d'un ensemble fini par uneclasse fonctionnelle est un ensemble fini : c'est la version pour les ensembles finis duschéma d'axiomes de remplacement. Celui-ci a pour conséquence que la classe fonctionnelle en question est une fonction, et nous avons vu que l'image d'un ensemble fini par un ensemble fini est fini. cependant, dans le cas des ensembles finis, le schéma de remplacement n'ajoute rien. On peut démontrer directement, en utilisant l'axiome de la paire et de la réunion, que la classe fonctionnelle est finie, et donc le schéma de remplacement est superflu (il faut également le schéma de compréhension).
Étant donné un ensemble finiE = {A1… ,An} d'ensembles non vides, une fonction de choixf surE associe àAi un élémentai est une fonction de graphe fini. L'existence d'une fonction de choix pour un ensemble fini se démontre sans utiliser l'axiome du choix. La fonction se définit par récurrence, en utilisant à chaque étape que l'élément deE en jeu est un ensemble non vide. Il est juste besoin de supposer que l'ensemble sur lequel est défini la fonction de choix est fini.
En revanche, on ne peut se passer de l'axiome du choix pour obtenir une fonction de choix sur un ensemble infini même s'il est constitué seulement d'ensembles finis[17].
Les ensembles héréditairement finis sont des ensembles non seulement finis, mais dont les éléments sont eux-mêmes finis, et ainsi de suite. Plus formellement, dans la théorie des ensembles de Zermelo-Fraenkel, la classe des ensembles hériditairement finis est la plus petite classe contenant l'ensemble vide et close par passage à l'ensemble des parties. On montre que c'est un ensemble en utilisant l'axiome de l'infini et leschéma de remplacement. On la note Vω[18], c'est le niveau ω de lahiérarchie de von Neumann, plus précisément :
L'entier de von Neumannn appartient à Vn+1, les entiers de von Neumann sont donc héréditairement finis. L'ensemble Vω des héréditairement finis est lui-mêmedénombrable, au sens de la théorie, c'est-à-dire que l'on montre l'existence d'une bijection entre Vω et ω.
On montre que, dans un modèle de ZF, Vω muni de l'appartenance du modèle restreinte à Vω est un modèle de tous les axiomes de ZF excepté l'axiome de l'infini. Celui-ci n'est donc pas démontrable à partir des autres axiomes de ZF.
