Raisonnement et vocabulaire ensembliste

Cours · mathématiques approfondies (ECG 1re année), chapitre 1 · prépa ECG, 1re année · le début du chapitre, la suite sur Adloun

Deux ensembles A et B et leur intersection.

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.

Exercices du chapitre

Quantifier, puis nier corrigé
Contraposer, puis raisonner par l'absurde corrigé
Somme des carrés corrigé
Divisibilité par 3 corrigé
L'inégalité de Bernoulli, et son hypothèse corrigé
Une somme et un produit corrigé

La suite du cours · Tous les exercices du chapitre