Mathématiques pour l’Informatique 2 2016–17 http://www.lri.fr/~blsk/MathInfo2
Mathématiques pour l’Informatique 2 |
2 Théorie naive des ensembles
La théorie naive des ensembles formalise la notion de collection
d’objets. Les ensembles eux-mêmes sont des objets que l’on
peut organiser dans d’autres ensembles.
2.1 Constructions de base
Propriétés des ensembles.
-
L’appartenance x ∈ X est un symbole de prédicat
primitif pour la théorie des ensembles.
On écrira aussi x ∉X pour ¬ x∈ X.
- L’inclusion X ⊆ Y est définie comme
∀ x, x ∈ X ⇒ x ∈ Y
- L’egalité X = Y est définie comme ∀ x, x
∈ X ⇔ x ∈ Y qui est équivalent à X ⊆ Y
∧ Y ⊆ X.
Notations.
On écrira ∀ x ∈ A,P pour
∀ x, x ∈ A ⇒ P et ∃ x ∈ A,P pour
∃ x, x ∈ A ∧ P.
Ensembles de base.
-
∅ ensemble vide, on a ∀ x,
x∉∅. La formule ∀ x ∈ ∅,P est toujours vraie et la formule ∃ x ∈ ∅,P est toujours fausse.
- Ensemble défini par extension {a1;…;an } qui
représente l’ensemble formé des éléments a1,…,an. On
a x ∈ {a1;…;an } ⇔ x=a1 ∨ … ∨
x=an.
- ℕ ensemble des entiers; l’ensemble des entiers
contient un élément 0 et pour tout entier n, un
entier n+1. Cet ensemble est infini.
- A × B est le produit cartésien des
ensembles A et B. C’est l’ensemble des couples
(a,b) avec a ∈ A et b ∈ B.
Si
p∈ A× B alors il existe a∈ A et b
∈ B tel que p=(a,b). On note fst(p) la
première composante a et snd(p) la seconde
composante b.
- ℘(A) ensemble des parties de A. On a X
∈ ℘(A) ssi X ⊆ A. On dit que X est un
sous-ensemble de A.
Exemple 1
L’ensemble des parties d’un ensemble X contient toujours
l’ensemble vide ∅ et l’ensemble X lui-même.
-
L’ensemble des parties de l’ensemble vide est l’ensemble
{∅ } formé d’un seul élement
∅.
- L’ensemble des parties de {∅ } est
{∅;{∅ } }.
Définition par compréhension.
Soit une formule P et un ensemble X, on peut définir
par compréhension un nouvel ensemble {x ∈ X | P}
qui est le sous-ensemble de X des objets qui vérifient
P. On a:
x ∈ {x ∈ X | P} ⇔ x ∈ X ∧ P |
Exemple 2
On suppose définie la relation usuelle d’ordre strict sur les
entiers x<y.
On définit l’ensemble [0,n[ comme {x ∈ ℕ | x < n}
Le schéma de compréhension introduit une correspondance entre une
formule logique P(x) portant sur une variable x
désignant un objet dans l’ensemble A et le sous-ensemble de
A des objets qui satisfont P.
Exemple 3 (Paradoxe de Russel)
Que se passe-t-il si on peut construire l’ensemble P suivant
des ensembles qui n’appartiennent pas à eux mêmes. P =def
{x | x ∉x}.Si P est un ensemble, on se pose
la question: est-ce que P ∈ P? On remarque que P
∈ P ⇔ P ∉P, d’où une contradiction. On en déduit
que P n’est pas un ensemble ou encore que l’ensemble
de tous les ensembles n’existe pas (sinon le schéma de
compréhension permettrait de définir P).
Intersection, union, différence.
Des opérations usuelles sur les ensembles sont l’union, l’intersection
et la différence. Soient A et B deux ensembles, on
peut construire les ensembles suivants:
-
A ∩ B =def {x ∈ A | x ∈ B}
- A ∖ B =def {x ∈ A | x ∉B}
Exercice 1
Montrer que si X ⊆ A et X ⊆ B alors
X ⊆ A∩ B
Pour définir l’union de manière similaire, il faut identifier un
ensemble W tel que A,B ⊆ W
et définir:
A ∪ B =def {x ∈ W | x ∈ A ∨ x ∈ B}.
La théorie des ensembles comporte une règle spécifique qui garantit
l’existence de W. C’est la règle de l’union qui est
généralisée à une famille quelconque d’ensembles. Plus précisément, si
on a un ensemble X qui est formé d’ensembles, alors il existe
un ensemble ∪X qui correspond à l’union de tous les
ensembles Y ∈ X. C’est-à-dire que :
Dans le cas de l’union de deux ensembles A et B, on
pose X={A,B } (définition par extension)
on a Y∈ X ⇔ Y=A ∨ Y=B. On
pose A ∪ B =def ∪{A,B } et on vérifie que
x ∈ A ∪ B ⇔ (x ∈ A ∨ x ∈ B).
Intersection.
Soit X un ensemble non vide d’ensembles. On définit l’intersection
∩X de tous les éléments de X, c’est-à-dire que
x appartient à ∩X s’il appartient à tous les
ensembles Y ∈ X.
Comme X est non vide, il existe X0 ∈ X et on
définit ∩X =def {x ∈ X0 | ∀ Y∈ X, x ∈ Y}.
2.2 Relations
La notion de relation est importante en informatique en particulier pour modéliser des systèmes d’information, c’est-à-dire des ensembles d’objets qui ont des relations entre elles. De plus parmi les relations, nous distinguerons celles qui ont la propriété d’être des fonctions qui vont être utilisées pour représenter des transformations de données.
Définition 1 (Relation binaire)
Une relation binaire sur A× B est un
sous-ensemble de A× B, c’est-à-dire un élément de
℘(A × B).
Exemple 4
On considère l’ensemble A des étudiants et l’ensemble
B des cours ainsi qu’une relation suit entre étudiants
et cours qui capture le fait qu’un étudiant suit un cours. Le même
étudiant peut suivre plusieurs cours (éventuellement zéro). De même
un cours peut être suivi par zéro ou plusieurs étudiants.
Le schéma de compréhension introduit une correspondance entre les
formules logiques R(x,y) portant sur une variable x
désignant un objet dans l’ensemble A et une variable y
désignant un objet dans l’ensemble B et les sous-ensembles de
A × B. La formule R(x,y) correspond à l’ensemble
défini par compréhension {p ∈ A ×
B | R(fst(p),snd(p))} que l’on notera aussi
{(x,y) ∈ A × B | R(x,y)}. Inversement, si R est une
relation binaire, on pourra écrire R(x,y) la propriété
(x,y) ∈ R.
Exemple 5
Soient R et S deux relations binaires sur A× B, on introduit les relations suivantes:
-
R−1 =def {(y,x) ∈ B × A | (x,y)∈ R}
- ¬ R =def {p ∈ A × B | p ∉R} qui peut s’écrire
{(x,y) ∈ A × B | ¬ R(x,y)}
- R ∩ S =def {p ∈ A × B | p∈ R ∧ p ∈ S} qui peut s’écrire {(x,y) ∈ A × B | R(x,y) ∧ S(x,y)}
- R ∪ S =def {p ∈ A × B | p∈ R ∨ p ∈ S} qui peut s’écrire {(x,y) ∈ A × B | R(x,y) ∨ S(x,y)}
Exercice 2
Soit R la relation binaire sur les entiers x ≤
y.
-
Faire le lien entre R−1, ¬ R et les
relations d’ordre usuelles sur les entiers.
- Trouver d’autres liens entre les relations d’ordre et
l’égalité.
Le domaine d’une relation est le sous-ensemble de A
des objets qui ont un correspondant dans la relation et
l’image d’une relation est le sous-ensemble de B des
objets qui ont un correspondant dans la relation.
dom(R) | | {x ∈ A | ∃ y,R(x,y)}
img(R) | | {y ∈ B | ∃ x,R(x,y)} |
2.3 Fonctions
Une fonction d’un ensemble A dans un ensemble B
est une manière d’associer à un élément de A,
un unique élément d’un ensemble B.
Les fonctions sont des cas particuliers de relations binaires, à savoir
l’ensemble des couples (x,y), telle que la fonction f
associe y à x. La relation est parfois appelée le
graphe de la fonction.
-
Une relation R est fonctionnelle si elle associe
au plus un élément de B à chaque élément de
A.
Rfun(R) | | ∀ a ∈ A, ∀ b1
b2 ∈ B, R(a,b1) ∧ R(a,b2) ⇒ b1=b2 |
- Une relation R est totale si elle associe
au moins un élément de B à chaque élément de
A.
Rtot(R) | | ∀ a ∈ A, ∃ b
∈ B, R(a,b) |
- Une relation R est une fonction totale si elle
est fonctionnelle et totale:
On introduit l’ensemble des fonctions totales de A dans
B comme un sous-ensemble des relations, celles qui sont
fonctionnelles et totales.
Définition 2 (Ensemble A→ B des fonctions totales de
A dans B)
L’ensemble A→ B des fonctions totales de A dans
B (appelées aussi applications)
est défini par compréhension: A→ B | |
{f ∈ ℘(A × B) | Fun(f)} |
Notation fonctionnelle.
Une fonction totale f associe exactement un élément de
B à chaque élément a∈ A et on note cet élément
f(a).
On peut définir une fonction à partir d’une expression e qui
représente un objet dans l’ensemble B qui dépend d’une
variable x dans l’ensemble A. On note fun x ⇒ e
cette fonction.
fun x ⇒ e | | {(x,y) ∈ A ×
B | y=e} |
Soit f le nom donné à cette fonction on pourra
aussi écrire f(x) =def e.
Définition 3 (Fonction partielle)
Une relation fonctionnelle f qui n’est pas totale est appelée
une fonction partielle. On utilise encore la notation
f(a) lorsque a appartient au domaine de la fonction.
Exercice 3
Si A est l’ensemble vide, existe-t-il des fonctions dans
A → B. Même question si A est non vide mais B
est vide.
Définition 4 (Restriction)
Si f est une application de A→ B et C⊆
A alors il existe une application fC de C→ B qui
coincide avec f sur C. On dira que fC est la restriction de f à C.
Définition 5 (Application injective)
Une application f ∈ A → B est injective si elle ne
relie pas deux éléments différents au même résultat.
Inj(f) | | ∀ x1 x2 ∈ A, f(x1)=f(x2) ⇒
x1=x2 |
Définition 6 (Application surjective)
Une application f ∈ A → B est surjective si tous les éléments de B sont accédés.
Surj(f) | | ∀ y ∈ B, ∃ x ∈ A, f(x)=y |
Définition 7 (Application bijective)
Une application qui est injective et surjective est dite bijective. Elle met en correspondance exacte les objets de A et les objets de B.
Définition 8 (Application réciproque)
Soit f une application dans A→ B. Si f est
bijective alors la relation réciproque f−1 est une application (dite application réciproque)
et on a
∀ x∈ A, f−1(f(x))=x ∀ y ∈ B, f(f−1(y))=y |
Exercice 4
On note n/2
la division entière.
-
La fonction qui à n associe 2× n est-elle
injective ? surjective ?
- Mêmes questions pour la fonction qui à
n associe n mod 2.
- Construire une application dans ℕ → ℕ qui n’est ni
injective, ni surjective.
Solution: f(n)=2 × (n/2) envoie 2k et 2k+1 sur 2k et donc n’atteint que les entiers pairs.
- Construire une bijection dans ℕ → ℤ.
Solution: f(n)= n/2 si n est pair et f(n)= −(n/2)−1 si n est impair.
Image d’un ensemble par une application.
Soit f une application dans A → B et X un
sous-ensemble de A. On note f(X), l’image de
l’ensemble X par f l’ensemble des éléments de
B qui peuvent être atteints par f à partir d’un
élément de X.
f(X)={y ∈ B | ∃ x ∈ X, f(x)=y} |
On définit également l’image inverse d’un ensemble par une application. Si Y est un sous-ensemble de B, on note f−1(Y), l’image inverse de
l’ensemble Y par f l’ensemble des éléments de
A qui atteignent par f un
élément de Y.
Exercice 5
-
Montrer que si Z ⊆ Z′ alors f(Z) ⊆ f(Z′) et
f−1(Z) ⊆ f−1(Z′)
- Soient deux ensembles X et X′
-
Montrer que f (X∩ X′) ⊆ f(X)∩ f(X′)
- L’égalité n’est pas vérifiée en général : donner un exemple où ces deux ensembles diffèrent, dire sous quelle condition sur f on a égalité.
Application à plusieurs arguments.
Une relation F(x1,…,xn,y) dans A1 ×
… × An× B est fonctionnelle si
∀ x1… xn y z,F(x1,…,xn,y) ⇒
F(x1,…,xn,z) ⇒ y=z |
On notera F(x1,…,xn) l’unique y tel que
F(x1,…,xn,y) lorsqu’il existe.
Une application à plusieurs arguments peut se voir comme une application à
un seul argument qui est un n-uplet dans le produit cartésien
A1 × … × An.
On notera A1 × … × An → B
l’ensemble des applications à n arguments.
Exercice 6
On s’intéresse à une relation entre des entiers naturels et des booléens {V;F}
R | | {(1,F);(2,V);(3,V);(4,F)} |
-
Cette relation définit-elle une fonction partielle ? une application ?
- Quelle est son domaine, son image ?
- Quelle est l’image par cette relation de l’ensemble {2;3} ?
- Quelle est l’image inverse par cette relation de l’ensemble {F} ?
- La relation est-elle injective ? surjective ? bijective ?
2.4 Ensemble fini
Définition 9 (Ensemble fini)
L’ensemble A est fini s’il existe un entier n∈ℕ et une application (fonction totale) injective f de A dans l’ensemble [0,n[.
Propriétés des ensembles finis.
Proposition 1
-
∅ est fini.
- Pour tout n, [0,n[ est fini.
- Si A est fini et B ⊆ A alors B
est fini.
- Si A et B sont finis alors il en est de même
de A∪ B.
- ℕ n’est pas fini.
Preuve:
-
Il existe une seule application dans ∅ →
[0,0[ (correspondant au graphe vide). Elle est
injective (par l’absurde, car il n’existe pas de
x∈∅, donc ∀ x y∈∅,
f(x)=f(y) ⇒ x=y est toujours vérifié.
- Il suffit de prendre la fonction identité (f(x)=x pour tout x∈ [0,n[).
- Si A est fini alors il existe n une application injective f dans A → [0,n[.
Soit l’application g dans B → [0,n[,
définie par ∀ x ∈ B, h(x)=f(x) (restriction de
f à B). Cette application est injective, donc
B est fini. - Si A et B sont finis alors il existe
n et m et des applications injectives f
dans A → [0,n[ et g dans B →
[0,m[. Soit l’application h dans A ∪
B → [0,n[, définie par ∀ x ∈ A,
h(x)=f(x) et ∀ x ∈ B∖ A, h(x)=n+g(x)
Cette relation est une application injective, donc A ∪
B est fini.
- On montre qu’il ne peut exister d’application injective de
ℕ → [0,n[. Intuitivement, si une telle
application f existe, on regarde l’image par f
des n+1 entiers f(0),…,f(n). Comme
f est injective, ils sont 2 à 2 distincts donc on a
n+1 éléments distincts qui devraient appartenir à un
[0,n[ qui ne contient que n éléments.
Formellement, cette propriété appelée lemme du tiroir se
montre par récurrence sur n.
□
Proposition 2 (Lemme du tiroir)
Soit n, m ∈ ℕ, si n < m alors il n’existe pas d’application injective dans [0,m[→ [0,n[.
Preuve:
La preuve est par récurrence sur n. On peut se ramener au cas où m=n+1 en effet s’il y a une application injective de
[0,m[→ [0,n[ avec n+1≤ m alors par restriction il en existe aussi une de [0,n+1[→ [0,n[.
-
Pour n=0 comme [0,1[ est non vide et
[0,0[ est vide, il n’existe pas d’application de
[0,1[ → [0,0[, a fortiori pas d’application
injective.
- Soit n quelconque, on suppose qu’il n’existe pas d’application injective de [0,n+1[→ [0,n[ et on va montrer qu’il n’en existe pas dans [0,n+2[→ [0,n+1[.
Supposons que l’on ait une application f injective de
[0,n+2[ → [0,n+1[. Nous allons construire
g injective de [0,n+1[ → [0,n[. On
pose k=f(n+1) on a 0 ≤ k ≤ n. Comme
f est injective et f(n+1)=k, on a ∀ x
<n+1, f(x)≠k. On pose pour x<n+1,
g(x)=f(x) si f(x)<k et g(x)=f(x)−1 si
k<f(x). On a ∀ x ∈ [0,n+1[, g(x)∈
[0,n[ et g est injective.
□
Définition 10 (Cardinal d’un ensemble fini)
Soit A un ensemble fini, il existe un unique entier n
tel qu’il existe une bijection dans A → [0,n[. Cet
entier est appelé le cardinal de l’ensemble A et est
noté |A|.
Preuve:
L’entier est unique car s’il existe une bijection f
de A → [0,n[ et une bijection g de A
→ [0,m[ alors il existe une bijection
f ∘ g−1 de [0,m[ → [0,n[,
une bijection est injective donc le
principe des tiroirs nous dit que m≤ n.
De même g ∘ f−1 est une application injective de
[0,n[ → [0,m[, et donc n ≤ m et donc
n=m.Montrons l’existence de n. Comme A est fini, il
existe une injection g de A → [0,m[.
On va montrer par
récurrence sur m que l’existence
d’une injection g de A → [0,m[ implique l’existence de n
≤ m et d’une bijection f de A → [0,n[.
-
Si m=0 alors A=∅ et g est une bijection.
- Supposons la propriété vraie pour une injection de
A → [0,m[ et montrons la pour une injection
g de A → [0,m+1[. Si g est
surjective, alors g est bijective et on a donc démontré le
résultat. Sinon, il existe k < m tel que
∀ x∈ A, g(x)≠k. On construit une injection
h de A → [0,m[ de la manière suivante :
Si g(x)<k alors h(x)=g(x), sinon
h(x)=g(x)−1. On montre comme dans le cas du lemme du tiroir
que h est injective et donc par hypothèse de récurrence, il
existe n≤ m et une bijection de A →
[0,n[.
□
La notion de finitude et de cardinal est préservée par la relation
pour deux ensembles d’être en bijection.
Proposition 3
Soient A et B deux ensembles tels qu’il existe une
bijection de A dans B. Si A est fini alors
B est fini et |A|=|B|.
Preuve:
La preuve est immédiate par composition de la bijection de A
dans [0,n[ et l’application réciproque de la bijection
de A dans B.
□
Proposition 4
-
Soit A un ensemble fini et B un sous-ensemble
de B alors B est fini et |B|≤ |A|.
- Soit A un ensemble fini non vide et x∈ A
alors |A∖{x }|=|A|−1.
En particulier, si B est un sous-ensemble de
A et si |A|=|B| alors A=B.
- Soient A et B deux ensembles finis, l’ensemble
A× B est fini et |A× B| = |A|
× |B|.
Preuve:
-
En composant les bijections, on obtient une injection de
[0,|B|[ → [0,|A|[ et le lemme du
tiroir nous permet de conclure que |B|≤ |A|.
- A partir de la bijection f de A→ [0,n[
on en construit une (A∖{x })→ [0,n−1[
en décalant les valeurs supérieures à f(x).
- Soient f∈ A → [0,n[ et b∈ B →
[0,m[. On construit h∈ A× B →
[0,n× m[ par h(x,y)= n× g(y) +
f(x). Les propriétés de la division euclidienne nous permettent
de montrer que c’est une bijection.
□
Exercice 7
Soient A et B deux ensembles finis tels que
|A|=|B| et f∈ A → B. Montrer que les 2
propriétés suivantes sont équivalentes:
-
f est injective
- f est bijective
Preuve:
On suppose que f est injective donc f est bijective de
A dans Img(f) donc
|B|=|A|=|Img(f)| et Img(f)
⊆ B donc Img(f)=B et donc f est
surjective et donc f est
bijective.
□
Exercice 8
Soit A un ensemble de cardinal n et B un ensemble de cardinal m
-
Le cardinal de A× B est : n× m
- Le cardinal de A→ B est : mn
- Le cardinal de ℘(A) est : 2n
- Le cardinal de l’ensemble des suites de longueur k d’éléments de A est : nk
- Il y a des fonctions injectives de A dans B si et seulement si : n≤ m
- Il y a des fonctions surjectives de A dans B si et seulement si : m≤ n
- Il y a des fonctions bijectives de A dans B si et seulement si : n=m
Exercice 9
Jean a élaboré une fonction z de compression de données qui permet de traiter des suites finies de 0 et de 1.
-
Quelle propriété doit avoir cette fonction pour que l’on puisse décompresser les données.
- Jean affirme a son acheteur que sa fonction a de très bonnes performances et renvoie toujours une suite de longueur plus petite.
-
est-ce possible ?
- la fonction de Jean est-elle vraiment efficace ?
2.5 Ensemble dénombrable
Définition 11 (Ensemble dénombrable)
L’ensemble A est dénombrable s’il existe une bijection de
A → ℕ.
Si un ensemble est dénombrable, alors il est possible d’énumérer ses
éléments, c’est-à-dire de construire une suite (un)n∈
ℕ qui parcourt l’ensemble des éléments de A en passant
exactement une fois par chaque élément. Il suffit d’utiliser
l’application réciproque d’une bijection de A→ ℕ.
Proposition 5
Un ensemble A est dénombrable si et seulement si il existe un
ensemble B dénombrable et une application bijective dans
A→ B.
Proposition 6
-
Un ensemble fini n’est pas dénombrable.
- ℕ est dénombrable.
- ℕ × ℕ est dénombrable.
Preuve:
-
Par le lemme des tiroirs, on a montré qu’il ne peut y avoir de bijection de [0,n[ dans ℕ.
- Il suffit de prendre la fonction identité.
- On fait une énumération diagonale :
| | 0 | 1 | 2 | 3 | 4 | … |
0 | 0 | 2 | 5 | 9 | | |
1 | 1 | 4 | 8 | | | |
2 | 3 | 7 | | | | |
3 | 6 | | | | | |
4 | | | | | | |
|
Le couple x,y est sur la diagonale d’indice x+y+1.
Son numéro est donc (Σi=0x+y i) +
x=(x+y)(x+y+1)/2+x. La fonction
f(x,y)= (x+y)(x+y+1)/2+x est une bijection de
ℕ × ℕ dans N.
En effet soit n∈ ℕ, il existe un unique p∈ ℕ
tel que Σi=0p i ≤ n <
Σi=0p+1 i =Σi=0p i +p+1. On pose
x=n−Σi=0p i. On a x < p+1, soit
y=p−x, on vérifie que f(x,y)=n.
□
Proposition 7
L’ensemble ℘(ℕ) des parties de ℕ n’est pas
dénombrable.
Preuve:
La preuve utilise l’argument de la diagonale de Cantor.
On suppose qu’il existe une application bijective f:℘(ℕ)→
ℕ et donc une application réciproque g:ℕ →
℘(ℕ) qui permet d’énumérer tous les ensembles de
℘(ℕ). On va construire un nouvel ensemble d’entiers
qui ne pourra être aucun de ceux-là.
On définit A =def {k ∈ ℕ | k ∉g(k)} et on pose
n =def f(A).
On a alors n ∈ A ⇔ n ∉g(n)⇔ n ∉g(f(A))⇔ n ∉A |
d’où une contradiction.
□
Dans le cas des ensembles finis, un sous-ensemble strict
d’un ensemble fini a un cardinal plus petit. Cela n’est pas le cas des
ensembles infinis.
Par exemple l’ensemble A des nombres pairs est en bijection avec
l’ensemble des entiers. Il suffit de prendre l’application
correspondant à la division par 2.
Cette propriété caractérise les ensembles infinis.
Définition 12 (Ensemble infini)
Un ensemble A est infini s’il existe un sous-ensemble
B de A qui est différent de A et une
application injective de A → B.
Proposition 8
Tout sous-ensemble d’un ensemble dénombrable est fini ou
dénombrable.
Preuve:
Soit A un ensemble dénombrable et f une bijection dans
A → ℕ. Soit B un sous-ensemble de A et
f|B la restriction de f à B.
On regarde l’image de f|B. C’est un sous-ensemble
C de ℕ. Si cet ensemble est borné alors il existe
n tel que ∀ x ∈ B, f(b)<n et donc
f|B est une injection de B dans
[0,n[. et donc B est fini.
Dans le cas contraire, on sait que pour tout n∈ ℕ, il
existe x ∈ B tel que n ≤ f(x).
A chaque n on peut donc associer h(n)
le plus petit k∈ ℕ tel que f−1(k) ∈ B.
On peut alors énumérer les éléments de B par une fonction g.
On pose g(0)=f−1(h(0)) et g(x+1)=f−1(h(g(x)+1)).
Le fait que ces deux équations définissent bien une fonction sera
justifié plus tard.
□
Proposition 9
L’union dénombrable d’ensembles dénombrables est dénombrable.
Preuve:
On se donne un ensemble d’ensembles X. On suppose que cet
ensemble est dénombrable, c’est-à-dire que l’on peut énumérer les
éléments de X : X0,X1,…. De plus chaque
ensemble Xi est dénombrable, soit fi la bijection
associée.
A chaque élément x∈ ∪X on associe le couple
(i,fi(x)) avec i le plus petit entier tel que
x∈ Xi. On vérifie que cette application est injective de
∪X dans ℕ× ℕ.
C’est donc une bijection de ∪X dans un sous-ensemble
de ℕ× ℕ. L’ensemble ∪X est donc fini
ou dénombrable. Comme cet ensemble contient X0 qui est infini
dénombrable, on en déduit que ∪X est dénombrable.
□
Exercice 10
-
Dire si les ensembles suivants sont dénombrables
-
ℕ×ℕ : dénombrable
- ℕ→ℕ : non dénombrable, contient ℕ→ {0;1} qui est isomorphe à ℘(ℕ)
- ℘(ℕ) : non dénombrable
- ℝ : non dénombrable
- L’ensemble des suites finies de {0;1} : dénombrable, union dénombrable d’ensembles finis
- L’ensemble des suites infinies de {0;1} : non dénombrable, isomorphe à ℘(ℕ)
- Existe-t-il une partie X de ℕ différente de
ℕ, telle que X est en bijection avec ℕ.
Ce document a été traduit de LATEX par HEVEA