Éducation Nationale Française · BCPST

Logique, ensembles et raisonnement

⌚ ~458 min ▢ 55 blocs ✓ 245 exercices ➣ Prérequis : Raisonnement et Démonstration

Vue d'ensemble du chapitre

Toute démonstration s'écrit avec quelques mots : non, et, ou, si … alors, si et seulement si, pour tout, il existe. Ce chapitre fait de ces mots un langage précis. Un connecteur est défini par sa table de vérité ; les règles familières — lois de De Morgan, négation d'une implication, équivalence d'une implication avec sa contraposée, négation d'un énoncé quantifié — deviennent des lois, c'est-à-dire des formules vraies quelles que soient les propositions auxquelles on les applique, et chacune est démontrée : en raisonnant sur les lignes de la table où elle pourrait être fausse, par un calcul avec des lois déjà démontrées, ou par la table elle-même. Derrière les schémas de démonstration du chapitre Raisonner et rédiger — déduire, distinguer des cas, contraposer, raisonner par l'absurde — se tiennent ces lois. Le chapitre se termine par les quantificateurs : comment les nier, quand deux d'entre eux peuvent s'échanger, comment ils se combinent avec « et » et « ou ».
Notations. Les deux valeurs de vérité sont notées V (vrai) et F (faux). Les lettres $p$, $q$, $r$ désignent des propositions, et une loi s'énonce « pour toutes propositions $p$, $q$ : … ». L'équivalence s'écrit $\iff$, l'implication $\Rightarrow$.

Signaler une erreur

Prérequis

Ce chapitre suppose connus le chapitre Raisonnement et démonstration — propositions, connecteurs et leurs tables de vérité, la Méthode « Construire une table de vérité », quantificateurs — et le chapitre Raisonner et rédiger : les schémas de démonstration et leurs Méthodes, la négation d'un énoncé quantifié comme méthode de rédaction, le contre-exemple, la récurrence simple et la récurrence forte. Les exemples utilisent aussi : le calcul sur les réels (identités, inégalités, valeur absolue et inégalité triangulaire) ; la divisibilité des entiers, les nombres pairs et impairs ; les fonctions usuelles ; les suites, la définition de la convergence étant rappelée là où elle sert ; les approximations décimales d'un réel ; le langage des ensembles du chapitre Théorie des ensembles (élément, inclusion, ensemble vide, définition en compréhension, intersection, réunion, complémentaire).

Signaler une erreur

I Propositions et connecteurs

I.1 Propositions et prédicats

La table est la définition

Les propositions se combinent à l'aide de connecteurs : non, et, ou, si … alors, si et seulement si. En mathématiques, un connecteur est défini par sa table de vérité, qui donne la valeur de vérité de la proposition composée pour chaque combinaison des valeurs de vérité de ses composantes. La table n'est pas une illustration du connecteur : elle en est la définition. Une loi de la logique est alors un énoncé sur des tables, qui se lit sur elles ou se calcule à partir de lois déjà démontrées.

Signaler une erreur

Des énoncés vrais ou faux

La logique étudie les énoncés qui sont vrais ou faux, et la façon dont ils se combinent. Deux sortes d'énoncés se distinguent dès le départ : une proposition a une valeur de vérité telle qu'elle est écrite ; un prédicat dépend d'une variable et n'acquiert une valeur de vérité qu'une fois cette variable fixée. Les quantificateurs font d'un prédicat une proposition d'une autre façon.

Signaler une erreur

Définition — Proposition, valeur de vérité, prédicat

Une proposition est un énoncé déclaratif auquel on peut attribuer exactement l'une des deux valeurs de vérité V (vrai) ou F (faux). On note les propositions par des lettres minuscules $p, q, r, \dots$. Une proposition n'est jamais simultanément V et F ; c'est le principe de non-contradiction, que l'on adopte comme loi primitive du discours mathématique.
Un énoncé qui dépend d'une variable libre, par exemple « $n$ est pair » ou « $f(x) > 0$ », est appelé prédicat. Un prédicat n'a pas de valeur de vérité tel quel ; il n'en acquiert une qu'une fois la variable fixée.

Deux principes

Deux principes gouvernent toute proposition — le premier déjà énoncé dans la Définition « Proposition, valeur de vérité, prédicat » :

le principe de non-contradiction : aucune proposition n'est à la fois vraie et fausse ;
le principe du tiers exclu : toute proposition est vraie ou fausse — il n'y a pas de troisième valeur.

Ensemble, ils disent que toute proposition a exactement l'une des deux valeurs V et F. C'est pourquoi une table de vérité n'utilise que ces deux valeurs, et compte $2^n$ lignes pour $n$ propositions. Certains schémas de démonstration reposent sur le tiers exclu ; la Proposition « Raisonnement par l'absurde » montre exactement où il sert.

Signaler une erreur

Exemple — Des propositions, et des phrases qui n'en sont pas

« $7$ est un nombre premier » est une proposition, de valeur V.
« $\sqrt{2}$ est un nombre rationnel » est une proposition, de valeur F : une phrase fausse reste une proposition.
« Tout entier pair strictement supérieur à $2$ est la somme de deux nombres premiers » est une proposition — la conjecture de Goldbach — dont la valeur est inconnue à ce jour : une proposition a une valeur de vérité même quand personne ne la connaît.
« Soit $x$ un réel » et l'expression $x^2 + 1$ ne sont pas des propositions : la question « est-ce vrai ? » n'a pas de sens pour l'introduction d'une lettre, ni pour une expression, qui n'affirme rien.

Exemple — Un prédicat devient une proposition

Pour un entier $n$, la phrase $P(n)$ : « $n$ est pair » est un prédicat ; elle n'a pas de valeur de vérité tant que $n$ n'est pas fixé. Fixer $n$ donne des propositions : $P(4)$ est vraie, $P(5)$ est fausse, $P(0)$ est vraie. Quantifier $n$ est une autre façon : « pour tout entier $n$, $n$ est pair » est une proposition, de valeur F, et « il existe un entier $n$ tel que $n$ soit pair » est une proposition, de valeur V. Dans ces deux phrases, la lettre $n$ ne désigne plus un entier particulier.

Compétences à pratiquer

Déterminer la valeur de vérité d'une proposition ★
Distinguer une proposition d'un prédicat ★

I.2 Négation, conjonction, disjonction

Des connecteurs vérifonctionnels

Un connecteur construit une proposition à partir d'une ou de plusieurs propositions : « non », « et », « ou », mais aussi « parce que ». Un connecteur est vérifonctionnel lorsque la valeur de vérité de la proposition composée ne dépend que des valeurs de vérité de ses composantes, et non de leur sens. Les connecteurs des mathématiques sont tous vérifonctionnels : c'est pourquoi chacun d'eux est entièrement décrit par sa table de vérité. Le connecteur « parce que » ne l'est pas. Pour une fonction $f$ dérivable, « $f$ est continue parce que $f$ est dérivable » est vraie, alors que « $f$ est continue parce que $7$ est premier », dont les deux composantes sont vraies elles aussi, est fausse : que $7$ soit premier n'est une raison de rien pour $f$.

Signaler une erreur

Définition — Négation

La négation d'une proposition $p$, notée $\neg p$ (lue « non $p$ »), est la proposition dont la valeur de vérité est l'opposée de celle de $p$. Sa table de vérité est :

$p$	$\neg p$
V	F
F	V

Exemple — Nier n'est pas prendre le contraire

La négation de « $x \ge 0$ » est « $x < 0$ », et non « $x \le 0$ » : le réel $0$ vérifie à la fois « $x \ge 0$ » et « $x \le 0$ », alors qu'une proposition et sa négation n'ont jamais la même valeur.
La négation de « $f$ est croissante sur $\mathbb{R}$ » est « $f$ n'est pas croissante sur $\mathbb{R}$ », ce qui n'est pas « $f$ est décroissante sur $\mathbb{R}$ » : la fonction $x \longmapsto x^2$ n'est ni croissante ni décroissante sur $\mathbb{R}$, puisque $-1 < 0$ et $(-1)^2 > 0^2$, alors que $0 < 1$ et $0^2 < 1^2$.
La négation de « l'entier $n$ est pair » est « $n$ est impair » : ici la propriété contraire est la négation, parce que tout entier est pair ou impair, et pas les deux.

Nier une propriété, c'est affirmer qu'elle est en défaut ; cela ne coïncide avec une propriété contraire que lorsque les deux couvrent tous les cas et s'excluent.

Définition — Conjonction

La conjonction de deux propositions $p$ et $q$, notée $p \wedge q$ (lue « $p$ et $q$ »), est vraie lorsque $p$ et $q$ sont vraies toutes les deux, et fausse sinon. Sa table de vérité est :

$p$	$q$	$p \wedge q$
V	V	V
V	F	F
F	V	F
F	F	F

Exemple — Deux conjonctions

La double inégalité $-1 \le x \le 1$ est une conjonction : elle signifie « $-1 \le x$ et $x \le 1$ ». Pour $x = 0$ les deux parties sont vraies, donc elle est vraie ; pour $x = 2$ la seconde partie est fausse, donc elle est fausse.
Pour un entier $n$, la conjonction « $2 \mid n$ et $3 \mid n$ » est vraie exactement lorsque $6 \mid n$. Si $6 \mid n$, écrivons $n = 6k$ avec $k \in \mathbb{Z}$ ; alors $$ \begin{aligned} n &= 2 \times 3k && \text{(} 6 = 2 \times 3\text{)} \\ &= 3 \times 2k, \end{aligned} $$ donc $2 \mid n$ et $3 \mid n$ : les deux parties sont vraies. Si $2 \mid n$ et $3 \mid n$, il existe $a, b \in \mathbb{Z}$ tels que $n = 2a$ et $n = 3b$, et $$ \begin{aligned} n &= 3n - 2n && \text{(} 3 - 2 = 1\text{)} \\ &= 3 \times 2a - 2 \times 3b && \text{(} n = 2a \text{ et } n = 3b\text{)} \\ &= 6(a - b), \end{aligned} $$ avec $a - b \in \mathbb{Z}$ : $6 \mid n$.

Définition — Disjonction

La disjonction de deux propositions $p$ et $q$, notée $p \vee q$ (lue « $p$ ou $q$ »), est vraie lorsque au moins l'une de $p$ ou $q$ est vraie, et fausse sinon. C'est le « ou » inclusif : $p$ seul, $q$ seul, ou les deux, sont acceptés. Sa table de vérité est :

$p$	$q$	$p \vee q$
V	V	V
V	F	V
F	V	V
F	F	F

Exemple — Ou inclusif, ou exclusif

En mathématiques, « ou » est inclusif : « $2 \mid 6$ ou $3 \mid 6$ » est vraie, et ses deux parties sont vraies. La langue courante emploie souvent un « ou » exclusif : « fromage ou dessert », sur un menu, exclut de prendre les deux. Le ou exclusif, vrai lorsque exactement l'une des propositions $p$ et $q$ est vraie, se dit « ou bien $p$, ou bien $q$ » ; sa table ne diffère de celle de $p \vee q$ que sur la première ligne :

$p$	$q$	$p \vee q$	ou exclusif
V	V	V	F
V	F	V	V
F	V	V	V
F	F	F	F

Compétences à pratiquer

Évaluer une proposition composée ★
Traduire une phrase en formule ★★

I.3 Implication et équivalence

La convention de l'hypothèse fausse

Une implication « si $p$, alors $q$ » n'affirme qu'une chose : chaque fois que $p$ est vraie, $q$ est vraie. Elle n'est donc fausse que dans un cas, $p$ vraie et $q$ fausse, et vraie dans tous les autres — en particulier chaque fois que $p$ est fausse. Cette convention est exigée par les énoncés « pour tout $x$ » : le théorème « pour tout réel $x$, si $x \ge 2$, alors $x^2 \ge 4$ » est vrai, donc l'implication doit être vraie pour tout $x$, y compris pour ceux pour lesquels $x \ge 2$ est fausse. Une implication n'est pas une causalité : « si $0 = 0$, alors $7$ est premier » est vraie, bien que l'égalité $0 = 0$ ne soit en rien une raison pour que $7$ soit premier ; seules comptent les valeurs de vérité.

Signaler une erreur

Définition — Implication

L'implication de $p$ vers $q$, notée $p \Rightarrow q$ (lue « si $p$, alors $q$ » ou « $p$ implique $q$ »), est la proposition qui est fausse uniquement lorsque $p$ est vraie et $q$ est fausse ; elle est vraie dans tous les autres cas. En particulier, une implication d'hypothèse fausse est automatiquement vraie. Sa table de vérité :

$p$	$q$	$p \Rightarrow q$
V	V	V
V	F	F
F	V	V
F	F	V

Exemple — Trois sortes de lignes

L'implication « $0 = 1 \Rightarrow 1 = 1$ » est vraie, et « $0 = 1 \Rightarrow 0 = 2$ » aussi : leur hypothèse est fausse.
La proposition « pour tout réel $x$, si $x$ est un entier naturel, alors $x \ge 0$ » est vraie. Selon $x$, l'implication qu'elle contient tombe sur trois sortes de lignes de la table : pour $x = 3$, entier naturel, elle est du type « V $\Rightarrow$ V » ; pour $x = \frac{1}{2}$, positif sans être un entier naturel, du type « F $\Rightarrow$ V » ; pour $x = -1$, du type « F $\Rightarrow$ F ». Elle est vraie sur chacune. La quatrième sorte, « V $\Rightarrow$ F », ne se produit jamais : c'est exactement ce qu'affirme la proposition.

Définition — Équivalence, contraposée, réciproque

Soient $p$ et $q$ deux propositions. L'équivalence de $p$ et $q$, notée $p \iff q$ et lue « $p$ si et seulement si $q$ », est la proposition qui est vraie lorsque $p$ et $q$ ont la même valeur de vérité, et fausse sinon. Sa table de vérité est :

$p$	$q$	$p \iff q$
V	V	V
V	F	F
F	V	F
F	F	V

La contraposée de l'implication $p \Rightarrow q$ est l'implication $\neg q \Rightarrow \neg p$ ; sa réciproque est l'implication $q \Rightarrow p$.

Exemple — Une réciproque fausse

Pour un réel $x$, l'implication « $x = 1 \Rightarrow x^2 = 1$ » est vraie : si $x = 1$, alors $x^2 = 1^2 = 1$. Sa réciproque « $x^2 = 1 \Rightarrow x = 1$ » est un autre énoncé, et elle est fausse pour $x = -1$ : l'hypothèse $(-1)^2 = 1$ est vraie et la conclusion $-1 = 1$ est fausse. Sa contraposée « $x^2 \ne 1 \Rightarrow x \ne 1$ », en revanche, est vraie pour tout réel $x$, comme l'implication elle-même : une implication et sa contraposée ont toujours la même valeur de vérité, ce qu'établit la Proposition « Équivalence avec la contraposée ».

Compétences à pratiquer

Déterminer la valeur de vérité d'une implication ★

II Tautologies et lois logiques

II.1 Lois de la négation, de la conjonction et de la disjonction

Des lois qui portent un nom

Les lois les plus utilisées portent un nom : double négation, lois de De Morgan, commutativité, associativité, distributivité. Un nom permet à un calcul de justifier chaque étape par la loi qu'il applique, comme un calcul algébrique justifie $x(y + z) = xy + xz$ par la distributivité ; la Méthode « Simplifier une formule » met ces lois au travail.

Signaler une erreur

Proposition — Double négation

Pour toute proposition $p$ : $$ \neg\neg p \iff p. $$ Nier deux fois redonne la proposition.

Preuve

Par la Définition « Négation », la valeur de vérité de $\neg p$ est l'opposée de celle de $p$, et la valeur de vérité de $\neg\neg p$ est l'opposée de celle de $\neg p$. Il n'y a que deux valeurs de vérité, donc l'opposée de l'opposée d'une valeur est cette valeur elle-même : $\neg\neg p$ a la valeur de vérité de $p$, sur les deux lignes. Donc $\neg\neg p \iff p$ est une tautologie.
Seconde démonstration : par la table de vérité.

$p$	$\neg p$	$\neg\neg p$
V	F	V
F	V	F

Les colonnes de $p$ et de $\neg\neg p$ coïncident sur les deux lignes.

Proposition — Lois de De Morgan

Pour toutes propositions $p$, $q$ : $$ \neg(p \wedge q) \iff \neg p \vee \neg q \qquad \text{et} \qquad \neg(p \vee q) \iff \neg p \wedge \neg q. $$ La négation échange « et » et « ou », et nie chaque partie.

Preuve

Première loi. Par la Définition « Conjonction », $p \wedge q$ est fausse exactement lorsque l'une au moins des propositions $p$, $q$ est fausse, c'est-à-dire lorsque l'une au moins des propositions $\neg p$, $\neg q$ est vraie — ce qui signifie que $\neg p \vee \neg q$ est vraie, par la Définition « Disjonction ». Ainsi $\neg(p \wedge q)$, vraie exactement lorsque $p \wedge q$ est fausse, et $\neg p \vee \neg q$ sont vraies sur les mêmes lignes : elles sont logiquement équivalentes.
Seconde loi. Elle découle de la première, appliquée aux propositions $\neg p$ et $\neg q$ : $$ \begin{aligned} \neg(p \vee q) &\iff \neg(\neg\neg p \vee \neg\neg q) && \text{(double négation, deux fois, et remplacement)} \\ &\iff \neg\neg(\neg p \wedge \neg q) && \text{(première loi pour } \neg p, \neg q\text{, et remplacement)} \\ &\iff \neg p \wedge \neg q. \end{aligned} $$ La dernière équivalence est la double négation, appliquée à $\neg p \wedge \neg q$.
Seconde démonstration : par la table de vérité.

$p$	$q$	$\neg p$	$\neg q$	$p \wedge q$	$\neg(p \wedge q)$	$\neg p \vee \neg q$	$p \vee q$	$\neg(p \vee q)$	$\neg p \wedge \neg q$
V	V	F	F	V	F	F	V	F	F
V	F	F	V	F	V	V	V	F	F
F	V	V	F	F	V	V	V	F	F
F	F	V	V	F	V	V	F	V	V

Les colonnes de $\neg(p \wedge q)$ et de $\neg p \vee \neg q$ coïncident, de même que les colonnes de $\neg(p \vee q)$ et de $\neg p \wedge \neg q$.

Exemple — Nier une double inégalité

Pour un réel $x$, la négation de la double inégalité $-1 \le x \le 1$ se calcule avec la loi de De Morgan : $$ \begin{aligned} \neg(-1 \le x \le 1) &\iff \neg\left((-1 \le x) \wedge (x \le 1)\right) && \text{(une double inégalité est une conjonction)} \\ &\iff \neg(-1 \le x) \vee \neg(x \le 1) && \text{(loi de De Morgan)} \\ &\iff (x < -1) \vee (x > 1). \end{aligned} $$ La dernière équivalence nie chaque inégalité : pour des réels, la négation de $a \le b$ est $a > b$. La négation de « entre $-1$ et $1$ » est « en dehors » : le complémentaire de $[-1, 1]$ dans $\mathbb{R}$ est $]-\infty, -1[ \, \cup \, ]1, +\infty[$. Le « et » est devenu « ou » : aucun réel n'est à la fois strictement inférieur à $-1$ et strictement supérieur à $1$.

Proposition — Commutativité et associativité

Pour toutes propositions $p$, $q$, $r$ : $$ p \wedge q \iff q \wedge p, \qquad (p \wedge q) \wedge r \iff p \wedge (q \wedge r), $$ $$ p \vee q \iff q \vee p, \qquad (p \vee q) \vee r \iff p \vee (q \vee r). $$ Ainsi $p \wedge q \wedge r$ et $p \vee q \vee r$ s'écrivent sans parenthèses. Une formule qui mélange les deux connecteurs garde ses parenthèses : $(p \wedge q) \vee r$ et $p \wedge (q \vee r)$ ne sont pas logiquement équivalentes, et l'on n'écrit jamais $p \wedge q \vee r$.

Preuve

Par la Définition « Conjonction », une conjonction est vraie exactement lorsque ses deux parties sont vraies. Ainsi $p \wedge q$ et $q \wedge p$ sont toutes deux vraies exactement lorsque $p$ et $q$ sont vraies ; et $(p \wedge q) \wedge r$ est vraie exactement lorsque $p \wedge q$ et $r$ sont vraies, c'est-à-dire lorsque $p$, $q$, $r$ sont vraies toutes les trois — exactement comme $p \wedge (q \wedge r)$. Par la Définition « Disjonction », une disjonction est fausse exactement lorsque ses deux parties sont fausses. Ainsi $p \vee q$ et $q \vee p$ sont toutes deux fausses exactement lorsque $p$ et $q$ sont fausses ; et $(p \vee q) \vee r$ et $p \vee (q \vee r)$ sont toutes deux fausses exactement lorsque $p$, $q$, $r$ sont fausses toutes les trois. Dans chacune des quatre lois, les deux membres ont la même valeur de vérité sur chaque ligne.
Sur la ligne où $p$ est fausse et $q$, $r$ vraies, $(p \wedge q) \vee r$ est vraie, puisque $r$ l'est, alors que $p \wedge (q \vee r)$ est fausse, puisque $p$ l'est : les deux formules ne sont pas logiquement équivalentes.

Proposition — Distributivité

Pour toutes propositions $p$, $q$, $r$ : $$ p \wedge (q \vee r) \iff (p \wedge q) \vee (p \wedge r) \qquad \text{et} \qquad p \vee (q \wedge r) \iff (p \vee q) \wedge (p \vee r). $$ Chacun des deux connecteurs se distribue sur l'autre — à la différence de la multiplication et de l'addition des réels, pour lesquelles $x + yz$ et $(x + y)(x + z)$ diffèrent en général.

Preuve

Les tables de la conjonction et de la disjonction donnent, pour toute proposition $X$ : si $p$ est vraie, $p \wedge X$ a la valeur de $X$ et $p \vee X$ est vraie ; si $p$ est fausse, $p \wedge X$ est fausse et $p \vee X$ a la valeur de $X$. On distingue deux cas, selon la valeur de $p$ ; ils couvrent les huit lignes de la table, quatre dans chacun.

Cas $p$ vraie. Les formules $p \wedge (q \vee r)$ et $(p \wedge q) \vee (p \wedge r)$ ont toutes deux la valeur de $q \vee r$, la seconde parce que $p \wedge q$ et $p \wedge r$ ont les valeurs de $q$ et de $r$. Les formules $p \vee (q \wedge r)$ et $(p \vee q) \wedge (p \vee r)$ sont toutes deux vraies, la seconde comme conjonction de deux propositions vraies.
Cas $p$ fausse. Les formules $p \wedge (q \vee r)$ et $(p \wedge q) \vee (p \wedge r)$ sont toutes deux fausses, la seconde comme disjonction de deux propositions fausses. Les formules $p \vee (q \wedge r)$ et $(p \vee q) \wedge (p \vee r)$ ont toutes deux la valeur de $q \wedge r$, la seconde parce que $p \vee q$ et $p \vee r$ ont les valeurs de $q$ et de $r$.

Dans les deux cas, les deux membres de chaque loi ont la même valeur de vérité : les deux lois sont des tautologies.
Seconde démonstration : par la table de vérité. Huit lignes, une table pour chaque loi :

$p$	$q$	$r$	$q \vee r$	$p \wedge (q \vee r)$	$p \wedge q$	$p \wedge r$	$(p \wedge q) \vee (p \wedge r)$
V	V	V	V	V	V	V	V
V	V	F	V	V	V	F	V
V	F	V	V	V	F	V	V
V	F	F	F	F	F	F	F
F	V	V	V	F	F	F	F
F	V	F	V	F	F	F	F
F	F	V	V	F	F	F	F
F	F	F	F	F	F	F	F

$p$	$q$	$r$	$q \wedge r$	$p \vee (q \wedge r)$	$p \vee q$	$p \vee r$	$(p \vee q) \wedge (p \vee r)$
V	V	V	V	V	V	V	V
V	V	F	F	V	V	V	V
V	F	V	F	V	V	V	V
V	F	F	F	V	V	V	V
F	V	V	V	V	V	V	V
F	V	F	F	F	V	F	F
F	F	V	F	F	F	V	F
F	F	F	F	F	F	F	F

Les colonnes de $p \wedge (q \vee r)$ et de $(p \wedge q) \vee (p \wedge r)$ coïncident, de même que les colonnes de $p \vee (q \wedge r)$ et de $(p \vee q) \wedge (p \vee r)$.

Méthode — Simplifier une formule

Pour transformer une formule en une formule équivalente plus simple :

écrire une chaîne alignée d'équivalences qui s'ouvre sur la formule donnée, une loi par ligne, nommée dans la colonne de droite — sauf sur la dernière ligne, dont la loi est nommée dans la phrase qui suit la chaîne ;
simplifier d'abord les parties internes lorsqu'une partie devient une tautologie ou une contradiction, puis faire entrer les négations jusqu'aux lettres, avec les lois de De Morgan et la double négation ;
utiliser les constantes : pour une tautologie $L$ et une contradiction $C$, et toute formule $X$, $$ X \wedge L \iff X, \qquad X \vee L \iff L, \qquad X \wedge C \iff C, \qquad X \vee C \iff X, $$ puisque sur chaque ligne $L$ est vraie et $C$ fausse, et que les tables de $\wedge$ et de $\vee$ donnent la valeur ; par commutativité, il en va de même avec la constante à gauche.

Par le principe de remplacement, chaque formule de la chaîne est logiquement équivalente à la première.

Exemple — Simplifier une négation

Montrer que $\neg(p \vee (\neg p \wedge q)) \iff \neg p \wedge \neg q$ est une tautologie, en simplifiant son membre de gauche.

Correction

La partie interne se simplifie d'abord : $$ \begin{aligned} \neg(p \vee (\neg p \wedge q)) &\iff \neg\left((p \vee \neg p) \wedge (p \vee q)\right) && \text{(distributivité, et remplacement)} \\ &\iff \neg(p \vee q) && \text{(} p \vee \neg p \text{ est une tautologie, neutre pour } \wedge\text{)} \\ &\iff \neg p \wedge \neg q. \end{aligned} $$ La dernière équivalence est la loi de De Morgan. Donc l'équivalence est une tautologie. En mots : « ni $p$, ni ($\neg p$ et $q$) » revient à « ni $p$ ni $q$ ».
Seconde méthode : faire entrer la négation d'abord. $$ \begin{aligned} \neg(p \vee (\neg p \wedge q)) &\iff \neg p \wedge \neg(\neg p \wedge q) && \text{(loi de De Morgan)} \\ &\iff \neg p \wedge (\neg\neg p \vee \neg q) && \text{(loi de De Morgan, et remplacement)} \\ &\iff \neg p \wedge (p \vee \neg q) && \text{(double négation, et remplacement)} \\ &\iff (\neg p \wedge p) \vee (\neg p \wedge \neg q) && \text{(distributivité)} \\ &\iff \neg p \wedge \neg q. \end{aligned} $$ La dernière équivalence vient de ce que $\neg p \wedge p$ est une contradiction, neutre pour $\vee$. La première méthode est plus courte : simplifier d'abord l'intérieur a supprimé toute une partie avant qu'il faille faire entrer la négation.

Compétences à pratiquer

Reconnaître la négation d'une formule ★
Nier une conjonction ou une disjonction ★
Appliquer les lois de De Morgan ★★
Simplifier une formule ★★

II.2 Lois de l'implication

Le connecteur des théorèmes

L'implication est le connecteur des théorèmes : presque tout théorème s'énonce « si …, alors … », et presque toute démonstration en établit une. Ses lois disent comment réécrire une implication — comme une disjonction, par sa négation, par sa contraposée — et comment deux implications font une équivalence.

Signaler une erreur

Proposition — L'implication comme disjonction

Pour toutes propositions $p$, $q$ : $$ (p \Rightarrow q) \iff \neg p \vee q. $$ Une implication est vraie exactement lorsque son hypothèse est fausse ou sa conclusion vraie.

Preuve

Par la Définition « Implication », $p \Rightarrow q$ n'est fausse que sur une ligne : $p$ vraie et $q$ fausse. Par la Définition « Disjonction », $\neg p \vee q$ n'est fausse que lorsque $\neg p$ et $q$ sont fausses toutes les deux, c'est-à-dire sur la même ligne : $p$ vraie et $q$ fausse. Les deux formules sont fausses sur la même ligne et vraies sur les trois autres : elles sont logiquement équivalentes.

Proposition — Négation d'une implication

Pour toutes propositions $p$, $q$ : $$ \neg(p \Rightarrow q) \iff p \wedge \neg q. $$ La négation d'une implication n'est pas une implication : c'est la conjonction « $p$ et non $q$ », qui décrit l'unique ligne où l'implication est fausse.

Preuve

On transforme le membre de gauche : $$ \begin{aligned} \neg(p \Rightarrow q) &\iff \neg(\neg p \vee q) && \text{(l'implication comme disjonction, et remplacement)} \\ &\iff \neg\neg p \wedge \neg q && \text{(loi de De Morgan)} \\ &\iff p \wedge \neg q. \end{aligned} $$ La dernière équivalence est la double négation, appliquée à la partie $\neg\neg p$ par remplacement.
Seconde démonstration : par l'unique ligne fausse. L'implication $p \Rightarrow q$ n'est fausse que sur une ligne, $p$ vraie et $q$ fausse ; donc sa négation n'est vraie que sur cette ligne. La conjonction $p \wedge \neg q$ est vraie exactement lorsque $p$ et $\neg q$ sont vraies, c'est-à-dire lorsque $p$ est vraie et $q$ fausse : sur la même ligne. Les deux formules sont vraies sur la même ligne et fausses sur les autres : elles sont logiquement équivalentes.

Proposition — Équivalence avec la contraposée

Pour toutes propositions $p$, $q$ : $$ (p \Rightarrow q) \iff (\neg q \Rightarrow \neg p). $$ Une implication et sa contraposée ont toujours la même valeur de vérité. Sa réciproque $q \Rightarrow p$, en revanche, ne lui est pas logiquement équivalente.

Preuve

On transforme la contraposée : $$ \begin{aligned} (\neg q \Rightarrow \neg p) &\iff \neg\neg q \vee \neg p && \text{(l'implication comme disjonction)} \\ &\iff q \vee \neg p && \text{(double négation, et remplacement)} \\ &\iff \neg p \vee q && \text{(commutativité)} \\ &\iff (p \Rightarrow q). \end{aligned} $$ La dernière équivalence est la Proposition « L'implication comme disjonction », lue de droite à gauche.
Seconde démonstration : par le sens. La contraposée $\neg q \Rightarrow \neg p$ n'est fausse que sur une ligne : $\neg q$ vraie et $\neg p$ fausse, c'est-à-dire $q$ fausse et $p$ vraie — exactement la ligne où $p \Rightarrow q$ est fausse. Les deux implications sont fausses sur la même ligne et vraies sur les autres : elles sont logiquement équivalentes.
La réciproque. Sur la ligne $p$ fausse, $q$ vraie, l'implication $p \Rightarrow q$ est vraie et sa réciproque $q \Rightarrow p$ est fausse : la formule $(p \Rightarrow q) \iff (q \Rightarrow p)$ est fausse sur cette ligne, donc ce n'est pas une tautologie.

Exemple — Quatre énoncés autour d'une implication

Pour un réel $x$, on considère l'implication « $x = 2 \Rightarrow x^2 = 4$ ». Écrire sa réciproque, sa contraposée et sa négation, et déterminer pour quels réels $x$ chacun des quatre énoncés est vrai.

Correction

L'implication « $x = 2 \Rightarrow x^2 = 4$ » est vraie pour tout réel $x$ : si $x = 2$, alors $x^2 = 2^2 = 4$ ; si $x \ne 2$, son hypothèse est fausse.
La réciproque « $x^2 = 4 \Rightarrow x = 2$ » est fausse pour $x = -2$, où son hypothèse $(-2)^2 = 4$ est vraie et sa conclusion $-2 = 2$ fausse. Elle est vraie pour tout autre réel : pour $x = 2$ sa conclusion est vraie, et pour $x \notin \{-2, 2\}$ son hypothèse est fausse.
La contraposée « $x^2 \ne 4 \Rightarrow x \ne 2$ » est vraie pour tout réel $x$, par l'équivalence avec la contraposée.
La négation « $x = 2$ et $x^2 \ne 4$ », obtenue par la négation d'une implication, est fausse pour tout réel $x$ : elle exigerait $x = 2$ et $2^2 \ne 4$.

L'implication et sa contraposée ont la même valeur de vérité pour tout $x$, et la négation prend la valeur opposée ; la réciproque est un autre énoncé, faux pour $x = -2$ seulement.

Proposition — Équivalence et double implication

Pour toutes propositions $p$, $q$ : $$ (p \iff q) \iff \left((p \Rightarrow q) \wedge (q \Rightarrow p)\right). $$ Une équivalence est une double implication : elle se démontre en démontrant les deux implications.

Preuve

Par la Définition « Conjonction », le membre de droite est faux exactement lorsque l'une des deux implications est fausse : $p \Rightarrow q$ sur la ligne $p$ vraie, $q$ fausse, ou $q \Rightarrow p$ sur la ligne $q$ vraie, $p$ fausse. Ce sont exactement les deux lignes où $p$ et $q$ n'ont pas la même valeur de vérité, c'est-à-dire où $p \iff q$ est fausse, par la Définition « Équivalence, contraposée, réciproque ». Les deux membres sont faux sur les mêmes lignes : ils sont logiquement équivalents.
Seconde démonstration : par la table de vérité.

$p$	$q$	$p \Rightarrow q$	$q \Rightarrow p$	$(p \Rightarrow q) \wedge (q \Rightarrow p)$	$p \iff q$
V	V	V	V	V	V
V	F	F	V	F	F
F	V	V	F	F	F
F	F	V	V	V	V

Les colonnes de $(p \Rightarrow q) \wedge (q \Rightarrow p)$ et de $p \iff q$ coïncident.

Compétences à pratiquer

Nommer la loi d'une équivalence ★
Écrire la contraposée, la réciproque et la négation d'une implication ★★

III Ensembles et éléments

III.1 Ensembles, éléments, égalité

Connu par ses éléments

Un ensemble est connu par ses éléments, et par rien d'autre : deux ensembles qui ont les mêmes éléments sont égaux. Il se décrit de trois façons — par la liste de ses éléments, par une condition que vérifient ses éléments, ou comme l'ensemble des valeurs d'une expression quand un paramètre varie. Deux relations relient un ensemble à d'autres objets, et elles ne doivent pas être confondues : l'appartenance, $x \in E$, entre un élément et un ensemble, et l'inclusion, $A \subset E$, entre deux ensembles.

Signaler une erreur

Une notion première

La notion d'ensemble est première : elle ne se définit pas à partir d'objets plus élémentaires, et le chapitre Théorie des ensembles en a donné le sens — une collection d'objets, ses éléments. Ce que ce chapitre ajoute, c'est la précision : les définitions s'écrivent en formules, avec les quantificateurs et les connecteurs du chapitre Logique, de sorte que les énoncés sur les ensembles se démontrent comme les autres, par un calcul sur des formules. Dans ces formules, la variable $x$ parcourt tous les objets, comme dans la Définition « Universel, existentiel, unicité » ; les Propositions « Négation des quantificateurs » et « Quantificateurs et connecteurs », énoncées là pour un ensemble $E$, valent de la même façon pour une variable qui parcourt tous les objets. Une nouveauté apparaît dès le départ : un élément d'un ensemble peut être lui-même un ensemble.

Signaler une erreur

Définition — Ensemble, élément, égalité

Un ensemble est une collection d'objets, appelés ses éléments. Pour un objet $x$ et un ensemble $E$, $x \in E$ se lit « $x$ appartient à $E$ », ou « $x$ est un élément de $E$ » ; sa négation s'écrit $x \notin E$. Un élément d'un ensemble peut être lui-même un ensemble : l'ensemble $\{1, \{1\}\}$ a deux éléments, le nombre $1$ et l'ensemble $\{1\}$.
Deux ensembles $E$ et $F$ sont égaux, et l'on note $E = F$, lorsqu'ils ont les mêmes éléments : $$ E = F \iff \forall x, \ (x \in E \iff x \in F). $$

Exemple — Ni l'ordre ni les répétitions ne comptent

Pour l'ensemble $E = \{1, 2, 3, 4, 5, 6\}$ des résultats d'un dé, $2 \in E$ et $7 \notin E$. Les ensembles $\{1, 2, 3\}$, $\{3, 1, 2\}$ et $\{1, 1, 2, 3\}$ sont égaux : un objet appartient à l'un d'eux exactement lorsqu'il vaut $1$, $2$ ou $3$, donc ils ont les mêmes éléments, et la Définition « Ensemble, élément, égalité » donne l'égalité. Ni l'ordre dans lequel les éléments sont listés ni leurs répétitions ne changent l'ensemble.
L'ensemble $\{1, \{1\}\}$ n'est pas égal à $\{1\}$. Son élément $\{1\}$ est un ensemble à un élément, donc ce n'est pas le nombre $1$, qui est le seul élément de $\{1\}$ : ainsi $\{1\} \in \{1, \{1\}\}$ alors que $\{1\} \notin \{1\}$. Deux objets différents sont listés dans $\{1, \{1\}\}$ : il a deux éléments.

Définition — Ensemble vide

Il existe un unique ensemble sans élément, appelé l'ensemble vide et noté $\emptyset$ (ou $\{\}$). Formellement : $$ \forall x, \ x \notin \emptyset. $$

Exemple — Vide ou non vide

Le carré d'un réel est positif, donc aucun réel $x$ ne vérifie $x^2 = -1$ : $$ \{x \in \mathbb{R} \mid x^2 = -1\} = \emptyset. $$ La même condition, lue dans $\mathbb{C}$, donne un ensemble non vide : pour tout $z \in \mathbb{C}$, $$ \begin{aligned} z^2 = -1 &\iff z^2 = i^2 && \text{($i^2 = -1$)} \\ &\iff z^2 - i^2 = 0 && \text{(en soustrayant $i^2$)} \\ &\iff (z - i)(z + i) = 0 && \text{(factorisation)} \\ &\iff (z = i \text{ ou } z = -i), \end{aligned} $$ la dernière équivalence parce qu'un produit de complexes est nul si et seulement si l'un de ses facteurs est nul. Donc $\{z \in \mathbb{C} \mid z^2 = -1\} = \{i, -i\}$ : un ensemble défini par une condition dépend de l'ensemble dans lequel on lit la condition.
Les ensembles $\emptyset$ et $\{\emptyset\}$ ne sont pas égaux : $\emptyset$ n'a aucun élément, alors que $\{\emptyset\}$ en a un, l'ensemble vide lui-même. Ainsi $\emptyset \in \{\emptyset\}$, alors que $\emptyset \notin \emptyset$.

Compétences à pratiquer

Compter les éléments distincts d'un ensemble ★
Décider l'appartenance à un ensemble défini par une condition ★
Décider si deux ensembles sont égaux ★

III.2 Décrire un ensemble

Une liste, une condition, un paramètre

Un ensemble se décrit de trois façons. En extension, on liste ses éléments : $\{1, 2, 3\}$, ce qui ne convient qu'à un ensemble fini. En compréhension, une condition sélectionne des éléments dans un ensemble déjà connu : $\{x \in \mathbb{R} \mid x^2 \le 1\}$. Par un paramètre, l'ensemble est formé des valeurs d'une expression quand un paramètre parcourt un ensemble : $\{2k \mid k \in \mathbb{Z}\}$ est l'ensemble des entiers pairs. La troisième description cache un quantificateur : y appartenir, c'est être l'une des valeurs, c'est-à-dire qu'il existe un paramètre qui la produit.

Signaler une erreur

Définition — Extension, compréhension

Extension. Pour des objets $a_1, \dots, a_n$, l'ensemble $\{a_1, \dots, a_n\}$ est l'ensemble dont les éléments sont exactement $a_1, \dots, a_n$. Un ensemble $\{a\}$ est un singleton ; un ensemble $\{a, b\}$ avec $a \ne b$ est une paire.
Compréhension. Pour un ensemble $E$ et un prédicat $P(x)$, l'ensemble $\{x \in E \mid P(x)\}$ est l'ensemble des éléments $x$ de $E$ pour lesquels $P(x)$ est vraie. La condition sélectionne toujours des éléments d'un ensemble $E$ donné à l'avance.
Paramètre. Pour un ensemble $I$ et une expression $e(k)$ définie pour tout $k \in I$, l'ensemble $\{e(k) \mid k \in I\}$ est l'ensemble des valeurs de $e(k)$ quand $k$ parcourt $I$ : ses éléments sont les objets $y$ pour lesquels il existe $k \in I$ tel que $y = e(k)$. Plusieurs paramètres sont permis, comme dans $\{a^2 + b^2 \mid a, b \in \mathbb{N}\}$.

Exemple — Un ensemble, trois descriptions

Les carrés des cinq premiers entiers strictement positifs forment un ensemble qui a trois descriptions :

en extension, $\{1, 4, 9, 16, 25\}$ ;
par un paramètre, $\{k^2 \mid k \in \{1, 2, 3, 4, 5\}\}$ ;
en compréhension, $\{n \in \mathbb{N}^* \mid \sqrt{n} \in \mathbb{N} \text{ et } n \le 25\}$.

Les trois ensembles sont égaux : un entier $n \ge 1$ a une racine carrée entière exactement lorsque $n = k^2$ avec $k \in \mathbb{N}^*$, et alors $k^2 \le 25$ signifie $k \le 5$. L'extension montre les valeurs, le paramètre la règle qui les produit, la compréhension la propriété qui les caractérise.

Méthode — Traduire une appartenance

Pour décider si un objet appartient à un ensemble, traduire l'appartenance en un énoncé, puis démontrer ou réfuter cet énoncé :

Condition. Pour un ensemble $\{x \in E \mid P(x)\}$ et un objet $a$ : $a \in \{x \in E \mid P(x)\} \iff (a \in E \text{ et } P(a))$. La lettre $x$ est une variable muette : l'objet testé reçoit un autre nom ; c'est le dépliage déjà employé dans la Méthode « Démontrer une inclusion ».
Paramètre. Pour un ensemble $\{e(k) \mid k \in I\}$ et un objet $y$ : $y \in \{e(k) \mid k \in I\} \iff \exists k \in I, \ y = e(k)$. Pour démontrer l'appartenance, exhiber un $k$, comme dans la Méthode « Démontrer une proposition existentielle » ; pour la réfuter, démontrer la négation $\forall k \in I, \ y \ne e(k)$ : aucun $k$ ne convient.

Par exemple, $10 \in \{a^2 + b^2 \mid a, b \in \mathbb{N}\}$, avec les témoins $a = 1$ et $b = 3$ : $1^2 + 3^2 = 10$. En revanche, $7 \notin \{a^2 + b^2 \mid a, b \in \mathbb{N}\}$ : on démontre la négation $\forall a, b \in \mathbb{N}, \ a^2 + b^2 \ne 7$. Soient $a, b \in \mathbb{N}$. Si $a \ge 3$, alors $a^2 + b^2 \ge 9 > 7$, et de même si $b \ge 3$. Sinon $a, b \in \{0, 1, 2\}$, donc $a^2$ et $b^2$ sont dans $\{0, 1, 4\}$, et les sommes possibles sont $0$, $1$, $2$, $4$, $5$ et $8$. Dans tous les cas $a^2 + b^2 \ne 7$ : aucun choix de $a$ et $b$ ne produit $7$.

Définition — Intervalle d'entiers

Pour des entiers $a$ et $b$, l'intervalle d'entiers $\llbracket a, b \rrbracket$ est l'ensemble des entiers compris entre $a$ et $b$ au sens large : $$ \llbracket a, b \rrbracket = \{n \in \mathbb{Z} \mid a \le n \le b\} = [a, b] \cap \mathbb{Z}. $$ Il est vide lorsque $a > b$. Les variantes excluent une borne : $\llbracket a, b \llbracket \, = \{n \in \mathbb{Z} \mid a \le n < b\}$, $\rrbracket a, b \rrbracket = \{n \in \mathbb{Z} \mid a < n \le b\}$ et $\rrbracket a, b \llbracket \, = \{n \in \mathbb{Z} \mid a < n < b\}$.

Piège — un intervalle d'entiers n'est pas un intervalle de réels

$\llbracket a, b \rrbracket$ ne contient que des entiers. L'intervalle de réels $[0, 3]$ contient $\sqrt{2}$, $\tfrac{1}{2}$ et une infinité d'autres nombres, alors que $\llbracket 0, 3 \rrbracket = \{0, 1, 2, 3\}$ a quatre éléments. Pour des entiers $a \le b$, $\llbracket a, b \rrbracket$ a $b - a + 1$ éléments, comme on l'a compté dans le chapitre Dénombrement, et non $b - a$ : de $3$ à $7$, il y a cinq entiers, $3$, $4$, $5$, $6$ et $7$.

Signaler une erreur

Exemple — Cinq intervalles d'entiers

On liste les entiers compris entre les bornes : $$ \llbracket 0, 3 \rrbracket = \{0, 1, 2, 3\}, \qquad \llbracket -2, 1 \rrbracket = \{-2, -1, 0, 1\}, \qquad \llbracket 5, 5 \rrbracket = \{5\}, \qquad \llbracket 1, 4 \llbracket \, = \{1, 2, 3\}. $$ Et $\llbracket 7, 4 \rrbracket = \emptyset$ : aucun entier $n$ ne vérifie $7 \le n \le 4$. De même, $\llbracket 0, 3 \rrbracket = [0, 3] \cap \mathbb{Z}$, puisque les entiers de l'intervalle de réels $[0, 3]$ sont $0$, $1$, $2$ et $3$.

Compétences à pratiquer

Compter les éléments d'un ensemble défini par une condition ★
Écrire un ensemble en extension ★
Écrire un ensemble par une condition ou un paramètre ★
Compter les entiers qui vérifient une condition ★★
Déplier un ensemble décrit par un paramètre ★★

III.3 Inclusion

Deux façons de se rapporter

Deux ensembles peuvent être égaux, ou l'un peut être contenu dans l'autre : tout élément du premier est élément du second. Cette seconde relation, l'inclusion, est celle que l'on démontre le plus souvent, parce qu'une égalité d'ensembles se démontre par deux inclusions. Une inclusion est une implication entre appartenances sous un quantificateur universel : elle se démontre avec un élément générique.

Signaler une erreur

Définition — Inclusion, sous-ensemble

Soient $E$ et $F$ deux ensembles. $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 \iff \forall x, \ (x \in E \Rightarrow x \in F). $$ On dit aussi que $E$ est un sous-ensemble, ou une partie, de $F$, et que $F$ contient $E$. Cette inclusion est prise au sens large — c'est le $E \subseteq F$ du chapitre Théorie des ensembles — donc $E \subset E$, tout élément de $E$ étant élément de $E$. Sa négation, notée $E \not\subset F$, signifie $\exists x \in E, \ x \notin F$, par les Propositions « Négation des quantificateurs » et « Négation d'une implication ». L'inclusion est stricte, et l'on note $E \subsetneq F$, lorsque $E \subset F$ et $E \ne F$.

Exemple — La chaîne des ensembles de nombres

Les ensembles de nombres s'emboîtent, et chaque inclusion est stricte : $$ \mathbb{N} \subsetneq \mathbb{Z} \subsetneq \mathbb{D} \subsetneq \mathbb{Q} \subsetneq \mathbb{R} \subsetneq \mathbb{C}. $$ Chaque inclusion est vraie parce que tout entier naturel est un entier relatif, tout entier $n = \frac{n}{10^0}$ est un nombre décimal, tout décimal $\frac{k}{10^p}$ est un rationnel, tout rationnel est réel, et tout réel $x = x + 0i$ est complexe. Chaque inclusion est stricte à cause d'un élément du plus grand ensemble situé hors du plus petit — un témoin :

$-1 \in \mathbb{Z}$ et $-1 \notin \mathbb{N}$ ;
$\tfrac{1}{2} = \tfrac{5}{10} \in \mathbb{D}$ et $\tfrac{1}{2} \notin \mathbb{Z}$, puisque $0 < \tfrac{1}{2} < 1$ ;
$\tfrac{1}{3} \in \mathbb{Q}$ et $\tfrac{1}{3} \notin \mathbb{D}$ : une égalité $\tfrac{1}{3} = \tfrac{k}{10^p}$ avec $k \in \mathbb{Z}$ et $p \in \mathbb{N}$ donnerait $10^p = 3k$, alors que $10^p$ n'est pas multiple de $3$, la somme de ses chiffres valant $1$ ;
$\sqrt{2} \in \mathbb{R}$ et $\sqrt{2} \notin \mathbb{Q}$, puisque $\sqrt{2}$ est irrationnel ;
$i \in \mathbb{C}$ et $i \notin \mathbb{R}$, puisque $i^2 = -1$ alors que le carré d'un réel est positif.

Un témoin démontre $E \ne F$ : il est dans $F$ et pas dans $E$, donc $E$ et $F$ n'ont pas les mêmes éléments. Sur la figure, chaque ensemble est un rectangle, et chaque couronne entre deux rectangles contient des témoins d'une inclusion stricte.

L'appartenance n'est pas l'inclusion

$\in$ relie un élément à un ensemble ; $\subset$ relie un ensemble à un ensemble. L'entier $-1$ est un élément de $\mathbb{Z}$, $-1 \in \mathbb{Z}$, alors que le singleton $\{-1\}$ en est une partie, $\{-1\} \subset \mathbb{Z}$ ; l'écriture $-1 \subset \mathbb{Z}$ n'a pas de sens, $-1$ n'étant pas un ensemble, et $\{-1\} \in \mathbb{Z}$ est fausse, les éléments de $\mathbb{Z}$ étant des nombres. Pour un objet $x$ et un ensemble $E$, $x \in E \iff \{x\} \subset E$, puisque le seul élément de $\{x\}$ est $x$. Quand les éléments sont eux-mêmes des ensembles, les deux relations peuvent être vraies à la fois : dans $F = \{1, \{1\}\}$, l'ensemble $\{1\}$ est un élément, $\{1\} \in F$, et aussi une partie, $\{1\} \subset F$, puisque son seul élément $1$ appartient à $F$.

Signaler une erreur

Méthode — Démontrer une inclusion

Pour démontrer $A \subset B$ :

Soit $x \in A$.
$\vdots$ $\quad$ (déduire $x \in B$ de $x \in A$, en dépliant les définitions)
Donc $x \in B$. Comme $x$ est quelconque dans $A$, $A \subset B$.

Quand $A$ est défini par une propriété, $A = \{x \in E \mid P(x)\}$, l'hypothèse « $x \in A$ » se déplie en « $x \in E$ et $P(x)$ » ; quand $P$ est existentielle, elle fournit un témoin.

Proposition — Égalité par double inclusion

Pour tous ensembles $E$ et $F$ : $$ E = F \iff (E \subset F) \wedge (F \subset E). $$ Deux ensembles sont égaux lorsque chacun est inclus dans l'autre.

Preuve

Soient $E$ et $F$ deux ensembles. $$ \begin{aligned} E = F &\iff \forall x, \ (x \in E \iff x \in F) && \text{(définition de l'égalité)} \\ &\iff \forall x, \ \big((x \in E \Rightarrow x \in F) \wedge (x \in F \Rightarrow x \in E)\big) && \text{(équivalence et double implication, sous $\forall$)} \\ &\iff \big(\forall x, \ (x \in E \Rightarrow x \in F)\big) \wedge \big(\forall x, \ (x \in F \Rightarrow x \in E)\big) && \text{(« pour tout » et « et »)} \\ &\iff (E \subset F) \wedge (F \subset E). \end{aligned} $$ La dernière équivalence est la définition de l'inclusion, deux fois ; la troisième est la loi de la Proposition « Quantificateurs et connecteurs » selon laquelle « pour tout » se distribue sur « et ».
Seconde démonstration : par les deux implications. Supposons $E = F$. Tout $x \in E$ vérifie $x \in E \iff x \in F$, donc $x \in F$ : ainsi $E \subset F$, et de même $F \subset E$. Réciproquement, supposons $E \subset F$ et $F \subset E$, et soit $x$ un objet. Si $x \in E$, alors $x \in F$, puisque $E \subset F$ ; si $x \in F$, alors $x \in E$, puisque $F \subset E$. Donc $x \in E \iff x \in F$ ; l'objet $x$ étant quelconque, $E = F$.

Méthode — Démontrer une égalité d'ensembles

Deux approches :

Par double inclusion. Démontrer $A \subset B$ et $B \subset A$, chacune par la Méthode « Démontrer une inclusion ».
Par une chaîne d'équivalences. Pour $x$ dans un ensemble qui contient $A$ et $B$, démontrer $x \in A \iff \dots \iff x \in B$, chaque étape justifiée.

La chaîne est plus courte quand chaque étape réécrit une définition ; la double inclusion s'impose quand les deux sens ont des démonstrations différentes.

Proposition — Transitivité de l'inclusion

Pour tous ensembles $A$, $B$, $C$ : si $A \subset B$ et $B \subset C$, alors $A \subset C$. Deux inclusions s'enchaînent en une seule.

Preuve

Soient $A$, $B$, $C$ des ensembles tels que $A \subset B$ et $B \subset C$. On applique la Méthode « Démontrer une inclusion ». Soit $x \in A$. Comme $A \subset B$, $x \in B$ ; comme $B \subset C$, $x \in C$. Comme $x$ est quelconque dans $A$, $A \subset C$.
Seconde démonstration : la transitivité de l'implication, sous le quantificateur. Par définition de l'inclusion, les hypothèses s'écrivent $\forall x, \ (x \in A \Rightarrow x \in B)$ et $\forall x, \ (x \in B \Rightarrow x \in C)$. Soit $x$ un objet : les implications $x \in A \Rightarrow x \in B$ et $x \in B \Rightarrow x \in C$ sont toutes deux vraies. Par la Proposition « Transitivité de l'implication », appliquée aux propositions $x \in A$, $x \in B$ et $x \in C$, l'implication $x \in A \Rightarrow x \in C$ est vraie. L'objet $x$ étant quelconque, $\forall x, \ (x \in A \Rightarrow x \in C)$, c'est-à-dire $A \subset C$.

Proposition — L'ensemble vide est inclus dans tout ensemble

Pour tout ensemble $E$ : $$ \emptyset \subset E. $$

Preuve

Soit $E$ un ensemble. Il faut démontrer $\forall x, \ (x \in \emptyset \Rightarrow x \in E)$. Soit $x$ un objet. Par la Définition « Ensemble vide », $x \in \emptyset$ est fausse, et une implication dont l'hypothèse est fausse est vraie (Définition « Implication ») : $x \in \emptyset \Rightarrow x \in E$ est vraie. L'objet $x$ étant quelconque, $\emptyset \subset E$. C'est la convention de l'hypothèse fausse du Texte « Quantificateurs sur l'ensemble vide » : tout élément de $\emptyset$ appartient à $E$, puisqu'il n'y a rien à vérifier.
Seconde démonstration : par l'absurde. Supposons par l'absurde que $\emptyset \not\subset E$. Par la négation de l'inclusion, il existe $x \in \emptyset$ tel que $x \notin E$ ; en particulier, un objet appartient à $\emptyset$, ce qui contredit la Définition « Ensemble vide ». Contradiction ! Donc l'hypothèse est fausse, et $\emptyset \subset E$.
Les deux démonstrations n'utilisent que l'absence d'éléments. Ainsi deux ensembles $V$ et $W$ sans élément vérifient $V \subset W$ et $W \subset V$, donc $V = W$ par la Proposition « Égalité par double inclusion » : cela justifie l'unicité affirmée dans la Définition « Ensemble vide ».

Exemple — Un ensemble donné par une équation

Démontrer que $\{x \in \mathbb{R} \mid x^2 = x\} = \{0, 1\}$.

Correction

Soit $A = \{x \in \mathbb{R} \mid x^2 = x\}$. Chaque étape du calcul ci-dessous est une équivalence, donc une chaîne d'équivalences démontre les deux inclusions à la fois : pour tout $x \in \mathbb{R}$, $$ \begin{aligned} x \in A &\iff x^2 = x && \text{(définition de $A$, $x \in \mathbb{R}$)} \\ &\iff x^2 - x = 0 && \text{(en soustrayant $x$)} \\ &\iff x(x - 1) = 0 && \text{(factorisation)} \\ &\iff (x = 0 \text{ ou } x = 1), \end{aligned} $$ la dernière étape parce qu'un produit est nul si et seulement si l'un de ses facteurs est nul. Ainsi $x \in A \iff x \in \{0, 1\}$ pour tout $x \in \mathbb{R}$, et les deux ensembles sont des parties de $\mathbb{R}$ : ils sont égaux.
Seconde méthode : par double inclusion. Quand un sens demande un argument propre, une égalité se démontre par deux inclusions ; ici elles demandent deux arguments différents — résoudre l'équation, puis vérifier deux valeurs.
($\subset$) Soit $x \in A$ : $x \in \mathbb{R}$ et $x^2 = x$. Alors $$ \begin{aligned} x(x - 1) &= x^2 - x && \text{(développement)} \\ &= 0, \end{aligned} $$ la dernière égalité par l'hypothèse $x^2 = x$. Un produit de réels n'est nul que si l'un de ses facteurs est nul, donc $x = 0$ ou $x = 1$, c'est-à-dire $x \in \{0, 1\}$. Comme $x$ est quelconque dans $A$, $A \subset \{0, 1\}$.
($\supset$) Soit $x \in \{0, 1\}$, c'est-à-dire $x = 0$ ou $x = 1$. Si $x = 0$, alors $x^2 = 0 = x$ ; si $x = 1$, alors $x^2 = 1 = x$. Dans les deux cas, $x$ est un réel tel que $x^2 = x$, donc $x \in A$. Ainsi $\{0, 1\} \subset A$.
Par la Proposition « Égalité par double inclusion », $A = \{0, 1\}$.

Compétences à pratiquer

Choisir entre $\in$ et $\subset$ ★
Décider une inclusion ★
Démontrer une inclusion ou une égalité d'ensembles ★★

III.4 Ensemble des parties

Un niveau au-dessus

Les parties d'un ensemble $E$ peuvent elles-mêmes être rassemblées en un ensemble, $\mathcal{P}(E)$, dont les éléments sont des ensembles : un ensemble $A$ est un élément de $\mathcal{P}(E)$ exactement lorsqu'il est une partie de $E$. Ce changement de niveau est le point délicat : $\{1\}$ est une partie de $\{1, 2\}$ et un élément de $\mathcal{P}(\{1, 2\})$, alors que $1$ est un élément de $\{1, 2\}$ et pas un élément de $\mathcal{P}(\{1, 2\})$, dont les éléments sont tous des ensembles.

Signaler une erreur

Définition — Ensemble des parties

Pour tout ensemble $E$, l'ensemble des parties de $E$ est l'ensemble de tous les sous-ensembles de $E$ : $$ \mathcal{P}(E) = \{ A \ \mid \ A \subset E \}. $$ Pour tout ensemble $A$ : $$ A \in \mathcal{P}(E) \ \iff \ A \subset E. $$

Exemple — Deux parties que tout ensemble possède

Pour tout ensemble $E$, l'ensemble vide et $E$ lui-même sont des éléments de $\mathcal{P}(E)$ : $$ \emptyset \in \mathcal{P}(E) \qquad \text{et} \qquad E \in \mathcal{P}(E). $$ Le premier parce que $\emptyset \subset E$, par la Proposition « L'ensemble vide est inclus dans tout ensemble » ; le second parce que $E \subset E$, tout élément de $E$ étant élément de $E$. Ainsi $\mathcal{P}(E)$ n'est jamais vide : même $\mathcal{P}(\emptyset) = \{\emptyset\}$ a un élément, puisqu'une partie $A$ de $\emptyset$ vérifie $A \subset \emptyset$, et $\emptyset \subset A$ par la même Proposition : donc $A = \emptyset$, par la Proposition « Égalité par double inclusion ».

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

Pour $E = \{0, 1, 2\}$, les parties de $E$, classées selon leur nombre d'éléments, sont : $\emptyset$ ; puis $\{0\}$, $\{1\}$, $\{2\}$ ; puis $\{0, 1\}$, $\{0, 2\}$, $\{1, 2\}$ ; et enfin $\{0, 1, 2\}$. Donc $$ \mathcal{P}(E) = \big\{\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}\big\}. $$ Il a $1 + 3 + 3 + 1 = 8 = 2^3$ éléments, comme le prévoit le chapitre Dénombrement : un ensemble à $n$ éléments a $2^n$ parties.

Méthode — Lister les parties d'un ensemble fini

Pour lister les parties d'un ensemble fini $E$ à $n$ éléments, deux procédés :

Par taille. Lister la partie à $0$ élément, $\emptyset$, puis les parties à $1$ élément, les singletons, puis celles à $2$ éléments, et ainsi de suite jusqu'à $E$ lui-même.
Élément par élément. Décider pour chaque élément, l'un après l'autre, s'il est dans la partie ou hors d'elle, comme dans un arbre : chaque chemin de l'arbre donne une partie, et deux chemins différents donnent deux parties différentes.

Contrôler le compte : un ensemble à $n$ éléments a $2^n$ parties, par le chapitre Dénombrement. Pour $E = \{a, b\}$ avec $a \ne b$, élément par élément : $a$ dehors et $b$ dehors donnent $\emptyset$ ; $a$ dehors et $b$ dedans donnent $\{b\}$ ; $a$ dedans et $b$ dehors donnent $\{a\}$ ; $a$ dedans et $b$ dedans donnent $\{a, b\}$ — quatre parties, et $2^2 = 4$.

Exemple — Huit parties rangées par inclusion

Pour $E = \{a, b, c\}$ avec $a, b, c$ deux à deux distincts, les $2^3 = 8$ parties de $E$ sont rangées par taille, de $\emptyset$ en bas jusqu'à $E$ en haut. Un segment relie une partie $X$ à une partie $Y$ dessinée au-dessus lorsque $X \subset Y$ et que $Y$ a exactement un élément de plus que $X$ ; les inclusions entre parties de $E$ se lisent en suivant les segments vers le haut.

Deux parties d'une même ligne ne sont jamais incluses l'une dans l'autre : $\{a\} \not\subset \{b\}$ et $\{a, b\} \not\subset \{b, c\}$. L'inclusion ne compare pas toutes les parties de $E$ ; par exemple, $\{a\} \not\subset \{b, c\}$ et $\{b, c\} \not\subset \{a\}$.

Compétences à pratiquer

Compter des parties ★
Lister les parties d'un ensemble fini ★
Distinguer un élément et une partie de $\mathcal{P}(E)$ ★
Démontrer une propriété des ensembles de parties ★★

IV Opérations sur les ensembles

IV.1 Réunion et intersection

De nouveaux ensembles à partir d'ensembles donnés

Réunion, intersection, différence et complémentaire fabriquent de nouveaux ensembles à partir d'ensembles donnés. Chacune de ces opérations est un connecteur du chapitre Logique lu sur l'appartenance, et il en va de même de chaque relation entre ensembles : le Texte « Des connecteurs aux opérations » présente ce dictionnaire. Par conséquent, chaque loi des opérations — commutativité, associativité, distributivité, lois de De Morgan — est une loi de la logique lue sur l'appartenance. Chaque loi est démontrée une fois, en revenant aux éléments ; elle devient ensuite une règle de calcul sur les ensembles, employée sans revenir aux éléments.

Signaler une erreur

Des connecteurs aux opérations

Dans tout le tableau, $A$ et $B$ sont des parties d'un ensemble ambiant $E$, dessiné comme un rectangle, et $x$ est un objet. La première colonne donne une notation du langage des ensembles ; la deuxième, ce qu'elle dit dans le langage du chapitre Logique — pour une opération, la condition pour que $x$ appartienne à l'ensemble, et pour une relation, l'énoncé qu'elle abrège ; la troisième, le diagramme de Venn du chapitre Théorie des ensembles.

Ensembles	Logique	Diagramme de Venn
$x \in A \cap B$	$x \in A \wedge x \in B$
$x \in A \cup B$	$x \in A \vee x \in B$
$x \in \overline{A}$	$x \in E \wedge \neg(x \in A)$
$x \in A \setminus B$	$x \in A \wedge \neg(x \in B)$
$A \subset B$	$\forall x, \ (x \in A \Rightarrow x \in B)$
$A = B$	$\forall x, \ (x \in A \iff x \in B)$	la même région
$A \cap B = \emptyset$	$\neg \exists x, \ (x \in A \wedge x \in B)$

Les diagrammes sont ceux du chapitre Théorie des ensembles ; la deuxième colonne est la nouvelle, et c'est elle qui démontre : une loi des ensembles se démontre en traduisant chaque membre en sa formule et en appliquant une loi de la logique.

Signaler une erreur

Deux connecteurs, deux opérations

La réunion de deux ensembles rassemble les éléments de l'un ou de l'autre ; l'intersection garde leurs éléments communs. Ce sont les connecteurs « ou » et « et » lus sur l'appartenance, et leurs lois — commutativité, associativité, distributivité — sont les lois de ces connecteurs. Deux autres faits organisent les calculs : la réunion de deux ensembles est le plus petit ensemble qui les contient tous les deux, et leur intersection le plus grand ensemble contenu dans les deux.

Signaler une erreur

Définition — Réunion et intersection

Soient $E$ un ensemble et $A$, $B$ deux parties de $E$.

La réunion de $A$ et $B$ est $A \cup B = \{x \in E \mid x \in A \text{ ou } x \in B\}$.
L'intersection de $A$ et $B$ est $A \cap B = \{x \in E \mid x \in A \text{ et } x \in B\}$.

Pour tout objet $x$, $$ x \in A \cup B \iff (x \in A \vee x \in B) \qquad \text{et} \qquad x \in A \cap B \iff (x \in A \wedge x \in B). $$ En effet, pour $x \notin E$, les deux membres de chaque équivalence sont faux, puisque $A$ et $B$ sont des parties de $E$. Ainsi $A \cup B$ et $A \cap B$ ne dépendent pas de l'ensemble ambiant choisi.

Exemple — Réunions et intersections

$\{1, 2, 3\} \cup \{2, 4\} = \{1, 2, 3, 4\}$ et $\{1, 2, 3\} \cap \{2, 4\} = \{2\}$ : la réunion liste une fois les éléments de l'un ou l'autre ensemble, l'intersection garde l'élément commun aux deux.
Dans $\mathbb{R}$, $[0, 2] \cup [1, 3] = [0, 3]$ et $[0, 2] \cap [1, 3] = [1, 2]$ : un réel $x$ vérifie $0 \le x \le 2$ et $1 \le x \le 3$ exactement lorsque $1 \le x \le 2$, et il vérifie l'une des deux conditions exactement lorsque $0 \le x \le 3$, les deux intervalles se chevauchant.
$\mathbb{N} \cup \mathbb{Z} = \mathbb{Z}$ et $\mathbb{N} \cap \mathbb{Z} = \mathbb{N}$ : tout entier naturel étant un entier relatif, un objet est dans $\mathbb{N}$ ou dans $\mathbb{Z}$ exactement lorsqu'il est dans $\mathbb{Z}$, et il est à la fois dans $\mathbb{N}$ et dans $\mathbb{Z}$ exactement lorsqu'il est dans $\mathbb{N}$.

Proposition — Lois de la réunion et de l'intersection

Soient $E$ un ensemble et $A$, $B$, $C$ des parties de $E$.

Comparaison : $A \cap B \subset A \subset A \cup B$ et $A \cap B \subset B \subset A \cup B$.
Commutativité et associativité : $A \cup B = B \cup A$, $A \cap B = B \cap A$, $(A \cup B) \cup C = A \cup (B \cup C)$ et $(A \cap B) \cap C = A \cap (B \cap C)$.
Idempotence : $A \cup A = A$ et $A \cap A = A$.
Les parties $\emptyset$ et $E$ : $A \cup \emptyset = A$, $A \cap \emptyset = \emptyset$, $A \cup E = E$ et $A \cap E = A$.
Distributivité : $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ et $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

L'associativité permet d'écrire $A \cup B \cup C$ et $A \cap B \cap C$ sans parenthèses ; une expression qui mélange $\cup$ et $\cap$ garde ses parenthèses.

Preuve

Par la Définition « Réunion et intersection », pour tout objet $x$, l'appartenance $x \in A \cup B$ est la proposition « $x \in A$ ou $x \in B$ », et $x \in A \cap B$ est « $x \in A$ et $x \in B$ ». Chaque loi est donc une loi du chapitre Logique appliquée aux propositions $x \in A$, $x \in B$, $x \in C$ ; et deux ensembles qui ont les mêmes éléments sont égaux, par la Définition « Ensemble, élément, égalité ». Soit $x$ un objet.

Comparaison. Si $x \in A \cap B$, alors $x \in A$ et $x \in B$ : donc $A \cap B \subset A$ et $A \cap B \subset B$. Si $x \in A$, la disjonction « $x \in A$ ou $x \in B$ » a une partie vraie, donc elle est vraie, par la Définition « Disjonction » : $x \in A \cup B$, et $A \subset A \cup B$. Si $x \in B$, la même disjonction a son autre partie vraie, donc elle est vraie pour la même raison : $x \in A \cup B$, et $B \subset A \cup B$.
Commutativité et associativité. Pour l'intersection, d'abord l'associativité : $$ \begin{aligned} x \in (A \cap B) \cap C &\iff (x \in A \cap B) \wedge (x \in C) && \text{(définition de $\cap$)} \\ &\iff (x \in A \wedge x \in B) \wedge x \in C && \text{(définition de $\cap$)} \\ &\iff x \in A \wedge (x \in B \wedge x \in C) && \text{(associativité de $\wedge$)} \\ &\iff x \in A \wedge (x \in B \cap C) && \text{(définition de $\cap$)} \\ &\iff x \in A \cap (B \cap C), \end{aligned} $$ la dernière étape par la définition de $\cap$ ; puis la commutativité : $$ \begin{aligned} x \in A \cap B &\iff x \in A \wedge x \in B && \text{(définition de $\cap$)} \\ &\iff x \in B \wedge x \in A && \text{(commutativité de $\wedge$)} \\ &\iff x \in B \cap A, \end{aligned} $$ la dernière étape par la définition de $\cap$. Pour la réunion, l'associativité : $$ \begin{aligned} x \in (A \cup B) \cup C &\iff (x \in A \cup B) \vee (x \in C) && \text{(définition de $\cup$)} \\ &\iff (x \in A \vee x \in B) \vee x \in C && \text{(définition de $\cup$)} \\ &\iff x \in A \vee (x \in B \vee x \in C) && \text{(associativité de $\vee$)} \\ &\iff x \in A \vee (x \in B \cup C) && \text{(définition de $\cup$)} \\ &\iff x \in A \cup (B \cup C), \end{aligned} $$ la dernière étape par la définition de $\cup$ ; et la commutativité : $$ \begin{aligned} x \in A \cup B &\iff x \in A \vee x \in B && \text{(définition de $\cup$)} \\ &\iff x \in B \vee x \in A && \text{(commutativité de $\vee$)} \\ &\iff x \in B \cup A, \end{aligned} $$ la dernière étape par la définition de $\cup$. Les lois de connecteurs employées dans ces chaînes sont celles de la Proposition « Commutativité et associativité ».
Idempotence. Par la Définition « Conjonction », « $x \in A$ et $x \in A$ » a la valeur de vérité de $x \in A$, donc $x \in A \cap A \iff x \in A$. Par la Définition « Disjonction », « $x \in A$ ou $x \in A$ » a aussi la valeur de vérité de $x \in A$, donc $x \in A \cup A \iff x \in A$.
Les parties $\emptyset$ et $E$. La proposition $x \in \emptyset$ est fausse, par la Définition « Ensemble vide ». Donc « $x \in A$ ou $x \in \emptyset$ » a la valeur de vérité de $x \in A$, et « $x \in A$ et $x \in \emptyset$ » est fausse, comme $x \in \emptyset$ : $A \cup \emptyset = A$ et $A \cap \emptyset = \emptyset$. Comme $A \subset E$, l'implication $x \in A \Rightarrow x \in E$ est vraie. Si $x \in E$, alors « $x \in A$ ou $x \in E$ » est vraie ; si $x \notin E$, alors $x \notin A$, et elle est fausse : elle a la valeur de vérité de $x \in E$, donc $A \cup E = E$. Si $x \in A$, alors $x \in E$, et « $x \in A$ et $x \in E$ » est vraie ; si $x \notin A$, elle est fausse : elle a la valeur de vérité de $x \in A$, donc $A \cap E = A$.
Distributivité. Première identité : $$ \begin{aligned} x \in A \cap (B \cup C) &\iff x \in A \wedge (x \in B \cup C) && \text{(définition de $\cap$)} \\ &\iff x \in A \wedge (x \in B \vee x \in C) && \text{(définition de $\cup$)} \\ &\iff (x \in A \wedge x \in B) \vee (x \in A \wedge x \in C) && \text{(distributivité de $\wedge$ sur $\vee$)} \\ &\iff (x \in A \cap B) \vee (x \in A \cap C) && \text{(définition de $\cap$)} \\ &\iff x \in (A \cap B) \cup (A \cap C), \end{aligned} $$ la dernière étape par la définition de $\cup$. Seconde identité : $$ \begin{aligned} x \in A \cup (B \cap C) &\iff x \in A \vee (x \in B \cap C) && \text{(définition de $\cup$)} \\ &\iff x \in A \vee (x \in B \wedge x \in C) && \text{(définition de $\cap$)} \\ &\iff (x \in A \vee x \in B) \wedge (x \in A \vee x \in C) && \text{(distributivité de $\vee$ sur $\wedge$)} \\ &\iff (x \in A \cup B) \wedge (x \in A \cup C) && \text{(définition de $\cup$)} \\ &\iff x \in (A \cup B) \cap (A \cup C), \end{aligned} $$ la dernière étape par la définition de $\cap$.

Dans chaque cas, l'objet $x$ étant quelconque, les deux membres ont les mêmes éléments : ils sont égaux.
Les parenthèses. Prenons $E = \{1\}$, $A = \emptyset$ et $B = C = E$. D'une part, l'élément $1$ est dans $(A \cap B) \cup C$, puisqu'il est dans $C$ ; d'autre part, il n'est pas dans $A \cap (B \cup C)$, puisqu'il n'est pas dans $A$. Donc $(A \cap B) \cup C \ne A \cap (B \cup C)$ : les parenthèses d'une expression qui mélange $\cup$ et $\cap$ ne peuvent pas être supprimées. C'est la ligne du chapitre Logique où $p$ est fausse et où $q$, $r$ sont vraies.

Exemple — La distributivité en image

À gauche, la partie $B \cup C$ est légèrement grisée et son intersection avec $A$ fortement ; à droite, les deux parties $A \cap B$ et $A \cap C$ sont fortement grisées. Les régions fortement grisées coïncident. La figure illustre l'identité $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ sur une configuration de trois ensembles ; la chaîne de la Proposition « Lois de la réunion et de l'intersection » la démontre pour toutes.

Proposition — Réunion et intersection comme bornes

Soient $E$ un ensemble et $A$, $B$, $C$ des parties de $E$.

La réunion est la plus petite partie qui contient $A$ et $B$ : $A \cup B \subset C \iff (A \subset C) \wedge (B \subset C)$.
L'intersection est la plus grande partie contenue dans $A$ et $B$ : $C \subset A \cap B \iff (C \subset A) \wedge (C \subset B)$.
Conséquence : si $A \subset B$, alors $A \cup C \subset B \cup C$ et $A \cap C \subset B \cap C$.

Preuve

La réunion. $$ \begin{aligned} A \cup B \subset C &\iff \forall x, \ (x \in A \cup B \Rightarrow x \in C) && \text{(définition de $\subset$)} \\ &\iff \forall x, \ \big((x \in A \vee x \in B) \Rightarrow x \in C\big) && \text{(définition de $\cup$)} \\ &\iff \forall x, \ \big((x \in A \Rightarrow x \in C) \wedge (x \in B \Rightarrow x \in C)\big) && \text{(disjonction des cas, sous $\forall$)} \\ &\iff \big(\forall x, \ (x \in A \Rightarrow x \in C)\big) \wedge \big(\forall x, \ (x \in B \Rightarrow x \in C)\big) && \text{(« pour tout » et « et »)} \\ &\iff (A \subset C) \wedge (B \subset C). \end{aligned} $$ La dernière équivalence est la définition de l'inclusion, deux fois. La troisième applique la Proposition « Disjonction des cas » aux propositions $x \in A$, $x \in B$, $x \in C$, pour chaque $x$ ; la quatrième est la loi de la Proposition « Quantificateurs et connecteurs » selon laquelle « pour tout » se distribue sur « et ».
L'intersection. On démontre d'abord, pour toutes propositions $p$, $q$, $r$, la loi $\big(r \Rightarrow (p \wedge q)\big) \iff \big((r \Rightarrow p) \wedge (r \Rightarrow q)\big)$, par le sens. Le membre de gauche est faux exactement lorsque $r$ est vraie et $p \wedge q$ fausse, c'est-à-dire lorsque $r$ est vraie et que l'une des propositions $p$, $q$ est fausse. Le membre de droite est faux exactement lorsque l'une des deux implications est fausse, c'est-à-dire lorsque $r$ est vraie et $p$ fausse, ou $r$ vraie et $q$ fausse. Les deux membres sont faux sur les mêmes lignes : ils sont logiquement équivalents. Alors $$ \begin{aligned} C \subset A \cap B &\iff \forall x, \ (x \in C \Rightarrow x \in A \cap B) && \text{(définition de $\subset$)} \\ &\iff \forall x, \ \big(x \in C \Rightarrow (x \in A \wedge x \in B)\big) && \text{(définition de $\cap$)} \\ &\iff \forall x, \ \big((x \in C \Rightarrow x \in A) \wedge (x \in C \Rightarrow x \in B)\big) && \text{(la loi ci-dessus, sous $\forall$)} \\ &\iff \big(\forall x, \ (x \in C \Rightarrow x \in A)\big) \wedge \big(\forall x, \ (x \in C \Rightarrow x \in B)\big) && \text{(« pour tout » et « et »)} \\ &\iff (C \subset A) \wedge (C \subset B). \end{aligned} $$ La dernière équivalence est la définition de l'inclusion, deux fois ; la quatrième est la même loi de la Proposition « Quantificateurs et connecteurs ».
La conséquence. Supposons $A \subset B$. Comme $B \subset B \cup C$, par la Proposition « Lois de la réunion et de l'intersection », la Proposition « Transitivité de l'inclusion » donne $A \subset B \cup C$ ; et $C \subset B \cup C$. Le premier point, appliqué aux parties $A$, $C$ et $B \cup C$, donne $A \cup C \subset B \cup C$. De même, $A \cap C \subset A \subset B$ donne $A \cap C \subset B$, et $A \cap C \subset C$ ; le deuxième point donne $A \cap C \subset B \cap C$.
Seconde démonstration des deux premiers points : les deux implications, élément par élément. Supposons $A \cup B \subset C$. Soit $x \in A$ : alors $x \in A \cup B$, donc $x \in C$ ; ainsi $A \subset C$, et de même $B \subset C$. Réciproquement, supposons $A \subset C$ et $B \subset C$, et soit $x \in A \cup B$. On distingue deux cas, qui couvrent toutes les possibilités : si $x \in A$, alors $x \in C$, puisque $A \subset C$ ; si $x \in B$, alors $x \in C$, puisque $B \subset C$. Dans tous les cas $x \in C$ : $A \cup B \subset C$. Pour l'intersection, supposons $C \subset A \cap B$ : tout élément de $C$ est dans $A \cap B$, donc dans $A$ et dans $B$, d'où $C \subset A$ et $C \subset B$. Réciproquement, si $C \subset A$ et $C \subset B$, tout élément de $C$ est dans $A$ et dans $B$, c'est-à-dire dans $A \cap B$ : $C \subset A \cap B$.

Proposition — Inclusion caractérisée par réunion ou intersection

Soient $E$ un ensemble et $A$, $B$ des parties de $E$. Les trois énoncés $$ A \subset B, \qquad A \cup B = B, \qquad A \cap B = A $$ sont équivalents. Une inclusion s'écrit comme une égalité d'ensembles, ce qui la rend utilisable dans un calcul.

Preuve

Première démonstration : par les bornes. L'inclusion $B \subset A \cup B$ est toujours vraie, par la Proposition « Lois de la réunion et de l'intersection », donc $$ \begin{aligned} A \cup B = B &\iff (A \cup B \subset B) \wedge (B \subset A \cup B) && \text{(égalité par double inclusion)} \\ &\iff A \cup B \subset B && \text{($B \subset A \cup B$ est vraie)} \\ &\iff (A \subset B) \wedge (B \subset B) && \text{(réunion et intersection comme bornes)} \\ &\iff A \subset B, \end{aligned} $$ la dernière étape parce que $B \subset B$ est vraie. De même, $A \cap B \subset A$ est toujours vraie, donc $$ \begin{aligned} A \cap B = A &\iff (A \cap B \subset A) \wedge (A \subset A \cap B) && \text{(égalité par double inclusion)} \\ &\iff A \subset A \cap B && \text{($A \cap B \subset A$ est vraie)} \\ &\iff (A \subset A) \wedge (A \subset B) && \text{(réunion et intersection comme bornes)} \\ &\iff A \subset B, \end{aligned} $$ la dernière étape parce que $A \subset A$ est vraie. La deuxième et la dernière étape de chaque chaîne utilisent la Définition « Conjonction » : une conjonction dont une partie est vraie a la valeur de vérité de l'autre partie.
Seconde démonstration : un cycle de trois implications, élément par élément.

Supposons $A \subset B$. L'inclusion $B \subset A \cup B$ est vraie. Réciproquement, soit $x \in A \cup B$ : si $x \in A$, alors $x \in B$, puisque $A \subset B$ ; si $x \in B$, il n'y a rien à démontrer. Donc $A \cup B \subset B$, et $A \cup B = B$ par double inclusion.
Supposons $A \cup B = B$. L'inclusion $A \cap B \subset A$ est vraie. Réciproquement, soit $x \in A$ : alors $x \in A \cup B = B$, donc $x \in A$ et $x \in B$, c'est-à-dire $x \in A \cap B$. Donc $A \cap B = A$.
Supposons $A \cap B = A$. Soit $x \in A$ : alors $x \in A \cap B$, donc $x \in B$. Ainsi $A \subset B$.

Les trois implications forment un cycle, donc les trois énoncés sont équivalents.

Compétences à pratiquer

Lire la condition d'appartenance à un ensemble ★
Calculer réunions et intersections ★
Simplifier une expression avec les lois de $\cup$ et $\cap$ ★★
Démontrer une relation entre réunions et intersections ★★

IV.2 Différence et complémentaire

Ce qui n'est pas dans un ensemble

La différence $A \setminus B$ garde les éléments de $A$ qui ne sont pas dans $B$ ; le complémentaire d'une partie $A$ de $E$ est la différence $E \setminus A$, tout ce qui est dans $E$ hors de $A$. Toutes deux lisent « non » sur l'appartenance. Le chapitre Théorie des ensembles notait le complémentaire dans un ensemble universel $U$ par $\overline{A}$ ou $U \setminus A$. Ici l'ensemble ambiant s'appelle $E$, et le complémentaire se note $\overline{A}$, ou $\complement_E A$ lorsqu'il faut nommer $E$ : le complémentaire de $[0, 1]$ n'est pas le même dans $\mathbb{R}$ et dans $[0, 2]$.

Signaler une erreur

Définition — Différence, complémentaire

Soient $A$ et $B$ deux ensembles.

La différence $A$ privé de $B$ est $$ A \setminus B = \{ x \ \mid \ x \in A \ \wedge \ x \notin B \}. $$
Soit $E$ un ensemble et $A \subset E$. Le complémentaire de $A$ dans $E$ est l'ensemble $E \setminus A$, noté $\overline{A}$ ou $\complement_E A$ ou $A^c$ lorsque $E$ est clair par le contexte.

Exemple — Différences et complémentaires

$\{1, 2, 3, 4\} \setminus \{2, 4\} = \{1, 3\}$ : les éléments du premier ensemble qui ne sont pas dans le second.
$\mathbb{R} \setminus \mathbb{Q}$ est l'ensemble des nombres irrationnels ; par exemple $\sqrt{2} \in \mathbb{R} \setminus \mathbb{Q}$.
Dans $E = \mathbb{R}$, $\overline{[0, 1]} = \, ]-\infty, 0[ \, \cup \, ]1, +\infty[$ : un réel $x$ est hors de $[0, 1]$ exactement lorsque $x < 0$ ou $x > 1$, la négation de $0 \le x \le 1$ par les lois de De Morgan. Dans $E = [0, 2]$, en revanche, $\complement_E [0, 1] = \, ]1, 2]$.
Pour toute partie $A$ d'un ensemble $E$, $A \cap \overline{A} = \emptyset$ et $A \cup \overline{A} = E$ : aucun objet n'est à la fois dans $A$ et hors de $A$, par le principe de non-contradiction, et tout élément de $E$ est dans $A$ ou hors de $A$, par le principe du tiers exclu.

Proposition — Propriétés du complémentaire

Soient $E$ un ensemble et $A$, $B$ des parties de $E$ ; les complémentaires sont pris dans $E$.

Double complémentaire : $\overline{\overline{A}} = A$.
Les complémentaires de $\emptyset$ et de $E$ : $\complement_E \emptyset = E$ et $\complement_E E = \emptyset$.
Une partie et son complémentaire : $A \cap \overline{A} = \emptyset$ et $A \cup \overline{A} = E$.
La différence comme intersection : $A \setminus B = A \cap \overline{B}$.
Le complémentaire renverse l'inclusion : $A \subset B \iff \overline{B} \subset \overline{A}$.

Preuve

Tous les ensembles comparés sont des parties de $E$, donc, par la Méthode « Démontrer une égalité d'ensembles », il suffit de comparer les appartenances d'un élément de $E$ ; et pour $x \in E$, $x \in \overline{A}$ signifie $x \notin A$, par la Définition « Différence, complémentaire ». Soit $x \in E$.

Double complémentaire. $$ \begin{aligned} x \in \overline{\overline{A}} &\iff \neg\big(x \in \overline{A}\big) && \text{(définition du complémentaire)} \\ &\iff \neg\neg(x \in A) && \text{(définition du complémentaire)} \\ &\iff x \in A, \end{aligned} $$ la dernière étape par la Proposition « Double négation ».
Les complémentaires de $\emptyset$ et de $E$. La proposition $x \notin \emptyset$ est vraie, par la Définition « Ensemble vide », donc $x \in \complement_E \emptyset$ : tout élément de $E$ appartient à $\complement_E \emptyset$, et $\complement_E \emptyset = E$. Alors $$ \begin{aligned} \complement_E E &= \complement_E (\complement_E \emptyset) && \text{($\complement_E \emptyset = E$)} \\ &= \emptyset, \end{aligned} $$ la dernière étape par le double complémentaire, appliqué à la partie $\emptyset$ de $E$.
Une partie et son complémentaire. Pour l'intersection, $$ \begin{aligned} x \in A \cap \overline{A} &\iff x \in A \wedge x \in \overline{A} && \text{(définition de $\cap$)} \\ &\iff x \in A \wedge \neg(x \in A) && \text{(définition du complémentaire)} \\ &\iff x \in \emptyset, \end{aligned} $$ la dernière étape parce que les deux propositions sont fausses : la première par le principe de non-contradiction, la seconde par la Définition « Ensemble vide ». Pour la réunion, $$ \begin{aligned} x \in A \cup \overline{A} &\iff x \in A \vee x \in \overline{A} && \text{(définition de $\cup$)} \\ &\iff x \in A \vee \neg(x \in A) && \text{(définition du complémentaire)} \\ &\iff x \in E, \end{aligned} $$ la dernière étape parce que les deux propositions sont vraies : la première par le principe du tiers exclu, la seconde parce que $x \in E$.
La différence comme intersection. $$ \begin{aligned} x \in A \setminus B &\iff x \in A \wedge x \notin B && \text{(définition de la différence)} \\ &\iff x \in A \wedge x \in \overline{B} && \text{(définition du complémentaire)} \\ &\iff x \in A \cap \overline{B}, \end{aligned} $$ la dernière étape par la définition de $\cap$.
Le complémentaire renverse l'inclusion. Un objet hors de $E$ n'appartient ni à $A$ ni à $\overline{B}$, donc les inclusions de ces deux parties ne se vérifient que sur les éléments de $E$ : $$ \begin{aligned} A \subset B &\iff \forall x \in E, \ (x \in A \Rightarrow x \in B) && \text{(définition de $\subset$, $A \subset E$)} \\ &\iff \forall x \in E, \ (x \notin B \Rightarrow x \notin A) && \text{(équivalence avec la contraposée, sous $\forall$)} \\ &\iff \forall x \in E, \ \big(x \in \overline{B} \Rightarrow x \in \overline{A}\big) && \text{(définition du complémentaire)} \\ &\iff \overline{B} \subset \overline{A}, \end{aligned} $$ la dernière étape par la définition de $\subset$, $\overline{B}$ étant une partie de $E$.

Seconde démonstration du renversement : par l'absurde. Supposons $A \subset B$, et soit $x \in \overline{B}$ : $x \in E$ et $x \notin B$. Supposons par l'absurde que $x \notin \overline{A}$. Comme $x \in E$, cela signifie $x \in A$, et $A \subset B$ donne $x \in B$ — alors que $x \notin B$. Contradiction ! Donc $x \in \overline{A}$, et $\overline{B} \subset \overline{A}$. Réciproquement, si $\overline{B} \subset \overline{A}$, l'implication que l'on vient de démontrer, appliquée aux parties $\overline{B}$ et $\overline{A}$, donne $\overline{\overline{A}} \subset \overline{\overline{B}}$, c'est-à-dire $A \subset B$ par le double complémentaire.

Compétences à pratiquer

Calculer une différence ★
Calculer un complémentaire ★
Démontrer une identité avec différences et complémentaires ★★

IV.3 Lois de De Morgan

Le complémentaire échange réunion et intersection

Les lois de De Morgan du chapitre Logique disent que la négation échange « et » et « ou ». Lues sur l'appartenance, elles disent que le complémentaire échange intersection et réunion : être hors de $A \cup B$, c'est être hors de $A$ et hors de $B$. Avec ces lois, les lois de la réunion et de l'intersection et les propriétés du complémentaire, une identité entre ensembles se démontre par le calcul, une loi par ligne, comme une identité algébrique.

Signaler une erreur

Proposition — Lois de De Morgan pour deux ensembles

Soient $E$ un ensemble et $A$, $B$ des parties de $E$ ; les complémentaires sont pris dans $E$. Alors $$ \overline{A \cup B} = \overline{A} \cap \overline{B} \qquad \text{et} \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}. $$ Le complémentaire d'une réunion est l'intersection des complémentaires ; le complémentaire d'une intersection est la réunion des complémentaires.

Preuve

Première loi. Les deux membres sont des parties de $E$ ; soit $x \in E$. $$ \begin{aligned} x \in \overline{A \cup B} &\iff \neg(x \in A \cup B) && \text{(définition du complémentaire)} \\ &\iff \neg(x \in A \vee x \in B) && \text{(définition de $\cup$)} \\ &\iff \neg(x \in A) \wedge \neg(x \in B) && \text{(lois de De Morgan)} \\ &\iff x \in \overline{A} \wedge x \in \overline{B} && \text{(définition du complémentaire)} \\ &\iff x \in \overline{A} \cap \overline{B}, \end{aligned} $$ la dernière étape par la définition de $\cap$. C'est l'identité de l'Exemple « Loi de De Morgan pour deux ensembles » du chapitre Raisonner et rédiger, où elle illustre une Méthode ; elle est ici une loi, énoncée pour toutes les parties de $E$ et employée dans les calculs qui suivent.
Seconde loi, par dualité. La première loi, appliquée aux parties $\overline{A}$ et $\overline{B}$, donne $\overline{\overline{A} \cup \overline{B}} = \overline{\overline{A}} \cap \overline{\overline{B}}$. Alors $$ \begin{aligned} \overline{A \cap B} &= \overline{\overline{\overline{A}} \cap \overline{\overline{B}}} && \text{(double complémentaire, pour $A$ et $B$)} \\ &= \overline{\overline{\overline{A} \cup \overline{B}}} && \text{(première loi, pour $\overline{A}$ et $\overline{B}$)} \\ &= \overline{A} \cup \overline{B}, \end{aligned} $$ la dernière étape par le double complémentaire, pour la partie $\overline{A} \cup \overline{B}$.
Seconde démonstration de la seconde loi : la chaîne directe. Pour $x \in E$, $$ \begin{aligned} x \in \overline{A \cap B} &\iff \neg(x \in A \cap B) && \text{(définition du complémentaire)} \\ &\iff \neg(x \in A \wedge x \in B) && \text{(définition de $\cap$)} \\ &\iff \neg(x \in A) \vee \neg(x \in B) && \text{(lois de De Morgan)} \\ &\iff x \in \overline{A} \vee x \in \overline{B} && \text{(définition du complémentaire)} \\ &\iff x \in \overline{A} \cup \overline{B}, \end{aligned} $$ la dernière étape par la définition de $\cup$.

Exemple — De Morgan sur des intervalles

Dans $E = \mathbb{R}$, soient $A = \, ]-\infty, 0]$ et $B = [1, +\infty[$. D'une part, $A \cup B = \, ]-\infty, 0] \cup [1, +\infty[$, et un réel $x$ est hors de $A \cup B$ exactement lorsque $x > 0$ et $x < 1$ : $\overline{A \cup B} = \, ]0, 1[$. D'autre part, $\overline{A} = \, ]0, +\infty[$ et $\overline{B} = \, ]-\infty, 1[$, donc $\overline{A} \cap \overline{B} = \, ]0, 1[$. Les deux calculs donnent le même ensemble, comme le prévoit la première des lois de De Morgan pour deux ensembles. La seconde loi, avec $A \cap B = \emptyset$ — aucun réel n'est à la fois inférieur ou égal à $0$ et supérieur ou égal à $1$ —, donne $$ \begin{aligned} \overline{A} \cup \overline{B} &= \overline{A \cap B} && \text{(lois de De Morgan pour deux ensembles)} \\ &= \complement_{\mathbb{R}} \emptyset && \text{($A \cap B = \emptyset$)} \\ &= \mathbb{R}, \end{aligned} $$ la dernière étape par $\complement_E \emptyset = E$, le complémentaire de l'ensemble vide (Proposition « Propriétés du complémentaire »), ici avec $E = \mathbb{R}$ ; et en effet tout réel est strictement positif ou strictement inférieur à $1$.

Exemple — De Morgan en image

À gauche, le complémentaire de $A \cup B$ est grisé : les points de $E$ situés hors des deux disques. À droite, les points hors de $A$ ont une teinte et les points hors de $B$ l'autre ; les points à double teinte, hors des deux disques, forment l'intersection des deux complémentaires. Ce sont les points grisés à gauche : la première des lois de De Morgan pour deux ensembles, vue sur une configuration.

Méthode — Calculer sur les ensembles sans revenir aux éléments

Pour démontrer une identité entre parties d'un ensemble $E$, ou pour simplifier une expression :

écrire une chaîne alignée d'égalités qui s'ouvre sur un membre, une loi par ligne, nommée dans la colonne de droite — les lois de la réunion et de l'intersection, les propriétés du complémentaire, en particulier $A \setminus B = A \cap \overline{B}$, qui change toute différence en intersection, et les lois de De Morgan ; la loi de la dernière ligne est nommée dans la phrase qui suit la chaîne ;
faire entrer les complémentaires avec les lois de De Morgan et le double complémentaire, puis distribuer, et simplifier avec $A \cap \overline{A} = \emptyset$ et $A \cup \overline{A} = E$ (propriétés du complémentaire) et les lois des parties $\emptyset$ et $E$ ;
revenir aux éléments quand aucune loi ne s'applique directement : pour une inclusion qu'on n'a pas d'abord écrite comme une égalité par la Proposition « Inclusion caractérisée par réunion ou intersection », pour un ensemble défini par une condition, ou pour réfuter une identité, ce pour quoi un élément situé dans un membre et pas dans l'autre suffit.

Un calcul démontre l'identité pour toutes les parties à la fois ; un diagramme de Venn ne fait que l'illustrer.

Exemple — La différence d'une différence

Soient $E$ un ensemble et $A$, $B$, $C$ des parties de $E$. L'identité $(A \setminus B) \setminus C = A \setminus (B \cup C)$ se démontre par le calcul : $$ \begin{aligned} (A \setminus B) \setminus C &= (A \setminus B) \cap \overline{C} && \text{(différence comme intersection)} \\ &= (A \cap \overline{B}) \cap \overline{C} && \text{(différence comme intersection)} \\ &= A \cap (\overline{B} \cap \overline{C}) && \text{(associativité de $\cap$)} \\ &= A \cap \overline{B \cup C} && \text{(lois de De Morgan pour deux ensembles)} \\ &= A \setminus (B \cup C). \end{aligned} $$ La dernière égalité est la différence comme intersection, lue de droite à gauche. Retirer $B$, puis $C$, c'est retirer $B \cup C$ — et aucun élément n'a eu à être nommé.

Compétences à pratiquer

Reconnaître le complémentaire d'une réunion ou d'une intersection ★
Vérifier les lois de De Morgan sur un exemple ★
Simplifier une expression avec les lois de De Morgan ★★
Démontrer une identité par le calcul ensembliste ★★

V Ensembles disjoints et partitions

V.1 Ensembles disjoints

Découper en morceaux

Découper un problème en cas, c'est découper un ensemble en morceaux : les entiers en pairs et impairs, les réels en strictement négatifs, nul et strictement positifs. Pour que chaque cas soit traité une fois, les morceaux ne doivent pas se chevaucher : ils doivent être disjoints. Une partition découpe un ensemble en morceaux non vides qui ne se chevauchent pas et qui couvrent tout l'ensemble ; c'est le langage du raisonnement par disjonction des cas, et du dénombrement morceau par morceau.

Signaler une erreur

Définition — Ensembles disjoints, famille deux à deux disjointe

Soit $E$ un ensemble.

Deux parties $A$ et $B$ de $E$ sont disjointes lorsque $A \cap B = \emptyset$. Leur réunion se note alors aussi $A \sqcup B$ et s'appelle une réunion disjointe : $A \sqcup B$ est l'ensemble $A \cup B$, et la notation ajoute que $A$ et $B$ sont disjointes.
Une famille $(A_i)_{i \in I}$ de parties de $E$ est deux à deux disjointe lorsque deux ensembles de la famille d'indices distincts sont toujours disjoints : $$ \forall i, j \in I, \ \big(i \ne j \Rightarrow A_i \cap A_j = \emptyset\big). $$ Sa réunion se note alors aussi $\bigsqcup_{i \in I} A_i$.

Une famille deux à deux disjointe n'est pas la même chose qu'une famille d'intersection vide. Lorsque $I$ contient deux indices distincts $i$ et $j$, le fait que la famille soit deux à deux disjointe entraîne $\bigcap_{k \in I} A_k \subset A_i \cap A_j = \emptyset$ ; la réciproque est fausse.

Exemple — Intersection vide, morceaux qui se chevauchent

Dans $E = \{1, 2, 3\}$, les parties $A = \{1, 2\}$, $B = \{2, 3\}$ et $C = \{1, 3\}$ ont une intersection vide : $A \cap B = \{2\}$ et $2 \notin C$, donc $A \cap B \cap C = \emptyset$. Pourtant, deux quelconques d'entre elles se rencontrent : $A \cap B = \{2\}$, $B \cap C = \{3\}$ et $C \cap A = \{1\}$. La famille $(A, B, C)$ a une intersection vide et n'est pas deux à deux disjointe. Sur la figure, chaque ensemble est dessiné autour de ses deux éléments.

Toute réunion se récrit en réunion disjointe : pour toutes parties $A$ et $B$ d'un ensemble $E$, $A \cup B = A \sqcup (B \setminus A)$. Les deux ensembles sont disjoints, puisqu'un élément de $B \setminus A$ n'est pas dans $A$ ; et $$ \begin{aligned} A \cup (B \setminus A) &= A \cup (B \cap \overline{A}) && \text{(différence comme intersection)} \\ &= (A \cup B) \cap (A \cup \overline{A}) && \text{(distributivité de $\cup$ sur $\cap$)} \\ &= (A \cup B) \cap E && \text{($A \cup \overline{A} = E$, une partie et son complémentaire)} \\ &= A \cup B, \end{aligned} $$ la dernière égalité par les lois de la réunion et de l'intersection, $A \cup B$ étant une partie de $E$. Le dénombrement morceau par morceau repose sur cette écriture : pour des ensembles finis, $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \setminus A \rvert$.

Compétences à pratiquer

Décider si deux ensembles sont disjoints ★
Dénombrer une réunion par morceaux disjoints ★★

VI Produits cartésiens

VI.1 Couples et produits

L'ordre compte

Le chapitre Théorie des ensembles a introduit les couples $(a, b)$ et les $n$-uplets $(a_1, \dots, a_n)$, ainsi que le produit cartésien de deux ensembles. À la différence d'un ensemble, un $n$-uplet a un ordre — $(1, 2) \ne (2, 1)$ — et peut répéter une composante — $(1, 1)$ est un couple. Le produit de $n$ ensembles rassemble tous les $n$-uplets dont la $i$-ième composante est prise dans le $i$-ième ensemble : le plan $\mathbb{R}^2$, l'espace $\mathbb{R}^3$, les issues de $n$ tirages successifs.

Signaler une erreur

Définition — Produit cartésien

Soient $n \ge 1$ un entier et $E_1, \dots, E_n$ des ensembles.

Deux $n$-uplets sont égaux lorsque leurs composantes sont égales, rang par rang : $$ (x_1, \dots, x_n) = (y_1, \dots, y_n) \iff \forall i \in \llbracket 1, n \rrbracket, \ x_i = y_i. $$
Le produit cartésien de $E_1, \dots, E_n$ est l'ensemble des $n$-uplets dont la $i$-ième composante appartient à $E_i$ pour tout $i$ : $$ E_1 \times \dots \times E_n = \{(x_1, \dots, x_n) \mid \forall i \in \llbracket 1, n \rrbracket, \ x_i \in E_i\}. $$ Lorsque $E_1 = \dots = E_n = E$, le produit se note $E^n$. Pour $n = 2$, les éléments de $E \times F$ sont les couples $(x, y)$ tels que $x \in E$ et $y \in F$.

Un quantificateur sur un produit abrège plusieurs quantificateurs : « $\forall (x, y) \in E \times F, \ P(x, y)$ » abrège « $\forall x \in E, \ \forall y \in F, \ P(x, y)$ », et « $\exists (x, y) \in E \times F, \ P(x, y)$ » abrège « $\exists x \in E, \ \exists y \in F, \ P(x, y)$ ».

Exemple — Produits d'ensembles

Avec $a \ne b$, $\{1, 2, 3\} \times \{a, b\} = \{(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)\}$ : six couples, chaque élément du premier ensemble étant associé à chaque élément du second.
$\mathbb{R}^2 = \{(x, y) \mid x, y \in \mathbb{R}\}$ est l'ensemble des coordonnées des points d'un plan muni d'un repère, et $\mathbb{R}^3$ celui des points de l'espace.
Pour des ensembles finis $A$ et $B$, $\lvert A \times B \rvert = \lvert A \rvert \times \lvert B \rvert$, comme le chapitre Théorie des ensembles l'a montré avec un tableau de couples ; ici $3 \times 2 = 6$.

Exemple — Un produit en grille

Pour $A = \{1, 2, 3, 4\}$ et $B = \{1, 2, 3\}$, le produit $A \times B$ se dessine comme une grille : la première composante sur l'axe horizontal, la seconde sur l'axe vertical, un point pour chaque couple. La grille a $4$ colonnes de $3$ points, donc $\lvert A \times B \rvert = 4 \times 3 = 12$ ; les couples $(1, 2)$ et $(2, 1)$ sont deux points différents de la grille.

Piège — un n-uplet n'est pas un ensemble

Un $n$-uplet $(x_1, \dots, x_n)$ n'est pas l'ensemble $\{x_1, \dots, x_n\}$. Deux différences :

L'ordre. $(1, 2) \ne (2, 1)$, alors que $\{1, 2\} = \{2, 1\}$.
Les répétitions. $(1, 1, 2)$ est un $3$-uplet dont les deux premières composantes sont égales, alors que $\{1, 1, 2\} = \{1, 2\}$ a deux éléments.

Le produit fabrique des $n$-uplets, la réunion fabrique des ensembles. Écrire $\{x, y\}$ pour le couple $(x, y)$ perd l'ordre et, lorsque $x = y$, un élément.

Signaler une erreur

Compétences à pratiquer

Compter les éléments d'un produit ★
Lister les éléments d'un produit ★
Comparer $n$-uplets et ensembles ★

VII Quantificateurs

VII.1 Quantificateurs universel et existentiel

Des prédicats aux propositions

Un prédicat devient une proposition quand sa variable est fixée, ou quand sa variable est quantifiée : « pour tout $x$ de $E$, … », « il existe $x$ dans $E$ tel que … ». Les quantificateurs ont leurs propres lois : comment les nier, quand deux d'entre eux peuvent s'échanger, comment ils se combinent avec « et » et « ou ». Les définitions de l'analyse — une fonction bornée, une suite convergente, une fonction continue — sont des énoncés à plusieurs quantificateurs, et ces lois calculent leurs négations.

Signaler une erreur

Trois quantificateurs

Le quantificateur universel $\forall$ affirme que tout élément d'un ensemble vérifie un prédicat ; le quantificateur existentiel $\exists$, qu'au moins un élément le vérifie ; $\exists !$, qu'exactement un le vérifie. Une variable quantifiée ne désigne plus un objet particulier : l'énoncé n'en dépend pas, et la lettre pourrait être changée.

Signaler une erreur

Définition — Universel, existentiel, unicité

Soit $P(x)$ un prédicat d'une variable $x$.

$\forall x, \ P(x)$, lu « pour tout $x$, $P(x)$ », est la proposition qui est vraie lorsque tout objet $x$ vérifie $P$, et fausse lorsqu'au moins un objet ne le vérifie pas. Le symbole $\forall$ est le quantificateur universel.
$\exists x, \ P(x)$, lu « il existe $x$ tel que $P(x)$ », est la proposition qui est vraie lorsqu'au moins un objet vérifie $P$, et fausse lorsqu'aucun ne le vérifie. Le symbole $\exists$ est le quantificateur existentiel.

Pour un ensemble $E$, les quantificateurs bornés sont des abréviations : $\forall x \in E, \ P(x)$ abrège $\forall x, \ (x \in E \Rightarrow P(x))$, et $\exists x \in E, \ P(x)$ abrège $\exists x, \ (x \in E \wedge P(x))$. Un objet hors de $E$ rend vraie l'implication $x \in E \Rightarrow P(x)$, donc $\forall x \in E, \ P(x)$ est vraie exactement lorsque tout élément de $E$ vérifie $P$, et fausse lorsqu'au moins un élément de $E$ ne le vérifie pas ; et $\exists x \in E, \ P(x)$ est vraie exactement lorsqu'au moins un élément de $E$ vérifie $P$. Enfin, $\exists ! \, x \in E, \ P(x)$, lu « il existe un unique $x$ dans $E$ tel que $P(x)$ », abrège l'existence et « au plus un » : $$ \left(\exists x \in E, \ P(x)\right) \wedge \left(\forall x, x' \in E, \ (P(x) \wedge P(x')) \Rightarrow x = x'\right). $$ Les symboles $\forall$ et $\exists$ appartiennent aux formules ; ce ne sont pas des abréviations de mots : dans une phrase, on écrit « pour tout entier $n$ », jamais « $\forall$ entier $n$ ».

Définition — Variables libres et variables liées

Dans un énoncé, une occurrence d'une variable est liée lorsqu'elle se trouve dans la portée d'un quantificateur portant sur cette variable, ou d'une notation qui introduit sa propre variable, comme une somme $\sum_{k=1}^{n}$, une intégrale $\int_a^b f(t)\,\mathrm{d}t$ ou un ensemble $\{x \in E \mid \dots\}$ ; une occurrence qui n'est pas liée est libre. La portée d'un quantificateur va jusqu'à la fin de l'énoncé, ou jusqu'à la parenthèse qui renferme le quantificateur. Une même lettre peut avoir des occurrences libres et des occurrences liées : dans $(\forall x \in \mathbb{R}, \ x^2 \ge 0) \wedge (x > 0)$, le dernier $x$ est libre et les autres sont liés. Un énoncé ne dépend que de ses variables libres, celles qui ont une occurrence libre : c'est un prédicat de ses variables libres, et une proposition lorsqu'il n'en a aucune. Une variable liée est muette : les occurrences liées par un même quantificateur peuvent être renommées ensemble, avec une lettre qui n'est pas utilisée ailleurs dans l'énoncé, sans en changer le sens ; $\forall x \in \mathbb{R}, \ f(x) \ge 0$ et $\forall t \in \mathbb{R}, \ f(t) \ge 0$ disent tous deux « $f$ est positive ». Deux quantificateurs portant sur la même lettre, dans deux parties séparées d'un énoncé, lient deux variables différentes : dans $(\exists x \in \mathbb{N}, \ a = bx) \wedge (\exists x \in \mathbb{N}, \ b = ax)$, rien ne dit que les deux $x$ sont égaux, et l'énoncé s'écrit mieux $(\exists x \in \mathbb{N}, \ a = bx) \wedge (\exists y \in \mathbb{N}, \ b = ay)$.

Quantificateurs sur l'ensemble vide

Pour tout prédicat $P$, la proposition $\exists x \in \emptyset, \ P(x)$ est fausse : elle abrège $\exists x, \ (x \in \emptyset \wedge P(x))$, et $x \in \emptyset$ est fausse pour tout $x$. La proposition $\forall x \in \emptyset, \ P(x)$ est vraie : elle abrège $\forall x, \ (x \in \emptyset \Rightarrow P(x))$, une implication d'hypothèse fausse pour tout $x$. « Tout élément de l'ensemble vide est un entier strictement supérieur à $10$ et strictement inférieur à $5$ » est vraie : il n'y a rien à vérifier. C'est la convention de l'hypothèse fausse à l'œuvre ; c'est aussi pourquoi $\emptyset \subset E$ pour tout ensemble $E$.

Signaler une erreur

Exemple — Carrés de réels

Trois propositions vraies sur les carrés de réels :

$\forall x \in \mathbb{R}, \ x^2 \ge 0$ : tout réel a un carré positif.
$\exists x \in \mathbb{R}, \ x^2 = 2$ : au moins un réel a pour carré $2$ — en fait deux, $\sqrt{2}$ et $-\sqrt{2}$ ; donc $\exists ! \, x \in \mathbb{R}, \ x^2 = 2$ est fausse.
$\exists ! \, x \in \mathbb{R}_+, \ x^2 = 2$ : parmi les réels positifs, seul $\sqrt{2}$ a pour carré $2$.

L'ensemble fait partie de l'énoncé : remplacer $\mathbb{R}$ par $\mathbb{R}_+$ change un $\exists !$ faux en un $\exists !$ vrai.

Exemple — Quantificateurs implicites

La phrase « si $x > 2$, alors $x^2 > 4$ », énoncée comme une propriété des réels, porte un quantificateur universel non écrit : elle signifie $\forall x \in \mathbb{R}, \ (x > 2 \Rightarrow x^2 > 4)$. Dans un théorème, une phrase conditionnelle sur un objet est universelle : sa variable est quantifiée par « pour tout ».
Dans $\exists x \in \mathbb{R}, \ x^2 = m$, la variable $x$ est liée et $m$ est libre : c'est un prédicat de $m$, qui dit « l'équation $x^2 = m$ a une solution réelle ». Il est vrai pour $m \ge 0$, avec $x = \sqrt{m}$, et faux pour $m < 0$, un carré étant positif. La proposition $\forall m \in \mathbb{R}_+, \ \exists x \in \mathbb{R}, \ x^2 = m$ est vraie, et ne dépend plus de $m$.

Méthode — Écrire un énoncé avec des quantificateurs

Pour écrire une phrase comme un énoncé quantifié :

nommer les objets et les ensembles qu'ils parcourent ;
écrire les quantificateurs dans l'ordre des dépendances : un objet choisi après un autre peut en dépendre, jamais l'inverse ;
écrire le prédicat, avec ses connecteurs ;
relire l'énoncé en mots, et vérifier que chaque lettre est liée ou désigne un objet donné par la phrase.

Par exemple, « la fonction $f \colon \mathbb{R} \to \mathbb{R}$ admet un minimum » signifie qu'un réel $a$ vérifie $f(x) \ge f(a)$ pour tout réel $x$ : $$ \exists a \in \mathbb{R}, \ \forall x \in \mathbb{R}, \ f(x) \ge f(a). $$ Le point $a$ est choisi d'abord et ne dépend pas de $x$, donc $\exists a$ vient avant $\forall x$. Les lettres $a$ et $x$ sont liées : l'énoncé ne dépend que de $f$.

Compétences à pratiquer

Compter les éléments qui vérifient un énoncé quantifié ★
Repérer les variables libres et liées ★
Traduire un énoncé avec des quantificateurs ★
Traduire des propriétés de fonctions et de suites ★★

VII.2 Négation des quantificateurs

Nier est un calcul

Réfuter un énoncé, c'est démontrer sa négation, et la négation d'un énoncé quantifié se calcule, elle ne se devine pas. La Méthode « Nier un énoncé quantifié » du chapitre Raisonner et rédiger en donne la règle : échanger les quantificateurs, nier la propriété finale. La règle découle de la négation d'un seul quantificateur et d'une remarque : si $P(x) \iff Q(x)$ est vraie pour tout $x \in E$, les deux prédicats sont vérifiés par les mêmes éléments de $E$, donc $\forall x \in E, \ P(x)$ et $\forall x \in E, \ Q(x)$ ont la même valeur de vérité, de même que $\exists x \in E, \ P(x)$ et $\exists x \in E, \ Q(x)$. Une équivalence de prédicats passe sous un quantificateur.

Signaler une erreur

Proposition — Négation des quantificateurs

Pour tout ensemble $E$ et tout prédicat $P(x)$ sur $E$ : $$ \neg\left(\forall x \in E, \ P(x)\right) \iff \exists x \in E, \ \neg P(x) \qquad \text{et} \qquad \neg\left(\exists x \in E, \ P(x)\right) \iff \forall x \in E, \ \neg P(x). $$ La négation échange « pour tout » et « il existe », garde l'ensemble, et nie le prédicat.

Preuve

Première loi. Par la Définition « Universel, existentiel, unicité », $\forall x \in E, \ P(x)$ est fausse exactement lorsqu'au moins un élément de $E$ ne vérifie pas $P$. Un élément $x$ qui ne vérifie pas $P$ est un élément pour lequel $P(x)$ n'est pas vraie, c'est-à-dire, par le tiers exclu, pour lequel $P(x)$ est fausse, et $\neg P(x)$ vraie par la Définition « Négation ». Ainsi $\forall x \in E, \ P(x)$ est fausse exactement lorsque $\exists x \in E, \ \neg P(x)$ est vraie ; et $\neg(\forall x \in E, \ P(x))$, vraie exactement lorsque $\forall x \in E, \ P(x)$ est fausse, a la valeur de vérité de $\exists x \in E, \ \neg P(x)$.
Seconde loi. Elle découle de la première, appliquée au prédicat $\neg P$ : $$ \begin{aligned} \neg\left(\exists x \in E, \ P(x)\right) &\iff \neg\left(\exists x \in E, \ \neg\neg P(x)\right) && \text{(double négation, sous } \exists\text{)} \\ &\iff \neg\neg\left(\forall x \in E, \ \neg P(x)\right) && \text{(première loi pour } \neg P\text{, et remplacement)} \\ &\iff \forall x \in E, \ \neg P(x). \end{aligned} $$ La dernière équivalence est la double négation, appliquée à la proposition $\forall x \in E, \ \neg P(x)$.
Seconde démonstration : par l'abréviation. Le raisonnement de la première loi, avec « tout objet » au lieu de « tout élément de $E$ », donne $\neg(\forall x, \ R(x)) \iff \exists x, \ \neg R(x)$ pour tout prédicat $R$. Appliqué à $R(x)$ : « $x \in E \Rightarrow P(x)$ », $$ \begin{aligned} \neg\left(\forall x \in E, \ P(x)\right) &\iff \neg\left(\forall x, \ (x \in E \Rightarrow P(x))\right) && \text{(quantificateur borné)} \\ &\iff \exists x, \ \neg(x \in E \Rightarrow P(x)) && \text{(négation de } \forall\text{)} \\ &\iff \exists x, \ (x \in E \wedge \neg P(x)) && \text{(négation d'une implication, sous } \exists\text{)} \\ &\iff \exists x \in E, \ \neg P(x). \end{aligned} $$ L'appartenance $x \in E$ n'est pas niée : c'est l'hypothèse de l'implication, et la négation d'une implication garde son hypothèse. La seconde loi découle de la première comme dans la première démonstration.

Proposition — Négation d'une implication quantifiée

Pour tout ensemble $E$ et tous prédicats $P(x)$, $Q(x)$ sur $E$ : $$ \neg\left(\forall x \in E, \ (P(x) \Rightarrow Q(x))\right) \iff \exists x \in E, \ (P(x) \wedge \neg Q(x)). $$ Pour réfuter une implication universelle, on exhibe un contre-exemple : un élément qui vérifie l'hypothèse et pas la conclusion.

Preuve

$$ \begin{aligned} \neg\left(\forall x \in E, \ (P(x) \Rightarrow Q(x))\right) &\iff \exists x \in E, \ \neg(P(x) \Rightarrow Q(x)) && \text{(négation des quantificateurs)} \\ &\iff \exists x \in E, \ (P(x) \wedge \neg Q(x)). \end{aligned} $$ La dernière équivalence est la négation d'une implication, appliquée pour chaque $x$ et passée sous $\exists$. C'est la loi qui fonde la Méthode « Réfuter une implication » du chapitre Raisonner et rédiger.

Proposition — Nier plusieurs quantificateurs

Soient $n \ge 1$, des ensembles $E_1, \dots, E_n$, chaque $E_k$ pouvant dépendre de $x_1, \dots, x_{k-1}$ (comme dans « $\forall n \ge N$ »), un prédicat $P(x_1, \dots, x_n)$, et des quantificateurs $Q_1, \dots, Q_n$, chacun égal à $\forall$ ou à $\exists$ ; on note $Q^*$ l'autre quantificateur : $\forall^*$ est $\exists$, et $\exists^*$ est $\forall$. La négation de $$ Q_1 x_1 \in E_1, \ Q_2 x_2 \in E_2, \ \dots, \ Q_n x_n \in E_n, \ P(x_1, \dots, x_n) $$ a la même valeur de vérité, quels que soient les ensembles et le prédicat, que $$ Q_1^* x_1 \in E_1, \ Q_2^* x_2 \in E_2, \ \dots, \ Q_n^* x_n \in E_n, \ \neg P(x_1, \dots, x_n). $$ Chaque quantificateur est échangé, l'ordre et les ensembles sont gardés, et le prédicat final est nié.

Preuve

Pour $n \ge 1$, notons $H_n$ la propriété « la règle vaut pour tout énoncé à $n$ quantificateurs, quels que soient ses ensembles et son prédicat ».
Initialisation. $H_1$ est la Proposition « Négation des quantificateurs ».
Hérédité. Soit $n \ge 1$. Supposons $H_n$. Montrons $H_{n+1}$. Un énoncé à $n + 1$ quantificateurs s'écrit $Q_1 x_1 \in E_1, \ R(x_1)$, où $R(x_1)$ désigne l'énoncé $$ Q_2 x_2 \in E_2, \ \dots, \ Q_{n+1} x_{n+1} \in E_{n+1}, \ P(x_1, \dots, x_{n+1}). $$ Dans $R(x_1)$, la variable $x_1$ est libre et les autres sont liées : pour chaque $x_1 \in E_1$, c'est un énoncé à $n$ quantificateurs, dont les ensembles peuvent dépendre de $x_1$. Notons $R^*(x_1)$ l'énoncé $$ Q_2^* x_2 \in E_2, \ \dots, \ Q_{n+1}^* x_{n+1} \in E_{n+1}, \ \neg P(x_1, \dots, x_{n+1}). $$ Par $H_n$, $\neg R(x_1) \iff R^*(x_1)$ pour tout $x_1 \in E_1$. Alors $$ \begin{aligned} \neg\left(Q_1 x_1 \in E_1, \ R(x_1)\right) &\iff Q_1^* x_1 \in E_1, \ \neg R(x_1) && \text{(négation des quantificateurs)} \\ &\iff Q_1^* x_1 \in E_1, \ R^*(x_1). \end{aligned} $$ La dernière équivalence est l'hypothèse de récurrence, passée sous $Q_1^*$ ; c'est la règle pour $n + 1$ quantificateurs. Donc $H_{n+1}$.
Conclusion. Puisque $H_1$ est vraie et que $H_n \Rightarrow H_{n+1}$ pour tout $n \ge 1$, par récurrence à partir du rang $1$, $H_n$ est vraie pour tout $n \ge 1$.

Exemple — Deux négations

L'énoncé « tout réel dont le carré est strictement supérieur à $1$ est strictement supérieur à $1$ » s'écrit $\forall x \in \mathbb{R}, \ (x^2 > 1 \Rightarrow x > 1)$. Par la négation d'une implication quantifiée, sa négation est $\exists x \in \mathbb{R}, \ (x^2 > 1 \wedge x \le 1)$, qui est vraie : $x = -2$ vérifie $(-2)^2 = 4 > 1$ et $-2 \le 1$. Donc l'énoncé est faux, et $x = -2$ est un contre-exemple.
La négation de $\exists x \in \mathbb{R}, \ x^2 < 0$ est $\forall x \in \mathbb{R}, \ x^2 \ge 0$, qui est vraie. Donc l'énoncé existentiel est faux.

D'un énoncé et de sa négation, exactement un est vrai : démontrer l'un réfute l'autre.

Exemple — La négation de la convergence

Une suite réelle $(u_n)$ converge vers le réel $\ell$ lorsque $$ \forall \varepsilon > 0, \ \exists N \in \mathbb{N}, \ \forall n \ge N, \ \lvert u_n - \ell \rvert < \varepsilon. $$ Par la Proposition « Nier plusieurs quantificateurs », $(u_n)$ ne converge pas vers $\ell$ lorsque $$ \exists \varepsilon > 0, \ \forall N \in \mathbb{N}, \ \exists n \ge N, \ \lvert u_n - \ell \rvert \ge \varepsilon. $$ La règle opère de gauche à droite : $\forall \varepsilon > 0$ devient $\exists \varepsilon > 0$, puis $\exists N$ devient $\forall N$, puis $\forall n \ge N$ devient $\exists n \ge N$, et enfin $\lvert u_n - \ell \rvert < \varepsilon$ devient $\lvert u_n - \ell \rvert \ge \varepsilon$. Les ensembles sont gardés : « $\varepsilon > 0$ » décrit l'ensemble $]0, +\infty[$ et « $n \ge N$ » les entiers à partir de $N$ — un ensemble qui dépend de $N$, ce que la Proposition permet — et la négation ne les change jamais en « $\varepsilon \le 0$ » ou « $n < N$ ». En mots : une certaine distance $\varepsilon > 0$ à $\ell$ est atteinte ou dépassée par des termes d'indice arbitrairement grand.

Compétences à pratiquer

Nier un énoncé à un quantificateur ★
Nier un énoncé à plusieurs quantificateurs ★★

VIII Démontrer avec des connecteurs

VIII.1 Implication et contraposition

Ce que dit une implication

Une implication $p \Rightarrow q$ ne dit rien de $p$ elle-même : elle dit que chaque fois que $p$ est vraie, $q$ l'est aussi. Elle se démontre en supposant $p$ et en en déduisant $q$ — ou, quand $p$ donne peu de prise, en démontrant l'implication équivalente $\neg q \Rightarrow \neg p$, sa contraposée.

Signaler une erreur

Méthode — Démontrer une implication

Pour démontrer $p \Rightarrow q$ :

Supposons $p$. Montrons $q$.
$\vdots$ $\quad$ (démonstration de $q$, en utilisant $p$)
Donc $q$. Ainsi $p \Rightarrow q$ est vraie.

$p$ est un outil, $q$ est le but : la démonstration utilise $p$ et ne suppose jamais $q$. Pour un énoncé $\forall x \in E, \ p(x) \Rightarrow q(x)$, l'ouverture est « Soit $x \in E$ tel que $p(x)$. »

Exemple — Une implication qui restreint les solutions

Montrer que pour tout $x \in [0, 1]$, $x - x^2 \in \mathbb{Z} \Rightarrow x \in \{0, 1\}$.

Correction

Soit $x \in [0, 1]$ tel que $x - x^2 \in \mathbb{Z}$. Montrons $x \in \{0, 1\}$.
Minoration. Comme $x \in [0, 1]$, $x \ge 0$ et $1 - x \ge 0$. Un produit de deux nombres positifs étant positif, $$ \begin{aligned} x - x^2 &= x(1 - x) && \text{(factorisation)} \\ &\ge 0. \end{aligned} $$ Majoration. Un carré est positif, donc $$ \begin{aligned} x - x^2 &= \frac{1}{4} - \left(x - \frac{1}{2}\right)^2 && \text{(forme canonique)} \\ &\le \frac{1}{4}. \end{aligned} $$ Ainsi $x - x^2$ est un entier de $\left[0, \frac{1}{4}\right]$, donc $x - x^2 = 0$, c'est-à-dire $x(1 - x) = 0$ : $x = 0$ ou $x = 1$, car un produit n'est nul que si l'un de ses facteurs est nul.
Donc $x \in \{0, 1\}$, et l'implication vaut pour tout $x \in [0, 1]$. Les deux hypothèses ont servi — $x - x^2 \in \mathbb{Z}$ pour l'entier, $x \in [0, 1]$ pour la minoration — et la seconde ne peut pas être retirée : $x = 2$ donne $x - x^2 = -2 \in \mathbb{Z}$ et $2 \notin \{0, 1\}$.

Piège — la flèche d'implication n'est pas le mot donc

Le symbole $\Rightarrow$ construit la proposition « $p \Rightarrow q$ » ; ce n'est pas une abréviation de « donc ». Une copie fausse typique écrit $$ 0 \le x \le 1 \Rightarrow 0 \le x^2 \le 1 \Rightarrow 0 \le 1 - x^2 \le 1 \Rightarrow \sqrt{1 - x^2} \in [0, 1]. $$ Ce n'est pas une démonstration : $x$ n'est pas introduit, et chaque flèche affirme une implication sans dire que son membre de gauche est vrai. Une copie correcte écrit : « Soit $x \in [0, 1]$. La fonction carré étant croissante sur $\mathbb{R}_+$, $0 \le x^2 \le 1$. Donc $0 \le 1 - x^2 \le 1$. La fonction racine carrée étant croissante sur $\mathbb{R}_+$, $0 \le \sqrt{1 - x^2} \le 1$, c'est-à-dire $\sqrt{1 - x^2} \in [0, 1]$. » Dans le corps d'une démonstration, la flèche $\Rightarrow$ est rare : le raisonnement s'articule avec des mots — donc, ainsi, par conséquent, d'où.

Signaler une erreur

Méthode — Démontrer une implication par contraposée

L'implication $p \Rightarrow q$ et sa contraposée $\neg q \Rightarrow \neg p$ sont équivalentes. Pour démontrer $p \Rightarrow q$ :

Montrons la contraposée : si $\neg q$, alors $\neg p$. Supposons $\neg q$.
$\vdots$ $\quad$ (démonstration de $\neg p$, en utilisant $\neg q$)
Donc $\neg p$. Puisque nous avons démontré la contraposée, $p \Rightarrow q$ est vraie.

La contraposée aide quand $\neg q$ donne plus de prise que $p$ : une factorisation, un témoin, une inégalité explicite. La contraposée de $p \Rightarrow q$ est $\neg q \Rightarrow \neg p$, pas $q \Rightarrow p$ : cette dernière, la réciproque, est un autre énoncé, qui peut être faux.

Exemple — Nombres de Mersenne

Soit $n \ge 2$ un entier. Montrer que si $2^n - 1$ est premier, alors $n$ est premier.

Correction

Montrons la contraposée : si $n$ n'est pas premier, alors $2^n - 1$ n'est pas premier. Supposons $n$ non premier. Comme $n \ge 2$, $n$ a un diviseur $a$ tel que $1 < a < n$ : il existe $b \in \mathbb{N}^*$ tel que $n = ab$. Posons $x = 2^a$ ; alors $x \ne 1$, et $$ \begin{aligned} 2^n - 1 &= x^b - 1 && \text{($2^{ab} = (2^a)^b$)} \\ &= (x - 1) \sum_{k=0}^{b-1} x^k && \text{(somme géométrique, $x \ne 1$)} \\ &= (2^a - 1) \sum_{k=0}^{b-1} 2^{ak}. \end{aligned} $$ La somme est un entier naturel, donc $2^a - 1$ divise $2^n - 1$. De plus $2 \le a < n$ donne $3 \le 2^a - 1 < 2^n - 1$, la fonction $t \longmapsto 2^t$ étant strictement croissante. Ainsi $2^n - 1$ a un diviseur autre que $1$ et lui-même : il n'est pas premier.
Donc $2^n - 1$ n'est pas premier. Puisque nous avons démontré la contraposée, l'énoncé initial est vrai.
Contre-exemple à la réciproque : $n = 11$. D'une part, $11$ est premier ; d'autre part, $2^{11} - 1 = 2047 = 23 \times 89$ n'est pas premier.

Compétences à pratiquer

Écrire la contraposée ★
Corriger une copie : implication et équivalence ★★
Démontrer une implication ★★

IX Démontrer par récurrence

IX.1 Bon ordre et récurrence simple

L'idée de la récurrence

Une propriété $P_n$ de l'entier $n$ ne peut pas se vérifier pour chaque $n$ l'un après l'autre : $\mathbb{N}$ est infini. La récurrence remplace une infinité de vérifications par deux : la propriété est vraie au départ, et elle passe de chaque entier au suivant. La récurrence n'est pas un axiome : elle se démontre à partir d'une propriété de $\mathbb{N}$, l'existence d'un plus petit élément, et ses variantes aussi.

Signaler une erreur

Proposition — Plus petit élément

Toute partie non vide $A$ de $\mathbb{N}$ possède un plus petit élément : il existe $m \in A$ tel que $m \le a$ pour tout $a \in A$. Cet élément est unique ; on l'appelle le plus petit élément de $A$.

Preuve

L'existence est admise : c'est l'une des propriétés fondatrices de $\mathbb{N}$, qu'une construction de $\mathbb{N}$ prend pour axiome ou démontre, et dont partent les théorèmes de récurrence.
Unicité. Si $m$ et $m'$ sont deux plus petits éléments de $A$, alors $m \le m'$ et $m' \le m$, donc $m = m'$.
Cette propriété s'appelle le bon ordre de $\mathbb{N}$. Elle est fausse dans $\mathbb{Z}$, qui n'a pas de plus petit élément, et dans $\mathbb{R}_+$, dont la partie $]0, 1]$ n'en a pas.

Théorème — Récurrence simple

Soit $A \subset \mathbb{N}$. Si $0 \in A$ et $\forall n \in \mathbb{N}, \ n \in A \Rightarrow n + 1 \in A$, alors $A = \mathbb{N}$.

Preuve

Soit $A \subset \mathbb{N}$ tel que $0 \in A$ et $n \in A \Rightarrow n + 1 \in A$ pour tout $n \in \mathbb{N}$.
Supposons par l'absurde que $A \ne \mathbb{N}$. Alors l'ensemble $F = \mathbb{N} \setminus A$ des entiers hors de $A$ est une partie non vide de $\mathbb{N}$ ; par la Proposition « Plus petit élément », il possède un plus petit élément $m$.
Comme $m \in F$ et $0 \in A$, $m \ne 0$ ; donc $m \ge 1$ et $m - 1 \in \mathbb{N}$.
Comme $m - 1 < m$ et que $m$ est le plus petit élément de $F$, $m - 1 \notin F$, c'est-à-dire $m - 1 \in A$.
L'hypothèse appliquée à $n = m - 1$ donne $m \in A$, c'est-à-dire $m \notin F$ — alors que $m \in F$.
Contradiction ! Donc l'hypothèse est fausse, et $A = \mathbb{N}$.

Méthode — Rédiger une récurrence simple

Pour démontrer $\forall n \in \mathbb{N}, \ P_n$, on applique le Théorème « Récurrence simple » à $A = \{n \in \mathbb{N} \mid P_n \text{ est vraie}\}$. La copie s'écrit :

Pour $n \in \mathbb{N}$, notons $P_n$ la propriété « … ».
Initialisation. $P_0$ est vraie car $\dots$
Hérédité. Soit $n \in \mathbb{N}$. Supposons $P_n$ (hypothèse de récurrence). Montrons $P_{n+1}$. $\vdots$ $\quad$ (l'hypothèse de récurrence est citée là où elle sert) Donc $P_{n+1}$.
Conclusion. Puisque $P_0$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence, $P_n$ est vraie pour tout $n \in \mathbb{N}$.

La propriété $P_n$ s'énonce d'abord, pour un $n$ donné : elle parle d'un entier, jamais de « tout $n$ ».

Méthode — Récurrence à partir d'un rang non nul

Soit $n_0 \in \mathbb{N}$. Pour démontrer $\forall n \ge n_0, \ P_n$ :

Initialisation. Montrer $P_{n_0}$.
Hérédité. Soit $n \ge n_0$. Supposons $P_n$. Montrons $P_{n+1}$.
Conclusion. Puisque $P_{n_0}$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \ge n_0$, par récurrence à partir du rang $n_0$, $P_n$ est vraie pour tout $n \ge n_0$.

C'est le Théorème « Récurrence simple » appliqué à $A' = \{k \in \mathbb{N} \mid P_{n_0 + k} \text{ est vraie}\}$ : $0 \in A'$ est l'initialisation, et $k \in A' \Rightarrow k + 1 \in A'$ est l'hérédité pour $n = n_0 + k$.

Exemple — Une suite récurrente majorée

Soit $(a_n)_{n \in \mathbb{N}}$ définie par $a_0 = 1$ et $a_{n+1} = 1 + \frac{a_n}{n + 1}$ pour tout $n \in \mathbb{N}$. Montrer que $a_n \le 2$ pour tout $n \in \mathbb{N}$.

Correction

L'inégalité dont l'hérédité a besoin ne vaut que pour $n \ge 1$. On démontre donc $a_n \le 2$ pour tout $n \ge 1$ par récurrence à partir du rang $1$, et l'on vérifie $a_0$ à part : $a_0 = 1 \le 2$.
Pour $n \ge 1$, notons $P_n$ la propriété « $a_n \le 2$ ».
Initialisation. $a_1 = 1 + \frac{a_0}{1} = 2$, donc $P_1$ est vraie.
Hérédité. Soit $n \ge 1$. Supposons $P_n$. Montrons $P_{n+1}$. $$ \begin{aligned} a_{n+1} &= 1 + \frac{a_n}{n + 1} && \text{(définition de la suite)} \\ &\le 1 + \frac{2}{n + 1} && \text{(hypothèse de récurrence, $n + 1 > 0$)} \\ &\le 1 + \frac{2}{2} && \text{($n + 1 \ge 2$)} \\ &= 2. \end{aligned} $$ Donc $P_{n+1}$.
Conclusion. Puisque $P_1$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \ge 1$, par récurrence à partir du rang $1$, $a_n \le 2$ pour tout $n \ge 1$ ; avec $a_0 = 1$, $a_n \le 2$ pour tout $n \in \mathbb{N}$.

Piège — l'hérédité porte sur un entier générique

L'hérédité démontre un énoncé universel : pour tout $n \in \mathbb{N}$, $P_n \Rightarrow P_{n+1}$. Elle s'ouvre donc comme toute démonstration universelle : « Soit $n \in \mathbb{N}$. Supposons $P_n$. » Deux autres ouvertures se rencontrent dans les copies. « Supposons $P_n$ vraie pour tout $n \in \mathbb{N}$ » est faux : c'est supposer ce qu'il faut démontrer, et il ne resterait rien à prouver. « Supposons $P_n$ vraie pour un certain $n$ » n'est acceptable que si $n$ désigne un entier quelconque fixé : cela ne doit pas vouloir dire que l'on suppose seulement l'existence d'un rang où $P_n$ est vraie. « Soit $n \in \mathbb{N}$. Supposons $P_n$. » le dit explicitement, c'est pourquoi on préfère cette ouverture.

Signaler une erreur

Compétences à pratiquer

Calculer à partir d'une définition par récurrence ★
Corriger une copie : hérédité ★★
Rédiger une récurrence simple ★★

IX.2 Récurrences double et forte

Quand un rang ne suffit pas

Parfois $P_{n+1}$ demande plus que $P_n$ : les deux rangs précédents, pour une suite définie par $u_{n+2} = a u_{n+1} + b u_n$ ; ou tous les rangs précédents, comme lorsque $n + 1 = k \ell$ se décompose en deux facteurs plus petits. Les deux variantes découlent de la récurrence simple, appliquée à une propriété plus forte.

Signaler une erreur

Théorème — Récurrence double

Soit $A \subset \mathbb{N}$. Si $0 \in A$, $1 \in A$, et $\forall n \in \mathbb{N}, \ (n \in A \text{ et } n + 1 \in A) \Rightarrow n + 2 \in A$, alors $A = \mathbb{N}$.

Preuve

Supposons par l'absurde que $A \ne \mathbb{N}$. L'ensemble $F = \mathbb{N} \setminus A$ est une partie non vide de $\mathbb{N}$ ; par la Proposition « Plus petit élément », il possède un plus petit élément $m$. Comme $m \in F$ et $0, 1 \in A$, $m \ge 2$, donc $m - 2$ et $m - 1$ sont des entiers naturels.
Les entiers $m - 2$ et $m - 1$ sont plus petits que $m$, donc ils ne sont pas dans $F$ : $m - 2 \in A$ et $m - 1 \in A$.
L'hypothèse appliquée à $n = m - 2$ donne $m \in A$, c'est-à-dire $m \notin F$ — alors que $m \in F$.
Contradiction ! Donc l'hypothèse est fausse, et $A = \mathbb{N}$.
Seconde démonstration, par récurrence simple. Soit $B = \{n \in \mathbb{N} \mid n \in A \text{ et } n + 1 \in A\}$ ; on applique le Théorème « Récurrence simple » à $B$.
$0 \in B$, puisque $0 \in A$ et $1 \in A$.
Soit $n \in \mathbb{N}$ tel que $n \in B$ : $n \in A$ et $n + 1 \in A$. L'hypothèse donne $n + 2 \in A$ ; ainsi $n + 1 \in A$ et $n + 2 \in A$, c'est-à-dire $n + 1 \in B$.
Par récurrence simple, $B = \mathbb{N}$. Tout $n \in \mathbb{N}$ est alors dans $B$, donc dans $A$ : $A = \mathbb{N}$.

Méthode — Rédiger une récurrence double

Pour démontrer $\forall n \in \mathbb{N}, \ P_n$ quand $P_{n+2}$ utilise à la fois $P_n$ et $P_{n+1}$ :

Initialisation. Montrer $P_0$ et $P_1$.
Hérédité. Soit $n \in \mathbb{N}$. Supposons $P_n$ et $P_{n+1}$ (hypothèse de récurrence). Montrons $P_{n+2}$.
Conclusion. Puisque $P_0$ et $P_1$ sont vraies et que ($P_n$ et $P_{n+1}$) $\Rightarrow P_{n+2}$ pour tout $n \in \mathbb{N}$, par récurrence double, $P_n$ est vraie pour tout $n \in \mathbb{N}$.

Deux initialisations, pas une : l'hérédité pour $n = 0$ utilise à la fois $P_0$ et $P_1$. À partir d'un rang $n_0$, comme pour une récurrence simple, les initialisations sont $P_{n_0}$ et $P_{n_0 + 1}$, l'hérédité vaut pour tout $n \ge n_0$, et la conclusion s'écrit « par récurrence double à partir du rang $n_0$ ».

Exemple — Une formule explicite par récurrence double

Soit $(u_n)_{n \in \mathbb{N}}$ définie par $u_0 = 4$, $u_1 = 5$ et $u_{n+2} = 3 u_{n+1} - 2 u_n$ pour tout $n \in \mathbb{N}$. Montrer que $u_n = 2^n + 3$ pour tout $n \in \mathbb{N}$.

Correction

Pour $n \in \mathbb{N}$, notons $P_n$ la propriété « $u_n = 2^n + 3$ ».
Initialisation. $u_0 = 4 = 2^0 + 3$ et $u_1 = 5 = 2^1 + 3$ : $P_0$ et $P_1$ sont vraies.
Hérédité. Soit $n \in \mathbb{N}$. Supposons $P_n$ et $P_{n+1}$. Montrons $P_{n+2}$. $$ \begin{aligned} u_{n+2} &= 3 u_{n+1} - 2 u_n && \text{(définition de la suite)} \\ &= 3\left(2^{n+1} + 3\right) - 2\left(2^n + 3\right) && \text{(hypothèse de récurrence $P_{n+1}$ et $P_n$)} \\ &= 3 \cdot 2^{n+1} - 2^{n+1} + 3 && \text{($2 \cdot 2^n = 2^{n+1}$)} \\ &= 2^{n+2} + 3. \end{aligned} $$ Donc $P_{n+2}$.
Conclusion. Puisque $P_0$ et $P_1$ sont vraies et que ($P_n$ et $P_{n+1}$) $\Rightarrow P_{n+2}$ pour tout $n \in \mathbb{N}$, par récurrence double, $u_n = 2^n + 3$ pour tout $n \in \mathbb{N}$.
Seconde méthode : la formule trouvée, pas seulement vérifiée. Pour tout $n \in \mathbb{N}$, $$ \begin{aligned} u_{n+2} - 2 u_{n+1} &= 3 u_{n+1} - 2 u_n - 2 u_{n+1} && \text{(définition de la suite)} \\ &= u_{n+1} - 2 u_n, \end{aligned} $$ donc la suite $(u_{n+1} - 2 u_n)_{n \in \mathbb{N}}$ est constante, égale à $u_1 - 2 u_0 = -3$. Ainsi $u_{n+1} = 2 u_n - 3$, c'est-à-dire $u_{n+1} - 3 = 2(u_n - 3)$, pour tout $n \in \mathbb{N}$ : la suite $(u_n - 3)_{n \in \mathbb{N}}$ est géométrique de raison $2$ et de premier terme $u_0 - 3 = 1$, donc $u_n - 3 = 2^n$, c'est-à-dire $u_n = 2^n + 3$. La récurrence double est devenue une récurrence simple, et la formule sort du calcul au lieu d'être donnée.

Théorème — Récurrence forte

Soit $A \subset \mathbb{N}$. Si $0 \in A$ et $\forall n \in \mathbb{N}, \ \left(\forall k \in \llbracket 0, n \rrbracket, \ k \in A\right) \Rightarrow n + 1 \in A$, alors $A = \mathbb{N}$.

Preuve

Soit $A \subset \mathbb{N}$ vérifiant les deux hypothèses.
Supposons par l'absurde que $A \ne \mathbb{N}$. L'ensemble $F = \mathbb{N} \setminus A$ est une partie non vide de $\mathbb{N}$ ; par la Proposition « Plus petit élément », il possède un plus petit élément $m$. Comme $m \in F$ et $0 \in A$, $m \ge 1$, donc $m - 1 \in \mathbb{N}$.
Tout $k \in \llbracket 0, m - 1 \rrbracket$ vérifie $k < m$, donc $k \notin F$ par minimalité de $m$, c'est-à-dire $k \in A$.
L'hypothèse appliquée à $n = m - 1$ donne alors $m \in A$, c'est-à-dire $m \notin F$ — alors que $m \in F$.
Contradiction ! Donc l'hypothèse est fausse, et $A = \mathbb{N}$.
Seconde démonstration, par récurrence simple. Soit $B = \{n \in \mathbb{N} \mid \llbracket 0, n \rrbracket \subset A\}$.
$0 \in B$, puisque $\llbracket 0, 0 \rrbracket = \{0\} \subset A$.
Soit $n \in \mathbb{N}$ tel que $n \in B$ : $\llbracket 0, n \rrbracket \subset A$, donc l'hypothèse donne $n + 1 \in A$, et $\llbracket 0, n + 1 \rrbracket = \llbracket 0, n \rrbracket \cup \{n + 1\} \subset A$, c'est-à-dire $n + 1 \in B$.
Par récurrence simple, $B = \mathbb{N}$. Tout $n \in \mathbb{N}$ vérifie alors $n \in \llbracket 0, n \rrbracket \subset A$, donc $A = \mathbb{N}$.

Méthode — Rédiger une récurrence forte

Pour démontrer $\forall n \in \mathbb{N}, \ P_n$ quand $P_{n+1}$ peut utiliser n'importe lequel des $P_0, \dots, P_n$ :

Initialisation. Montrer $P_0$.
Hérédité. Soit $n \in \mathbb{N}$. Supposons $P_k$ pour tout $k \in \llbracket 0, n \rrbracket$ (hypothèse de récurrence forte). Montrons $P_{n+1}$.
Conclusion. Puisque $P_0$ est vraie et que ($P_0, \dots, P_n$) $\Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence forte, $P_n$ est vraie pour tout $n \in \mathbb{N}$.

L'hypothèse s'écrit en entier, avec le domaine de $k$ : « pour tout $k \in \llbracket 0, n \rrbracket$ ». À partir d'un rang $n_0$, l'initialisation est $P_{n_0}$ et l'hypothèse couvre $\llbracket n_0, n \rrbracket$.

Exemple — Une majoration par la somme des termes précédents

Soit $(v_n)_{n \in \mathbb{N}}$ une suite réelle telle que $v_0 \ge 0$ et $v_{n+1} \le \sum_{k=0}^{n} v_k$ pour tout $n \in \mathbb{N}$. Montrer que $v_n \le 2^n v_0$ pour tout $n \in \mathbb{N}$.

Correction

Pour $n \in \mathbb{N}$, notons $P_n$ la propriété « $v_n \le 2^n v_0$ ».
Initialisation. $v_0 = 2^0 v_0$, donc $P_0$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$. Supposons $P_k$ pour tout $k \in \llbracket 0, n \rrbracket$. Montrons $P_{n+1}$. Comme $v_0 \ge 0$, $$ \begin{aligned} v_{n+1} &\le \sum_{k=0}^{n} v_k && \text{(hypothèse sur la suite)} \\ &\le \sum_{k=0}^{n} 2^k v_0 && \text{(hypothèse de récurrence forte, pour chaque $k \in \llbracket 0, n \rrbracket$)} \\ &= \left(2^{n+1} - 1\right) v_0 && \text{(somme géométrique)} \\ &\le 2^{n+1} v_0. \end{aligned} $$ Donc $P_{n+1}$.
Conclusion. Puisque $P_0$ est vraie et que ($P_0, \dots, P_n$) $\Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence forte, $v_n \le 2^n v_0$ pour tout $n \in \mathbb{N}$. L'hérédité utilise tous les rangs précédents à la fois : une récurrence simple sur $P_n$ seule ne suffirait pas.
Seconde méthode : une récurrence simple sur les sommes partielles. Pour $n \in \mathbb{N}$, posons $S_n = \sum_{k=0}^{n} v_k$. Pour tout $n \in \mathbb{N}$, comme $v_{n+1} \le S_n$ par hypothèse, $$ \begin{aligned} S_{n+1} &= S_n + v_{n+1} && \text{(dernier terme à part)} \\ &\le 2 S_n. \end{aligned} $$ Pour $n \in \mathbb{N}$, notons $Q_n$ la propriété « $S_n \le 2^n v_0$ ».
Initialisation. $S_0 = v_0 = 2^0 v_0$, donc $Q_0$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$. Supposons $Q_n$. Montrons $Q_{n+1}$. $$ \begin{aligned} S_{n+1} &\le 2 S_n && \text{(ci-dessus)} \\ &\le 2 \cdot 2^n v_0 && \text{(hypothèse de récurrence)} \\ &= 2^{n+1} v_0. \end{aligned} $$ Donc $Q_{n+1}$.
Conclusion. Puisque $Q_0$ est vraie et que $Q_n \Rightarrow Q_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence, $S_n \le 2^n v_0$ pour tout $n \in \mathbb{N}$.
Enfin, comme $v_0 \ge 0$, pour tout $n \in \mathbb{N}$, $$ \begin{aligned} v_{n+1} &\le S_n && \text{(hypothèse sur la suite)} \\ &\le 2^n v_0 && \text{(propriété $Q_n$)} \\ &\le 2^{n+1} v_0. \end{aligned} $$ Avec $v_0 = 2^0 v_0$, $v_n \le 2^n v_0$ pour tout $n \in \mathbb{N}$. La somme $S_n$ porte tous les rangs précédents en un seul nombre : une récurrence simple suffit, et elle donne même $v_{n+1} \le 2^n v_0$.

Compétences à pratiquer

Rédiger une récurrence double ou forte ★★

X Révision & Quizz

Compétences à pratiquer

Quiz

Aller à la section

\(p\)	\(q\)	\(p \vee q\)	ou exclusif
V	V	V	F
V	F	V	V
F	V	V	V
F	F	F	F

\(p\)	\(q\)	\(\neg p\)	\(\neg q\)	\(p \wedge q\)	\(\neg(p \wedge q)\)	\(\neg p \vee \neg q\)	\(p \vee q\)	\(\neg(p \vee q)\)	\(\neg p \wedge \neg q\)
V	V	F	F	V	F	F	V	F	F
V	F	F	V	F	V	V	V	F	F
F	V	V	F	F	V	V	V	F	F
F	F	V	V	F	V	V	F	V	V

\(p\)	\(q\)	\(r\)	\(q \vee r\)	\(p \wedge (q \vee r)\)	\(p \wedge q\)	\(p \wedge r\)	\((p \wedge q) \vee (p \wedge r)\)
V	V	V	V	V	V	V	V
V	V	F	V	V	V	F	V
V	F	V	V	V	F	V	V
V	F	F	F	F	F	F	F
F	V	V	V	F	F	F	F
F	V	F	V	F	F	F	F
F	F	V	V	F	F	F	F
F	F	F	F	F	F	F	F

\(p\)	\(q\)	\(r\)	\(q \wedge r\)	\(p \vee (q \wedge r)\)	\(p \vee q\)	\(p \vee r\)	\((p \vee q) \wedge (p \vee r)\)
V	V	V	V	V	V	V	V
V	V	F	F	V	V	V	V
V	F	V	F	V	V	V	V
V	F	F	F	V	V	V	V
F	V	V	V	V	V	V	V
F	V	F	F	F	V	F	F
F	F	V	F	F	F	V	F
F	F	F	F	F	F	F	F

\(p\)	\(q\)	\(p \Rightarrow q\)	\(q \Rightarrow p\)	\((p \Rightarrow q) \wedge (q \Rightarrow p)\)	\(p \iff q\)
V	V	V	V	V	V
V	F	F	V	F	F
F	V	V	F	F	F
F	F	V	V	V	V