Le cours

Résumé en cinq points

L'appartenance relie un élément à un ensemble, l'inclusion relie deux ensembles. Une égalité d'ensembles se prouve par double inclusion.
Union, intersection et complémentaire sont les traductions ensemblistes de « ou », « et » et « non », d'où la distributivité et les lois de De Morgan.
$\mathcal{P}(E)$ a $2^n$ éléments quand $E$ en a $n$ , et $\binom{n}{p}$ compte les parties à $p$ éléments.
Le produit cartésien est fait de couples, où l'ordre compte.
Injective signifie au plus un antécédent, surjective au moins un, bijective exactement un. La bijectivité dépend autant des ensembles choisis que de la formule.

Pourquoi ce chapitre

Ce chapitre fournit la langue commune de toute l'année.

Les probabilités parlent d'événements, qui sont des parties de l'univers, et les opérations sur les événements sont l'union, l'intersection et le complémentaire.
L'algèbre linéaire parle de sous-espaces, qui sont des parties stables, et d'applications linéaires, qui sont des applications avant d'être linéaires.
L'analyse parle de fonctions définies sur un intervalle, donc de restriction et de prolongement.

Le chapitre installe aussi le dénombrement des parties d'un ensemble fini, qui donne les coefficients binomiaux et, plus tard, la loi binomiale. Rien n'est difficile ici. Tout doit être automatique.

1Ensembles et parties d'un ensemble

1.1Appartenance et inclusion

Définition 1.1Ensemble, appartenance

Un ensemble est une collection d'objets appelés ses éléments. On écrit $x \in E$ pour dire que $x$ est un élément de $E$ , et $x \notin E$ sinon.

Définition 1.2Inclusion

On dit que $A$ est inclus dans $E$ , noté $A \subset E$ , quand tout élément de $A$ est élément de $E$ . Autrement dit : $\forall x,\ x \in A \Rightarrow x \in E.$ On dit alors que $A$ est une partie de $E$ .

Attention

Il faut distinguer $\in$ et $\subset$ . L'appartenance relie un élément à un ensemble, l'inclusion relie deux ensembles. Pour $E = \{1, 2, 3\}$ , on a $1 \in E$ et $\{1\} \subset E$ , mais $1 \subset E$ n'a pas de sens et $\{1\} \in E$ est faux.

Propriété 1.3Égalité de deux ensembles

$A = B$ équivaut à $A \subset B$ et $B \subset A$ .

C'est la méthode standard pour prouver une égalité d'ensembles : la double inclusion. On raisonne par éléments, en commençant par « soit $x$ un élément de $A$ ».

Définition 1.4Ensemble vide

L'ensemble vide, noté $\emptyset$ , ne contient aucun élément. Il est inclus dans tout ensemble.

1.2Ensemble des parties

Définition 1.5Ensemble des parties

L'ensemble des parties de $E$ est noté $\mathcal{P}(E)$ . Ses éléments sont les parties de $E$ . Ainsi $A \subset E$ équivaut à $A \in \mathcal{P}(E)$ .

Exemple 1.6

Si $E = \{a, b\}$ , alors $\mathcal{P}(E) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$ , qui compte 4 éléments. Si $E$ possède $n$ éléments, $\mathcal{P}(E)$ en possède $2^n$ .

1.3Nombre de parties à p éléments

Propriété 1.7Nombre de parties à $p$ éléments

Hypothèses

$E$ est un ensemble à $n$ éléments ;
$p$ est un entier avec $0 \leqslant p \leqslant n$ .

Alors le nombre de parties de $E$ à $p$ éléments est le coefficient binomial $\binom{n}{p} = \frac{n!}{p!\,(n-p)!}.$

Le programme fait le lien avec l'arbre binaire de terminale : $\binom{n}{p}$ est aussi le nombre de chemins réalisant $p$ succès au cours de $n$ répétitions. C'est cette lecture qui servira pour la loi binomiale.

Formules à savoir utiliser :

symétrie, $\binom{n}{p} = \binom{n}{n-p}$ , car choisir une partie à $p$ éléments revient à choisir son complémentaire ;
formule du pion, $p\binom{n}{p} = n\binom{n-1}{p-1}$ pour $p \geqslant 1$ ;
formule de Pascal, $\binom{n}{p} + \binom{n}{p+1} = \binom{n+1}{p+1}$ .

Propriété 1.8Somme des coefficients binomiaux

En regroupant les parties de $E$ selon leur nombre d'éléments, on obtient $\sum_{p=0}^{n} \binom{n}{p} = 2^n,$ ce qui recoupe le comptage de $\mathcal{P}(E)$ .

1.4Opérations sur les parties

Soit $E$ un ensemble et $A$ , $B$ deux parties de $E$ .

Définition 1.9Complémentaire

Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $E$ qui ne sont pas dans $A$ . Le programme privilégie la notation $\overline{A}$ , et la notation $\complement_E A$ en cas d'ambiguïté sur l'ensemble de référence.

Définition 1.10Union, intersection, disjonction, différence

L'union $A \cup B$ est l'ensemble des $x$ qui sont dans $A$ ou dans $B$ , au sens inclusif.
L'intersection $A \cap B$ est l'ensemble des $x$ qui sont à la fois dans $A$ et dans $B$ .
$A$ et $B$ sont disjointes quand $A \cap B = \emptyset$ .
La différence $A \setminus B$ est l'ensemble des éléments de $A$ qui ne sont pas dans $B$ .

Attention

Ne pas confondre « disjointes » et « distinctes ».

Lien avec les connecteurs logiques : l'union correspond au « ou », l'intersection au « et », le complémentaire au « non ». Toutes les propriétés ci-dessous se lisent directement sur les connecteurs.

Propriété 1.11Distributivité

Pour toutes parties $A$ , $B$ , $C$ de $E$ : $\begin{aligned} A \cap (B \cup C) &= (A \cap B) \cup (A \cap C),\\ A \cup (B \cap C) &= (A \cup B) \cap (A \cup C). \end{aligned}$

Les deux sens fonctionnent, ce qui n'est pas le cas pour l'addition et la multiplication des nombres.

Propriété 1.12Lois de De Morgan

Pour toutes parties $A$ et $B$ de $E$ : $\begin{aligned} \overline{A \cup B} &= \overline{A} \cap \overline{B},\\ \overline{A \cap B} &= \overline{A} \cup \overline{B}. \end{aligned}$

Ces deux formules seront utilisées en permanence en probabilités, pour passer d'un « au moins un » à un « aucun ».

Propriété 1.13Complémentaire et inclusion

$\overline{\overline{A}} = A$ ;
$A \subset B$ équivaut à $\overline{B} \subset \overline{A}$ .

1.5Produit cartésien

Définition 1.14Produit cartésien

Le produit cartésien de $E$ et $F$ , noté $E \times F$ , est l'ensemble des couples $(x, y)$ avec $x \in E$ et $y \in F$ . Deux couples sont égaux quand leurs deux composantes le sont, dans l'ordre.

Attention

Un couple n'est pas une paire : $(1, 2)$ et $(2, 1)$ sont différents alors que $\{1, 2\}$ et $\{2, 1\}$ sont le même ensemble.

On généralise à $n$ ensembles avec les $n$ -uplets. Les notations $\R^2$ et $\R^n$ désignent respectivement l'ensemble des couples et l'ensemble des $n$ -uplets de réels.

Propriété 1.15Cardinal d'un produit

Si $E$ possède $n$ éléments et $F$ possède $p$ éléments, alors $E \times F$ en possède $np$ .

2Applications

2.1Définition

Définition 2.1Application

Une application $f$ de $E$ dans $F$ associe à chaque élément $x$ de $E$ un unique élément de $F$ , noté $f(x)$ .

$E$ est l'ensemble de départ, $F$ l'ensemble d'arrivée ;
$f(x)$ est l'image de $x$ ;
tout $x$ tel que $f(x) = y$ est un antécédent de $y$ .

Deux applications sont égales quand elles ont mêmes ensembles de départ et d'arrivée, et quand elles coïncident en chaque point. Changer l'ensemble d'arrivée change l'application, même si la formule est la même. C'est ce détail qui fait qu'une même formule peut être surjective ou non.

Définition 2.2Identité

L'application identité de $E$ , notée $\mathrm{Id}_E$ , envoie chaque $x$ sur lui-même.

2.2Composition

Définition 2.3Composée

Si $f$ va de $E$ dans $F$ et $g$ de $F$ dans $G$ , la composée $g \circ f$ va de $E$ dans $G$ et envoie $x$ sur $g(f(x))$ .

La composition est associative. Elle n'est pas commutative : $g \circ f$ et $f \circ g$ n'ont en général ni le même sens ni la même valeur.

Exemple 2.4

Sur $\R$ , avec $f(x) = x + 1$ et $g(x) = x^2$ , on obtient $g(f(x)) = (x+1)^2$ alors que $f(g(x)) = x^2 + 1$ .

2.3Restriction et prolongement

Définition 2.5Restriction et prolongement

Si $f$ est définie sur $E$ et si $A$ est une partie de $E$ , la restriction de $f$ à $A$ est l'application de $A$ dans $F$ qui coïncide avec $f$ sur $A$ . Inversement, prolonger une application définie sur $A$ , c'est construire une application définie sur un ensemble plus grand qui coïncide avec elle sur $A$ .

Le programme précise que ces deux notions ne sont introduites que dans les cours d'algèbre linéaire et d'analyse, là où elles servent. L'exemple typique d'analyse est le prolongement par continuité en un point.

2.4Injectivité, surjectivité, bijectivité

Soit $f$ une application de $E$ dans $F$ .

Définition 2.6Injectivité

$f$ est injective quand deux éléments distincts ont des images distinctes. Formulation utilisable : $\forall (x, y) \in E^2,\ f(x) = f(y) \Rightarrow x = y.$ Cela signifie que tout élément de $F$ a au plus un antécédent.

Définition 2.7Surjectivité

$f$ est surjective quand tout élément de $F$ possède au moins un antécédent : $\forall y \in F,\ \exists x \in E,\ f(x) = y.$

Définition 2.8Bijectivité

$f$ est bijective quand elle est à la fois injective et surjective, c'est-à-dire quand tout élément de $F$ possède exactement un antécédent. Il existe alors une application réciproque, notée $f^{-1}$ , qui va de $F$ dans $E$ et qui envoie $y$ sur son unique antécédent. Elle vérifie $f^{-1} \circ f = \mathrm{Id}_E, \qquad f \circ f^{-1} = \mathrm{Id}_F.$

Exemple 2.9Exemples de référence, tous à connaître

La fonction carré de $\R$ dans $\R$ n'est ni injective, car $1$ et $-1$ ont la même image, ni surjective, car $-1$ n'a pas d'antécédent.
La même formule, de $\R_+$ dans $\R_+$ , est bijective, de réciproque la racine carrée. Le changement porte uniquement sur les ensembles.
L'exponentielle, de $\R$ dans $\R$ , est injective mais pas surjective. De $\R$ dans $\R_+^*$ , elle est bijective, de réciproque le logarithme népérien.
La fonction cube de $\R$ dans $\R$ est bijective.

Propriété 2.10Composition et injectivité, surjectivité, bijectivité

Une composée d'injections est injective.
Une composée de surjections est surjective.
Une composée de bijections est bijective, et la réciproque de $g \circ f$ est $f^{-1} \circ g^{-1}$ , dans cet ordre inversé.

Attention

Une application peut être injective sans être surjective et inversement.

Pour réfuter l'injectivité, il suffit de deux points distincts de même image.
Pour réfuter la surjectivité, il suffit d'un élément de l'ensemble d'arrivée sans antécédent.
Un exemple ne prouve jamais l'injectivité, il faut un raisonnement général.

Propriété 2.11Cas des ensembles finis

Hypothèses

$E$ et $F$ sont finis ;
$E$ et $F$ ont le même cardinal.

Alors une application de $E$ dans $F$ est injective si et seulement si elle est surjective, donc si et seulement si elle est bijective.

Attention

Ce résultat est faux sans l'hypothèse de finitude. Sur $\N$ , l'application $n \mapsto n + 1$ est injective et non surjective.

Méthodes

MéthodeProuver une égalité d'ensembles

Faire une double inclusion.
Raisonner sur un élément quelconque.
Ne jamais manipuler des ensembles comme des nombres.

MéthodeTraduire un énoncé ensembliste

Remplacer $\cup$ par « ou », $\cap$ par « et », le complémentaire par « non ».
Appliquer les règles de logique.

MéthodeTraiter un « au moins un » en probabilités

Dès qu'apparaît un « au moins un », passer au complémentaire par De Morgan.

MéthodeÉtudier injectivité et surjectivité

Pour l'injectivité, partir de $f(x) = f(y)$ et conclure $x = y$ .
Pour la surjectivité, partir d'un $y$ quelconque et résoudre l'équation $f(x) = y$ d'inconnue $x$ .

MéthodeMontrer qu'une application est bijective

Résoudre $f(x) = y$ d'inconnue $x$ .
Constater qu'il y a une unique solution pour tout $y$ de $F$ .
Lire la réciproque dans cette résolution.

MéthodeDénombrer des parties

Se demander si l'ordre compte.
Si oui, on est dans un produit cartésien.
Si non, on est dans un coefficient binomial.

Ce qu'il faut savoir refaire en khôlle

Écrire $\mathcal{P}(E)$ pour un ensemble à trois éléments et compter ses éléments.
Démontrer les lois de De Morgan par double inclusion.
Démontrer la distributivité de l'intersection sur l'union.
Justifier que le nombre de parties à $p$ éléments d'un ensemble à $n$ éléments est $\binom{n}{p}$ , et en déduire $\sum_{p=0}^{n}\binom{n}{p} = 2^n$ .
Étudier l'injectivité et la surjectivité de la fonction carré selon les ensembles de départ et d'arrivée choisis.
Montrer qu'une composée d'injections est injective, et que la réciproque d'une composée inverse l'ordre.
Donner un exemple d'application injective et non surjective sur un ensemble infini.
Expliquer la différence entre un couple et une paire.

Méthodes et exercices

Les résultats à connaître

Égalité de deux ensembles. A = B si et seulement si A ⊂ B et B ⊂ A. Exigible, c'est la méthode de la double inclusion.
L'ensemble vide est inclus dans tout ensemble. Exigible, l'implication « x ∈ ∅ ⇒ x ∈ E » a une hypothèse toujours fausse.
Si E possède n éléments, P(E) en possède 2ⁿ. Exigible avec démonstration, par récurrence sur n ou par comptage des parties selon leur cardinal.
Le nombre de parties à p éléments d'un ensemble à n éléments est C(n, p) = n!/(p!(n − p)!). Exigible, avec le lien au nombre de chemins à p succès dans un arbre binaire à n niveaux.
Symétrie C(n, p) = C(n, n − p), formule du pion p C(n, p) = n C(n − 1, p − 1), formule de Pascal. Exigibles, la symétrie a une preuve ensembliste, le passage au complémentaire.
Σ_p=0ⁿ C(n, p) = 2ⁿ. Exigible, par regroupement des parties selon leur cardinal ou par le binôme.
Distributivité, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) et A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Exigibles avec démonstration par double inclusion ou par chaîne d'équivalences.
Lois de De Morgan. Le complémentaire de A ∪ B est l'intersection des complémentaires, celui de A ∩ B est l'union des complémentaires. Exigibles avec démonstration.
A ⊂ B équivaut à ce que le complémentaire de B soit inclus dans celui de A. Exigible.
Produit cartésien. E × F est l'ensemble des couples, et si E a n éléments et F en a p, E × F en a np. Exigible.
La composition est associative et non commutative. Exigible, avec un contre-exemple.
Une composée d'injections est injective, une composée de surjections est surjective, une composée de bijections est bijective et (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹. Exigibles avec démonstration.
Si g ∘ f = Id_E alors f est injective et g est surjective. Exigible avec démonstration, très demandé en khôlle.
Si E et F sont finis de même cardinal, une application de E dans F est injective si et seulement si elle est surjective. Admis en première année, à savoir énoncer avec l'hypothèse de finitude.
Hors programme, à signaler si un exercice les demande, l'image directe et l'image réciproque d'une partie comme notions générales, la théorie des cardinaux, et le théorème de Cantor.

Clés de démonstration

Cardinal de P(E). Récurrence sur n. Pour passer de n à n + 1, on fixe un élément a de E, et on sépare les parties de E en celles qui ne contiennent pas a, ce sont les parties de E privé de a, et celles qui le contiennent, obtenues en ajoutant a à une partie de E privé de a. Chaque famille en compte 2ⁿ. Astuce, la bijection X ↦ X ∪ {a} entre les deux familles.

De Morgan. On prend x dans E, et on traduit « x n'est pas dans A ∪ B » par « non (x ∈ A ou x ∈ B) », qui est « x ∉ A et x ∉ B » par De Morgan logique, donc x est dans l'intersection des complémentaires. Chaque étape est une équivalence, une seule chaîne suffit. Astuce, tout énoncé ensembliste est une phrase logique sur un élément générique.

Composée d'injections. Si g(f(x)) = g(f(y)), l'injectivité de g donne f(x) = f(y), celle de f donne x = y. Astuce, on remonte de l'extérieur vers l'intérieur.

g ∘ f = Id implique f injective et g surjective. Si f(x) = f(y), on applique g et on obtient x = y. Pour la surjectivité de g, tout x de E s'écrit x = g(f(x)), donc f(x) est un antécédent. Astuce, l'identité fournit gratuitement un antécédent.

Réciproque d'une composée. On calcule (f⁻¹ ∘ g⁻¹) ∘ (g ∘ f) = f⁻¹ ∘ (g⁻¹ ∘ g) ∘ f = f⁻¹ ∘ f = Id_E par associativité, et de même dans l'autre sens. Astuce, l'ordre s'inverse comme quand on enlève des chaussettes puis des chaussures.

Symétrie des coefficients binomiaux. L'application qui à une partie de E associe son complémentaire est une bijection de l'ensemble des parties à p éléments sur l'ensemble des parties à n − p éléments, sa réciproque est elle-même. Astuce, une bijection entre deux ensembles finis prouve l'égalité des cardinaux sans calcul.

Exemples et contre-exemples à connaître

Pour E = {1, 2, 3}, on a 1 ∈ E, {1} ⊂ E, {1} ∈ P(E), mais 1 ∉ P(E). Appartenance et inclusion ne vivent pas au même étage.
P(∅) = {∅}, qui a un élément. L'ensemble vide et l'ensemble contenant l'ensemble vide sont différents.
(1, 2) ≠ (2, 1) alors que {1, 2} = {2, 1}. Un couple est ordonné, une paire ne l'est pas.
Les événements « pile au premier lancer » et « face au deuxième » sont distincts mais pas disjoints. Disjoint signifie intersection vide.
x ↦ x² est injective de R+ dans R, surjective de R dans R+, bijective de R+ dans R+, ni l'un ni l'autre de R dans R. La formule ne suffit pas, les ensembles comptent.
exp est injective de R dans R mais non surjective, et bijective de R sur ]0, +∞[ de réciproque ln. Restreindre l'ensemble d'arrivée rend surjective.
n ↦ n + 1 de N dans N est injective mais pas surjective, 0 n'a pas d'antécédent. L'équivalence injective si et seulement si surjective est fausse sur un ensemble infini.
Avec f(x) = x + 1 et g(x) = x² sur R, g ∘ f(x) = (x + 1)² et f ∘ g(x) = x² + 1. La composition n'est pas commutative.
f l'inclusion de N dans Z et g la valeur absolue de Z dans N. Alors g ∘ f = Id_N, pourtant f n'est pas surjective et g n'est pas injective.
L'application n ↦ (−1)ⁿ de N dans {−1, 1} est surjective et pas injective. Deux éléments à l'arrivée, une infinité au départ, il n'y a aucune chance d'injectivité.

Techniques du chapitre

Double inclusion. Mini-exercice, montrer que A ∩ (A ∪ B) = A. Si x ∈ A ∩ (A ∪ B), alors x ∈ A. Si x ∈ A, alors x ∈ A ∪ B, donc x ∈ A ∩ (A ∪ B). Les deux inclusions sont établies.

Traduction en connecteurs. Mini-exercice, en probabilités, l'événement « au moins un des trois tirages donne un as » est A₁ ∪ A₂ ∪ A₃. Son contraire est « aucun tirage ne donne un as », c'est l'intersection des trois complémentaires par De Morgan. C'est le réflexe du chapitre probabilités.

Injectivité par résolution. Mini-exercice, f définie sur R par f(x) = 3x − 2. Si f(x) = f(y), alors 3x − 2 = 3y − 2, donc x = y. f est injective.

Surjectivité par construction d'un antécédent. Mini-exercice, f de R dans R définie par f(x) = x³ + x. Pour y réel, la fonction f est continue et strictement croissante, de limites −∞ et +∞, donc y admet un unique antécédent par le théorème des valeurs intermédiaires. f est bijective. Cette technique s'appuie sur le cours d'analyse du semestre.

Bijectivité par résolution de f(x) = y. Mini-exercice, f de R dans ]−1, 1[ définie par f(x) = x/(1 + |x|). Pour y dans ]0, 1[, on cherche x > 0 avec x/(1 + x) = y, soit x = y/(1 − y) > 0, unique. Pour y dans ]−1, 0[, par imparité, x = y/(1 + y). Pour y = 0, x = 0. Chaque y a exactement un antécédent, f est bijective.

Comptage de parties. Mini-exercice, nombre de comités de 3 personnes parmi 10 contenant une personne donnée. On choisit les 2 autres parmi 9, il y a C(9, 2) = 36 comités. Le total est C(10, 3) = 120, et 3 × 120 = 10 × 36 est la formule du pion.

Ordre ou pas ordre. Mini-exercice, nombre de codes à 4 chiffres, c'est 10⁴ car un code est un 4-uplet. Nombre de choix de 4 chiffres distincts sans ordre, c'est C(10, 4) = 210. La question à se poser, l'ordre compte-t-il.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Exercice 1. Différence symétrique

Classiques de khôlle et concours · Niveau khôlle

Pour A et B parties de E, on note A Δ B l'ensemble des éléments qui sont dans A ou dans B mais pas dans les deux. (a) Montrer que A Δ B = (A ∪ B) privé de (A ∩ B). (b) Montrer que A Δ B = ∅ si et seulement si A = B.

Technique raisonner sur un élément, traduire « ou exclusif ».

Voir le corrigé

(a) x ∈ A Δ B signifie (x ∈ A ou x ∈ B) et non(x ∈ A et x ∈ B), c'est exactement x ∈ A ∪ B et x ∉ A ∩ B. 2. (b) Si A = B, alors A ∪ B = A ∩ B, donc A Δ B = ∅. 3. Réciproquement, si A Δ B = ∅, soit x ∈ A. Comme x ∉ A Δ B, x n'est pas dans A sans être dans B, donc x ∈ B. Donc A ⊂ B, et B ⊂ A par symétrie.

piège : Écrire des égalités d'ensembles par manipulation formelle sans revenir à un élément.

Exercice 2. Deux égalités d'ensembles

Classiques de khôlle et concours · Niveau khôlle

Soient A, B, C parties de E. Montrer que si A ∩ B = A ∩ C et A ∪ B = A ∪ C, alors B = C.

Technique double inclusion avec disjonction selon l'appartenance à A.

Voir le corrigé

Soit x ∈ B. Si x ∈ A, alors x ∈ A ∩ B = A ∩ C, donc x ∈ C. 2. Si x ∉ A, alors x ∈ A ∪ B = A ∪ C, et x ∉ A, donc x ∈ C. 3. Dans les deux cas x ∈ C, donc B ⊂ C. L'hypothèse est symétrique en B et C, d'où C ⊂ B.

piège : Oublier le cas x ∉ A, ou vouloir « simplifier par A » comme dans une équation.

Exercice 3. Cardinal de P(E)

Classiques de khôlle et concours · Niveau khôlle

Montrer par récurrence que si E a n éléments, P(E) en a 2ⁿ. Retrouver ce résultat avec les coefficients binomiaux.

Technique récurrence avec partition des parties selon un élément fixé, puis binôme.

Voir le corrigé

Pour n = 0, E = ∅ et P(E) = {∅} a 1 = 2⁰ élément. 2. Soit E de cardinal n + 1 et a un élément de E. Les parties de E qui ne contiennent pas a sont les parties de E privé de a, il y en a 2ⁿ par hypothèse. Celles qui contiennent a sont de la forme X ∪ {a} avec X partie de E privé de a, et X ↦ X ∪ {a} est une bijection, il y en a 2ⁿ. 3. Total 2ⁿ + 2ⁿ = 2ⁿ⁺¹. 4. Autre voie, il y a C(n, p) parties à p éléments, donc P(E) a Σ_p=0ⁿ C(n, p) = (1 + 1)ⁿ éléments.

piège : Dans l'hérédité, compter deux fois la partie vide ou oublier les parties qui contiennent a.

Exercice 4. Une application de P(E) dans P(E)

Classiques de khôlle et concours · Niveau khôlle

Soit E un ensemble et B une partie fixée de E. On définit φ de P(E) dans P(E) par φ(X) = X ∩ B. (a) φ est-elle injective. (b) Déterminer l'ensemble des images de φ. (c) À quelle condition sur B φ est-elle bijective.

Technique tester sur des parties simples, X = ∅ et X = E.

Voir le corrigé

(a) φ(E) = B = φ(B). Si B ≠ E, deux parties distinctes ont la même image, φ n'est pas injective. 2. (b) Toute image est incluse dans B. Réciproquement une partie Y de B vérifie φ(Y) = Y. L'ensemble des images est donc P(B). 3. (c) φ est surjective sur P(E) si et seulement si P(B) = P(E), c'est-à-dire B = E. Dans ce cas φ est l'identité, donc bijective. Conclusion, φ est bijective si et seulement si B = E.

piège : Croire qu'une application définie par une formule simple est forcément injective.

Exercice 5. Composition et identité

Classiques de khôlle et concours · Niveau khôlle

Soient f de E dans F et g de F dans E telles que g ∘ f = Id_E. (a) Montrer que f est injective et g surjective. (b) Montrer que si de plus f ∘ g = Id_F, alors f est bijective et g = f⁻¹. (c) Donner un exemple où g ∘ f = Id_E sans que f soit bijective.

Technique composer par la bonne application, l'identité fournit des antécédents.

Voir le corrigé

(a) Si f(x) = f(y), alors g(f(x)) = g(f(y)), soit x = y. Pour x ∈ E, x = g(f(x)), donc x a l'antécédent f(x) par g. 2. (b) Pour y ∈ F, y = f(g(y)), donc y a un antécédent, f est surjective, donc bijective. On compose g ∘ f = Id_E à droite par f⁻¹, ce qui donne g = f⁻¹. 3. (c) L'exemple 9 de la section 3, f l'inclusion de N dans Z et g la valeur absolue.

piège : Conclure que f est bijective avec la seule hypothèse g ∘ f = Id_E.

Exercice 6. Une bijection de N sur Z

Classiques de khôlle et concours · Niveau khôlle

Soit f définie sur N par f(n) = n/2 si n est pair et f(n) = −(n + 1)/2 si n est impair. Montrer que f est une bijection de N sur Z.

Technique disjonction selon la parité, puis résolution de f(n) = m.

Voir le corrigé

f est à valeurs dans Z, les pairs donnent 0, 1, 2, …, les impairs donnent −1, −2, …. 2. Surjectivité, pour m ≥ 0, n = 2m est pair et f(n) = m. Pour m < 0, n = −2m − 1 est un entier naturel impair et f(n) = −(−2m)/2 = m. 3. Injectivité, un pair a une image positive ou nulle et un impair une image strictement négative, donc f(n) = f(n') impose la même parité, puis n = n' par calcul dans chaque cas.

piège : Oublier que 0 est atteint une seule fois, par n = 0.

Exercice 7. Injectivité et composition

Classiques de khôlle et concours · Niveau khôlle

Soient f de E dans F et g de F dans G. (a) Montrer que si g ∘ f est injective, alors f est injective. (b) Montrer que si g ∘ f est surjective, alors g est surjective. (c) Montrer par un exemple que g ∘ f injective n'impose pas g injective.

Technique revenir aux définitions, l'hypothèse porte sur la composée.

Voir le corrigé

(a) Si f(x) = f(y), alors g(f(x)) = g(f(y)), donc x = y par injectivité de g ∘ f. 2. (b) Pour z ∈ G, il existe x ∈ E avec g(f(x)) = z, donc f(x) est un antécédent de z par g. 3. (c) f l'inclusion de R+ dans R et g le carré de R dans R. Alors g ∘ f est le carré sur R+, injectif, alors que g ne l'est pas.

piège : Prouver l'injectivité de g au lieu de celle de f, en se trompant sur l'application intérieure.

Exercice 8. Dénombrement de parties et de fonctions

Classiques de khôlle et concours · Niveau écrit Ecricome

Soit E un ensemble à n éléments. (a) Combien y a-t-il d'applications de E dans {0, 1}. (b) En déduire une nouvelle preuve que P(E) a 2ⁿ éléments. (c) Combien de parties de E ont un nombre pair d'éléments.

Technique bijection entre parties et fonctions indicatrices, binôme en (−1, 1).

Voir le corrigé

(a) Une application de E dans {0, 1} est un n-uplet de 0 et de 1, il y en a 2ⁿ. 2. (b) À une partie A on associe l'application qui vaut 1 sur A et 0 ailleurs. Réciproquement une application à valeurs dans {0, 1} définit la partie des éléments où elle vaut 1. C'est une bijection entre P(E) et l'ensemble des applications de E dans {0, 1}, donc P(E) a 2ⁿ éléments. 3. (c) Le nombre cherché est Σ C(n, p) sur les p pairs. Or Σ_p=0ⁿ (−1)^p C(n, p) = 0 pour n ≥ 1, donc la somme sur les p pairs égale la somme sur les p impairs, et leur total vaut 2ⁿ. Il y a 2ⁿ⁻¹ parties de cardinal pair, pour n ≥ 1.

piège : Dans (c), oublier le cas n = 0 où la réponse est 1 et non 2⁻¹.

Exercice 9. Nombre de parties à p éléments par récurrence

Classiques de khôlle et concours · Niveau écrit Ecricome

On note N(n, p) le nombre de parties à p éléments d'un ensemble à n éléments. Montrer que N(n + 1, p + 1) = N(n, p) + N(n, p + 1), et en déduire N(n, p) = C(n, p).

Technique séparer les parties selon qu'elles contiennent un élément fixé, puis récurrence sur n avec la formule de Pascal.

Voir le corrigé

Soit E de cardinal n + 1 et a ∈ E. Une partie à p + 1 éléments de E contient a ou non. Si elle le contient, elle est déterminée par une partie à p éléments de E privé de a, il y en a N(n, p). Sinon c'est une partie à p + 1 éléments de E privé de a, il y en a N(n, p + 1). 2. On a N(n, 0) = 1 = C(n, 0) et N(n, n) = 1 = C(n, n). 3. Par récurrence sur n, si N(n, p) = C(n, p) pour tout p, alors N(n + 1, p + 1) = C(n, p) + C(n, p + 1) = C(n + 1, p + 1) par Pascal, et les bords sont vérifiés en 2. 4. Conclusion pour tout n et tout p.

piège : Oublier de traiter les bords p = 0 et p = n + 1 dans l'hérédité.

Exercice 10. Ensembles finis et bijections

Classiques de khôlle et concours · Niveau écrit BCE, type EDHEC

Soit E un ensemble fini à n éléments et f une application de E dans E. Montrer que f est injective si et seulement si f est surjective. Le résultat est-il vrai si E est infini.

Technique comparer le nombre d'images distinctes au cardinal de E.

Voir le corrigé

Si f est injective, les n éléments de E ont n images deux à deux distinctes, toutes dans E qui a n éléments. L'ensemble des images est donc E tout entier, f est surjective. 2. Si f est surjective, les ensembles d'antécédents des n éléments de E sont non vides, deux à deux disjoints, et leur réunion est E qui a n éléments. Chacun a donc exactement un élément. Deux éléments distincts ne peuvent pas avoir la même image, f est injective. 3. Faux si E est infini, n ↦ n + 1 sur N est injective non surjective, et n ↦ partie entière de n/2 est surjective non injective.

piège : Utiliser ce résultat en probabilités ou en algèbre linéaire sans avoir vérifié que l'ensemble est fini, ou que l'on est en dimension finie.

Exercice 11. Fonctions strictement croissantes de {1, …, p} dans {1, …, n}

Classiques de khôlle et concours · Niveau écrit HEC ou ESSEC

Soit p ≤ n. Montrer que le nombre d'applications strictement croissantes de {1, …, p} dans {1, …, n} vaut C(n, p).

Technique bijection entre ces applications et les parties à p éléments.

Voir le corrigé

À une application f strictement croissante on associe l'ensemble de ses images {f(1), …, f(p)}. Ces p valeurs sont deux à deux distinctes par stricte croissance, c'est donc une partie à p éléments de {1, …, n}. 2. Réciproquement, une partie à p éléments se range d'une seule manière en ordre croissant a₁ < … < a_p, et f(i) = a_i est l'unique application strictement croissante d'images cette partie. 3. On a une bijection entre les applications strictement croissantes et les parties à p éléments, il y en a C(n, p).

piège : Ne prouver qu'un sens de la correspondance, alors qu'une bijection exige les deux.

Erreurs fréquentes

Confondre ∈ et ⊂, ou écrire x ⊂ E pour un élément x.
Prouver une égalité d'ensembles par un calcul formel au lieu d'une double inclusion sur un élément générique.
Croire qu'un exemple prouve l'injectivité, alors qu'un exemple ne peut que la réfuter.
Parler d'une bijection sans préciser les ensembles de départ et d'arrivée, alors que la même formule est bijective ou non selon ces ensembles.
Utiliser « injective équivaut à surjective » sur un ensemble infini, ou compter des couples là où l'ordre ne compte pas.

Fiche de cours rédigée à partir du programme officiel d'ECG mathématiques approfondies (2021), enseignement du premier semestre, partie I « Raisonnement et vocabulaire ensembliste », paragraphe « Ensembles, applications ». Le programme indique que l'objectif est d'acquérir un vocabulaire en vue de l'algèbre linéaire et des probabilités, et que tout exposé théorique est exclu.

Ensembles et applications

Résumé en cinq points

1Ensembles et parties d'un ensemble

1.1Appartenance et inclusion

1.2Ensemble des parties

1.3Nombre de parties à p éléments

1.4Opérations sur les parties

1.5Produit cartésien

2Applications

2.1Définition

2.2Composition

2.3Restriction et prolongement

2.4Injectivité, surjectivité, bijectivité

Méthodes

Ce qu'il faut savoir refaire en khôlle

Les résultats à connaître

Clés de démonstration

Exemples et contre-exemples à connaître

Techniques du chapitre

Exercices classiques corrigés

Exercice 1. Différence symétrique

Exercice 2. Deux égalités d'ensembles

Exercice 3. Cardinal de P(E)

Exercice 4. Une application de P(E) dans P(E)

Exercice 5. Composition et identité

Exercice 6. Une bijection de N sur Z

Exercice 7. Injectivité et composition

Exercice 8. Dénombrement de parties et de fonctions

Exercice 9. Nombre de parties à p éléments par récurrence

Exercice 10. Ensembles finis et bijections

Exercice 11. Fonctions strictement croissantes de {1, …, p} dans {1, …, n}

Erreurs fréquentes