Ensemble fini - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
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 (En mathématiques, l'ensemble vide est l'ensemble ne contenant aucun élément.) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection...) vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) 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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...) fait référence aux entiers, mais certains mathématiciens et logiciens ont souhaité fonder les mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide...) sur la notion d'ensemble qui leur semblait plus primitive. Des définitions d'ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement s'il existe un entier n et une...) 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 (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but...) de Dedekind si et seulement s'il ne peut pas être mis en bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y...) 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 (Un axiome (du grec ancien αξιωμα/axioma,...) du choix.

Les développements de la théorie des ensembles (La théorie des ensembles est une branche des mathématiques, créée par le...), 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 (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent...) 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 (En mathématiques, un entier naturel est un nombre positif (ou nul) permettant fondamentalement...), alors E est un ensemble fini de cardinal n, quand E est en bijection avec les n premiers entiers naturels, soit {xN | 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 (Le mot « infini » (-e, -s ; du latin finitus,...). On va voir que la classe des ensembles finis est stable par les opérations usuelles de la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer,...) des ensembles : on ne peut introduire d'ensemble infini (En mathématiques, un ensemble est infini s'il n'est pas fini, c'est-à-dire s'il contient un...) par ces opérations, sauf à utiliser un ensemble dont on sait déjà qu'il est infini.

Mais tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) 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 {xN | x < n}, qui permet de parler du cardinal d'un ensemble fini E.

L'objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans...) 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 pn.

On procède par récurrence sur n. Si n = 0, Nn est vide et E forcément vide aussi (le graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) 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 pn + 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 pn et np.

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 pn. 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 (La formulation est une activité industrielle consistant à fabriquer des produits...) du principe des tiroirs (Le principe des tiroirs déclare que si n chaussettes occupent m tiroirs, et si n > m, alors au...) 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.

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 (La réciproque est une relation d'implication.) à 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 :

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.
Page générée en 0.044 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique