L1 maths · Chapitre 01

Logique, raisonnement, ensembles et applications

Quantificateurs, connecteurs, négation d'un énoncé, récurrence, raisonnement par l'absurde et par contraposée, analyse-synthèse, ensembles et parties, image directe et image réciproque, injectivité, surjectivité, bijectivité, relations d'équivalence et d'ordre.

Ce qu'il faut savoir faire

Quantificateurs
Connecteurs
Négation d'un énoncé
Récurrence
Raisonnement par l'absurde et par contraposée
Analyse-synthèse
Ensembles et parties
Image directe et image réciproque
Injectivité
Surjectivité
Bijectivité
Relations d'équivalence et d'ordre

Ce chapitre est le premier de l'année, et c'est le seul dont on puisse dire qu'il ne sert à rien tout seul. Il ne contient presque aucun calcul, presque aucun résultat que l'on citera plus tard sous son nom. Il fixe autre chose : la langue dans laquelle tous les autres chapitres seront écrits, et la forme que doit avoir une copie pour valoir des points.

Le passage du lycée à la première année de licence se joue exactement là. Au lycée, on répond à une question ; ici, on démontre une affirmation, et ce n'est pas la même activité. Un étudiant qui connaît son cours et rate son partiel a presque toujours perdu ses points sur ce terrain : un « soit $x$ » manquant, une réciproque démontrée à la place de l'implication demandée, un objet utilisé avant d'exister, une conclusion générale tirée d'un seul cas. La section « Comment on rédige une démonstration » est écrite pour cela, et c'est la plus importante du chapitre.

Remarque

Ce cours et votre fac. Il n'existe pas de programme national de licence de mathématiques : les contenus sont arrêtés par le conseil de chaque établissement. Ce chapitre couvre le socle commun aux maquettes consultées, celui que l'on retrouve partout, et signale par un encadré Selon les facs les quatre points qui, eux, varient d'un établissement à l'autre : le calcul propositionnel formel, l'ensemble quotient, l'ordre produit et l'ordre lexicographique, la dénombrabilité. Ils sont traités, pas écartés : mieux vaut lire une section que votre fac verra plus tard qu'ignorer une notion que votre voisin de TD connaît.

Remarque

Notations fixées une fois pour toutes. $E$ , $F$ , $G$ désignent des ensembles, $A$ , $B$ , $C$ des parties d'un ensemble, $P (E)$ l'ensemble des parties de $E$ , $\overline{A}$ le complémentaire de $A$ dans $E$ , $A ∖ B$ la différence, $c a r d (A)$ le cardinal d'un ensemble fini, $f : E \to F$ une application, ${i d}_{E}$ l'identité de $E$ , $R$ une relation binaire, notée $x R y$ , et $c l (x)$ la classe d'équivalence de $x$ .

Assertions, connecteurs et implication

Assertion et valeur de vérité

Définition

Une assertion (on dit aussi une proposition) est un énoncé mathématique dont on peut affirmer sans ambiguïté qu'il est vrai, ou qu'il est faux. On appelle valeur de vérité de l'assertion le fait qu'elle soit vraie (on note V) ou fausse (on note F).

Deux principes sont admis, et ils ne se discutent pas dans ce cours : une assertion ne peut pas être à la fois vraie et fausse (principe de non-contradiction), et elle est nécessairement l'une des deux (principe du tiers exclu).

a. « $7$ est un nombre premier » : vraie.

b. « $5 \in Q$ » : vraie.

c. « $Z \subset N$ » : fausse.

d. « $0 \in \emptyset$ » : fausse.

e. « $(- 2)^{3} = - 8$ » : vraie.

f. « $π$ est un entier » : fausse.

Définition

Un énoncé dont la valeur de vérité dépend d'une ou plusieurs variables s'appelle un prédicat, et se note $P (x)$ , $Q (x, y)$ , etc. Un prédicat devient une assertion dès que l'on fixe ses variables, ou dès qu'on les quantifie (section suivante).

On ne confond pas non plus une assertion avec une expression. « $x^{2} - 4$ » est un nombre, pas une phrase : il n'a pas de valeur de vérité, et il n'a donc aucun sens de dire qu'il est vrai. « $x^{2} - 4 = 0$ », en revanche, est un prédicat. Cette distinction, qui paraît évidente, est à l'origine d'une des fautes de rédaction les plus fréquentes de la première année : on la retrouvera en bonne place.

Les connecteurs et leurs tables de vérité

À partir d'assertions données, on en fabrique de nouvelles avec des connecteurs logiques.

Définition

Soient $P$ et $Q$ deux assertions.

La négation de $P$ , notée $\neg P$ et lue « non $P$ », est vraie lorsque $P$ est fausse, et fausse lorsque $P$ est vraie.
La conjonction $P \land Q$ , lue « $P$ et $Q$ », est vraie lorsque les deux le sont, et fausse sinon.
La disjonction $P \lor Q$ , lue « $P$ ou $Q$ », est vraie lorsque l'une au moins des deux est vraie, et fausse lorsque les deux sont fausses.

Ces définitions se lisent entièrement sur une table de vérité, qui énumère les quatre cas possibles :

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

Remarque

Le « ou » mathématique est inclusif. L'assertion $P \lor Q$ n'exclut pas que $P$ et $Q$ soient vraies en même temps. C'est une différence avec le langage courant, où « fromage ou dessert » veut dire « l'un des deux, pas les deux ». Ainsi « $6$ est pair ou $6$ est un multiple de $3$ » est une assertion vraie, alors même que les deux membres le sont.

Définition

Deux assertions $P$ et $Q$ construites sur les mêmes assertions élémentaires sont logiquement équivalentes, ce que l'on note $P \equiv Q$ , lorsqu'elles ont la même valeur de vérité dans tous les cas, c'est-à-dire lorsque leurs colonnes de table de vérité coïncident ligne à ligne.

Une assertion vraie dans tous les cas s'appelle une tautologie ; une assertion fausse dans tous les cas s'appelle une contradiction (ou antilogie).

Ainsi $P \lor \neg P$ est une tautologie, et $P \land \neg P$ une contradiction : ce sont les deux principes admis plus haut, réécrits comme des formules.

Propriété

Soient $P$ , $Q$ , $R$ trois assertions.

Double négation : $\neg (\neg P) \equiv P$ .
Commutativité : $P \land Q \equiv Q \land P$ et $P \lor Q \equiv Q \lor P$ .
Associativité : $(P \land Q) \land R \equiv P \land (Q \land R)$ , et de même pour $\lor$ .
Idempotence : $P \land P \equiv P$ et $P \lor P \equiv P$ .
Distributivité de chacun sur l'autre : $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$ , et $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$ .

Démonstration. Chacune de ces équivalences se vérifie en écrivant la table de vérité des deux membres et en constatant que les colonnes coïncident ligne à ligne : quatre lignes quand deux assertions élémentaires interviennent, huit lignes quand il y en a trois. $□$

Remarque

Selon les facs. Le calcul propositionnel présenté ici de manière formelle, avec ses tables de vérité et ses équivalences, n'est développé pour lui-même que dans une partie des maquettes de première année : certaines lui consacrent un module de logique à part entière, d'autres passent directement aux quantificateurs et emploient « et », « ou », « non » de façon intuitive, sans jamais écrire une table. Ces équivalences sont traitées ici parce que tout le reste du chapitre en dépend : nier un énoncé quantifié, comprendre pourquoi une contraposée démontre autant que l'implication de départ, savoir ce qu'il faut supposer pour un raisonnement par l'absurde reposent toutes les trois sur elles.

Implication, réciproque, contraposée, équivalence

Définition

Soient $P$ et $Q$ deux assertions. L'assertion $P \Rightarrow Q$ , lue « $P$ implique $Q$ » ou « si $P$ alors $Q$ », est par définition l'assertion $\neg P \lor Q$ .

Elle est donc fausse dans le seul cas où $P$ est vraie et $Q$ est fausse, et vraie dans les trois autres.

$P$	$Q$	$P \Rightarrow Q$	$Q \Rightarrow P$	$\neg Q \Rightarrow \neg P$
V	V	V	V	V
V	F	F	V	F
F	V	V	F	V
F	F	V	V	V

Remarque

Une implication dont l'hypothèse est fausse est vraie. L'assertion « si $1 = 2$ , alors $3 = 4$ » est vraie, et cela surprend toujours au début. Cette convention n'est pas un caprice : sans elle, l'énoncé « pour tout réel $x$ , si $x > 3$ alors $x^{2} > 9$ » ne pourrait pas être vrai, puisqu'il parle aussi des réels qui ne dépassent pas $3$ , et pour lesquels il n'y a rien à vérifier.

Définition

Soit une implication $P \Rightarrow Q$ .

Sa réciproque est l'implication $Q \Rightarrow P$ .
Sa contraposée est l'implication $\neg Q \Rightarrow \neg P$ .

Propriété

Une implication et sa contraposée sont logiquement équivalentes :

(P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P) .

Démonstration. On revient à la définition, sans passer par une table. Par définition, $P \Rightarrow Q$ est l'assertion $\neg P \lor Q$ . Toujours par définition, $\neg Q \Rightarrow \neg P$ est l'assertion $\neg (\neg Q) \lor \neg P$ , c'est-à-dire $Q \lor \neg P$ d'après la règle de double négation. Or la disjonction est commutative : $\neg P \lor Q$ et $Q \lor \neg P$ sont la même assertion. $□$

Les deux dernières colonnes du tableau ci-dessus coïncident ligne à ligne : c'est la lecture graphique du même résultat.

Remarque

Contraposée et réciproque n'ont rien à voir, et c'est la confusion la plus coûteuse du premier semestre.

La contraposée d'une implication lui est équivalente : la démontrer, c'est démontrer l'implication de départ, ni plus ni moins. C'est un changement de point de vue, pas un changement d'énoncé.

Définition

L'assertion $P ⟺ Q$ , lue « $P$ équivaut à $Q$ » ou « $P$ si et seulement si $Q$ », est vraie lorsque $P$ et $Q$ ont la même valeur de vérité, et fausse sinon.

Propriété

$(P ⟺ Q) \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ .

C'est cette propriété, et elle seule, qui justifie la phrase que vous écrirez des dizaines de fois cette année : « montrons les deux implications ». Une équivalence n'est pas un énoncé plus fort qu'une implication, c'est deux énoncés.

Remarque

L'implication n'est pas associative. On a vu que $\land$ et $\lor$ le sont, ce qui autorise à écrire $P \land Q \land R$ sans parenthèses. Rien de tel avec l'implication : les assertions $(P \Rightarrow Q) \Rightarrow R$ et $P \Rightarrow (Q \Rightarrow R)$ ne sont pas équivalentes. Prenons en effet $P$ , $Q$ et $R$ toutes les trois fausses : alors $P \Rightarrow Q$ est vraie, donc la première assertion est une implication d'hypothèse vraie et de conclusion fausse, donc fausse ; la seconde, elle, a une hypothèse fausse, donc elle est vraie. Une écriture $P \Rightarrow Q \Rightarrow R$ n'a donc pas de sens tant qu'on n'a pas dit où sont les parenthèses.

Propriété

Transitivité de l'implication (syllogisme). L'assertion $((P \Rightarrow Q) \land (Q \Rightarrow R)) \Rightarrow (P \Rightarrow R)$ est une tautologie.

C'est la règle qui autorise l'enchaînement de déductions d'une démonstration : chaque « donc » est une application de ce résultat.

Négation : lois de De Morgan et négation d'une implication

Propriété

Lois de De Morgan logiques. Pour toutes assertions $P$ et $Q$ :

\neg (P \land Q) \equiv \neg P \lor \neg Q, \neg (P \lor Q) \equiv \neg P \land \neg Q .

Démonstration. Établissons la première. L'assertion $\neg (P \land Q)$ est vraie exactement lorsqu'il est faux que $P$ et $Q$ soient vraies simultanément, c'est-à-dire lorsque l'une au moins des deux est fausse : c'est exactement $\neg P \lor \neg Q$ . Les deux assertions sont donc vraies dans les mêmes cas.

Pour la seconde, appliquons la première à $\neg P$ et $\neg Q$ : elle donne $\neg (\neg P \land \neg Q) \equiv P \lor Q$ , en utilisant deux fois la double négation. En niant les deux membres, il vient $\neg P \land \neg Q \equiv \neg (P \lor Q)$ , ce qui est le résultat annoncé. $□$

Propriété

Négation d'une implication. Pour toutes assertions $P$ et $Q$ :

\neg (P \Rightarrow Q) \equiv P \land \neg Q .

Démonstration. Par définition, $P \Rightarrow Q$ est l'assertion $\neg P \lor Q$ . Sa négation est donc, d'après la seconde loi de De Morgan, l'assertion $\neg (\neg P) \land \neg Q$ , c'est-à-dire $P \land \neg Q$ après double négation. $□$

Remarque

La négation d'une implication n'est pas une implication. C'est le point que l'on rate le plus souvent. Nier « si $P$ alors $Q$ » ne donne pas « si $P$ alors non $Q$ » : cela donne « $P$ est vraie et $Q$ est fausse ».

La conséquence est pratique et concerne toutes vos copies : pour réfuter une implication, il faut exhiber une situation où l'hypothèse est réalisée et la conclusion ne l'est pas. Une situation où l'hypothèse n'est pas réalisée ne prouve rien du tout — l'implication est alors vraie sans contenu. Un contre-exemple à « si $n$ est pair alors $n$ est un multiple de $4$ » doit être un entier pair non multiple de $4$ : $n = 6$ convient, $n = 7$ ne prouve rien.

Condition nécessaire, condition suffisante

Définition

Soit l'implication $P \Rightarrow Q$ , supposée vraie. On dit alors que :

$P$ est une condition suffisante pour $Q$ : il suffit que $P$ soit vraie pour que $Q$ le soit ;
$Q$ est une condition nécessaire pour $P$ : il faut que $Q$ soit vraie pour que $P$ puisse l'être.

Lorsque $P ⟺ Q$ , on dit que $P$ est une condition nécessaire et suffisante pour $Q$ .

Ce vocabulaire est celui des énoncés de concours, des sujets de partiel et des articles : il faut pouvoir le traduire sans y penser.

Méthode

Traduire une phrase en implication. Repérez le mot clé, il donne le sens de la flèche.

« Il suffit que $P$ pour que $Q$ » se traduit par $P \Rightarrow Q$ . La condition suffisante est à la source de la flèche.
« Il faut que $Q$ pour que $P$ » se traduit par $P \Rightarrow Q$ . La condition nécessaire est à la pointe de la flèche.
« $P$ seulement si $Q$ » se traduit par $P \Rightarrow Q$ .
« $P$ si $Q$ » se traduit par $Q \Rightarrow P$ : attention, la flèche est dans l'autre sens.
« $P$ si et seulement si $Q$ » se traduit par $P ⟺ Q$ .

Exemple

Considérons, pour un entier $n$ , les deux assertions « $n$ est un multiple de $12$ » et « $n$ est pair ».

Être pair est une condition nécessaire pour être multiple de $12$ : tout multiple de $12$ est pair, donc il faut être pair pour espérer être multiple de $12$ . Ce n'est pas suffisant : $n = 10$ est pair sans être multiple de $12$ .

Enfin, « $n$ est multiple de $3$ et $n$ est multiple de $4$ » est une condition nécessaire et suffisante pour que $n$ soit multiple de $12$ .

Quantificateurs

Les quantificateurs, variables libres et liées

Un prédicat $P (x)$ n'a pas de valeur de vérité. Pour en fabriquer une assertion, on peut fixer $x$ , ou bien quantifier la variable : dire que la propriété vaut pour tous les éléments, ou qu'elle vaut pour au moins un.

Définition

Soit $E$ un ensemble et $P (x)$ un prédicat portant sur les éléments de $E$ .

L'assertion $\forall x \in E, P (x)$ , lue « pour tout $x$ de $E$ , $P (x)$ », est vraie lorsque $P (x)$ est vraie pour chaque élément $x$ de $E$ . Le symbole $\forall$ est le quantificateur universel.
L'assertion $\exists x \in E, P (x)$ , lue « il existe $x$ dans $E$ tel que $P (x)$ », est vraie lorsqu'il y a au moins un élément $x$ de $E$ pour lequel $P (x)$ est vraie. Le symbole $\exists$ est le quantificateur existentiel.

Définition

Dans l'assertion $\forall x \in E, P (x)$ , la variable $x$ est dite liée (ou muette) : on peut la renommer sans rien changer, et elle n'a aucune existence en dehors de l'énoncé. Une variable qui n'est pas liée par un quantificateur est dite libre.

Remarque

Le cas de l'ensemble vide. L'assertion $\forall x \in \emptyset, P (x)$ est vraie, quel que soit $P$ : il n'y a aucun élément à tester, donc aucun contre-exemple possible. Symétriquement, $\exists x \in \emptyset, P (x)$ est fausse, toujours. Ce n'est pas une curiosité : c'est ce qui rendra vraies, plus loin, des phrases comme « toute partie de l'ensemble vide est … ».

L'ordre des quantificateurs change le sens

C'est le point de cette section qu'il faut retenir avant tous les autres, parce qu'il coûte plus de points que n'importe quel autre en première année.

Exemple

Prenons $E$ l'ensemble des habitants d'une ville, et le prédicat $M (x, y)$ : « $y$ est la mère de $x$ ». Comparons deux phrases qui contiennent exactement les mêmes symboles, dans un ordre différent.

\forall x \in E, \exists y \in E, M (x, y)

se lit : « tout habitant a une mère ». C'est raisonnable.

\exists y \in E, \forall x \in E, M (x, y)

se lit : « il existe une habitante qui est la mère de tous les habitants ». C'est absurde.

La différence tient à un seul point : dans la première phrase, $y$ est choisi après $x$ , il a donc le droit d'en dépendre — à chacun sa mère. Dans la seconde, $y$ est choisi avant $x$ , il doit donc convenir pour tout le monde à la fois.

Exemple

La même distinction, sur un énoncé de mathématiques que vous rencontrerez dès le chapitre suivant. Soit $(u_{n})$ une suite réelle. Comparons :

\forall n \in N, \exists M \in R, u_{n} \leq M et \exists M \in R, \forall n \in N, u_{n} \leq M .

La première est vraie pour toute suite, sans exception : il suffit, une fois $n$ fixé, de prendre $M = u_{n}$ . Elle ne dit donc strictement rien.

La seconde est la définition de « la suite $(u_{n})$ est majorée », et elle est fausse pour beaucoup de suites, par exemple pour $u_{n} = n$ . Le $M$ y est choisi une fois pour toutes, avant de connaître $n$ : il doit convenir simultanément pour tous les rangs.

Une copie qui démontre la première en croyant démontrer la seconde ne vaut aucun point, et c'est une copie que l'on voit à chaque session.

Propriété

Deux quantificateurs de même nature qui se suivent peuvent être échangés :

(\forall x \in E, \forall y \in F, P (x, y)) \equiv (\forall y \in F, \forall x \in E, P (x, y)),

et de même pour deux $\exists$ consécutifs. En revanche, $\exists$ et $\forall$ ne commutent pas : on a seulement l'implication

(\exists y \in F, \forall x \in E, P (x, y)) \Rightarrow (\forall x \in E, \exists y \in F, P (x, y)),

et la réciproque est fausse en général.

Négation d'un énoncé quantifié

Propriété

Pour tout ensemble $E$ et tout prédicat $P$ :

\neg (\forall x \in E, P (x)) \equiv (\exists x \in E, \neg P (x)), \neg (\exists x \in E, P (x)) \equiv (\forall x \in E, \neg P (x)) .

Démonstration. Dire que « $P (x)$ pour tout $x$ de $E$ » est faux, c'est dire que la propriété échoue quelque part, c'est-à-dire qu'il existe au moins un élément $x$ de $E$ pour lequel $P (x)$ est fausse : c'est exactement $\exists x \in E, \neg P (x)$ . Réciproquement, si un tel $x$ existe, l'énoncé universel ne peut pas être vrai.

Ces deux règles sont les analogues exacts des lois de De Morgan : le $\forall$ joue le rôle d'un « et » répété sur tous les éléments, le $\exists$ celui d'un « ou ».

Méthode

La règle mécanique de négation. Pour nier un énoncé quantifié, on parcourt la formule de gauche à droite :

chaque $\forall$ devient $\exists$ , chaque $\exists$ devient $\forall$ ; l'ordre des quantificateurs ne change pas, et les ensembles ne changent pas non plus ;
on arrive au bout, sur la partie non quantifiée : on la nie, et c'est le seul endroit où il faut réfléchir ;
dans cette partie finale, on applique les règles déjà connues : un « et » devient un « ou », un « ou » devient un « et », et une implication $P \Rightarrow Q$ devient $P \land \neg Q$ .

Exemple

Nier « $f$ est injective ». Pour $f : E \to F$ , l'injectivité s'écrit

\forall x \in E, \forall x^{'} \in E, (f (x) = f (x^{'}) \Rightarrow x = x^{'}) .

La règle donne : les deux $\forall$ deviennent des $\exists$ , puis on nie l'implication finale, qui devient une conjonction. La négation est donc

\exists x \in E, \exists x^{'} \in E, (f (x) = f (x^{'}) \land x \neq x^{'}),

ce qui se lit : « il existe deux éléments distincts de $E$ ayant la même image ». C'est bien ce que l'on attend, et c'est exactement la phrase qu'il faudra écrire pour montrer qu'une application n'est pas injective : exhiber deux tels éléments, et les exhiber explicitement.

Remarque

Trois fautes à connaître, parce qu'elles reviennent toutes les trois à chaque partiel.

La première consiste à changer l'ordre des quantificateurs en niant. C'est toujours faux, sans discussion : la mécanique conserve l'ordre.

La deuxième consiste à nier une inégalité large en inégalité stricte de même sens : la négation de $a \leq b$ est $a > b$ , pas $a \geq b$ ni $a < b$ . La négation d'une inégalité inverse le sens et change la nature de l'inégalité.

La troisième consiste à nier « $P$ implique $Q$ » en « $P$ implique non $Q$ ». On a vu qu'il fallait écrire $P \land \neg Q$ . Elle est d'autant plus dangereuse qu'elle produit une phrase qui a l'air correcte.

Le quantificateur « il existe un unique »

Définition

Soient $E$ un ensemble et $P$ un prédicat. L'assertion $\exists! x \in E, P (x)$ , lue « il existe un unique $x$ de $E$ tel que $P (x)$ », est par définition la conjonction de deux assertions :

(\exists x \in E, P (x)) \land (\forall x \in E, \forall x^{'} \in E, (P (x) \land P (x^{'})) \Rightarrow x = x^{'}) .

La première est l'existence, la seconde l'unicité.

Méthode

Démontrer un « il existe un unique ». La démonstration a toujours deux parties, séparées et annoncées.

Existence : on exhibe un objet et on vérifie qu'il convient. C'est le geste du $\exists$ .
Unicité : on se donne deux objets $x$ et $x^{'}$ vérifiant la propriété, et on montre qu'ils sont égaux. C'est le geste du $\forall$ , appliqué deux fois.

Exemple

Soient $a$ et $b$ deux réels, avec $a \neq 0$ . Montrons qu'il existe un unique réel $x$ tel que $a x + b = 0$ .

Existence. Posons $x_{0} = - \frac{b}{a}$ , ce qui a un sens puisque $a \neq 0$ . Alors $a x_{0} + b = - b + b = 0$ : cet élément convient.

Unicité. Soient $x$ et $x^{'}$ deux réels tels que $a x + b = 0$ et $a x^{'} + b = 0$ . En soustrayant les deux égalités, il vient $a (x - x^{'}) = 0$ . Comme $a \neq 0$ , on en déduit $x - x^{'} = 0$ , c'est-à-dire $x = x^{'}$ .

Il existe donc un unique réel solution, et c'est $- \frac{b}{a}$ .

Comment on rédige une démonstration

Cette section décide de vos notes du premier semestre. Le contenu mathématique de la première année n'est pas très difficile : les calculs y sont souvent plus simples qu'en terminale. Ce qui coûte des points, ce sont des fautes de forme qui sont en réalité des fautes de logique, et qui ont toutes un nom. Les nommer, c'est déjà à moitié les éviter.

L'anatomie d'une démonstration

Définition

Une démonstration d'un énoncé est une suite finie d'affirmations, dont chacune est soit une hypothèse de l'énoncé, soit une définition, soit un résultat déjà établi, soit une conséquence des précédentes obtenue par une règle de logique, et dont la dernière est l'énoncé à démontrer.

Trois choses découlent de cette définition, et il faut les prendre au sérieux.

Chaque ligne doit être justifiée par ce qui précède, et par rien d'autre. Une phrase qui utilise un objet non encore introduit, ou une propriété non encore établie, casse la chaîne.

La dernière ligne doit être exactement l'énoncé demandé, pas un énoncé voisin. C'est le contrôle le plus rapide et le plus efficace que vous puissiez faire sur votre propre copie : relisez la question, relisez votre dernière phrase, et vérifiez qu'elles disent la même chose.

Méthode

Les trois questions à se poser avant d'écrire la première ligne. Elles prennent trente secondes et font gagner une demi-heure.

Qu'est-ce que je suppose ? Listez les hypothèses, toutes, y compris celles qui sont dans l'énoncé du chapitre et pas dans la question.
Qu'est-ce que je dois établir ? Écrivez la conclusion en toutes lettres, sur le brouillon.
Quelle est la forme logique de cette conclusion ? Un « pour tout » ? un « il existe » ? une implication ? une égalité d'ensembles ? C'est cette forme, et elle seule, qui décide de votre première phrase.

Le tableau suivant répond à la troisième question dans tous les cas que vous rencontrerez ce semestre. Il n'est pas à réciter, il est à utiliser.

Ce qu'il faut démontrer	La première ligne de la copie
$\forall x \in E, P (x)$	Soit $x \in E$ .
$\exists x \in E, P (x)$	Posons $x = \dots$ et vérifions.
$\exists! x \in E, P (x)$	Existence, puis unicité, dans cet ordre.
$P \Rightarrow Q$	Supposons $P$ .
$P ⟺ Q$	Montrons les deux implications.
$A \subset B$	Soit $x \in A$ .
$A = B$	Montrons la double inclusion.
$\neg P$	Supposons $P$ , et cherchons une contradiction.
$P \lor Q$	Supposons $\neg P$ , et montrons $Q$ .

Les deux gestes d'ouverture

Presque tout ce que vous aurez à démontrer cette année commence par l'un de ces deux gestes. Ils sont à connaître comme un pianiste connaît ses gammes.

Méthode

Geste n°1 : « Soit $x \in A$ . » C'est l'ouverture d'une démonstration de $\forall x \in A, P (x)$ .

On introduit un élément $x$ de $A$ fixé mais quelconque : fixé, parce qu'à partir de là on a le droit de calculer avec lui comme avec un objet précis ; quelconque, parce qu'on ne lui suppose aucune propriété particulière. On démontre alors $P (x)$ pour cet $x$ -là, sans jamais utiliser autre chose que « $x \in A$ ». Comme le raisonnement n'a rien utilisé de spécifique, il vaut pour tous les éléments : l'énoncé universel est démontré.

Deux points de vigilance sur ce geste, tous les deux fréquents.

Une fois écrit « Soit $x \in A$ », $x$ est fixé pour tout le reste de la démonstration. On ne peut plus le remplacer par un autre, ni le faire varier, ni écrire « prenons maintenant $x = 3$ ». Si vous avez besoin d'un second élément, introduisez-le avec un autre nom.

Exemple

Montrons que pour tout réel $x$ , on a $x^{2} - 2 x + 3 > 0$ .

Soit $x \in R$ . On écrit $x^{2} - 2 x + 3 = (x - 1)^{2} + 2$ . Or $(x - 1)^{2} \geq 0$ comme carré d'un réel, donc $(x - 1)^{2} + 2 \geq 2 > 0$ . Ainsi $x^{2} - 2 x + 3 > 0$ .

Ceci vaut pour tout réel $x$ , ce qui est le résultat annoncé.

Méthode

Geste n°2 : « Posons $x = \dots$ » C'est l'ouverture d'une démonstration de $\exists x \in E, P (x)$ .

Exemple

Montrons qu'il existe un entier $n \geq 0$ tel que $n^{2} + n + 41$ ne soit pas un nombre premier.

Posons $n = 41$ . Alors

n^{2} + n + 41 = 41^{2} + 41 + 41 = 41 \times (41 + 1 + 1) = 41 \times 43 = 1763.

Ce nombre s'écrit comme produit de deux entiers tous deux différents de $1$ : il n'est donc pas premier. L'entier $n = 41$ convient, ce qui établit l'existence annoncée.

Les six fautes qui coûtent le plus de points en première année

Faute n°1 — Un exemple n'est pas une démonstration.

Exemple

Énoncé. Montrer que pour tout réel $x$ , on a $x^{2} + 1 \geq 2 x$ .

Sur la copie. « Pour $x = 3$ : $9 + 1 = 10$ et $2 \times 3 = 6$ , donc $10 \geq 6$ . Pour $x = 0$ : $1 \geq 0$ . Donc pour tout réel $x$ , $x^{2} + 1 \geq 2 x$ . »

Ce qui ne va pas. Le « donc » de la dernière phrase n'a aucune justification. Deux cas particuliers, ou deux mille, ne démontrent pas un énoncé universel : il resterait toujours une infinité de réels non testés. La copie a vérifié l'énoncé, elle ne l'a pas démontré.

La version correcte. Soit $x \in R$ . On a $x^{2} + 1 - 2 x = (x - 1)^{2} \geq 0$ , comme carré d'un réel. Donc $x^{2} + 1 \geq 2 x$ . Ceci valant pour tout réel $x$ , l'énoncé est démontré.

Une seule ligne a changé, et c'est la première : « Soit $x \in R$ » remplace « Pour $x = 3$ ». Toute la différence est là.

Faute n°2 — Démontrer la réciproque à la place de l'implication.

Exemple

Énoncé. Soit $x$ un réel tel que $x^{2} = 4 x - 4$ . Montrer que $x = 2$ .

Sur la copie. « Si $x = 2$ , alors $x^{2} = 4$ et $4 x - 4 = 8 - 4 = 4$ . Donc $x^{2} = 4 x - 4$ , et $x = 2$ convient. »

Ce qui ne va pas. La copie est mathématiquement juste, ligne par ligne, et pourtant elle vaut zéro. Elle démontre « si $x = 2$ alors $x^{2} = 4 x - 4$ », c'est-à-dire exactement la réciproque de ce qui était demandé. Elle prouve qu'il y a au moins une solution ; on demandait qu'il n'y en ait pas d'autre.

La version correcte. Soit $x$ un réel tel que $x^{2} = 4 x - 4$ . Alors $x^{2} - 4 x + 4 = 0$ , c'est-à-dire $(x - 2)^{2} = 0$ . Le carré d'un réel est nul si et seulement si ce réel l'est, donc $x - 2 = 0$ , c'est-à-dire $x = 2$ .

La même faute, en version ensembliste. Elle prend le visage suivant : on demande de montrer $A = B$ , la copie montre proprement $A \subset B$ , et conclut « donc $A = B$ ». Une inclusion sur deux, c'est une implication sur deux : le raisonnement est à moitié fait, et la moitié manquante est souvent la plus difficile.

Faute n°3 — La flèche $\Rightarrow$ employée comme signe de ponctuation.

Exemple

Énoncé. Résoudre dans $R$ l'équation $x^{2} = 4 x - 4$ .

Sur la copie. « $x^{2} = 4 x - 4 \Rightarrow x^{2} - 4 x + 4 \Rightarrow (x - 2)^{2} \Rightarrow x = 2$ . »

Ce qui ne va pas. Deux choses, et la seconde est grave. D'abord, « $x^{2} - 4 x + 4$ » et « $(x - 2)^{2}$ » ne sont pas des assertions : ce sont des nombres. Une flèche d'implication relie deux phrases, pas deux expressions ; ici elle ne relie rien du tout. Ensuite, ce symbole est employé comme on emploierait une virgule, pour signifier « et ensuite j'écris ceci ». Un correcteur, lui, le lit comme ce qu'il est, et il lit une suite d'énoncés dépourvus de sens.

La version correcte. L'équation $x^{2} = 4 x - 4$ équivaut à $x^{2} - 4 x + 4 = 0$ , c'est-à-dire à $(x - 2)^{2} = 0$ , c'est-à-dire à $x = 2$ . L'ensemble des solutions est donc ${2}$ .

Faute n°4 — L'objet qui dépend d'un autre, et le quantificateur qui glisse.

C'est la faute la plus coûteuse de toutes, et c'est aussi celle qui passe le plus facilement inaperçue à la relecture, parce que chaque ligne prise séparément est vraie.

Exemple

Énoncé. Soit $(u_{n})$ la suite définie par $u_{n} = n$ pour tout $n \in N$ . Montrer qu'elle est majorée, ou qu'elle ne l'est pas.

Sur la copie. « Soit $n \in N$ . Posons $M = u_{n}$ . Alors $u_{n} \leq M$ . Donc pour tout $n \in N$ , $u_{n} \leq M$ : la suite $(u_{n})$ est majorée. »

Ce qui ne va pas. Le $M$ a été construit après que $n$ ait été fixé : il en dépend. Écrire ensuite « pour tout $n$ , $u_{n} \leq M$ » consiste à faire sortir $M$ du champ du quantificateur, ce qui n'est pas permis. La copie a démontré $\forall n, \exists M, u_{n} \leq M$ , qui est vrai pour n'importe quelle suite et ne dit rien ; l'énoncé demandait $\exists M, \forall n, u_{n} \leq M$ , qui est ici faux.

La version correcte. La suite n'est pas majorée. En effet, supposons qu'il existe un réel $M$ tel que $u_{n} \leq M$ pour tout $n \in N$ . Cet $M$ étant fixé, prenons pour $n$ un entier strictement supérieur à $M$ , ce qui est possible car $N$ n'est pas majoré dans $R$ . Alors $u_{n} = n > M$ , ce qui contredit $u_{n} \leq M$ . Donc aucun tel $M$ n'existe.

Le signal d'alarme. Chaque fois qu'un objet est introduit par « posons » à l'intérieur d'un « soit », demandez-vous s'il dépend de la variable en cours. Si oui, il ne peut pas ressortir.

Faute n°5 — Diviser, ou simplifier, par une quantité qui peut être nulle.

Exemple

Énoncé. Soient $a$ et $b$ deux réels tels que $a^{2} = a b$ . Que peut-on dire de $a$ et $b$ ?

Sur la copie. « De $a^{2} = a b$ , on tire en divisant par $a$ : $a = b$ . »

Ce qui ne va pas. Rien n'assure que $a$ est non nul. Le contre-exemple est immédiat : $a = 0$ et $b = 7$ vérifient bien $a^{2} = 0 = a b$ , sans que $a = b$ . La conclusion de la copie est donc fausse, et l'erreur tient à une division non justifiée.

La version correcte. De $a^{2} = a b$ on tire $a^{2} - a b = 0$ , c'est-à-dire $a (a - b) = 0$ . Un produit de deux réels est nul si et seulement si l'un des facteurs l'est, donc $a = 0$ ou $a = b$ . On ne peut rien dire de plus, et les deux cas se produisent effectivement.

Faute n°6 — Conclure d'un seul cas d'une disjonction.

Exemple

Énoncé. Montrer que pour tout entier $n$ , l'entier $n^{2} + n$ est pair.

Sur la copie. « Si $n$ est pair, il s'écrit $n = 2 k$ avec $k$ entier, et alors $n^{2} + n = 4 k^{2} + 2 k = 2 (2 k^{2} + k)$ est pair. Donc pour tout entier $n$ , $n^{2} + n$ est pair. »

Ce qui ne va pas. La copie a traité un cas sur deux. Le raisonnement est correct dans ce cas, mais rien n'a été dit des entiers impairs, qui sont pourtant la moitié du problème. Le « donc » final annonce un résultat général à partir d'une hypothèse particulière.

La version correcte. Soit $n$ un entier. Distinguons deux cas, qui recouvrent toutes les possibilités.

Premier cas : $n$ est pair. Il s'écrit $n = 2 k$ avec $k$ entier, et alors $n^{2} + n = 2 (2 k^{2} + k)$ est pair.

Second cas : $n$ est impair. Il s'écrit $n = 2 k + 1$ avec $k$ entier, et alors $n^{2} + n = (4 k^{2} + 4 k + 1) + (2 k + 1) = 2 (2 k^{2} + 3 k + 1)$ est pair.

Dans les deux cas $n^{2} + n$ est pair, et tout entier relève de l'un des deux : le résultat est démontré pour tout entier $n$ .

Trois modèles de rédaction commentés

Méthode

Modèle 1 — Une implication.

Énoncé. Soit $n$ un entier. Si $n$ est somme de deux carrés d'entiers, alors $2 n$ l'est aussi.

Rédaction. Supposons que $n$ soit somme de deux carrés d'entiers. Il existe donc deux entiers $a$ et $b$ tels que $n = a^{2} + b^{2}$ . Considérons les entiers $a + b$ et $a - b$ . On calcule

(a + b)^{2} + (a - b)^{2} = (a^{2} + 2 a b + b^{2}) + (a^{2} - 2 a b + b^{2}) = 2 a^{2} + 2 b^{2} = 2 n .

L'entier $2 n$ est donc somme des carrés des deux entiers $a + b$ et $a - b$ : il est bien somme de deux carrés d'entiers.

Ce que chaque phrase fait. La première ouvre l'implication en supposant l'hypothèse, et rien d'autre. La deuxième déballe l'hypothèse : « être somme de deux carrés » est une phrase d'existence, on introduit donc les objets dont elle affirme l'existence, avec des noms. La troisième introduit les candidats, la quatrième vérifie, la cinquième conclut dans les mots exacts de l'énoncé.

Méthode

Modèle 2 — Une inclusion.

Énoncé. On pose $A = {x \in R; x^{2} < x}$ et $B = {x \in R; 0 < x < 1}$ . Montrer que $A \subset B$ .

Rédaction. Soit $x \in A$ . Par définition de $A$ , on a $x^{2} < x$ , c'est-à-dire $x^{2} - x < 0$ , c'est-à-dire $x (x - 1) < 0$ . Le produit des deux réels $x$ et $x - 1$ est strictement négatif, donc ces deux réels sont de signes stricts contraires. Or $x - 1 < x$ : c'est donc $x - 1$ qui est le négatif et $x$ le positif, autrement dit $x - 1 < 0$ et $x > 0$ . Ainsi $0 < x < 1$ , c'est-à-dire $x \in B$ .

Tout élément de $A$ appartient donc à $B$ : on a bien $A \subset B$ .

Ce que chaque phrase fait. La première est le geste d'ouverture : une inclusion est un « pour tout », elle commence par « soit ». La deuxième traduit l'appartenance en la propriété qui définit $A$ , ce qui est toujours le premier travail. Le corps est un calcul, écrit en phrases. L'avant-dernière phrase traduit la propriété obtenue en l'appartenance à $B$ : c'est le mouvement inverse du début. La dernière conclut sur l'inclusion elle-même, et pas seulement sur $x$ .

Méthode

Modèle 3 — Une équivalence, par double implication.

Énoncé. Soient $A$ et $B$ deux parties d'un ensemble $E$ . Montrer que $A \subset B$ si et seulement si $A \cap B = A$ .

Rédaction. Montrons les deux implications.

Sens direct. Supposons $A \subset B$ , et montrons $A \cap B = A$ par double inclusion. L'inclusion $A \cap B \subset A$ est vraie pour toutes parties, par définition de l'intersection. Réciproquement, soit $x \in A$ . Comme $A \subset B$ , on a aussi $x \in B$ , donc $x \in A \cap B$ . D'où $A \subset A \cap B$ , et finalement $A \cap B = A$ .

Sens réciproque. Supposons $A \cap B = A$ , et montrons $A \subset B$ . Soit $x \in A$ . L'hypothèse donne $x \in A \cap B$ , donc en particulier $x \in B$ . D'où $A \subset B$ .

Les deux implications étant établies, l'équivalence est démontrée.

Ce que chaque phrase fait. La première annonce le plan, et cette annonce n'est pas décorative : c'est elle qui garantit au correcteur, et à vous, qu'aucun des deux sens ne sera oublié. Chaque sens est ouvert par « supposons », puis rappelle ce qu'il faut établir. Remarquez que le sens direct contient lui-même une double inclusion : une démonstration peut parfaitement en emboîter une autre, à condition que chaque niveau soit annoncé et refermé. La phrase finale referme l'équivalence.

Les modes de raisonnement

Raisonnement direct

C'est le mode par défaut : on part des hypothèses et on avance jusqu'à la conclusion par une chaîne de déductions. Le squelette est celui du modèle 1 de la section précédente : Supposons $P$ . … Donc $Q$ .

Raisonnement par contraposée

Méthode

Principe. Pour démontrer $P \Rightarrow Q$ , on démontre $\neg Q \Rightarrow \neg P$ , qui lui est logiquement équivalente.

Squelette. Montrons la contraposée : si $\neg Q$ , alors $\neg P$ . Supposons donc $\neg Q$ . … Donc $\neg P$ . Par contraposée, on a bien $P \Rightarrow Q$ .

Quand y penser. Quand l'hypothèse $P$ est difficile à exploiter et que sa négation, elle, est concrète ; ou quand la conclusion $Q$ est une négation, une inégalité stricte, ou une disjonction — car sa négation, elle, sera une conjonction, plus facile à manipuler.

Exemple

Soit $n$ un entier. Montrons que si $n^{3} + 5$ est impair, alors $n$ est pair.

Montrons la contraposée : si $n$ est impair, alors $n^{3} + 5$ est pair. Supposons donc $n$ impair, et écrivons $n = 2 k + 1$ avec $k$ entier. Alors $n^{3}$ est impair, comme produit de trois entiers impairs, donc $n^{3} = 2 m + 1$ pour un certain entier $m$ , et $n^{3} + 5 = 2 m + 6 = 2 (m + 3)$ est pair. Par contraposée, l'implication annoncée est démontrée.

Raisonnement par l'absurde, et sa différence avec la contraposée

Méthode

Principe. Pour démontrer une assertion $P$ , on suppose $\neg P$ et on en déduit une contradiction, c'est-à-dire une assertion et sa négation, ou un énoncé manifestement faux. Comme $\neg P$ conduit à une absurdité, $\neg P$ est fausse, donc $P$ est vraie.

Squelette. Raisonnons par l'absurde, et supposons $\neg P$ . … On aboutit à [énoncé faux], ce qui est absurde. Donc $P$ .

L'annonce est obligatoire, et pour une raison plus forte que le confort du correcteur : tout ce qui est écrit après « supposons par l'absurde » est faux. Une copie qui oublie de refermer le raisonnement affirme des choses fausses sans les désavouer.

Exemple

Soit $x$ un réel tel que $∣ x ∣ \leq ε$ pour tout réel $ε > 0$ . Montrons que $x = 0$ .

Raisonnons par l'absurde, et supposons $x \neq 0$ . Alors $∣ x ∣ > 0$ , et le réel $ε_{0} = \frac{∣ x ∣}{2}$ est strictement positif. L'hypothèse, appliquée à ce $ε_{0}$ , donne $∣ x ∣ \leq \frac{∣ x ∣}{2}$ , d'où $\frac{∣ x ∣}{2} \leq 0$ , puis $∣ x ∣ \leq 0$ . Or $∣ x ∣ > 0$ : c'est une contradiction. Donc $x = 0$ .

Remarque

Absurde ou contraposée : la question que tout le monde se pose, et la réponse.

Les deux modes se ressemblent, puisque tous deux commencent par nier quelque chose. La différence est nette dès qu'on regarde ce qu'on suppose et ce qu'on obtient.

Dans une contraposée d'une implication $P \Rightarrow Q$ , on suppose $\neg Q$ seulement, et on doit arriver à $\neg P$ . Il n'y a aucune contradiction dans la démonstration : c'est un raisonnement direct, mené sur un autre énoncé.
Dans un raisonnement par l'absurde appliqué à la même implication, on suppose $P$ et $\neg Q$ à la fois, et on doit arriver à une contradiction avec n'importe quoi : une hypothèse, un résultat du cours, une évidence numérique.

L'absurde donne donc une hypothèse de plus, ce qui est confortable, mais il oblige à surveiller la cohérence de tout ce qu'on écrit. Le test pratique : si votre raisonnement par l'absurde se termine en contredisant précisément $P$ , c'est que vous avez fait une contraposée sans le dire. Réécrivez-la comme telle, elle sera plus courte et plus claire.

Disjonction de cas

Méthode

Principe. Pour démontrer une assertion, on découpe la situation en un nombre fini de cas qui recouvrent toutes les possibilités, et on démontre l'assertion dans chacun.

Squelette. Distinguons [deux, trois] cas, selon que … . Premier cas : supposons … . Alors … . Second cas : supposons … . Alors … . Dans tous les cas, … , ce qui démontre l'énoncé.

Exemple

Montrons que pour tout réel $x$ , on a $x^{4} - x^{3} + x^{2} - x + 1 > 0$ .

Soit $x \in R$ . Distinguons trois cas, selon la position de $x$ par rapport à $0$ et à $1$ .

Premier cas : $x \leq 0$ . Alors $x^{4} \geq 0$ , $- x^{3} \geq 0$ , $x^{2} \geq 0$ et $- x \geq 0$ . La somme des quatre est positive ou nulle, donc l'expression vaut au moins $1 > 0$ .

Deuxième cas : $0 < x \leq 1$ . On regroupe autrement : $x^{4} - x^{3} + x^{2} - x + 1 = x^{4} + x^{2} (1 - x) + (1 - x)$ . Ici $1 - x \geq 0$ et $x^{4} > 0$ , donc la somme est strictement positive.

Troisième cas : $x > 1$ . On regroupe encore autrement : $x^{4} - x^{3} + x^{2} - x + 1 = x^{3} (x - 1) + x (x - 1) + 1$ . Ici $x - 1 > 0$ et $x > 0$ , donc les deux premiers termes sont positifs, et la somme vaut au moins $1 > 0$ .

Tout réel relève de l'un de ces trois cas, et l'inégalité est vraie dans chacun : elle est vraie pour tout réel $x$ .

Contre-exemple

Méthode

Principe. Pour démontrer qu'une assertion de la forme $\forall x \in E, P (x)$ est fausse, il suffit d'exhiber un élément $x_{0}$ de $E$ tel que $P (x_{0})$ soit fausse. C'est le geste du $\exists$ , appliqué à la négation.

Squelette. Cette assertion est fausse. Prenons en effet $x_{0} = \dots$ . Alors … , donc $P (x_{0})$ est fausse, et l'assertion universelle ne peut pas être vraie.

Exemple

L'assertion « pour toutes parties $A$ , $B$ , $C$ d'un ensemble $E$ , on a $A \cap (B \cup C) = (A \cap B) \cup C$ » est fausse.

Prenons $E = {1, 2}$ , puis $A = {1}$ , $B = \emptyset$ et $C = {2}$ . D'une part $B \cup C = {2}$ , donc $A \cap (B \cup C) = {1} \cap {2} = \emptyset$ . D'autre part $A \cap B = \emptyset$ , donc $(A \cap B) \cup C = \emptyset \cup {2} = {2}$ .

Les deux membres valent respectivement $\emptyset$ et ${2}$ : ils sont différents, et l'assertion est fausse.

Remarque

Contre-exemple à une implication. Pour réfuter « pour tout $x$ , si $P (x)$ alors $Q (x)$ », il faut un $x_{0}$ vérifiant $P (x_{0})$ et $\neg Q (x_{0})$ : c'est la négation d'une implication, vue plus haut. Un $x_{0}$ qui ne vérifie pas $P$ ne prouve rien du tout, puisque l'implication est alors vraie sans contenu. C'est l'erreur la plus fréquente sur ce mode de raisonnement.

Analyse-synthèse

Méthode

Principe. On veut déterminer tous les objets vérifiant une propriété. On procède en deux temps, séparés et annoncés.

Analyse. On suppose qu'un objet $x$ convient, et on en déduit des conditions nécessaires, jusqu'à n'avoir plus qu'une liste finie de candidats. Cette étape ne démontre aucune existence : elle dit seulement « s'il y a une solution, elle est dans cette liste ».
Synthèse. On reprend chaque candidat et on vérifie s'il convient vraiment. Cette étape seule établit l'existence, et élimine les candidats parasites.

Squelette. Analyse. Supposons que $x$ convienne. Alors … , donc nécessairement $x = \dots$ . Synthèse. Réciproquement, vérifions que $x = \dots$ convient : … . Conclusion. L'ensemble des solutions est … .

Exemple

Résolvons dans $R$ l'équation $\sqrt{x + 1} = x - 1$ .

Analyse. Supposons que $x$ soit solution. Les deux membres sont alors égaux, donc leurs carrés le sont : $x + 1 = (x - 1)^{2} = x^{2} - 2 x + 1$ , d'où $x^{2} - 3 x = 0$ , c'est-à-dire $x (x - 3) = 0$ . Nécessairement $x = 0$ ou $x = 3$ .

Synthèse. Pour $x = 0$ : le membre de gauche vaut $\sqrt{1} = 1$ , le membre de droite vaut $- 1$ . Ils diffèrent, donc $0$ n'est pas solution. Pour $x = 3$ : le membre de gauche vaut $\sqrt{4} = 2$ , le membre de droite vaut $2$ . Ils coïncident, donc $3$ est solution.

Conclusion. L'ensemble des solutions est ${3}$ .

Cet exemple montre exactement pourquoi la synthèse n'est pas une formalité : l'analyse a produit deux candidats, dont l'un ne convient pas. La raison est que l'élévation au carré n'est pas une équivalence — deux réels de carrés égaux peuvent être opposés. Une copie qui s'arrête après l'analyse répond « $0$ ou $3$ », et se trompe.

Raisonnement par récurrence

Propriété

Principe de récurrence. Soit $P (n)$ un prédicat portant sur les entiers naturels, et soit $n_{0} \in N$ . Si

$P (n_{0})$ est vraie, et
pour tout entier $n \geq n_{0}$ , $P (n) \Rightarrow P (n + 1)$ ,

alors $P (n)$ est vraie pour tout entier $n \geq n_{0}$ .

Cette propriété n'est pas un théorème que l'on démontre à partir de plus simple : c'est l'un des axiomes qui caractérisent $N$ . On l'admet, et on s'en sert. Elle est par ailleurs équivalente à un autre énoncé, qui s'admet lui aussi : toute partie non vide de $N$ admet un plus petit élément.

Récurrence simple

Méthode

Squelette de rédaction, à recopier tel quel.

Pour $n \geq n_{0}$ , notons $P (n)$ l'assertion : « … ». Montrons par récurrence que $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Initialisation. Pour $n = n_{0}$ : … . Donc $P (n_{0})$ est vraie.

Hérédité. Soit $n \geq n_{0}$ un entier tel que $P (n)$ soit vraie. Montrons que $P (n + 1)$ l'est aussi. … Donc $P (n + 1)$ est vraie.

Conclusion. $P (n_{0})$ est vraie et $P$ est héréditaire à partir du rang $n_{0}$ : d'après le principe de récurrence, $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Trois exigences se cachent dans ce squelette, et chacune est un point de barème. $P (n)$ doit être écrite explicitement, comme une assertion portant sur un seul entier : « la propriété est vraie » n'est pas un énoncé. L'hérédité s'ouvre par « soit $n$ tel que $P (n)$ », jamais par « supposons la propriété vraie ». Et la conclusion se rédige, en rappelant les deux ingrédients.

Exemple

Montrons que pour tout $n \in N$ , on a $2^{n} \geq n + 1$ .

Pour $n \in N$ , notons $P (n)$ l'assertion « $2^{n} \geq n + 1$ ».

Initialisation. Pour $n = 0$ : $2^{0} = 1$ et $0 + 1 = 1$ , donc $2^{0} \geq 0 + 1$ . Ainsi $P (0)$ est vraie.

Hérédité. Soit $n \in N$ tel que $P (n)$ soit vraie, c'est-à-dire $2^{n} \geq n + 1$ . Alors, en multipliant cette inégalité par $2$ , qui est strictement positif, on obtient $2^{n + 1} \geq 2 (n + 1) = 2 n + 2$ . Or $n \geq 0$ , donc $2 n + 2 \geq n + 2$ . Par transitivité, $2^{n + 1} \geq n + 2$ , c'est-à-dire $P (n + 1)$ .

Conclusion. $P (0)$ est vraie et $P$ est héréditaire : $2^{n} \geq n + 1$ pour tout $n \in N$ .

Remarque

Les deux erreurs classiques.

L'initialisation oubliée, ou faite au mauvais rang. Une propriété peut être parfaitement héréditaire et fausse partout. Prenons $P (n)$ : « $3$ divise $4^{n} + 1$ ». Elle est héréditaire : si $3$ divise $4^{n} + 1$ , alors, puisque $4^{n + 1} + 1 = 4 (4^{n} + 1) - 3$ , l'entier $4^{n + 1} + 1$ est différence de deux multiples de $3$ , donc multiple de $3$ . Et pourtant $P (n)$ est fausse pour tout $n$ : $4^{0} + 1 = 2$ , $4^{1} + 1 = 5$ , $4^{2} + 1 = 17$ , aucun n'est divisible par $3$ . L'hérédité seule ne démontre rien : elle propage une vérité qu'il faut d'abord poser quelque part.

L'hypothèse de récurrence mal énoncée. La forme la plus coûteuse est celle qui fait glisser un quantificateur. On veut montrer qu'une suite $(u_{n})$ est majorée, et on démontre par récurrence l'assertion « il existe $M$ tel que $u_{k} \leq M$ pour tout $k \leq n$ ». Cette assertion est vraie pour tout $n$ , et la récurrence est correcte. Mais le $M$ qu'elle fournit dépend de $n$ : à chaque rang, la démonstration en fabrique un nouveau. Conclure « donc $(u_{n})$ est majorée » revient à échanger $\forall n$ et $\exists M$ , ce qui est interdit. C'est la faute n°4 de la section précédente, sous son déguisement le plus efficace.

Récurrence double

Propriété

Principe de récurrence double. Soit $P (n)$ un prédicat sur les entiers. Si $P (n_{0})$ et $P (n_{0} + 1)$ sont vraies, et si pour tout $n \geq n_{0}$ on a $(P (n) \land P (n + 1)) \Rightarrow P (n + 2)$ , alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Méthode

Squelette. Notons $P (n)$ l'assertion « … ».

Initialisation. On vérifie $P (n_{0})$ et $P (n_{0} + 1)$ — deux rangs, pas un.

Hérédité. Soit $n \geq n_{0}$ tel que $P (n)$ et $P (n + 1)$ soient vraies. Montrons $P (n + 2)$ . …

Conclusion. Par récurrence double, $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Le point de barème est l'initialisation : deux rangs consécutifs, faute de quoi l'hérédité ne démarre jamais. Le second est d'utiliser effectivement les deux hypothèses ; si une seule sert, c'est qu'une récurrence simple suffisait.

Exemple

Soit $(a_{n})$ la suite définie par $a_{0} = 0$ , $a_{1} = 1$ et, pour tout $n \in N$ , $a_{n + 2} = 4 a_{n + 1} - 3 a_{n}$ . Montrons que $a_{n} = \frac{3^{n} - 1}{2}$ pour tout $n \in N$ .

Notons $P (n)$ l'assertion « $a_{n} = \frac{3^{n} - 1}{2}$ ».

Initialisation. Pour $n = 0$ : $\frac{3^{0} - 1}{2} = 0 = a_{0}$ . Pour $n = 1$ : $\frac{3^{1} - 1}{2} = 1 = a_{1}$ . Donc $P (0)$ et $P (1)$ sont vraies.

Hérédité. Soit $n \in N$ tel que $P (n)$ et $P (n + 1)$ soient vraies. Alors

a_{n + 2} = 4 \cdot \frac{3^{n + 1} - 1}{2} - 3 \cdot \frac{3^{n} - 1}{2} = \frac{4 \cdot 3^{n + 1} - 4 - 3^{n + 1} + 3}{2} = \frac{3 \cdot 3^{n + 1} - 1}{2} = \frac{3^{n + 2} - 1}{2},

c'est-à-dire $P (n + 2)$ . Les deux hypothèses ont servi, chacune une fois.

Conclusion. Par récurrence double, $a_{n} = \frac{3^{n} - 1}{2}$ pour tout $n \in N$ .

Récurrence forte

Propriété

Principe de récurrence forte. Soit $P (n)$ un prédicat sur les entiers, et $n_{0} \in N$ . Si $P (n_{0})$ est vraie, et si pour tout $n \geq n_{0}$ l'implication

(\forall k \in {n_{0}, \dots, n}, P (k)) \Rightarrow P (n + 1)

est vraie, alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Méthode

Squelette. Notons $P (n)$ l'assertion « … ».

Initialisation. $P (n_{0})$ est vraie car … .

Hérédité forte. Soit $n \geq n_{0}$ tel que $P (k)$ soit vraie pour tout $k$ compris entre $n_{0}$ et $n$ . Montrons $P (n + 1)$ . … On applique l'hypothèse au rang $k_{0} = \dots$ , qui vérifie bien $n_{0} \leq k_{0} \leq n$ . …

Conclusion. Par récurrence forte, $P (n)$ est vraie pour tout $n \geq n_{0}$ .

La phrase à ne pas rater est celle qui vérifie que le rang auquel on redescend est dans la plage autorisée. C'est là, et nulle part ailleurs, que se joue la validité d'une récurrence forte.

Exemple

Soit $(u_{n})_{n \geq 1}$ la suite définie par $u_{1} = 1$ et, pour tout $n \geq 2$ , $u_{n} = u_{1} + u_{2} + \dots + u_{n - 1}$ . Montrons que $u_{n} = 2^{n - 2}$ pour tout $n \geq 2$ .

Notons $P (n)$ l'assertion « $u_{n} = 2^{n - 2}$ », pour $n \geq 2$ .

Initialisation. $u_{2} = u_{1} = 1 = 2^{0}$ , donc $P (2)$ est vraie.

Hérédité forte. Soit $n \geq 2$ tel que $P (k)$ soit vraie pour tout $k$ de ${2, \dots, n}$ . Par définition, $u_{n + 1} = u_{1} + u_{2} + \dots + u_{n}$ . Le premier terme vaut $1$ , et l'hypothèse s'applique à chacun des suivants, dont les indices vont de $2$ à $n$ : donc

u_{n + 1} = 1 + \sum_{k = 2}^{n} 2^{k - 2} = 1 + (2^{n - 1} - 1) = 2^{n - 1} = 2^{(n + 1) - 2},

en reconnaissant une somme de puissances de $2$ consécutives. Ainsi $P (n + 1)$ est vraie.

Conclusion. Par récurrence forte, $u_{n} = 2^{n - 2}$ pour tout $n \geq 2$ .

Une récurrence simple aurait échoué ici : la définition de $u_{n + 1}$ fait intervenir tous les termes précédents, pas seulement le dernier.

Récurrence descendante

Deux situations différentes portent ce nom, et il vaut mieux les distinguer.

Propriété

Récurrence finie descendante. Soient $N$ un entier et $P (k)$ un prédicat défini pour $k \in {0, \dots, N}$ . Si $P (N)$ est vraie et si, pour tout $k \in {0, \dots, N - 1}$ , $P (k + 1) \Rightarrow P (k)$ , alors $P (k)$ est vraie pour tout $k \in {0, \dots, N}$ .

Ce n'est pas un nouvel axiome : il suffit d'appliquer le principe de récurrence ordinaire au prédicat $Q (j) = P (N - j)$ , pour $j$ allant de $0$ à $N$ .

Méthode

Squelette. Notons $P (k)$ l'assertion « … », pour $0 \leq k \leq N$ .

Initialisation, au rang le plus haut. $P (N)$ est vraie car … .

Hérédité descendante. Soit $k \in {0, \dots, N - 1}$ tel que $P (k + 1)$ soit vraie. Montrons $P (k)$ . …

Conclusion. Par récurrence descendante, $P (k)$ est vraie pour tout $k$ de ${0, \dots, N}$ .

Exemple

Soient $N \geq 1$ et $f : {0, 1, \dots, N} \to N$ une application telle que $f (N) = 0$ et, pour tout $k \in {0, \dots, N - 1}$ , $f (k) \leq f (k + 1) + 1$ . Montrons que $f (k) \leq N - k$ pour tout $k$ .

Notons $P (k)$ l'assertion « $f (k) \leq N - k$ ».

Initialisation. $f (N) = 0 = N - N$ , donc $P (N)$ est vraie.

Hérédité descendante. Soit $k \in {0, \dots, N - 1}$ tel que $P (k + 1)$ soit vraie, c'est-à-dire $f (k + 1) \leq N - (k + 1)$ . L'hypothèse sur $f$ donne alors $f (k) \leq f (k + 1) + 1 \leq N - k - 1 + 1 = N - k$ , c'est-à-dire $P (k)$ .

Conclusion. Par récurrence descendante, $f (k) \leq N - k$ pour tout $k$ de ${0, \dots, N}$ .

Remarque

Le schéma de Cauchy.

Une variante, le schéma de Cauchy, combine une montée et une descente. Pour établir $P (n)$ pour tout $n \geq 2$ , on démontre $P (2)$ , puis l'implication $P (n) \Rightarrow P (2 n)$ , qui donne la propriété pour toutes les puissances de $2$ , puis l'implication $P (n) \Rightarrow P (n - 1)$ , qui permet de redescendre de n'importe quelle puissance de $2$ jusqu'à l'entier voulu. Le squelette de la conclusion est celui-ci : soit $n \geq 2$ ; il existe une puissance de $2$ supérieure ou égale à $n$ , disons $2^{p} \geq n$ ; la propriété est vraie au rang $2^{p}$ par la première hérédité, et en appliquant $2^{p} - n$ fois la seconde, elle est vraie au rang $n$ . C'est de cette manière que se démontre l'inégalité entre moyenne arithmétique et moyenne géométrique.

Ensembles

On ne définira pas ce qu'est un ensemble : c'est une notion première, comme le point en géométrie. Un ensemble est déterminé par ses éléments, et deux ensembles ayant les mêmes éléments sont égaux. Tout le reste en découle.

Appartenance et inclusion

Définition

Soit $E$ un ensemble. On note $x \in E$ pour dire que $x$ est un élément de $E$ , et $x \notin E$ pour la négation.

Un ensemble se décrit en extension, en listant ses éléments entre accolades, ou en compréhension, en donnant la propriété qui les caractérise : ${x \in E; P (x)}$ . L'ensemble sans aucun élément est l'ensemble vide, noté $\emptyset$ .

$A$ est une partie de $E$ , ou est inclus dans $E$ , ce qu'on note $A \subset E$ , lorsque tout élément de $A$ est élément de $E$ : $\forall x, (x \in A \Rightarrow x \in E)$ .

Remarque

$\in$ et $\subset$ ne sont pas la même chose, et c'est le premier point d'échec du premier TD. L'appartenance relie un élément à un ensemble ; l'inclusion relie deux ensembles. Le piège vient de ce qu'un ensemble peut être élément d'un autre ensemble.

Prenons $E = {1, {1}}$ , qui a deux éléments : le nombre $1$ , et l'ensemble ${1}$ . Alors :

a. $1 \in E$ : vrai, c'est le premier élément.

b. ${1} \in E$ : vrai, c'est le second élément.

c. ${1} \subset E$ : vrai, car $1 \in E$ .

d. $1 \subset E$ : dépourvu de sens, $1$ n'est pas un ensemble.

Les points b et c sont tous deux vrais, pour des raisons entièrement différentes : le premier parce que ${1}$ figure dans la liste des éléments, le second parce que l'unique élément de ${1}$ figure dans cette liste. Sur un ensemble où l'un serait vrai et l'autre faux, la confusion coûte la question entière.

Propriété

Pour tout ensemble $E$ : $\emptyset \subset E$ et $E \subset E$ . De plus, l'inclusion est transitive : si $A \subset B$ et $B \subset C$ , alors $A \subset C$ .

Démonstration. L'inclusion $\emptyset \subset E$ signifie « pour tout $x$ , si $x \in \emptyset$ alors $x \in E$ ». L'hypothèse de cette implication n'est jamais réalisée : c'est une implication vide, donc vraie. Pour la transitivité, soit $x \in A$ ; alors $x \in B$ par la première inclusion, puis $x \in C$ par la seconde. $□$

Égalité par double inclusion

Propriété

Soient $A$ et $B$ deux ensembles. Alors $A = B$ si et seulement si $A \subset B$ et $B \subset A$ .

C'est la traduction directe du fait qu'un ensemble est déterminé par ses éléments : $A = B$ signifie $\forall x, (x \in A ⟺ x \in B)$ , et une équivalence, c'est deux implications.

Méthode

Démontrer une égalité d'ensembles. Deux rédactions sont admises, et une seule est sans risque.

Par double inclusion, toujours valable. Montrons les deux inclusions. Soit $x \in A$ ; … donc $x \in B$ : d'où $A \subset B$ . Réciproquement, soit $x \in B$ ; … donc $x \in A$ : d'où $B \subset A$ . Par double inclusion, $A = B$ .

Par équivalences, plus rapide mais plus exposée. Soit $x$ . On a $x \in A ⟺ \dots ⟺ x \in B$ . Donc $A = B$ . Elle n'est correcte que si chaque flèche est bien une équivalence, ce qu'il faut vérifier ligne à ligne.

Réunion, intersection, complémentaire, différence

Définition

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

La réunion : $A \cup B = {x \in E; x \in A ou x \in B}$ .
L'intersection : $A \cap B = {x \in E; x \in A et x \in B}$ . Si $A \cap B = \emptyset$ , les parties sont dites disjointes.
Le complémentaire de $A$ dans $E$ : $\overline{A} = {x \in E; x \notin A}$ .
La différence : $A ∖ B = {x \in A; x \notin B}$ .

Propriété

Soient $A$ , $B$ , $C$ des parties de $E$ . Les opérations $\cup$ et $\cap$ sont commutatives, associatives et idempotentes ; chacune est distributive sur l'autre :

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

De plus $\overline{\overline{A}} = A$ , $A \cup \overline{A} = E$ et $A \cap \overline{A} = \emptyset$ .

Chacune de ces égalités se démontre en une ligne à partir de la propriété correspondante des connecteurs. Par exemple, pour la première distributivité : $x \in A \cap (B \cup C)$ équivaut à « $x \in A$ et ( $x \in B$ ou $x \in C$ ) », donc, par distributivité du « et » sur le « ou », à « ( $x \in A$ et $x \in B$ ) ou ( $x \in A$ et $x \in C$ ) », c'est-à-dire à $x \in (A \cap B) \cup (A \cap C)$ .

Propriété

Lois de De Morgan ensemblistes. Pour toutes parties $A$ et $B$ d'un ensemble $E$ :

\overline{A \cup B} = \overline{A} \cap \overline{B}, \overline{A \cap B} = \overline{A} \cup \overline{B} .

Démonstration. Établissons la première par double inclusion, en rédigeant complètement.

Soit $x \in \overline{A \cup B}$ . Alors $x \in E$ et $x \notin A \cup B$ , c'est-à-dire qu'il est faux que $x$ appartienne à $A$ ou à $B$ . D'après la loi de De Morgan logique, cela signifie que $x \notin A$ et $x \notin B$ , autrement dit $x \in \overline{A}$ et $x \in \overline{B}$ , c'est-à-dire $x \in \overline{A} \cap \overline{B}$ . D'où la première inclusion.

Réciproquement, soit $x \in \overline{A} \cap \overline{B}$ . Alors $x \in E$ , $x \notin A$ et $x \notin B$ . Si $x$ appartenait à $A \cup B$ , il appartiendrait à $A$ ou à $B$ , ce qui est exclu. Donc $x \notin A \cup B$ , c'est-à-dire $x \in \overline{A \cup B}$ . D'où la seconde inclusion, et l'égalité.

Pour la seconde loi, on applique la première aux parties $\overline{A}$ et $\overline{B}$ : elle donne $\overline{\overline{A} \cup \overline{B}} = A \cap B$ . En prenant le complémentaire des deux membres et en utilisant $\overline{\overline{X}} = X$ , il vient $\overline{A} \cup \overline{B} = \overline{A \cap B}$ . $□$

Ensemble des parties

Définition

Soit $E$ un ensemble. L'ensemble des parties de $E$ , noté $P (E)$ , est l'ensemble dont les éléments sont exactement les parties de $E$ :

A \in P (E) ⟺ A \subset E .

Cette équivalence est la seule chose à savoir, et elle est aussi le principal piège du chapitre : à gauche un $\in$ , à droite un $\subset$ . Une même relation change de symbole selon qu'on regarde $A$ comme une partie de $E$ ou comme un élément de $P (E)$ .

Exemple

Pour $E = {a, b}$ , on a $P (E) = {\emptyset, {a}, {b}, {a, b}}$ : quatre éléments.

Propriété

Si $E$ est un ensemble fini à $n$ éléments, alors $P (E)$ est fini et $c a r d P (E) = 2^{n}$ .

L'idée est qu'une partie de $E$ est entièrement déterminée par le choix, pour chacun des $n$ éléments, de le prendre ou de ne pas le prendre : cela fait deux possibilités indépendantes par élément. La démonstration rigoureuse se fait par récurrence sur $n$ , et elle est l'objet d'un exercice de ce chapitre.

Produit cartésien

Définition

Soient $E$ et $F$ deux ensembles. Le produit cartésien $E \times F$ est l'ensemble des couples $(x, y)$ avec $x \in E$ et $y \in F$ . Deux couples sont égaux lorsque leurs deux composantes le sont :

(x, y) = (x^{'}, y^{'}) ⟺ (x = x^{'} et y = y^{'}) .

On note $E^{2} = E \times E$ , et plus généralement $E^{n}$ l'ensemble des $n$ -uplets d'éléments de $E$ .

Un couple n'est pas une paire : dans $(x, y)$ l'ordre compte, dans ${x, y}$ non. En conséquence $E \times F$ et $F \times E$ sont différents en général, et $E \times F = \emptyset$ si et seulement si $E = \emptyset$ ou $F = \emptyset$ . Enfin, si $E$ et $F$ sont finis, $c a r d (E \times F) = c a r d (E) \times c a r d (F)$ .

Familles indexées, réunions et intersections quelconques, partitions

Définition

Soit $I$ un ensemble, appelé ensemble d'indices. Une famille de parties de $E$ indexée par $I$ est la donnée, pour chaque $i \in I$ , d'une partie $A_{i}$ de $E$ ; on la note $(A_{i})_{i \in I}$ . On définit alors

⋃_{i \in I} A_{i} = {x \in E; \exists i \in I, x \in A_{i}}, ⋂_{i \in I} A_{i} = {x \in E; \forall i \in I, x \in A_{i}} .

Tout est dans les quantificateurs, et ils décident de la rédaction. Pour montrer qu'un élément appartient à la réunion, il suffit d'exhiber un indice qui convient ; pour montrer qu'il appartient à l'intersection, il faut ouvrir par « soit $i \in I$ » et traiter tous les indices d'un coup.

Propriété

Lois de De Morgan pour une famille. Pour toute famille $(A_{i})_{i \in I}$ de parties de $E$ avec $I \neq \emptyset$ :

\overline{⋃_{i \in I} A_{i}} = ⋂_{i \in I} \overline{A_{i}}, \overline{⋂_{i \in I} A_{i}} = ⋃_{i \in I} \overline{A_{i}} .

La démonstration reprend mot pour mot celle du cas de deux parties, en remplaçant le « ou » par « il existe $i$ » et le « et » par « pour tout $i$ » : nier une existence donne une universalité, et réciproquement.

Définition

Une partition d'un ensemble $E$ est une famille $(A_{i})_{i \in I}$ de parties de $E$ telle que :

chaque $A_{i}$ est non vide ;
les $A_{i}$ sont deux à deux disjoints : pour tous $i \neq j$ dans $I$ , $A_{i} \cap A_{j} = \emptyset$ ;
leur réunion est $E$ tout entier : $⋃_{i \in I} A_{i} = E$ .

Les points 2 et 3 réunis disent exactement ceci : tout élément de $E$ appartient à un $A_{i}$ et à un seul. C'est la formulation à retenir, et c'est sous cette forme qu'une partition sert : elle transforme une propriété globale sur $E$ en une disjonction de cas, un cas par morceau.

Ensembles finis, cardinal, crible, principe des tiroirs

Définition

Un ensemble $E$ est fini s'il est vide, ou s'il existe un entier $n \geq 1$ et une bijection de ${1, \dots, n}$ sur $E$ . Cet entier $n$ est alors unique : on l'appelle le cardinal de $E$ et on le note $c a r d (E)$ . Par convention $c a r d (\emptyset) = 0$ . Un ensemble non fini est dit infini.

Propriété

Soient $A$ et $B$ des parties d'un ensemble fini.

Si $A \subset B$ , alors $c a r d (A) \leq c a r d (B)$ , avec égalité si et seulement si $A = B$ .
Si $A$ et $B$ sont disjoints, $c a r d (A \cup B) = c a r d (A) + c a r d (B)$ .
Formule du crible à deux ensembles : $c a r d (A \cup B) = c a r d (A) + c a r d (B) - c a r d (A \cap B)$ .
$c a r d (\overline{A}) = c a r d (E) - c a r d (A)$ , où le complémentaire est pris dans un ensemble fini $E$ .

Le point 3 se ramène au point 2 : la réunion $A \cup B$ est la réunion disjointe de $A$ et de $B ∖ A$ , tandis que $B$ est la réunion disjointe de $B ∖ A$ et de $A \cap B$ . En additionnant convenablement, les éléments comptés deux fois dans $c a r d (A) + c a r d (B)$ sont exactement ceux de $A \cap B$ , d'où la correction. La formule analogue à trois ensembles s'en déduit ; au-delà, le crible général relève du chapitre de dénombrement et n'est pas traité ici.

Propriété

Principe des tiroirs. Pour tout entier $n \geq 1$ , il n'existe aucune application injective de ${1, \dots, n + 1}$ dans ${1, \dots, n}$ .

Autrement dit : si l'on range $n + 1$ objets dans $n$ tiroirs, au moins un tiroir contient au moins deux objets.

La démonstration se fait par récurrence sur $n$ , et c'est l'objet d'un exercice de ce chapitre. La forme générale, que l'on utilisera plus loin, est la suivante : s'il existe une injection d'un ensemble fini $A$ dans un ensemble fini $B$ , alors $c a r d (A) \leq c a r d (B)$ . Sous cette forme, le principe des tiroirs est l'outil qui permet de démontrer une existence sans jamais exhiber l'objet : on compte, et on conclut qu'une collision est inévitable.

Applications

Définition, et ce que « bien définie » veut dire

Définition

Soient $E$ et $F$ deux ensembles. Une application $f$ de $E$ dans $F$ est un procédé qui associe à chaque élément $x$ de $E$ un unique élément de $F$ , noté $f (x)$ et appelé image de $x$ . On note $f : E \to F$ , et $x \mapsto f (x)$ .

L'ensemble $E$ est l'ensemble de départ, $F$ l'ensemble d'arrivée. Si $y = f (x)$ , on dit que $x$ est un antécédent de $y$ .

Deux applications $f$ et $g$ sont égales lorsqu'elles ont le même ensemble de départ, le même ensemble d'arrivée, et que $f (x) = g (x)$ pour tout $x$ . Changer l'ensemble d'arrivée change l'application, même si la formule est la même : c'est ce qui rendra possible, plus loin, de rendre une application surjective en rétrécissant son arrivée.

Méthode

Vérifier qu'une formule définit bien une application. La définition contient deux exigences, et il faut les contrôler séparément.

Existence : pour tout $x$ de $E$ , la formule produit-elle effectivement un résultat, et ce résultat est-il dans $F$ ?
Unicité : le résultat est-il déterminé sans ambiguïté par $x$ ? La question se pose dès que $x$ peut s'écrire de plusieurs façons, ou que la formule contient un choix.

Exemple

Une formule qui échoue sur l'existence. « $g : R \to R$ , $x \mapsto \frac{1}{x^{2} - 4}$ » ne définit pas une application de $R$ dans $R$ : pour $x = 2$ et $x = - 2$ , le dénominateur est nul et l'expression n'a pas de sens. Elle définit en revanche une application sur $R ∖ {- 2, 2}$ , et c'est là qu'il faut la poser.

Une formule qui échoue sur l'unicité. « $f : Z \to Z$ , $n \mapsto$ un diviseur de $n$ » ne définit pas une application : pour $n = 6$ , on pourrait répondre $1$ , $2$ , $3$ ou $6$ . La formule contient un choix qui n'est pas tranché, donc l'image n'est pas déterminée par $n$ .

Composition, restriction, prolongement

Définition

Soient $f : E \to F$ et $g : F \to G$ . La composée $g \circ f$ est l'application de $E$ dans $G$ définie par $(g \circ f) (x) = g (f (x))$ pour tout $x \in E$ .

L'identité de $E$ est l'application ${i d}_{E} : E \to E$ , $x \mapsto x$ .

Propriété

La composition est associative : pour $f : E \to F$ , $g : F \to G$ et $h : G \to H$ , on a $h \circ (g \circ f) = (h \circ g) \circ f$ . Elle admet les identités pour éléments neutres : $f \circ {i d}_{E} = f$ et ${i d}_{F} \circ f = f$ .

Démonstration de l'associativité. Les deux composées vont de $E$ dans $H$ . Soit $x \in E$ : les deux valent $h (g (f (x)))$ , en appliquant deux fois la définition. Elles coïncident donc en tout point, et sont égales. $□$

En revanche la composition n'est pas commutative. Sur $R$ , prenons $f : x \mapsto x + 1$ et $g : x \mapsto 3 x$ . Alors $(g \circ f) (0) = g (1) = 3$ tandis que $(f \circ g) (0) = f (0) = 1$ : les deux composées diffèrent en $0$ , donc elles sont différentes.

Définition

Soit $f : E \to F$ et $A \subset E$ . La restriction de $f$ à $A$ , notée $f ∣_{A}$ , est l'application de $A$ dans $F$ qui à $x \in A$ associe $f (x)$ .

Réciproquement, si $A \subset E$ et $g : A \to F$ , une application $f : E \to F$ telle que $f ∣_{A} = g$ s'appelle un prolongement de $g$ à $E$ .

Image directe et image réciproque

Définition

Soit $f : E \to F$ , $A \subset E$ et $B \subset F$ .

L'image directe de $A$ est $f (A) = {y \in F; \exists x \in A, y = f (x)}$ . C'est une partie de $F$ .
L'image réciproque de $B$ est $f^{- 1} (B) = {x \in E; f (x) \in B}$ . C'est une partie de $E$ .

On note $I m (f) = f (E)$ l'image de $f$ .

Les deux caractérisations à utiliser sans arrêt sont donc

y \in f (A) ⟺ \exists x \in A, y = f (x), x \in f^{- 1} (B) ⟺ f (x) \in B .

Elles ne se manient pas de la même façon, et c'est la source de la moitié des erreurs. La seconde est une équivalence directe, sans quantificateur : elle se prête aux démonstrations par équivalences, et c'est pour cela que l'image réciproque se comporte bien avec toutes les opérations ensemblistes. La première contient un $\exists$ : elle donne, dans le sens utile, une implication seulement, et c'est pour cela que l'image directe ne se comporte bien qu'avec la réunion.

Remarque

Attention : $f^{- 1} (B)$ a un sens même si $f$ n'est pas bijective. La notation $f^{- 1}$ désigne ici un procédé qui transforme une partie de $F$ en une partie de $E$ , et rien d'autre. Elle ne suppose aucune hypothèse sur $f$ , elle ne désigne aucune application de $F$ dans $E$ , et l'écriture $f^{- 1} (y)$ pour un élément $y$ n'a, elle, aucun sens tant que $f$ n'est pas bijective. On écrit $f^{- 1} ({y})$ , avec les accolades, et c'est une partie de $E$ qui peut être vide, avoir un élément, ou en avoir mille.

Propriété

Soit $f : E \to F$ , $A$ , $A^{'}$ des parties de $E$ et $B$ , $B^{'}$ des parties de $F$ .

$f (A \cup A^{'}) = f (A) \cup f (A^{'})$ .
$f (A \cap A^{'}) \subset f (A) \cap f (A^{'})$ , et l'inclusion peut être stricte.
$f^{- 1} (B \cup B^{'}) = f^{- 1} (B) \cup f^{- 1} (B^{'})$ et $f^{- 1} (B \cap B^{'}) = f^{- 1} (B) \cap f^{- 1} (B^{'})$ .
$f^{- 1} (\overline{B}) = \overline{f^{- 1} (B)}$ .
$A \subset f^{- 1} (f (A))$ et $f (f^{- 1} (B)) \subset B$ , les deux inclusions pouvant être strictes.

Démonstration du point 1. Montrons les deux inclusions. Soit $y \in f (A \cup A^{'})$ : il existe $x \in A \cup A^{'}$ tel que $y = f (x)$ . Ce $x$ appartient à $A$ ou à $A^{'}$ . Dans le premier cas $y \in f (A)$ , dans le second $y \in f (A^{'})$ ; dans les deux, $y \in f (A) \cup f (A^{'})$ .

Réciproquement, soit $y \in f (A) \cup f (A^{'})$ . Supposons par exemple $y \in f (A)$ : il existe alors $x \in A$ tel que $y = f (x)$ , et comme $A \subset A \cup A^{'}$ , ce même $x$ appartient à $A \cup A^{'}$ , donc $y \in f (A \cup A^{'})$ . Le cas $y \in f (A^{'})$ est identique. D'où l'égalité. $□$

Le point 2 s'obtient de la même façon dans un seul sens, et il s'arrête là : si $y \in f (A) \cap f (A^{'})$ , on dispose d'un $x \in A$ et d'un $x^{'} \in A^{'}$ ayant tous deux $y$ pour image, mais rien ne dit que $x = x^{'}$ . C'est exactement le point où l'injectivité manquerait. Les points 3, 4 et 5 se démontrent en revenant aux caractérisations ci-dessus ; les inclusions strictes des points 2 et 5 sont examinées dans les exercices.

Injection, surjection, bijection

Définition

Soit $f : E \to F$ .

$f$ est injective lorsque $\forall x \in E, \forall x^{'} \in E, (f (x) = f (x^{'}) \Rightarrow x = x^{'})$ : deux éléments distincts ont des images distinctes.
$f$ est surjective lorsque $\forall y \in F, \exists x \in E, y = f (x)$ : tout élément de l'arrivée a au moins un antécédent.
$f$ est bijective lorsqu'elle est injective et surjective, c'est-à-dire lorsque tout élément de $F$ a exactement un antécédent : $\forall y \in F, \exists! x \in E, y = f (x)$ .

Méthode

Les phrases exactes à écrire. Ce sont elles qui sont attendues, et elles suffisent presque toujours à structurer la question.

Injectivité. Soient $x$ et $x^{'}$ dans $E$ tels que $f (x) = f (x^{'})$ . Montrons que $x = x^{'}$ . …

Non-injectivité. Prenons $x = \dots$ et $x^{'} = \dots$ . On a $x \neq x^{'}$ et pourtant $f (x) = f (x^{'}) = \dots$ , donc $f$ n'est pas injective. Il faut deux éléments explicites.

Surjectivité. Soit $y \in F$ . Cherchons un antécédent de $y$ par $f$ . Posons $x = \dots$ ; il appartient bien à $E$ car … , et $f (x) = \dots = y$ . Donc $f$ est surjective.

Non-surjectivité. Montrons que $y_{0} = \dots$ n'a pas d'antécédent. Supposons qu'il existe $x \in E$ tel que $f (x) = y_{0}$ ; alors … , ce qui est impossible.

Deux pièges de rédaction reviennent constamment. Pour la surjectivité, le $x$ construit dépend de $y$ : c'est normal et c'est même le but, puisque $y$ est fixé avant. Mais il faut vérifier que ce $x$ appartient bien à $E$ — c'est l'étape que les copies sautent, et c'est souvent là qu'est toute la difficulté. Pour l'injectivité, il ne faut pas confondre l'énoncé « $f (x) = f (x^{'}) \Rightarrow x = x^{'}$ » avec sa réciproque « $x = x^{'} \Rightarrow f (x) = f (x^{'})$ », qui est vraie pour toute application et ne dit rien.

Exemple

Injective non surjective. $f : Z \to Z$ , $n \mapsto 2 n$ . Si $2 n = 2 n^{'}$ alors $n = n^{'}$ : elle est injective. Mais $1$ n'a pas d'antécédent, car $2 n = 1$ est impossible dans $Z$ : elle n'est pas surjective.

Surjective non injective. $g : N \to N$ , $n \mapsto ⌊ n / 2 ⌋$ . Soit $m \in N$ : l'entier $n = 2 m$ vérifie $g (n) = m$ , donc $g$ est surjective. Mais $g (2) = g (3) = 1$ avec $2 \neq 3$ : elle n'est pas injective.

Propriété

Soient $f : E \to F$ et $g : F \to G$ .

Si $f$ et $g$ sont injectives, $g \circ f$ l'est ; si elles sont surjectives, $g \circ f$ l'est ; si elles sont bijectives, $g \circ f$ l'est.
Si $g \circ f$ est injective, alors $f$ est injective.
Si $g \circ f$ est surjective, alors $g$ est surjective.

Démonstration des points 2 et 3. Pour le point 2, soient $x$ et $x^{'}$ dans $E$ tels que $f (x) = f (x^{'})$ . En appliquant $g$ , il vient $g (f (x)) = g (f (x^{'}))$ , c'est-à-dire $(g \circ f) (x) = (g \circ f) (x^{'})$ . Comme $g \circ f$ est injective, $x = x^{'}$ . Donc $f$ est injective.

Pour le point 3, soit $z \in G$ . Comme $g \circ f$ est surjective, il existe $x \in E$ tel que $g (f (x)) = z$ . L'élément $y = f (x)$ appartient à $F$ et vérifie $g (y) = z$ : c'est un antécédent de $z$ par $g$ . Donc $g$ est surjective. $□$

Les deux implications qui manquent à cette liste — « $g \circ f$ injective donc $g$ injective » et « $g \circ f$ surjective donc $f$ surjective » — sont fausses, et les contre-exemples font l'objet d'un exercice.

Application réciproque

Propriété

Soit $f : E \to F$ . Les deux assertions suivantes sont équivalentes :

$f$ est bijective ;
il existe une application $g : F \to E$ telle que $g \circ f = {i d}_{E}$ et $f \circ g = {i d}_{F}$ .

Dans ce cas, une telle $g$ est unique : on l'appelle l'application réciproque de $f$ et on la note $f^{- 1}$ .

Démonstration. Supposons $f$ bijective. Soit $y \in F$ . Par bijectivité, il existe un unique $x \in E$ tel que $f (x) = y$ ; notons-le $g (y)$ . Ce procédé associe à chaque $y$ de $F$ un unique élément de $E$ : c'est bien une application $g : F \to E$ . Par construction, $f (g (y)) = y$ pour tout $y \in F$ , c'est-à-dire $f \circ g = {i d}_{F}$ . Et pour $x \in E$ , l'élément $g (f (x))$ est l'unique antécédent de $f (x)$ ; or $x$ en est un ; par unicité, $g (f (x)) = x$ , c'est-à-dire $g \circ f = {i d}_{E}$ .

Réciproquement, supposons une telle $g$ donnée. L'application $g \circ f = {i d}_{E}$ est injective, donc $f$ est injective d'après le point 2 de la propriété précédente. L'application $f \circ g = {i d}_{F}$ est surjective, donc $f$ est surjective d'après le point 3. Ainsi $f$ est bijective.

Unicité. Soient $g$ et $h$ deux applications vérifiant la condition 2. Alors, en utilisant l'associativité,

g = g \circ {i d}_{F} = g \circ (f \circ h) = (g \circ f) \circ h = {i d}_{E} \circ h = h .

D'où l'unicité. $□$

Propriété

Si $f : E \to F$ et $g : F \to G$ sont bijectives, alors $f^{- 1}$ est bijective de réciproque $f$ , et $g \circ f$ est bijective avec $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ .

Le premier point est immédiat : la condition 2 est symétrique en $f$ et $g$ . Pour le second, il suffit de vérifier que $f^{- 1} \circ g^{- 1}$ convient, en composant : $(f^{- 1} \circ g^{- 1}) \circ (g \circ f) = f^{- 1} \circ (g^{- 1} \circ g) \circ f = f^{- 1} \circ f = {i d}_{E}$ , et de même dans l'autre sens. L'ordre s'inverse, exactement comme lorsqu'on se déshabille dans l'ordre inverse de l'habillage.

Le cas des ensembles finis

Propriété

Soient $E$ et $F$ deux ensembles finis de même cardinal, et $f : E \to F$ . Les trois assertions suivantes sont équivalentes : $f$ est injective ; $f$ est surjective ; $f$ est bijective.

Le mécanisme est le principe des tiroirs. Si $f$ est injective, l'image $f (E)$ a autant d'éléments que $E$ , donc autant que $F$ ; étant une partie de $F$ de même cardinal que $F$ , elle est égale à $F$ , ce qui est la surjectivité. Inversement, si $f$ est surjective sans être injective, deux éléments distincts auraient même image et l'on couvrirait $F$ avec strictement moins de valeurs que $c a r d (E)$ , ce qui contredit l'égalité des cardinaux. La rédaction complète est l'objet d'un exercice.

Remarque

La finitude est indispensable, et c'est ce qui rend l'infini intéressant. L'application $s : N \to N$ , $n \mapsto n + 1$ , est injective et n'est pas surjective : $0$ n'a pas d'antécédent. Sur un ensemble infini, une application peut donc mettre l'ensemble en bijection avec une partie stricte de lui-même. C'est même une caractérisation possible des ensembles infinis, et le point de départ de la dernière section de ce chapitre.

Relations binaires

Relation binaire et ses quatre propriétés

Définition

Une relation binaire $R$ sur un ensemble $E$ est la donnée, pour chaque couple $(x, y)$ d'éléments de $E$ , du fait que $x$ est en relation avec $y$ ou non. On écrit alors $x R y$ . Formellement, $R$ est déterminée par la partie $Γ = {(x, y) \in E \times E; x R y}$ , appelée son graphe.

Définition

Une relation $R$ sur $E$ est dite :

réflexive si $\forall x \in E, x R x$ ;
symétrique si $\forall x \in E, \forall y \in E, (x R y \Rightarrow y R x)$ ;
antisymétrique si $\forall x \in E, \forall y \in E, ((x R y et y R x) \Rightarrow x = y)$ ;
transitive si $\forall x, y, z \in E, ((x R y et y R z) \Rightarrow x R z)$ .

Remarque

Antisymétrique ne veut pas dire « non symétrique ». Ce sont deux notions indépendantes. La relation d'égalité est à la fois symétrique et antisymétrique. La relation « $x$ et $y$ ont même signe strict » sur $R^{*}$ est symétrique et non antisymétrique. La relation « $x < y$ » sur $R$ est antisymétrique — l'hypothèse de l'implication n'est jamais réalisée, donc l'implication est vraie — et non symétrique.

Relations d'équivalence, classes et partition

Définition

Une relation d'équivalence sur $E$ est une relation binaire réflexive, symétrique et transitive. Pour $x \in E$ , la classe d'équivalence de $x$ est la partie

c l (x) = {y \in E; y R x} .

Tout élément de $c l (x)$ est appelé un représentant de cette classe.

Remarque

Notation. Beaucoup d'ouvrages notent $\overset{ˉ}{x}$ la classe de $x$ . Nous ne le faisons pas : dans tout ce chapitre, la barre horizontale désigne le complémentaire d'une partie, et une seule notation par objet est la seule protection contre les confusions d'impression. Nous écrirons donc toujours $c l (x)$ .

Propriété

Soit $R$ une relation d'équivalence sur $E$ , et soient $x, y \in E$ .

$x \in c l (x)$ ; en particulier $c l (x)$ n'est jamais vide.
$x R y ⟺ c l (x) = c l (y)$ .
Si $c l (x) \cap c l (y) \neq \emptyset$ , alors $c l (x) = c l (y)$ : deux classes sont égales ou disjointes.

Démonstration. Le point 1 est exactement la réflexivité.

Point 2, sens direct. Supposons $x R y$ , et montrons $c l (x) = c l (y)$ par double inclusion. Soit $z \in c l (x)$ , c'est-à-dire $z R x$ . Avec $x R y$ , la transitivité donne $z R y$ , donc $z \in c l (y)$ : d'où $c l (x) \subset c l (y)$ . Réciproquement, soit $z \in c l (y)$ , c'est-à-dire $z R y$ ; la symétrie appliquée à l'hypothèse donne $y R x$ , et la transitivité donne $z R x$ , donc $z \in c l (x)$ . D'où l'égalité.

Point 2, sens réciproque. Supposons $c l (x) = c l (y)$ . Par le point 1, $x \in c l (x)$ , donc $x \in c l (y)$ , c'est-à-dire $x R y$ .

Point 3. Supposons qu'il existe $z \in c l (x) \cap c l (y)$ . Alors $z R x$ et $z R y$ . Par symétrie, $x R z$ , puis par transitivité avec $z R y$ , il vient $x R y$ . Le point 2 donne alors $c l (x) = c l (y)$ . $□$

Propriété

Les classes d'équivalence forment une partition. Soit $R$ une relation d'équivalence sur un ensemble $E$ non vide. L'ensemble des classes d'équivalence est une partition de $E$ .

Réciproquement, toute partition de $E$ provient d'une unique relation d'équivalence : celle qui met en relation deux éléments lorsqu'ils appartiennent au même morceau.

Démonstration. Vérifions les trois points de la définition d'une partition.

Les classes sont non vides : c'est le point 1 de la propriété précédente.

Elles sont deux à deux disjointes : si deux classes ne sont pas disjointes, le point 3 affirme qu'elles sont égales. Deux classes distinctes sont donc bien d'intersection vide.

Leur réunion est $E$ : l'inclusion de la réunion dans $E$ est claire, puisque chaque classe est une partie de $E$ . Réciproquement, soit $x \in E$ ; alors $x \in c l (x)$ , donc $x$ appartient à la réunion des classes. D'où l'égalité.

Exemple

Fixons un entier $n \geq 1$ et posons, pour $a, b \in Z$ : $a \equiv b [n]$ lorsque $n$ divise $b - a$ . C'est une relation d'équivalence : elle est réflexive car $n$ divise $0$ ; symétrique car si $n$ divise $b - a$ , il divise son opposé $a - b$ ; transitive car si $n$ divise $b - a$ et $c - b$ , il divise leur somme $c - a$ .

Ses classes sont les $n$ ensembles $c l (0), c l (1), \dots, c l (n - 1)$ , où $c l (r)$ rassemble les entiers de reste $r$ dans la division par $n$ . Elles forment bien une partition de $Z$ : tout entier a un reste, et un seul. La théorie de la divisibilité relève d'un autre chapitre ; la congruence ne sert ici que d'exemple.

Ensemble quotient et surjection canonique

Définition

Soit $R$ une relation d'équivalence sur $E$ . L'ensemble quotient de $E$ par $R$ , noté $E / R$ , est l'ensemble des classes d'équivalence. La surjection canonique est l'application

π : E \to E / R, x \mapsto c l (x) .

Elle est bien surjective, par définition même : toute classe est la classe d'au moins un élément. Le geste que cette construction rend possible est le suivant : on décide de ne plus distinguer deux éléments en relation, et l'on travaille dans un ensemble où ils sont devenus le même objet.

Remarque

Selon les facs. L'ensemble quotient n'est pas construit partout en première année : certaines maquettes se contentent des classes d'équivalence et repoussent le quotient au cours de structures algébriques, d'autres le construisent dès le premier semestre parce que $Z / n Z$ y sert immédiatement.

Il est traité ici parce qu'il porte un geste de rédaction qui, lui, tombe à tous les partiels : vérifier qu'une opération définie sur les classes est bien définie. Si l'on veut poser $c l (x) ⋆ c l (y) = c l (x * y)$ , le membre de droite dépend a priori des représentants $x$ et $y$ choisis, alors que le membre de gauche n'en dépend pas. Il faut donc démontrer que si $c l (x) = c l (x^{'})$ et $c l (y) = c l (y^{'})$ , alors $c l (x * y) = c l (x^{'} * y^{'})$ . Sans cette vérification, l'écriture n'a pas de sens : c'est le défaut d'unicité rencontré au début de la section sur les applications, sous son déguisement le plus fréquent.

Relations d'ordre

Définition

Une relation d'ordre sur $E$ est une relation binaire réflexive, antisymétrique et transitive. On la note souvent $⪯$ , et le couple $(E, ⪯)$ s'appelle un ensemble ordonné.

L'ordre est total si deux éléments quelconques sont toujours comparables : $\forall x, y \in E, (x ⪯ y ou y ⪯ x)$ . Sinon il est partiel.

Exemple

$(R, \leq)$ est totalement ordonné. $(P (E), \subset)$ ne l'est pas dès que $E$ a au moins deux éléments : pour $E = {1, 2}$ , les parties ${1}$ et ${2}$ ne sont pas comparables, aucune n'étant incluse dans l'autre. De même, $(N^{*}, divise)$ est un ordre partiel : $2$ et $3$ ne se divisent pas l'un l'autre.

Définition

Soit $(E, ⪯)$ un ensemble ordonné et $A$ une partie de $E$ .

$M \in E$ est un majorant de $A$ si $\forall a \in A, a ⪯ M$ . On définit de même un minorant.
$M$ est le plus grand élément de $A$ si $M$ est un majorant de $A$ et $M \in A$ . De même pour le plus petit élément.
La borne supérieure de $A$ , notée $\sup A$ , est le plus petit élément de l'ensemble des majorants de $A$ , lorsqu'il existe. La borne inférieure $\inf A$ est le plus grand des minorants.

Propriété

Le plus grand élément d'une partie, la borne supérieure d'une partie, sont uniques lorsqu'ils existent.

Démonstration. Traitons le plus grand élément. Soient $M$ et $M^{'}$ deux plus grands éléments de $A$ . Alors $M \in A$ et $M^{'}$ majore $A$ , donc $M ⪯ M^{'}$ ; symétriquement $M^{'} ⪯ M$ . L'antisymétrie donne $M = M^{'}$ . Le raisonnement est identique pour la borne supérieure, qui est le plus petit élément d'une certaine partie. $□$

C'est ici que l'antisymétrie sert : sans elle, ces objets ne seraient pas uniques et on ne pourrait pas parler « du » plus grand élément.

Remarque

Plus grand élément et borne supérieure : la distinction qui coûte le plus cher. Un plus grand élément appartient à la partie ; une borne supérieure n'y est pas obligée. Un plus grand élément est toujours borne supérieure ; l'inverse est faux.

Dans $(P ({1, 2}), \subset)$ , considérons $A = {{1}, {2}}$ . Ses majorants sont les parties contenant ${1}$ et ${2}$ , c'est-à-dire la seule partie ${1, 2}$ . Cette partie est donc la borne supérieure de $A$ — et elle n'appartient pas à $A$ . La partie $A$ n'a donc pas de plus grand élément, alors qu'elle a une borne supérieure. Un réflexe utile : après avoir trouvé un $\sup$ , demandez-vous toujours s'il appartient à la partie.

Le cas particulier de $R$ , où toute partie non vide majorée admet une borne supérieure, n'est pas traité ici : c'est une propriété propre à $R$ , et elle est étudiée dans le chapitre consacré aux suites réelles.

Propriété

Dans $(P (E), \subset)$ , toute famille $(A_{i})_{i \in I}$ de parties admet une borne supérieure et une borne inférieure, à savoir sa réunion et son intersection.

Démonstration pour la borne supérieure. Posons $U = ⋃_{i \in I} A_{i}$ . D'abord, $U$ est un majorant de la famille : pour tout $j \in I$ et tout $x \in A_{j}$ , on a bien $x \in U$ , donc $A_{j} \subset U$ . Ensuite, $U$ est le plus petit : soit $M$ un majorant quelconque, c'est-à-dire une partie telle que $A_{i} \subset M$ pour tout $i$ ; soit $x \in U$ ; il existe alors $i \in I$ tel que $x \in A_{i}$ , donc $x \in M$ . D'où $U \subset M$ . L'ensemble des majorants admet donc $U$ pour plus petit élément : $U = \sup$ de la famille. $□$

Remarque

Selon les facs. Les ordres construits à partir d'autres ordres sont traités dans certaines maquettes seulement, souvent comme réservoir d'exemples d'ordres non totaux. Ils méritent d'être connus.

Sur un produit $E \times F$ d'ensembles ordonnés, l'ordre produit est défini par

(x, y) ⪯ (x^{'}, y^{'}) ⟺ (x \leq x^{'} et y \leq y^{'}) .

C'est un ordre, et il n'est pas total dès que $E$ et $F$ ont chacun deux éléments comparables distincts : dans $R^{2}$ , les couples $(0, 1)$ et $(1, 0)$ ne sont pas comparables.

L'ordre lexicographique, celui du dictionnaire, est défini par

(x, y) ⪯_{lex} (x^{'}, y^{'}) ⟺ (x < x^{'}) ou (x = x^{'} et y \leq y^{'}) .

Il est total dès que les deux ordres de départ le sont : on compare les premières composantes, et on ne regarde les secondes qu'en cas d'égalité. Ces deux ordres sur $R^{2}$ sont étudiés en détail dans les exercices.

Dénombrabilité

Remarque

Selon les facs. La dénombrabilité est enseignée en première année dans une partie des maquettes seulement ; ailleurs elle apparaît en deuxième année, dans un cours de topologie ou de théorie de la mesure. Elle est traitée ici pour deux raisons : elle ne demande rien d'autre que les notions de ce chapitre, et elle répond à une question que tout le monde se pose au premier semestre — y a-t-il plusieurs tailles d'infini ?

Définition

Un ensemble $E$ est dénombrable s'il existe une bijection de $N$ sur $E$ . Il est dit au plus dénombrable s'il est fini ou dénombrable.

Propriété

Les ensembles $N$ , $Z$ , $N \times N$ et $Q$ sont dénombrables. Toute partie infinie de $N$ est dénombrable. L'image d'un ensemble dénombrable par une application surjective est au plus dénombrable.

Ces résultats sont établis dans les exercices du chapitre, et ils réservent une surprise : $Q$ est dénombrable, alors même qu'entre deux rationnels distincts il y en a toujours un autre. « Être dénombrable » ne dit donc rien de la densité, ni de la taille au sens intuitif.

Propriété

Théorème de Cantor. Pour tout ensemble $E$ , il n'existe aucune application surjective de $E$ sur $P (E)$ .

En particulier, l'ensemble des suites à valeurs dans ${0, 1}$ n'est pas dénombrable, et $R$ non plus.

Ce théorème est le point d'arrivée du chapitre, et il n'est pas anodin : il affirme qu'il existe plusieurs infinis, et qu'aucun ensemble ne peut être mis en bijection avec l'ensemble de ses parties, si grand soit-il. Sa démonstration, dans la version portant sur les suites de $0$ et de $1$ , fait l'objet d'un exercice : elle repose sur un procédé diagonal qui construit explicitement, à partir de n'importe quelle liste de suites, une suite qui n'y figure pas.

Le cours en PDF(PDF, 214 Ko)

Bloqué sur « Logique, raisonnement, ensembles et applications » ?

On peut le travailler ensemble dès cette semaine. La première heure est offerte — on fait le point honnêtement, et vous repartez au minimum avec une méthode.

Réserver ma 1ʳᵉ heure offerte

Licence 1 maths

L1 maths · Chapitre 01

Logique, raisonnement, ensembles et applications

Ce qu'il faut savoir faire

Quantificateurs
Connecteurs
Négation d'un énoncé
Récurrence
Raisonnement par l'absurde et par contraposée
Analyse-synthèse
Ensembles et parties
Image directe et image réciproque
Injectivité
Surjectivité
Bijectivité
Relations d'équivalence et d'ordre

Remarque

Assertions, connecteurs et implication

Assertion et valeur de vérité

Définition

a. « $7$ est un nombre premier » : vraie.

b. « $5 \in Q$ » : vraie.

c. « $Z \subset N$ » : fausse.

d. « $0 \in \emptyset$ » : fausse.

e. « $(- 2)^{3} = - 8$ » : vraie.

f. « $π$ est un entier » : fausse.

Définition

Les connecteurs et leurs tables de vérité

À partir d'assertions données, on en fabrique de nouvelles avec des connecteurs logiques.

Définition

Soient $P$ et $Q$ deux assertions.

La négation de $P$ , notée $\neg P$ et lue « non $P$ », est vraie lorsque $P$ est fausse, et fausse lorsque $P$ est vraie.
La conjonction $P \land Q$ , lue « $P$ et $Q$ », est vraie lorsque les deux le sont, et fausse sinon.
La disjonction $P \lor Q$ , lue « $P$ ou $Q$ », est vraie lorsque l'une au moins des deux est vraie, et fausse lorsque les deux sont fausses.

Ces définitions se lisent entièrement sur une table de vérité, qui énumère les quatre cas possibles :

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

Remarque

Définition

Une assertion vraie dans tous les cas s'appelle une tautologie ; une assertion fausse dans tous les cas s'appelle une contradiction (ou antilogie).

Ainsi $P \lor \neg P$ est une tautologie, et $P \land \neg P$ une contradiction : ce sont les deux principes admis plus haut, réécrits comme des formules.

Propriété

Soient $P$ , $Q$ , $R$ trois assertions.

Double négation : $\neg (\neg P) \equiv P$ .
Commutativité : $P \land Q \equiv Q \land P$ et $P \lor Q \equiv Q \lor P$ .
Associativité : $(P \land Q) \land R \equiv P \land (Q \land R)$ , et de même pour $\lor$ .
Idempotence : $P \land P \equiv P$ et $P \lor P \equiv P$ .
Distributivité de chacun sur l'autre : $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$ , et $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$ .

Remarque

Implication, réciproque, contraposée, équivalence

Définition

Soient $P$ et $Q$ deux assertions. L'assertion $P \Rightarrow Q$ , lue « $P$ implique $Q$ » ou « si $P$ alors $Q$ », est par définition l'assertion $\neg P \lor Q$ .

Elle est donc fausse dans le seul cas où $P$ est vraie et $Q$ est fausse, et vraie dans les trois autres.

$P$	$Q$	$P \Rightarrow Q$	$Q \Rightarrow P$	$\neg Q \Rightarrow \neg P$
V	V	V	V	V
V	F	F	V	F
F	V	V	F	V
F	F	V	V	V

Remarque

Définition

Soit une implication $P \Rightarrow Q$ .

Sa réciproque est l'implication $Q \Rightarrow P$ .
Sa contraposée est l'implication $\neg Q \Rightarrow \neg P$ .

Propriété

Une implication et sa contraposée sont logiquement équivalentes :

(P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P) .

Les deux dernières colonnes du tableau ci-dessus coïncident ligne à ligne : c'est la lecture graphique du même résultat.

Remarque

Contraposée et réciproque n'ont rien à voir, et c'est la confusion la plus coûteuse du premier semestre.

Définition

L'assertion $P ⟺ Q$ , lue « $P$ équivaut à $Q$ » ou « $P$ si et seulement si $Q$ », est vraie lorsque $P$ et $Q$ ont la même valeur de vérité, et fausse sinon.

Propriété

$(P ⟺ Q) \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ .

Remarque

Propriété

Transitivité de l'implication (syllogisme). L'assertion $((P \Rightarrow Q) \land (Q \Rightarrow R)) \Rightarrow (P \Rightarrow R)$ est une tautologie.

C'est la règle qui autorise l'enchaînement de déductions d'une démonstration : chaque « donc » est une application de ce résultat.

Négation : lois de De Morgan et négation d'une implication

Propriété

Lois de De Morgan logiques. Pour toutes assertions $P$ et $Q$ :

\neg (P \land Q) \equiv \neg P \lor \neg Q, \neg (P \lor Q) \equiv \neg P \land \neg Q .

Propriété

Négation d'une implication. Pour toutes assertions $P$ et $Q$ :

\neg (P \Rightarrow Q) \equiv P \land \neg Q .

Remarque

Condition nécessaire, condition suffisante

Définition

Soit l'implication $P \Rightarrow Q$ , supposée vraie. On dit alors que :

$P$ est une condition suffisante pour $Q$ : il suffit que $P$ soit vraie pour que $Q$ le soit ;
$Q$ est une condition nécessaire pour $P$ : il faut que $Q$ soit vraie pour que $P$ puisse l'être.

Lorsque $P ⟺ Q$ , on dit que $P$ est une condition nécessaire et suffisante pour $Q$ .

Ce vocabulaire est celui des énoncés de concours, des sujets de partiel et des articles : il faut pouvoir le traduire sans y penser.

Méthode

Traduire une phrase en implication. Repérez le mot clé, il donne le sens de la flèche.

« Il suffit que $P$ pour que $Q$ » se traduit par $P \Rightarrow Q$ . La condition suffisante est à la source de la flèche.
« Il faut que $Q$ pour que $P$ » se traduit par $P \Rightarrow Q$ . La condition nécessaire est à la pointe de la flèche.
« $P$ seulement si $Q$ » se traduit par $P \Rightarrow Q$ .
« $P$ si $Q$ » se traduit par $Q \Rightarrow P$ : attention, la flèche est dans l'autre sens.
« $P$ si et seulement si $Q$ » se traduit par $P ⟺ Q$ .

Exemple

Considérons, pour un entier $n$ , les deux assertions « $n$ est un multiple de $12$ » et « $n$ est pair ».

Enfin, « $n$ est multiple de $3$ et $n$ est multiple de $4$ » est une condition nécessaire et suffisante pour que $n$ soit multiple de $12$ .

Quantificateurs

Les quantificateurs, variables libres et liées

Définition

Soit $E$ un ensemble et $P (x)$ un prédicat portant sur les éléments de $E$ .

L'assertion $\forall x \in E, P (x)$ , lue « pour tout $x$ de $E$ , $P (x)$ », est vraie lorsque $P (x)$ est vraie pour chaque élément $x$ de $E$ . Le symbole $\forall$ est le quantificateur universel.
L'assertion $\exists x \in E, P (x)$ , lue « il existe $x$ dans $E$ tel que $P (x)$ », est vraie lorsqu'il y a au moins un élément $x$ de $E$ pour lequel $P (x)$ est vraie. Le symbole $\exists$ est le quantificateur existentiel.

Définition

Remarque

L'ordre des quantificateurs change le sens

C'est le point de cette section qu'il faut retenir avant tous les autres, parce qu'il coûte plus de points que n'importe quel autre en première année.

Exemple

\forall x \in E, \exists y \in E, M (x, y)

se lit : « tout habitant a une mère ». C'est raisonnable.

\exists y \in E, \forall x \in E, M (x, y)

se lit : « il existe une habitante qui est la mère de tous les habitants ». C'est absurde.

Exemple

La même distinction, sur un énoncé de mathématiques que vous rencontrerez dès le chapitre suivant. Soit $(u_{n})$ une suite réelle. Comparons :

\forall n \in N, \exists M \in R, u_{n} \leq M et \exists M \in R, \forall n \in N, u_{n} \leq M .

La première est vraie pour toute suite, sans exception : il suffit, une fois $n$ fixé, de prendre $M = u_{n}$ . Elle ne dit donc strictement rien.

Une copie qui démontre la première en croyant démontrer la seconde ne vaut aucun point, et c'est une copie que l'on voit à chaque session.

Propriété

Deux quantificateurs de même nature qui se suivent peuvent être échangés :

(\forall x \in E, \forall y \in F, P (x, y)) \equiv (\forall y \in F, \forall x \in E, P (x, y)),

et de même pour deux $\exists$ consécutifs. En revanche, $\exists$ et $\forall$ ne commutent pas : on a seulement l'implication

(\exists y \in F, \forall x \in E, P (x, y)) \Rightarrow (\forall x \in E, \exists y \in F, P (x, y)),

et la réciproque est fausse en général.

Négation d'un énoncé quantifié

Propriété

Pour tout ensemble $E$ et tout prédicat $P$ :

\neg (\forall x \in E, P (x)) \equiv (\exists x \in E, \neg P (x)), \neg (\exists x \in E, P (x)) \equiv (\forall x \in E, \neg P (x)) .

Ces deux règles sont les analogues exacts des lois de De Morgan : le $\forall$ joue le rôle d'un « et » répété sur tous les éléments, le $\exists$ celui d'un « ou ».

Méthode

La règle mécanique de négation. Pour nier un énoncé quantifié, on parcourt la formule de gauche à droite :

chaque $\forall$ devient $\exists$ , chaque $\exists$ devient $\forall$ ; l'ordre des quantificateurs ne change pas, et les ensembles ne changent pas non plus ;
on arrive au bout, sur la partie non quantifiée : on la nie, et c'est le seul endroit où il faut réfléchir ;
dans cette partie finale, on applique les règles déjà connues : un « et » devient un « ou », un « ou » devient un « et », et une implication $P \Rightarrow Q$ devient $P \land \neg Q$ .

Exemple

Nier « $f$ est injective ». Pour $f : E \to F$ , l'injectivité s'écrit

\forall x \in E, \forall x^{'} \in E, (f (x) = f (x^{'}) \Rightarrow x = x^{'}) .

La règle donne : les deux $\forall$ deviennent des $\exists$ , puis on nie l'implication finale, qui devient une conjonction. La négation est donc

\exists x \in E, \exists x^{'} \in E, (f (x) = f (x^{'}) \land x \neq x^{'}),

Remarque

Trois fautes à connaître, parce qu'elles reviennent toutes les trois à chaque partiel.

La première consiste à changer l'ordre des quantificateurs en niant. C'est toujours faux, sans discussion : la mécanique conserve l'ordre.

Le quantificateur « il existe un unique »

Définition

Soient $E$ un ensemble et $P$ un prédicat. L'assertion $\exists! x \in E, P (x)$ , lue « il existe un unique $x$ de $E$ tel que $P (x)$ », est par définition la conjonction de deux assertions :

(\exists x \in E, P (x)) \land (\forall x \in E, \forall x^{'} \in E, (P (x) \land P (x^{'})) \Rightarrow x = x^{'}) .

La première est l'existence, la seconde l'unicité.

Méthode

Démontrer un « il existe un unique ». La démonstration a toujours deux parties, séparées et annoncées.

Existence : on exhibe un objet et on vérifie qu'il convient. C'est le geste du $\exists$ .
Unicité : on se donne deux objets $x$ et $x^{'}$ vérifiant la propriété, et on montre qu'ils sont égaux. C'est le geste du $\forall$ , appliqué deux fois.

Exemple

Soient $a$ et $b$ deux réels, avec $a \neq 0$ . Montrons qu'il existe un unique réel $x$ tel que $a x + b = 0$ .

Existence. Posons $x_{0} = - \frac{b}{a}$ , ce qui a un sens puisque $a \neq 0$ . Alors $a x_{0} + b = - b + b = 0$ : cet élément convient.

Il existe donc un unique réel solution, et c'est $- \frac{b}{a}$ .

Comment on rédige une démonstration

L'anatomie d'une démonstration

Définition

Trois choses découlent de cette définition, et il faut les prendre au sérieux.

Chaque ligne doit être justifiée par ce qui précède, et par rien d'autre. Une phrase qui utilise un objet non encore introduit, ou une propriété non encore établie, casse la chaîne.

Méthode

Les trois questions à se poser avant d'écrire la première ligne. Elles prennent trente secondes et font gagner une demi-heure.

Qu'est-ce que je suppose ? Listez les hypothèses, toutes, y compris celles qui sont dans l'énoncé du chapitre et pas dans la question.
Qu'est-ce que je dois établir ? Écrivez la conclusion en toutes lettres, sur le brouillon.
Quelle est la forme logique de cette conclusion ? Un « pour tout » ? un « il existe » ? une implication ? une égalité d'ensembles ? C'est cette forme, et elle seule, qui décide de votre première phrase.

Le tableau suivant répond à la troisième question dans tous les cas que vous rencontrerez ce semestre. Il n'est pas à réciter, il est à utiliser.

Ce qu'il faut démontrer	La première ligne de la copie
$\forall x \in E, P (x)$	Soit $x \in E$ .
$\exists x \in E, P (x)$	Posons $x = \dots$ et vérifions.
$\exists! x \in E, P (x)$	Existence, puis unicité, dans cet ordre.
$P \Rightarrow Q$	Supposons $P$ .
$P ⟺ Q$	Montrons les deux implications.
$A \subset B$	Soit $x \in A$ .
$A = B$	Montrons la double inclusion.
$\neg P$	Supposons $P$ , et cherchons une contradiction.
$P \lor Q$	Supposons $\neg P$ , et montrons $Q$ .

Les deux gestes d'ouverture

Presque tout ce que vous aurez à démontrer cette année commence par l'un de ces deux gestes. Ils sont à connaître comme un pianiste connaît ses gammes.

Méthode

Geste n°1 : « Soit $x \in A$ . » C'est l'ouverture d'une démonstration de $\forall x \in A, P (x)$ .

Deux points de vigilance sur ce geste, tous les deux fréquents.

Exemple

Montrons que pour tout réel $x$ , on a $x^{2} - 2 x + 3 > 0$ .

Soit $x \in R$ . On écrit $x^{2} - 2 x + 3 = (x - 1)^{2} + 2$ . Or $(x - 1)^{2} \geq 0$ comme carré d'un réel, donc $(x - 1)^{2} + 2 \geq 2 > 0$ . Ainsi $x^{2} - 2 x + 3 > 0$ .

Ceci vaut pour tout réel $x$ , ce qui est le résultat annoncé.

Méthode

Geste n°2 : « Posons $x = \dots$ » C'est l'ouverture d'une démonstration de $\exists x \in E, P (x)$ .

Exemple

Montrons qu'il existe un entier $n \geq 0$ tel que $n^{2} + n + 41$ ne soit pas un nombre premier.

Posons $n = 41$ . Alors

n^{2} + n + 41 = 41^{2} + 41 + 41 = 41 \times (41 + 1 + 1) = 41 \times 43 = 1763.

Ce nombre s'écrit comme produit de deux entiers tous deux différents de $1$ : il n'est donc pas premier. L'entier $n = 41$ convient, ce qui établit l'existence annoncée.

Les six fautes qui coûtent le plus de points en première année

Faute n°1 — Un exemple n'est pas une démonstration.

Exemple

Énoncé. Montrer que pour tout réel $x$ , on a $x^{2} + 1 \geq 2 x$ .

Sur la copie. « Pour $x = 3$ : $9 + 1 = 10$ et $2 \times 3 = 6$ , donc $10 \geq 6$ . Pour $x = 0$ : $1 \geq 0$ . Donc pour tout réel $x$ , $x^{2} + 1 \geq 2 x$ . »

Une seule ligne a changé, et c'est la première : « Soit $x \in R$ » remplace « Pour $x = 3$ ». Toute la différence est là.

Faute n°2 — Démontrer la réciproque à la place de l'implication.

Exemple

Énoncé. Soit $x$ un réel tel que $x^{2} = 4 x - 4$ . Montrer que $x = 2$ .

Sur la copie. « Si $x = 2$ , alors $x^{2} = 4$ et $4 x - 4 = 8 - 4 = 4$ . Donc $x^{2} = 4 x - 4$ , et $x = 2$ convient. »

Faute n°3 — La flèche $\Rightarrow$ employée comme signe de ponctuation.

Exemple

Énoncé. Résoudre dans $R$ l'équation $x^{2} = 4 x - 4$ .

Sur la copie. « $x^{2} = 4 x - 4 \Rightarrow x^{2} - 4 x + 4 \Rightarrow (x - 2)^{2} \Rightarrow x = 2$ . »

La version correcte. L'équation $x^{2} = 4 x - 4$ équivaut à $x^{2} - 4 x + 4 = 0$ , c'est-à-dire à $(x - 2)^{2} = 0$ , c'est-à-dire à $x = 2$ . L'ensemble des solutions est donc ${2}$ .

Faute n°4 — L'objet qui dépend d'un autre, et le quantificateur qui glisse.

C'est la faute la plus coûteuse de toutes, et c'est aussi celle qui passe le plus facilement inaperçue à la relecture, parce que chaque ligne prise séparément est vraie.

Exemple

Énoncé. Soit $(u_{n})$ la suite définie par $u_{n} = n$ pour tout $n \in N$ . Montrer qu'elle est majorée, ou qu'elle ne l'est pas.

Sur la copie. « Soit $n \in N$ . Posons $M = u_{n}$ . Alors $u_{n} \leq M$ . Donc pour tout $n \in N$ , $u_{n} \leq M$ : la suite $(u_{n})$ est majorée. »

Faute n°5 — Diviser, ou simplifier, par une quantité qui peut être nulle.

Exemple

Énoncé. Soient $a$ et $b$ deux réels tels que $a^{2} = a b$ . Que peut-on dire de $a$ et $b$ ?

Sur la copie. « De $a^{2} = a b$ , on tire en divisant par $a$ : $a = b$ . »

Faute n°6 — Conclure d'un seul cas d'une disjonction.

Exemple

Énoncé. Montrer que pour tout entier $n$ , l'entier $n^{2} + n$ est pair.

Sur la copie. « Si $n$ est pair, il s'écrit $n = 2 k$ avec $k$ entier, et alors $n^{2} + n = 4 k^{2} + 2 k = 2 (2 k^{2} + k)$ est pair. Donc pour tout entier $n$ , $n^{2} + n$ est pair. »

La version correcte. Soit $n$ un entier. Distinguons deux cas, qui recouvrent toutes les possibilités.

Premier cas : $n$ est pair. Il s'écrit $n = 2 k$ avec $k$ entier, et alors $n^{2} + n = 2 (2 k^{2} + k)$ est pair.

Second cas : $n$ est impair. Il s'écrit $n = 2 k + 1$ avec $k$ entier, et alors $n^{2} + n = (4 k^{2} + 4 k + 1) + (2 k + 1) = 2 (2 k^{2} + 3 k + 1)$ est pair.

Dans les deux cas $n^{2} + n$ est pair, et tout entier relève de l'un des deux : le résultat est démontré pour tout entier $n$ .

Trois modèles de rédaction commentés

Méthode

Modèle 1 — Une implication.

Énoncé. Soit $n$ un entier. Si $n$ est somme de deux carrés d'entiers, alors $2 n$ l'est aussi.

Rédaction. Supposons que $n$ soit somme de deux carrés d'entiers. Il existe donc deux entiers $a$ et $b$ tels que $n = a^{2} + b^{2}$ . Considérons les entiers $a + b$ et $a - b$ . On calcule

(a + b)^{2} + (a - b)^{2} = (a^{2} + 2 a b + b^{2}) + (a^{2} - 2 a b + b^{2}) = 2 a^{2} + 2 b^{2} = 2 n .

L'entier $2 n$ est donc somme des carrés des deux entiers $a + b$ et $a - b$ : il est bien somme de deux carrés d'entiers.

Méthode

Modèle 2 — Une inclusion.

Énoncé. On pose $A = {x \in R; x^{2} < x}$ et $B = {x \in R; 0 < x < 1}$ . Montrer que $A \subset B$ .

Tout élément de $A$ appartient donc à $B$ : on a bien $A \subset B$ .

Méthode

Modèle 3 — Une équivalence, par double implication.

Énoncé. Soient $A$ et $B$ deux parties d'un ensemble $E$ . Montrer que $A \subset B$ si et seulement si $A \cap B = A$ .

Rédaction. Montrons les deux implications.

Sens réciproque. Supposons $A \cap B = A$ , et montrons $A \subset B$ . Soit $x \in A$ . L'hypothèse donne $x \in A \cap B$ , donc en particulier $x \in B$ . D'où $A \subset B$ .

Les deux implications étant établies, l'équivalence est démontrée.

Les modes de raisonnement

Raisonnement direct

Raisonnement par contraposée

Méthode

Principe. Pour démontrer $P \Rightarrow Q$ , on démontre $\neg Q \Rightarrow \neg P$ , qui lui est logiquement équivalente.

Squelette. Montrons la contraposée : si $\neg Q$ , alors $\neg P$ . Supposons donc $\neg Q$ . … Donc $\neg P$ . Par contraposée, on a bien $P \Rightarrow Q$ .

Exemple

Soit $n$ un entier. Montrons que si $n^{3} + 5$ est impair, alors $n$ est pair.

Raisonnement par l'absurde, et sa différence avec la contraposée

Méthode

Squelette. Raisonnons par l'absurde, et supposons $\neg P$ . … On aboutit à [énoncé faux], ce qui est absurde. Donc $P$ .

Exemple

Soit $x$ un réel tel que $∣ x ∣ \leq ε$ pour tout réel $ε > 0$ . Montrons que $x = 0$ .

Remarque

Absurde ou contraposée : la question que tout le monde se pose, et la réponse.

Les deux modes se ressemblent, puisque tous deux commencent par nier quelque chose. La différence est nette dès qu'on regarde ce qu'on suppose et ce qu'on obtient.

Dans une contraposée d'une implication $P \Rightarrow Q$ , on suppose $\neg Q$ seulement, et on doit arriver à $\neg P$ . Il n'y a aucune contradiction dans la démonstration : c'est un raisonnement direct, mené sur un autre énoncé.
Dans un raisonnement par l'absurde appliqué à la même implication, on suppose $P$ et $\neg Q$ à la fois, et on doit arriver à une contradiction avec n'importe quoi : une hypothèse, un résultat du cours, une évidence numérique.

Disjonction de cas

Méthode

Principe. Pour démontrer une assertion, on découpe la situation en un nombre fini de cas qui recouvrent toutes les possibilités, et on démontre l'assertion dans chacun.

Exemple

Montrons que pour tout réel $x$ , on a $x^{4} - x^{3} + x^{2} - x + 1 > 0$ .

Soit $x \in R$ . Distinguons trois cas, selon la position de $x$ par rapport à $0$ et à $1$ .

Premier cas : $x \leq 0$ . Alors $x^{4} \geq 0$ , $- x^{3} \geq 0$ , $x^{2} \geq 0$ et $- x \geq 0$ . La somme des quatre est positive ou nulle, donc l'expression vaut au moins $1 > 0$ .

Tout réel relève de l'un de ces trois cas, et l'inégalité est vraie dans chacun : elle est vraie pour tout réel $x$ .

Contre-exemple

Méthode

Squelette. Cette assertion est fausse. Prenons en effet $x_{0} = \dots$ . Alors … , donc $P (x_{0})$ est fausse, et l'assertion universelle ne peut pas être vraie.

Exemple

L'assertion « pour toutes parties $A$ , $B$ , $C$ d'un ensemble $E$ , on a $A \cap (B \cup C) = (A \cap B) \cup C$ » est fausse.

Les deux membres valent respectivement $\emptyset$ et ${2}$ : ils sont différents, et l'assertion est fausse.

Remarque

Analyse-synthèse

Méthode

Principe. On veut déterminer tous les objets vérifiant une propriété. On procède en deux temps, séparés et annoncés.

Analyse. On suppose qu'un objet $x$ convient, et on en déduit des conditions nécessaires, jusqu'à n'avoir plus qu'une liste finie de candidats. Cette étape ne démontre aucune existence : elle dit seulement « s'il y a une solution, elle est dans cette liste ».
Synthèse. On reprend chaque candidat et on vérifie s'il convient vraiment. Cette étape seule établit l'existence, et élimine les candidats parasites.

Exemple

Résolvons dans $R$ l'équation $\sqrt{x + 1} = x - 1$ .

Conclusion. L'ensemble des solutions est ${3}$ .

Raisonnement par récurrence

Propriété

Principe de récurrence. Soit $P (n)$ un prédicat portant sur les entiers naturels, et soit $n_{0} \in N$ . Si

$P (n_{0})$ est vraie, et
pour tout entier $n \geq n_{0}$ , $P (n) \Rightarrow P (n + 1)$ ,

alors $P (n)$ est vraie pour tout entier $n \geq n_{0}$ .

Récurrence simple

Méthode

Squelette de rédaction, à recopier tel quel.

Pour $n \geq n_{0}$ , notons $P (n)$ l'assertion : « … ». Montrons par récurrence que $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Initialisation. Pour $n = n_{0}$ : … . Donc $P (n_{0})$ est vraie.

Hérédité. Soit $n \geq n_{0}$ un entier tel que $P (n)$ soit vraie. Montrons que $P (n + 1)$ l'est aussi. … Donc $P (n + 1)$ est vraie.

Conclusion. $P (n_{0})$ est vraie et $P$ est héréditaire à partir du rang $n_{0}$ : d'après le principe de récurrence, $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Exemple

Montrons que pour tout $n \in N$ , on a $2^{n} \geq n + 1$ .

Pour $n \in N$ , notons $P (n)$ l'assertion « $2^{n} \geq n + 1$ ».

Initialisation. Pour $n = 0$ : $2^{0} = 1$ et $0 + 1 = 1$ , donc $2^{0} \geq 0 + 1$ . Ainsi $P (0)$ est vraie.

Conclusion. $P (0)$ est vraie et $P$ est héréditaire : $2^{n} \geq n + 1$ pour tout $n \in N$ .

Remarque

Les deux erreurs classiques.

Récurrence double

Propriété

Méthode

Squelette. Notons $P (n)$ l'assertion « … ».

Initialisation. On vérifie $P (n_{0})$ et $P (n_{0} + 1)$ — deux rangs, pas un.

Hérédité. Soit $n \geq n_{0}$ tel que $P (n)$ et $P (n + 1)$ soient vraies. Montrons $P (n + 2)$ . …

Conclusion. Par récurrence double, $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Exemple

Soit $(a_{n})$ la suite définie par $a_{0} = 0$ , $a_{1} = 1$ et, pour tout $n \in N$ , $a_{n + 2} = 4 a_{n + 1} - 3 a_{n}$ . Montrons que $a_{n} = \frac{3^{n} - 1}{2}$ pour tout $n \in N$ .

Notons $P (n)$ l'assertion « $a_{n} = \frac{3^{n} - 1}{2}$ ».

Initialisation. Pour $n = 0$ : $\frac{3^{0} - 1}{2} = 0 = a_{0}$ . Pour $n = 1$ : $\frac{3^{1} - 1}{2} = 1 = a_{1}$ . Donc $P (0)$ et $P (1)$ sont vraies.

Hérédité. Soit $n \in N$ tel que $P (n)$ et $P (n + 1)$ soient vraies. Alors

a_{n + 2} = 4 \cdot \frac{3^{n + 1} - 1}{2} - 3 \cdot \frac{3^{n} - 1}{2} = \frac{4 \cdot 3^{n + 1} - 4 - 3^{n + 1} + 3}{2} = \frac{3 \cdot 3^{n + 1} - 1}{2} = \frac{3^{n + 2} - 1}{2},

c'est-à-dire $P (n + 2)$ . Les deux hypothèses ont servi, chacune une fois.

Conclusion. Par récurrence double, $a_{n} = \frac{3^{n} - 1}{2}$ pour tout $n \in N$ .

Récurrence forte

Propriété

Principe de récurrence forte. Soit $P (n)$ un prédicat sur les entiers, et $n_{0} \in N$ . Si $P (n_{0})$ est vraie, et si pour tout $n \geq n_{0}$ l'implication

(\forall k \in {n_{0}, \dots, n}, P (k)) \Rightarrow P (n + 1)

est vraie, alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Méthode

Squelette. Notons $P (n)$ l'assertion « … ».

Initialisation. $P (n_{0})$ est vraie car … .

Conclusion. Par récurrence forte, $P (n)$ est vraie pour tout $n \geq n_{0}$ .

La phrase à ne pas rater est celle qui vérifie que le rang auquel on redescend est dans la plage autorisée. C'est là, et nulle part ailleurs, que se joue la validité d'une récurrence forte.

Exemple

Soit $(u_{n})_{n \geq 1}$ la suite définie par $u_{1} = 1$ et, pour tout $n \geq 2$ , $u_{n} = u_{1} + u_{2} + \dots + u_{n - 1}$ . Montrons que $u_{n} = 2^{n - 2}$ pour tout $n \geq 2$ .

Notons $P (n)$ l'assertion « $u_{n} = 2^{n - 2}$ », pour $n \geq 2$ .

Initialisation. $u_{2} = u_{1} = 1 = 2^{0}$ , donc $P (2)$ est vraie.

u_{n + 1} = 1 + \sum_{k = 2}^{n} 2^{k - 2} = 1 + (2^{n - 1} - 1) = 2^{n - 1} = 2^{(n + 1) - 2},

en reconnaissant une somme de puissances de $2$ consécutives. Ainsi $P (n + 1)$ est vraie.

Conclusion. Par récurrence forte, $u_{n} = 2^{n - 2}$ pour tout $n \geq 2$ .

Une récurrence simple aurait échoué ici : la définition de $u_{n + 1}$ fait intervenir tous les termes précédents, pas seulement le dernier.

Récurrence descendante

Deux situations différentes portent ce nom, et il vaut mieux les distinguer.

Propriété

Ce n'est pas un nouvel axiome : il suffit d'appliquer le principe de récurrence ordinaire au prédicat $Q (j) = P (N - j)$ , pour $j$ allant de $0$ à $N$ .

Méthode

Squelette. Notons $P (k)$ l'assertion « … », pour $0 \leq k \leq N$ .

Initialisation, au rang le plus haut. $P (N)$ est vraie car … .

Hérédité descendante. Soit $k \in {0, \dots, N - 1}$ tel que $P (k + 1)$ soit vraie. Montrons $P (k)$ . …

Conclusion. Par récurrence descendante, $P (k)$ est vraie pour tout $k$ de ${0, \dots, N}$ .

Exemple

Notons $P (k)$ l'assertion « $f (k) \leq N - k$ ».

Initialisation. $f (N) = 0 = N - N$ , donc $P (N)$ est vraie.

Conclusion. Par récurrence descendante, $f (k) \leq N - k$ pour tout $k$ de ${0, \dots, N}$ .

Remarque

Le schéma de Cauchy.

Ensembles

Appartenance et inclusion

Définition

Soit $E$ un ensemble. On note $x \in E$ pour dire que $x$ est un élément de $E$ , et $x \notin E$ pour la négation.

$A$ est une partie de $E$ , ou est inclus dans $E$ , ce qu'on note $A \subset E$ , lorsque tout élément de $A$ est élément de $E$ : $\forall x, (x \in A \Rightarrow x \in E)$ .

Remarque

Prenons $E = {1, {1}}$ , qui a deux éléments : le nombre $1$ , et l'ensemble ${1}$ . Alors :

a. $1 \in E$ : vrai, c'est le premier élément.

b. ${1} \in E$ : vrai, c'est le second élément.

c. ${1} \subset E$ : vrai, car $1 \in E$ .

d. $1 \subset E$ : dépourvu de sens, $1$ n'est pas un ensemble.

Propriété

Pour tout ensemble $E$ : $\emptyset \subset E$ et $E \subset E$ . De plus, l'inclusion est transitive : si $A \subset B$ et $B \subset C$ , alors $A \subset C$ .

Égalité par double inclusion

Propriété

Soient $A$ et $B$ deux ensembles. Alors $A = B$ si et seulement si $A \subset B$ et $B \subset A$ .

C'est la traduction directe du fait qu'un ensemble est déterminé par ses éléments : $A = B$ signifie $\forall x, (x \in A ⟺ x \in B)$ , et une équivalence, c'est deux implications.

Méthode

Démontrer une égalité d'ensembles. Deux rédactions sont admises, et une seule est sans risque.

Réunion, intersection, complémentaire, différence

Définition

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

La réunion : $A \cup B = {x \in E; x \in A ou x \in B}$ .
L'intersection : $A \cap B = {x \in E; x \in A et x \in B}$ . Si $A \cap B = \emptyset$ , les parties sont dites disjointes.
Le complémentaire de $A$ dans $E$ : $\overline{A} = {x \in E; x \notin A}$ .
La différence : $A ∖ B = {x \in A; x \notin B}$ .

Propriété

Soient $A$ , $B$ , $C$ des parties de $E$ . Les opérations $\cup$ et $\cap$ sont commutatives, associatives et idempotentes ; chacune est distributive sur l'autre :

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

De plus $\overline{\overline{A}} = A$ , $A \cup \overline{A} = E$ et $A \cap \overline{A} = \emptyset$ .

Propriété

Lois de De Morgan ensemblistes. Pour toutes parties $A$ et $B$ d'un ensemble $E$ :

\overline{A \cup B} = \overline{A} \cap \overline{B}, \overline{A \cap B} = \overline{A} \cup \overline{B} .

Démonstration. Établissons la première par double inclusion, en rédigeant complètement.

Ensemble des parties

Définition

Soit $E$ un ensemble. L'ensemble des parties de $E$ , noté $P (E)$ , est l'ensemble dont les éléments sont exactement les parties de $E$ :

A \in P (E) ⟺ A \subset E .

Exemple

Pour $E = {a, b}$ , on a $P (E) = {\emptyset, {a}, {b}, {a, b}}$ : quatre éléments.

Propriété

Si $E$ est un ensemble fini à $n$ éléments, alors $P (E)$ est fini et $c a r d P (E) = 2^{n}$ .

Produit cartésien

Définition

(x, y) = (x^{'}, y^{'}) ⟺ (x = x^{'} et y = y^{'}) .

On note $E^{2} = E \times E$ , et plus généralement $E^{n}$ l'ensemble des $n$ -uplets d'éléments de $E$ .

Familles indexées, réunions et intersections quelconques, partitions

Définition

⋃_{i \in I} A_{i} = {x \in E; \exists i \in I, x \in A_{i}}, ⋂_{i \in I} A_{i} = {x \in E; \forall i \in I, x \in A_{i}} .

Propriété

Lois de De Morgan pour une famille. Pour toute famille $(A_{i})_{i \in I}$ de parties de $E$ avec $I \neq \emptyset$ :

\overline{⋃_{i \in I} A_{i}} = ⋂_{i \in I} \overline{A_{i}}, \overline{⋂_{i \in I} A_{i}} = ⋃_{i \in I} \overline{A_{i}} .

Définition

Une partition d'un ensemble $E$ est une famille $(A_{i})_{i \in I}$ de parties de $E$ telle que :

chaque $A_{i}$ est non vide ;
les $A_{i}$ sont deux à deux disjoints : pour tous $i \neq j$ dans $I$ , $A_{i} \cap A_{j} = \emptyset$ ;
leur réunion est $E$ tout entier : $⋃_{i \in I} A_{i} = E$ .

Ensembles finis, cardinal, crible, principe des tiroirs

Définition

Propriété

Soient $A$ et $B$ des parties d'un ensemble fini.

Si $A \subset B$ , alors $c a r d (A) \leq c a r d (B)$ , avec égalité si et seulement si $A = B$ .
Si $A$ et $B$ sont disjoints, $c a r d (A \cup B) = c a r d (A) + c a r d (B)$ .
Formule du crible à deux ensembles : $c a r d (A \cup B) = c a r d (A) + c a r d (B) - c a r d (A \cap B)$ .
$c a r d (\overline{A}) = c a r d (E) - c a r d (A)$ , où le complémentaire est pris dans un ensemble fini $E$ .

Propriété

Principe des tiroirs. Pour tout entier $n \geq 1$ , il n'existe aucune application injective de ${1, \dots, n + 1}$ dans ${1, \dots, n}$ .

Autrement dit : si l'on range $n + 1$ objets dans $n$ tiroirs, au moins un tiroir contient au moins deux objets.

Applications

Définition, et ce que « bien définie » veut dire

Définition

L'ensemble $E$ est l'ensemble de départ, $F$ l'ensemble d'arrivée. Si $y = f (x)$ , on dit que $x$ est un antécédent de $y$ .

Méthode

Vérifier qu'une formule définit bien une application. La définition contient deux exigences, et il faut les contrôler séparément.

Existence : pour tout $x$ de $E$ , la formule produit-elle effectivement un résultat, et ce résultat est-il dans $F$ ?
Unicité : le résultat est-il déterminé sans ambiguïté par $x$ ? La question se pose dès que $x$ peut s'écrire de plusieurs façons, ou que la formule contient un choix.

Exemple

Composition, restriction, prolongement

Définition

Soient $f : E \to F$ et $g : F \to G$ . La composée $g \circ f$ est l'application de $E$ dans $G$ définie par $(g \circ f) (x) = g (f (x))$ pour tout $x \in E$ .

L'identité de $E$ est l'application ${i d}_{E} : E \to E$ , $x \mapsto x$ .

Propriété

Définition

Soit $f : E \to F$ et $A \subset E$ . La restriction de $f$ à $A$ , notée $f ∣_{A}$ , est l'application de $A$ dans $F$ qui à $x \in A$ associe $f (x)$ .

Réciproquement, si $A \subset E$ et $g : A \to F$ , une application $f : E \to F$ telle que $f ∣_{A} = g$ s'appelle un prolongement de $g$ à $E$ .

Image directe et image réciproque

Définition

Soit $f : E \to F$ , $A \subset E$ et $B \subset F$ .

L'image directe de $A$ est $f (A) = {y \in F; \exists x \in A, y = f (x)}$ . C'est une partie de $F$ .
L'image réciproque de $B$ est $f^{- 1} (B) = {x \in E; f (x) \in B}$ . C'est une partie de $E$ .

On note $I m (f) = f (E)$ l'image de $f$ .

Les deux caractérisations à utiliser sans arrêt sont donc

y \in f (A) ⟺ \exists x \in A, y = f (x), x \in f^{- 1} (B) ⟺ f (x) \in B .

Remarque

Propriété

Soit $f : E \to F$ , $A$ , $A^{'}$ des parties de $E$ et $B$ , $B^{'}$ des parties de $F$ .

$f (A \cup A^{'}) = f (A) \cup f (A^{'})$ .
$f (A \cap A^{'}) \subset f (A) \cap f (A^{'})$ , et l'inclusion peut être stricte.
$f^{- 1} (B \cup B^{'}) = f^{- 1} (B) \cup f^{- 1} (B^{'})$ et $f^{- 1} (B \cap B^{'}) = f^{- 1} (B) \cap f^{- 1} (B^{'})$ .
$f^{- 1} (\overline{B}) = \overline{f^{- 1} (B)}$ .
$A \subset f^{- 1} (f (A))$ et $f (f^{- 1} (B)) \subset B$ , les deux inclusions pouvant être strictes.

Injection, surjection, bijection

Définition

Soit $f : E \to F$ .

$f$ est injective lorsque $\forall x \in E, \forall x^{'} \in E, (f (x) = f (x^{'}) \Rightarrow x = x^{'})$ : deux éléments distincts ont des images distinctes.
$f$ est surjective lorsque $\forall y \in F, \exists x \in E, y = f (x)$ : tout élément de l'arrivée a au moins un antécédent.
$f$ est bijective lorsqu'elle est injective et surjective, c'est-à-dire lorsque tout élément de $F$ a exactement un antécédent : $\forall y \in F, \exists! x \in E, y = f (x)$ .

Méthode

Les phrases exactes à écrire. Ce sont elles qui sont attendues, et elles suffisent presque toujours à structurer la question.

Injectivité. Soient $x$ et $x^{'}$ dans $E$ tels que $f (x) = f (x^{'})$ . Montrons que $x = x^{'}$ . …

Non-injectivité. Prenons $x = \dots$ et $x^{'} = \dots$ . On a $x \neq x^{'}$ et pourtant $f (x) = f (x^{'}) = \dots$ , donc $f$ n'est pas injective. Il faut deux éléments explicites.

Surjectivité. Soit $y \in F$ . Cherchons un antécédent de $y$ par $f$ . Posons $x = \dots$ ; il appartient bien à $E$ car … , et $f (x) = \dots = y$ . Donc $f$ est surjective.

Non-surjectivité. Montrons que $y_{0} = \dots$ n'a pas d'antécédent. Supposons qu'il existe $x \in E$ tel que $f (x) = y_{0}$ ; alors … , ce qui est impossible.

Exemple

Propriété

Soient $f : E \to F$ et $g : F \to G$ .

Si $f$ et $g$ sont injectives, $g \circ f$ l'est ; si elles sont surjectives, $g \circ f$ l'est ; si elles sont bijectives, $g \circ f$ l'est.
Si $g \circ f$ est injective, alors $f$ est injective.
Si $g \circ f$ est surjective, alors $g$ est surjective.

Application réciproque

Propriété

Soit $f : E \to F$ . Les deux assertions suivantes sont équivalentes :

$f$ est bijective ;
il existe une application $g : F \to E$ telle que $g \circ f = {i d}_{E}$ et $f \circ g = {i d}_{F}$ .

Dans ce cas, une telle $g$ est unique : on l'appelle l'application réciproque de $f$ et on la note $f^{- 1}$ .

Unicité. Soient $g$ et $h$ deux applications vérifiant la condition 2. Alors, en utilisant l'associativité,

g = g \circ {i d}_{F} = g \circ (f \circ h) = (g \circ f) \circ h = {i d}_{E} \circ h = h .

D'où l'unicité. $□$

Propriété

Si $f : E \to F$ et $g : F \to G$ sont bijectives, alors $f^{- 1}$ est bijective de réciproque $f$ , et $g \circ f$ est bijective avec $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ .

Le cas des ensembles finis

Propriété

Soient $E$ et $F$ deux ensembles finis de même cardinal, et $f : E \to F$ . Les trois assertions suivantes sont équivalentes : $f$ est injective ; $f$ est surjective ; $f$ est bijective.

Remarque

Relations binaires

Relation binaire et ses quatre propriétés

Définition

Une relation $R$ sur $E$ est dite :

réflexive si $\forall x \in E, x R x$ ;
symétrique si $\forall x \in E, \forall y \in E, (x R y \Rightarrow y R x)$ ;
antisymétrique si $\forall x \in E, \forall y \in E, ((x R y et y R x) \Rightarrow x = y)$ ;
transitive si $\forall x, y, z \in E, ((x R y et y R z) \Rightarrow x R z)$ .

Remarque

Relations d'équivalence, classes et partition

Définition

Une relation d'équivalence sur $E$ est une relation binaire réflexive, symétrique et transitive. Pour $x \in E$ , la classe d'équivalence de $x$ est la partie

c l (x) = {y \in E; y R x} .

Tout élément de $c l (x)$ est appelé un représentant de cette classe.

Remarque

Propriété

Soit $R$ une relation d'équivalence sur $E$ , et soient $x, y \in E$ .

$x \in c l (x)$ ; en particulier $c l (x)$ n'est jamais vide.
$x R y ⟺ c l (x) = c l (y)$ .
Si $c l (x) \cap c l (y) \neq \emptyset$ , alors $c l (x) = c l (y)$ : deux classes sont égales ou disjointes.

Démonstration. Le point 1 est exactement la réflexivité.

Point 2, sens réciproque. Supposons $c l (x) = c l (y)$ . Par le point 1, $x \in c l (x)$ , donc $x \in c l (y)$ , c'est-à-dire $x R y$ .

Propriété

Les classes d'équivalence forment une partition. Soit $R$ une relation d'équivalence sur un ensemble $E$ non vide. L'ensemble des classes d'équivalence est une partition de $E$ .

Réciproquement, toute partition de $E$ provient d'une unique relation d'équivalence : celle qui met en relation deux éléments lorsqu'ils appartiennent au même morceau.

Démonstration. Vérifions les trois points de la définition d'une partition.

Les classes sont non vides : c'est le point 1 de la propriété précédente.

Elles sont deux à deux disjointes : si deux classes ne sont pas disjointes, le point 3 affirme qu'elles sont égales. Deux classes distinctes sont donc bien d'intersection vide.

Exemple

Ensemble quotient et surjection canonique

Définition

Soit $R$ une relation d'équivalence sur $E$ . L'ensemble quotient de $E$ par $R$ , noté $E / R$ , est l'ensemble des classes d'équivalence. La surjection canonique est l'application

π : E \to E / R, x \mapsto c l (x) .

Remarque

Relations d'ordre

Définition

Une relation d'ordre sur $E$ est une relation binaire réflexive, antisymétrique et transitive. On la note souvent $⪯$ , et le couple $(E, ⪯)$ s'appelle un ensemble ordonné.

L'ordre est total si deux éléments quelconques sont toujours comparables : $\forall x, y \in E, (x ⪯ y ou y ⪯ x)$ . Sinon il est partiel.

Exemple

Définition

Soit $(E, ⪯)$ un ensemble ordonné et $A$ une partie de $E$ .

$M \in E$ est un majorant de $A$ si $\forall a \in A, a ⪯ M$ . On définit de même un minorant.
$M$ est le plus grand élément de $A$ si $M$ est un majorant de $A$ et $M \in A$ . De même pour le plus petit élément.
La borne supérieure de $A$ , notée $\sup A$ , est le plus petit élément de l'ensemble des majorants de $A$ , lorsqu'il existe. La borne inférieure $\inf A$ est le plus grand des minorants.

Propriété

Le plus grand élément d'une partie, la borne supérieure d'une partie, sont uniques lorsqu'ils existent.

C'est ici que l'antisymétrie sert : sans elle, ces objets ne seraient pas uniques et on ne pourrait pas parler « du » plus grand élément.

Remarque

Propriété

Dans $(P (E), \subset)$ , toute famille $(A_{i})_{i \in I}$ de parties admet une borne supérieure et une borne inférieure, à savoir sa réunion et son intersection.

Remarque

Sur un produit $E \times F$ d'ensembles ordonnés, l'ordre produit est défini par

(x, y) ⪯ (x^{'}, y^{'}) ⟺ (x \leq x^{'} et y \leq y^{'}) .

C'est un ordre, et il n'est pas total dès que $E$ et $F$ ont chacun deux éléments comparables distincts : dans $R^{2}$ , les couples $(0, 1)$ et $(1, 0)$ ne sont pas comparables.

L'ordre lexicographique, celui du dictionnaire, est défini par

(x, y) ⪯_{lex} (x^{'}, y^{'}) ⟺ (x < x^{'}) ou (x = x^{'} et y \leq y^{'}) .

Dénombrabilité

Remarque

Définition

Un ensemble $E$ est dénombrable s'il existe une bijection de $N$ sur $E$ . Il est dit au plus dénombrable s'il est fini ou dénombrable.

Propriété

Théorème de Cantor. Pour tout ensemble $E$ , il n'existe aucune application surjective de $E$ sur $P (E)$ .

En particulier, l'ensemble des suites à valeurs dans ${0, 1}$ n'est pas dénombrable, et $R$ non plus.

Le cours en PDF(PDF, 214 Ko)

Bloqué sur « Logique, raisonnement, ensembles et applications » ?

On peut le travailler ensemble dès cette semaine. La première heure est offerte — on fait le point honnêtement, et vous repartez au minimum avec une méthode.

Réserver ma 1ʳᵉ heure offerte