Raisonnement et vocabulaire ensembliste

Cours complet · mathématiques appliquées (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 ne contient presque aucun résultat nouveau : il fixe la langue dans laquelle tout le reste sera écrit. Un énoncé mathématique n'est pas un texte ordinaire — « il existe un réel qui » et « pour tout réel » disent des choses opposées, et confondre une implication avec sa réciproque suffit à démontrer n'importe quoi. Le programme est explicite : tout exposé théorique est exclu. On apprend ces notions en s'en servant, et on y reviendra tout au long de l'année, à mesure que les chapitres en fourniront des exemples.

1.1 Éléments de logique

1.1.1 Propositions et connecteurs

Définition 1.1Proposition

Une proposition est un énoncé mathématique auquel on peut attribuer une valeur de vérité : vrai ou faux, et une seule.

« $2 + 2 = 4$ » est une proposition vraie, « $2$ est rationnel » une proposition fausse. « $x > 3$ » n'en est pas une tant que $x$ n'est pas fixé : sa vérité dépend de $x$ .

Définition 1.2Connecteurs « et », « ou »

Soient $P$ et $Q$ deux propositions.

« $P$ et $Q$ » est vraie lorsque $P$ et $Q$ sont toutes deux vraies.
« $P$ ou $Q$ » est vraie lorsque l'une au moins des deux est vraie.

AttentionLe « ou » n'est pas exclusif

En mathématiques, « $P$ ou $Q$ » reste vraie quand $P$ et $Q$ le sont toutes deux. « Ce menu comprend un dessert ou un café » se comprend, dans la vie courante, comme un choix ; en mathématiques, il n'en est rien. Ainsi $x^{2} = x$ équivaut à « $x = 0$ ou $x = 1$ », et ce « ou » n'interdit rien : il se trouve simplement qu'aucun réel ne vérifie les deux à la fois.

1.1.2 Quantificateurs

Définition 1.3Quantificateurs

Soit $P (x)$ une proposition dépendant d'un élément $x$ d'un ensemble $E$ .

$\forall x \in E, P (x)$ se lit « pour tout $x$ de $E$ , $P (x)$ » : quantificateur universel.
$\exists x \in E, P (x)$ se lit « il existe $x$ dans $E$ tel que $P (x)$ » : quantificateur existentiel.

ImportantLes quantificateurs ne sont pas des abréviations

$\forall$ et $\exists$ servent à écrire un énoncé avec précision, jamais à gagner de la place. On n'écrit pas « $\exists$ solution » au milieu d'une phrase française : on écrit « il existe une solution ». Le symbole n'apparaît que dans un énoncé formel, où l'ordre des quantificateurs porte du sens.

AttentionL'ordre des quantificateurs change tout

Comparons deux énoncés sur les réels :

$\forall x \in R, \exists y \in R, y > x et \exists y \in R, \forall x \in R, y > x .$

Le premier est vrai : à chaque $x$ on associe $y = x + 1$ , qui dépend de $x$ . Le second affirme qu'un même $y$ dépasse tous les réels à la fois : il est faux. Les mêmes symboles, échangés, disent le contraire.

iRemarqueLes quantifications implicites

« La fonction carré est positive » signifie en réalité « $\forall x \in R, x^{2} \geq 0$ ». Beaucoup d'énoncés portent ainsi un « pour tout » que l'on ne prononce pas. Savoir le rétablir est indispensable, en particulier pour nier l'énoncé.

1.1.3 Implication, réciproque, contraposée

Définition 1.4Proposition conditionnelle

La proposition « $P \Rightarrow Q$ » (si $P$ alors $Q$ ) est fausse uniquement lorsque $P$ est vraie et $Q$ fausse. On lui associe :

sa réciproque : $Q \Rightarrow P$ ;
sa contraposée : $non Q \Rightarrow non P$ ;
sa négation : $P$ et $non Q$ .

Lorsque $P \Rightarrow Q$ et $Q \Rightarrow P$ sont toutes deux vraies, on écrit $P \Leftrightarrow Q$ : $P$ et $Q$ sont équivalentes.

Proposition 1.5Une implication et sa contraposée disent la même chose

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 dans le cas « $P$ vraie et $Q$ fausse ». Or c'est exactement le seul cas où « non $Q$ » est vraie et « non $P$ » fausse, c'est-à-dire le seul cas où la contraposée est fausse. Les deux propositions sont donc fausses en même temps, donc vraies en même temps.

On visualise commodément « $P \Rightarrow Q$ » par une inclusion : l'ensemble des cas où $P$ est vraie est contenu dans celui où $Q$ l'est. La contraposée se lit alors sur le même dessin, vu de l'extérieur.

AttentionRéciproque

\neq =

contraposée

Une implication vraie a toujours une contraposée vraie, mais sa réciproque peut être fausse. « Si $x = 2$ alors $x^{2} = 4$ » est vraie ; sa contraposée « si $x^{2} \neq = 4$ alors $x \neq = 2$ » est vraie ; sa réciproque « si $x^{2} = 4$ alors $x = 2$ » est fausse, comme le montre $x = - 2$ .

Définition 1.6Condition nécessaire, condition suffisante

Si $P \Rightarrow Q$ , on dit que $P$ est une condition suffisante de $Q$ , et que $Q$ est une condition nécessaire de $P$ .

Exemple 1.7Lire une implication dans les deux sens

« Si une fonction est dérivable en $a$ , alors elle est continue en $a$ . » La dérivabilité est donc suffisante pour la continuité ; la continuité est nécessaire à la dérivabilité. Autrement dit : pour espérer dériver, il faut d'abord être continu — mais l'être ne suffit pas.

1.1.4 Nier une proposition

Proposition 1.8Règles de négation

Soient $P$ et $Q$ deux propositions et $P (x)$ une proposition dépendant de $x \in E$ :

$non (P et Q) non (P ou Q) non (\forall x \in E, P (x)) non (\exists x \in E, P (x)) e ˊ quivaut a ˋ e ˊ quivaut a ˋ e ˊ quivaut a ˋ e ˊ quivaut a ˋ (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

Pour nier un énoncé quantifié : on échange les quantificateurs ( $\forall$ devient $\exists$ et réciproquement), en conservant leur ordre, et on nie la proposition finale.

Exemple 1.9Nier «

f

est majorée »

« $f$ est majorée sur $R$ » s'écrit $\exists M \in R, \forall x \in R, f (x) \leq M$ . Sa négation est

$\forall M \in R, \exists x \in R, f (x) > M,$

c'est-à-dire : quel que soit le seuil qu'on se donne, $f$ le dépasse quelque part. Remarquez que le $x$ dépend maintenant de $M$ — l'ordre a été conservé.

1.2 Quelques types de raisonnement

Définition 1.10Trois raisonnements courants

Disjonction des cas : pour établir $P$ , on partage la situation en cas qui couvrent tout, et on démontre $P$ dans chacun.
Contraposée : pour établir $P \Rightarrow Q$ , on démontre $non Q \Rightarrow non P$ .
Absurde : pour établir $P$ , on suppose « non $P$ » et on en déduit une contradiction.

Exemple 1.11Disjonction des cas

Montrons que pour tout réel $x$ , $∣ x ∣ \geq x$ . Si $x \geq 0$ , alors $∣ x ∣ = x$ et l'inégalité est une égalité. Si $x < 0$ , alors $∣ x ∣ = - x > 0 > x$ . Les deux cas couvrent $R$ : l'inégalité est établie.

Exemple 1.12Contraposée

Montrons que si $n^{2}$ est impair, alors $n$ est impair ( $n \in N$ ). La contraposée s'énonce : si $n$ est pair, alors $n^{2}$ est pair. Or si $n = 2 k$ , alors $n^{2} = 4 k^{2} = 2 (2 k^{2})$ , qui est pair. La contraposée est vraie, donc l'implication de départ aussi.

Exemple 1.13Absurde

Montrons que $2$ n'est pas rationnel. Supposons le contraire : $2 = p / q$ avec $p, q$ entiers, $q \neq = 0$ , et la fraction irréductible. Alors $p^{2} = 2 q^{2}$ , donc $p^{2}$ est pair, donc $p$ est pair (exemple précédent, par contraposée), disons $p = 2 k$ . Il vient $4 k^{2} = 2 q^{2}$ , soit $q^{2} = 2 k^{2}$ : $q$ est pair à son tour. Mais $p$ et $q$ sont alors tous deux divisibles par $2$ , ce qui contredit l'irréductibilité. L'hypothèse est donc intenable.

iRemarqueLe contre-exemple

Pour montrer qu'une proposition universelle est fausse, un seul contre-exemple suffit — c'est exactement la règle de négation du $\forall$ . En revanche, aucun nombre d'exemples ne démontre une proposition universelle.

1.3 Raisonnement par récurrence

◆Théorème 1.14Principe 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}$ l'implication $P (n) \Rightarrow P (n + 1)$ est vraie, alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

ImportantUne rédaction en trois temps

Initialisation : on vérifie $P (n_{0})$ — ce n'est jamais facultatif. Hérédité : on suppose $P (n)$ vraie pour un $n \geq n_{0}$ fixé, et l'on démontre $P (n + 1)$ . Conclusion : on invoque le principe. Sauter l'initialisation permet de « démontrer » n'importe quoi : l'hérédité seule ne fait que propager, elle ne fait pas démarrer.

1.3.1 Sommes et produits

Définition 1.15Notations

\sum

\prod

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

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

Plus généralement, si $A$ est un sous-ensemble fini de $N$ ou de $N^{2}$ , $α \in A \sum u_{α}$ désigne la somme des $u_{α}$ pour $α$ parcourant $A$ .

iRemarqueL'indice est muet

$\sum_{i = 1}^{n} u_{i}$ et $\sum_{k = 1}^{n} u_{k}$ désignent le même nombre : le nom de l'indice ne sort pas de la somme. En revanche $n$ , lui, en sort — écrire $\sum_{i = 1}^{n} u_{n}$ est presque toujours une erreur de recopie.

Proposition 1.16Deux sommes à connaître

Pour tout entier $n \geq 1$ :

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

Démonstration

Démontrons la première par récurrence. Pour $n = 1$ , la somme vaut $1$ et la formule donne $\frac{1 \times 2}{2} = 1$ : l'initialisation est acquise. Supposons la formule vraie pour un $n \geq 1$ fixé. Alors

$k = 1 \sum n + 1 k = (k = 1 \sum n k) + (n + 1) = \frac{n ( n + 1 )}{2} + (n + 1) = (n + 1) (\frac{n}{2} + 1) = \frac{( n + 1 ) ( n + 2 )}{2},$

qui est bien la formule au rang $n + 1$ . La seconde se démontre de même, en partant de $\sum_{k = 1}^{n + 1} k^{2} = \sum_{k = 1}^{n} k^{2} + (n + 1)^{2}$ .

La première de ces deux formules se voit sans calcul. Empilons $1$ point, puis $2$ , puis $3$ … jusqu'à $n$ : on obtient un triangle de $\sum_{k = 1}^{n} k$ points. Deux tels triangles, l'un retourné sur l'autre, forment un rectangle $n \times (n + 1)$ .

Python : Vérifier une formule avant de la démontrer

Une somme se calcule en quelques lignes. Le programme ne demande pas de démontrer avec Python — il demande de savoir s'en servir pour explorer.


def somme_k(n):
    s = 0
    for k in range(1, n + 1):
        s = s + k
    return s

for n in [1, 5, 10, 100]:
    print(n, somme_k(n), n * (n + 1) // 2)

Les deux colonnes coïncident : la formule est plausible. Elle n'est démontrée que par la récurrence ci-dessus — aucun nombre d'essais ne remplace l'hérédité.

1.4 Ensembles et parties

Définition 1.17Ensemble, appartenance, inclusion

Un ensemble est une collection d'objets, ses éléments. On écrit $x \in E$ si $x$ est élément de $E$ , et $x \in / E$ sinon. Un ensemble $A$ est un sous-ensemble (ou une partie) de $E$ , noté $A \subset E$ , lorsque tout élément de $A$ est élément de $E$ :

$A \subset E signifie \forall x, (x \in A \Rightarrow x \in E) .$

L'ensemble de toutes les parties de $E$ est noté $P (E)$ .

ImportantDémontrer une égalité d'ensembles

Pour établir $A = B$ , on démontre les deux inclusions $A \subset B$ et $B \subset A$ . C'est la méthode par défaut, et elle consiste toujours à partir d'un élément quelconque de l'un pour montrer qu'il est dans l'autre.

Exemple 1.18Éléments et parties, à ne pas confondre

Si $E = {1, 2}$ , alors $P (E) = {\emptyset, {1}, {2}, {1, 2}}$ . On a $1 \in E$ et ${1} \subset E$ , mais $1 \neq \subset E$ et ${1} \in / E$ . En revanche ${1} \in P (E)$ .

Définition 1.19Opérations sur les parties

Soient $A$ et $B$ deux parties d'un ensemble $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 le complémentaire de $A$ dans $E$ est $A = {x \in E ∣ x \in / A}$ .

iRemarqueLes opérations ensemblistes sont les connecteurs logiques

$\cup$ traduit « ou », $\cap$ traduit « et », le complémentaire traduit la négation. Ce n'est pas une analogie : les propriétés de l'un se lisent sur l'autre, comme le montre le théorème suivant.

◆Théorème 1.20Lois de De Morgan

Pour toutes parties $A$ et $B$ d'un ensemble $E$ :

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

Démonstration

Soit $x \in E$ . Dire que $x \in A \cup B$ , c'est dire que $x$ n'appartient pas à $A \cup B$ , donc que la proposition « $x \in A$ ou $x \in B$ » est fausse. Par la règle de négation du « ou », cela équivaut à « $x \in / A$ et $x \in / B$ », c'est-à-dire $x \in A \cap B$ . Les deux ensembles ont donc les mêmes éléments. La seconde égalité s'obtient de la même façon, en niant un « et ».

Définition 1.21Produit cartésien

Le produit cartésien de deux ensembles $E$ et $F$ est l'ensemble des couples :

$E \times F = {(x, y) ∣ x \in E et y \in F} .$

On note $R^{2} = R \times R$ et, plus généralement, $R^{n}$ l'ensemble des $n$ -uplets $(x_{1}, \dots, x_{n})$ de réels.

AttentionUn couple n'est pas une paire

Dans un couple, l'ordre compte : $(1, 2) \neq = (2, 1)$ , alors que ${1, 2} = {2, 1}$ . C'est précisément ce qui permet à $R^{2}$ de représenter le plan.

1.5 Applications

Définition 1.22Application

Une application $f$ de $E$ dans $F$ associe à tout élément $x$ de $E$ un unique élément de $F$ , noté $f (x)$ . On écrit $f : E \to F$ . L'ensemble $E$ est l'ensemble de départ, $F$ l'ensemble d'arrivée.

Définition 1.23Composition

Si $f : E \to F$ et $g : F \to G$ , la composée $g \circ f : E \to G$ est définie par $(g \circ f) (x) = g (f (x))$ pour tout $x \in E$ .

AttentionL'ordre de lecture

$g \circ f$ applique d'abord $f$ , ensuite $g$ . La notation se lit de droite à gauche, à rebours de l'ordre des opérations.

Définition 1.24Injection, surjection, bijection

Soit $f : E \to F$ .

$f$ est injective si deux éléments distincts de $E$ ont des images distinctes : $\forall (x, x^{'}) \in E^{2}, f (x) = f (x^{'}) \Rightarrow x = x^{'}$ .
$f$ est surjective si tout élément de $F$ est atteint : $\forall y \in F, \exists x \in E, y = f (x)$ .
$f$ est bijective si elle est à la fois injective et surjective : tout $y \in F$ admet alors un unique antécédent, ce qui définit l'application réciproque $f^{- 1} : F \to E$ .

Exemple 1.25Le même calcul, trois réponses

Considérons $x \mapsto x^{2}$ .

De $R$ dans $R$ : ni injective ( $1$ et $- 1$ ont même image), ni surjective ( $- 1$ n'est pas atteint).
De $R_{+}$ dans $R$ : injective, mais toujours pas surjective.
De $R_{+}$ dans $R_{+}$ : bijective, de réciproque $y \mapsto y$ .

Injectivité et surjectivité ne sont pas des propriétés de la formule : elles dépendent des ensembles de départ et d'arrivée.

Proposition 1.26Composée de deux bijections

Si $f : E \to F$ et $g : F \to G$ sont bijectives, alors $g \circ f$ est bijective et

$(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1} .$

Démonstration

Posons $h = f^{- 1} \circ g^{- 1}$ . Pour $z \in G$ , $(g \circ f) \circ h (z) = g (f (f^{- 1} (g^{- 1} (z)))) = g (g^{- 1} (z)) = z$ , et de même $h \circ (g \circ f) (x) = x$ pour $x \in E$ . L'application $g \circ f$ admet donc une réciproque, c'est $h$ : elle est bijective.

iRemarqueL'ordre s'inverse

On enfile ses chaussettes puis ses chaussures ; pour défaire, on retire les chaussures puis les chaussettes. La réciproque d'une composée inverse l'ordre des opérations — c'est le sens de $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ .

1.6 L'essentiel du chapitre

Fiche de synthèse

Logique : le « ou » est inclusif ; l'ordre des quantificateurs porte du sens ; une implication équivaut à sa contraposée, jamais à sa réciproque ; $P$ suffisante pour $Q$ , $Q$ nécessaire à $P$ .
Nier : échanger $\forall$ et $\exists$ en conservant leur ordre, puis nier la conclusion. Un contre-exemple suffit à infirmer un « pour tout ».
Raisonnements : disjonction des cas, contraposée, absurde.
Récurrence : initialisation, hérédité à $n$ fixé, conclusion. L'initialisation n'est jamais facultative.
Sommes : $\sum_{k = 1}^{n} k = \frac{n ( n + 1 )}{2}$ et $\sum_{k = 1}^{n} k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ ; l'indice est muet.
Ensembles : $A = B$ se démontre par double inclusion ; De Morgan est la négation d'un « ou » et d'un « et » ; $P (E)$ a pour éléments les parties de $E$ .
Applications : injective, surjective, bijective — cela dépend des ensembles de départ et d'arrivée ; $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ .

Continuer sur Adloun : animation, QCM, fiches, exercices