MPSI · Chapitre 01 · Premier semestre

Raisonnement et vocabulaire ensembliste

Quantificateurs, modes de raisonnement, récurrence, ensembles et parties, applications, injections et bijections, relations d'équivalence et d'ordre.

Sommaire

Ce qu'il faut savoir faire

Ce chapitre ouvre l'année, et ce n'est pas un hasard : il ne contient presque aucun résultat spectaculaire, mais il fixe la langue dans laquelle tous les autres chapitres seront écrits. Au lycée, on calcule ; en classe préparatoire, on démontre, et démontrer suppose de savoir exactement ce que l'on affirme, ce que l'on suppose, et ce qu'il reste à établir. Nous allons donc préciser le sens des mots « ou », « si ... alors », « pour tout », « il existe », recenser les grandes manières de conduire une démonstration, puis mettre en place le vocabulaire des ensembles, des applications et des relations, qui servira absolument partout par la suite.

Les notations suivantes sont fixées une fois pour toutes et ne changeront plus : $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 ; $A Δ B$ la différence symétrique ; $1_{A}$ la fonction indicatrice de $A$ ; $f : E \to F$ une application ; ${i d}_{E}$ l'identité de $E$ ; $R$ une relation binaire, que l'on note $x R y$ . La classe d'équivalence d'un élément $x$ sera notée $C l (x)$ , et jamais autrement : la barre supérieure est réservée au complémentaire, nous ne l'emploierons pas pour une classe.

Rudiments de logique

Assertions et connecteurs

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 (notée $V$ ) ou fausse (notée $F$ ). Une assertion ne peut pas être à la fois vraie et fausse.

a. « $2 + 2 = 4$ » : vraie.

b. « $3 ∣ 12$ » : vraie.

c. « $\sqrt{2} \in Q$ » : fausse.

d. « $π > 4$ » : fausse.

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

f. « $N \subset R$ » : vraie.

Remarque

L'énoncé « $x > 0$ » n'est pas une assertion tant que $x$ n'est pas fixé : sa valeur de vérité dépend de $x$ . Un tel énoncé, dont la vérité dépend d'une ou plusieurs variables, s'appelle un prédicat et se note $P (x)$ . Il devient une assertion dès que l'on fixe $x$ , ou dès que l'on quantifie la variable (section « Quantificateurs »).

À partir d'assertions données, on en fabrique de nouvelles à l'aide de 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$ et $Q$ » est vraie lorsque $P$ et $Q$ sont toutes les deux vraies, et fausse sinon.
La disjonction « $P$ ou $Q$ » est vraie lorsque l'une au moins des deux assertions est vraie, et fausse lorsque les deux sont fausses.

Ces définitions se résument dans une table de vérité, qui énumère tous les cas possibles :

\begin{array}{ccccc} P & Q & \neg P & P et Q & P ou Q \\ V & V & F & V & V \\ V & F & F & F & V \\ F & V & V & F & V \\ F & F & V & F & F \end{array}

Remarque

Le « ou » mathématique est inclusif : « $P$ ou $Q$ » n'exclut pas que $P$ et $Q$ soient vraies simultanément. C'est une différence avec le langage courant, où « fromage ou dessert » signifie en général « l'un des deux, pas les deux ». Ainsi, l'assertion « $2$ est pair ou $2$ est premier » est vraie.

Propriété

Soient $P$ , $Q$ , $R$ trois assertions. Les assertions suivantes ont, deux à deux, la même valeur de vérité.

Double négation : $\neg (\neg P)$ et $P$ .
Négation d'une conjonction : $\neg (P et Q)$ et « $\neg P$ ou $\neg Q$ ».
Négation d'une disjonction : $\neg (P ou Q)$ et « $\neg P$ et $\neg Q$ ».
Distributivité : « $P$ et $(Q$ ou $R)$ » et « $(P$ et $Q)$ ou $(P$ et $R)$ ».

Démonstration. Il suffit de comparer les colonnes d'une table de vérité. Traitons la négation d'une conjonction :

\begin{array}{ccccccc} P & Q & P et Q & \neg (P et Q) & \neg P & \neg Q & \neg P ou \neg Q \\ V & V & V & F & F & F & F \\ V & F & F & V & F & V & V \\ F & V & F & V & V & F & V \\ F & F & F & V & V & V & V \end{array}

La quatrième et la septième colonne coïncident ligne à ligne : les deux assertions ont bien toujours la même valeur de vérité. Les trois autres points se vérifient exactement de la même façon, en écrivant la table correspondante. $□$

Ces règles ne sont pas là pour être étudiées pour elles-mêmes : ce sont des outils, dont nous nous servirons constamment pour nier une hypothèse ou pour raisonner par l'absurde.

Implication, réciproque, contraposée

Définition

Soient $P$ et $Q$ deux assertions. L'assertion « $P ⟹ Q$ », lue « $P$ implique $Q$ » ou « si $P$ alors $Q$ », est par définition l'assertion « $\neg P$ ou $Q$ ». Elle est donc fausse dans le seul cas où $P$ est vraie et $Q$ est fausse, et vraie dans tous les autres cas.

On dit alors que $P$ est une condition suffisante pour $Q$ , et que $Q$ est une condition nécessaire pour $P$ .

\begin{array}{ccc} P & Q & P ⟹ Q \\ V & V & V \\ V & F & F \\ F & V & V \\ F & F & V \end{array}

Remarque

Une implication dont l'hypothèse est fausse est vraie, quelle que soit la conclusion : l'assertion « si $1 = 2$ , alors $3 = 4$ » est vraie. Cela surprend au début, mais c'est indispensable : sans cette convention, l'énoncé « pour tout réel $x$ , si $x > 2$ alors $x^{2} > 4$ » ne pourrait pas être vrai, puisqu'il concerne aussi les réels qui ne sont pas plus grands que $2$ . On parle d'implication vide lorsque l'hypothèse n'est jamais réalisée ; ce cas servira notamment pour montrer que $\emptyset \subset E$ .

Définition

Soit l'implication $P ⟹ Q$ .

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

Propriété

Soient $P$ et $Q$ deux assertions.

L'implication $P ⟹ Q$ et sa contraposée $\neg Q ⟹ \neg P$ ont toujours la même valeur de vérité.
La négation de $P ⟹ Q$ est l'assertion « $P$ et $\neg Q$ ».

Démonstration. Pour le premier point, on peut se passer de table de vérité en revenant à la définition : par définition, $P ⟹ Q$ est l'assertion « $\neg P$ ou $Q$ », tandis que $\neg Q ⟹ \neg P$ est l'assertion « $\neg (\neg Q)$ ou $\neg P$ », c'est-à-dire « $Q$ ou $\neg P$ » d'après la règle de double négation. Or la disjonction ne dépend pas de l'ordre de ses deux membres : les deux assertions coïncident.

Pour le second point, la négation de « $\neg P$ ou $Q$ » est, d'après la négation d'une disjonction, l'assertion « $\neg (\neg P)$ et $\neg Q$ », c'est-à-dire « $P$ et $\neg Q$ ». $□$

Remarque

Piège classique : contraposée et réciproque n'ont rien à voir. La contraposée d'une implication lui est équivalente : la démontrer, c'est démontrer l'implication de départ. La réciproque, elle, est une assertion nouvelle, qui peut parfaitement être fausse alors que l'implication de départ est vraie. Confondre les deux est l'une des fautes les plus fréquentes en début d'année.

Exemple

Considérons, pour $n \in Z$ , l'implication « si $n^{2}$ est pair, alors $n$ est pair ».

Sa réciproque est : « si $n$ est pair, alors $n^{2}$ est pair ». Elle est vraie, et facile : si $n = 2 k$ , alors $n^{2} = 2 (2 k^{2})$ .
Sa contraposée est : « si $n$ n'est pas pair, alors $n^{2}$ n'est pas pair », autrement dit « si $n$ est impair, alors $n^{2}$ est impair ». Elle est vraie elle aussi, et c'est justement par elle que nous démontrerons l'implication de départ (section « Raisonnement par contraposée »).
Sa négation est : « $n^{2}$ est pair et $n$ est impair ». Pour réfuter l'implication, il faudrait exhiber un tel $n$ : c'est impossible, car l'implication est vraie.

Équivalence

Définition

Soient $P$ et $Q$ deux assertions. 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. On dit alors que $P$ est une condition nécessaire et suffisante pour $Q$ .

Propriété

Pour toutes assertions $P$ et $Q$ , l'assertion $P ⟺ Q$ a la même valeur de vérité que l'assertion

(P ⟹ Q) et (Q ⟹ P) .

Démonstration. Si $P$ et $Q$ sont toutes deux vraies, les deux implications sont vraies, donc leur conjonction aussi, et l'équivalence est vraie : les deux assertions valent $V$ . Même conclusion si $P$ et $Q$ sont toutes deux fausses (les deux implications ont alors une hypothèse fausse, donc sont vraies). Si en revanche $P$ est vraie et $Q$ fausse, l'équivalence est fausse, et l'implication $P ⟹ Q$ est fausse, donc la conjonction aussi ; le cas symétrique se traite de même. Dans les quatre cas, les deux assertions ont la même valeur de vérité. $□$

C'est ce résultat qui justifie la méthode de démonstration par double implication (section « Démonstration d'une équivalence »).

Remarque

Attention aux chaînes d'équivalences. Dans la résolution d'une équation, écrire une suite de signes $⟺$ engage à ce que chaque étape soit réversible. Élever au carré, par exemple, ne l'est pas : l'égalité $a = b$ entraîne $a^{2} = b^{2}$ , mais la réciproque est fausse. Une chaîne d'équivalences mal contrôlée fabrique des solutions parasites.

Exemple

Résolvons dans $R$ l'équation $\sqrt{x + 2} = x$ . Comme une racine carrée est positive ou nulle, une solution est nécessairement positive ou nulle. Pour $x \in R$ :

\begin{aligned} \sqrt{x + 2} = x & ⟺ (x ⩾ 0 et x + 2 = x^{2}) \\ ⟺ (x ⩾ 0 et x^{2} - x - 2 = 0) \\ ⟺ (x ⩾ 0 et (x - 2) (x + 1) = 0) \\ ⟺ x = 2. \end{aligned}

La condition $x ⩾ 0$ , traînée à chaque ligne, est exactement ce qui rend l'élévation au carré réversible : sans elle, on aurait « trouvé » la solution parasite $x = - 1$ .

Quantificateurs

Un prédicat $P (x)$ n'est pas une assertion. Pour en faire une, on peut fixer $x$ , ou bien quantifier la variable.

Définition

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

Le quantificateur universel : l'assertion $\forall x \in E, P (x)$ , lue « pour tout $x$ de $E$ , $P (x)$ », est vraie lorsque $P (x)$ est vraie pour chacun des éléments $x$ de $E$ .
Le quantificateur existentiel : l'assertion $\exists x \in E, P (x)$ , lue « il existe un $x$ de $E$ tel que $P (x)$ », est vraie lorsqu'au moins un élément $x$ de $E$ rend $P (x)$ vraie.
Le quantificateur d'existence et d'unicité : l'assertion $\exists! x \in E, P (x)$ , lue « il existe un unique $x$ de $E$ tel que $P (x)$ », est vraie lorsqu'exactement un élément $x$ de $E$ rend $P (x)$ vraie.

Remarque

La variable quantifiée est muette : les assertions $\forall x \in R, x^{2} ⩾ 0$ et $\forall t \in R, t^{2} ⩾ 0$ sont la même assertion. En revanche, une lettre libre dans un énoncé doit avoir été introduite avant : écrire « $x^{2} ⩾ 0$ » sans avoir dit qui est $x$ n'a pas de sens.

Remarque

Les quantificateurs ne sont pas des abréviations. Dans un texte rédigé, on écrit « pour tout réel $x$ », « il existe un entier $n$ tel que », en toutes lettres. Les symboles $\forall$ et $\exists$ sont réservés à l'écriture formelle d'une proposition que l'on veut manipuler, typiquement pour la nier. Une copie où l'on lit « $\forall x$ solution, $x \in R_{+}$ donc $\exists$ une racine » est une copie mal rédigée : ces symboles ne remplacent ni un verbe, ni un connecteur, ni le mot « donc ».

Remarque

L'assertion $\exists! x \in E, P (x)$ se démontre toujours en deux temps, qui sont deux démonstrations distinctes : l'existence d'un élément convenable, puis l'unicité, c'est-à-dire le fait que deux éléments convenables sont nécessairement égaux (section « Démonstration d'une existence et d'une unicité »).

Ordre des quantificateurs

Remarque

L'ordre des quantificateurs change le sens de l'énoncé. Deux quantificateurs de même nature peuvent être échangés sans dommage : $\forall x \in E, \forall y \in E, P (x, y)$ et $\forall y \in E, \forall x \in E, P (x, y)$ disent la même chose, de même pour deux $\exists$ consécutifs. Mais on ne peut jamais échanger un $\forall$ et un $\exists$ .

Exemple

Comparons deux énoncés qui ne diffèrent que par l'ordre des quantificateurs.

\forall x \in R, \exists y \in R, x + y = 0.

Cet énoncé est vrai : $x$ étant donné, il suffit de prendre $y = - x$ , qui dépend de $x$ , ce qui est parfaitement licite puisque $y$ est choisi après $x$ .

\exists y \in R, \forall x \in R, x + y = 0.

Cet énoncé est faux : il réclame un unique $y$ , choisi avant $x$ et donc valable pour tous les $x$ à la fois. Un tel $y$ devrait vérifier $0 + y = 0$ et $1 + y = 0$ , donc $y = 0$ et $y = - 1$ , ce qui est impossible.

La règle à retenir : dans un énoncé, chaque objet ne peut dépendre que de ceux qui ont été introduits avant lui.

Négation d'une proposition quantifiée

Propriété

Soit $P (x)$ un prédicat sur un ensemble $E$ . Alors :

\neg (\forall x \in E, P (x)) a la m \hat{e} me valeur de v \overset{ˊ}{e} rit \overset{ˊ}{e} que \exists x \in E, \neg P (x),

\neg (\exists x \in E, P (x)) a la m \hat{e} me valeur de v \overset{ˊ}{e} rit \overset{ˊ}{e} que \forall x \in E, \neg P (x) .

Démonstration. Dire que « $\forall x \in E, P (x)$ » est fausse, c'est dire qu'il n'est pas vrai que tous les éléments de $E$ vérifient $P$ , c'est-à-dire qu'au moins l'un d'eux ne la vérifie pas : c'est exactement l'assertion $\exists x \in E, \neg P (x)$ . Réciproquement, si un élément $x_{0}$ de $E$ vérifie $\neg P (x_{0})$ , alors l'assertion « $\forall x \in E, P (x)$ » est fausse, puisque $x_{0}$ la met en défaut. Les deux assertions sont donc simultanément vraies ou simultanément fausses.

La seconde règle s'obtient en appliquant la première à $\neg P$ , puis en utilisant la double négation : la négation de « $\exists x \in E, P (x)$ » est vraie exactement lorsqu'aucun élément de $E$ ne vérifie $P$ , c'est-à-dire lorsque tous vérifient $\neg P$ . $□$

Méthode

Nier une proposition quantifiée. On procède mécaniquement, de la gauche vers la droite, sans jamais changer l'ordre des quantificateurs :

remplacer chaque $\forall$ par un $\exists$ et chaque $\exists$ par un $\forall$ , en gardant leur ordre et leurs ensembles ;
nier la propriété finale, celle qui ne contient plus de quantificateur ;
dans cette dernière étape, appliquer les règles usuelles : la négation de « et » est « ou », celle de « ou » est « et », celle de « $P ⟹ Q$ » est « $P$ et $\neg Q$ », celle de $⩽$ est $>$ , celle de $=$ est $\neq$ ;
relire la proposition obtenue en français, pour vérifier qu'elle a un sens.

L'erreur à ne pas commettre est de nier « $\forall x \in E$ » en « $\forall x \notin E$ » : l'ensemble sur lequel on quantifie n'est jamais modifié.

Exemple

Nions quelques propositions courantes.

a. « Tout réel est positif ou nul », soit $\forall x \in R, x ⩾ 0$ . Négation : $\exists x \in R, x < 0$ . La négation est vraie (prendre $x = - 1$ ), donc la proposition de départ est fausse.

b. Soit $f : R \to R$ . La proposition « $f$ est majorée » s'écrit $\exists M \in R, \forall x \in R, f (x) ⩽ M$ . Sa négation est

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

En français : quelle que soit la hauteur $M$ que l'on se fixe, la fonction finit par la dépasser en un point.

c. Soit $f : R \to R$ . La proposition « $f$ s'annule » s'écrit $\exists x \in R, f (x) = 0$ , et sa négation est $\forall x \in R, f (x) \neq 0$ .

d. Soient $(u_{n})$ une suite réelle et $ℓ$ un réel. La proposition « $(u_{n})$ converge vers $ℓ$ » s'écrit

\forall ε > 0, \exists N \in N, \forall n \in N, (n ⩾ N ⟹ ∣ u_{n} - ℓ ∣ ⩽ ε) .

Nous n'utiliserons pas cette proposition ici, et nous ne démontrerons rien à son sujet : elle sert uniquement de matériau logique, car c'est l'énoncé quantifié le plus riche que vous rencontrerez cette année. Sa négation, obtenue mécaniquement par la méthode ci-dessus, est

\exists ε > 0, \forall N \in N, \exists n \in N, (n ⩾ N et ∣ u_{n} - ℓ ∣ > ε) .

Remarquez le traitement de l'implication finale : sa négation est bien une conjonction, et non une implication.

Modes de raisonnement

Savoir ce qu'est une implication ne dit pas encore comment la démontrer. Cette section recense les stratégies disponibles ; le choix de la bonne stratégie est souvent la moitié du travail.

Raisonnement direct

Méthode

Raisonnement direct. Pour démontrer $P ⟹ Q$ , on suppose $P$ vraie, et on en déduit $Q$ par une suite de déductions. Rédaction type : « Supposons $P$ . Alors ... Donc $Q$ . »

Pour démontrer une proposition universelle $\forall x \in E, P (x)$ , on commence par « Soit $x \in E$ », on démontre $P (x)$ sans jamais rien supposer de particulier sur $x$ , et on conclut. Le mot « Soit » signifie précisément : je prends un élément quelconque, fixé mais arbitraire.

Pour démontrer une proposition existentielle $\exists x \in E, P (x)$ , il suffit d'exhiber un élément convenable, et de vérifier qu'il convient. On n'est jamais tenu d'expliquer comment on l'a trouvé.

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} ⩾ 0$ comme carré d'un réel, donc $(x - 1)^{2} + 2 ⩾ 2 > 0$ . Ainsi $x^{2} - 2 x + 3 > 0$ . Comme $x$ était quelconque, la propriété vaut pour tout réel.

Raisonnement par contraposée

Méthode

Raisonnement par contraposée. Pour démontrer $P ⟹ Q$ , on démontre $\neg Q ⟹ \neg P$ , ce qui revient au même (propriété de la section « Implication, réciproque, contraposée »). On y pense lorsque l'hypothèse $\neg Q$ est plus maniable que l'hypothèse $P$ , typiquement lorsque $P$ ou $Q$ contient une négation, un « ne divise pas », un « n'est pas nul ».

Rédaction type : « Montrons la contraposée : supposons $\neg Q$ ... donc $\neg P$ . Par contraposition, on a bien $P ⟹ Q$ . »

Exemple

Montrons que pour tout $n \in Z$ , si $n^{2}$ est pair, alors $n$ est pair.

L'hypothèse « $n^{2}$ est pair » donne $n^{2} = 2 k$ , ce qui ne renseigne guère sur $n$ . Démontrons plutôt la contraposée : si $n$ est impair, alors $n^{2}$ est impair. Supposons donc $n$ impair : il existe $k \in Z$ tel que $n = 2 k + 1$ . Alors

n^{2} = (2 k + 1)^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1,

et $2 k^{2} + 2 k$ est un entier, donc $n^{2}$ est impair. La contraposée est établie, donc l'implication de départ également.

Raisonnement par l'absurde

Méthode

Raisonnement par l'absurde. Pour démontrer une assertion $P$ , on suppose $\neg P$ et l'on aboutit à une contradiction (une assertion à la fois vraie et fausse). On en conclut que $\neg P$ est fausse, donc que $P$ est vraie.

Rédaction type : « Supposons par l'absurde que ... Alors ... , ce qui est absurde. Donc ... »

Attention à ne pas confondre avec la contraposée : par l'absurde, pour démontrer $P ⟹ Q$ , on suppose à la fois $P$ et $\neg Q$ , et on cherche une contradiction. On dispose donc de deux hypothèses au lieu d'une.

Exemple

Montrons que $\sqrt{2}$ n'est pas un nombre rationnel.

Supposons par l'absurde que $\sqrt{2} \in Q$ . On peut alors écrire $\sqrt{2} = \frac{p}{q}$ , où $p$ et $q$ sont des entiers, $q$ non nul, et où la fraction est irréductible (on a simplifié au maximum, donc $p$ et $q$ ne sont pas tous les deux pairs). En élevant au carré, $2 = \frac{p^{2}}{q^{2}}$ , c'est-à-dire

p^{2} = 2 q^{2} .

Ainsi $p^{2}$ est pair, donc $p$ est pair d'après l'exemple de la section « Raisonnement par contraposée » : écrivons $p = 2 p^{'}$ avec $p^{'}$ entier. Alors $4 p^{' 2} = 2 q^{2}$ , donc $q^{2} = 2 p^{' 2}$ , donc $q^{2}$ est pair, donc $q$ est pair pour la même raison. Les entiers $p$ et $q$ sont donc tous les deux pairs, ce qui contredit l'irréductibilité de la fraction. L'hypothèse de départ est absurde : $\sqrt{2} \notin Q$ .

Remarque

Le raisonnement par l'absurde est puissant, mais il est souvent employé à tort. Si votre contradiction finale est « ... ce qui contredit l'hypothèse $\neg Q$ », c'est que vous avez en réalité démontré $P ⟹ Q$ directement, et le détour par l'absurde n'ajoute que du bruit. Réservez-le aux cas où l'hypothèse supplémentaire $\neg Q$ est réellement utilisée.

Raisonnement par disjonction de cas

Méthode

Disjonction de cas. Pour démontrer une assertion, on partage la situation en un nombre fini de cas qui couvrent toutes les possibilités, et on démontre l'assertion dans chacun d'eux. Il faut impérativement vérifier que la liste des cas est exhaustive ; qu'ils se recouvrent partiellement n'est en revanche pas gênant.

Exemple

Montrons que pour tout $n \in Z$ , l'entier $n^{2} + n$ est pair.

Soit $n \in Z$ . Tout entier est pair ou impair : ces deux cas couvrent bien toutes les possibilités.

Cas 1 : $n$ est pair. Écrivons $n = 2 k$ avec $k \in Z$ . Alors $n^{2} + n = 4 k^{2} + 2 k = 2 (2 k^{2} + k)$ , qui est pair.

Cas 2 : $n$ est impair. Écrivons $n = 2 k + 1$ avec $k \in Z$ . Alors

n^{2} + n = (2 k + 1)^{2} + (2 k + 1) = 4 k^{2} + 4 k + 1 + 2 k + 1 = 2 (2 k^{2} + 3 k + 1),

qui est pair.

Dans les deux cas, $n^{2} + n$ est pair.

Raisonnement par contre-exemple

Méthode

Contre-exemple. Pour démontrer qu'une assertion universelle $\forall x \in E, P (x)$ est fausse, il suffit, d'après la règle de négation, d'exhiber un seul élément $x_{0}$ de $E$ tel que $P (x_{0})$ soit fausse. Un contre-exemple ne se discute pas : il se vérifie. Inversement, aucun nombre d'exemples, si grand soit-il, ne démontre une assertion universelle.

Exemple

L'assertion « pour tout $n \in N$ , l'entier $n^{2} + n + 41$ est un nombre premier » est fausse. Elle est pourtant vraie pour $n = 0$ , $n = 1$ , ..., et en fait pour tous les entiers jusqu'à $39$ , ce qui est très encourageant. Mais pour $n = 40$ :

40^{2} + 40 + 41 = 41 \times 41,

qui n'est pas premier. Un seul contre-exemple suffit à ruiner l'énoncé, quel que soit le nombre de cas favorables observés auparavant.

Démonstration d'une équivalence

Méthode

Démontrer une équivalence. Deux stratégies.

Par double implication : on démontre $P ⟹ Q$ , puis $Q ⟹ P$ . On annonce clairement les deux sens, par exemple par les symboles $⟹$ et $⟸$ ou par les mots « sens direct » et « réciproque ». C'est la méthode par défaut, la plus sûre.
Par équivalences successives : on enchaîne des assertions reliées par $⟺$ . Cette rédaction est élégante, mais elle exige que chaque étape soit réversible ; au moindre doute, revenir à la double implication.

Exemple

Soient $x$ et $y$ deux réels. Montrons que $x^{2} + y^{2} = 0 ⟺ (x = 0$ et $y = 0)$ .

$(⟸)$ Si $x = 0$ et $y = 0$ , alors $x^{2} + y^{2} = 0$ .

$(⟹)$ Supposons $x^{2} + y^{2} = 0$ . Comme $x^{2} ⩾ 0$ et $y^{2} ⩾ 0$ , on a $x^{2} = - y^{2} ⩽ 0$ , donc $x^{2} = 0$ , donc $x = 0$ ; il vient alors $y^{2} = 0$ , donc $y = 0$ .

Démonstration d'une existence et d'une unicité

Méthode

Existence et unicité. L'assertion $\exists! x \in E, P (x)$ se démontre en deux temps indépendants.

Existence : exhiber un élément $x_{0}$ de $E$ vérifiant $P (x_{0})$ , ou en démontrer l'existence par un argument théorique.
Unicité : se donner $x$ et $x^{'}$ dans $E$ vérifiant tous deux $P$ , et démontrer que $x = x^{'}$ . C'est la rédaction correcte ; il ne suffit pas de dire « il n'y en a qu'un » ni de raisonner sur celui que l'on a trouvé.

Les deux temps peuvent être menés dans l'ordre que l'on veut, et l'unicité se démontre parfois plus facilement que l'existence.

Raisonnement par analyse-synthèse

Méthode

Analyse-synthèse. C'est la méthode reine lorsque l'on cherche tous les objets vérifiant une condition, sans en connaître aucun a priori. Elle se déroule en deux phases, qui doivent être annoncées et séparées.

Analyse : on suppose qu'un objet $x$ convient, et on en tire des conditions nécessaires, jusqu'à déterminer complètement $x$ (ou une courte liste de candidats). Cette phase ne démontre rien d'autre que : « s'il y a une solution, elle est forcément celle-là ». Elle règle donc l'unicité.
Synthèse : on prend le candidat obtenu et on vérifie qu'il convient réellement. Cette phase règle l'existence. Elle n'est jamais facultative : l'analyse ne produit que des conditions nécessaires.

Rédaction type : « Analyse. Supposons que $x$ convienne. Alors ... donc nécessairement $x = \dots$ Synthèse. Réciproquement, posons $x = \dots$ ; vérifions qu'il convient : ... Conclusion. Il existe une unique solution, à savoir ... »

Exemple

Montrons que toute application $f : R \to R$ s'écrit de manière unique comme somme d'une application paire et d'une application impaire.

Analyse. Supposons que $f = p + i$ , où $p$ est paire et $i$ impaire. Soit $x \in R$ . En évaluant en $x$ puis en $- x$ , et en utilisant $p (- x) = p (x)$ et $i (- x) = - i (x)$ :

\begin{aligned} f (x) & = p (x) + i (x), \\ f (- x) & = p (x) - i (x) . \end{aligned}

En additionnant puis en soustrayant ces deux égalités, on obtient nécessairement

p (x) = \frac{f (x) + f (- x)}{2} et i (x) = \frac{f (x) - f (- x)}{2} .

Le couple $(p, i)$ est donc entièrement déterminé par $f$ : s'il existe, il est unique.

Synthèse. Réciproquement, définissons $p$ et $i$ sur $R$ par les deux formules ci-dessus. Pour tout réel $x$ :

p (- x) = \frac{f (- x) + f (x)}{2} = p (x), i (- x) = \frac{f (- x) - f (x)}{2} = - i (x),

donc $p$ est paire et $i$ est impaire ; et $p (x) + i (x) = f (x)$ , donc $f = p + i$ . Le couple convient.

Conclusion. Il existe un unique couple $(p, i)$ formé d'une application paire et d'une application impaire tel que $f = p + i$ .

Raisonnement par récurrence

Le raisonnement par récurrence permet de démontrer une infinité d'assertions $P (0)$ , $P (1)$ , $P (2)$ , ... en un nombre fini de lignes. Il repose sur une propriété fondamentale de $N$ , que nous admettons.

Récurrence simple

Propriété

Principe de récurrence (admis). Soit $n_{0} \in N$ et soit, pour tout entier $n ⩾ n_{0}$ , une assertion $P (n)$ . On suppose que :

initialisation : $P (n_{0})$ est vraie ;
hérédité : pour tout entier $n ⩾ n_{0}$ , si $P (n)$ est vraie, alors $P (n + 1)$ est vraie.

Alors $P (n)$ est vraie pour tout entier $n ⩾ n_{0}$ .

Méthode

Rédiger une récurrence. La rédaction est très codifiée ; toute variante est perçue comme une maladresse.

Énoncer l'assertion : « Pour $n ⩾ n_{0}$ , notons $P (n)$ l'assertion : ... ». L'assertion $P (n)$ doit être une phrase mathématique complète, dépendant de $n$ , et surtout pas un simple nombre ni un calcul.
Initialisation : vérifier $P (n_{0})$ en calculant séparément les deux membres.
Hérédité : « Soit $n ⩾ n_{0}$ . Supposons $P (n)$ vraie. Montrons $P (n + 1)$ . » Écrire explicitement ce que l'on suppose (l'hypothèse de récurrence) et ce que l'on veut obtenir, puis faire apparaître l'hypothèse de récurrence dans le calcul, en la signalant.
Conclusion : « Par récurrence, $P (n)$ est vraie pour tout $n ⩾ n_{0}$ . »

Deux fautes à bannir : supposer « $P (n)$ vraie pour tout $n$ » dans l'hérédité (c'est ce que l'on veut démontrer), et oublier l'initialisation.

Exemple

Une récurrence rédigée en entier. Montrons que pour tout $n \in N$ ,

\sum_{k = 0}^{n} k = \frac{n (n + 1)}{2} .

Pour $n \in N$ , notons $P (n)$ l'assertion : « $\sum_{k = 0}^{n} k = \frac{n (n + 1)}{2}$ ».

Initialisation. Pour $n = 0$ , le membre de gauche vaut $\sum_{k = 0}^{0} k = 0$ , et le membre de droite vaut $\frac{0 \times 1}{2} = 0$ . Les deux membres coïncident, donc $P (0)$ est vraie.

Hérédité. Soit $n \in N$ . Supposons $P (n)$ vraie, c'est-à-dire $\sum_{k = 0}^{n} k = \frac{n (n + 1)}{2}$ . Montrons $P (n + 1)$ , c'est-à-dire $\sum_{k = 0}^{n + 1} k = \frac{(n + 1) (n + 2)}{2}$ . On isole le dernier terme de la somme :

\begin{aligned} \sum_{k = 0}^{n + 1} k & = (\sum_{k = 0}^{n} k) + (n + 1) \\ = \frac{n (n + 1)}{2} + (n + 1) par hypoth \overset{ˋ}{e} se de r \overset{ˊ}{e} currence \\ = (n + 1) (\frac{n}{2} + 1) \\ = (n + 1) \times \frac{n + 2}{2} = \frac{(n + 1) (n + 2)}{2} . \end{aligned}

Donc $P (n + 1)$ est vraie.

Conclusion. $P (0)$ est vraie et $P$ est héréditaire : par récurrence, pour tout $n \in N$ , $\sum_{k = 0}^{n} k = \frac{n (n + 1)}{2}$ . $□$

Remarque

L'initialisation n'est pas une formalité. Considérons l'assertion $P (n)$ : « $4^{n} + 1$ est divisible par $3$ ». Elle est héréditaire : si $3$ divise $4^{n} + 1$ , alors, comme

4^{n + 1} + 1 = 4 \times (4^{n} + 1) - 3,

l'entier $4^{n + 1} + 1$ est différence de deux multiples de $3$ , donc multiple de $3$ . Pourtant $P (n)$ est fausse pour tout $n$ : par exemple $4^{0} + 1 = 2$ et $4^{1} + 1 = 5$ ne sont pas divisibles par $3$ . Une propriété héréditaire mais jamais initialisée ne démarre jamais.

Récurrence double

Certaines suites sont définies par une relation faisant intervenir les deux termes précédents : l'hypothèse $P (n)$ seule ne suffit alors pas à obtenir $P (n + 1)$ .

Propriété

Récurrence double. Soit $n_{0} \in N$ et soit, pour tout entier $n ⩾ n_{0}$ , une assertion $P (n)$ . On suppose que :

$P (n_{0})$ et $P (n_{0} + 1)$ sont vraies ;
pour tout entier $n ⩾ n_{0}$ , si $P (n)$ et $P (n + 1)$ sont vraies, alors $P (n + 2)$ est vraie.

Alors $P (n)$ est vraie pour tout entier $n ⩾ n_{0}$ .

Exemple

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

Notons $P (n)$ l'assertion « $u_{n} = 2^{n}$ ».

Initialisation. $u_{0} = 1 = 2^{0}$ et $u_{1} = 2 = 2^{1}$ : $P (0)$ et $P (1)$ sont vraies.

Hérédité. Soit $n \in N$ . Supposons $P (n)$ et $P (n + 1)$ vraies, c'est-à-dire $u_{n} = 2^{n}$ et $u_{n + 1} = 2^{n + 1}$ . Alors

u_{n + 2} = 3 u_{n + 1} - 2 u_{n} = 3 \times 2^{n + 1} - 2 \times 2^{n} = 6 \times 2^{n} - 2 \times 2^{n} = 4 \times 2^{n} = 2^{n + 2},

donc $P (n + 2)$ est vraie.

Conclusion. Par récurrence double, $u_{n} = 2^{n}$ pour tout $n \in N$ . $□$

Remarquez que les deux initialisations sont indispensables : l'hérédité ne dit rien tant que l'on ne dispose pas de deux termes consécutifs.

Récurrence forte

Parfois, l'obtention de $P (n + 1)$ réclame non pas le rang précédent, ni les deux précédents, mais un rang antérieur que l'on ne maîtrise pas à l'avance.

Propriété

Récurrence forte. Soit $n_{0} \in N$ et soit, pour tout entier $n ⩾ n_{0}$ , une assertion $P (n)$ . On suppose que :

$P (n_{0})$ est vraie ;
pour tout entier $n ⩾ n_{0}$ , si $P (k)$ est vraie pour tout entier $k$ tel que $n_{0} ⩽ k ⩽ n$ , alors $P (n + 1)$ est vraie.

Alors $P (n)$ est vraie pour tout entier $n ⩾ n_{0}$ .

Exemple

Montrons que tout entier $n ⩾ 2$ admet au moins un diviseur premier.

Notons $P (n)$ l'assertion « $n$ admet au moins un diviseur premier », pour $n ⩾ 2$ .

Initialisation. $2$ est premier et se divise lui-même, donc $P (2)$ est vraie.

Hérédité. Soit $n ⩾ 2$ . Supposons $P (k)$ vraie pour tout entier $k$ tel que $2 ⩽ k ⩽ n$ , et montrons $P (n + 1)$ . Deux cas se présentent.

Cas 1 : $n + 1$ est premier. Alors $n + 1$ est un diviseur premier de lui-même, et $P (n + 1)$ est vraie.

Cas 2 : $n + 1$ n'est pas premier. Comme $n + 1 ⩾ 3$ , il admet un diviseur $d$ vérifiant $2 ⩽ d ⩽ n$ . L'hypothèse de récurrence forte s'applique à $d$ : il existe un nombre premier $p$ divisant $d$ . Or $d$ divise $n + 1$ , donc $p$ divise $n + 1$ par transitivité de la divisibilité, et $P (n + 1)$ est vraie.

Conclusion. Par récurrence forte, tout entier $n ⩾ 2$ admet un diviseur premier. $□$

Une récurrence simple aurait échoué ici : rien ne relie $n + 1$ à $n$ , alors que le diviseur $d$ qui apparaît est un entier quelconque entre $2$ et $n$ .

Récurrence finie

Propriété

Récurrence finie. Soient $n_{0}$ et $N$ deux entiers avec $n_{0} ⩽ N$ , et soit, pour tout entier $n$ tel que $n_{0} ⩽ n ⩽ N$ , une assertion $P (n)$ . On suppose que :

$P (n_{0})$ est vraie ;
pour tout entier $n$ tel que $n_{0} ⩽ n ⩽ N - 1$ , si $P (n)$ est vraie, alors $P (n + 1)$ est vraie.

Alors $P (n)$ est vraie pour tout entier $n$ compris entre $n_{0}$ et $N$ .

Exemple

Soient $a_{0}, a_{1}, \dots, a_{N}$ des réels tels que $a_{k} ⩽ a_{k + 1}$ pour tout $k$ tel que $0 ⩽ k ⩽ N - 1$ . Montrons que $a_{0} ⩽ a_{n}$ pour tout $n$ compris entre $0$ et $N$ .

Notons $P (n)$ l'assertion « $a_{0} ⩽ a_{n}$ ». $P (0)$ est vraie car $a_{0} ⩽ a_{0}$ . Soit $n$ tel que $0 ⩽ n ⩽ N - 1$ ; si $a_{0} ⩽ a_{n}$ , alors, comme $a_{n} ⩽ a_{n + 1}$ , la transitivité de $⩽$ donne $a_{0} ⩽ a_{n + 1}$ , donc $P (n + 1)$ est vraie. Par récurrence finie, $a_{0} ⩽ a_{n}$ pour tout $n$ entre $0$ et $N$ . $□$

L'hérédité s'arrête ici au rang $N - 1$ : il serait absurde de l'écrire au rang $N$ , puisque $a_{N + 1}$ n'existe pas.

Choisir la bonne forme de récurrence

Méthode

Quelle récurrence employer ? Regardez de quoi vous avez besoin pour franchir le pas de $n$ à $n + 1$ .

Le rang $n$ seul suffit (relation $u_{n + 1} = f (u_{n})$ , somme dont on isole le dernier terme, inégalité qui se propage) : récurrence simple.
Il faut les deux rangs précédents, et seulement ceux-là (relation $u_{n + 2} = a u_{n + 1} + b u_{n}$ ) : récurrence double, avec deux initialisations.
Il faut un rang antérieur inconnu à l'avance, ou tous les rangs précédents à la fois (décomposition d'un entier, division en deux morceaux de tailles quelconques) : récurrence forte.
La propriété n'a de sens que pour un nombre fini de rangs : récurrence finie, en prenant garde à arrêter l'hérédité au rang $N - 1$ .

En cas d'hésitation, la récurrence forte est toujours licite : elle suppose plus, donc elle est plus facile à faire aboutir. Mais annoncez alors clairement qu'il s'agit d'une récurrence forte, et écrivez l'hypothèse de récurrence en entier.

Ensembles

Appartenance, inclusion, égalité

La notion d'ensemble est ici une notion première : un ensemble est une collection d'objets, appelés ses éléments. Nous n'en donnerons pas de définition formelle, et nous n'entreprendrons aucune étude systématique de la théorie des ensembles : ce vocabulaire est un outil, pas un objet d'étude.

Définition

Si $x$ est un élément de l'ensemble $E$ , on écrit $x \in E$ ; dans le cas contraire, $x \notin E$ . Un ensemble peut être décrit :

en extension, par la liste de ses éléments : ${1, 2, 3}$ ;
en compréhension, par une propriété caractérisant ses éléments : ${x \in R ∣ x^{2} < 4}$ , qui se lit « l'ensemble des réels $x$ tels que $x^{2} < 4$ ».

L'ensemble ne contenant aucun élément est appelé ensemble vide et noté $\emptyset$ .

Définition

Soient $E$ et $F$ deux ensembles. On dit que $E$ est inclus dans $F$ , et l'on note $E \subset F$ , lorsque tout élément de $E$ est élément de $F$ :

E \subset F signifie \forall x, (x \in E ⟹ x \in F) .

On dit aussi que $E$ est une partie de $F$ , ou un sous-ensemble de $F$ . Lorsque $E \subset F$ et $E \neq F$ , l'inclusion est dite stricte et l'on note $E ⊊ F$ .

Remarque

Ne jamais confondre $\in$ et $\subset$ . Le symbole $\in$ relie un élément à un ensemble ; le symbole $\subset$ relie deux ensembles. Ainsi, pour $E = {1, 2}$ :

$1 \in E$ est vrai, mais $1 \subset E$ n'a pas de sens ;
${1} \subset E$ est vrai, mais ${1} \in E$ est faux, car les éléments de $E$ sont $1$ et $2$ , et non ${1}$ .

De même, $\emptyset \subset E$ est vrai pour tout $E$ , alors que $\emptyset \in E$ est en général faux.

Propriété

Soient $E$ , $F$ , $G$ des ensembles.

$\emptyset \subset E$ et $E \subset E$ .
Transitivité : si $E \subset F$ et $F \subset G$ , alors $E \subset G$ .
Double inclusion : $E = F$ si et seulement si $E \subset F$ et $F \subset E$ .

Démonstration. 1. L'inclusion $\emptyset \subset E$ signifie : pour tout $x$ , si $x \in \emptyset$ alors $x \in E$ . L'hypothèse « $x \in \emptyset$ » est toujours fausse, donc cette implication est vraie pour tout $x$ : c'est une implication vide, et l'inclusion est acquise. L'inclusion $E \subset E$ est immédiate.

2. Soit $x \in E$ . Comme $E \subset F$ , on a $x \in F$ ; comme $F \subset G$ , on a $x \in G$ . Ainsi tout élément de $E$ appartient à $G$ , c'est-à-dire $E \subset G$ .

3. Si $E = F$ , les deux inclusions sont évidentes. Réciproquement, si $E \subset F$ et $F \subset E$ , alors $E$ et $F$ ont exactement les mêmes éléments : pour tout $x$ , $x \in E$ entraîne $x \in F$ et réciproquement. Deux ensembles ayant les mêmes éléments sont égaux, donc $E = F$ . $□$

Méthode

Montrer une égalité d'ensembles $X = Y$ . Deux rédactions.

Par double inclusion (méthode par défaut) : on montre $X \subset Y$ , puis $Y \subset X$ . Chaque inclusion se rédige de la même façon : « Soit $x \in X$ . ... donc $x \in Y$ . » Annoncez les deux sens.
Par équivalences : on écrit une chaîne « $x \in X ⟺ \dots ⟺ x \in Y$ ». C'est plus court, mais chaque étape doit être une véritable équivalence. Dès qu'une étape n'est pas réversible (typiquement en présence d'un $\exists$ ), revenir à la double inclusion.

Dans les deux cas, on commence toujours par « Soit $x$ » : une égalité d'ensembles se démontre élément par élément.

Ensemble des parties

Définition

Soit $E$ un ensemble. L'ensemble de toutes les parties de $E$ est noté $P (E)$ . Ainsi, pour tout ensemble $A$ :

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

Exemple

Pour $E = {a, b}$ , les parties de $E$ sont $\emptyset$ , ${a}$ , ${b}$ et ${a, b}$ , donc

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

Pour $E = \emptyset$ , la seule partie de $E$ est $\emptyset$ lui-même, donc $P (\emptyset) = {\emptyset}$ .

Remarque

Les ensembles $\emptyset$ et ${\emptyset}$ sont différents : le premier n'a aucun élément, le second en a un, à savoir $\emptyset$ . De même, ${a}$ et $a$ ne sont pas le même objet.

Notez le changement de statut permanent de la barre : un objet $A$ est un élément de $P (E)$ et une partie de $E$ . Écrire $A \subset P (E)$ au lieu de $A \in P (E)$ est une faute de sens, pas une coquette.

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

Dans toute la suite de cette section, $E$ désigne un ensemble fixé, et $A$ , $B$ , $C$ des parties de $E$ .

Définition

La réunion de $A$ et $B$ est $A \cup B = {x \in E ∣ x \in A ou x \in B}$ .
L'intersection de $A$ et $B$ est $A \cap B = {x \in E ∣ x \in A et x \in B}$ .
$A$ et $B$ sont dits disjoints lorsque $A \cap B = \emptyset$ .
Le complémentaire de $A$ dans $E$ est $\overline{A} = {x \in E ∣ x \notin A}$ .
La différence de $A$ et $B$ est $A ∖ B = {x \in E ∣ x \in A et x \notin B}$ .

Remarque

La notation $\overline{A}$ n'a de sens que si l'ensemble ambiant $E$ est clairement fixé : le complémentaire de $N$ dans $Z$ n'est pas le complémentaire de $N$ dans $R$ . Quand un doute est possible, on écrit $E ∖ A$ .

Ne confondez pas « disjoints » et « distincts » : ${1, 2}$ et ${2, 3}$ sont distincts sans être disjoints.

Les identités suivantes se lisent directement sur les définitions et sur les règles logiques de la section « Assertions et connecteurs » ; nous les utiliserons sans les citer.

a. $A \cap \overline{A} = \emptyset$

b. $A \cup \overline{A} = E$

c. $\overline{\overline{A}} = A$

d. $A ∖ B = A \cap \overline{B}$

e. $A \cap E = A$ et $A \cup E = E$

f. $A \cap \emptyset = \emptyset$ et $A \cup \emptyset = A$

g. $A \cap A = A$ et $A \cup A = A$

h. $A \subset B ⟺ A \cap B = A ⟺ A \cup B = B$

Propriété

Soient $A$ , $B$ , $C$ des parties de $E$ . La réunion et l'intersection sont commutatives et associatives :

A \cup B = B \cup A, A \cap B = B \cap A,

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

On peut donc écrire $A \cup B \cup C$ et $A \cap B \cap C$ sans parenthèses.

Démonstration. Ces égalités traduisent, au niveau des ensembles, les propriétés correspondantes des connecteurs « ou » et « et ». Par exemple, pour l'associativité de la réunion, soit $x \in E$ :

\begin{aligned} x \in (A \cup B) \cup C & ⟺ ((x \in A ou x \in B) ou x \in C) \\ ⟺ (x \in A ou (x \in B ou x \in C)) \\ ⟺ x \in A \cup (B \cup C), \end{aligned}

la deuxième équivalence étant l'associativité de la disjonction, qui se vérifie sur une table de vérité. Les trois autres égalités s'obtiennent de la même manière. $□$

Lois de De Morgan et distributivité

Propriété

Lois de De Morgan. Soient $A$ et $B$ deux parties de $E$ . Alors

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

Démonstration. Démontrons la première égalité par double inclusion.

Inclusion $\overline{A \cup B} \subset \overline{A} \cap \overline{B}$ . Soit $x \in \overline{A \cup B}$ . Par définition du complémentaire, $x \in E$ et $x \notin A \cup B$ . Si l'on avait $x \in A$ , on aurait $x \in A \cup B$ par définition de la réunion, ce qui est exclu : donc $x \notin A$ , c'est-à-dire $x \in \overline{A}$ . Le même argument avec $B$ donne $x \in \overline{B}$ . Ainsi $x \in \overline{A} \cap \overline{B}$ .

Inclusion $\overline{A} \cap \overline{B} \subset \overline{A \cup B}$ . Soit $x \in \overline{A} \cap \overline{B}$ . Alors $x \in E$ , $x \notin A$ et $x \notin B$ . Si l'on avait $x \in A \cup B$ , alors $x$ appartiendrait à $A$ ou à $B$ , ce qui contredit ce qui précède : donc $x \notin A \cup B$ , c'est-à-dire $x \in \overline{A \cup B}$ .

Les deux inclusions donnent l'égalité.

Démontrons la seconde égalité par équivalences, l'autre technique. Soit $x \in E$ :

\begin{aligned} x \in \overline{A \cap B} & ⟺ x \notin A \cap B \\ ⟺ \neg (x \in A et x \in B) \\ ⟺ (x \notin A ou x \notin B) \\ ⟺ (x \in \overline{A} ou x \in \overline{B}) \\ ⟺ x \in \overline{A} \cup \overline{B} . \end{aligned}

La troisième équivalence est exactement la règle logique de négation d'une conjonction. Comme toutes les étapes sont des équivalences, les deux ensembles ont les mêmes éléments : ils sont égaux. $□$

Propriété

Distributivité. Soient $A$ , $B$ , $C$ des parties de $E$ . Alors

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

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

Démonstration. Démontrons la distributivité de $\cap$ sur $\cup$ par double inclusion.

Inclusion $A \cap (B \cup C) \subset (A \cap B) \cup (A \cap C)$ . Soit $x \in A \cap (B \cup C)$ . Alors $x \in A$ et $x \in B \cup C$ , donc $x \in B$ ou $x \in C$ . Distinguons ces deux cas.

Si $x \in B$ : comme de plus $x \in A$ , on a $x \in A \cap B$ , donc $x \in (A \cap B) \cup (A \cap C)$ .
Si $x \in C$ : comme de plus $x \in A$ , on a $x \in A \cap C$ , donc $x \in (A \cap B) \cup (A \cap C)$ .

Dans les deux cas, $x$ appartient à $(A \cap B) \cup (A \cap C)$ , ce qui établit l'inclusion.

Inclusion $(A \cap B) \cup (A \cap C) \subset A \cap (B \cup C)$ . Soit $x \in (A \cap B) \cup (A \cap C)$ . Alors $x \in A \cap B$ ou $x \in A \cap C$ .

Si $x \in A \cap B$ : alors $x \in A$ , et $x \in B$ donc $x \in B \cup C$ ; ainsi $x \in A \cap (B \cup C)$ .
Si $x \in A \cap C$ : alors $x \in A$ , et $x \in C$ donc $x \in B \cup C$ ; ainsi $x \in A \cap (B \cup C)$ .

Dans les deux cas, $x \in A \cap (B \cup C)$ , ce qui établit la seconde inclusion, donc l'égalité.

La seconde formule se démontre exactement de la même façon, en échangeant les rôles de $\cup$ et $\cap$ ; on peut aussi la déduire de la première en passant au complémentaire et en appliquant les lois de De Morgan. $□$

Remarque

Les deux distributivités sont vraies, contrairement à ce qui se passe pour l'addition et la multiplication des réels, où seule la multiplication est distributive sur l'addition. C'est une raison de plus pour ne pas raisonner par analogie avec le calcul algébrique : les symboles $\cup$ et $\cap$ ne sont pas $+$ et $\times$ .

Différence symétrique

Définition

Soient $A$ et $B$ deux parties de $E$ . La différence symétrique de $A$ et $B$ est

A Δ B = (A ∖ B) \cup (B ∖ A) .

C'est l'ensemble des éléments qui appartiennent à l'une des deux parties, mais pas aux deux.

Propriété

Pour toutes parties $A$ et $B$ de $E$ :

A Δ B = (A \cup B) ∖ (A \cap B) .

Démonstration. Soit $x \in E$ . Dire que $x \in A Δ B$ , c'est dire que $x$ appartient à $A$ et pas à $B$ , ou bien à $B$ et pas à $A$ . Dans les deux cas, $x$ appartient à $A \cup B$ et n'appartient pas à $A \cap B$ : donc $A Δ B \subset (A \cup B) ∖ (A \cap B)$ .

Réciproquement, soit $x \in (A \cup B) ∖ (A \cap B)$ : alors $x \in A$ ou $x \in B$ , et $x$ n'appartient pas simultanément aux deux. Si $x \in A$ , alors $x \notin B$ (sinon $x \in A \cap B$ ), donc $x \in A ∖ B$ . Sinon, $x \in B$ et $x \notin A$ , donc $x \in B ∖ A$ . Dans les deux cas $x \in A Δ B$ , d'où la seconde inclusion et l'égalité. $□$

Réunion et intersection d'une famille de parties

Définition

Soit $I$ un ensemble non vide, 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}} .

Exemple

Prenons $E = R$ , $I = N$ et, pour $n \in N$ , $A_{n} = [- n, n]$ . Un réel $x$ appartient à la réunion s'il appartient à l'un au moins des $A_{n}$ ; comme tout réel vérifie $∣ x ∣ ⩽ n$ pour un entier $n$ assez grand, on a $⋃_{n \in N} A_{n} = R$ .

Un réel appartient à l'intersection s'il appartient à tous les $A_{n}$ , en particulier à $A_{0} = {0}$ : ainsi $⋂_{n \in N} A_{n} = {0}$ .

Propriété

Lois de De Morgan généralisées. Soit $(A_{i})_{i \in I}$ une famille de parties de $E$ , avec $I$ non vide. Alors

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

Démonstration. Soit $x \in E$ . Pour la première égalité :

\begin{aligned} x \in \overline{⋃_{i \in I} A_{i}} & ⟺ \neg (\exists i \in I, x \in A_{i}) \\ ⟺ \forall i \in I, x \notin A_{i} \\ ⟺ \forall i \in I, x \in \overline{A_{i}} \\ ⟺ x \in ⋂_{i \in I} \overline{A_{i}} . \end{aligned}

La deuxième équivalence est la règle de négation d'une proposition existentielle. La seconde égalité s'obtient en échangeant les rôles de $\forall$ et $\exists$ , ou en appliquant la première à la famille $(\overline{A_{i}})_{i \in I}$ et en passant au complémentaire. $□$

Produit cartésien

Définition

Soient $E$ et $F$ deux ensembles. Le produit cartésien de $E$ par $F$ est l'ensemble des couples $(x, y)$ où $x \in E$ et $y \in F$ :

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

Deux couples sont égaux lorsqu'ils ont mêmes composantes, dans le même ordre :

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

On note $E^{2} = E \times E$ , et plus généralement $E \times F \times G$ l'ensemble des triplets, $E^{n}$ l'ensemble des $n$ -uplets $(x_{1}, \dots, x_{n})$ d'éléments de $E$ .

Remarque

Un couple n'est pas une paire : $(1, 2) \neq (2, 1)$ , alors que ${1, 2} = {2, 1}$ . Dans un couple, l'ordre compte et les répétitions sont permises.

De même, $E \times F$ et $F \times E$ sont en général différents, et $E \times \emptyset = \emptyset$ : s'il n'y a aucun second élément à choisir, il n'y a aucun couple.

Recouvrement et partition

Définition

Soit $(A_{i})_{i \in I}$ une famille de parties de $E$ .

La famille est un recouvrement de $E$ lorsque $⋃_{i \in I} A_{i} = E$ , c'est-à-dire lorsque tout élément de $E$ appartient à l'une au moins des parties $A_{i}$ .
La famille est une partition de E lorsque les trois conditions suivantes sont réunies :
1. pour tout $i \in I$ , $A_{i} \neq \emptyset$ ;
2. les parties sont deux à deux disjointes : pour tous $i, j \in I$ , si $i \neq j$ alors $A_{i} \cap A_{j} = \emptyset$ ;
3. la famille recouvre $E$ : $⋃_{i \in I} A_{i} = E$ .

Autrement dit, une partition de $E$ est un découpage de $E$ en morceaux non vides qui ne se chevauchent pas et ne laissent rien de côté : tout élément de $E$ appartient à une et une seule des parties de la famille.

Exemple

a. Les parties $P$ (entiers pairs) et $I$ (entiers impairs) forment une partition de $Z$ : aucune n'est vide, elles sont disjointes, et tout entier est pair ou impair.

b. Pour toute partie $A$ de $E$ avec $A \neq \emptyset$ et $A \neq E$ , la famille $(A, \overline{A})$ est une partition de $E$ . C'est la partition sous-jacente à toute disjonction de cas « selon que $x$ appartient ou non à $A$ ».

c. La famille formée de $] - \infty, 1]$ et de $[0, + \infty [$ est un recouvrement de $R$ , mais pas une partition : les deux parties ne sont pas disjointes, leur intersection étant $[0, 1]$ .

d. La famille $([n, n + 1 [)_{n \in Z}$ est une partition de $R$ : tout réel appartient à un unique intervalle de cette forme.

Remarque

Une partition n'est pas seulement un recouvrement : les conditions de non-vacuité et de disjonction sont essentielles, et ce sont elles qui donnent son sens à l'expression « une et une seule ». Nous retrouverons cette notion en fin de chapitre, avec les classes d'équivalence.

Applications

Définitions et premiers exemples

Définition

Soient $E$ et $F$ deux ensembles. Une application $f$ de $E$ dans $F$ , notée $f : E \to F$ , est la donnée, pour chaque élément $x$ de $E$ , d'un unique élément de $F$ noté $f (x)$ .

L'ensemble $E$ est l'ensemble de départ, $F$ l'ensemble d'arrivée. L'élément $f (x)$ est l'image de $x$ par $f$ ; si $y = f (x)$ , on dit que $x$ est un antécédent de $y$ par $f$ . On note $F (E, F)$ l'ensemble des applications de $E$ dans $F$ .

Remarque

Les mots comptent. Un élément de $E$ a une seule image ; un élément de $F$ peut avoir zéro, un, ou plusieurs antécédents. C'est cette dissymétrie qui produira les notions d'injection et de surjection.

Attention aussi à ne pas confondre $f$ , qui est l'application, et $f (x)$ , qui est un élément de $F$ . Écrire « la fonction $f (x)$ » est un abus toléré au lycée, mais proscrit ici.

Définition

Égalité de deux applications. Deux applications $f$ et $g$ sont égales lorsqu'elles ont le même ensemble de départ $E$ , le même ensemble d'arrivée $F$ , et vérifient

\forall x \in E, f (x) = g (x) .

Remarque

Les ensembles de départ et d'arrivée font partie de l'application. Les applications $f : R \to R$ , $x \mapsto x^{2}$ et $g : R \to R_{+}$ , $x \mapsto x^{2}$ ne sont pas égales, bien qu'elles aient la même formule : la seconde est surjective, la première ne l'est pas. Changer l'ensemble d'arrivée, c'est changer d'application.

Définition

L'identité de $E$ est l'application ${i d}_{E} : E \to E$ définie par ${i d}_{E} (x) = x$ pour tout $x \in E$ .
Soit $f : E \to F$ et $A$ une partie de $E$ . La restriction de $f$ à $A$ est l'application $f_{∣ A} : A \to F$ définie par $f_{∣ A} (x) = f (x)$ pour tout $x \in A$ .
Soient $E \subset E^{'}$ , $f : E \to F$ et $g : E^{'} \to F$ . On dit que $g$ est un prolongement de $f$ à $E^{'}$ lorsque $g_{∣ E} = f$ , c'est-à-dire lorsque $g (x) = f (x)$ pour tout $x \in E$ .

Exemple

Soit $f : R \to R$ , $x \mapsto x^{2}$ . Sa restriction $f_{∣ R_{+}}$ à $R_{+}$ est une application différente de $f$ : elle a un autre ensemble de départ, et nous verrons qu'elle est injective alors que $f$ ne l'est pas.

Inversement, l'application $g : R^{*} \to R$ , $x \mapsto \frac{\sin x}{x}$ admet plusieurs prolongements à $R$ : il suffit de choisir arbitrairement une valeur en $0$ . Un prolongement n'a donc aucune raison d'être unique.

Composition

Définition

Soient $f : E \to F$ et $g : F \to G$ . La composée de $f$ par $g$ est l'application

g \circ f : E \to G, (g \circ f) (x) = g (f (x)) pour tout x \in E .

Remarque

L'écriture $g \circ f$ n'a de sens que si l'ensemble d'arrivée de $f$ est l'ensemble de départ de $g$ . L'ordre de lecture est celui de l'écriture des images : dans $g \circ f$ , c'est $f$ qui agit en premier. C'est déroutant, mais c'est imposé par la notation $g (f (x))$ .

Propriété

Associativité de la composition. Soient $f : E \to F$ , $g : F \to G$ et $h : G \to H$ . Alors

h \circ (g \circ f) = (h \circ g) \circ f .

De plus, pour toute application $f : E \to F$ , on a $f \circ {i d}_{E} = f$ et ${i d}_{F} \circ f = f$ .

Démonstration. Les deux applications $h \circ (g \circ f)$ et $(h \circ g) \circ f$ ont le même ensemble de départ $E$ et le même ensemble d'arrivée $H$ : la première condition d'égalité est remplie. Soit maintenant $x \in E$ . D'une part,

(h \circ (g \circ f)) (x) = h ((g \circ f) (x)) = h (g (f (x))),

et d'autre part,

((h \circ g) \circ f) (x) = (h \circ g) (f (x)) = h (g (f (x))) .

Les deux applications coïncident en tout point de $E$ : elles sont égales.

Pour la seconde partie, $f \circ {i d}_{E}$ et $f$ vont toutes deux de $E$ dans $F$ , et pour tout $x \in E$ , $(f \circ {i d}_{E}) (x) = f ({i d}_{E} (x)) = f (x)$ ; de même, $({i d}_{F} \circ f) (x) = {i d}_{F} (f (x)) = f (x)$ . $□$

Remarque

La composition n'est pas commutative, même lorsque les deux composées ont un sens. Prenons $f : R \to R$ , $x \mapsto x + 1$ et $g : R \to R$ , $x \mapsto x^{2}$ . Alors

(g \circ f) (x) = (x + 1)^{2} et (f \circ g) (x) = x^{2} + 1,

et ces deux applications diffèrent, par exemple en $x = 1$ où elles valent respectivement $4$ et $2$ . L'associativité permet donc de supprimer les parenthèses, jamais de changer l'ordre des facteurs.

Fonction indicatrice

Définition

Soit $A$ une partie de $E$ . La fonction indicatrice de $A$ est l'application $1_{A} : E \to {0, 1}$ définie par

1_{A} (x) = {\begin{cases} 1 & si x \in A, \\ 0 & si x \notin A . \end{cases}

Propriété

Soient $A$ et $B$ deux parties de $E$ . Alors :

$A = B ⟺ 1_{A} = 1_{B}$ ;
$1_{\overline{A}} = 1 - 1_{A}$ ;
$1_{A \cap B} = 1_{A} 1_{B}$ ;
$1_{A \cup B} = 1_{A} + 1_{B} - 1_{A} 1_{B}$ .

Démonstration. 1. Si $A = B$ , les deux indicatrices sont visiblement égales. Réciproquement, supposons $1_{A} = 1_{B}$ et montrons $A = B$ par double inclusion. Soit $x \in A$ : alors $1_{A} (x) = 1$ , donc $1_{B} (x) = 1$ , donc $x \in B$ (si $x$ n'était pas dans $B$ , on aurait $1_{B} (x) = 0$ ). Ainsi $A \subset B$ , et l'inclusion réciproque s'obtient en échangeant les rôles.

2. Soit $x \in E$ . Si $x \in A$ , alors $x \notin \overline{A}$ , donc $1_{\overline{A}} (x) = 0 = 1 - 1 = 1 - 1_{A} (x)$ . Si $x \notin A$ , alors $x \in \overline{A}$ , donc $1_{\overline{A}} (x) = 1 = 1 - 0 = 1 - 1_{A} (x)$ . Les deux applications coïncident en tout point.

3. Soit $x \in E$ . Si $x \in A \cap B$ , le membre de gauche vaut $1$ , et le membre de droite vaut $1 \times 1 = 1$ . Sinon, $x \notin A$ ou $x \notin B$ , donc l'un au moins des deux facteurs $1_{A} (x)$ , $1_{B} (x)$ est nul, et le produit vaut $0$ , tout comme $1_{A \cap B} (x)$ .

4. Partons du complémentaire. D'après les lois de De Morgan, $\overline{A \cup B} = \overline{A} \cap \overline{B}$ , donc, en utilisant les points 2 et 3 :

\begin{aligned} 1 - 1_{A \cup B} = 1_{\overline{A \cup B}} = 1_{\overline{A} \cap \overline{B}} = 1_{\overline{A}} 1_{\overline{B}} & = (1 - 1_{A}) (1 - 1_{B}) \\ = 1 - 1_{A} - 1_{B} + 1_{A} 1_{B} . \end{aligned}

En simplifiant par $1$ et en changeant les signes, on obtient $1_{A \cup B} = 1_{A} + 1_{B} - 1_{A} 1_{B}$ . $□$

Exemple

Les indicatrices transforment les identités ensemblistes en calculs algébriques : c'est souvent la manière la plus rapide de démontrer une égalité de parties. Établissons ainsi

1_{A Δ B} = 1_{A} + 1_{B} - 2 1_{A} 1_{B} .

Comme $A Δ B = (A \cup B) ∖ (A \cap B)$ et que $A \cap B \subset A \cup B$ , un élément de $A Δ B$ est un élément de $A \cup B$ qui n'est pas dans $A \cap B$ , d'où

1_{A Δ B} = 1_{A \cup B} - 1_{A \cap B} = (1_{A} + 1_{B} - 1_{A} 1_{B}) - 1_{A} 1_{B} = 1_{A} + 1_{B} - 2 1_{A} 1_{B} .

Le point 1 de la propriété précédente garantit qu'une égalité d'indicatrices équivaut à une égalité de parties : le calcul est donc une démonstration complète, à condition de conclure explicitement.

Image directe et image réciproque

Définition

Soit $f : E \to F$ .

L'image directe d'une partie $A$ de $E$ est la partie de $F$

f (A) = {f (x) ∣ x \in A} = {y \in F ∣ \exists x \in A, y = f (x)} .

L'image réciproque d'une partie $B$ de $F$ est la partie de $E$

f^{- 1} (B) = {x \in E ∣ f (x) \in B} .

L'ensemble $f (E)$ s'appelle l'image de $f$ et se note aussi $I m (f)$ .

Remarque

La notation $f^{- 1} (B)$ ne suppose pas $f$ bijective. C'est le piège le plus fréquent du chapitre. L'écriture $f^{- 1} (B)$ a un sens pour n'importe quelle application $f$ et n'importe quelle partie $B$ de $F$ : c'est simplement l'ensemble des antécédents des éléments de $B$ . Elle ne présuppose l'existence d'aucune application réciproque, et $f^{- 1}$ n'y désigne pas un objet à part entière.

Ainsi, pour $f : R \to R$ , $x \mapsto x^{2}$ , qui n'est ni injective ni surjective, on a parfaitement le droit d'écrire $f^{- 1} ({4}) = {- 2, 2}$ et $f^{- 1} ({- 1}) = \emptyset$ .

Retenez la traduction, qui règle tous les exercices : $x \in f^{- 1} (B)$ signifie exactement $f (x) \in B$ .

Propriété

Soit $f : E \to F$ , soient $A$ et $A^{'}$ deux parties de $E$ , et soient $B$ et $B^{'}$ deux 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^{'})$ .
$f^{- 1} (B \cap B^{'}) = f^{- 1} (B) \cap f^{- 1} (B^{'})$ .
$f^{- 1} (\overline{B}) = \overline{f^{- 1} (B)}$ , les complémentaires étant pris respectivement dans $F$ et dans $E$ .
$A \subset f^{- 1} (f (A))$ et $f (f^{- 1} (B)) \subset B$ , ces inclusions pouvant être strictes.

Démonstration. 2. Soit $y \in f (A \cap A^{'})$ . Par définition de l'image directe, il existe $x \in A \cap A^{'}$ tel que $y = f (x)$ . Comme $x \in A$ , l'élément $y = f (x)$ appartient à $f (A)$ ; comme $x \in A^{'}$ , il appartient aussi à $f (A^{'})$ . Donc $y \in f (A) \cap f (A^{'})$ , ce qui prouve l'inclusion.

L'inclusion réciproque est fausse en général. Prenons $f : R \to R$ , $x \mapsto x^{2}$ , $A = {- 1}$ et $A^{'} = {1}$ . Alors $A \cap A^{'} = \emptyset$ , donc $f (A \cap A^{'}) = \emptyset$ , tandis que $f (A) = {1} = f (A^{'})$ , donc $f (A) \cap f (A^{'}) = {1}$ . L'inclusion est bien stricte. La raison profonde : si $y \in f (A) \cap f (A^{'})$ , on dispose d'un antécédent de $y$ dans $A$ et d'un antécédent de $y$ dans $A^{'}$ , mais rien ne dit que c'est le même.

4. Soit $x \in E$ . En utilisant deux fois la traduction « $x \in f^{- 1} (X)$ signifie $f (x) \in X$ » :

\begin{aligned} x \in f^{- 1} (B \cap B^{'}) & ⟺ f (x) \in B \cap B^{'} \\ ⟺ (f (x) \in B et f (x) \in B^{'}) \\ ⟺ (x \in f^{- 1} (B) et x \in f^{- 1} (B^{'})) \\ ⟺ x \in f^{- 1} (B) \cap f^{- 1} (B^{'}) . \end{aligned}

Toutes les étapes étant des équivalences, les deux ensembles sont égaux.

1. Montrons l'égalité par double inclusion. Si $y \in f (A \cup A^{'})$ , il existe $x \in A \cup A^{'}$ avec $y = f (x)$ ; selon que $x \in A$ ou $x \in A^{'}$ , on obtient $y \in f (A)$ ou $y \in f (A^{'})$ , donc $y \in f (A) \cup f (A^{'})$ . Réciproquement, si $y \in f (A) \cup f (A^{'})$ , alors $y = f (x)$ pour un $x$ appartenant à $A$ ou à $A^{'}$ , donc à $A \cup A^{'}$ , d'où $y \in f (A \cup A^{'})$ .

3. et 5. se démontrent comme le point 4, par une chaîne d'équivalences : pour le point 5, $x \in f^{- 1} (\overline{B}) ⟺ f (x) \in \overline{B} ⟺ f (x) \notin B ⟺ x \notin f^{- 1} (B) ⟺ x \in \overline{f^{- 1} (B)}$ .

6. Soit $x \in A$ . Alors $f (x) \in f (A)$ par définition de l'image directe, donc $x \in f^{- 1} (f (A))$ par définition de l'image réciproque : d'où $A \subset f^{- 1} (f (A))$ . Soit maintenant $y \in f (f^{- 1} (B))$ : il existe $x \in f^{- 1} (B)$ tel que $y = f (x)$ ; mais $x \in f^{- 1} (B)$ signifie $f (x) \in B$ , c'est-à-dire $y \in B$ . D'où $f (f^{- 1} (B)) \subset B$ . $□$

Remarque

Retenez la dissymétrie : l'image réciproque se comporte parfaitement bien (elle respecte la réunion, l'intersection et le complémentaire), alors que l'image directe ne respecte que la réunion. C'est une conséquence directe des quantificateurs en jeu : $f^{- 1}$ se définit avec un $\forall$ implicite sur $x$ fixé, tandis que $f (A)$ se définit avec un $\exists$ , et un $\exists$ ne traverse pas une conjonction.

Injections, surjections, bijections

Définition

Soit $f : E \to F$ .

$f$ est injective lorsque tout élément de $F$ admet au plus un antécédent par $f$ , ce qui s'écrit

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

$f$ est surjective lorsque tout élément de $F$ admet au moins un antécédent par $f$ , ce qui s'écrit

\forall y \in F, \exists x \in E, y = f (x) .

$f$ est bijective lorsqu'elle est à la fois injective et surjective, c'est-à-dire lorsque tout élément de $F$ admet exactement un antécédent :

\forall y \in F, \exists! x \in E, y = f (x) .

Méthode

Montrer qu'une application est injective, surjective, bijective.

Injectivité : on part de deux éléments $x$ et $x^{'}$ de $E$ tels que $f (x) = f (x^{'})$ , et on démontre $x = x^{'}$ . Rédaction : « Soient $x, x^{'} \in E$ tels que $f (x) = f (x^{'})$ . Alors ... donc $x = x^{'}$ . » On peut aussi utiliser la contraposée : « si $x \neq x^{'}$ alors $f (x) \neq f (x^{'})$ », mais c'est en général moins commode.
Non-injectivité : il suffit d'exhiber deux éléments distincts ayant la même image.
Surjectivité : on se donne $y \in F$ quelconque, et on construit un $x \in E$ tel que $f (x) = y$ ; on vérifie bien que ce $x$ appartient à $E$ . Rédaction : « Soit $y \in F$ . Posons $x = \dots$ ; alors $x \in E$ et $f (x) = y$ . »
Non-surjectivité : il suffit d'exhiber un élément de $F$ n'ayant aucun antécédent.
Bijectivité : trois voies. Soit on démontre séparément l'injectivité et la surjectivité ; soit on résout, pour $y \in F$ fixé, l'équation $f (x) = y$ d'inconnue $x \in E$ et l'on montre qu'elle admet une unique solution (c'est une analyse-synthèse déguisée) ; soit on exhibe une application $g : F \to E$ telle que $g \circ f = {i d}_{E}$ et $f \circ g = {i d}_{F}$ (caractérisation ci-dessous), ce qui est la voie la plus rapide quand on devine $g$ .

Exemple

a. $f : R \to R$ , $x \mapsto x^{2}$ n'est ni injective ( $f (- 1) = f (1) = 1$ avec $- 1 \neq 1$ ), ni surjective (le réel $- 1$ n'a pas d'antécédent, car un carré est positif ou nul).

b. $g : R_{+} \to R$ , $x \mapsto x^{2}$ est injective : si $x, x^{'} ⩾ 0$ vérifient $x^{2} = x^{' 2}$ , alors $(x - x^{'}) (x + x^{'}) = 0$ , donc $x = x^{'}$ ou $x = - x^{'}$ ; dans le second cas, $x$ et $x^{'}$ étant positifs ou nuls, on a $x = x^{'} = 0$ . Dans tous les cas $x = x^{'}$ . En revanche $g$ n'est pas surjective.

c. $h : R \to R$ , $x \mapsto 3 x - 5$ est bijective : soit $y \in R$ ; l'équation $3 x - 5 = y$ d'inconnue $x$ équivaut à $x = \frac{y + 5}{3}$ , qui est un réel bien défini et unique. Tout réel a donc un unique antécédent.

d. ${i d}_{E}$ est bijective, pour tout ensemble $E$ .

Définition

Soit $f : E \to F$ une application bijective. Pour tout $y \in F$ , il existe un unique $x \in E$ tel que $f (x) = y$ . L'application qui, à chaque $y \in F$ , associe cet unique antécédent est appelée application réciproque de $f$ et notée $f^{- 1} : F \to E$ . Elle vérifie, par construction,

\forall x \in E, \forall y \in F, (y = f (x) ⟺ x = f^{- 1} (y)) .

Remarque

La notation $f^{- 1}$ est malheureusement utilisée pour deux objets différents : l'application réciproque $f^{- 1} : F \to E$ , qui n'existe que si $f$ est bijective, et l'image réciproque $f^{- 1} (B)$ d'une partie, qui existe toujours. Le contexte tranche : si l'argument est une partie de $F$ , il s'agit de l'image réciproque ; si c'est un élément de $F$ , il s'agit de l'application réciproque.

Lorsque $f$ est bijective, les deux notions sont d'ailleurs cohérentes : l'image réciproque de $B$ par $f$ coïncide avec l'image directe de $B$ par l'application $f^{- 1}$ .

Propriété

Caractérisation des bijections par les composées. 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}$ .

De plus, lorsque c'est le cas, l'application $g$ est unique et vaut $f^{- 1}$ .

Démonstration. $(1) ⟹ (2)$ . Supposons $f$ bijective. Pour tout $y \in F$ , il existe un unique $x \in E$ tel que $f (x) = y$ ; posons $g (y) = x$ . Cela définit bien une application $g : F \to E$ , puisque l'élément associé à $y$ existe (surjectivité) et est unique (injectivité).

Vérifions les deux égalités. Soit $x \in E$ et posons $y = f (x)$ . Par définition, $g (y)$ est l'unique antécédent de $y$ par $f$ ; or $x$ en est un antécédent, donc $g (y) = x$ , c'est-à-dire $(g \circ f) (x) = x = {i d}_{E} (x)$ . Comme $g \circ f$ et ${i d}_{E}$ vont toutes deux de $E$ dans $E$ , on a $g \circ f = {i d}_{E}$ . Soit maintenant $y \in F$ ; par définition de $g$ , l'élément $g (y)$ est un antécédent de $y$ , donc $f (g (y)) = y = {i d}_{F} (y)$ , d'où $f \circ g = {i d}_{F}$ .

$(2) ⟹ (1)$ . Supposons qu'il existe $g : F \to E$ vérifiant $g \circ f = {i d}_{E}$ et $f \circ g = {i d}_{F}$ .

Injectivité de $f$ . Soient $x, x^{'} \in E$ tels que $f (x) = f (x^{'})$ . En appliquant $g$ aux deux membres, $g (f (x)) = g (f (x^{'}))$ , c'est-à-dire $(g \circ f) (x) = (g \circ f) (x^{'})$ , donc ${i d}_{E} (x) = {i d}_{E} (x^{'})$ , soit $x = x^{'}$ .

Surjectivité de $f$ . Soit $y \in F$ . Posons $x = g (y)$ , qui est bien un élément de $E$ . Alors

f (x) = f (g (y)) = (f \circ g) (y) = {i d}_{F} (y) = y,

donc $y$ admet $x$ pour antécédent.

Ainsi $f$ est injective et surjective, donc bijective.

Unicité de $g$ . Supposons que $g$ et $g^{'}$ vérifient toutes deux les conditions du point 2. En utilisant l'associativité de la composition et les propriétés de l'identité :

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

L'application $g$ est donc unique ; comme $f^{- 1}$ convient d'après le premier sens de la démonstration, on a $g = f^{- 1}$ . $□$

Remarque

Les deux égalités $g \circ f = {i d}_{E}$ et $f \circ g = {i d}_{F}$ sont toutes les deux nécessaires. Une seule ne suffit pas : si l'on prend $f : R_{+} \to R$ , $x \mapsto x^{2}$ et $g : R \to R_{+}$ , $y \mapsto \sqrt{∣ y ∣}$ , alors $g \circ f = {i d}_{R_{+}}$ , mais $f \circ g \neq {i d}_{R}$ (évaluer en $- 1$ ), et de fait $f$ n'est pas bijective.

Composition, injectivité et surjectivité

Propriété

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

Si $f$ et $g$ sont injectives, alors $g \circ f$ est injective.
Si $f$ et $g$ sont surjectives, alors $g \circ f$ est surjective.
Si $g \circ f$ est injective, alors $f$ est injective.
Si $g \circ f$ est surjective, alors $g$ est surjective.
Si $f$ et $g$ sont bijectives, alors $g \circ f$ est bijective et $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ .

Démonstration. 3. Soient $x, x^{'} \in E$ tels que $f (x) = f (x^{'})$ . En appliquant $g$ aux deux membres, on obtient $g (f (x)) = g (f (x^{'}))$ , c'est-à-dire $(g \circ f) (x) = (g \circ f) (x^{'})$ . Comme $g \circ f$ est injective, il vient $x = x^{'}$ . Donc $f$ est injective.

4. Soit $z \in G$ . Comme $g \circ f$ est surjective, il existe $x \in E$ tel que $(g \circ f) (x) = z$ , c'est-à-dire $g (f (x)) = z$ . L'élément $f (x)$ appartient à $F$ et est un antécédent de $z$ par $g$ : donc $g$ est surjective.

1. Soient $x, x^{'} \in E$ tels que $(g \circ f) (x) = (g \circ f) (x^{'})$ , c'est-à-dire $g (f (x)) = g (f (x^{'}))$ . L'injectivité de $g$ donne $f (x) = f (x^{'})$ , puis celle de $f$ donne $x = x^{'}$ .

2. Soit $z \in G$ . La surjectivité de $g$ fournit $y \in F$ tel que $g (y) = z$ , puis celle de $f$ fournit $x \in E$ tel que $f (x) = y$ . Alors $(g \circ f) (x) = g (y) = z$ .

5. D'après les points 1 et 2, $g \circ f$ est bijective. Posons $h = f^{- 1} \circ g^{- 1}$ , qui va bien de $G$ dans $E$ . En utilisant l'associativité :

\begin{aligned} h \circ (g \circ f) & = f^{- 1} \circ g^{- 1} \circ g \circ f = f^{- 1} \circ {i d}_{F} \circ f = f^{- 1} \circ f = {i d}_{E}, \\ (g \circ f) \circ h & = g \circ f \circ f^{- 1} \circ g^{- 1} = g \circ {i d}_{F} \circ g^{- 1} = g \circ g^{- 1} = {i d}_{G} . \end{aligned}

Par la caractérisation des bijections et l'unicité de l'application $g$ qui y figure, $h$ est la réciproque de $g \circ f$ : $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ . $□$

Remarque

Les réciproques des points 3 et 4 sont fausses, et les énoncés ne sont pas symétriques : de « $g \circ f$ injective » on ne peut rien conclure sur $g$ , et de « $g \circ f$ surjective » rien sur $f$ . Moyen mnémotechnique : c'est toujours l'application qui agit en premier ( $f$ ) qui hérite de l'injectivité, et celle qui agit en dernier ( $g$ ) qui hérite de la surjectivité. Notez aussi l'inversion de l'ordre dans la formule $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ : pour défaire deux opérations successives, on défait d'abord la dernière.

Relations binaires

Généralité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 ou n'est pas en relation avec $y$ . Lorsque $x$ est en relation avec $y$ , on écrit $x R y$ .

Définition

Soit $R$ une relation binaire sur $E$ . On dit que $R$ est :

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

Exemple

a. L'égalité sur $E$ est réflexive, symétrique, antisymétrique et transitive.

b. La relation $⩽$ sur $R$ est réflexive, antisymétrique et transitive, mais pas symétrique.

c. La relation $<$ sur $R$ est transitive, mais n'est ni réflexive, ni symétrique. Elle est antisymétrique, pour une raison amusante : l'hypothèse « $x < y$ et $y < x$ » n'est jamais réalisée, donc l'implication est vide, donc vraie.

d. L'inclusion $\subset$ sur $P (E)$ est réflexive, antisymétrique et transitive.

e. La divisibilité $∣$ sur $N$ est réflexive et transitive ; elle est antisymétrique, car deux entiers naturels qui se divisent mutuellement sont égaux.

f. La relation « avoir la même parité » sur $Z$ est réflexive, symétrique et transitive, mais pas antisymétrique ( $2$ et $4$ ont la même parité sans être égaux).

Remarque

Trois pièges de vocabulaire.

« Antisymétrique » ne signifie pas « non symétrique ». L'égalité est à la fois symétrique et antisymétrique ; la relation $<$ sur $R$ n'est ni l'une ni l'autre au sens intuitif, et pourtant elle est antisymétrique au sens de la définition.
La divisibilité sur $Z$ n'est pas antisymétrique : $1 ∣ - 1$ et $- 1 ∣ 1$ , mais $1 \neq - 1$ . Changer l'ensemble change la réponse.
Une relation réflexive et transitive n'est pas nécessairement une relation d'équivalence : il lui manque la symétrie. La divisibilité sur $N$ et l'inclusion sur $P (E)$ en sont deux exemples, et ce sont au contraire des relations d'ordre.

Remarque

Une fausse démonstration célèbre. « Si $R$ est symétrique et transitive, alors elle est réflexive : en effet, $x R y$ donne $y R x$ par symétrie, puis $x R x$ par transitivité. » L'argument est faux, car il suppose l'existence d'un $y$ tel que $x R y$ , ce que rien ne garantit. Contre-exemple : sur $E = {1, 2}$ , la relation définie par $1 R 1$ et rien d'autre est symétrique et transitive, mais pas réflexive, car $2 R 2$ est faux. Retenez la leçon : un quantificateur existentiel qui n'a pas été démontré ne se glisse pas discrètement dans une démonstration.

Relations d'équivalence et classes

Définition

Une relation d'équivalence sur $E$ est une relation binaire réflexive, symétrique et transitive.

Exemple

a. L'égalité sur n'importe quel ensemble.

b. « Avoir la même parité » sur $Z$ .

c. Sur $R$ , la relation définie par $x R y$ lorsque $x - y \in Z$ . Réflexive car $x - x = 0 \in Z$ ; symétrique car $y - x = - (x - y)$ est entier dès que $x - y$ l'est ; transitive car $x - z = (x - y) + (y - z)$ est somme de deux entiers.

d. Sur $R$ , la relation $∣ x ∣ = ∣ y ∣$ .

e. Étant donnée une application $f : E \to F$ , la relation définie sur $E$ par $x R y$ lorsque $f (x) = f (y)$ . C'est le modèle général : toutes les relations d'équivalence rencontrées en pratique sont de cette forme, « avoir le même quelque chose ».

Définition

Soit $R$ une relation d'équivalence sur $E$ et soit $x \in E$ . La classe d'équivalence de $x$ est la partie de $E$

C l (x) = {y \in E ∣ x R y} .

Tout élément d'une classe est appelé un représentant de cette classe.

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) \neq \emptyset$ .
$x R y ⟺ C l (x) = C l (y)$ .
Deux classes d'équivalence sont soit égales, soit disjointes : si $C l (x) \cap C l (y) \neq \emptyset$ , alors $C l (x) = C l (y)$ .

Démonstration. 1. La réflexivité donne $x R x$ , donc $x \in C l (x)$ , qui est par conséquent non vide.

2. Supposons $x R y$ et montrons $C l (x) = C l (y)$ par double inclusion. Soit $t \in C l (y)$ , c'est-à-dire $y R t$ . De $x R y$ et $y R t$ , la transitivité donne $x R t$ , donc $t \in C l (x)$ : ainsi $C l (y) \subset C l (x)$ . Pour l'autre inclusion, la symétrie donne $y R x$ , et le raisonnement précédent, appliqué en échangeant $x$ et $y$ , donne $C l (x) \subset C l (y)$ . D'où l'égalité.

Réciproquement, supposons $C l (x) = C l (y)$ . D'après le point 1, $y \in C l (y) = C l (x)$ , ce qui signifie exactement $x R y$ .

3. Supposons $C l (x) \cap C l (y) \neq \emptyset$ et choisissons $z$ dans cette intersection. Alors $x R z$ et $y R z$ . Par symétrie, $z R y$ , puis par transitivité appliquée à $x R z$ et $z R y$ , on obtient $x R y$ . Le point 2 donne alors $C l (x) = C l (y)$ . $□$

Propriété

Théorème. Soit $R$ une relation d'équivalence sur un ensemble $E$ non vide. Les classes d'équivalence de $R$ réalisent une partition de $E$ : elles sont non vides, deux à deux disjointes ou confondues, et tout élément de $E$ appartient à l'une d'elles, à savoir la sienne.

Autrement dit, la famille $(C l (x))_{x \in E}$ , dont on ne retient qu'une fois chaque partie distincte, est une partition de $E$ : chaque élément de $E$ appartient à une et une seule classe.

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

Les classes sont non vides. C'est le point 1 de la propriété précédente : $x \in C l (x)$ .

Deux classes distinctes sont disjointes. Soient $C l (x)$ et $C l (y)$ deux classes. D'après le point 3 de la propriété précédente, si leur intersection est non vide, elles sont égales. Par contraposition, si elles sont distinctes, leur intersection est vide : elles sont disjointes.

Les classes recouvrent $E$ . Chaque classe est une partie de $E$ , donc leur réunion est incluse dans $E$ . Réciproquement, tout $x \in E$ appartient à $C l (x)$ , qui est l'une des classes : $x$ appartient donc à la réunion. Par double inclusion, la réunion des classes est $E$ tout entier.

Unicité de la classe contenant un élément donné. Soit $x \in E$ . Il appartient à $C l (x)$ . S'il appartient aussi à une classe $C l (y)$ , alors $x \in C l (x) \cap C l (y)$ , donc cette intersection est non vide et $C l (x) = C l (y)$ : c'est bien la même classe. $□$

Exemple

Reprenons la relation « avoir la même parité » sur $Z$ . La classe de $0$ est l'ensemble des entiers pairs, la classe de $1$ est l'ensemble des entiers impairs, et ce sont les deux seules classes. Elles sont non vides, disjointes, et leur réunion est $Z$ : on retrouve la partition de $Z$ en pairs et impairs rencontrée à la section « Recouvrement et partition ».

Pour la relation $∣ x ∣ = ∣ y ∣$ sur $R$ , la classe de $0$ est ${0}$ , et la classe d'un réel $a$ non nul est la paire ${- a, a}$ . Là encore, ces parties sont non vides, deux à deux disjointes, et recouvrent $R$ .

Remarque

Une classe d'équivalence est une partie de $E$ , pas un élément de $E$ . Un même élément $y$ peut représenter sa classe aussi bien que n'importe quel autre élément de celle-ci : la notation $C l (x)$ dépend de $x$ , mais l'objet désigné ne dépend que de la classe. C'est pourquoi, dès qu'une définition est posée « sur les classes » à partir d'un représentant, il faut vérifier qu'elle ne dépend pas du représentant choisi.

Relations d'ordre

Définition

Une relation d'ordre sur $E$ est une relation binaire réflexive, antisymétrique et transitive. Le couple $(E, R)$ s'appelle alors un ensemble ordonné.

L'ordre est dit total lorsque deux éléments quelconques sont toujours comparables :

\forall x \in E, \forall y \in E, (x R y ou y R x) .

Dans le cas contraire, l'ordre est dit partiel.

Remarque

Une relation d'ordre quelconque se note souvent $⩽$ par analogie avec l'ordre usuel des réels ; nous conserverons ici la notation $R$ , réservée aux relations, afin d'éviter toute confusion avec l'ordre de $R$ .

Exemple

a. $⩽$ sur $R$ est un ordre total : deux réels sont toujours comparables.

b. L'inclusion $\subset$ sur $P (E)$ est un ordre partiel dès que $E$ possède au moins deux éléments distincts $a$ et $b$ : les parties ${a}$ et ${b}$ ne sont pas comparables, aucune n'étant incluse dans l'autre.

c. La divisibilité $∣$ sur $N$ est un ordre partiel : ni $2 ∣ 3$ , ni $3 ∣ 2$ .

Majorants, minorants, plus grand et plus petit élément

Dans toute cette section, $(E, R)$ est un ensemble ordonné et $A$ une partie de $E$ .

Définition

Un élément $m$ de $E$ est un majorant de $A$ lorsque $\forall a \in A, a R m$ . Si $A$ admet au moins un majorant, on dit que $A$ est majorée.
Un élément $m$ de $E$ est un minorant de $A$ lorsque $\forall a \in A, m R a$ . Si $A$ admet au moins un minorant, on dit que $A$ est minorée.
$A$ est bornée lorsqu'elle est à la fois majorée et minorée.

Remarque

Un majorant de $A$ est un élément de $E$ : il n'a aucune raison d'appartenir à $A$ . Ainsi, dans $R$ muni de $⩽$ , le réel $5$ est un majorant de l'intervalle $[0, 1]$ , et $1$ également. Un majorant n'est pas non plus unique : tout élément « plus grand » qu'un majorant en est un autre.

Définition

Un élément $m$ est un plus grand élément de $A$ lorsque $m \in A$ et $m$ est un majorant de $A$ , c'est-à-dire $\forall a \in A, a R m$ .
Un élément $m$ est un plus petit élément de $A$ lorsque $m \in A$ et $m$ est un minorant de $A$ , c'est-à-dire $\forall a \in A, m R a$ .

Propriété

Unicité. Une partie $A$ de $E$ admet au plus un plus grand élément, et au plus un plus petit élément. Lorsqu'il existe, le plus grand élément de $A$ se note $\max A$ , et le plus petit $\min A$ .

Démonstration. Supposons que $m$ et $m^{'}$ soient deux plus grands éléments de $A$ , et montrons $m = m^{'}$ .

Comme $m^{'}$ est un plus grand élément de $A$ , il appartient à $A$ ; comme $m$ est un majorant de $A$ , on en déduit $m^{'} R m$ .

Symétriquement, $m$ appartient à $A$ et $m^{'}$ est un majorant de $A$ , donc $m R m^{'}$ .

On a ainsi $m R m^{'}$ et $m^{'} R m$ ; l'antisymétrie de la relation d'ordre donne alors $m = m^{'}$ . Il y a donc au plus un plus grand élément, ce qui légitime l'article défini et la notation $\max A$ . La démonstration pour le plus petit élément est identique, en échangeant les deux membres de chaque relation. $□$

Remarque

C'est l'antisymétrie, et elle seule, qui assure cette unicité. C'est aussi ce qui distingue une relation d'ordre d'une relation seulement réflexive et transitive : sans antisymétrie, deux « plus grands éléments » distincts pourraient coexister.

Exemple

Dans $R$ muni de $⩽$ :

a. $[0, 1]$ admet $0$ pour plus petit élément et $1$ pour plus grand élément.

b. $[0, 1 [$ admet $0$ pour plus petit élément, mais pas de plus grand élément. Supposons en effet par l'absurde que $m = \max [0, 1 [$ . Alors $m \in [0, 1 [$ , donc $0 ⩽ m < 1$ . Posons $m^{'} = \frac{m + 1}{2}$ . Comme $m < 1$ , on a $m < m^{'} < 1$ , donc $m^{'} \in [0, 1 [$ ; mais $m^{'} > m$ , ce qui contredit le fait que $m$ majore $[0, 1 [$ . Il n'y a donc pas de plus grand élément, alors que la partie est pourtant majorée, par exemple par $1$ .

c. $R$ n'est ni majoré ni minoré, donc n'admet ni plus grand ni plus petit élément.

Éléments maximaux et minimaux

Lorsque l'ordre est partiel, la notion de plus grand élément est souvent trop exigeante : il faut être comparable à tous les éléments. On introduit alors une notion plus faible.

Définition

Soit $A$ une partie de $E$ .

Un élément $m$ de $A$ est maximal dans $A$ lorsqu'aucun élément de $A$ ne lui est strictement supérieur :

\forall a \in A, (m R a ⟹ a = m) .

Un élément $m$ de $A$ est minimal dans $A$ lorsque $\forall a \in A, (a R m ⟹ a = m)$ .

Remarque

La différence est subtile mais essentielle. Un plus grand élément est supérieur à tous les autres ; un élément maximal n'est inférieur à aucun autre, ce qui est beaucoup plus faible : il peut simplement n'être comparable à personne. Un plus grand élément est toujours maximal, et il est alors le seul élément maximal ; la réciproque est fausse en ordre partiel. Lorsque l'ordre est total, les deux notions coïncident.

Exemple

Munissons $A = {2, 3, 4, 6, 9}$ de la divisibilité. Les relations sont $2 ∣ 4$ , $2 ∣ 6$ , $3 ∣ 6$ , $3 ∣ 9$ , plus les relations de chaque élément avec lui-même.

Les éléments maximaux sont $4$ , $6$ et $9$ : aucun élément de $A$ n'est un multiple strict de l'un d'eux.
Les éléments minimaux sont $2$ et $3$ : aucun élément de $A$ ne les divise strictement.
$A$ n'admet ni plus grand ni plus petit élément : un plus grand élément devrait être un multiple de tous les autres, et il n'y en a pas dans $A$ .

Cet exemple montre bien qu'il peut exister plusieurs éléments maximaux, alors qu'il existe au plus un plus grand élément.

Applications croissantes

Définition

Soient $(E, R)$ et $(F, S)$ deux ensembles ordonnés, et $f : E \to F$ . On dit que $f$ est :

croissante lorsque $\forall x \in E, \forall y \in E, (x R y ⟹ f (x) S f (y))$ ;
décroissante lorsque $\forall x \in E, \forall y \in E, (x R y ⟹ f (y) S f (x))$ ;
monotone lorsqu'elle est croissante ou décroissante.

Lorsque les ordres sont totaux, on dit que $f$ est strictement croissante lorsque $x R y$ et $x \neq y$ entraînent $f (x) S f (y)$ et $f (x) \neq f (y)$ , et de même pour la stricte décroissance.

Exemple

a. Soit $f : E \to F$ . L'application $P (F) \to P (E)$ , $B \mapsto f^{- 1} (B)$ est croissante pour l'inclusion. En effet, si $B \subset B^{'}$ et si $x \in f^{- 1} (B)$ , alors $f (x) \in B \subset B^{'}$ , donc $f (x) \in B^{'}$ , donc $x \in f^{- 1} (B^{'})$ .

b. L'application $P (E) \to P (E)$ , $A \mapsto \overline{A}$ est décroissante pour l'inclusion : si $A \subset B$ , alors $\overline{B} \subset \overline{A}$ . Démontrons-le : soit $x \in \overline{B}$ , c'est-à-dire $x \in E$ et $x \notin B$ . Si l'on avait $x \in A$ , l'inclusion $A \subset B$ donnerait $x \in B$ , ce qui est exclu ; donc $x \notin A$ , soit $x \in \overline{A}$ .

c. L'application $N \to N$ , $n \mapsto 2 n$ est croissante pour la divisibilité : si $a ∣ b$ , alors $2 a ∣ 2 b$ .

Propriété

Soient $(E, R)$ , $(F, S)$ , $(G, T)$ trois ensembles ordonnés, $f : E \to F$ et $g : F \to G$ deux applications croissantes. Alors $g \circ f$ est croissante.

Démonstration. Soient $x, y \in E$ tels que $x R y$ . La croissance de $f$ donne $f (x) S f (y)$ , puis la croissance de $g$ , appliquée aux deux éléments $f (x)$ et $f (y)$ de $F$ , donne $g (f (x)) T g (f (y))$ , c'est-à-dire $(g \circ f) (x) T (g \circ f) (y)$ . Donc $g \circ f$ est croissante. $□$

Remarque

Ce chapitre ne contient presque aucun calcul, et c'est précisément ce qui le rend difficile : tout y est affaire de rédaction. Les réflexes à acquérir dès maintenant sont peu nombreux, mais ils doivent devenir automatiques. Pour montrer une inclusion, commencer par « Soit $x \in \dots$ ». Pour montrer une égalité d'ensembles, annoncer les deux inclusions. Pour montrer une existence et une unicité, séparer les deux temps. Pour nier une proposition, procéder mécaniquement de la gauche vers la droite. Pour montrer une propriété universelle, prendre un élément quelconque et ne rien lui supposer de plus. Ces cinq gestes reviendront dans tous les chapitres de l'année.

Le cours en PDF(PDF, 203 Ko)

Bloqué sur « Raisonnement et vocabulaire ensembliste » ?

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