Ensemble fini - Définition

Axiomatisation

Diverses caractérisations des ensembles finis

Les entiers et les bons ordres

Si on reprend la définition d'ensemble fini en thé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 de Zermelo-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 ensemble x est l'ensemble obtenu en lui ajoutant x comme élément : le successeur de x est x ∪ {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 les ordinaux finis, c'est-à-dire 0 et tous les ordinaux qui ont un prédécesseur ainsi que tous les ordinaux qui lui sont inférieurs. Dit autrement :

Un ordinal est fini quand tout ordinal non nul qui lui est inférieur ou égal a un prédécesseur.

On appellera dans la suite entier de von Neumann les ordinaux finis, c'est-à-dire, en présence de l'axiome de l'infini, les éléments de ω.

En effet un ordinal fini est bien élément de ω, car deux ordinaux sont toujours comparables, or un ordinal supérieur ou égal à ω ne peut être un ordinal fini, puisque ω n'a pas de prédécesseur. Il reste à montrer que les éléments de ω ont un prédécesseur, ce qui donne le résultat pour les éléments des éléments de ω , car ω est un ensemble transitif. Si n est un élément de ω non nul, il a pour élément 0. Si tous les éléments de n avaient un successeur, n serait un sur-ensemble de ω par définition de ce dernier, or l'appartenance définit un ordre strict sur ω (voir axiome de l'infini). Soit donc p un élément de n qui n'a pas de successeur dans n. Les éléments de p ∪ {p}, le successeur de p, sont tous des éléments de n, n ne peut donc être strictement inférieur au successeur de p. L'ordre sur les ordinaux étant total, n est donc le successeur de p.

Le prédécesseur d'un ordinal, quand il existe, est également le plus grand élément de cet ordinal en tant qu'ensemble ordonné. Tout ensemble en bijection avec un entier de von Neumann est bien ordonné, en transférant l'ordre par la bijection. L'entier de von Neumann est l'ordinal du bon ordre obtenu, c'est-à-dire le seul ordinal isomorphe à ce bon ordre. On peut également définir directement la notion de bon ordre fini :

Un ensemble bien ordonné est fini quand toutes ses parties non vides (y compris l'ensemble lui-même) ont un plus grand élément.

On passe en effet d'un bon ordre quelconque à son ordinal α par définition par récurrence. Si tout ordinal inférieur ou égal à α, qui est également un sous-ensemble de α, a un prédécesseur, celui-ci est par définition le plus grand parmi les éléments cet ordinal. Un sous-ensemble quelconque A de α a même élément maximal que l'ensemble β des ordinaux inférieurs ou égaux à au moins un élément de A, et on montre que β est un ordinal inférieur ou égal à α.

Il est donc équivalent (déjà dans la théorie de Zermelo) de définir un entier comme un élément de ω ou comme un ordinal fini tel que ci-dessus. On en déduit que l'on peut définir de façon équivalente un ensemble fini comme un ensemble qui peut être bien ordonné par un bon ordre fini, c'est-à-dire tel que tout sous-ensemble non vide a un plus grand élément, ce qui, comme un bon ordre est un ordre total, se dit également :

Un ensemble est fini si et seulement s'il existe un bon ordre sur celui-ci dont l'ordre inverse est aussi un bon ordre.

Les définitions de Tarski et de Russell-Whitehead

Alfred Tarski a donné en 1924 une définition des ensembles finis (reprise dans certains ouvrages plus récents) qui ne réfère pas à une définition préalable des entiers et qui s'avère équivalente aux précédentes dans une théorie des ensembles sans axiome du choix et qui est  :

un ensemble E est fini (au sens de Tarski) si et seulement si toute famille non vide de parties de E admet un élément minimal pour l'inclusion.

Cette définition est étroitement associée à une caractérisation inductive des ensembles finis, donnée par Russell et Whitehead dans le volume II (1912) des Principia Mathematica :

Un ensemble E est fini (au sens de Russell et Whitehead) quand E appartient à toute famille S de parties de E qui vérifie les deux conditions :

• ∅ ∈ S (l'ensemble vide appartient à S) ;
• Si A ∈ S et x ∈ E, alors A ∪ {x} ∈ S (si A appartient à S, toute partie obtenue en ajoutant un élément de E à A appartient également à S).

Cette définition est également équivalente aux précédentes, toujours dans une théorie des ensembles sans axiome du choix.

On montre ces équivalences dans la suite, à savoir qu'un ensemble est fini selon la définition initiale (équipotent à un entier de von Neumann) si et seulement s'il est fini au sens de Tarski, ou encore si et seulement s'il est fini au sens de Russell-Whitehead.

Remarquons tout d'abord que l'image par une bijection d'un ensemble fini au sens de Tarski est un ensemble fini au sens de Tarski.

L'ensemble vide est évidemment fini au sens de Tarski. Par ailleurs si E est un ensemble fini au sens de Tarski, alors un ensemble obtenu en ajoutant à E un élément, soit E ∪ {x}, est encore fini au sens de Tarski. En effet si une famille S non vide de parties de E ∪ {x} contient au moins une partie de S, alors la famille S’ des parties de E qui appartiennent à S admet un élément minimal, pour l'inclusion, qui est aussi minimal dans S. Sinon la famille S’ des parties de E qui, complétées par {x}, appartiennent à S admet un élément minimal. En ajoutant x à celui-ci on obtient forcément un élément de S, minimal dans S.

On en déduit donc que tous les entiers de von Neumann, et donc tous les ensembles finis par passage à la bijection, sont finis au sens de Tarski.

Montrons maintenant que si E est fini au sens de Tarski, alors E est fini au sens de Russell-Whitehead. En effet Soit S une partie de E vérifiant les deux conditions de Russell-Whitehead. Soit T l'ensemble des parties de E dont le complémentaire est dans S :

T = {E − X | X ∈ S}.

Comme ∅ ∈ S, T est non vide, elle a donc un élément minimal, soit I. Comme le complémentaire inverse l'ordre de l'inclusion, le complémentaire de I, E − I, est alors maximal pour l'inclusion dans S. On en déduit que, d'après la seconde condition de Russell-Whitehead, E − I = E, c'est-à-dire que E appartient à S.

On termine en montrant que si E est fini au sens de Russell-Whitehead, alors E est fini (équipotent à un entier de von Neumann). En effet, on vérifie facilement que S l'ensemble des parties finies (en bijection avec un entier de von Neumann) de E, satisfait les deux conditions de Russell-Whitehead, et donc que E est en bijection avec un entier de von Neumann.

On a donc démontré 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 on n'a pas utilisé l'axiome du choix.

La définition de 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). On a montré en début d'article que si E est fini (au sens utilisé précédemment), alors E est fini au sens de Dedekind, mais la réciproque se démontre avec l'axiome du choix. Plus précisément, l'axiome du choix dénombrable est une condition suffisante (mais non nécessaire) pour que tout ensemble fini au sens de Dedekind soit fini. Par contre, dans une théorie sans axiome du choix, on montre que l'on ne peut exclure l'existence d'ensembles finis au sens de Dedekind qui ne sont pas finis au sens usuel.

Les propriétés de clôture du point de vue des axiomes de la théorie des ensembles

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 la théorie des ensembles. Pour obtenir des propriétés vraiment satisfaisantes, il faut considérer la classe des ensembles héréditairement finis, c'est-à-dire les ensembles qui sont non seulement finis, mais dont les éléments sont aussi des ensemble finis et ainsi de suite.

Les premiers axiomes

En dehors de l'axiome d'extensionnalité et de l'axiome de fondation, les axiomes de la théorie des ensembles ZFC peuvent s'interpréter comme des propriétés d'existence d'ensembles, ou de clôture sous certaines constructions.

Les ensembles finis satisfont le sché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é.

Le schéma de remplacement

L'image d'un ensemble fini par une classe fonctionnelle est un ensemble fini : c'est la version pour les ensembles finis du sché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).

L'axiome du choix

Étant donné un ensemble fini E = {A₁, … , A_n} d'ensembles non vides, une fonction de choix f sur E associe à A_i un élément a_i 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 de E 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.

Par contre 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

Les ensembles héréditairement finis

Théorie des ensembles héréditairement finis et arithmétique