La "taille" des ensembles : ordinaux, cardinaux

La "taille" des ensembles : ordinaux, cardinaux

 

Source : http://www.les-mathematiques.net/a/a/a/node3.php3

Définition [Définitions de base pour les ordinaux] On dit qu'un ensemble muni d'une relation d'ordre est bien ordonné si et seulement si toute partie non vide de cet ensemble admet un élément minimum. L'ordre est alors appelé un bon ordre. On appelle segment initial d'une partie bien ordonnée un ensemble de cette partie tel que étant donné un élément de cette partie, tous les éléments qui sont inférieurs à cet élément sont aussi dans la partie. On appelle segment initial engendré par l'ensemble des  plus petits que ; cette partie est clairement un segment initial. 
Un ensemble est dit transitif si tout élément de cet ensemble est inclus dans cet ensemble. C'est à dire que si , alors  (non, il n'y a pas de faute de frappe!). Un ensemble est un ordinal s'il est transitif s'il est bien ordonné par , cette relation étant une relation d'ordre strict. On note  l'ensemble des ordinaux.

Par exemple les ensembles suivants sont des ordinaux:

 

 

 

Proposition Les segments initiaux d'un ordinal sont soit lui-même, soit ses éléments. 
Tout élément d'un ordinal est un ordinal. 
Un ordinal n'appartient pas à lui-même.

Démonstration
Soit  un segment initial d'un ordinal . Alors  est un segment initial engendré par un certain  ( est l'élément minimum de ); l'ensemble des éléments qui sont plus petits que  étant les éléments qui appartiennent à  (puisque c'est ainsi que l'on a défini la relation d'ordre),  est donc le segment initial engendré par . 
Facile... 
Il suffit de voir que l'on a imposé que  soit un ordre strict.

Proposition Etant donné deux ordinaux et , une et une seule des trois assertions suivantes est vérifiée: 

.

Démonstration Il suffit de considérer l'intersection de  et  et d'examiner ses propriétés.

La relation  est donc une relation d'ordre total sur la classe des ordinaux.

Proposition La relation  est un bon ordre sur la classe des ordinaux. 
Le plus petit élément de la classe des ordinaux plus grands que  est . 
L'union d'une classe d'ordinaux est un ordinal; il est plus grand que tous les ordinaux de cette classe, et il est plus petit que tous les autres ordinaux plus grands que tous ces ordinaux.

Démonstration
Il suffit de constater comme on l'a vu plus haut que le segment initial engendré par  est . 
Il est clair que  doit appartenir à un tel élément, ainsi qu'être inclus dedans; réciproquement l'ensemble . 
Facile.

Définition Etant donné  un ordinal,  est appelé le successeur de . On le note .  est dit le prédécesseur de .

Propriété amusante: 
La classe des ordinaux n'est pas un ensemble. En effet si un tel ensemble  existe, alors tout élément de  est un ordinal, et donc un ensemble d'ordinaux, et donc ; ce qui n'est pas possible pour un ordinal puisque  est une relation d'ordre strict.

Définition On appelle morphisme d'ordre entre deux ensembles ou classes ordonnés  et  une application de  vers  telle que . Un morphisme d'ordre bijectif est appelé isomorphisme d'ordre. S'il existe un isomorphisme d'ordre entre deux ensembles ou classes alors on dit que ces ensembles ou classes sont isomorphes pour l'ordre.

Théorème S'il existe un isomorphisme d'ordre entre deux ordinaux et , alors  et  sont égaux (alors l'isomorphisme d'ordre est l'identité).

Théorème Pour tout ensemble ordonné  il existe un et un seul isomorphisme d'ordre de  vers un ordinal.

Théorème Toute relation de bon ordre dont le domaine n'est pas un ensemble est nécessairement isomorphe pour l'ordre à la classe des ordinaux.

Il est ensuite possible de montrer que s'il est vrai pour une certaine propriété  à une seule variable libre  que  est vrai pour tout ordinal  plus petit que , alors  est vraie pour , alors on peut conclure que la propriété est vraie pour tout ordinal.

Il reste de nombreuses choses à justifier pour expliquer toutes les petites choses que l'on s'autorise en maths sans se prendre la tête trop; mais ces considérations dépassent mon propos...

 

 

 

 

Théorème [Théorème de Cantor-Bernstein] Soit  et  deux ensembles,  une injection de  dans , et  une injection de  dans ; alors il existe une bijection de  dans .

Démonstration On considère l'ensemble des parties  de  telles que . 
On montre que cet ensemble admet un élément maximal (car il est stable par réunion) 
On montre que le maximum  vérifie 
On montre que la fonction qui à  associe  si  et l'unique  tel que  si  est une bijection

 

 

Définition [Définitions sur les ordres] Un ordre est une relation réflexive, antisymétrique, transitive. 
Une relation d'ordre strict est une relation  telle que  définie par  soit une relation d'ordre, et telle que pour tout  . 
Un élément  d'une partie  est un minimum de cette partie  si et seulement si  et si . 
Un élément  d'une partie  est un élément minimal de  si et seulement si  et si  et . 
Un élément  est dit minorant d'une partie  si ; il n'est pas nécessaire que  soit dans . 
On définit de même maximum, élément minimal, majorant. 
La figure  illustre ces notions.

Un bon ordre est un ordre tel que toute partie non vide a un minimum.

 

 

 

Axiome [Axiome du choix, première version] Etant donné un ensemble , il existe une fonction  qui à une partie non vide de  associe un élément de cette partie.

Axiome [Axiome du choix, deuxième version] Un produit d'ensembles non vides est non vide.

On montre facilement que ces deux axiomes sont équivalents. Pour des applications amusantes de l'axiome du choix on pourra consulter .

Théorème [Théorème de Zermelo] non vide il existe une relation de bon ordre (i.e. telle que toute partie non vide admette un minimum).

Il est difficile de montrer ce théorème à partir de l'axiome du choix. La réciproque est par contre facile.

Définition [Ensemble inductif] Deux éléments sont dits comparables si l'un des deux est inférieur ou égal à l'autre. 
On appelle chaine un ensemble totalement ordonné, c'est à dire tel que deux éléments soient toujours comparables. 
Un ensemble ordonné est dit inductif si toute chaine admet un majorant.

Lemme [Lemme de Zorn] Tout ensemble non vide ordonné inductif admet un élément maximal.

Le lemme de Zorn est équivalent au théorème de Zermelo, lui même équivalent aux deux versions de l'axiome du choix. On peut montrer Zermelo à partir de Zorn en considérant l'ensemble des bons ordres sur des parties de , un couple  étant inférieur à un couple , avec  et  des parties de  et  et des bons ordres sur respectivement  et , si , , et si  et  avec , alors .

L'axiome du choix permet par exemple de démontrer l'existence d'une base pour tout espace vectoriel. L'axiome du choix est équivalent à l'existence d'une injection de dans  ou de  dans  pour tous ensembles  et ; la preuve de ce fait à partir de Zorn se fait facilement, en considérant les bijections entre des parties de  et des parties de , par contre la réciproque est difficile.

L'axiome de fondation est l'assertion selon laquelle dans tout ensemble non vide il existe un élément d'intersection vide avec cet ensemble; l'axiome de fondation sera plus détaillé en .

Théorème [Consistance relative de  et de ]

( désigne l'axiome du choix)

Si la théorie axiomatique de Zermelo-Fraenkel avec axiome de fondation est consistante, alors la théorie de Zermelo-Fraenkel avec axiome de fondation et axiome du choix est consistante. 
Si la théorie axiomatique de Zermelo-Fraenkel est consistante, alors la théorie de Zermelo-Fraenkel avec axiome du choix est consistante. 
D'autre part si la théorie de Zermelo-Fraenkel est consistante, alors la théorie de Zermelo-Fraenkel avec la négation de l'axiome du choix est consistante. 
Enfin, si la théorie de Zermelo-Fraenkel avec axiome de fondation est consistante, alors la théorie de Zermelo-Fraenkel avec axiome de fondation et avec la négation de l'axiome du choix (i.e. en supposant qu'il existe un ensemble sur lequel on ne peut pas construire une relation de bon ordre) est consistante. 

Démonstration Fortement non trivial. Je passe.

Il est aussi possible de remplacer la négation de l'axiome du choix par le fait que  ne puisse pas être bien ordonné; une telle théorie est consistante si la théorie avec axiome de fondation est consistante.

 

On peut énoncer sans l'axiome du choix: 
- un produit de groupes est non vide 
- un produit dénombrable d'espaces métriques compacts est compact

 

Définition Deux ensembles sont dits équipotents s'il existe une bijection de l'un dans l'autre.

Il est évident qu'il s'agit là d'une relation d'équivalence.

L'axiome du choix permet de démontrer le théorème suivant:

Théorème Tout ensemble est équipotent à un ordinal.

Définition Etant donné un ensemble, on sait qu'il existe au moins un ordinal auquel cet ensemble est équipotent. Eventuellement il peut y en avoir plusieurs; le plus petit élément de ces ordinaux (au sens défini plus haut sur les ordinaux, c'est à dire la relation ) est appelé le cardinal de l'ensemble. On note usuellement  le cardinal de , ou . On note  la classe des cardinaux.

Théorème [Théorème de Cantor] Pour tout ensemble , on a . 

Démonstration Supposons le contraire; alors il existe une surjection  de  dans . Posons  l'ensemble des  tels que ; il suffit alors de considérer le  tel que . On constate que si , alors ; et vice-versa.

On notera que  n'est pas un ensemble; sinon on pourrait construire un ensemble égal à , ce qui est impossible.

Définition [Somme de cardinaux] On note  le cardinal de l'union disjointe de deux ensembles respectivement équipotents à  et . 
On notera que cette définition pose quelques petits problèmes de définition, pas difficiles à résoudre. L'addition de cardinaux est commutative et associative. 
Une propriété importante est le fait que la somme des  pour  est le plus grand élément entre  et les , sous réserve que l'un au moins de ses ensembles (ou l'un des ) soit infini.

Définition [Produit de cardinaux] On note  le cardinal du produit cartésien de  et de . 

Là aussi il convient de vérifier que le produit de deux couples d'ensembles de mêmes cardinaux respectifs est le même. On peut en outre vérifier que la multiplication de cardinaux est associative et commutative, et distributive par rapport à l'addition. On notera que le produit de deux cardinaux est le plus grand de ces deux cardinaux.

Définition [Exponentiation de cardinaux] Etant donnés des cardinaux  et  on note  le cardinal de l'ensemble des applications de  dans . 
On vérifiera facilement que la définition a bien un sens. On peut aussi montrer que  et que .

De nombreuses manipulations plus approfondies sur les cardinaux requièrent l'axiome du choix.

Définition Un ordinal est dit fini si tout ordinal inclus dans cet ordinal admet un prédécesseur. On appelle aussi entier naturel un ordinal fini.

Moi ça m'amuse beaucoup de définir un entier naturel comme étant un ensemble  incluant chacun de ses éléments, tel que pour toute partie  de  il existe tel que  pour tout  et pour tout élément  de  il existe  incluant chacun de ses éléments, tel que pour toute partie  de  il existe  tel que  pour tout , et tel que . Si je me suis pas gouré.

On montre plein de choses bien agréables sur les ordinaux finis; ils sont stable par union, produit, exponentiation. On montre aussi que tout ordinal fini est un cardinal.

Définition Un cardinal est dit fini s'il est fini en tant qu'ordinal. Dans le cas contraire il est dit infini. On note  la classe des cardinaux infinis.

Nous supposons maintenant l'axiome de la théorie des ensembles selon lequel il existe un ordinal infini. Un ordinal infini est, par définition, un ordinal qui n'est pas fini. Cet axiome de la théorie des ensembles est équivalent à l'axiome selon lequel la classe des ordinaux finis est un ensemble; ainsi, puisque la classe des ordinaux n'est pas un axiome, il existe un ordinal infini. On peut encore formuler cet axiome en disant qu'il existe un ordinal limite, au vu de la définition ci-dessous:

Définition Un ordinal différent du vide et sans prédécesseur est appelé un ordinal limite. C'est donc un ordinal non vide tel que tout élément plus petit que lui a un successeur aussi plus petit que lui.

Propriété: Un ordinal limite est l'union des ordinaux qui lui sont inférieurs.

Définition On appelle  le minimum des ordinaux infinis.  est donc un ordinal limite, c'est le plus petit, et c'est l'ensemble des ordinaux finis. 
Un ensemble est dit fini si son cardinal est fini. 
Un ensemble est dit dénombrable si son cardinal est inférieur ou égal à . 
est un cardinal; on note  et pour tout ordinal  n'étant pas un ordinal limite, alors avec  le prédécesseur de ,  est le plus petit ordinal plus grand que ; et si  est un ordinal limite, alors  est l'union des  pour .

Propriété: 
Un ensemble infini est un ensemble contenant une partie dénombrable infinie. 
Un ensemble infini est un ensemble qui est en bijection avec l'une de ses parties propres. 
est un cardinal.

 

---

suivant: monter: précédent:

C.Antonini_JF.Quint_P.Borgnat_J.Berard_E.Lebeau_E.Souche_A.Chateau_O.Teytaud