Téorie des ensembles

Exercice1
1) Soient A,B et C des propositions, montrer les équivalences suivantes :
(i) A ou B et C  A ou B et A ou C
(ii) A et B ou C  A et B ou A et C
2) Soient X,Y et Z trois ensembles, montrer les égalités suivantes :
(i) X ∩ Y  Z  X ∩ Y  X ∩ Z
(ii) X  Y ∩ Z  X  Y ∩ X  Z
Exercice2
Soient E un ensemble et A, B, C des parties de E.
Montrer que : A\B  A ∩ B c  A\A ∩ B ;A ∩ B c  A c  B c ; A  B c  A c ∩ B c ;
A ∩ B\C  A\C ∩ B\C ; A  B\C  A\C  B\C ; A\B ∩ C  A\B  A\C ;
A\B  C  A\B ∩ A\C.
Exercice3
Soient E et F deux parties d’un ensemble A tels que : E ∩ F ≠ ∅ ; E ∩ F ≠ E ; E ∩ F ≠ F ; E  F ≠ A.
Montrer que E ∩ F, E\E ∩ F, F\E ∩ F, C A E  F est une partition de A.
Exercice4
Soient A et B deux propositions, on appelle disjonction exclusive des propositions A et B, une
proposition notée (A ou bien B) qui n’est vraie que si l’une et l’une seulement entre les propositions A et B
est vraie. on a en particulier : (A ou bien B)  (B ou bien A)
Montrer que si A,B, et C sont des propositions, alors :
(i) [A et (B ou bien C)]  [(A et B) ou bien (A et C)]
(ii) [A ou bien (B ou bien C)]  [(A ou bien B) ou bien C]
1) Soient X,Y et Z trois ensembles.
a) Montrer que XY  x ∈ X  Y tq x ∈ X ou bien x ∈ Y
b) Montrer que XY  X  Y \ X ∩ Y.
2) Montrer que : X ∩ YZ  X ∩ YX ∩ Z et XY ∩ Z  X ∩ ZY ∩ Z et
XΔYΔZ  XΔYΔZ.
3) Á t’on X  YZ  X  YX  Z ? XY  Z  X  ZY  Z ?
Exercice5
Soient A et B deux parties d’un ensemble E, resoudre dans PE les équations :
A ∩ X  B et A  X  B et AΔX  B.
Exercice6
Soient E un ensemble, et f, g : E  R deux applications; on note f  g l’application f  g : E  R
définie par : ∀x ∈ E f  gx  fx  gx; de même on note f. g l’application f. g : E  R définie
par : ∀x ∈ E f. gx  fx. gx.
Si X est une partie de E, on note i X l’application i X : E  R définie par :
∀x ∈ X i X x  1 et ∀x ∈ E\X i X x  0.
L’application i X s’appelle fonction indicatrice de la partie X de E.
Soient X et Y deux parties de E.
1) Montrer que : (i) i X∩Y  i X . i Y
(ii) i XY  i X  i Y − i X . i Y
(iii) i E\X  1 − i X
(iv) i X\Y  i X − i X . i Y
(v) i XY  i X − 2i X . i Y  i Y
2) Montrer que X  Y  i X  i Y .
3) Retrouver les resultats de l’exercice 1-2) et de l’exercice 3-2).
Exercice7
Soient E un ensemble et I un ensemble non vide, soient A une partie de E et A i  i∈I une famille de
parties de E, on note  A i la partie de E donnée par :
i∈I
 A i  x ∈ E tq ∃i ∈ I x ∈ A i  ; et on note  A i la partie de E donnée par :  A i  x ∈ E tq
i∈I i∈I i∈I
∀i ∈ I x ∈ A i  ; montrer que :
a) A ∩  Ai  A ∩ A i  et A   Ai  A  A i 
i∈I i∈I i∈I i∈I

b) A\  A i  A\A i  et A\  A i  A\A i 
i∈I c i∈I i∈I c i∈I

c)  Ai  A ci et  Ai   A ci
i∈I i∈I i∈I i∈I

d)  A i \A  A i \A et  A i \A  A i \A
i∈I i∈I i∈I i∈I
Exercice8
Soient E un ensemble et A, B deux parties de E.
1) Montrer les équivalences suivantes :
A ⊂ B  A ∩ B  A  A  B  B  A ∩ B c  ∅.
2) Soit f : PE → PE l’application définie par : fX  A ∩ X  B ∩ X c .
a) Montrer que l’équation fX  ∅ admet des solutions sur PE si et seulement si A ∩ B  ∅.
b) On suppose que A ∩ B  ∅, et soit X ∈ PE. Montrer que fX  ∅ si et seulement si
X  A c ∩ Y  B ∩ Y c  pour un certain Y ∈ PE.
Exercice9
Soit f : N → N une application telle que : ∀n ∈ N ffn  fn  1.
1) Soient p ∈ N et D p  n ∈ N tq n ≥ p
Montrer par récurrence sur p ∈ N que fD p  ⊂ D p .
2) Montrer que f est strictement croissante.
3) En déduire que f est l’identité de N.
Exercice10
Soient f : E  F ; g : F  G ; et h : G  H des applications.
1) Montrer que h ∘ g ∘ f  h ∘ g ∘ f.
2) Montrer que si g ∘ f et h ∘ g sont bijectives alors f,g et h sont bijectives.
Exercice11
Soient f : E  F et g : F  G deux applications.
1) Montrer que si g ∘ f est injective et f est surjective alors g est injective.
2) Montrer que si g ∘ f est surjective et g est injective alors f est surjective.
Exercice12
Soient A et B deux parties non vides d’un ensemble E et f : PE → PA  PB l’application définie
par : fX  A ∩ X, B ∩ X.
Donner une C. N. S pour que f soit injective ; (resp surjective ; bijective) ?
Expliciter f −1 dans le cas où f est bijective.
Exercice13
Soit E un ensemble non vide et f : E  PE une application; montrer que f ne peut pas être surjective.
(Considérer X  a ∈ E tq a ∉ fa et faire un raisonnement par l’absurde).
Exercice14
Soient E un ensemble et f : PE → R  une application vérifiant :
∀A, B ∈ PE A ∩ B  ∅  fA  B  fA  fB
a) Montrer que f∅  0.
b) Soient X, Y ∈ PE, montrer que fX  Y  fX  fY − fX ∩ Y.
c) Soient X, Y, Z ∈ PE, calculer fX  Y  Z.
Exercice15
Soient E un ensemble et A une partie de E, soient les applications :
 A : PE  PE définie par : ∀X ∈ PE  A X  A ∩ X
 A : PE  PE définie par : ∀X ∈ PE  A X  A  X
a) Montrer que les conditions suivantes sont équivalentes :
(i)  A est injective
(ii)  A est surjective
 (iii)  A bijective
(iv) A  E
b) Montrer que les conditions suivantes sont équivalentes :
(i)  A est injective
(ii)  A est surjective
(iii)  A bijective
(iv) A  ∅
(Pour b) faire deux methodes, l’une directe et l’une utilisant a)).
Exercice16
Soient E un ensemble, R et S deux relations d’ordre total dans E, telles que :
∀x, y ∈ E 2 xRy  xSy
Montrer que ∀x, y ∈ E xRy  xSy
Exercice17
On munit C de la relation binaire R définie par : ∀z, z ′ ∈ C z R z ′  z − z ′ ∈ R.
1) Montrer que R est une relation d’équivalence.
2) Pour z ∈ C, quelle est la classe d’équivalence de z ?
3) Quel est l’ensemble quotient de R ?
Exercice18
Soient A, ≤ un ensemble ordonné et E  PA\∅; on définit sur E la relation binaire R par :
∀X, Y ∈ E X R Y  ∀x ∈ X ∀y ∈ Y x ≤ y ou X  Y
Montrer que R est une relation d’ordre sur E.
Exercice19
On munit R 2 des relations binaires R et S définies par :
(i) ∀x, y; x ′ , y ′  ∈ R 2 x, y R x ′ , y ′   x ≤ x ′ et y ≤ y ′
(ii) ∀x, y; x ′ , y ′  ∈ R 2 x, y S x ′ , y ′   x  x ′ ou x  x′ et y ≤ y ′ 
1) Montrer que R et S sont des relations d’ordre.
2) Laquelle entre R et S est totale ?
Exercice20
Soient E un ensemble non vide fini et R une relation d’équivalence sur E, soit G le graphe de R. Montrer
que cardE 2 ≤ cardE/R. cardG.
Étudier la cas d’égalité.
Exercice21
Soit E un ensemble muni d’une loi de composition interne notée multiplicativement, associative, et telle
que pour tout a ∈ E, l’application  a : E  E définie par : ∀x ∈ E  a x  a. x, soit injective.
a) Montrer que si u ∈ E est idempotent (c.à.d u 2  u), alors ( ∀x ∈ E u. x  x )
b) Montrer que si u et v sont deux idempotents de E distincts, alors il n’existe aucun couple x, y ∈ E 2
tel que x. u  y. v.
c) Montrer que si E admet un neutre e, alors E n’admet que e comme idempotent.
Exercice22
Montrer par récurrence sur n ∈ N ∗ que :
nn1
S n  1  2 . . . n  2
nn12n1
T n  1 2  2 2 . . . n 2  6
n 2 n1 2
U n  1 3  2 3 . . . n 3  4
nn12n13n 2 3n−1
V n  1  2 . . . n 
4 4 4
30
Exercice23
Soient n ∈ N ∗ et E un ensemble à n éléments; quel est le nombre des couples X, Y ∈ PE  PE tels
que X ⊂ Y ?
Exercice24
Soit f : N  N une application strictement croissante c.à.d ∀m, n ∈ N n  m  fn  fm ;
montrer que ∀n ∈ N fn ≥ n.
Exercice25
Soient n et p deux entiers naturels tels que p ≤ n.
 n
Montrer que ∑ C k  C n1 . (Faire un raisonnement par récurrence)
p p1

kp
Exercice26
Soient E,F et G des ensembles finis, montrer que
cardE  F  G  cardE  cardF  cardG  cardE ∩ F ∩ G
− cardE ∩ F − cardF ∩ G − cardG ∩ E