Raisonnement, ensembles et applications

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

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

Ce premier chapitre ne contient presque aucun résultat nouveau. Il installe la langue dans laquelle tout le reste de l'année sera écrit : ce que veut dire « si … alors », ce que nie une phrase, ce qu'est un ensemble, ce qu'est une application.

AttentionCe chapitre n'est pas un cours de logique

Le programme est net : « Ces outils ne doivent pas faire l'objet d'un exposé théorique », et « tout exposé théorique sur le raisonnement par récurrence est exclu ». On apprend donc ces mots en s'en servant, sur des exemples pris dans les autres chapitres — jamais pour eux-mêmes.

1.1 La langue des propositions

Définition 1.1Proposition

Une proposition est un énoncé dont on peut dire, sans ambiguïté, qu'il est vrai ou qu'il est faux.

« $3 > 2$ » est une proposition vraie. « $3 < 2$ » est une proposition fausse. « $x > 2$ » n'en est pas une tant qu'on n'a pas dit ce qu'est $x$ .

Définition 1.2Les connecteurs « et », « ou »

Soient $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.

ImportantLe « ou » des mathématiques n'exclut pas

Dans la langue courante, « fromage ou dessert » veut dire l'un ou l'autre, pas les deux. En mathématiques, « $x = 1$ ou $x = 2$ » reste vraie si les deux le sont — cela n'arrive simplement jamais ici, puisqu'un nombre ne vaut pas à la fois $1$ et $2$ .

La règle est simple et sans exception : le « ou » mathématique est inclusif.

1.1.1 Implication, réciproque, contraposée, négation

Définition 1.3Proposition conditionnelle

La proposition « $P \Rightarrow Q$ », lue « $P$ implique $Q$ » ou « si $P$ alors $Q$ », est fausse dans un seul cas : $P$ vraie et $Q$ fausse.

À partir d'elle on en forme trois autres :

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

◆Théorème 1.4Une implication et sa contraposée disent la même chose

Pour toutes propositions $P$ et $Q$ , 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$ est fausse exactement quand $P$ est vraie et $Q$ fausse. Or $non Q \Rightarrow non P$ est fausse exactement quand $non Q$ est vraie et $non P$ fausse, c'est-à-dire quand $Q$ est fausse et $P$ vraie. C'est le même cas ; dans tous les autres, les deux sont vraies.

ImportantCondition nécessaire, condition suffisante

Quand $P \Rightarrow Q$ est vraie, on dit que

$P$ est une condition suffisante de $Q$ : il suffit d'avoir $P$ pour avoir $Q$ ;
$Q$ est une condition nécessaire de $P$ : sans $Q$ , pas de $P$ .

Les deux phrases décrivent la même implication, vue de ses deux bouts.

Exemple 1.5Sur un cas où l'on ne se trompe pas

« Si une entreprise est cotée en bourse, alors elle publie des comptes annuels. » Publier des comptes est nécessaire pour être cotée ; être cotée est suffisant pour publier des comptes.

La réciproque est fausse : beaucoup d'entreprises publient des comptes sans être cotées. La contraposée, elle, est vraie : une entreprise qui ne publie pas de comptes annuels n'est pas cotée.

AttentionLa réciproque n'est pas la contraposée

C'est la confusion la plus fréquente de l'année, et elle coûte cher : la contraposée est toujours vraie en même temps que l'implication, la réciproque n'a aucune raison de l'être. Les deux se ressemblent parce qu'on y échange $P$ et $Q$ ; mais dans la contraposée, on les nie aussi.

1.1.2 Les quantificateurs

Définition 1.6Pour tout, il existe

$\forall$ se lit « pour tout » ; $\exists$ se lit « il existe ». La négation échange les deux :

$non (\forall x, P (x)) = \exists x, non P (x), non (\exists x, P (x)) = \forall x, non P (x) .$

AttentionLes quantificateurs ne sont pas des abréviations

Le programme l'écrit noir sur blanc : « l'emploi des quantificateurs en guise d'abréviations est exclu ». On n'écrit donc pas « $\forall$ entreprise du secteur » au milieu d'une phrase : $\forall$ et $\exists$ servent à formuler un énoncé mathématique et sa négation, pas à gagner de la place.

Exemple 1.7L'ordre des quantificateurs change tout

Comparons deux phrases construites avec les mêmes symboles :

$\forall x \in R, \exists n \in N, n > x et \exists n \in N, \forall x \in R, n > x .$

La première est vraie. Prenons $x$ réel ; l'entier $n$ obtenu en arrondissant $x$ à l'entier supérieur puis en ajoutant $1$ convient. Ici $n$ dépend de $x$ , et c'est permis : le $\exists$ vient après le $\forall$ .

La seconde est fausse. Elle affirmerait qu'un même entier $n$ dépasse tous les réels à la fois ; il suffit de prendre $x = n$ pour la mettre en défaut.

1.2 Quatre façons de démontrer

ImportantLe répertoire de l'année

Directement : on part de $P$ et l'on arrive à $Q$ .
Par contraposée : on démontre $non Q \Rightarrow non P$ , ce qui revient au même. Utile quand la négation est plus maniable que l'énoncé.
Par l'absurde : on suppose $P$ vraie et $Q$ fausse, et l'on aboutit à une contradiction.
Par disjonction des cas : on découpe la situation en cas qui couvrent tout, et l'on traite chacun.

Pour infirmer une proposition qui commence par « pour tout », un seul contre-exemple suffit — et rien d'autre n'est demandé.

Exemple 1.8Un contre-exemple suffit

« Tout nombre pair est divisible par $4$ » : $6$ est pair et n'est pas divisible par $4$ . C'est fini, la proposition est fausse. Il serait inutile — et faux — d'ajouter « et $10$ non plus, et $14$ non plus » : un seul contre-exemple abat un « pour tout ».

Exemple 1.9Par contraposée

Montrons que si $n^{2}$ est impair alors $n$ est impair.

La contraposée s'écrit : 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 démontrée, donc l'énoncé aussi.

Remarquons ce qu'on a gagné : « $n$ est pair » se manipule ( $n = 2 k$ ), « $n^{2}$ est impair » beaucoup moins.

1.2.1 Le raisonnement par récurrence

ImportantComment on l'écrit

Pour démontrer qu'une propriété $P (n)$ est vraie pour tout entier $n \geq n_{0}$ :

Initialisation : on vérifie $P (n_{0})$ .
Hérédité : on suppose $P (n)$ vraie pour un entier $n \geq n_{0}$ fixé, et l'on en déduit $P (n + 1)$ .
Conclusion : $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Les trois étapes s'écrivent, toujours, et dans cet ordre.

Exemple 1.10La somme des premiers entiers

Montrons que pour tout $n \geq 1$ : $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ .

Initialisation. Pour $n = 1$ : la somme vaut $1$ , et $\frac{1 \times 2}{2} = 1$ . Acquise.

Hérédité. Supposons la formule vraie pour un $n \geq 1$ fixé. Alors

$1 + 2 + \dots + n + (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$ .

Conclusion. Par récurrence, la formule vaut pour tout $n \geq 1$ .

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


def somme(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(n), n*(n + 1)//2)
# 1 1 1 / 5 15 15 / 10 55 55 / 100 5050 5050

La machine corrobore la formule sur quatre valeurs ; elle ne la démontre pas. Un million de vérifications ne diraient rien du rang suivant — c'est exactement le travail que fait la récurrence, et qu'aucun ordinateur ne fera.

1.3 Ensembles

Définition 1.11Ensemble, appartenance, inclusion

Un ensemble est une collection d'objets, appelés ses éléments. On écrit $x \in E$ si $x$ est élément de $E$ , et $x \in / E$ sinon.

$A$ est inclus dans $E$ , noté $A \subset E$ , si tout élément de $A$ est élément de $E$ ; on dit aussi que $A$ est une partie de $E$ . L'ensemble vide, noté $\emptyset$ , n'a aucun élément ; il est inclus dans tout ensemble.

Définition 1.12Réunion, intersection, complémentaire

Soient $A$ et $B$ deux parties d'un ensemble $E$ .

$A \cup B$ (réunion) : les éléments qui sont dans $A$ ou dans $B$ .
$A \cap B$ (intersection) : ceux qui sont dans $A$ et dans $B$ .
$A$ (complémentaire de $A$ dans $E$ ) : ceux de $E$ qui ne sont pas dans $A$ .

$A$ et $B$ sont disjoints lorsque $A \cap B = \emptyset$ .

◆Théorème 1.13Lois 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'est ni dans $A$ ni dans $B$ , donc qu'il est à la fois dans $A$ et dans $B$ : c'est exactement $x \in A \cap B$ . La seconde égalité se démontre de la même façon.

On reconnaît la négation d'un « ou », qui donne un « et » : les opérations sur les ensembles et les connecteurs logiques sont les mêmes règles, écrites deux fois.

Définition 1.14Ensemble des parties

L'ensemble de toutes les parties de $E$ se note $P (E)$ . Ses éléments sont des ensembles.

Exemple 1.15Les huit parties d'un ensemble à trois éléments

Pour $E = {a, b, c}$ :

$P (E) = {\emptyset, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} .$

Il y en a $8$ . On remarquera que $\emptyset$ et $E$ lui-même en font partie, et qu'écrire $a \in P (E)$ serait une faute : c'est ${a}$ qui appartient à $P (E)$ , pas $a$ .

Définition 1.16Produit cartésien

Le produit cartésien $A \times B$ est l'ensemble des couples $(x, y)$ avec $x \in A$ et $y \in B$ . On note $R^{2} = R \times R$ , et plus généralement $R^{n}$ l'ensemble des $n$ -uplets de réels.

1.3.1 Compter les éléments

Définition 1.17Cardinal

Le cardinal d'un ensemble fini $E$ , noté $Card (E)$ , est son nombre d'éléments.

◆Théorème 1.18Trois formules, et rien de plus

Soient $A$ et $B$ deux ensembles finis.

Si $A$ et $B$ sont disjoints : $Card (A \cup B) = Card (A) + Card (B)$ .
Dans tous les cas (formule de Poincaré) :

$Card (A \cup B) = Card (A) + Card (B) - Card (A \cap B) .$

$Card (A \times B) = Card (A) \times Card (B)$ .

AttentionLe cardinal n'est ici qu'un outil pour les probabilités

Le programme est explicite : « La notion de cardinal est introduite pour son application au calcul des probabilités (uniquement dans le cas de l'équiprobabilité). Tout exercice de dénombrement pur est exclu. »

Il n'y aura donc dans ce livre ni arrangements, ni combinaisons étudiés pour eux-mêmes : on compte pour diviser par un nombre de cas, jamais pour le plaisir de compter.

Python : Les ensembles existent aussi en Python


A = {1, 2, 3, 4}
B = {3, 4, 5}

print(A | B)          # {1, 2, 3, 4, 5}   reunion
print(A & B)          # {3, 4}            intersection
print(len(A | B))     # 5
print(len(A) + len(B) - len(A & B))       # 5 : Poincare

Les deux dernières lignes donnent le même nombre, et ce n'est pas un hasard : c'est la formule de Poincaré, vérifiée sur un exemple.

1.4 Applications

Définition 1.19Application, image, antécédent

Une application $f$ de $E$ dans $F$ associe à chaque élément $x$ de $E$ un seul élément de $F$ , noté $f (x)$ et appelé l'image de $x$ .

Si $y = f (x)$ , on dit que $x$ est un antécédent de $y$ . Un élément de $F$ peut avoir plusieurs antécédents, ou aucun.

Définition 1.20Composition

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 vaut $(g \circ f) (x) = g (f (x))$ .

ImportantOn lit de droite à gauche

Dans $g \circ f$ , c'est $f$ qui agit d'abord. L'écriture inverse l'ordre de l'action, et c'est une source d'erreurs constante : relire $(g \circ f) (x) = g (f (x))$ jusqu'à ce que l'ordre devienne évident.

Définition 1.21Bijection, application réciproque

$f : E \to F$ est une bijection si tout élément de $F$ admet un et un seul antécédent dans $E$ . On peut alors définir l'application réciproque $f^{- 1} : F \to E$ , qui à chaque $y$ associe son unique antécédent.

Exemple 1.22Une bijection de

R

dans

R

Soit $f (x) = 2 x + 3$ . Cherchons les antécédents de $y$ : l'équation $2 x + 3 = y$ a pour unique solution $x = \frac{y - 3}{2}$ .

Chaque réel a donc un antécédent, et un seul : $f$ est une bijection, et $f^{- 1} (y) = \frac{y - 3}{2}$ . On vérifie que $f^{- 1} (f (x)) = \frac{( 2 x + 3 ) - 3}{2} = x$ .

AttentionCe que ce chapitre ne fera pas

Le programme écarte explicitement l'image réciproque d'une partie de l'ensemble d'arrivée : la notation $f^{- 1} (B)$ pour un ensemble $B$ n'est pas un attendu. Ici, $f^{- 1}$ ne désigne jamais que l'application réciproque d'une bijection.

Python : Une application, et sa réciproque


def f(x):
    return 2*x + 3

def g(y):
    return (y - 3)/2

for x in [-2, 0, 1.5, 7]:
    print(x, f(x), g(f(x)))
# -2 -1 -2.0 / 0 3 0.0 / 1.5 6.0 1.5 / 7 17 7.0

La troisième colonne redonne la première : $g$ défait ce que $f$ a fait. C'est la définition de l'application réciproque, mise à l'épreuve.

Continuer sur Adloun : animation, QCM, fiches, exercices