Eléments de logique

Exercice 1 Décrire les parties de
dans lesquelles évoluent x pour que les assertions suivantes soient
vraies :
a) (x > 0 et x < 1) ou x = 0 b) x > 3 et x < 5 et x ≠ 4
c) (x ≤ 0 et x > 1) ou x = 4 d) x ≥ 0 ⇒ x ≥ 2 .

a) [ 0,1[ b) ]3, 4[ ∪ ]4,5[ c) {4} d) ]−∞,0[ ∪ [ 2, +∞[ .

Exercice 2 Etant donnés P , Q et R trois assertions, vérifier en dressant la table de vérité :

a) P ou (Q et R ) ∼ (P ou Q ) et (P ou R )
b) non(P ⇒ Q ) ∼ P et non(Q ) .

P v v v v f f f f
Q v v f f v v f f
a) Dans les deux cas on obtient la table
R v f v f v f v f
v v v v v f f f

P v v f f
b) Dans les deux cas on obtient la table Q v f v f
f v f f

Exercice 3 On dispose de neuf billes visuellement identiques, huit d’entre elles ont même masse mais la
neuvième est plus lourde. Comment, en deux pesées sur une balance à deux plateaux, peut-on
démasquer l’intrus ?
On compare deux paquets de trois billes.
Si l’un est plus lourd que l’autre, c’est qu’il contient l’intrus.
Sinon, l’intrus est parmi les trois billes restantes.
Ainsi, on sait dans quel paquet de trois billes se situe l’intrus.
Dans ce celui-ci, on compare deux billes.
Si l’une est plus lourde que l’autre, c’est l’intrus.
Sinon, l’intrus est la troisième.

Exercice 4 On dispose de neuf billes visuellement identiques, elles ont toutes la même masse sauf une.
Comment, à l’aide d’une balance à deux plateaux, démasquer l’intrus en trois pesées ?
Notons 1,2,3,4,5,6,7,8,9 nos billes.
On commence par comparer 2 lots constituées de 1,2,3 et de 4,5,6.
Si ceux-ci ont même masse alors l’intrus se trouve dans 7,8,9.
On compare alors 1 et 7 puis 1 et 8 pour démasquer l’intrus.
Si les deux premiers lots n’ont pas même masse, l’intrus ci trouve.
La bille 9 servira alors de bille témoin.
Pour fixer les idées (et sans perte de généralités), supposons que le premier lot est plus lourd que le second.
Comparons maintenant les billes 1 et 4 avec les billes 2 et 5.
Si celles-ci ont même masse commune, l’intrus se trouve dans les deux autres billes 3 et 6. Une comparaison de
3 avec 9 permet alors de savoir qui est l’intrus de 3 ou de 6.
Si celles-ci n’ont pas même masse commune, pour fixer les idées (et sans perte de généralités), supposons que 1
et 4 soient plus lourdes que 2 et 5.
Si l’intrus est plus lourd que ses congénères alors cela ne peut ni être 4 ni être 2 à cause respectivement des
première et deuxième pesées.
Si l’intrus est plus léger que ses congénères alors cela ne peut ni être 2 ni être 4 à cause respectivement des
première et deuxième pesées.
Dans tous les cas l’intrus est soit 1, soit 5.
Une comparaison de 1 avec 9 permet alors de démasquer l’intrus.
 Quantificateurs

Exercice 5 Soit I un intervalle de
et f : I →
une fonction définie sur I à valeurs réelles.

Exprimer verbalement la signification des assertions suivantes :
a) ∃C ∈
, ∀x ∈ I , f (x ) = C
b) ∀x ∈ I , f (x ) = 0 ⇒ x = 0
c) ∀y ∈
, ∃x ∈ I , f (x ) = y
d) ∀x , y ∈ I , x ≤ y ⇒ f (x ) ≤ f (y )
e) ∀x , y ∈ I , f (x ) = f (y ) ⇒ x = y .

a) la fonction f est constante

b) la fonction f ne peut s’annuler qu’en 0 (mais n’y est pas forcée de s’y annuler)
c) la fonction f prend toute valeur réelle
d) la fonction f est croissante
e) la fonction f ne prend jamais deux fois la même valeur

Exercice 6 Soit I un intervalle de
et f : I →
une fonction définie sur I à valeurs réelles.

Exprimer à l’aide de quantificateurs les assertions suivantes :
a) « la fonction f s’annule »
b) « la fonction f est la fonction nulle »
c) « f n’est pas une fonction constante »
d) « f ne prend jamais deux fois la même valeur »
e) « la fonction f présente un minimum »
f) « f prend des valeurs arbitrairement grandes »
g) « f ne peut s’annuler qu’une seule fois ».

a) ∃x ∈ I , f (x ) = 0
b) ∀x ∈ I , f (x ) = 0
c) ∃x , y ∈ I , f (x ) ≠ f (y )
d) ∀x , y ∈ I , x ≠ y ⇒ f (x ) ≠ f (y ) ou ∀x , y ∈ I , f (x ) = f (y ) ⇒ x = y
e) ∃a ∈ I , ∀x ∈ I , f (x ) ≥ f (a )
f) ∀M ∈
, ∃x ∈ I , f (x ) > M
g) ∀x , y ∈ I , f (x ) = 0 et f (y ) = 0 ⇒ x = y .

Exercice 7 Soit I un intervalle de
non vide et f : I →
une fonction à valeurs réelles définie sur I .
Exprimer les négations des assertions suivantes :
a) ∀x ∈ I , f (x ) ≠ 0
b) ∀y ∈
, ∃x ∈ I , f (x ) = y
c) ∃M ∈
, ∀x ∈ I , f (x ) ≤ M
d) ∀x , y ∈ I , x ≤ y ⇒ f (x ) ≤ f (y )
e) ∀x , y ∈ I , f (x ) = f (y ) ⇒ x = y
f) ∀x ∈ I , f (x ) > 0 ⇒ x ≤ 0 .

a) ∃x ∈ I , f (x ) = 0
b) ∃y ∈
, ∀x ∈ I , f (x ) ≠ y
c) ∀M ∈
, ∃x ∈ I , f (x ) > M
d) ∃x , y ∈ I , x ≤ y et f (x ) > f (y )
e) ∃x , y ∈ I , f (x ) = f (y ) et x ≠ y
f) ∃x ∈ I , f (x ) > 0 et x > 0 .
Exercice 8 Soit f :
→
. Quelle différence de sens ont les deux assertions proposées :
a) ∀x ∈
, ∃y ∈
, y = f (x ) et ∃y ∈
, ∀x ∈
, y = f (x ) .
b) ∀y ∈
, ∃x ∈
, y = f (x ) et ∃x ∈
, ∀y ∈
, y = f (x ) .
c) ∀x ∈
, ∃M ∈
, f (x ) ≤ M et ∃M ∈
, ∀x ∈
, f (x ) ≤ M ?

a) la première assertion est vérifiée par toute assertion, la seconde signifie f constante.
b) la première assertion signifie que f prend toute valeur dans
, la seconde est absurde.
c) la première est toujours vérifiée, la seconde signifie que f est majorée.

Exercice 9 Soit f :
→
une fonction continue. On considère les assertions suivantes :

P : « ∀x ∈
, f (x ) = 0 »,Q : « ∃x ∈
, f (x ) = 0 »
et R : « ( ∀x ∈
, f (x ) > 0) ou ( ∀x ∈
, f (x ) < 0) ».
Parmi les implications suivantes lesquelles sont exactes :
a) P ⇒ Q b) Q ⇒ P c) Q ⇒ R
d) non(R ) ⇒ Q e) non(Q ) ⇒ non(P ) f) non(P ) ⇒ non(R ) ?

a) d) e) sont les assertions exactes

Exercice 10 Soita ∈
.
a) Montrer que ( ∀ε ≥ 0, a ≤ ε) ⇒ a = 0 .
b) Montrer que ( ∀ε > 0, a ≤ ε) ⇒ a = 0 .

a) Supposons ∀ε ≥ 0, a ≤ ε . En particulier, pour ε = 0 , on a a ≤ 0 donc a = 0 .

b) Par contraposée, montrons : a ≠ 0 ⇒ ∃ε > 0, a > ε .
a
Supposons a ≠ 0 . Pour ε = on a ε > 0 et a > ε ce qui détermine un ε convenable.
2

Ensembles

Exercice 11 Soit E = {a ,b ,c } un ensemble. Peut-on écrire :

a)a ∈ E b)a ⊂ E c) {a } ⊂ E
d) ∅ ∈ E e) ∅ ⊂ E f) {∅} ⊂ E ?

On peut écrire : a), c), e).

Exercice 12 Un ensemble est dit décrit en compréhension lorsqu’il réunit les éléments d’un ensemble vérifiant
une propriété. Un ensemble est dit décrit en extension lorsqu’on cite ses éléments. Par exemple,
{n ∈  / ∃k ∈ , n = 2k } et {2k / k ∈ } sont des descriptions respectivement en compréhension et
en extension de l’ensemble des entiers pairs.
a) Décrire en compréhension et en extension l’ensemble {1,3,5,7,…} .
b) Décrire en compréhension et en extension l’ensemble {1,10,100,1000,…} .
c) Décrire en extension l’ensemble des nombres rationnels.
d) Décrire en en compréhension l’ensemble ]0,1] . Pensez-vous qu’il soit possible de décrire cet
ensemble en extension ?
e) Décrire en compréhension et en extension l’ensemble des valeurs prises par une
fonction f :
→
.
f) Décrire en compréhension l’ensemble des antécédents d’un réel y par une fonction f :
→
.

a) {1,3,5,7} = {n ∈  / ∃k ∈ , n = 2k + 1} = {2k + 1/ k ∈ } .
b) {1,10,100,1000,…} = {x ∈
/ ∃k ∈ , x = 10k } = {10k / k ∈ } .
c)  = {p q | p ∈ ,q ∈ ∗ } .
d) ]0,1] = {x ∈
/ 0 < x ≤ 1} .
e) {y ∈
/ ∃x ∈
, y = f (x )} = {f (x ) / x ∈
} .
f) {x ∈
/ f (x ) = y } .

Exercice 13 Décrire P (P ({a })) où a désigne un élément.

P ({a }) = {∅, {a }} et P (P ({a })) = {∅, {∅} , {{a }} , {∅, {a }}} .

Exercice 14 Soit A, B ,C ∈ P (E ) . Etablir A \ (B ∩C ) = (A \ B ) ∪ (A \ C )

A \ (B ∩C ) = A ∩C E (B ∩C ) = (A ∩C E B ) ∪ (A ∩C EC ) = (A \ B ) ∪ (A \ C )

Exercice 15 Etant donné A et B deux parties de E , justifier C E A \ C E B = B \ A .

C E A \ C E B = C E A ∩C EC E B = B ∩C E A = B \ A .

Exercice 16 Etant données A , B et C trois parties de E , justifier les équivalences suivantes :

a) A ⊂ B ⇔ A ∪ B = B .
b) A = B ⇔ A ∩ B = A ∪ B .
c) A ∪ B = A ∩C ⇔ B ⊂ A ⊂C
A ∪ B = A ∪C
d)  ⇔ B =C
A ∩ B = A ∩C

a) (⇒) Supposons A ⊂ B . On a toujours B ⊂ A ∪ B .

Pour x ∈ A ∪ B . Que x ∈ A ou x ∈ B on a x ∈ B donc A ∪ B ⊂ B . Ainsi A ∪ B = B .
(⇐) Supposons A ∪ B = B . Puisque A ⊂ A ∪ B , on a A ⊂ B .
b) (⇒) Supposons A = B . On a A ∩ B = A = A ∪ B .
(⇐) Supposons A ∩ B = A ∪ B . On a A ⊂ A ∪ B ⊂ A ∩ B ⊂ B et de même B ⊂ A donc A = B .
c) (⇒) Supposons A ∪ B = A ∩C .
On a B ⊂ A ∪ B = A ∩C ⊂ A ⊂ A ∪ B = A ∩C ⊂ C .
(⇐) Supposons B ⊂ A ⊂ C . A ∪ B = A = A ∩C .
d) (⇒) Supposons A ∪ B = A ∪C et A ∩ B = A ∩C . Soit x ∈ B .
Si x ∈ A alors x ∈ A ∩ B = A ∩C donc x ∈ C .
Si x ∉ A alors B ⊂ f ( f −1 (B )) donc x ∈ A ∪C , or x ∉ A donc x ∈ C .
Dans les deux cas x ∈ C . Ainsi B ⊂ C et de manière symétrique C ⊂ B d’où l’égalité.
(⇐) Si B = C alors clairement A ∪ B = A ∪C et A ∩ B = A ∩C .

Exercice 17 Soit A et B deux parties de E , on appelle différence symétrique de A et B ,

l’ensemble : A ∆ B = (A \ B ) ∪ (B \ A) . Montrer que A∆B = (A ∪ B ) \ (A ∩ B ) .

Soit x ∈ E .
x ∈ A∆B ⇔ (x ∈ A et x ∉ B ) ou (x ∈ B et x ∉ A)
⇔ (x ∈ A ou x ∈ B ) et (x ∈ A ou x ∉ A) et (x ∉ B ou x ∈ B ) et (x ∉ B ou x ∉ A)
⇔ x ∈ A ∪ B et x ∉ A ∩ B ⇔ x ∈ (A ∪ B ) \ (A ∩ B )
d’où l’égalité des ensembles.

Exercice 18 Etant donnés A , B et C trois parties d’un ensemble E , montrer que :

a) A∆B = A∆C ⇔ B = C
b) A \ B = A ⇔ B \ A = B
c) A∆B = A ∩ B ⇒ A = B = ∅ .
a) Si A∆B = A∆C alors pour tout x ∈ B :
Si x ∈ A alors x ∉ A∆B et donc x ∉ A∆C et puisque x ∈ A , x ∈ C .
Si x ∉ A alors x ∈ A∆B et donc x ∈ A∆C et puisque x ∉ A , x ∈ C .
Dans les deux cas x ∈ C . Ainsi B ⊂ C et un raisonnement symétrique donne C ⊂ B puis l’égalité.
Réciproque immédiate.
b) A \ B = A ⇔ A ∩C E B = A ⇔ A ⊂ C E B or A ⊂ C E B ⇔ B ⊂ C E A et donc A \ B = A ⇔ B \ A = B .
c) A∆B = (A ∪ B ) \ (A ∩ B ) donc A∆B = A ∩ B ⇒ A ∩ B = ∅ = A ∪ B ⇒ A = B = ∅ .

Exercice 19 Soit A, B deux parties de E .

Discuter et résoudre l’équation A ∪ X = B d’inconnue X ∈ P (E ) .

Si A ⊄ B il est clair que l’équation n’a pas de solutions. S = ∅ .

Si A ⊂ B alors A ∪ X = B ⇒ X ⊂ B et A \ B ⊂ X . Inversement ok
Ainsi S = {X ∈℘ (E ) / A \ B ⊂ X ⊂ B }

Exercice 20 Soit A, B deux parties de E .

Discuter et résoudre l’équation A ∩ X = B d’inconnue X ∈ P (E ) .

Si B ⊄ A alors l’équation n’a pas de solution.

Si B ⊂ A . Soit X une solution de l’équation.
On a X = (A ∩ X ) ∪ (A ∩ X ) = B ∪C avecC = A ∩ X ⊂ A .
Inversement, pour X = B ∪C avecC ⊂ A , A ∩ X = (A ∩ B ) ∪ (A ∩C ) = B .
Ainsi S = {X = B ∪C /C ⊂ A} = {X ∈ P (E ) / B ⊂ X ⊂ B ∪ A} .

Injectivité, surjectivité et bijectivité

Exercice 21 Soit f :  →  et g :  →  les applications définies par :

k / 2 si k est pair
∀k ∈ , f (k ) = 2k et g (k ) =  .
(k −1) / 2 si k est impair

a) Etudier l’injectivité, la surjectivité et la bijectivité de f et g .
b) Préciser les applications g  f et f  g .
Etudier leur injectivité, surjectivité et bijectivité.

k 0 1 2 3 … k 0 1 2 3 …
a) et .
f (k ) 0 2 4 6 … g (k ) 0 0 1 1 …
f est injective car 2k = 2k ′ ⇒ k = k ′ mais non surjective car les nombres impairs ne sont pas des valeurs
prises.
g est surjective car 2y est un antécédent de y mais non injective car un nombre pair et l’impair qui le suit
prennent même valeur pas g .
k si k est pair
b) (g  f )(k ) = k donc g  f = Id  . ( f  g )(k ) =  .
k −1 sinon
g  f est bijective. f  g n’est ni injective, ni surjective.

Exercice 22 Soita , b et c trois réels tels que c ≠ 0 et a 2 + bc ≠ 0 .

ax + b
On considère la fonction f :
\ {a c } →
\ {a c } définie par f (x ) = .
cx −a
Justifier que f est bien définie.
Calculer f  f , en déduire que f est une permutation dont on déterminera l’application réciproque.
f est bien définie sur
\ {a c } car le dénominateur ne s’y annule pas.
a
f (x ) = ⇔ (ax + b )c = a (cx −a ) ⇔ a 2 + bc = 0 qui est exclu, donc f est à valeurs dans
\ {a c } .
c
( f  f )(x ) =  = x . Puisque f  f = Id
, f est une involution, c’est donc une permutation et f −1 = f .

n 2 si n est pair


Exercice 23 Soit f :  →  définie par f (n ) =  n + 1 .
− sinon
 2
Montrer que f est bien définie et bijective.

Soit n ∈  .
Si n est pair alors f (n ) = n 2 ∈ + et si n est impair alors f (n ) = − (n + 1) 2 ∈ −∗ .
Dans les deux cas f (n ) ∈  .
Soit n , n ′ ∈  . Supposons f (n ) = f (n ′) .
Compte tenu de la remarque précédente, n et n ′ ont nécessairement même parité.
Si n et n ′ sont pairs alors n 2 = n ′ 2 donc n = n ′ .
Si n et n ′ sont impairs alors − (n + 1) 2 = − (n ′ + 1) 2 donc n = n ′ .
Ainsi f est injective.
Soit m ∈  .
2m
Si m ≥ 0 alors pour n = 2m ∈  on a f (n ) = =m .
2
2m
Si m < 0 alors pour n = −2m −1 ∈  on a f (n ) = =m .
2
Ainsi f est surjective.
Finalement f est bijective.

Exercice 24 Soit f : E → F et g : F → G . Etablir les implications suivantes :

a) g  f injective ⇒ f injective.
b) g  f surjective ⇒ g surjective
c) g  f injective et f surjective ⇒ g injective.
d) g  f surjective et g injective ⇒ f surjective.

a) Supposons g  f injective.
Soit x , x ′ ∈ E . Si f (x ) = f (x ′) alors g ( f (x )) = g ( f (x ′)) . Or g  f injective, donc x = x ′ .
Ainsi f injective.
b) Supposons g  f surjective.
Soit z ∈ G . Il existe x ∈ E tel que z = g ( f (x )) . Pour y = f (x ) ∈ F , on a g (y ) = z . Ainsi g surjective.
c) Supposons g  f injective et f surjective.
Par a), on a f injective et donc f bijective. Introduisons f −1 .
g = (g  f )  f −1 est injective par composition d’applications injectives.
d) Supposons g  f surjective et g injective.
Par b), on a g surjective donc g bijective. Introduisons g −1 .
f = g −1  (g  f ) est surjective par composition d’applications surjectives.

Exercice 25 Soit E , F ,G trois ensembles, f : E → F , g : F → G et h :G → E

Etablir que si h  g  f est injective et que g  f  h et f  h  g sont surjectives alors f , g et h
sont bijectives.
Supposons h  g  f injective et g  f  h ainsi que f  h  g surjectives.
Puisque (h  g )  f est injective, on a f injective.
Puisque f  (h  g ) est surjective, on a f surjective.
Par suite f est bijective et on peut introduire f −1 .
Par composition h  g = (h  g  f )  f −1 est injective et par suite g est injective.
D’autre part g  f  h est surjective et donc g aussi. Finalement g est bijective.
Par composition h = (h  g )  g −1 est injective et h = f −1  ( f  h  g )  g −1 est surjective donc h est bijective.

Exercice 26 Soit E un ensemble et f : E → E telle que f  f  f = f .

Montrer que f est injective ssi f est surjective.

Supposons f injective.
Soit y ∈ E . On a f (( f  f )(y )) = f (y ) , or f est injective donc ( f  f )(y ) = y .
Pour x = f (y ) ∈ E on a f (x ) = f ( f (y )) = y . Finalement f est surjective.
Supposons f surjective.
Soit x , x ′ ∈ E tels que f (x ) = f (x ′) .
Puisque f est surjective, f  f l’est aussi et donc ∃a ,a ′ ∈ E tels que x = ( f  f )(a ) et x ′ = ( f  f )(a ′) .
La relation f (x ) = f (x ′) donne alors ( f  f  f )(a ′) = ( f  f  f )(a ′) d’où f (a ) = f (a ′)
puis x = f ( f (a )) = f ( f (a ′)) = x ′ . Finalement f est injective.

Exercice 27 Soit f : E → F et g : F → E deux applications telles que f  g  f soit bijective.

Montrer que f et g sont bijectives

Par l’exercice précédent, f  g  f bijective implique f injective et f surjective.

Ainsi f est bijective et on peut introduire f −1 .
g = f −1  ( f  g  f )  f −1 est bijective par composition d’applications bijectives.

Exercice 28 Soit E , F ,G trois ensembles, f1 , f2 : E → F et g : F → G .

On suppose g  f1 = g  f2 et g injective. Montrer que f1 = f2 .

∀x ∈ E on a (g  f1 )(x ) = (g  f2 )(x ) i.e. g ( f1 (x )) = g ( f2 (x )) donc f1 (x ) = f2 (x ) . Ainsi f1 = f2 .

Exercice 29 Soit E , F ,G trois ensembles, f : E → F et g1 , g 2 : F → G .

On suppose f surjective et g1  f = g 2  f . Montrer que g1 = g 2 .

∀y ∈ F , ∃x ∈ E tel que y = f (x ) et alors g1 (y ) = (g1  f )(x ) = (g 2  f )(x ) = g 2 (y ) donc g1 = g 2 .

Exercice 30 Soit f : E → I une application surjective, on pose, pour tout i ∈ I , Ai = f −1 ({i }) .

Montrer que les Ai sont non vides, deux à deux disjoints, de réunion égale à E .

Puisque f est surjective, les Ai sont non vides.

Si Ai ∩ Aj ≠ ∅ alors pour x ∈ Ai ∩ Aj on a f (x ) = i et f (x ) = j donc i = j .
Par contraposée : i ≠ j ⇒ Ai ∩ Aj = ∅ .
Soit x ∈ E et i = f (x ) . On a x ∈ Ai . Ainsi E ⊂ ∪ Ai puis l’égalité.
i ∈I

P (E ) → P (A)× P (B )
Exercice 31 Soit A et B deux parties d’un ensemble E et f :  . Montrer que :
X (X ∩ A, X ∩ B )

a) f est injective ssi A ∪ B = E
b) f est surjective ssi A ∩ B = ∅ .

a) Supposons f injective. f (E ) = (A, B ) = f (A ∪ B ) donc E = A ∪ B .

Supposons A ∪ B = E . Soit X ,Y ∈ P (E ) .
Si f (X ) = f (Y ) alors (X ∩ A, X ∩ B ) = (Y ∩ A,Y ∩ B )
donc X = X ∩ E = X ∩ (A ∪ B ) = (X ∩ A) ∪ (X ∩ B ) = (Y ∩ A) ∪ (Y ∩ B ) =Y ∩ (A ∪ B ) =Y ∩ E =Y .
Ainsi f est injective.
b) Supposons f surjective. L’élément (A, ∅) possède un antécédent X ∈ P (E ) .
On a A ∩ B = (X ∩ A) ∩ B = A ∩ (X ∩ B ) = A ∩ ∅ = ∅ .
Supposons A ∩ B = ∅ .
Soit (A′, B ′) ∈ P (A) × P (B ) . Pour X = A′ ∪ B ′ , on a f (X ) = ((A′ ∩ A) ∪ (B ′ ∩ A),(A′ ∩ B ) ∪ (B ′ ∩ B )) = (A′, B ′)
car A′ ∩ A = A′ , B ′ ∩ A = ∅ etc.

Image directe et image réciproque d’une partie

Exercice 32 Décrire l’image directe de
par la fonction exponentielle.

Déterminer l’image réciproque de l’intervalle [−1, 4] par la fonction f : x x 2 définie sur
.

exp(
) =
+∗ et f −1 ([1, 4]) = [−2, 2] .

Exercice 33 Soit f : E → F une application.

a) Montrer que : ∀A, A′ ∈ P (E ) , f (A ∪ A′) = f (A) ∪ f (A′) et f (A ∩ A′) ⊂ f (A) ∩ f (A′) .
b) Montrer que : ∀B , B ′ ∈ P (F ) , f −1 (B ∪ B ′) = f −1 (B ∪ B ′) et f −1 (B ∩ B ′) = f −1 (B ∩ B ′) .

a) Soit y ∈ f (A ∪ A′) . Il existe x ∈ A ∪ A′ tel que y = f (x ) .

Si x ∈ A alors y ∈ f (A) . Sinon, x ∈ A′ et y ∈ f (A′) . Dans les deux cas y ∈ f (A) ∪ f (A′) .
Inversement, soit y ∈ f (A) ∪ f (A′) . Si y ∈ f (A) alors il existe x ∈ A tel que y = f (x ) .
Or x ∈ A ⊂ A ∪ A′ donc y ∈ f (A ∪ A′) . De même si y ∈ f (A′) .
Par double inclusion, l’égalité.
Soit y ∈ f (A ∩ A′) . Il existe x ∈ A ∩ A′ tel que y = f (x ) .
Puisque x ∈ A ∩ A′ , on a x ∈ A donc y ∈ f (A) . De même y ∈ f (A′) donc y ∈ f (A) ∩ f (A′) .
b) Soit x ∈ E .
x ∈ f −1 (B ∪ B ′) ⇔ f (x ) ∈ B ∪ B ′ ⇔ f (x ) ∈ B ou f (x ) ∈ B ′
⇔ x ∈ f −1 (B ) ou x ∈ f −1 (B ′) ⇔ x ∈ f −1 (B ) ∪ f −1 (B ′)
D’où la première égalité. La seconde égalité s’établit par la même démonstration, en changeant union en
intersection et « et » en « ou ».

Exercice 34 Soit f : E → F une application.

Etablir : ∀A ∈ P (E ), A ⊂ f −1 ( f (A)) et ∀B ∈ P (F ), f ( f −1 (B )) ⊂ B .

Soit x ∈ A . On a f (x ) ∈ f (A) donc x ∈ f −1 ( f (A)) . Ainsi A ⊂ f −1 ( f (A)) .

Soit y ∈ f ( f −1 (B )) . Il existe x ∈ f −1 (B ) tel que y = f (x ) . Or, puisque x ∈ f −1 (B ) , on a f (x ) ∈ B i.e. y ∈ B .
Ainsi f ( f −1 (B )) ⊂ B .

Exercice 35 Soit E et F deux ensembles et f : E → F .

Montrer que f est injective ssi ∀A, A′ ∈℘ (E ), f (A ∩ A′) = f (A) ∩ f (A′) .

Supposons f injective.
Soit A, A′ ∈℘ (E ) . On sait déjà f (A ∩ A′) ⊂ f (A) ∩ f (A′) .
Soit y ∈ f (A) ∩ f (A′) . Il existe x ∈ A et x ′ ∈ A′ tel que y = f (x ) = f (x ′) .
Or f est injective donc x = x ′ ∈ A ∩ A′ puis y ∈ f (A ∩ A′) .
Inversement supposons ∀A, A′ ∈℘ (E ), f (A ∩ A′) = f (A) ∩ f (A′) .
Soit x , x ′ ∈ E . Supposons f (x ) = f (x ′) .
Pour A = {x } et A′ = {x ′} on a f (A ∩ A′) = f (A) ∩ f (A′) = {f (x )} ≠ ∅ donc A ∩ A′ ≠ ∅ puis x = x ′ .

Exercice 36 Soit f : E → F une application. Montrer que :

a) f est injective ⇔ ∀A ∈℘ (E ), A = f −1 ( f (A)) .
b) f est surjective ⇔ ∀B ∈℘ (F ), f ( f −1 (B )) = B .

a) (⇒) Supposons f injective. Soit A ∈ P (E ) .

On sait déjà que A ⊂ f −1 ( f (A)) .
Pour x ∈ f −1 ( f (A)) , on a f (x ) ∈ f (A) donc il existe x ′ ∈ A tel que f (x ) = f (x ′) .
Puisque f est injective, x = x ′ et donc x ∈ A . Ainsi f −1 ( f (A)) ⊂ A puis l’égalité.
(⇐) Supposons ∀A ∈ P (E ), A = f −1 ( f (A)) . Soit x , x ′ ∈ A .
Si f (x ) = f (x ′) . Considérons A = {x } . On a f (A) = {f (x )} donc x ′ ∈ f −1 ( f (A)) = A d’où x = x ′ .
Ainsi f injective.
b) (⇒) Supposons f surjective. Soit B ∈ P (F ) .
On sait déjà f ( f −1 (B )) ⊂ B .
Soit y ∈ B . Puisque f est surjective, il existe x ∈ E tel que f (x ) = y .
Puisque f (x ) ∈ B , on a x ∈ f −1 (B ) et donc y = f (x ) ∈ f ( f −1 (B )) . Ainsi B ⊂ f ( f −1 (B )) puis l’égalité.
(⇐) Supposons ∀B ∈ P (F ), f ( f −1 (B )) = B .
Soit y ∈ F . Pour B = {y } , on a f ( f −1 ({y })) = {y } donc f −1 ({y }) ≠ ∅ . Par suite f est surjective.

Exercice 37 Soit f : E → F une application. Montrer que :

f est bijective ssi ∀A ∈℘ (E ), f (C E A) = C F f (A) .

(⇒) Soit A ∈ P (E ) . Soit y ∈ f (C E A) , il existe x ∈ C E A tel que y = f (x ) .

Pour tout y ′ ∈ f (A) , il existe x ′ ∈ A tel que y ′ = f (x ′) , or x ′ ∈ A et x ∉ A donc x ≠ x ′ et f étant
injective y = f (x ) ≠ f (x ′) = y ′ . Par suite y ∈ C F f (A) . Ainsi f (C E A) ⊂ C F f (A) .
Inversement. Soit y ∈ C F f (A) , comme f est surjective, il existe x ∈ E tel que y = f (x ) .
Or y ∉ f (A) donc x ∉ A i.e. x ∈ C E A puis y = f (x ) ∈ f (C E A) . Ainsi C F f (A) ⊂ f (C E A) .
(⇐) Montrons que f est injective. Soit x , x ′ ∈ E .
Si x ≠ x ′ alors pour A = {x } on a x ′ ∈ C E A puis f (x ′) ∈ f (C E A) = C F f (A) = C F { f (x )} i.e. f (x ) ≠ f (x ′) .
Montrons que f est surjective.
Pour A = E on a Im f = f (E ) = C F (C F f (E )) = C F ( f (C E E )) = C F f (∅) = C F ∅ = F .
Finalement f est bijective.

Ensembles ordonnés

Exercice 38 On définit une relation binaire
sur
+∗ par : x
y ⇔ ∃n ∈ , y = x n .

Montrer que
est une relation d’ordre. Cet ordre est-il total ?

Soit x > 0 , on a x = x n pour n = 1 ∈  donc x
x . La relation
est réflexive.

Soit x , y > 0 , si x
y et y
x alors ∃n , m ∈  tels que y = x n et x = y m .
On a alors x = x nm donc ln x = nm ln x
Si x = 1 alors y = x n = 1 = x .
Si x ≠ 1 alors ln x ≠ 0 puis 1 = nm . Or n , m ∈  donc n = m = 1 puis x = y .
Finalement la relation
est antisymétrique.
Soit x , y , z > 0 . Si x
y et y
z alors ∃n , m ∈  tels que y = x n et z = y m .
On a z = x mn avec mn ∈  donc x
z . La relation
est transitive.
Finalement
est une relation d’ordre.

Exercice 39 Soit
la relation définie sur E = {(x , y ) ∈
2 / x ≤ y } par :

(x , y )
(x ′, y ′) ⇔ (x , y ) = (x ′, y ′) ou y ≤ x ′
Montrer que
est une relation d’ordre sur E .

est clairement réflexive et transitive.

Si (x , y )
(x ′, y ′) et (x ′, y ′)
(x , y ) alors (x , y ) = (x ′, y ′) ou x ≤ y ≤ x ′ ≤ y ′ ≤ x et
donc (x , y ) = (x , x ) = (x ′, y ′) .

Exercice 40 On définit une relation binaire
sur {z ∈ / Im(z ) ≥ 0} par : z
z ′ ⇔ z < z ′ ou z = z ′

et Re(z ) ≤ Re(z ′) . Montrer qu’il s’agit d’une relation d’ordre total.

est clairement réflexive.

Si z
z ′ et z ′
z alors nécessairement z = z ′ et Re(z ) = Re(z ′) donc z = z ′ car Im(z ), Im(z ′) ≥ 0 .
Si z
z ′ et z ′
z ′′ alors si z < z ′′ alors z
z ′′ et sinon z = z ′ = z ′′ et donc Re(z ) ≤ Re(z ′) ≤ Re(z ′′) ce
qui permet à nouveau d’affirmer z
z ′′ .

Exercice 41 Soit E l’ensemble des couples (I , f ) formé d’un intervalle I et d’une fonction réelle définie
sur I .
On définit une relation
sur E par : (I , f )
(J , g ) ⇔ I ⊂ J et g|I = f .
Montrer que
est une relation d’ordre sur E .

La relation est clairement symétrique.

Si (I , f )
(J , g ) et (J , g )
(I , f ) alors I ⊂ J , J ⊂ I et g|I = f donc I = J et f = g .
Si (I , f )
(J , g ) et (J , g )
(K , h ) alors I ⊂ J ⊂ K et h|I = (h|J )|I = g|I = f donc (I , f )
(K , h ) .
Finalement
est une relation d’ordre.

Exercice 42 Soit E un ensemble et f : E →
une application injective.

On définit sur E une relation binaire
par : x
y ⇔ f (x ) ≤ f (y ) .
Montrer que
est une relation d’ordre sur E .

Soit x ∈ E . On a f (x ) ≤ f (x ) donc x

x.
Soit x , y ∈ E . Si x
y et y
x alors f (x ) ≤ f (y ) et f (y ) ≤ f (x ) donc f (x ) = f (y ) . Or f est injective
donc x = y .
Soit x , y , z ∈ E . Si x
y et y
z alors f (x ) ≤ f (y ) et f (y ) ≤ f (z ) donc f (x ) ≤ f (z ) puis x
z
Finalement,
est une relation d’ordre.

Exercice 43 Soit A, B deux parties d’un ensemble E ordonné par
.

On suppose que A et B ont chacun un plus grand élément. Qu’en est-il de A ∪ B ? de A ∩ B ?

A ∪ B possède un plus grand élément : max(A ∪ B ) = max(max(A), max(B )) .

A ∩ B peut ne pas posséder de plus grand élément, cet ensemble peut notamment être vide.

Exercice 44 Soit (E ,
) un ensemble ordonné tel que toute partie non vide admet un plus petit élément et un
plus grand élément. Montrer que E est fini.
Par l’absurde supposons E infini.
Posons x 0 = min E , x1 = min E \ {x 0 } ,..., x n = min E \ {x 0 , x1 ,…, x n −1 } ,...
L’ensemble {x 0 ,…, x n ,…} n’a pas de plus grand élément. Absurde.
Exercice 45 Soit E un ensemble ordonné par une relation ≤ .
Un tableau à n lignes et p colonnes est formé d’éléments ai , j ∈ E avec 1 ≤ i ≤ n et1 ≤ j ≤ p .
On note le plus petit élément de chaque ligne et l’on prend le plus grand de ces plus
petits : max min ai , j .
1≤ j ≤p 1≤i ≤n

On note le plus grand élément de chaque ligne et l’on prend le plus petit de ces plus
grands : min max ai , j .
1≤i ≤n 1≤ j ≤p

Comparer ces deux nombres.

Notons k la ligne correspondant à la détermination de min max ai , j .
1≤i ≤n 1≤ j ≤p

Notons la colonne correspondant à la détermination de max min ai , j .

1≤ j ≤p 1≤i ≤n

On a min max ai , j = max ak , j ≥ ak , et max min ai , j = min ai , ≤ ak , donc min max ai , j ≤ max min ai , j .
1≤i ≤n 1≤ j ≤p 1≤ j ≤p 1≤ j ≤p 1≤i ≤n 1≤i ≤n 1≤i ≤n 1≤ j ≤p 1≤ j ≤p 1≤i ≤n

Les ensembles finis

Exercice 46 Soit E un ensemble fini, F un ensemble quelconque et f : E → F une application.

Montrer que : f est injective ssi Card( f (E )) = Card(E ) .

Si E = ∅ alors f (E ) = ∅ et l’égalité proposée est vraie.

Sinon, on peut écrire E = {x1 ,…, x n } avec des x i deux à deux distincts et n = Card E .
f (E ) = {f (x1 ),…, f (x n )} , or f est injective, les f (x i ) sont deux à deux distincts donc Card( f (E )) = n .

Exercice 47 Soit A , B et C trois parties d’un ensemble finie E . Exprimer Card(A ∪ B ∪C ) en fonctions des
cardinaux de A, B ,C , A ∩ B , B ∩C ,C ∩ A et A ∩ B ∩C .

Card(A ∪ B ∪C ) = Card A + Card B ∪C − Card(A ∩ B ) ∪ (A ∩C ) donc

Card(A ∪ B ∪C ) = Card A + Card B + CardC − Card B ∩C − Card A ∩ B − CardC ∩ A + Card A ∩ B ∩C

Exercice 48 Soit A et B deux parties de E et F .

Etant donnée une application f : E → F , est-il vrai que :
a) Si A est une partie finie de E alors f (A) est une partie finie de F .
b) Si f (A) est une partie finie de F alors A est une partie finie de E .
c) Si B est une partie finie de F alors f −1 (B ) est une partie finie de E .
d) Si f −1 (B ) est une partie finie de E alors B est une partie finie de F ?

a) oui, car si A = {x1 ,…, x n } alors f (A) = {f (x1 ),…, f (x n )} est fini.
b) non, il suffit de considérer une fonction constante définie sur un ensemble infini.
c) non, il suffit de considérer une fonction constante définie sur un ensemble infini.
d) oui, car B ⊂ f ( f −1 (B )) et f ( f −1 (B )) est fini.

Dénombrement

Exercice 49 Soit E et F deux ensembles finis de cardinaux respectifs n et p .

Combien y a-t-il d’injections de E dans F ?
Si n > p , il n’y a pas d’injections possibles.
Si n = 0 , il y a une injection : l’application vide.
Si 0 < n ≤ p alors on peut écrire E = {x1 ,…, x n } avec les x i deux à deux distincts.
Pour former une injection de E dans F :
On choisit f (x1 ) dans F : p choix.
On choisit f (x 2 ) dans F \ {f (x1 )} : p −1 choix.
...
On choisit f (x n ) dans F \ {f (x1 ),…, f (x n−1 )} : p − n + 1 choix.
p!
Au total, il y a p × (p −1) ×× (p − n + 1) = choix.
(p − n )!

Exercice 50 Soit E = {1,…, n } et F = {1,…, p } avec n ≤ p ∈  .

Combien y a-t-il d’applications strictement croissantes de E vers F ?
Une application f : E → F strictement croissante est entièrement déterminée par son image qui est une partie

()
formée de n éléments de F . Il y a p parties à n éléments dans F et donc autant d’applications strictement
n
croissantes de E vers F .

Exercice 51 Combien existe-t-il de relation d’ordre total sur un ensemble E à n éléments ?

Une relation d’ordre total sur E permet définit une bijection de {1,…,n } vers E et inversement.
Par suite il y a n ! relation d’ordre total possibles.

Exercice 52 On trace dans un plan n droites en position générale (i.e. deux d’entre elles ne sont jamais
parallèles ni trois d’entre elles concourantes). Combien forme-t-on ainsi de triangles ?
Notons tn le nombre de triangles formés.
t0 = t1 = t 2 = 0 et t3 = 1 .
n (n −1) n (n −1)
Pour tout n ≥ 3 , tn +1 = tn + car la nouvelle droite définit, en plus des précédents, nouveaux
2 2
triangles (correspondants au choix de deux droites parmi les précédentes).
n
k (k −1) 1 n 2 1 n n (n + 1)(2n + 1) n (n + 1) n (n + 1)(n −1)
Par suite tn +1 = ∑ = ∑k − ∑k = − = .
k =1 2 2 k =1 2 k =1 12 4 6

Exercice 53 Soit p ,q ∈  et n ∈ 0, p + q  . Proposer une démonstration par dénombrement de

n

( )
l’égalité p + q = ∑ p
n k =0
k n ( )( )
q .
− k

Soit E un ensemble à p + q éléments séparé en deux parties disjointes E ′ et E ′′ de cardinaux p etq .

( )
Il y a exactement p + q parties à n éléments dans E .
n
Or pour former une partie à n élément de E , on peut pour chaque k ∈ 0, n  commencer par choisir k éléments

dans E ′ avant d’en choisir n − k dans E ′′ . Il y a k q

p n −k ( )( )
possibilités pour chaque k ∈ 0, n  puis au total
n

∑ (kp )(n −q k ) possibilités d’où l’identité.

k =0

Exercice 54 Soit E et F deux ensembles finis non vides de cardinaux respectifs n et p .

On note Snp le nombre de surjections de E sur F .
a) Calculer S n1 , S nn et Snp pour p > n .
b) On suppose p ≤ n et on considère a un élément de E .
On observant qu’une surjection de E sur F réalise, ou ne réalise pas, une surjection de E \ {a }
sur F , établir Snp = p (Snp−−11 + Snp−1 ) .
p
c) En déduire que S np = ∑ (−1) p−k p k n .
k =0
k ()
a) Si F est un singleton, il n’y a qu’une application à valeurs dans F et celle-ci est surjective. Sn1 = 1 .
Si Card E = Card F < +∞ alors les surjections de E sur F sont aussi les bijections. Par suite Snn = n ! .
Si Card E < Card F , il n’existe pas de surjections de E sur F . Ainsi S np = 0 .
b) Une surjection de E sur F telle que sa restriction à E \ {a } soit surjective peut prendre n’importe quelle
valeurs ena . Il y en a pSnp−1 .
Une surjection de E sur F telle que sa restriction à E \ {a } ne soit pas surjective doit prendre en a la valeur
manquante. Il y a p possibilité pour choisir la valeur en a et Snp−−11 surjections de E \ {a } sur F \ {f (a )} . Au
total, il y en a pSnp−−11 .
Au final S np = p (Snp−−11 + S np−1 ) .
c) Montrons la propriété par récurrence sur n ∈ ∗ .
1
Pour n = 1 . p = 1 , S11 = 1 et ∑ (−1)1−k 1 k = 1 .
k =0
k ()
Supposons la propriété établie au rang n −1 ≥ 1 .
n
Pour p = 1 : S n1 = 1 et ∑ (−1)1−k n k = 1 .
k =0
k ()
Pour 1 ≤ p ≤ n :
p−1 p

k =0
( )
S np = p (Snp−−11 + S np−1 ) = p ∑ (−1) p−1−k p −1 k n−1 + p ∑ (−1) p−k p k n−1
k k =0
k ()
p p
= ∑ (−1) p−k p (p −1)k = ∑ (−1) (p )k
n −1 p−k n

k =0
k −1 k k =0
Récurrence établie.

Exercice 55 Pour n ∈ ∗ et p ∈  , on note Σnp le nombre de n uplets (x1 ,…, x n ) ∈ n tels

que x1 +  + x n = p .
a) Déterminer Σn0 , Σ1n , Σn2 , Σ1n et Σn2 .
b) Etablir ∀n ∈ ∗ , ∀p ∈  , Σnp +1 = Σn0 + Σ1n +  + Σnp .

c) En déduire que Σnp = n + p −1 .

p ( )
n (n −1) n (n + 1)
a) Σn0 = 1 , Σ1n = n , Σn2 = n + = , Σ1n = n et Σn2 = n + 1 .
2 2
b) Le nombre de n + 1 uplets (x1 ,..., x n , x n +1 ) ∈ n tels que x1 +  + x n +1 = p avec x n +1 = k ∈ 0, p  est Σnp−k .
Donc Σnp +1 = Σn0 + Σ1n +  + Σnp .

c) Par récurrence sur n ∈ ∗ , montrons ∀n ∈ ∗ , Σnp = n + p −1 .

p ( )
Pour n = 1 : ok
Supposons la propriété établie au rang n ≥ 1 :

( ) ()
∀p ∈ , Σnp +1 = Σn0 +  + Σnn = n −1 + n +  + n + p −1 = n + p
0 1 p p ( ) ( )
Récurrence établie.

Exercice 56 Soit E un ensemble à n éléments.

a) Soit X une partie à p éléments de E .
Combien y a-t-il de parties Y de E disjointes de X ?
b) Combien y a-t-il de couples (X ,Y ) formés de parties disjointes de E ?

a) Autant que de parties de E \ X : 2n−p

n

p =0
()
b) ∑ n 2n−p = (1 + 2)n = 3n .
p
Exercice 57 Soit E un ensemble à n éléments. Combien y a-t-il de parties X et Y de E telles que X ⊂Y ?

()
Pour k ∈ {0,…, n } , il y a n parties Y à un k éléments dans E .
k
Pour une telle partieY , il y a 2k parties X incluses dansY .
n

k =0
k()
Au total, il y a ∑ n 2k = (1 + 2)n = 3n couples (X ,Y ) ∈℘ (E ) 2 tels que X ⊂Y .

Exercice 58 Soit A une partie d’un ensemble E à n éléments. On pose p = Card A .

a) Combien y a-t-il de parties X de E contenant A ?
b) Combien y a-t-il de parties X de E à m ∈ {p ,…, n } éléments contenant A ?
c) Combien y a-t-il de couples (X ,Y ) de parties de E tels que X ∩Y = A ?

a) Autant que de parties de E \ A : 2n−p

b) Autant que de parties de E \ A à m − p éléments : n − p .
m −p ( )
c) Une fois X à m éléments contenant A déterminé il y a 2n−m choix de Y possibles et donc
n n −p

∑
m =p
(m − p )
n − p 2n−m =
∑
k =0
k ( )
n − p 2n−p−k = (1 + 2)n−p = 3n−p .

Exercice 59 Soit E un ensemble à n éléments. Calculer ∑ Card(X ) et ∑ Card(X ∩Y ) .

X ⊂E X ,Y ⊂E

()
Pour k ∈ {0,…, n } , il y a n parties X à un k éléments dans E .
k
n n
Par suite ∑ Card(X ) = ∑
X ⊂E k =0
∑
X ⊂E k =0
()
k = ∑ k n = n 2n−1 .
k
Card( X )=k

()
Pour k ∈ {0,…, n } , il y a n parties Z à k éléments dans E .
k
Pour une telle partie Z , les parties X contenant Z ont ∈ {k ,…, n } éléments.

−k( )
Il y a n − k parties X à éléments contenant Z .

Pour une telle partie X , une partie Y telle que X ∩Y = Z est une partie Y déterminée par Z ⊂Y ⊂ Z ∪C E X .
Il y a 2n− parties Y possibles.
n

=k
( )
Il y a ∑ n − k 2n− = (1 + 2)n−k = 3n−k parties (X ,Y ) tel que X ∩Y = Z .
−k
n n

∑
X ,Y ⊂E
Card(X ∩Y ) = ∑
k =0
∑ ∑
Z ⊂E X ,Y ⊂E k =0
k ()
Card(X ∩Y ) = ∑ k n 3n−k .
Card Z =k X ∩Y =Z
n

k =0
k ()
Or ((3 + x )n )′ = n (3 + x )n−1 = ∑ k n 3n−k x k −1 donc ∑ Card(X ∩Y ) = n 4n−1 .
X ,Y ⊂E

david Delaunay [Link]