Raisonnement et vocabulaire ensembliste

Cours · mathématiques MPSI, chapitre 1 · MPSI (classe préparatoire scientifique) · le début du chapitre, la suite sur Adloun

Deux ensembles A et B et leur intersection.

1.1 Introduction et motivation

La logique et la théorie des ensembles constituent les fondations du langage mathématique moderne. Formulées à la fin du XIX^e siècle par des mathématiciens comme Georg Cantor et Gottlob Frege, elles permettent de structurer le raisonnement de façon rigoureuse, d'éviter les ambiguïtés du langage naturel et de définir précisément les objets mathématiques (nombres, fonctions, espaces vectoriels).

Ce chapitre introduit :

les rudiments de la logique propositionnelle et les principaux modes de raisonnement mathématiques ;
le vocabulaire de base de la théorie des ensembles et les opérations associées ;
la notion d'application d'un ensemble dans un autre, ainsi que ses propriétés fondamentales (injectivité, surjectivité, bijectivité) ;
l'étude des relations binaires sur un ensemble (relations d'équivalence et relations d'ordre).

L'assimilation de ces notions de vocabulaire et de raisonnement constitue un objectif majeur pour le premier semestre de la classe préparatoire MPSI.

1.2 Rudiments de logique

1.2.1 Assertions et connecteurs logiques

Une assertion (ou proposition) est un énoncé mathématique auquel on peut attribuer, de manière exclusive, l'une des deux valeurs de vérité : vrai (V) ou faux (F).

Définition 1.1Connecteurs logiques

Soient $P$ et $Q$ deux assertions. On définit les connecteurs logiques usuels :

Nom	Symbole	Signification
Négation	$\neg P$ ou $non P$	Est vraie si et seulement si $P$ est fausse.
Conjonction	$P \land Q$ ou $P et Q$	Est vraie si et seulement si $P$ et $Q$ sont toutes deux vraies.
Disjonction	$P \lor Q$ ou $P ou Q$	Est vraie si au moins l'une des deux assertions $P$ ou $Q$ est vraie.
Implication	$P \Rightarrow Q$	Définie par $(\neg P) \lor Q$ . Elle se lit " $P$ implique $Q$ ".
Équivalence	$P \Leftrightarrow Q$	Définie par $(P \Rightarrow Q) \land (Q \Rightarrow P)$ . Elle se lit " $P$ équivaut à $Q$ ".

On peut dresser la table de vérité de ces connecteurs :

$P$	$Q$	$\neg P$	$P \land Q$	$P \lor Q$	$P \Rightarrow Q$	$P \Leftrightarrow Q$
V	V	F	V	V	V	V
V	F	F	F	V	F	F
F	V	V	F	V	V	F
F	F	V	F	F	V	V

iRemarqueContraposée et réciproque

Pour une implication $P \Rightarrow Q$ :

sa contraposée est l'implication $\neg Q \Rightarrow \neg P$ . Elle est logiquement équivalente à $P \Rightarrow Q$ .
sa réciproque est l'implication $Q \Rightarrow P$ . Elle n'est pas logiquement équivalente à l'implication directe en général.

Proposition 1.2Lois de De Morgan

Pour toutes assertions $P$ et $Q$ , on a les équivalences logiques suivantes (appelées tautologies) :

$\neg (P \land Q) \Leftrightarrow (\neg P) \lor (\neg Q)$
$\neg (P \lor Q) \Leftrightarrow (\neg P) \land (\neg Q)$

1.2.2 Quantificateurs

En mathématiques, les assertions dépendent souvent d'une variable évoluant dans un ensemble. On parle alors de prédicats. Pour exprimer ces assertions, on utilise des quantificateurs.

Définition 1.3Quantificateurs

Soit $E$ un ensemble et $P (x)$ un prédicat dépendant d'une variable $x \in E$ .

Quantificateur universel ( $\forall$ , se lit "pour tout") : l'assertion $\forall x \in E, P (x)$ est vraie si le prédicat $P (x)$ est vrai pour tous les éléments $x$ de $E$ .
Quantificateur existentiel ( $\exists$ , se lit "il existe") : l'assertion $\exists x \in E, P (x)$ est vraie s'il existe au moins un élément $x$ de $E$ pour lequel $P (x)$ est vrai.
S'il existe un unique élément $x \in E$ vérifiant $P (x)$ , on note $\exists! x \in E, P (x)$ .

Important

L'emploi des symboles $\forall$ et $\exists$ en guise d'abréviations dans les phrases rédigées en langage naturel est formellement exclu. Ils doivent être réservés exclusivement aux formules mathématiques formelles.

Proposition 1.4Négation des quantificateurs

Soit $P (x)$ un prédicat sur $E$ . On a les équivalences de négation :

$\neg (\forall x \in E, P (x)) \Leftrightarrow \exists x \in E, \neg P (x)$
$\neg (\exists x \in E, P (x)) \Leftrightarrow \forall x \in E, \neg P (x)$

1.2.3 Modes de raisonnement

Pour rédiger des démonstrations rigoureuses, le mathématicien utilise différents modes de raisonnement.

Raisonnement par disjonction des cas

Si on veut montrer qu'une propriété $P (x)$ est vraie pour tout $x \in E$ , on peut partitionner $E$ en sous-ensembles et traiter séparément chaque cas.

Exemple 1.5

Montrer que pour tout $n \in Z$ , le nombre $n (n + 1)$ est pair.

Cas 1 : $n$ est pair. Alors il existe $k \in Z$ tel que $n = 2 k$ . D'où $n (n + 1) = 2 k (2 k + 1) = 2 [k (2 k + 1)]$ , qui est pair.
Cas 2 : $n$ est impair. Alors il existe $k \in Z$ tel que $n = 2 k + 1$ . D'où $n (n + 1) = (2 k + 1) (2 k + 2) = 2 (2 k + 1) (k + 1)$ , qui est pair.

Dans tous les cas, le nombre est pair.

Raisonnement par contraposition

Pour montrer que $P \Rightarrow Q$ , on démontre sa contraposée $\neg Q \Rightarrow \neg P$ , souvent plus simple à aborder.

Exemple 1.6

Soit $n \in N$ . Montrer que si $n^{2}$ est impair, alors $n$ est impair. Par contraposition, supposons que $n$ n'est pas impair, donc que $n$ est pair. Il existe $k \in N$ tel que $n = 2 k$ . Alors $n^{2} = (2 k)^{2} = 4 k^{2} = 2 (2 k^{2})$ , qui est pair. Ainsi, la contraposée est démontrée, donc l'assertion d'origine est vraie.

Raisonnement par l'absurde

Pour montrer qu'une assertion $P$ est vraie, on suppose que sa négation $\neg P$ est vraie et on cherche à en déduire une contradiction logique.

Exemple 1.7

Montrer que $2 \in / Q$ . Supposons par l'absurde que $2 \in Q$ . Alors il existe $p \in Z$ et $q \in N^{*}$ tels que $2 = \frac{p}{q}$ , la fraction étant irréductible. En élevant au carré, $2 = \frac{p ^{2}}{q ^{2}}$ , soit $p^{2} = 2 q^{2}$ . Donc $p^{2}$ est pair, ce qui implique $p$ pair. On pose $p = 2 k$ . Alors $4 k^{2} = 2 q^{2}$ , d'où $q^{2} = 2 k^{2}$ . Donc $q^{2}$ est pair, ce qui implique $q$ pair. Ainsi $p$ et $q$ sont tous deux pairs, ce qui contredit le fait que la fraction $\frac{p}{q}$ est irréductible. L'hypothèse de départ est fausse, d'où $2 \in / Q$ .

Raisonnement par analyse-synthèse

Ce mode est utilisé pour déterminer l'ensemble des solutions d'un problème ou prouver l'existence et l'unicité d'un objet.

L'analyse (Condition Nécessaire) : On suppose qu'une solution existe et on étudie ses propriétés nécessaires pour restreindre les candidats possibles.
La synthèse (Condition Suffisante) : On teste les candidats retenus pour vérifier s'ils conviennent effectivement au problème d'origine.

1.2.4 Raisonnement par récurrence

Le raisonnement par récurrence repose sur la structure fondamentale des entiers naturels.

Proposition 1.8Propriété du bon ordre de

N

Toute partie non vide de $N$ possède un plus petit élément.

◆Théorème 1.9Récurrence simple

Soit $n_{0} \in N$ et $P (n)$ une propriété dépendant de $n \geq n_{0}$ . Si :

Initialisation : $P (n_{0})$ est vraie,
Hérédité : pour tout entier $n \geq n_{0}$ , si $P (n)$ est vraie, alors $P (n + 1)$ est vraie,

alors la propriété $P (n)$ est vraie pour tout $n \geq n_{0}$ .

◆Théorème 1.10Variantes de la récurrence

Soit $P (n)$ un prédicat sur $n \geq n_{0}$ :

Récurrence double : Si $P (n_{0})$ et $P (n_{0} + 1)$ sont vraies, et si pour tout $n \geq n_{0}$ , $[P (n) \land P (n + 1)] \Rightarrow P (n + 2)$ , alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .
Récurrence forte : Si $P (n_{0})$ est vraie, et si pour tout $n \geq n_{0}$ , $[\forall k \in [[n_{0}, n]], P (k)] \Rightarrow P (n + 1)$ , alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Exercices du chapitre

La barre de Sheffer corrigé
Une équation fonctionnelle, par analyse-synthèse corrigé
Renforcer l'hypothèse de récurrence corrigé
Quatre équations dans $P (E)$ corrigé
Trois inclusions et ce qu'elles mesurent corrigé
Inverses à gauche et à droite corrigé

La suite du cours · Tous les exercices du chapitre