61
(4) Cardinal d’un ensemble
(a) Définition
de l’ensemble A et noté card (A) ou ⋕A.
Soit A un ensemble, nous allons définir un nouvel objet mathématique appelé cardinal
Soit A un ensemble, alors tous les ensembles équipotents à A appartiennent à une même
classe d’équivalence qu’on appelle cardinal de A.
Ainsi, le cardinal d’un ensemble A est la classe d’équivalence de A par la relation
d’équipotence. C’est donc une collection de tous les ensembles qui sont équipotents à A. D’où
le cardinal d’un ensemble n’est pas un ensemble.
Remarque : Si E est un ensemble, alors card E = n existe et on l’appelle parfois nombre
cardinal.
(b) Conséquences de la définition d’un cardinal
i. Soient A et B deux ensembles, alors card (A) = card (B) si A et B sont équipotents, i.e.
il existe une bijection entre A et B.
ii. Le cas de l’ensemble vide.
L’ensemble vide est le seul et unique équipotent à ∅. Alors on pose traditionnellement que :
• Card (∅) = 0 nombre cardinal zéro
• ∀a, objet, l’ensemble {a} existe et card ({a}) = 1 nombre cardinal 1.
i.e. 1 est une collection de tous les ensembles singletons.
Par ailleurs, 0 ≠ 1 puisqu’ il n’existe aucune bijection entre ∅ et un ensemble singleton.
D’où card ({∅}) = card ({0}) = card ({a}) = 1. Etc.
Puisque 0 ≠ 1, alors {0, 1} est une paire et card ({0, 1}) = 2.
Signalons que les nombres cardinaux ne constituent pas un ensemble, mais cependant, on peut
envisager des ensembles de cardinaux. D’où au paragraphe suivant, nous identifieront
l’ensemble des entiers naturels à l’ensemble des cardinaux finis.
(c) Relations d’ordre définie entre les cardinaux
Soient A et B deux ensembles, nous pouvons nous trouver devant les situations
suivantes :
• Soit que A et B sont équipotents
• Soit que l’un est équipotent à une partie de l’autre
Soit A cet ensemble qui est équipotent à une partie de B, cela signifie qu’il existe une
injection entre A et B.
Algèbre Linéaire – Nkumbi Mwamba
Print by Maison FAKAM, contact : 0994907833, 0853366628,
[email protected] 62
(i) Définition
Soient x et y deux cardinaux tels qu’il existe des ensembles X et Y avec x = card (X)
On dit que x ≤ y (lire x est inférieur ou égal à y) i.e. card (X) ≤ card (Y).
et y = card (Y).
S’il existe une injection entre X et Y, montrons que la relation « ≤ » est une relation d’ordre :
i. ∀ x, cardinal, on a x ≤ x, car il existe 1x : X → X qui est injective [x = card X ] et
« ≤ » est réflexive.
ii. ∀ A, B deux ensembles tels que card A ≤ card B et card B ≤ card A, alors card A =
card B.
card A ≤ card B ⇒ ∃ f : A → B injective et
En effet :
card B ≤ card A ⇒ ∃ g : B → A injective.
Puisque f : A → B et g : B → A sont injectives, alors f : A → B est bijective. Donc A et B sont
équipotents i. e. card A = card B et « ≤ » est antisymétrique.
D’où le théorème ci – dessous dit :
∀ x, y deux cardinaux, si x ≤ y et y ≤ x, alors x = y.
Théorème de CANTOR – BERNSTEIN
Si card (A) ≤ card B et card B ≤ card C, alors card A ≤ card C.
iii. ∀ A, B, C trois ensembles,
card A ≤ card B ⇒ ∃ f : A → B injective
En effet :
card B ≤ card A ⇒ ∃ g : B → A injective.
et
(f : A → B et g : B → C injectives ) ⇒ g ∘ f : A → C injective par suite card (A) ≤ card (C) et
« ≤ » est transitive.
D’où (i), (ii) et (iii) ⇒ la relation « ≤ » est d’ordre.
Cette relation « ≤ » est d’ordre total d’après le théorème de ZERMELO ci – dessous qu’on
doit admettre.
∀ x, y deux cardinaux, l’une des propositions suivantes : x ≤ y ou y ≤ x est vrai.
Théorème de ZERMELO
(ii) Remarques
Si A’ ⊂ A, alors card A’ ≤ A car il existe une injection canonique f : A’ → A, qui à x
Soient A et A’ deux ensembles,
i.
ii. Si A’ ⊂ A avec A’ ≠ A.
associe x.
Alors (card A’ ≤ card A et card A’ ≠ card A) se note card A’ < card A et le signe
« < » se lit « est inférieur à ».
D’où x < y ⇔ x ≤ y et x ≠ y.
Remarquer que 0 ≤ 1 car ∅ ⊂ {0}.
Algèbre Linéaire – Nkumbi Mwamba
Print by Maison FAKAM, contact : 0994907833, 0853366628,
[email protected] 63
(d) Etudes des opérations x et + dans la collection des
cardinaux
(i) Multiplication des cardinaux
(a) Préliminaire
Si A et A’, B et B’ sont des ensembles équipotents, alors A x B et A’ x B’ sont
équipotents, alors A x B et A’ x B’ sont équipotents.
A q A’ ⟹ ∃ f : A → A’
En effet,
x ⇝ f(x) bijective.
B q B’ ⟹ ∃ g : B → B’
et
y ⇝ g(y) bijective.
h : A x B → A’ x B’
Définissons l’application h de la manière suivante :
(x, y) ⇝ h(x, y) = (f(x), g(y)).
Puisque f et g sont bijectives, alors h l’est aussi et A x B est équipotent à A’ x B’. D’où la
définition suivante :
(b) Définition
x × y = card (A x B).
b1 Si x et y sont des cardinaux tels que x = card A et y = card B, alors par définition :
La loi x s’appelle multiplication et x × y ou x ∙ y est le produit de x et y.
b2 Propriétés.
N. B. : On sait que ∀ A, B ensembles, A x B ≠ B x A, mais l’application
1. La multiplication des cardinaux est associative et commutative.
f:AxB → BxA
(x, y) ⇝ (y, x) est bijective et A x B est équipotent à B x A.
2. Elle admet 1 pour élément neutre. i.e. ∀ x, cardinal : x . 1 = x.
g : A x {a} → A
En effet, soit un ensemble A tel que card A = x, si B = {a}, alors l’application
(x, a) ⇝ x est bijective.
Par conséquent, A x {a} q A et card (A x {a}) = card A, soit x ∙ 1 = x.
3. 0 est un élément absorbant pour la loi " × ". i.e. ∀ x, cardinal ; on a :
x ∙ 0 = 0, trivial car A × ∅, ∀ A ensemble.
4. ∀ x, y, deux cardinaux :
x. y =1⇒ x =1et y =1
x. y = 0 ⇒ x = 0 ou y = 0.
5. La multiplication est distributive par rapport à l’addition (exercice).
Algèbre Linéaire – Nkumbi Mwamba
Print by Maison FAKAM, contact : 0994907833, 0853366628,
[email protected] 64
(ii) L’addition des cardinaux
i. Soient A et A’, B et B’ des ensembles équipotents tels que A ∩ B = ∅. Alors A ∪ B est
(a) Préliminaire
équipotent à A’ ∪ B’.
En effet, soit f : A → A’ une bijection et g : B → B’ une bijection. Montrons que A ∪ B est
équipotent à A’ ∪ B’.
Puisque A ∩ B = ∅, alors définissons l’application h de la manière suivante :
h : A ∪ B → A’ ∪ B’
z ⇝ h(z) =
f (z)si z ∈ A
.
g(z)si z ∈ B
Comme A’ ∪ B’ = ∅, chaque élément de A ∪ B aura une image et une seule par h et
réciproquement, ce qui prouve que h est une bijection et on a : A ∪ B q A’ ∪ B’.
(A’) et y = card (B’) avec A’ ∪ B’ = ∅.
ii. Si x et y sont des cardinaux, alors il existe des ensembles A’ et B’ tels que x = card
En effet, si x et y sont tels que card (A) = x et card (B) = y alors il suffit de prendre A’ = A ×
{0} et B’ = B × {1} car, dans ce cas, card (A’ × {0}) = x et card (B × {1}) = 1
avec (A × {0}) ∩ (B × {1} = ∅.
D’où la définition suivante :
(b) Définition
et y = card (B), avec A ∩ B = ∅, alors par définition : x + y = card (A ∪ B) avec A ∩ B = ∅.
Si x et y sont deux cardinaux tels que x et y sont deux cardinaux tels que x = card (A)
La loi (+) s’appelle addition des cardinaux ; x + y est la somme de x et y.
b1 Propriétés.
1. L’addition des cardinaux est associative et commutative (exercice).
A ∪ ∅ = A, alors card (A ∪ ∅) = card (A), soit x + 0 = x.
2. Elle admet 0 pour élément neutre i.e. ∀ x, cardinal : x + 0 = x. Si x = card (A), comme
3. ∀ x, y deux cardinaux, x + y = 0 ⟹ x = 0 et y = 0. Ce qui est vrai car si x = card (A) et
y = card (B), alors A ∪ B = ∅ ⟺ A = ∅ est B = ∅.
Soit x et y deux cardinaux, alors x ≤ y ssi il existe un cardinal z tel que : x + z = y.
b2 Théorème
i. ⟹ Supposons que x ≤ y et soit A, B deux ensembles tels que x = card A et y = card
Preuve
B. x ≤ y ⟹ ∃ f : A → B injective. Comme f : A → f o (A) = B’ ⊂ B est bijective.
Il suffit de considérer z = ðBB ′ , alors z ∩ B’ = ∅ et z ∪ B’ = ∅ et z ∪ B’= B. En posant
i.e. card A = card B’.
z = card(Z), alors card (B), soit x + z = y.
⟸ Supposons qu’il existe un cardinal z tel que : x + z = y et soit A, B et Z des
ensembles tels que : card (A) = x, card (B) = y et card (Z) = z avec A ∩ Z = ∅ puisque
ii.
x + z = y, alors il existe une bijection entre A ∪ Z et B.
Algèbre Linéaire – Nkumbi Mwamba
Print by Maison FAKAM, contact : 0994907833, 0853366628,
[email protected] 65
Soit f : A ∪ Z → B cette bijection, alors la restriction de f à A est une injection de A vers
B.D’où x ≤ y.
NB : On sait que ∀ A, B, C des ensembles : A × (B ∪ C) = (A × B) ∪ (A × C)
Si B ∩ C = ∅ et (A × B) ∩ (A × C) = ∅, alors card [A × (B ∪C)] = card [(A × B) ∪ (A × C)].
Soit x ∙ (y + z) = xy + xz, sachant que x = card (A), y = card (B) et z = card (C).
(e) Cardinaux Finis (Entiers Naturels).
(i) Théorème
∀ x, y deux cardinaux, alors x + 1 = y + 1⇔ x = y.
• x = y, alors x + 1 = y + 1 (trivial).
• Soit x et y deux cardinaux tels que x + 1= y + 1.
éléments distincts i et j n’appartenant pas à A ∪ B.
Si A et B sont deux ensembles tels que : x = card (A) et y = card (B), considérons deux
Alors : x + 1 = card (A’) avec A ′ = A ∪ {i}
y + 1 = card (B’) avec B ′ = B ∪ {j}.
Puisque x + 1 = y + 1, il existe une bijection f de A’ vers B’.
Deux cas sont possibles :
• Si f(i) ≠ j, soit b = f(i) et a = f -1(j). Posons A ′′ = A - {a} et B′′ = B - {b}, alors
• Si f(i) = j, alors f/A est une bijection de A vers B. D’où x = y.
l’application h = f/ A ′′ est bijective de A ′′ vers B′′ .
• Si on prolonge h à A par h(a) = b, on obtient une bijection h de A vers B et x = y.
(ii) Cardinaux finis
Un cardinal n est fini ssi n ≠ n + 1.
(a) Définitions
• 0 est un cardinal fini car 0 ≠ 0 + 1 = 1
Exemples :
• 1 est un cardinal fini car 1 ≠ 1 + 1 = 2.
Un cardinal non fini est dit infini.
Un ensemble est dit fini ou infini suivant que son cardinal est fini ou infini.
Un cardinal fini est aussi appelé un nombre naturel.
Si A est un ensemble fini, alors card (A) est appelé nombre d’éléments de A.
Si A est un ensemble infini, alors card (A) est appelé nombre transfini.
(b) Axiome de l’infini
Les cardinaux finis constituent un ensemble. Cet ensemble est désigné par N, qu’on
Il est légitime d’écrire que : 0 ∈ ℕ, 1 ∈ ℕ.
appelle ensemble des cardinaux finis ou des nombres naturels.
NB : ℕ* = ℕ - {0}.
Algèbre Linéaire – Nkumbi Mwamba
Print by Maison FAKAM, contact : 0994907833, 0853366628,
[email protected] 66
(c) Ensemble infini des cardinaux finis
L’application f de ℕ dans ℕ définie par ∀ n ∈ ℕ, f(n) = n + 1 est bijective de ℕ dans ℕ*.
Propriétés
i.e. f : ℕ → ℕ*
n ⇝ n + 1 est bijective.
i. F est une application si ∀ n ∈ ℕ, n + 1 est un cardinal fini. Sachant que n est un
En effet, il faut montrer que f est une application bijective.
cardinal fini, alors n ≠ n + 1 entraîne n + 1 ≠ (n + 1) + 1 car par contraposée,
n + 1 =(n + 1) + 1 ⟹ n = n + 1
D’où n + 1 est un cardinal fini. De plus, n + 1≠ 0, puisque 1 ≠ 0.
Vrai d’après le théorème d.5.a).
ii. f est injective d’après le théorème d. 5. a).
Montrons que f est surjective ou ∀ n ∈ ℕ*, ∃ m ∈ ℕ : f(m) = n, i.e. m + 1 = n.
Soit n ∈ ℕ*, alors il existe A ≠ ∅, tel que n = card (A).
iii.
A ≠ ∅ ⟹ ∃ a ∈ A, alors en posant A ′ = A - {a}, on a : A = A ′ ∪ {a} et A ′ ∩ {a} = ∅, alors
card (A) = card ( A ′ ∪ {a}).
Dès lors il existe m tel que : n = m + 1. C’est m = card ( A ′ ). m est un cardinal fini :
si non m + 1 = n ne serait pas un cardinal fini.
Définition
Il faut noter que, ∀ n ∈ ℕ, n ≤ n + 1. Ainsi, dans ℕ :
Pour tout cardinal fini n, le cardinal fini n + 1 est appelé le successeur de n.
i. Tout élément n a un successeur unique.
ii. Deux éléments différents ont des successeurs différents.
iii. Zéro n’est le successeur d’aucun élément.
D’où ℕ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, …, }.
D’après ce qui précède, on a vu que ℕ* = ℕ − {0}.
Conséquence
Sachant que ℕ*∩ {0} = ∅, alors card (N) = card (ℕ* ∪ {0})
D’autre part, card (ℕ) = card (ℕ ) car il existe une bijection f de ℕ vers ℕ* associant n
= card (ℕ*) + 1 (i).
*
à n + 1. D’où (i) devient : card (ℕ) = card (ℕ) + 1.
Par suite card ℕ n’est pas un cardinal fini et ℕ est un ensemble infini. En désignant le cardinal
de ℕ par N o (lire aleph zéro), alors N o est un nombre transfini et on a : N o = N o + 1.
Conclusion
moins un ensemble de cardinal n tel que n = n + 1. Soit par exemple l’ensemble ℕ. D’où ℕ est
Cette conséquence prouve que la définition d’un cardinal fini a un sens, car il existe au
un ensemble infini et N o est un nombre transfini.
Algèbre Linéaire – Nkumbi Mwamba
Print by Maison FAKAM, contact : 0994907833, 0853366628,
[email protected] 67
L’ensemble ℕ est l’ensemble des nombres naturels. On va le munir de la loi ( + ), de la
b) L’ensemble N
loi ( x ) et de la relation d’ordre.
Les propriétés de ( + ) dans ℕ
• (+) est associative, commutative et admet 0 ∈ ℕ comme élément neutre.
(1)
• Soit x ′ ∈ ℕ*, ∃ x ∈ ℕ : x ′ + x = 0
• Tout élément de ℕ est régulier pour l’addition, c’est – à – dire :
∀ x, y, z ∈ ℕ, x + y = y + z ⟹ x = y.
(2) Les propriétés de (∙) dans ℕ
0 est un élément absorbant pour (∙) dans ℕ : c’est – à – dire : ∀ n ∈ ℕ : n ∙ 0 = 0
• (∙) est commutative, associative et admet 1 pour élément neutre.
∀ x, y, z ∈ ℕ* : x ∙ z = y ∙ z ⟹ x = z.
•
De plus, la loi ( ∙ ) est distributive par rapport à la loi ( + ) dans ℕ
•
•
a. ∀ a, b ∈ ℕ : a ≤ ⟺ ¡ ∈ ℕ ∶ ¢ = £ + ¤, ⟹ ¤ = ¢ − £ qu’on appelle
(3) (ℕ,≤) est un ensemble totalement ordonné
b. ∀ ⊂ ℕ £¥¦§ ¨ ≠ ∅, ∃© ∈ ¨; ∀ª ∈ ¨, on a k ≤ x, donc k est le plus petit
différence entre a et b.
élément de A et en particulier, 0 est le plus petit élément de ℕ.
c. ∀r, ∈ ℕ £¥¦§ £ ≤ ¢
[a, b] = {x ∈ ℕ ∶ £ ≤ ª ≤ ¢} alors a est le plus petit élément de [a, b] et b est
d. ∀ ∈ ℕ*, ∃ x′ = x + 1 qu’on appelle successeur de x.
le plus grand élément de [a, b].
e. ∀ ∈ ℕ*, ∃ x′ = x − 1 qu’on appelle prédécesseur de x.
f. «′osqot o ℕ est un ensemble infini d’éléments, c’est – à – dire ℕ n’a pas un
plus grand élément : car ∀ ∈ ℕ, ∃® ∈ ℕ ∶ ª ≤ ®.
Soit A ⊂ ℕ, (A ≠ 0) tel que :
(4) Théorème
i. Avec 0 ∈
ii. ∀ ∈ ∶ + 1 ∈
Alors : A = ℕ.
Supposons A ≠ ℕ c’est – à – dire ℕ ∖ A ≠ ∅ avec ℕ ∖ A ⊂ ℕ
Démonstration par absurde
D’après c.2., ∃l ∈ ℕ ∖ A tel que ∀x ∈ ℕ ∖ A, k ≤ x, k est le plus petit élément de ℕ ∖ A.
Puisque 0 ∈ A, alors 0 n’appartient pas à ℕ ∖ A ⟹ l ≠ 0. D’après c.5., k admet un
prédécesseur qui est k – 1.
k – 1 ∉ ℕ ∖ A car k − 1 < l op l q(±±'qé o ±(q ±opmp éétosp ¡o ℕ ∖ A,
Sûrement que :
⟹ k − 1 ∈ A.
D’ où finalement, on a : k – 1 ∉ ℕ ∖ A et k – 1 ∈ A, k ∉ A et k ∈ ℕ ∖ A .
Or k – 1 ∈ A et k ∉ A.
Algèbre Linéaire – Nkumbi Mwamba
Print by Maison FAKAM, contact : 0994907833, 0853366628,
[email protected] 68
⇓ Hypothèse.
k – 1 + 1 ∈ A, donc k ∈ A.
On arrive ainsi à une contradiction car on a supposé que A ≠ ℕ.
Donc A ≠ ℕ est faux et A = ℕ est vrai.
(5) Ensemble finis
i. Définition :
Un ensemble A est dit fini ou qu’il contient n éléments c’est – à – dire card A = n s’il
existe une bijection entre A et [1, n] à n éléments.
Soit A l’ensemble des lettres de l’alphabet français, alors A est fini car ∃ f ∶ A →
ii. Exemple :
#1, 26$ bijective. ⟹ ⋕ A = 26.
∃ f ∶ V → #1, 6$. NB : [1, n]∈ ℕ.
Si V est l’ensemble des voyelles de l’alphabet français, alors V à six élément, car :
Si f : A → B est injective alors card A ≤ card B
Soient A et B deux ensembles finis.
f : A → B est surjective alors card A ≥ card B
f : A→ B est bijective alors card A = card B
2. Analyse Combinatoire
a) Nombre d’application d’ensemble fini vers un
ensemble fini
(1) Théorème :
Soit A et B deux ensembles finis ayant respectivement p et n éléments. i.e. card A = p
Alors le nombre d’application de A vers B est np, (p, n ∈ ℕ*). Ce qu’on écrit : card (BA) = np.
et card B = n.
Ainsi tout élément h ∈ BA s’appelle Arrangement avec répétition de p élément pris dans un
ensemble à n éléments.
Démonstration par récurrence sur p
Soit A = {a1, a2, …, ap} et B = {b1, b2, …, bn}, ces deux ensembles.
• Si p = 1, i.e. card A = 1, alors A = {a1} et le nombre d’applications de A vers B est n.
Ce qu’on écrit : card (BA) = n1 = n (vraie).
Algèbre Linéaire – Nkumbi Mwamba
Print by Maison FAKAM, contact : 0994907833, 0853366628,
[email protected]
