Raisonnement et vocabulaire ensembliste

Cours complet · mathématiques approfondies (ECG 1re année), chapitre 1 · prépa ECG, 1re année

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

Ce chapitre fixe la langue du reste de l'année, et y ajoute deux outils de calcul dont on ne se passera plus : les sommes et produits indexés, et les coefficients binomiaux. Le programme est explicite — tout exposé théorique est exclu : ces notions s'acquièrent en s'en servant, et seront réemployées dans chaque chapitre, en algèbre linéaire comme en probabilités.

1.1 Éléments de logique

Définition 1.1Proposition et connecteurs

Une proposition est un énoncé auquel on attribue une valeur de vérité, vrai ou faux, et une seule. Pour $P$ et $Q$ deux propositions :

« $P$ et $Q$ » est vraie lorsque les deux le sont ;
« $P$ ou $Q$ » est vraie lorsque l'une au moins l'est ;
« non $P$ » est vraie lorsque $P$ est fausse.

AttentionLe « ou » est inclusif

« $P$ ou $Q$ » reste vraie quand $P$ et $Q$ le sont toutes deux. L'équation $x^{2} = x$ équivaut à « $x = 0$ ou $x = 1$ » : ce « ou » n'exclut rien, il se trouve seulement qu'aucun réel ne vérifie les deux conditions.

Définition 1.2Implication, réciproque, contraposée

« $P \Rightarrow Q$ » est fausse dans le seul cas où $P$ est vraie et $Q$ fausse. On lui associe sa réciproque $Q \Rightarrow P$ , sa contraposée $non Q \Rightarrow non P$ , et sa négation « $P$ et non $Q$ ». Si $P \Rightarrow Q$ et $Q \Rightarrow P$ , on écrit $P \Leftrightarrow Q$ .

Proposition 1.3Contraposition

Les propositions $P \Rightarrow Q$ et $non Q \Rightarrow non P$ ont toujours la même valeur de vérité.

Démonstration

$P \Rightarrow Q$ n'est fausse que si $P$ est vraie et $Q$ fausse. C'est précisément le seul cas où « non $Q$ » est vraie et « non $P$ » fausse, donc le seul cas où la contraposée est fausse. Elles sont fausses ensemble, donc vraies ensemble.

AttentionNe pas confondre avec la réciproque

« Si $x = 2$ alors $x^{2} = 4$ » est vraie, sa contraposée « si $x^{2} \neq = 4$ alors $x \neq = 2$ » aussi ; mais sa réciproque « si $x^{2} = 4$ alors $x = 2$ » est fausse, comme le montre $x = - 2$ . Démontrer une équivalence demande donc deux démonstrations, sauf à raisonner par équivalences successives.

Définition 1.4Quantificateurs

Pour $P (x)$ dépendant de $x \in E$ : $\forall x \in E, P (x)$ signifie « pour tout $x$ de $E$ » ; $\exists x \in E, P (x)$ signifie « il existe $x$ dans $E$ tel que ».

AttentionL'ordre des quantificateurs porte du sens

$\forall x \in R, \exists y \in R, y > x$ est vraie : il suffit de prendre $y = x + 1$ , qui dépend de $x$ . En échangeant les deux symboles, $\exists y \in R, \forall x \in R, y > x$ affirme qu'un même $y$ dépasse tous les réels : c'est faux.

Proposition 1.5Négations

$non (P et Q) non (P ou Q) non (\forall x \in E, P (x)) non (\exists x \in E, P (x)) \Leftrightarrow \Leftrightarrow \Leftrightarrow \Leftrightarrow (non P) ou (non Q) (non P) et (non Q) \exists x \in E, non P (x) \forall x \in E, non P (x)$

ImportantLa règle pratique

Nier un énoncé quantifié : échanger $\forall$ et $\exists$ en conservant leur ordre, puis nier la conclusion. Un seul contre-exemple suffit ainsi à infirmer un « pour tout ».

Exemple 1.6Nier une majoration

« $(u_{n})$ est majorée » s'écrit $\exists M \in R, \forall n \in N, u_{n} \leq M$ . Sa négation est $\forall M \in R, \exists n \in N, u_{n} > M$ : quel que soit le seuil, la suite le dépasse au moins une fois. L'indice $n$ dépend désormais de $M$ .

1.2 Raisonnement par récurrence

◆Théorème 1.7Principe de récurrence

Soit $P (n)$ une proposition dépendant de $n \in N$ et $n_{0} \in N$ . Si $P (n_{0})$ est vraie et si, pour tout $n \geq n_{0}$ , $P (n) \Rightarrow P (n + 1)$ , alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

ImportantTrois temps, jamais deux

Initialisation : vérifier $P (n_{0})$ . Hérédité : supposer $P (n)$ pour un $n \geq n_{0}$ fixé, en déduire $P (n + 1)$ . Conclusion. L'hérédité seule propage sans jamais démarrer : sans initialisation, on « démontrerait » que tout entier est impair.

1.3 Sommes et produits

Définition 1.8Notations

\sum

\prod

Pour des réels $u_{1}, \dots, u_{n}$ :

$i = 1 \sum n u_{i} = u_{1} + \dots + u_{n}, i = 1 \prod n u_{i} = u_{1} \times \dots \times u_{n} .$

Si $A$ est un sous-ensemble fini de $N$ ou de $N^{2}$ , $i \in A \sum u_{i}$ désigne la somme des $u_{i}$ pour $i$ décrivant $A$ . Par convention, une somme vide vaut $0$ et un produit vide vaut $1$ .

iRemarqueL'indice est muet

$\sum_{i = 1}^{n} u_{i}$ et $\sum_{k = 1}^{n} u_{k}$ sont le même nombre : le nom de l'indice ne survit pas à la somme. En revanche $n$ , lui, en sort.

Proposition 1.9Deux sommes de référence

Pour tout $n \in N$ et tout réel $q \neq = 1$ :

$k = 0 \sum n q^{k} = \frac{1 - q ^{n + 1}}{1 - q}, k = 1 \sum n k = \frac{n ( n + 1 )}{2} .$

Si $q = 1$ , la première somme vaut simplement $n + 1$ .

Démonstration

Pour la somme géométrique, posons $S = \sum_{k = 0}^{n} q^{k}$ . Alors

$(1 - q) S = k = 0 \sum n q^{k} - k = 0 \sum n q^{k + 1} = k = 0 \sum n q^{k} - k = 1 \sum n + 1 q^{k} = q^{0} - q^{n + 1} = 1 - q^{n + 1},$

la somme étant télescopique après changement d'indice ; on divise par $1 - q$ , non nul. Pour la seconde, une récurrence : elle vaut $1 = \frac{1 \times 2}{2}$ au rang $1$ , et si elle vaut $\frac{n ( n + 1 )}{2}$ au rang $n$ , alors au rang suivant $\frac{n ( n + 1 )}{2} + (n + 1) = \frac{( n + 1 ) ( n + 2 )}{2}$ .

iRemarqueCe qui est exigible, et ce qui ne l'est pas

Le programme retient ces deux formules. Celles donnant $\sum_{k = 1}^{n} k^{2}$ et $\sum_{k = 1}^{n} k^{3}$ seront rencontrées en exercice mais ne sont pas exigibles : on doit savoir les établir par récurrence, non les réciter.

1.4 Factorielle et coefficients binomiaux

Définition 1.10Factorielle

Pour $n \in N^{*}$ , $n! = 1 \times 2 \times \dots \times n = \prod_{k = 1}^{n} k$ , et l'on pose $0! = 1$ — c'est la convention du produit vide.

Définition 1.11Coefficient binomial

Pour $n \in N$ et $p \in N$ avec $0 \leq p \leq n$ , le nombre de parties à $p$ éléments d'un ensemble à $n$ éléments est

$(p n) = \frac{n !}{p ! ( n - p )!} .$

On pose $(p n) = 0$ lorsque $p < 0$ ou $p > n$ .

iRemarqueLe lien avec l'arbre de terminale

$(p n)$ compte aussi les chemins réalisant $p$ succès en $n$ répétitions dans un arbre binaire — la lecture rencontrée en terminale avec la loi binomiale. Choisir une partie à $p$ éléments, ou choisir à quels rangs placer les $p$ succès, c'est le même choix.

Proposition 1.12Symétrie et formule du capitaine

Pour $0 \leq p \leq n$ :

$(p n) = (n - p n), et pour 1 \leq p \leq n, (p n) = \frac{n}{p} (p - 1 n - 1) .$

Démonstration

La symétrie est immédiate sur la formule : échanger $p$ et $n - p$ échange les deux facteurs du dénominateur. Pour la seconde,

$\frac{n}{p} (p - 1 n - 1) = \frac{n}{p} \cdot \frac{( n - 1 )!}{( p - 1 )! ( n - p )!} = \frac{n !}{p ! ( n - p )!} = (p n),$

en utilisant $n \times (n - 1)! = n!$ et $p \times (p - 1)! = p!$ .

iRemarquePourquoi « du capitaine »

Choisir $p$ joueurs parmi $n$ puis désigner un capitaine parmi eux, c'est $p (p n)$ possibilités ; choisir d'abord le capitaine parmi les $n$ puis ses $p - 1$ coéquipiers parmi les $n - 1$ restants, c'est $n (p - 1 n - 1)$ . Les deux comptages portent sur le même ensemble.

◆Théorème 1.13Relation de Pascal

Pour $1 \leq p \leq n$ :

$(p n) = (p - 1 n - 1) + (p n - 1) .$

Démonstration

Soit $E$ un ensemble à $n$ éléments et $x$ l'un d'eux. Les parties à $p$ éléments de $E$ se répartissent en deux familles sans recouvrement : celles qui contiennent $x$ — il reste à choisir $p - 1$ éléments parmi les $n - 1$ autres, soit $(p - 1 n - 1)$ — et celles qui ne le contiennent pas, soit $(p n - 1)$ . Le total est $(p n)$ .

◆Théorème 1.14Formule du binôme de Newton

Pour tous réels $a$ et $b$ et tout $n \in N$ :

$(a + b)^{n} = k = 0 \sum n (k n) a^{k} b^{n - k} .$

Démonstration

Par récurrence sur $n$ . Au rang $0$ , les deux membres valent $1$ . Supposons la formule au rang $n$ . Alors

$(a + b)^{n + 1} = (a + b) k = 0 \sum n (k n) a^{k} b^{n - k} = k = 0 \sum n (k n) a^{k + 1} b^{n - k} + k = 0 \sum n (k n) a^{k} b^{n + 1 - k} .$

Dans la première somme, le changement d'indice $j = k + 1$ donne $\sum_{j = 1}^{n + 1} (j - 1 n) a^{j} b^{n + 1 - j}$ . En regroupant les deux sommes terme à terme et en appliquant la relation de Pascal $(j - 1 n) + (j n) = (j n + 1)$ , on obtient $\sum_{j = 0}^{n + 1} (j n + 1) a^{j} b^{n + 1 - j}$ , les termes extrêmes $j = 0$ et $j = n + 1$ se recollant sans peine.

Python : Le triangle de Pascal, ligne par ligne

La relation de Pascal se programme telle qu'elle s'écrit — chaque ligne se déduit de la précédente, sans jamais calculer de factorielle.


def ligne_suivante(L):
    return [1] + [L[i] + L[i + 1] for i in range(len(L) - 1)] + [1]

L = [1]
for n in range(6):
    print(n, L)
    L = ligne_suivante(L)

Calculer $(p n)$ par $n! / (p! (n - p)!)$ manipule des nombres énormes pour un résultat modeste ; la relation de Pascal n'additionne que des entiers déjà calculés.

1.5 Ensembles et parties

Définition 1.15Appartenance, inclusion, parties

On note $x \in E$ si $x$ est élément de $E$ . Un ensemble $A$ est inclus dans $E$ , noté $A \subset E$ , lorsque tout élément de $A$ appartient à $E$ . L'ensemble des parties de $E$ est noté $P (E)$ .

ImportantDouble inclusion

Pour démontrer $A = B$ , on établit $A \subset B$ puis $B \subset A$ . C'est la méthode par défaut : on part d'un élément quelconque de l'un pour le placer dans l'autre.

Exemple 1.16Élément ou partie

Pour $E = {1, 2}$ : $P (E) = {\emptyset, {1}, {2}, {1, 2}}$ . On a $1 \in E$ et ${1} \subset E$ , mais ${1} \in / E$ ; en revanche ${1} \in P (E)$ . Un ensemble à $n$ éléments a $2^{n}$ parties, dont $(p n)$ à exactement $p$ éléments.

Définition 1.17Union, intersection, complémentaire

Pour $A$ et $B$ parties de $E$ :

$A \cup B = {x \in E ∣ x \in A ou x \in B}, A \cap B = {x \in E ∣ x \in A et x \in B},$

et $A = {x \in E ∣ x \in / A}$ . En cas d'ambiguïté sur l'ensemble ambiant, on note $∁_{E} A$ .

◆Théorème 1.18Distributivité et lois de De Morgan

Pour toutes parties $A$ , $B$ , $C$ de $E$ :

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C), A \cup (B \cap C) = (A \cup B) \cap (A \cup C),$

$A \cup B = A \cap B, A \cap B = A \cup B .$

Démonstration

Chacune se lit sur les connecteurs. Pour la première loi de De Morgan : dire $x \in A \cup B$ , c'est nier « $x \in A$ ou $x \in B$ », donc affirmer « $x \in / A$ et $x \in / B$ », soit $x \in A \cap B$ . Pour la distributivité, dire $x \in A \cap (B \cup C)$ , c'est « $x \in A$ et ( $x \in B$ ou $x \in C$ ) », ce qui équivaut à « ( $x \in A$ et $x \in B$ ) ou ( $x \in A$ et $x \in C$ ) ». Les opérations ensemblistes ne font que transcrire les connecteurs logiques.

Définition 1.19Produit cartésien

$E \times F = {(x, y) ∣ x \in E, y \in F}$ . On note $R^{2} = R \times R$ et $R^{n}$ l'ensemble des $n$ -uplets de réels.

AttentionLe couple est ordonné

$(1, 2) \neq = (2, 1)$ , alors que ${1, 2} = {2, 1}$ . C'est cet ordre qui permet à $R^{2}$ de représenter le plan, et à $R^{n}$ de porter toute l'algèbre linéaire qui vient.

1.6 Applications

Définition 1.20Application, composée

Une application $f : E \to F$ associe à tout $x \in E$ un unique $f (x) \in F$ . Si $g : F \to G$ , la composée $g \circ f : E \to G$ est définie par $(g \circ f) (x) = g (f (x))$ .

Attention

g \circ f

applique

f

d'abord

La notation se lit de droite à gauche, à rebours de l'ordre des opérations.

Définition 1.21Injection, surjection, bijection

Soit $f : E \to F$ .

$f$ est injective si $\forall (x, x^{'}) \in E^{2}, f (x) = f (x^{'}) \Rightarrow x = x^{'}$ ;
$f$ est surjective si $\forall y \in F, \exists x \in E, y = f (x)$ ;
$f$ est bijective si elle est injective et surjective ; tout $y \in F$ a alors un unique antécédent, ce qui définit la réciproque $f^{- 1} : F \to E$ .

Exemple 1.22Cela dépend des ensembles, pas de la formule

L'application $x \mapsto x^{2}$ n'est ni injective ni surjective de $R$ dans $R$ ; elle est injective de $R_{+}$ dans $R$ ; elle est bijective de $R_{+}$ dans $R_{+}$ , de réciproque $y \mapsto y$ . Changer les ensembles de départ ou d'arrivée change la réponse.

Proposition 1.23Composée de bijections

Si $f : E \to F$ et $g : F \to G$ sont bijectives, $g \circ f$ l'est aussi et $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ .

Démonstration

Posons $h = f^{- 1} \circ g^{- 1}$ . Pour $z \in G$ , on a $(g \circ f) (h (z)) = g (g^{- 1} (z)) = z$ , et pour $x \in E$ , $h ((g \circ f) (x)) = f^{- 1} (f (x)) = x$ . L'application $g \circ f$ admet donc $h$ pour réciproque.

1.7 L'essentiel du chapitre

Fiche de synthèse

Logique : « ou » inclusif ; une implication équivaut à sa contraposée, jamais à sa réciproque ; l'ordre des quantificateurs porte du sens ; nier, c'est échanger $\forall$ et $\exists$ en gardant l'ordre.
Récurrence : initialisation, hérédité à $n$ fixé, conclusion.
Sommes : $\sum_{k = 0}^{n} q^{k} = \frac{1 - q ^{n + 1}}{1 - q}$ ( $q \neq = 1$ ) et $\sum_{k = 1}^{n} k = \frac{n ( n + 1 )}{2}$ ; somme vide $= 0$ , produit vide $= 1$ ; l'indice est muet.
Binomiaux : $(p n) = \frac{n !}{p ! ( n - p )!}$ ; symétrie $(p n) = (n - p n)$ ; capitaine $(p n) = \frac{n}{p} (p - 1 n - 1)$ ; Pascal $(p n) = (p - 1 n - 1) + (p n - 1)$ ; binôme $(a + b)^{n} = \sum_{k = 0}^{n} (k n) a^{k} b^{n - k}$ .
Ensembles : double inclusion ; distributivité ; De Morgan ; $P (E)$ a $2^{n}$ éléments si $∣ E ∣ = n$ .
Applications : injective, surjective, bijective — cela dépend des ensembles ; $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ .

Continuer sur Adloun : animation, QCM, fiches, exercices