Equinumérosité - Equinumerosity
En mathématiques , deux ensembles ou des classes A et B sont equinumerous s'il existe une relation un-à-un de correspondance (ou bijection) entre eux, qui est, s'il existe une fonction de A à B de telle sorte que pour chaque élément y de B , il existe exactement un élément x de A avec f ( x ) = y . On dit que les ensembles équinumériques ont la même cardinalité (nombre d'éléments). L'étude de la cardinalité est souvent appelée équinumérosité ( égalité-de-nombre ). Les termes équipollence ( equalness-de-force ) et équipotence ( equalness-de puissance ) sont parfois utilisés à la place.
L'équinumérosité a les propriétés caractéristiques d'une relation d'équivalence . L'affirmation selon laquelle deux ensembles A et B sont équinumériques est généralement notée
- ou , ou
La définition de l'équinumérosité à l'aide de bijections peut être appliquée à la fois aux ensembles finis et infinis , et permet d'affirmer si deux ensembles ont la même taille même s'ils sont infinis. Georg Cantor , l'inventeur de la théorie des ensembles , a montré en 1874 qu'il existe plus d'un type d'infini, en particulier que la collection de tous les nombres naturels et la collection de tous les nombres réels , bien qu'infinis, ne sont pas équinumériques (voir la première indénombrable de Cantor preuve ). Dans son article controversé de 1878, Cantor définissait explicitement la notion de « puissance » des ensembles et l'utilisait pour prouver que l'ensemble de tous les nombres naturels et l'ensemble de tous les nombres rationnels sont équinumériques (un exemple où un sous - ensemble propre d'un ensemble infini est équinumérique à l'ensemble original), et que le produit cartésien d'un nombre infini de copies des nombres réels est égal à une copie unique des nombres réels.
Le théorème de Cantor de 1891 implique qu'aucun ensemble n'est égal à son propre ensemble de puissance (l'ensemble de tous ses sous-ensembles). Cela permet de définir des ensembles infinis de plus en plus grands à partir d'un seul ensemble infini.
Si l'axiome du choix est vérifié, alors le nombre cardinal d'un ensemble peut être considéré comme le plus petit nombre ordinal de cette cardinalité (voir ordinal initial ). Sinon, il peut être considéré (par le truc de Scott ) comme l'ensemble des ensembles de rang minimal ayant cette cardinalité.
L'affirmation selon laquelle deux ensembles sont soit équinumériques, soit l'un a une plus petite cardinalité que l'autre équivaut à l' axiome du choix .
Cardinalité
Les ensembles équinumériques ont une correspondance un à un entre eux et sont dits avoir la même cardinalité . La cardinalité d'un ensemble X est une mesure du "nombre d'éléments de l'ensemble". L'équinumérosité a les propriétés caractéristiques d'une relation d'équivalence ( réflexivité , symétrie et transitivité ) :
- Réflexivité
- Étant donné un ensemble A , la fonction identité sur A est une bijection de A à lui-même, montrant que tout ensemble A est équinumérique à lui-même : A ~ A .
- Symétrie
- Pour toute bijection entre deux ensembles A et B , il existe une fonction inverse qui est une bijection entre B et A , impliquant que si un ensemble A est équinumérique à un ensemble B alors B est également équinumérique à A : A ~ B implique B ~ A .
- Transitivité
- Etant donné trois ensembles A , B et C avec deux bijections f : A → B et g : B → C , la composition g ∘ f de ces bijections est une bijection de A vers C , donc si A et B sont équinumériques et B et C sont équinumériques alors A et C sont équinumériques : A ~ B et B ~ C impliquent ensemble A ~ C .
Une tentative de définir la cardinalité d'un ensemble comme la classe d'équivalence de tous les ensembles equinumerous à elle est problématique dans la théorie des ensembles Zermelo-Fraenkel , la forme standard de la théorie des ensembles axiomatique , parce que la classe d'équivalence d'un ensemble non vide serait trop grand être un ensemble : ce serait une classe propre . Dans le cadre de la théorie des ensembles de Zermelo-Fraenkel, les relations sont par définition restreintes aux ensembles (une relation binaire sur un ensemble A est un sous - ensemble du produit cartésien A × A ), et il n'y a pas d' ensemble de tous les ensembles dans l' ensemble de Zermelo-Fraenkel théorie. Dans la théorie des ensembles de Zermelo-Fraenkel, au lieu de définir la cardinalité d'un ensemble comme la classe d'équivalence de tous les ensembles qui lui sont équinumériques, on essaie d'attribuer un ensemble représentatif à chaque classe d'équivalence ( assignation cardinale ). Dans certains autres systèmes de théorie des ensembles axiomatiques, par exemple dans la théorie des ensembles de Von Neumann-Bernays-Gödel et la théorie des ensembles de Morse-Kelley , les relations sont étendues aux classes .
Un ensemble A est dit avoir une cardinalité inférieure ou égale à la cardinalité d'un ensemble B , s'il existe une fonction un-à-un (une injection) de A dans B . Ceci est noté | A | | B |. Si A et B ne sont pas équinumériques, alors la cardinalité de A est dite strictement inférieure à la cardinalité de B . Ceci est noté | A | < | B |. Si l'axiome du choix est vérifié , alors la loi de la trichotomie est valable pour les nombres cardinaux , de sorte que deux ensembles sont soit équinumériques, soit l'un a une cardinalité strictement plus petite que l'autre. La loi de la trichotomie pour les nombres cardinaux implique également l' axiome du choix .
Le théorème de Schröder–Bernstein énonce que deux ensembles A et B pour lesquels il existe deux fonctions biunivoques f : A → B et g : B → A sont équinumériques : si | A | | B | et | B | | A |, puis | A | = | B |. Ce théorème ne repose pas sur l' axiome du choix .
théorème de Cantor
Le théorème de Cantor implique qu'aucun ensemble n'est égal à son ensemble de puissance (l'ensemble de tous ses sous-ensembles ). Cela vaut même pour les ensembles infinis . Plus précisément, l'ensemble de puissance d'un ensemble dénombrable infini est un ensemble indénombrable .
En supposant l'existence d'un ensemble infini N composé de tous les nombres naturels et en supposant l'existence de l'ensemble de puissance d'un ensemble donné permet la définition d'une séquence N , P ( N ), P ( P ( N )), P ( P ( P ( N ))), … d'ensembles infinis où chaque ensemble est l'ensemble de puissance de l'ensemble qui le précède. Par le théorème de Cantor, la cardinalité de chaque ensemble dans cette séquence dépasse strictement la cardinalité de l'ensemble qui le précède, conduisant à des ensembles infinis de plus en plus grands.
Le travail de Cantor a été durement critiqué par certains de ses contemporains, par exemple par Leopold Kronecker , qui a fortement adhéré à une philosophie finitiste des mathématiques et a rejeté l'idée que les nombres peuvent former une totalité réelle et achevée (une infinité réelle ). Cependant, les idées de Cantor ont été défendues par d'autres, par exemple par Richard Dedekind , et ont finalement été largement acceptées, fortement soutenues par David Hilbert . Voir Controverse sur la théorie de Cantor pour en savoir plus.
Dans le cadre de la théorie des ensembles de Zermelo-Fraenkel , l' axiome des ensembles de puissance garantit l'existence de l'ensemble de puissance d'un ensemble donné. De plus, l' axiome de l'infini garantit l'existence d'au moins un ensemble infini, à savoir un ensemble contenant les nombres naturels. Il existe d' autres théories des ensembles , par exemple la " théorie générale des ensembles " (GST), la théorie des ensembles de Kripke-Platek et la théorie des ensembles de poche (PST), qui omettent délibérément l'axiome de l'ensemble de puissance et l'axiome de l'infini et ne permettent pas la définition de la hiérarchie infinie des infinis proposée par Cantor.
Les cardinalités correspondant aux ensembles N , P ( N ), P ( P ( N )), P ( P ( P ( N ))), … sont les nombres de beth , , , , …, le premier nombre de beth étant égal à ( aleph naught ), la cardinalité de tout ensemble dénombrable infini, et le deuxième nombre de Beth étant égal à , la cardinalité du continu .
Dedekind-ensembles infinis
Dans certaines occasions, il est possible qu'un ensemble S et son sous-ensemble propre soient équinumériques. Par exemple, l'ensemble des nombres naturels pairs est égal à l'ensemble de tous les nombres naturels. Un ensemble qui est égal à un sous-ensemble propre de lui-même est appelé Dedekind-infinite .
L' axiome du choix dénombrable (AC ω ), une variante faible de l' axiome du choix (AC), est nécessaire pour montrer qu'un ensemble qui n'est pas Dedekind-infini est en fait fini . Les axiomes de la théorie des ensembles de Zermelo-Fraenkel sans l'axiome du choix (ZF) ne sont pas assez forts pour prouver que tout ensemble infini est infini de Dedekind, mais les axiomes de la théorie des ensembles de Zermelo-Fraenkel avec l'axiome du choix dénombrable ( ZF + AC ω ) sont assez forts. D'autres définitions de la finitude et de l'infinité des ensembles que celle donnée par Dedekind ne nécessitent pas l'axiome du choix pour cela, voir Ensemble fini § Conditions nécessaires et suffisantes pour la finitude .
Compatibilité avec les opérations définies
L'équinumérosité est compatible avec les opérations ensemblistes de base d' une manière qui permet la définition de l' arithmétique cardinale . Concrètement, l'équinumérosité est compatible avec les unions disjointes : Soit quatre ensembles A , B , C et D avec A et C d'une part et B et D d'autre part disjoints deux à deux et avec A ~ B et C ~ D alors A ∪ C ~ B ∪ D . Ceci est utilisé pour justifier la définition de l' addition cardinale .
De plus, l'équinumérosité est compatible avec les produits cartésiens :
- Si A ~ B et C ~ D alors A × C ~ B × D .
- A × B ~ B × A
- ( A × B ) × C ~ A × ( B × C )
Ces propriétés sont utilisées pour justifier la multiplication cardinale .
Étant donné deux ensembles X et Y , l'ensemble de toutes les fonctions de Y à X est noté X Y . Alors les affirmations suivantes tiennent :
- Si A ~ B et C ~ D alors A C ~ B D .
- A B ∪ C ~ A B × A C pour B et C disjoints .
- ( A × B ) C ~ A C × B C
- ( A B ) C ~ A B × C
Ces propriétés sont utilisées pour justifier l' exponentiation cardinale .
De plus, l' ensemble de puissance d'un ensemble donné A (l'ensemble de tous les sous - ensembles de A ) est équinumérique à l'ensemble 2 A , l'ensemble de toutes les fonctions de l'ensemble A à un ensemble contenant exactement deux éléments.
Définition catégorielle
En théorie des catégories , la catégorie des ensembles , notée Ensemble , est la catégorie constituée de la collection de tous les ensembles en tant qu'objets et de la collection de toutes les fonctions entre les ensembles en tant que morphismes , avec la composition des fonctions comme composition des morphismes. Dans Set , un isomorphisme entre deux ensembles est précisément une bijection, et deux ensembles sont équinumériques précisément s'ils sont isomorphes en tant qu'objets dans Set .