Dernière version du 04.10.2009 22h10
Sommaire
1 NOMBRES TRANSFINIS
1.1 RAPPELS : RELATIONS D'EQUIVALENCE
1.1.1 Relations entre ensembles.
1.1.1.1 Exemples de relations
1.1.2 Relations dans un ensemble.
1.1.2.1 Réflexivité
1.1.2.2 Symétrie
1.1.2.3 Antisymétrie
1.1.2.4 Transitivité
1.1.3 Relations d'équivalence dans un ensemble
1.1.3.1 Classes d'équivalence
1.1.4 Notion de partition d'un ensemble
2 Equipotence d'ensembles et cardinal
2.1 L'équipotence est une relation d'équivalence
2.2 Entiers naturels en tant que classes d'équivalence
3 Opérations sur les cardinaux
4 Ensembles dénombrables ; cardinal du dénombrable
5 Cardinal de l'ensemble des parties d'un ensemble
6 Cardinal du continu
6.1 Le cardinal du continu est strictement supérieur au cardinal du dénombrable
[modifier (
modifier-632-section-1.cours)]NOMBRES TRANSFINIS
"Trans" signifie : "au-delà de".
Ces nombres sont donc des infinis. Par exemple, le cardinal (nombre d'éléments) de ou de
.
[modifier ( modifier-632-section-2.cours)]RAPPELS : RELATIONS D'EQUIVALENCE
[modifier ( modifier-632-section-3.cours)]Relations entre ensembles.
Soient deux ensembles et
. On appelle produit cartésien
l'ensemble des couples dont le premier élément appartient à
et le second à
:
Une relation d'un ensemble
vers un ensemble
est par définition le triplet
, où
G est une partie de
, appelé graphe de la relation.
Nous noterons :
est appelé ensemble de départ, et
ensemble d'arrivée.
Soient ; on dira que
est en relation avec
par la relation
si et seulement si
appartient au graphe de
, et l'on notera
Dans le cas contraire, n'est pas en relation avec
par
:
[modifier ( modifier-632-section-4.cours)]Exemples de relations
1. Si pour tout , il existe un et un seul
tel que
, on dira que
est une application de
vers
.
On notera dans ce cas particulier au lieu de
le fait que
est en relation avec
.
On dira que est l'image de
, que
est un antécédent de
.
On notera aussi dans le cas où
est une application.
L'ensemble des applications de vers
est noté
(nous verrons plus tard pourquoi).
Les Anglo-Saxons nomment "mappings" les applications.
2. Si pour tout , il existe au plus un
tel que
, on dit que
est une fonction de
vers
.
On notera également si
est une fonction de
vers
.
On notera aussi au lieu de
.
On dira égalemnet que est l'image de
(si elle existe), et
un antécédent de
L'ensemble des qui ont une image dans
est appelé domaine de définition ou ensemble de définition de
et noté
:
Les applications sont des cas particuliers de fonctions, correspondant au cas où tout entier.
3. Une classe très importante d'applications de vers
est constituée par les bijections.
On dit qu'une application est une bijection, ou est bijective, si :
tout a un antécédent et un seul dans
(et bien sûr, tout a une image et une seule dans
).
Pour les Anglo-Saxons, une bijection est appelée "one-to-one mapping" (un élément de l'un des ensembles correspond à un élément de l'autre, dans les deux sens).
Les conséquences sont importantes : comme tout élément a une et une seule image dans
, s'il existe
éléments dans
, il y a au plus
images dans
.
Or, comme tous les éléments de ont un antécédent, c'est-à-dire sont des images, il y a au plus
éléments dans
. On notera
(cardinal = nombre d'éléments)
D'autre part, tous les éléments de sont des antécédents, puisque
est une application. Il ne peut y avoir plus d'éléments dans
que dans
, car les éléments de
ont chacun un antécédent et un seul. Donc
Nous énoncerons : s'il existe une bijection de vers
(on dit souvent "de
sur
)"), alors ces ensembles ont même cardinal (
).
[modifier ( modifier-632-section-5.cours)]Relations dans un ensemble.
On considère ici les relations de vers lui-même. On dira que ce sont des relations dans E.
On peut définir dans ce cadre plusieurs propriétés possibles :
[modifier ( modifier-632-section-6.cours)]Réflexivité
Une relation dans un ensemble
est dite réflexive si
(tout élément de est en relation avec lui-même)
Exemples :
La relation d'égalité dans (
de toute évidence) ; le parallélisme dans l'ensemble des droites du plan (
) ; la relation d'ordre dans
(
également) ; la relation "divise" dans
: on a bien
(on définit cette relation par
) ; la relation "congruence modulo 6" définie dans
par
, etc.
[modifier ( modifier-632-section-7.cours)]Symétrie
Une relation dans un ensemble
est dite symétrique si
(si est en relation avec
, alors
est aussi en relation avec
)
Exemples :
La relation d'égalité dans (
de toute évidence) ; le parallélisme de droites (
) ; la relation "congruence modulo 5" définie dans
par
, etc.
[modifier ( modifier-632-section-8.cours)]Antisymétrie
Une relation dans un ensemble
est dite antisymétrique si
On peut montrer (voir Logique) que cette définition équivaut à
Autrement dit, si deux éléments distincts vérifient , on n'a pas
.
Exemples :
La relation d'ordre dans :
; la relation "divise" dans
(en effet, si
, alors il existe
entiers naturels tels que
, ce qui implique
pour toutes les valeurs de
dans
, autrement dit
; la seule possibilité dans
est
, ce qui implique bien
)
[modifier ( modifier-632-section-9.cours)]Transitivité
Une relation dans un ensemble
est dite transitive si
Exemples :
La relation d'égalité dans (
) ; le parallélisme de droites (
) ; la relation "divise" dans
; la congruence modulo
(
), etc.
[modifier ( modifier-632-section-10.cours)]Relations d'équivalence dans un ensemble
C'est une notion d'une extrême importance.
Par définition, une relation dans
est appelée relation d'équivalence si elle a les 3 propriétés
- réflexivité
- symétrie
- transitivité
Exemples de relations d'équivalence
L'égalité dans un ensemble quelconque ; la relations entre élèves du Lycée "est dans la même classe que" ; le parallélisme d'un ensemble de droites ; la congruence modulo dans
ou
, etc.
[modifier ( modifier-632-section-11.cours)]Classes d'équivalence
Soit une relation d'équivalence dans l'ensemble
.
Soit un élément de
.
La classe d'équivalence de , ou plus brièvement la classe de
, est l'ensemble
des éléments de
en relation avec
:
ou, vue la symétrie de toutes les relations d'équivalence,
Première propriété
Une classe d'équivalence n'est jamais vide : en effet, comme on a toujours ,
contient au moins
:
(lire : la classe de contient comme élément
, ou contient (pour l'inclusion) le singleton
, qui est non vide)
Deuxième propriété (importante)
Si deux classes d'équivalence ont un élément en commun, elles sont confondues.
Les classes sont des parties de .
Soient deux classes dans l'ensemble
.
Supposons qu'elles aient un élément en commun :
.
Cela veut dire que (et aussi
).
Appelons un élément quelconque de
: on a donc
.
Mais alors, comme et aussi
, on a successivement
, donc
.
Autrement dit, , ce qui veut dire que
(tout élément de
est élément de
).
On peut évidemment raisonner dans l'autre sens, ce qui donne .
En tout, on obtient .
En contraposant cet énoncé, on obtient :
Deux classes d'équivalence différentes sont disjointes.
En effet, la contraposition de
est
.
Troisième propriété (assez évidente)
La réunion des classes d'équivalence est tout entier.
En effet, la classe de ,
, contient
(réflexivité).
Donc la réunion de toutes les classes des éléments contient tous les éléments
, donc contient dans le sens de l'inclusion l'ensemble
. Comme toutes ces classes sont des parties de
, leur réunion est une partie de
.
En tout, la réunion des classes est :
[modifier ( modifier-632-section-12.cours)]Notion de partition d'un ensemble
Soit une famille de parties
d'un ensemble
.
Une telle famille est la donnée d'un certain nombre de parties repérées par un indice
appartenant à un ensemble d'indices
quelconque.
Une famille de parties de
est appelée partition de
si :
- Toutes les parties
sont non-vides.
- Les
- La réunion des
tout entier.
Autrement dit :
On voit donc que :
Pour toute relation d'équivalence sur , les classes d'équivalence constituent une partition de
.
Juste un exemple :
La congruence modulo 4 dans est une relation d'équivalence dont les classes sont
(On vérifie facilement que ces 4 classes forment une partition de )
Si l'on considère la même relation, mais dans l'ensemble , les classes sont
Là aussi, on a une partition de .
[modifier ( modifier-632-section-13.cours)]Equipotence d'ensembles et cardinal
Définition : On dira que deux ensembles et
sont équipotents s'il existe une bijection de l'un sur l'autre ; autrement dit, s'ils ont même nombre d'éléments (cas des ensembles finis).
On notera cela
(
équipotent à
)
[modifier ( modifier-632-section-14.cours)]L'équipotence est une relation d'équivalence
Attention ! L'ensemble de tous les ensembles n'existe pas (si l'on essayait de la définir, on aurait des problèmes de logique !).
Mais on peut considérer disons, des ensembles "limités" d'ensembles, et là-dessus, il n'est pas difficile de définir l'équipotence comme relation.
L'équipotence est réflexive
En effet, puisque
est une bijection (évidente).
L'équipotence est symétrique
En effet, s'il existe une bijection , alors il existe une bijection
, la réciproque de
précisément.
(rappel : Si est une bijection,
)
L'équipotence est transitive
Il est clair que s'il existe une bijection et une bijection
, alors
définie par
est également une bijection.
[modifier ( modifier-632-section-15.cours)]Entiers naturels en tant que classes d'équivalence
Donnons des noms aux classes selon la relation "équipotence" :
La classe de l'ensemble vide sera appelée 0 ;
La classe des singletons sera appelée 1 ;
La classe des paires sera appelée 2, etc. :
...
, etc.
On appellera cardinaux finis ces classes d'équivalence.
On dit aussi entiers naturels, synonyme de cardinaux finis.
L'ensemble des cardinaux finis est appelé :
On généralise à tout ensemble en appelant cardinal d'un ensemble sa classe d'équivalence pour la relation d'équipotence.
[modifier ( modifier-632-section-16.cours)]Opérations sur les cardinaux
Si deux ensembles sont disjoints, on pose
et pour deux ensembles quelconques, on pose
C'est assez intuitif. Pour les cardinaux finis, ce sont les définitions usuelles de l'addition et de la multiplication. Mais on étendra cette définition aux ensembles infinis.
[modifier ( modifier-632-section-17.cours)]Ensembles dénombrables ; cardinal du dénombrable
On dit qu'un ensemble est dénombrable s'il existe une bijection entre cet ensemble et , autrement dit, s'il est équipotent à
, ou encore de même cardinal que
.
On appelle ce cardinal le cardinal du dénombrable, noté avec la lettre hébreue (aleph) munie d'un indice supérieur 0.
Ce n'est pas un entier naturel, un nombre fini, mais "le plus petit" des cardinaux transfinis (ou infinis).
Propriété 1
On a
C'est une propriété vérifiée par les nombres transfinis en général.
Elle implique immédiatement, pour tout :
Preuve : 1) Il existe une bijection de sur
:
.
Donc, comme et
sont disjoints, on peut écrire
2) Raisonnons par récurrence : si , alors
.
Propriété 2
On a
soit
ce qui implique immédiatement, pour tout :
Preuve :
1) Soit l'ensemble des entiers naturels pairs et
l'ensemble des entiers naturels impairs.
Il existe une bijection de sur chacun d'eux :
et
.
Donc
Mais ils sont disjoints et leur réunion est , donc
2) Raisonnons par récurrence : si l'on a
alors
.
C'est prouvé.
Propriété 3
On a
ou
Ceci se généralise aisément, pour tout :
Preuve :
1) Montrons qu'il existe une bijection , autrement dit de l'ensemble des entiers naturels sur l'ensemble des couples d'entiers naturels.
Formons un tableau avec les couples :
| (0,0) | (0,1) | (0,2) | (0,3) | (0,4) ... |
| (1,0) | (1,1) | (1,2) | (1,3) | (1,4) ... |
| (2,0) | (2,1) | (2,2) | (2,3) | (2,4) ... |
| (3,0) | (3,1) | (3,2) | (3,3) | (3,4) ... |
| ... | ... | ... | ... | ... |
Décidons que
, etc.>
On voit que les couples de forme avec
ont
images dans
.
Définissons l'image d'un couple :
Avant ce couple, il y a eu tous les couples avec
.
Ces couples sont au nombre de
Le dernier de ces couples précédents a pour image :
D'autre part, parmi les couples dont la somme des deux arguments vaut , le couple
est le
.
Donc l'image de est
Vérifions :
L'image de est
.
C'est bien ce qui a été vu plus haut.
Ainsi, on a défini sans ambiguité une bijection de sur
.
2) Si l'on a , alors
.
[modifier ( modifier-632-section-18.cours)]Cardinal de l'ensemble des parties d'un ensemble
D'abord, montrons que pour un ensemble fini de cardinal
, le nombre de parties de
est
.
Si , il n'y a qu'une seule partie de
, lui-même (soit l'ensemble vide).
Le nombre de parties de , pour
, est donc
.
Soit à présent un ensemble fini de cardinal
.
Supposons que .
Considérons , où
, donc
.
Quelles sont les parties de ?
On peut les classer en deux catégories : celles qui ne contiennent pas , et celles qui contiennent
.
Celles qui ne contiennent pas ne sont autres que les ensembles de
. Il y en a donc
.
Celles qui contiennent sont de forme
, où
est une partie de
. Il y en a aussi
.
Donc a
parties. La preuve (par récurrence) est faite.
Notation
Pour tout ensemble , on notera
(mais aussi
) l'ensemble des parties de
.
On peut donc écrire
ou
.
Propriété (théorème de Cantor)
Le cardinal de l'ensemble des parties d'un ensemble (fini ou infini) est toujours strictement supérieur au cardinal de cet ensemble.
Autrement dit, pour tout ensemble , on a
Preuve
Soit un ensemble. Supposons (preuve par l'absurde) qu'il existe une bijection
.
Définissons la partie de
telle que
Cet ensemble existe, et il n'est pas vide a priori. Sinon,
n'aurait pas d'antécédent, ce qui serait en contradiction avec l'hypothèse (qui dit qu'il existe une bijection de
sur
).
contient l'antécédent (unique) de
, donc est non-vide.
Comme est une bijection, il existe
telle que
.
Deux cas se présentent.
Si , alors la définition de
implique
. C'est absurde.
Si , la définition de
implique
, ce qui est tout aussi absurde.
Donc l'existence de , bijection de
sur
, est absurde.
On a donc forcément
Notamment, on a
et bien sûr
, etc.
Il existe donc une hiérarchie dans les nombres "infinis".
[modifier ( modifier-632-section-19.cours)]Cardinal du continu
On pose pour l'ensemble des réels :
(cardinal du continu)
Propriété
Montrons que le cardinal de est aussi le cardinal de son intervalle fini
:
En effet, l'application
est une bijection de sur
.
est strictement croissante sur
.
Donc et donc
Tout élément de a un antécédent : l'équation en
\frac{x}{1+|x|}=y</math> a une solution qu'on remarque du même signe que
:
Si , alors
, et la solution unique est
Si , alors
, et la solution unique est
Et si ,
.
On a bien montré que
Remarque : cela équivaut aussi à dire que le cardinal de égale celui de n'importe quel intervalle non-vide de
, ouvert, fermé ou semi-ouvert.
[modifier ( modifier-632-section-20.cours)]Le cardinal du continu est strictement supérieur au cardinal du dénombrable
Comme , on a déjà
.
Montrons que cette inégalité est stricte, en prouvant que
.
(la dernière égalité est facile à démontrer : en effet, est une bijection).
Preuve (par l'absurde) :
Supposons qu'il existe une bijection .
A tout entier , on pourrait faire correspondre par cette bijection un nombre appartenant à
, nombre dont le développement décimal est de forme
.
Construisons un réel appartenant à
, s'écrivant donc
, de la manière suivante :
* si
- si
...
et pour tout ,
- si
- si
.
Il est clair que est distinct de tous les
pour
.
Autrement dit, est un élément de
qui n'a pas d'antécédent.
C'est une contradiction ; donc une telle bijection ne saurait exister.
Nous avons ainsi prouvé que
On a formulé une hypothèse encore non démontrée (à ma connaissance) : que (Hypothèse du Continu).
Cela ne veut pas dire que et le nombre transfini le plus grand, puisque nous avons vu que
est encore plus grand.