Voir la source de Ensemble fini

{{Infobox | objet = [[Entier naturel]] <br /> [[Nombre cardinal]] | type = Objet mathématique <br /> ([[Ensemble]]) | partie de = [[Catégorie des ensembles]] <br /> [[Théorie des ensembles]] | image = Example of a set.svg | légende image = Représentation d'un ensemble fini d'[[Appartenance (mathématiques)|éléments]] <br /> dans un [[diagramme d'Euler]]. }}
En [[mathématiques]], un '''ensemble fini''' est un [[ensemble]] qui possède un nombre fini d'[[Appartenance (mathématiques)|éléments]], c'est-à-dire qu'il est possible de compter ses éléments, le résultat étant un nombre entier. Un [[ensemble infini]] est un ensemble qui n'est pas fini.

Ainsi l'ensemble des [[chiffre]]s usuels (en base dix)
:<math>\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}</math>
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 nombres [[entier naturel|entiers naturels]]
:<math>\{0, 1, 2, 3, \ldots, 10, \ldots, 100, \ldots\}</math>
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 <math>E</math> est dit ''fini'' s'il existe un entier naturel <math>n</math> et une [[bijection]] entre <math>E</math> et l'ensemble des entiers naturels strictement plus petits que <math>n</math>. Cet entier <math>n</math>, qui est alors unique, est appelé le ''nombre d'éléments'', ou [[Cardinalité (mathématiques)#Cardinal d'un ensemble fini|''cardinal'', de l'ensemble fini]] <math>E</math>. Établir une telle bijection revient à étiqueter les éléments de <math>E</math> avec les entiers de <math>0</math> à <math>n-1</math> ou, ce qui revient au même, avec les entiers de <math>1</math> à <math>n</math>.

Une propriété importante des ensembles finis est donnée par le [[principe des tiroirs]] de [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet]] : une fonction d'un ensemble fini dans un ensemble fini de cardinal strictement inférieur ne peut être [[Injection (mathématiques)|injective]]. Cette propriété est utile en particulier en [[combinatoire]], 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é [[fondements des mathématiques|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 de [[Richard Dedekind|Dedekind]]<ref>Exposée dans ''{{lang|de|Was sind und was sollen die Zahlen}}'', 1888.</ref>, 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 ses [[Inclusion (mathématiques)|parties]] propres. Mais les ensembles finis au sens de Dedekind ne sont finis au sens usuel que dans une [[thé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 par [[Ernst 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.

== Cardinal d'un ensemble fini ==
=== Définitions ===
Pour tout entier naturel <math>n</math>, on va noter, dans ce paragraphe et les suivants, <math>N_n=\{x\in \mathbb N\mid x<n\}=\{0, \ldots, n-1\}</math> l'ensemble des ''n'' premiers entiers naturels (<math>\mathbb N</math> désigne l'ensemble des entiers naturels).
On dit que
{{énoncé|''E est un ensemble fini de cardinal n'', quand ''E'' est [[équipotence|équipotent]] à N{{ind|''n''}}, c'est-à-dire en [[bijection]] avec cet ensemble.}} En particulier, l'[[ensemble vide]] est l'unique ensemble fini de cardinal 0. Pour ''n'' non nul, il est équivalent de dire que ''E'' est équipotent à l'ensemble {1, … , ''n''} des ''n'' premiers entiers naturels non nuls.
On dit aussi de ''n'' que c'est le nombre des éléments de ''E'', ou (en [[statistique]], en [[démographie]]{{etc.}}) son ''effectif''.

Cette notion est 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.

On dit alors que
{{énoncé|''E est un ensemble fini'' quand il existe un entier naturel ''n'' tel que ''E'' soit fini de cardinal ''n''.}}
Un ensemble qui n'est pas fini est dit [[ensemble infini|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 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 ''E'' fini, l'unicité de l'entier ''n'' tel que ''E'' est équipotent à N{{ind|''n''}}. Cette unicité, qui permet de parler ''du'' [[Cardinalité (mathématiques)#Cardinal d'un ensemble fini|cardinal d'un ensemble fini]] ''E'', 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 la [[raisonnement par récurrence|récurrence]], quelques propriétés arithmétiques élémentaires, à commencer par celles de la [[relation d'ordre]] usuelle.

{{Ancre|Comparaison des cardinaux et unicité}}

=== Unicité du cardinal ===
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 une [[Injection (mathématiques)|injection]] d'un ensemble fini de cardinal <math>p</math> dans un ensemble fini de cardinal <math>n</math> alors <math>p\leqslant n</math>.

[[À quelque chose près|À bijection près]], il s'agit simplement de démontrer que s'il existe une injection de <math>N_p</math> dans <math>N_n</math> alors <math>p\leqslant n</math>. On peut le prouver par récurrence sur ''n''<ref name=Wikiversité>{{Note autre projet|Wikiversité|Introduction aux mathématiques/Rudiments de combinatoire#Ensembles finis|« Rudiments de combinatoire »|début=Voir par exemple le chapitre}}</ref>.

Ce lemme peut être vu comme une formulation du [[principe des tiroirs]] de [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet]], dont l'énoncé usuel est plutôt la [[contraposée]] :
<center>Une application d'un ensemble de cardinal ''p'' dans un ensemble de cardinal ''n'' < ''p'' ne peut pas être injective.
</center>

On en déduit immédiatement l'unicité du cardinal. En effet, si un ensemble est à la fois de cardinal ''n'' et ''p'' alors, 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'' (la notation pour le cardinal varie suivant les ouvrages, on trouve ''n'' = card(''E''), ''n'' = '''#'''''E'', ''n'' = '''|'''''E'''''|''', ou même la notation originelle de [[Georg Cantor]] ''n'' = <span style="border-top: 4px double;">''E''</span>).

=== Comparaison des cardinaux ===
Si ''E'' est un ensemble fini de cardinal ''n'', alors toute partie de ''E'' et toute [[Image d'une application|image]] de ''E'' (par une application) est un ensemble fini, de cardinal inférieur ou égal à ''n''. Ou, ce qui est équivalent :

{{Ancre|Cardinal de l'image d'un ensemble fini}}
'''Proposition<ref name=Wikiversité/>. —''' ''Soient E un ensemble fini et F un ensemble quelconque. S'il existe une injection de F dans E ou une [[surjection]] de E dans F, alors F est fini et'' card ''F'' ≤ card ''E''.

== Clôture sous les opérations usuelles ==

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 (mathématiques)|intersection]], ou la différence ensembliste.

=== Union ===
La [[Union (mathématiques)|réunion]] de deux ensembles finis <math>E</math> et <math>F</math> est finie, et
:<math>\text{card}(E\cup F)=\text{card}\; E+\text{card}\;  F-\text{card}(E\cap F)</math>

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.
{{article détaillé|Principe d'inclusion-exclusion}}

=== Produit cartésien ===
Si <math>E</math> et <math>F</math> sont finis, de cardinaux respectifs <math>n</math> et <math>p</math>, leur [[produit cartésien]] <math>E\times F</math> est fini de cardinal <math>np</math><ref name=Wikiversité/>.

=== Ensemble des applications d'un ensemble fini dans un ensemble fini ===
On déduit de la propriété précédente<ref name=Wikiversité/> que l'ensemble des [[application (mathématiques)|applications]] d'un ensemble fini de cardinal ''n'' dans un ensemble fini de cardinal ''p'', est un ensemble fini de cardinal ''p{{exp|n}}''.

=== Ensemble des parties ===

L'[[ensemble des parties d'un ensemble|ensemble des parties]] ''P''(''E'') d'un ensemble fini ''E'' de cardinal ''n'' est un ensemble fini de cardinal 2<sup>''n''</sup>.

C'est le cas particulier ''p'' = 2 de la propriété précédente, via la bijection entre l'ensemble des parties de ''E'' et l'ensemble des applications de ''E'' dans {0, 1} qui associe à chaque partie de ''E'' sa [[Fonction caractéristique (théorie des ensembles)|fonction caractéristique]]<ref name=Wikiversité/>.

== Axiomatisation ==
=== Diverses caractérisations des ensembles finis ===
==== Les entiers et les bons ordres ====
Si l'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 [[Théorie des ensembles de Zermelo-Fraenkel|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 (mathématiques)|inclusion ensembliste]].
{{article détaillé|Axiome de l'infini}}
Une caractérisation plus directe, et qui ne nécessite pas l'axiome de l'infini, est de définir les entiers comme les [[Nombre ordinal#Propriétés|ordinaux finis]] :
:''Un ordinal est fini quand tout ordinal non nul qui lui est inférieur ou égal a un prédécesseur<ref>{{Krivine98}}.</ref>''
ou, ce qui est équivalent<ref>Voir [[Nombre ordinal#Propriétés]].</ref>, quand toute partie non vide de cet ordinal admet un plus grand élément, autrement dit :
:''Un ordinal est fini quand son [[ordre opposé]] est un [[bon ordre]].''
On appellera dans la suite ''entiers de von Neumann'' les ordinaux finis. En présence de l'axiome de l'infini (déjà dans la théorie de Zermelo), [[Axiome de l'infini#Ordre|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 est [[Isomorphisme d'ordres|isomorphe]] à un ordinal. Par conséquent :
:''Un ensemble est fini si et seulement s'il existe un bon ordre sur celui-ci dont l'ordre opposé est aussi un bon ordre''<ref>Définition donnée par [[Paul Stäckel]] en 1907, selon {{Harvsp|Tarski|1924|p=81}}.</ref>.

Tous les [[Ordre total|ordres totaux]] sur un ensemble fini étant isomorphes, on en déduit :
:''Un ensemble bien ordonné est fini si et seulement si l'ordre opposé est aussi un bon ordre''.

==== Les définitions de Tarski et de Russell-Whitehead ====
[[Alfred Tarski]] a donné en 1924<ref name="ref_auto_1">{{Harvsp|Tarski|1924}}.</ref> une définition des ensembles finis (reprise dans certains ouvrages plus récents<ref>{{Ouvrage|langue=en|auteur1={{Lien|Patrick Suppes}}|titre=Axiomatic Set Theory|éditeur=Van Nostrand|année=1972|année première édition=1960|page=100|pages=267|lire en ligne={{Google Livres|sxr4LrgJGeAC|page=100}}}}.</ref>{{,}}<ref>[[Roland Fraïssé]], ''Logique mathématique'', t.1, Gauthier-Villars, Paris, 1971, {{p.}}12-14.</ref>) 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 sans [[axiome du choix]]<ref name="Dedekind">{{chapitre | titre chapitre = Que sont et à quoi servent les nombres ? | titre ouvrage = La création des nombres | auteur1 = Richard Dedekind | auteur2 = Hourya Sinaceur | éditeur = Librairie Philosophique J. Vrin | année = 2008 | lire en ligne = https://books.google.fr/books?id=6Rs8pJawb_8C&pg=PA147&dq=ensemble+est+fini+au+sens+de+Tarski&hl=fr&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwjEtNOuyoaLAxX5AvsDHdvIE_EQ6AF6BAgFEAI#v=onepage&q=ensemble%20est%20fini%20au%20sens%20de%20Tarski&f=false}}.</ref>{{,}}<ref name="Sinaceur2">{{chapitre | numéro chapitre = 4 | titre chapitre = Logique et algèbre réelle | titre ouvrage = Corps et modèles: essai sur l'histoire de l'algèbre réelle | auteur = Hourya Sinaceur | éditeur = Librairie Philosophique J. Vrin | année = 1991 | lire en ligne = https://books.google.fr/books?id=905BD6REsQMC&pg=PA303 | passage = 303 à 375}}.</ref> : {{Citation bloc|Un ensemble E est '''fini au sens de Tarski''' quand toute [[Famille (mathématiques)|famille]] non [[Ensemble vide|vide]] de [[Sous-ensemble|parties]] de E admet un [[élément minimal]] pour l'[[Inclusion (mathématiques)|inclusion]]|{{Lien|Patrick Suppes}}, 1972 {{p.|149}}<ref name="Suppes5.2">{{chapitre | langue = en | numéro chapitre = 5.2 | titre chapitre = Finite ordinals and denumerable sets |auteur={{Lien|Patrick Suppes}}|titre ouvrage=Axiomatic Set Theory|éditeur=Van Nostrand|année=1972|année première édition=1960|page=100|pages=267|lire en ligne={{Google Livres|sxr4LrgJGeAC|page=149}}}}.</ref>}}, ou encore (par passage aux [[Complémentaire (théorie des ensembles)|complémentaires]]) quand toute famille non vide de parties de ''E'' admet un [[élément maximal]] pour l'inclusion<ref name="ref_auto_1" />{{,}}<ref name="Suppes5.2"/>.

Cette définition est équivalente à une caractérisation inductive des ensembles finis, donnée par [[Bertrand Russell|Russell]] et [[Alfred North Whitehead|Whitehead]] dans le volume II (1912) des ''[[Principia Mathematica]]''<ref>Selon {{Harvsp|Tarski|1924|p=56}}, Corollaire 15, Russell et Whitehead ne prennent pas cette caractérisation comme définition mais la donnent comme théorème, dans le cadre de la théorie des types.</ref>{{,}}<ref>Il en existe des variantes dues à [[Wacław Sierpiński]] en 1919 et [[Kazimierz Kuratowski]] en 1921, d'après {{Harvsp|Tarski|1924|p=56}}, et {{p.|47}} pour les références bibliographiques précises.</ref> :
:''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'' :
:* <math>\emptyset \in S </math> (''l'ensemble vide appartient à S'') ;
:* ''Si'' <math>A\in S</math> et <math>x\in E</math>, alors <math>A\cup \{x\}\in S</math> (''si A appartient à S, toute partie obtenue en ajoutant un élément de E à A appartient également à S'').

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.

{{Démonstration/début|titre=Preuve de l'équivalence entre les trois définitions}}
Montrons d'abord, [[Raisonnement par récurrence|par récurrence]], que tout entier de von Neumann ''n'' — donc aussi tout ensemble en bijection avec ''n'' — est fini au sens de Tarski. L'entier 0 (l'ensemble vide) est évidemment fini au sens de Tarski. Supposons maintenant que ''n''&nbsp;=&nbsp;''m''&nbsp;∪&nbsp;{''m''} avec ''m'' fini au sens de Tarski, et soit ''S'' une famille de parties de ''n''. Notons ''S{{'}}'' la sous-famille constituée des parties de ''m'' qui appartiennent à ''S'', et ''S"'' la famille des parties ''E'' de ''m'' telles que ''E'' ∪ {''m''} appartient à ''S''. Si ''S'' est non vide alors ''S{{'}}'' ou ''S"'' est non vide. Dans le premier cas, ''S{{'}}'' admet un élément minimal, qui est aussi minimal dans ''S''. Dans le second cas, ''S"'' admet un élément minimal ''E'', et ''E'' ∪ {''m''} est un élément minimal de ''S''.

Montrons maintenant que si ''E'' est fini au sens de Tarski, alors ''E'' est fini au sens de Russell-Whitehead. Soit ''S'' une partie de ''E'' vérifiant les deux conditions de Russell-Whitehead. Comme ∅ ∈ ''S'', ''S'' est non vide ; elle a donc un élément maximal ''I''. D'après la seconde condition de Russell-Whitehead, ''I'' = ''E'', c'est-à-dire que ''E'' appartient à ''S''.

Enfin, pour tout ensemble ''E'', l'ensemble ''S'' des parties finies de ''E'' (ses parties [[équipotence|équipotentes]] à un entier de von Neumann) satisfait les deux conditions de Russell-Whitehead, donc si ''E'' est fini au sens de Russell-Whitehead alors il est équipotent à un entier de von Neumann.
{{Démonstration/fin}}

==== La définition de Dedekind ====
Un ensemble ''E'' est dit {{Lien|langue=en|trad=Dedekind-infinite set|fr=Ensemble infini au sens de Dedekind|texte=fini au sens de Dedekind}} s'il ne peut pas être mis en [[bijection]] avec l'une de ses [[Inclusion (mathématiques)#Inclusion, sous-ensembles et sur-ensembles, sous-ensembles propres|parties propres]] (ou encore : toute [[Injection (mathématiques)|injection]] de ''E'' dans lui-même est [[surjection|surjective]]). [[Richard Dedekind|Dedekind]] est le premier à donner une définition des ensembles infinis, en 1888 dans ''Was sind und was sollen die Zahlen'', et celle-ci revient à prendre le [[principe des tiroirs]] de Dirichlet comme caractérisation des ensembles finis<ref>{{article|auteur=[[Akihiro Kanamori]]|titre=The Mathematical Inﬁnite as a Matter of Method|revue=Annals of the Japan Association for Philosophy of Science|volume=20|pages=1-13|année=2012|lang=en|url=http://math.bu.edu/people/aki/22.pdf}}, {{p.|3}}.</ref>.

Si ''E'' est fini (au sens utilisé précédemment, devenu le sens usuel), alors ''E'' est fini au sens de Dedekind, mais la réciproque n'est pas démontrable dans la [[théorie des ensembles de Zermelo-Fraenkel]] sans [[axiome du choix]]<ref name="Herrlich">Voir par exemple {{Ouvrage|langue=en|auteur1=[[Horst Herrlich]]|titre=Axiom of Choice|éditeur=Springer|lieu=Berlin|année=2006|pages totales=194|page=48|isbn=978-3-540-30989-5|lire en ligne={{Google Livres|JXIiGGmq4ZAC|page=48}}|numéro chapitre=4}}.</ref>. L'[[Axiome du choix#Axiome du choix dénombrable|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)<ref name="Herrlich"/>.

=== 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 ensembles 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 [[Théorie des ensembles de Zermelo-Fraenkel|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'[[axiome de l'ensemble vide|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 (mathématiques)|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''<sub>1</sub>… , ''A''<sub>n</sub>} d'ensembles non vides, une fonction de choix ''f'' sur ''E'' associe à ''A''<sub>''i''</sub> un élément ''a''<sub>''i''</sub> 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.

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<ref>Cette restriction donne cependant un axiome du choix faible, voir par exemple {{Harvsp|Herrlich|2006|loc=chap. 2, {{p.}}14-16}}.</ref>.

==== Les ensembles héréditairement finis ====
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 d'un ensemble|ensemble des parties]]. On montre que c'est un ensemble en utilisant l'[[axiome de l'infini]] et le [[schéma d'axiomes de remplacement|schéma de remplacement]]. On la note V<sub>ω</sub><ref>{{Harvsp|Krivine|texte=Krivine 2007|p=45-46}}.</ref>, c'est le niveau ω de la [[axiome de fondation|hiérarchie de von Neumann]], plus précisément :
* V<sub>0</sub> = Ø
* V<sub>''n''+1</sub> = ''P''(V<sub>''n''</sub>)
* V<sub>ω</sub> = {{Grossir|'''∪'''|facteur=1.3}}<sub>''n'' ∈ '''N'''</sub> ''V''<sub>n</sub> .
L'[[axiome de l'infini|entier de von Neumann]] ''n'' appartient à V<sub>''n''+1</sub>, les entiers de von Neumann sont donc héréditairement finis. L'ensemble V<sub>ω</sub> des héréditairement finis est lui-même [[Ensemble dénombrable|dénombrable]], au sens de la théorie, c'est-à-dire que l'on montre l'existence d'une bijection entre V<sub>ω</sub> et ω.

On montre que, dans un modèle de ZF, V<sub>ω</sub> muni de l'appartenance du modèle restreinte à V<sub>ω</sub> 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.

== Notes et références ==
=== Notes ===
{{Crédit d'auteurs|interne|Ensemble fini au sens de Tarski|218394005}}
=== Références ===
{{Références|taille=25}}

== Bibliographie ==
* {{Halmos65}}.
* {{Article|auteur=Alfred Tarski|année=1924|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm6/fm619.pdf|titre=Sur les ensembles finis|revue=[[Fundamenta Mathematicae|Fund. Math.]]|vol=6|p.=45-95}}.
* {{Cori-Lascar II}} chap. 7.

{{Portail|mathématiques}}

[[Catégorie:Théorie des ensembles]]