N O T I O N S D E L O G I Q U E , R A I S O N N E M E N T S .

E N S E M B L E S , É Q U AT I O N S , I N É Q U AT I O N S
1
1.1 assertions, quantificateurs

Motivation : installer les bases du formalisme mathématique.

Prérequis
— Manipulations algébriques élémentaires dans R ou C, identités remarquables, forme canonique.
Nouvelles notions : Assertion, ∀, ∃, type des objets, variables libres et liées, portée d’un symbole, arbre d’expression
Savoir faire
— identifier les types d’objets (nombre, assertion, fonction, suite, non sens)
— identifier les variables liées et les variables libres
— identifier le connecteur principal, construire l’arbre d’expression
— traduire une assertion quantifiée en une phrase en français et vice-versa.
— Démontrer des assertions quantifiées avec ∀ ou ∃ (notion d’introduction)
— Utiliser dans une preuve des hypothèses quantifiées avec ∀ ou ∃ (notion d’élimination)
— Démontrer la négation d’assertions quantifiées avec ∀ ou ∃

1.1.1 Assertions

Vocabulaire [Link] (Assertion).

Assertion : énoncé mathématique correctement formé susceptible d’avoir une valeur de vérité (vrai ou faux) (elle
comporte un verbe).
Une assertion démontrable est appelée théorème.

√
3 π
Exemples : = cos est une assertion fausse ; 4 + 2 6 1 + 5 est une assertion vraie. La phrase “Tous les entiers sont
2 3
négatifs” est une assertion (fausse). Contre exemples : 4 + 2 6 Z n’est pas une assertion (erreur de typage). 4 + 2 n’est pas une
assertion (c’est un nombre).

[Link] Type des objets mathématiques

Le décryptage d’un texte mathématique passe par l’identification systématique du type de chaque objet désigné par chaque
expression ou sous expression présente dans le texte.

Exercice [Link].

Déterminez le type des objets désignés par l’expression ci-dessous et par les sous-expressions qu’elle contient :
“Soit a un nombre entier et soit f l’application qui à un entier n associe n + a. Si a > 5 alors
{m ∈ N | f(m − 1) < 4} est vide.”
Début de réponse : “a est un nombre, 5 est un nombre, a > 5 est une assertion... ”

import [Link].
Basic L’exercice ci-dessus devra être répété à la lecture de chaque texte mathématique. Le logiciel Lean
#check 4
([Link] peut vous aider dans ce travail : utilisez la commande #check pour
#check 4+2
#check 4+2 6 1+5 déterminer le type d’un objet désigné par une expression. Dans Lean, Prop signifie assertion.
#check (fun n:N7→ n+1)

1
[Link] Assertion dépendant d’une variable (prédicat) - Variable libre Le logiciel Lean permet de représenter une assertion dépendant
d’une ou plusieurs variables. On dit que la variable x est libre
Exercice [Link]. dans
P(x) (x − 1)2 = x2 − 1
Vrai ou faux ? Si vous pensez que la question est mal posée,
import [Link]
reformulez, discutez, détaillez. def P (x:Z) := (x-1)^2 = x^2 - 1

(a) (x − 1)2 = x2 − 2x + 1 #check P -- P (x : Z) : Prop

#check (P) -- P : Z→ Prop
(b) (x − 1)2 = x2 − 1 #check (P 2) -- P 2 : Prop

(c) x2 < 0 #reduce (P (-1)) -- [Link] 4 = [Link] 0 -- 4= 0

#reduce (P 0) -- [Link] 1 = [Link] 0 -- 1=-1
#reduce (P 1) -- [Link] 0 = [Link] 0 -- 0= 0
#reduce (P 2) -- [Link] 1 = [Link] 3 -- 1= 3

1.1.2 Quantificateur universel

Exercice [Link].

Vocabulaire [Link] (Quantificateur universel). Lesquelles des assertions ci-dessous sont vraies ?
(pas de preuve rédigée pour l’instant)
L’expression “pour tout” est appelé quantificateur universel, et noté ∀. (a) ∀x ∈ R, (x − 1)2 = x2 − 2x + 1
∀x ∈ E, P(x) est une assertion signifiant qu’en remplaçant x par n’im-
(b) ∀x ∈ R, (x − 1)2 = x2 − 1
porte quel élément de E, P(x) est vraie.
(c) ∀n ∈ {17; 13; 25; 0; 11} , n est impair
(d) ∀x ∈ R, x2 < 0

[Link] Démontrer ∀x ∈ E, P(x) : introduction de ∀

Pour démontrer ∀x ∈ E, P(x), on fixe un élément u quelconque (sans contrainte) de E en on prouve que P(u) est vraie pour ce u
particulier. Attention : on ne choisit pas la valeur de u, ni aucune hypothèse le concernant (sauf u ∈ E) puisque u doit rester
“générique”. Cette démarche s’initie avec le mot clé "Soit". Le u ainsi défini restera valide dans une zone du texte appelée sa portée
que l’on mettre en évidence par une indentation appropriée.
[Link] Démontrer ∀x ∈ E, P(x)
import [Link]
Soit u un élément de E. example: ∀x:R, (x-1)^2 = x^2 -2*x + 1 :=
λ u:R7→ -- soit u:R,
··· (
sorry: P u
· · · INDENTER )
···
· · · Donc P(u) est vraie. Dans Lean, déplacez le curseur devant le λ, puis devant le sorry,
Donc ∀x ∈ E, P(x) et observez l’évolution du contexte (Tactic state) et du but (Goal).

Exercice [Link].
Exercice [Link].
1. Montrez que ∀x ∈ {−1; 2} , x + 1 6 5 − x.
Démontrez les assertions de l’exercice [Link] dont vous
2. Prouvez que ∀x ∈ {1; 2} , x3 − 3x2 + 2x = 0.
avez conjecturé qu’elles sont vraies.
3. Démontrez que ∀y ∈ R, y2 − 4y + 7 > 1.

[Link] Utiliser ∀x ∈ E, P(x) : élimination de ∀

Utiliser une assertion du type ∀x ∈ E, P(x) consiste à la spécialiser : si P(x) est vrai pour n’importe quel x, il sera vrai en
particulier pour un u de notre choix (on choisit un u qui nous arrange).

Exercice [Link].
example (a:R) (h: ∀x:R,a 6 x^2 -2*x) : a 6 -1 :=
Soit a un nombre réel. calc
a 6 1^2-2*1 := h 1 -- on applique h à 1
On suppose que ∀x ∈ R, a 6 x2 − 2x. Montrez que a 6 −1. _ = -1 := by norm_num

Exercice [Link].
1. Soit a un nombre réel vérifiant : ∀x ∈ R, a sin(x) = 0. Montrez que a = 0.
2. Soient a et b des nombres réels. On suppose que ∀x ∈ R, x > a OU x 6 b. Montrez que a 6 b.
3. Soit a un nombre réel tel que a2 6 2, et qui est supérieur ou égal à tout nombre réel dont le carré est inférieur
ou égal à 2. Soit b un nombre réel possédant les deux mêmes propriétés. Prouvez que a = b.

2
1.1.3 Quantificateur Existentiel

Vocabulaire [Link] (Quantificateur existentiel).

L’expression “il existe” (signifiant “il existe au moins”) est appelé quantificateur existentiel, et noté ∃.
∃x ∈ E, P(x) est une assertion signifiant qu’il existe (au moins) un élément u de E tel que l’assertion P(u) soit vraie.

Exercice [Link].
Exercice [Link].
Lesquelles des assertions ci-dessous sont vraies ?
1. ∃n ∈ {17; 13; 25; 0; 11} , n est impair. (i) Donnez la définition d’un nombre entier impair
2. ∃x ∈ R, (x − 1)2 = x2 − 2x + 1 (ii) La formulation suivante est incorrecte, car imprécise :
3. ∃x ∈ R, (x − 1)2 = x2 −1
cos(x) = 0 équivaut à x = π2 + kπ avec k ∈ Z.
Donnez en une formulation correcte.
4. ∃x ∈ R, x2 < 0

[Link] Démontrer ∃x ∈ E, P(x) : introduction de ∃

Pour démontrer ∃x ∈ E, P(x), on exhibe un élément particulier u de E qui vérifie P(u). Trouver un u qui fonctionne, peut, selon
les cas, demander plus ou moins d’imagination. Cet élément peut être introduit à nouveau à l’aide le mot clé "Soit" mais utilisé
de façon différente :
Démontrer ∃x ∈ E, P(x)
Méthode constructive : “ exhiber” un élément u de E vérifiant P(x).
Soit u := . . . . Alors on a bien u ∈ E car . . . .
import [Link]
De plus,
example: ∃x:R, (x-1)^2 = x^2 - 1 :=
··· [Link] 1 ( -- introduction de 1 comme candidat
calc ((1:R)-1)^2 = 1^2 - 1 := by norm_num
· · · INDENTER )
···
· · · Donc P(u) est vraie.
Donc ∃x ∈ E, P(x)
Le u ainsi défini restera valide dans une zone du texte appelée sa portée que l’on mettre en évidence par une indentation
appropriée.

Exercice [Link].

1. Démontrez les assertions de l’exercice [Link] dont vous avez conjecturé qu’elles sont vraies.
2. Montrez que ∃x ∈ {1; 2} , x2 − 5x + 6 = 0.
3. Montrez que 7 est impair. [Cela signifie “Montrez que 7 vérifie la définition d’un entier impair”].

[Link] Utiliser ∃x ∈ E, P(x) : élimination de ∃

Si ∃x ∈ E, P(x) est une hypothèse, alors on peut fixer un élément u de E qui possède la propriété P(u). Mais attention : on ne
peut pas choisir la valeur de u : on ne sait rien d’autre sur u à part P(u).

Exercice [Link].

1. Montrez que si n est un nombre entier impair, alors 3n + 2 est impair.

[ Cela signifie : montrez que si n vérifie la définition d’un nombre entier impair alors 3n + 2 vérifie la définition
d’un nombre entier impair ] .
2. Montrez que si x et y sont des nombres entier impairs, alors x + y + 1 est impair.
3. Donnez la définition d’un nombre pair.

3
1.1.4 Variable liée, portée

Dans ∀x ∈ R, (x − 1)2 > 0, la variable x est dite liée. Ce qui signifie

• Elle n’est pas définie en dehors de la portée du connecteur ∀ qui la lie. Ici cette portée import [Link]
def P := ∀ x:Z , x > 0
est (x − 1)2 > 0 ; def Q := x > 0 -- error
def P’ : Prop := ∀ x:Z , x > 0
• Elle est interchangeable avec tout autre symbole : ∀t ∈ R, (t − 1)2 > 0 a la même def Q’ : Prop := x > 0 -- error
def R : Z→ Prop := fun x:Z7→ x > 0
signification ; def S : Z→ Prop := fun a:Z7→ ∃ x:Z , a*x > 0
example : S 5 = ∃ x:Z , 5*x > 0 := rfl
• La même assertion pourrait s’exprimer sans variable : “ Pour tout nombre réel, si on
lui enlève 1 et qu’on met le résultat au carré, on obtient un nombre positif”.
De même pour les assertions quantifiées à l’aide de ∃.

Exercice [Link].
Quelles sont les variables libres dans les assertions suivantes ? Identifiez les variables liées et leur portée.
1. bx2 > 0 5. ∀w ∈ R, f(w) 6 M 9. ∃M ∈ R, (∀u ∈ R, f(x) 6 M)
2. ∀x ∈ R, bx2 > 0 6. Si a > 0 alors ∀a ∈ R, f(a) 6 M 10. ∀x ∈ R, (x + m = 2 ⇐⇒ x = −m + 2)
3. f(u) 6 M 7. Si a > 0 alors ∀r ∈ R, f(r) 6 M
4. Si t > 0 alors f(t) 6 M 8. ∃M ∈ R, (∀x ∈ R, f(x) 6 M)
P R
Remarque : autres mutateurs ( , , lim, 7→, ...)

Exercice [Link].
Quelles sont les variables libres dans les expressions suivantes ? Identifiez les variables liées et leur portée.
Zx
X
n
1 X
n
1 5. fy : R −→ R
1. y cos(a + xt) dt 3. n 4. k
a n+k k+n x 7→ exp(xy)
k=1 k=1
Zt
(ln y)x
2. y cos(a + xt) dt 6. lim
a y→+∞ yt

1.1.5 Démontrer que des assertions quantifiées sont fausses

Exercice [Link].
1. Démontrez que les assertions de l’exercice [Link] dont vous avez conjecturé qu’elles sont fausses le sont.
2. Démontrez que les assertions de l’exercice [Link] dont vous avez conjecturé qu’elles sont fausses le sont.
3. Donnez une assertion équivalente à NON (∀x ∈ E, P(x)) et une assertion équivalente à NON (∃x ∈ E, P(x))
On donnera la preuve de ces résultats plus tard.

1.1.6 Structure syntaxique

Exercice [Link].
Pour chacune des expressions ci-après, identifiez le connecteur principal, et construisez l’arbre de l’expression. Placez les parenthèses
implicites. Repérez la portée de chaque symbole.

1. ∀x ∈ R, ∃y ∈ R, y > x OU ∃x ∈ R, ∀y ∈ R, y > x 3. ∀x ∈ N, (∃y ∈ N, y > x) ⇐⇒ (∃z ∈ N, z > x + 1)

2. ∀x ∈ Z, 3x + 2 > 0 =⇒ x > −1 4. (∀x ∈ E, x2 > 0) =⇒ (∀x ∈ E 0 , x2 − 4x + 6 > 0)

1.1.7 Enoncés quantifiés imbriqués

∀ ∃
Démontrer (intro) Pas le choix (autre joueur) Choix (vous)
Utiliser (elim) Choix (vous) Pas le choix (autre joueur)

Exercice [Link].
1. Montrez que ∀x ∈ R, ∃y ∈ R, y > x
2. Montrez que l’assertion suivante est fausse : ∃y ∈ R, ∀x ∈ R, y > x

4
1.2 implication ; raisonnement par récurrence

Motivation : Formaliser la notion implication - approfondir la notion de récurrence

Prérequis : Cours de Lycée sur la logique, la récurrence - Chapitre 1, séance 1
Notions abordées : Implication, Condition Suffisante, Condition Nécessaire, Raisonnements par récurrence
Savoir faire
— Maîtriser le sens et la rédaction des raisonnements par implication
— Déterminer une condition nécessaire sur x pour avoir P(x)
— Déterminer une condition suffisante sur x pour avoir P(x)
— Mener des raisonnements par récurrence (simple, double, forte)

1.2.1 L’implication =⇒

Vocabulaire [Link].
Si P et Q sont des assertions, P =⇒ Q est une assertion qui, lorsqu’elle est vraie, permet de produire une preuve de
Q lorsqu’on a la garantie que P est vraie. Voici d’autres formulations de P =⇒ Q :
• Si P alors Q
• Pour que P soit vraie, il est nécessaire que Q soit vraie (Q est une condition nécessaire (CN) pour P)
• Pour que Q soit vraie, il est suffisant que P soit vraie (P est une condition suffisante (CS) pour Q)
• Q si P
• P seulement si Q
• « Théorème : Supposons que soient satisfaites les hypothèses (P). Alors on aura (conclusion) (Q) ».
L’assertion Q =⇒ P s’appelle Réciproque de P =⇒ Q. Attention : une implication et sa réciproque n’ont pas, en
général, la même valeur de vérité.

Remarque importante (nous démontrerons cela plus tard) : P =⇒ Q est vraie dans deux cas, et seulement ces deux cas :
— si Q est vraie (dans ce cas peu importe la valeur de vérité de P)
— si P est fausse (dans ce cas peu importe la valeur de vérité de Q)
Il est crucial de comprendre que P =⇒ Q ne dit rien sur la valeur de vérité de P : P =⇒ Q peut parfois être vraie lorsque P est
vraie, mais aussi lorsque P est fausse. Affirmer P =⇒ Q n’a d’intérêt que lorsqu’on n’a pas d’information sur la valeur de vérité
de P. (Si on savait que P est vraie, il suffirait d’affirmer Q). (en ceci P =⇒ Q se distingue de P donc Q).

[Link] Implication et quantification universelle

x x=2 x2 = 4 x = 2 =⇒ x2 = 4 x2 = 4 =⇒ x = 2 Exercice [Link].

0 F F V V
1. Complétez le tableau ci-contre.
1
2. Vrai ou faux ? ∀x ∈ R, x = 2 =⇒ x2 = 4


2 V V V V
3. Vrai ou faux ? ∀x ∈ R, x2 = 4 =⇒ x = 2


−2

[Link] Démontrer P =⇒ Q - (introduction de =⇒)

Prouver P =⇒ Q
Supposons P.
example: ∀x:R, (x=2 → x^2=4) :=
··· λ x:R7→ --- soit x:R ,
· · · INDENTER λ h:x=2 7→ --- supposons h:x=2 ,
··· calc
· · · Donc Q est vraie. x^2 = 2^2 := congr_arg (fun z:R7→ z^2) (h:x=2)
_ = 4 := by norm_num
Donc P =⇒ Q.

Exercice [Link].
1. Reformulez le problème ci-dessous en utilisant ∀ et =⇒ puis le résoudre :
“Soient a et b des nombres rationnels. Supposons que a − b = 4 et ab = 1. Montrez que (a + b)2 = 20.”
2. Reformulez le problème ci-dessous et français (comme dans la question précédente) puis le résoudre :
“ Montrez que : ∀x ∈ Z, ∀y ∈ Z, (x + 3 6 2 ET y + 2x > 3) =⇒ y > 3 ”
3. Reformuler en utilisant ∀ et =⇒ puis montrez que : “La somme de deux entiers impairs est un entier pair.”

5
[Link] Utilisation de P =⇒ Q (élimination de =⇒) - Modus Ponens
Règle du Modus Ponens : Lorsque P =⇒ Q et P figurent dans les hypothèses, on peut en déduire Q.
Exemple : Théorème de Pythagore : Soient A, B et C trois points du plan. Alors (ABC rectangle en A) =⇒ BC2 = BA2 + AC2 .
Modus Ponens

theorem joli_theoreme : ∀ x:Z, ∀ y:Z, ∀ z:Z, (z> 0 → (x 6 y →

z*x 6 z*y)):=
λ x:Z7→ λ y:Z7→ λ z:Z7→ λ h1:z> 0 7→ λ h2:x 6 y 7→
mul_le_mul_of_nonneg_left h2 h1
On a prouvé P.
Or P =⇒ Q . example (x:Z) (h1: x+3 6 2) : 2*(x+3) 6 4 :=
Donc Q. have h2 : 0 6 (2:Z) := by norm_num
calc
2*(x+3) 6 2*2 := (joli_theoreme (x+3) 2 2)
h2
h1
_ 64 := by norm_num

Exercice [Link].

Soit a un nombre réel dont le carré est au plus 2, et qui est supérieur ou égal à n’importe quel nombre réel dont le
carré est au plus 2. Soit b un nombre réel avec les deux mêmes propriétés. Prouvez que a = b.

[Link] Expression de ∃ et ∀ avec un sous-ensemble

Exercice [Link].

1. Traduire par des assertions commençant par ∀x ∈ R, . . .

a) Pour tout réel x tel que x 6 −2, on a x2 > 4
b) Pour tous réels x et y tels que x 6 y, on a f(x) 6 f(y)
c) ∀x ∈ {1; 2} , x2 − 3x + 2 = 0
2. Traduire par des assertions commençant par ∃x ∈ R, . . .
a) ∃x ∈ {0; 1} , x2 − 3x + 2 = 0
b) Il existe un réel x négatif tel que x2 − 2 = 0.

[Link] Notion de Condition Suffisante

Exercice [Link].

Dans l’exercice [Link], vous avez prouvé que ∀x ∈ {1; 2} , x3 − 3x2 + 2x = 0.

Avez-vous résolu l’équation x3 − 3x2 + 2x = 0 ? Pourquoi ?

Ainsi, vous avez établi que : ∀x ∈ R, x ∈ {1; 2} =⇒ x3 − 3x2 + 2x = 0 , c’est-à-dire que pour tout nombre réel x, x ∈ {1; 2} est

UNE condition suffisante pour que x3 − 3x2 + 2x = 0. Par contre, elle n’est pas nécessaire, car...
Dans les énoncés d’exercices vous aurez des questions du type “Donnez une condition suffisante sur x ∈ E pour que P(x)”. La
question peut se reformuler de la façon suivante :
• Trouvez une assertion C(x) dépendant de x telle que ∀x ∈ E, ? C(x) ? =⇒ P(x)
• Démontrez que ∀x ∈ E, C(x) =⇒ P(x).
Exercice [Link].

1. Ecrivez dans Lean une fonction de deux assertions P et Q exprimant : “P est une condition suffisante pour Q”.
def ConditionSuffisante (P Q : Prop): Prop := sorry

2. Donnez une condition suffisante sur x ∈ R pour que x5 − x4 + x3 − x2 + x − 1 = 0.

6
[Link] Notion de Condition Nécessaire

Exercice [Link] (Notion de CN).

√
1. Résolvez l’équation x + 7 = x + 1.
2. Vérifiez vos calculs en remplaçant la/les valeur(s) trouvée(s) dans l’équation de départ.

√ Au cours de la résolution√ de l’exercice précedent, vous êtes peut-être arrivé-e à “ x = 2 ou x = −3”. Pourtant, si on a bien
2 + 7 = 2 + 1, on n’a pas −3 + 7 = −3 + 1.√
Vous avez donc démontré que ∀x ∈ R, x + 7 =√x + 1 =⇒ x ∈ {2; −3} c’est-à-dire que pour tout nombre réel x, l’assertion

x ∈ {2; −3} est UNE condition nécessaire pour que x + 7 = x + 1. (par contre, ce n’est pas une condition suffisante).
Dans les énoncés d’exercices vous aurez des questions du type “Donnez une condition nécessaire sur x ∈ E pour que P(x)”. La
question peut se reformuler de la façon suivante :
• Trouvez une assertion C(x) dépendant de x telle que ∀x ∈ E, P(x) =⇒ ? C(x) ?
• Démontrez que ∀x ∈ E, P(x) =⇒ C(x).

Exercice [Link].

1. Ecrivez dans Lean une fonction de deux assertions P et Q exprimant : “P est une condition nécessaire pour Q”.
√
2. Donnez une condition nécessaire sur x ∈ R pour que x + 6 = x + 4. Est-elle suffisante ?
3. trouvez une CN, non suffisante, pour qu’un quadrilatère ABCD soit un rectangle
4. trouvez une CS, non nécessaire, pour qu’un quadrilatère ABCD soit un rectangle

1.2.2 Raisonnement par récurrence

import [Link]
import [Link]
import [Link]
Théorème [Link] (Principe de récurrence). example : ∀ n:N, n^2 > n :=
[Link]
-- initialisation
(calc 0^2 > 0 := by norm_num)
Soit n0 un entier naturel. -- hérédité
Considérons une assertion H(n) dépendant d’un entier n, telle que (λ k:N7→
λ ih: k^2 > k 7→
(1) H(n0 ) soit vraie calc
(k+1)^2 = k^2+(2*k+1) := by ring
(2) ∀k ∈ N, ((k > n0 ET H(k)) =⇒ H(k + 1)) _ > k +(2*k+1) := add_le_add_right ih _
_ = (k+1)+2*k := by ring
Alors _ > k+1 :=
le_add_of_nonneg_right
∀n ∈ N, n > n0 =⇒ H(n) ((mul_nonneg
(by norm_num : 2 > 0)
(zero_le k : k > 0)
): 2*k > 0)
)

Démontrer par récurrence

Principe :
• On identifie une assertion H(n) dépendant d’un entier naturel n (“hypothèse de récurrence”)
• On souhaite prouver pour un certain rang n0 donné : ∀n ∈ N, n > n0 , H(n)
• Il suffit de prouver 2 choses :
(i) Initialisation : H(n0 )
(ii) Hérédité : H(n) =⇒ H(n + 1) pour tout entier n > n0 .
Attention : Il faut bien identifier H(n) (en particulier, elle dépend de n donc ne doit pas comporter ∀n)

Exercice [Link].
1. Réécrire le théorème précédent comme une seule phrase quantifiée.
2. Montrez que pour tout n ∈ N, 2n > n
3. Prouvez que l’assertion H(n) : le nombre 4n + 1 est un multiple de 3 est héréditaire. Pouvez-vous trouver un entier n tel
que 4n + 1 est multiple de 3 ?

7
Récurrence double
C’est un cas particulier de raisonnement par récurrence où H(n) est de la forme : P(n) ET P(n + 1).

Exercice [Link].
On considère la suite (Fn )n∈N des nombres de Fibonnacci définie par F0 = 0 et F1 = 1 et ∀n ∈ N, Fn+2 = Fn+1 + Fn .

n
Montrez que ∀n ∈ N, Fn < 35 .

Récurrence finie
C’est un cas particulier de raisonnement par récurrence où, étant donné un entier N fixé, H(n) est de la forme : (n 6 N =⇒ P(n)).
Exemple : cf TD

Récurrence forte
C’est un cas particulier de raisonnement par récurrence où H(n) est de la forme : ∀k ∈ J0; NK , P(k).

Exercice [Link].
1
Soit (un )n∈N la suite définie par u0 = 1 et ∀n ∈ N, un+1 = u20 + u21 + · · · + u2n . Montrez que ∀n ∈ N, un = 1.


n+1

8
1.3 ensembles - equivalence - equations et inéquations

Motivation : En s’appuyant sur la notion de résolution d’équations, et d’inéquations, consolider et formaliser les concepts
d’ensemble et d’équivalence logique
Prérequis
— Manipulations algébriques élémentaires dans R ou C , identités remarquables
— Résolution d’une équation/inéquations du premier et second degré dans R et dans C
— Définition de la racine carrée
Nouvelles notions : équivalence logique ; condition nécessaire et suffisante ; Analyse/Synthèse/Conclusion ; équation, inéqua-
tion ; définition d’un ensemble en compréhension ; intervalles de R
Savoir faire
— Démontrer une assertion du type P ⇐⇒ Q
— Rédiger parfaitement la résolution d’équation (définition de symbole, utilisation appropriée de l’équivalence)
— Résoudre des équations du second degré sans forcément calculer delta (autres techniques : factorisation, forme canonique,
solutions évidentes, somme et produit). Importance donnée à la rédaction logique du raisonnement et non au calcul détaillé
de delta.
— Reconnaitre un raisonnement par CN et un raisonnement par CNS et un raisonnement par CS
— Maitrise de l’utilisation de ⇐⇒
— Résoudre des équations à paramètres
— Résoudre des inéquations dans R (à paramètre ou non) en exprimant l’ensemble solution à l’aide des intervalles de R
— Mener un raisonnement par analyse / synthèse / conclusion

1.3.1 Equivalence logique

Définition [Link].

Etant données deux assertions P et Q, on note P ⇐⇒ Q l’assertion

(P =⇒ Q)ET (Q =⇒ P)

Autres écritures possibles de P ⇐⇒ Q :

• P équivaut à Q
• P si et seulement si Q
• Q si et seulement si P
• P est une condition nécessaire et suffisante pour Q
• Q est une condition nécessaire et suffisante pour P

Nous pourrons démontrer que P =⇒ Q est vraie dans exactement deux cas :
• lorsque P et Q sont vraies toutes les deux
• lorsque P et Q sont fausses toutes les deux
De même que pour l’implication, l’écriture P ⇐⇒ Q n’a d’intérêt que lorsqu’on ne connaît pas les valeurs de vérité de P ou de Q,
c’est à dire en pratique lorsque P et Q dépendent d’une variable non connue. En particulier : ∀x ∈ E, P(x) ⇐⇒ Q(x).

[Link] Démontrer P ⇐⇒ Q (introduction de ⇐⇒)

Une preuve de P ⇐⇒ Q se construit par juxtaposition d’une preuve de P =⇒ Q et d’une preuve de Q =⇒ P.

Exercice [Link].

1. Soit a un nombre rationnel. Montrez que 3a + 1 6 7 si et seulement si a 6 2.

2. Soit x un nombre réel. Montrez que 2x − 1 = 11 si et seulement si x = 6.
3. Soit x un nombre réel. Montrez que x2 + x − 6 = 0 si et seulement si x = −3 ou x = 2.

9
 Remarque : L’équivalence étant transitive, une preuve par équivalences successives est possible à condition de bien veiller
à la conservation de l’équivalence à chaque étape : S1 ⇐⇒ S2 puis S2 ⇐⇒ S3 puis . . .Sn−1 ⇐⇒ Sn permettent de conclure à
S1 ⇐⇒ Sn .

import [Link]
example (x:R) : 4*x+3=0 ↔ x=-3/4 :=
calc
4*x+3=0 ↔ 4*x+3+(-3)=0+(-3) := (add_right_cancel_iff).symm
_ ↔ 4*x = -3 := by ring_nf
_ ↔ 4*x/4 = -3/4 := (div_left_inj’ (by norm_num)).symm
_ ↔ x = -3/4 := by ring_nf

1.3.2 Résoudre une équation

Au § [Link] nous avons vu que ∀x ∈ R, x ∈ {1; 2} =⇒ x3 − 3x2 + 2x = 0 . Ainsi, les nombres 1 et 2 vérifient l’équation, on dit

qu’elles en sont solutions. Pourtant, l’affirmation précédente, quoique correcte, ne garantit pas qu’il n’y a pas d’autre solution. Par
exemple, 03 − 3 × 02 + 2 × 0 = 0.
√
Au § [Link] nous avons vu que ∀x ∈ R, x + 7 = x + 1 =⇒ (x = 2 OU x = −3) . Cela garantit qu’aucune valeur en dehors de

2√et de −3 ne peut être solution de l’équation, mais n’assure pas que ces deux valeurs sont effectivement solutions. D’ailleurs
−3 + 7 6= −3 + 1.
Résoudre une équation c’est déterminer TOUTES les solutions et seulement les solutions (ne pas en oublier, et ne pas en donner
en trop). Résoudre en x ∈ E une équation P(x) consiste donc à trouver une assertion concernant x équivalente à P(x) pour tout
x ∈ E ou encore : trouver une condition nécessaire et suffisante sur x ∈ E pour que P(x).

• Trouvez une assertion C(x) dépendant de x telle que ∀x ∈ E, P(x) ⇐⇒ ? C(x) ?

• Démontrez que ∀x ∈ E, P(x) ⇐⇒ C(x).

Exercice [Link].

Trouvez une condition nécessaire et suffisante sur x ∈ R pour que (x − 3)2 = 2.

[Link] Notation ensembliste en compréhension

Vocabulaire [Link].

Soit P une assertion dépendant d’une variable x et E un ensemble (ou un type) (dit ensemble ou type de référence).
L’ensemble F des éléments x de E vérifiant P(x) se note

F := {x ∈ E | P(x)}

P s’appelle la propriété caractéristique de F. L’ensemble F ne contient que des éléments de E : on dit que c’est un
sous-ensemble de E (ou un ensemble d’éléments de type E).
Etant donné x de E : x ∈ F se lit “x appartient à F” et signifie P(x)

import [Link]
Exercice [Link]. import [Link]

def A := {x:Z | ∃ k:Z, x = 3*k+1 }

1. Montrez que 7 ∈ {x ∈ Z | ∃k ∈ Z, x = 3k + 1} #check A

/ f ∈ RR | f π


2. Montrez que sin ∈ example : 7 ∈ A :=
2 6 f(π)
[Link] 2
(calc (7:Z) = 3*2+1 := by norm_num)

[Link] Egalité et inclusion

Soit E un ensemble de référence (ou type) et A et B des sous-ensembles de E de propriétés caractéristiques respectives PA et PB .

10
 Définition [Link].

• A = B signifie ∀x ∈ E, x ∈ A ⇐⇒ x ∈ B ou encore ∀x ∈ E, PA (x) ⇐⇒ PB (x) (extentionnalité)

• A ⊂ B signifie ∀x ∈ E, x ∈ A =⇒ x ∈ B ou encore ∀x ∈ E, PA (x) =⇒ PB (x)

Théorème [Link].

Soit E un ensemble de référence (ou type) et A et B des Exercice [Link].

sous-ensembles de E. Alors 1. Prouvez le théorème précédent.
A = B ⇐⇒ (A ⊂ B ET B ⊂ A) 2. Montrez que {x ∈ N | (x + 3)(x − 4) = 0} = {4}

3. Soient F := (a; b) ∈ R2 | ∀x ∈ R, aex + be−x = 0

Une égalité ensembliste est une double inclusion. et G := (a; b) ∈ R2 | b = −a . Montrez que F ⊂ G.
[Prouver que deux ensembles sont égaux : 2 choses à faire]

[Link] Différentes formulations

Les énoncés ci-dessous traduisent exactement la même question, dans laquelle la notion d’équivalence logique est sous-jacente :


(i) Résoudre en le réel x l’équation (x − 3)2 = 2 (vii) Montrez que x ∈ R | (x − 3)2 = 2 = {. . .}
(ii) Résoudre dans R l’équation (x − 3)2 = 2 (viii) Montrez que ∀x ∈ R, (x − 3)2 = 2 ⇐⇒ x = . . . OU . . .


(iii) (imprécis) Résoudre (x − 3)2 =2
(ix) (imprécis) Quels sont les réels vérifiant (x − 3)2 = 2 ?
(iv) Soit x ∈ R. Trouvez une CNS sur x pour que (x − 3)2 = 2
(v) Déterminez l’ensemble des réels x vérifiant (x − 3)2 = 2 (x) (imprécis) Déterminez x tel que (x − 3)2 = 2

(vi) Déterminez x ∈ R | (x − 3)2 = 2 (xi) Soit x ∈ R. Donnez une caracérisation de (x − 3)2 = 2

[Link] Equations du second degré : comment éviter delta

Exercice [Link].
Résolvez dans R les équations
Indications :
ci-dessous sans utiliser le discri-
minant : (i) Si a et b sont des nombres réels alors ab = 0 équivaut à a = 0 ou b = 0
(i) (x + 3)(x − 4) = 0 (ii) Identité remarquable
(ii) x2 = 25 (iii) Identité remarquable
(iii) (x + 1)2 −9 = 0 (iv) Une solution évidente ; Le produit des solutions de x2 − sx + p = 0 est p et leur
somme est s.
(iv) x2 +x−2 = 0
(v) Forme canonique
(v) x2 + 2x − 4 = 0

1.3.3 Inéquations

Exercice [Link].
[Prep - inéquations, intervalles]
1. Quel est l’ensemble des nombres réels x tels que x2 > 2 ?
2. Quel est l’ensemble des nombres réels x tels que x2 > 2 ?
3. Quel est l’ensemble des nombres réels x tels que x2 > −2 ?
4. Quel est l’ensemble des nombres réels x tels que x2 < −2 ?

Les inéquations fonctionnent sur le même principe que les équations, à ceci près que l’assertion “dépendant d’un paramètre”
n’est plus une égalité mais une inégalité. Le verbe n’est plus “=” mais l’un des verbes suivants : “<” ; “>” ; “6” ; “>”.
L’ensemble solution d’une inéquation n’est généralement pas constitué d’une ou quelques valeurs isolées, mais d’une infinité
de valeurs. Pour répondre à l’exercice précédent, vous avez dû être confronté(e) à l’écriture des intervalles réels. Confirmez, à
l’aide des définitions ci-dessous, que vos solutions à l’exercice précédent utilisent les notations correctes :

11
 Définition [Link] (Intervalles de R).
Soient a et b deux nombres réels tels que a 6 b. On appelle intervalle tout ensemble de l’une des formes ci-dessous :

[a; b] := {t ∈ R | a 6 t ET t 6 b} [a; +∞[:= {t ∈ R | t > a}

]a; b] := {t ∈ R | a < t ET t 6 b} ]a; +∞[:= {t ∈ R | t > a}
[a; b[:= {t ∈ R | a 6 t ET t < b} ] − ∞; b] := {t ∈ R | t 6 b}
]a; b[:= {t ∈ R | a < t ET t < b} ] − ∞; b[:= {t ∈ R | t < b}

1.3.4 Avec un ou plusieurs paramètres

Exercice [Link].
1. Soit m un paramètre réel fixé. Résolvez (en la variable réelle x) : (m + 1)x + 2 − m = 0
2. Soit m un nombre réel. Quel est l’ensemble des nombres réels x tels que (m + 1)x − m2 − m > 0 ?

Attention au statut des symboles : il faut bien identifier les symboles désignant des paramètres (“fixés”) et le symbole désignant
la variable par rapport à laquelle on résoud.
Par exemple dans la q1, l’ensemble cherché Em := {x ∈ R | (m + 1)x + 2 − m = 0} dépendant de m qui est fixé mais pas de x
qui est liée dans l’écriture ensembliste.
import [Link]
def P (m:R ) (x:R) := (m+1) * x + 2 - m = 0
def E := {x: R | P m x } -- error : undefined m
def F (m:R) := { x : R | P m x }
def G (m:R) (x:R) := { x : R | P m x } -- warning : unused x

1.3.5 Raisonnement par Analyse / Synthèse / Conclusion

Ce type de raisonnement est utilisé lorsque, étant donnée une assertion P dépendant d’une variable x ∈ E, on souhaite
démontrer une assertion du type ∀x ∈ E, P(x) ⇐⇒ C(x) mais que la condition C(x) est à trouver.
En pratique, les questions ressemblent à “Trouver une condition nécessaire et suffisante (CNS) pour que...” ou à “Donnez une
caractérisation de ...” ou “ Déterminez l’ensemble ...”.
analyse : Etant donné x ∈ E, on suppose P(x) et on cherche tout ce qu’on peut en déduire. Cette étape permet d’établir une
condition N(x) nécessaire pour que P(x) soit vérifiée, pour tout x ∈ E. En exploitant l’information contenue dans P(x), on
essaye de choisir N(x) la plus contraignante, restrictive, précise, possible. A ce stade on a prouvé

∀x ∈ E, P(x) =⇒ N(x) ou encore : {x ∈ E | P(x)} ⊂ {x ∈ E | N(x)}

synthèse : On essaye de prouver ∀x ∈ E, N(x) =⇒ P(x).

• Si ça marche, en posant C := N, on a trouvé la condition nécessaire et suffisante cherchée.
• Sinon, c’est que l’analyse a perdu un peu d’information en passant de P(x) à N(x). On peut
— soit retoucher approfondir l’analyse (en essayant de soutirer encore plus d’information de P(x)) pour aboutir à
une condition nécessaire N 0 (x) qui elle sera, espérons le, suffisante.
— soit diviser N(x) en deux cas : N(x) ⇐⇒ F(x) OU C(x) de sorte que ∀x ∈ E, F(x) =⇒ (NON (P(x))) et ∀x ∈
E, C(x) =⇒ P(x). Alors une condition nécessaire et suffisante répondant au problème est C(x).
Conclusion : On conclut : ∀x ∈ E, P(x) ⇐⇒ C(x)
Le raisonnement par analyse-synthèse-conclusion s’utilise aussi pour prouver l’existence et l’unicité.
Montrez ∃!x ∈ E, P(x)
Analyse : On prouve P(x) =⇒ x = a pour un élément a à déterminer. Ceci établit la partie unicité.
Synthèse : On prouve x = a =⇒ P(x). Ceci établit la partie existence.

Exercice [Link].
√
1. Trouvez une condition nécessaire et suffisante sur x ∈ [−3; +∞[ pour que x − 3 = x + 3.

2. Déterminez (a; b) ∈ R2 | ∀x ∈ R, a cos x + b sin x = 0 .
3. Montrez qu’il existe un unique nombre rationnel a tel que ∀x ∈ Q, (x > 1 ET x 6 3) =⇒ (a − x)2 6 1.

12
1.4 compléments de logique propositionnelle : la négation

Motivation :
Prérequis
— Chapitre 1, séances 1,2,3
Nouvelles notions : ET, OU, Négation d’une assertion ; raisonnement par la contraposée ; raisonnement par l’absurde
Savoir faire
— Calculer la négation d’une formule propositionnelle
— Calculer la négation d’une formule quantifiée avec ∀ ou ∃
— Conduire un raisonnement par la contraposée
— Conduire un raisonnement par l’absurde
— Faire des preuves en logique propositionnelle

1.4.1 ET, OU

Vocabulaire [Link] (ET, OU).

On définit ET et OU par leur introduction et leur élimination.

Introduction de ET : pour prouver P ET Q, on donne une preuve de P suivie d’une preuve de Q.
Elimination de ET : Si P ET Q est une hypothèse, on a accés à une preuve de P et à une preuve de Q.
Introduction à gauche de OU : pour prouver P OU Q, on donne une preuve de P
Introduction à droite de OU : pour prouver P OU Q, on donne une preuve de Q
Elimination de OU : Si P OU Q est une hypothèse, on peut déduire une conclusion R d’une preuve de P =⇒ R et
d’une preuve de Q =⇒ R (méthode de la disjonction de cas).

Proposition [Link] (Propriétés).

Soient A, B, C des assertions quelconques.

(i) A ET B ⇐⇒ B ETA (on dit que ET est commutative)
(ii) OU est commutative
(iii) A ET (B ET C) ⇐⇒ (A ET B) ET C (on dit que ET est associative)
(iv) OU est associative
(v) A OU (B ET C) ⇐⇒ (A OU B) ET (A OU C) (on dit que OU est distributive par rapport à ET )
(vi) ET est distributive par rapport à OU

1.4.2 Le Faux et la Négation

Vocabulaire [Link] (le FAUX).

Le FAUX est une assertion qui n’a pas d’introduction (on ne peut pas en construire de preuve), mais dont l’élimination
permet de construire une preuve de n’importe quelle assertion. (Si les poules ont des dents, on peut mettre paris en
bouteille). Ce principe s’appelle le principe d’explosion, ou ”ex falso“.

Proposition [Link].

Pour toute assertion P, on a FAUX =⇒ P

Démonstration. Ex falso.

13
 Définition [Link].

On appelle négation d’une assertion P, et on note NON P , l’assertion P =⇒ FAUX.

Conséquence : prouver NON P, c’est supposer P et aboutir à une contradiction.

Remarque : on a P =⇒ NON NON P car si P est vraie, alors (P =⇒ FAUX) =⇒ FAUX ce qui est exactement NON NON P.

1.4.3 Tiers exclu Lois de De Morgan

Proposition [Link] (Tiers exclu et Lois de De Morgan).

Soient A et B deux assertions.

• Axiome du Tiers Exclu : A ⇐⇒ NON NON A
• NON (A OU B) est équivalente à ( NON A) ET ( NON B)
• NON (A ET B) est équivalente à ( NON A) OU ( NON B)

1.4.4 Négation des quantificateurs

Proposition [Link].

• NON (∀x ∈ E, P(x)) équivaut à . . .

• NON (∃x ∈ E, Q(x)) équivaut à . . .

Exercice [Link] (généralisation - contre exemple à th bidon (fausse négation)).

1. Complétez la règle ci-dessus

2. V ou F ? ∀u ∈ R, ∀b ∈ R, (u + b)2 = u2 + b2
3. V ou F ? ∀u ∈ R, ∀b ∈ R, (u + b)2 6= u2 + b2

Exercice [Link].

Soit f une fonction de R dans R. Exprimez la négation de ∃M ∈ R, ∀x ∈ R, (x < 0 OU f(x) > M).

montrer qu’une assertion est fausse On montre que sa négation est vraie.

Exercice [Link].

Montrez qu’il existe une fonction positive f de R dans R et un nombre réel λ tels que λ · f n’est pas positive.

1.4.5 La contraposée

Définition [Link].

L’implication (NON (Q) =⇒ (NON (P)) est appelée contraposée de l’implication P =⇒ Q.

14
 Proposition [Link].

Une implication est équivalente à sa contraposée : ((NON (Q)) =⇒ (NON (P))) ⇐⇒ (P =⇒ Q)

Démonstration. Se démontre avec une table de vérité ou en utilisant les propriétés des assertions.

Exercice [Link].

Montrez (en utilisant la contraposée) que n2 pair =⇒ n pair

1.4.6 Négation d’une implication

Proposition [Link].

(NON (P =⇒ Q)) ⇐⇒ (P ET (NON (Q)))

Signification : Prouver que ∀x ∈ E, P(x) =⇒ Q(x) est fausse revient à prouver que ∃x ∈ E, (P(x) ET NON (Q(x))), c’est-à-dire
trouver un contre-exemple x pour lequel P(x) est vraie alors que Q(x) est fausse.
Démonstration. Se démontre avec une table de vérité ou en utilisant les propriétés des assertions.

Exercice [Link].
La définition de limn→∞ un = +∞ est : ∀A ∈ R, ∃n0 ∈ N, ∀n ∈ N, n > n0 =⇒ un > A.
Quelle est sa négation ?

1.4.7 Raisonnement par l’absurde

Proposition [Link].

Le raisonnement par l’absurde se base sur la propriété suivante :

P ⇐⇒ ((NON (P)) =⇒ FAUX)

Démonstration. Se démontre avec une table de vérité ou en utilisant les propriétés des assertions.

Conséquence : Pour prouver que P est vraie, on peut supposer qu’elle est fausse et aboutir à une contradiction
Remarque : A réserver lorsque la démonstration directe semble trop difficile.

Exercice [Link].
x+1
1. Montrez que pour tout nombre réel x différent de −2 on a : 6= 1.
x+2
√
2. (*) Montrez que 2 n’est pas un nombre rationnel.

15
16
1.5 opérations sur les ensembles

Motivation : Aborder les principales opérations ensemblistes

Prérequis : chapitre 1.1 à 1.4 ; cours de Lycée sur les ensembles
Nouvelles notions : Intersection (∩), réunion (∪), complémentaire ; Produit cartésien (×) ; Ensemble des parties (P (E)) ; Familles indexées ( (an )n∈I )
Savoir faire
• Faire un diagramme de Venn
• Prouver une inclusion d’ensembles
• Prouver une égalité d’ensembles
• Faire la distinction entre inclusion et égalité d’ensembles
• Faire le lien avec les connecteurs logiques, sans toutefois confondre les natures d’objets
• Déterminer l’ensemble des parties d’un ensemble fini
• Maitriser la distinction entre ⊂ (est inclus dans) et ∈ (appartient à)

1.5.1 Description d’un ensemble

On a déjà abordé la notation d’un ensemble en compréhension, défini par sa propriété caractéristique : {x ∈ E | P(x)}.
On peut aussi définir un ensemble fini en extension : si E est un ensemble de référence, n ∈ N et x1 , . . . , xn ∈ E alors :
{x1 , x2 , . . . , xn } := {x ∈ E | x = x1 OU x = x2 OU . . . OU x = xn }
Un ensemble est uniquement caractérisé par l’appartenance des éléments. Consésquences :
? pas de notion d’ordre : {a; b; c} = {c; b; a}
 √   √ 
3 2 π 3
? pas de répétition : 4; ; 2 ; cos = 4;
2 6 2

Définition [Link] (Ensemble vide, singleton).

• On appelle ensemble vide et on note ∅ l’ensemble qui ne contient aucun élément.

• Un ensemble contenant un seul élément s’appelle un singleton.

Remarque [Link]. Ne pas confondre le singleton {0} avec l’ensemble vide ∅.

1.5.2 Complémentaire

Définition [Link] (Complémentaire).

Soit E un ensemble et A un sous-ensemble de E. On appelle complémentaire de A dans E et on note {E A l’ensemble des

éléments de E qui n’appartiennent pas à A : {E A := {x ∈ E | x ∈
/ A}

Remarque : s’il n’y a pas d’ambiguïté, {E A peut aussi être noté {A ou A ou c A

Proposition [Link].

Exercice [Link].
(i) {E {E A = A
(ii) {E ∅ = E
1. Démontrez la proposition [Link], (iv).
(iii) {E E = ∅
(iv) A ⊂ B ⇐⇒ {E B ⊂ {E A
Figure 1 – Complémentaire

1.5.3 Intersection et réunion

Dans cette partie, on considère A et B deux sous-ensembles d’un ensemble E.

[Link] Définitions

Définition [Link] (Intersection).

On appelle intersection de A et de B et on note A ∩ B l’ensemble des éléments de E qui

appartiennent simultanément à A et à B :
A ∩ B := {x ∈ E | x ∈ A ET x ∈ B}
On dit que A et B sont disjointes si et seulement si A ∩ B = ∅

Figure 2 – Intersection
Attention : L’intersection ne se note PAS “n”.

17
 Définition [Link] (Différence ensembliste).

On appelle différence de A et B (“A privé de B”) et on note A \ B l’ensemble des éléments de E qui appartiennent à A mais pas à B :
A \ B := {x ∈ A | x ∈ / B}

Attention : La différence ensembliste ne se note PAS “/” ni “−” . Remarque : A \ B = A ∩ {E B et aussi A \ B = {A (A ∩ B)

Définition [Link] (Réunion).

On appelle réunion de A et de B (“A union B”) et on note A ∪ B l’ensemble des éléments

de E qui appartiennent à A ou à B (ou inclusif) :
A ∪ B := {x ∈ E | x ∈ A OU x ∈ B}

Figure 3 – Réunion
Attention : La réunion ne se note PAS “u”.

Exercice [Link]. Proposition [Link].

# √ "!! ∩ et ∪ sont commutatives et associatives.

√ 1
 
2
Ecrivez − 2; \ {−1; 1} ∪ [0; 0, 5] ∩ −1; comme
3 4
réunion d’intervalles.
Démonstration. Cela résulte de la commutativité et de l’associativité de ET et de
OU.
[Link] Distributivité
[Link] Loi de de Morgan Soient A, B, C trois sous-ensembles de E.

Proposition [Link].
Proposition [Link]. Exercice [Link].

• {E (A ∩ B) = {E A ∪ {E B
i) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C) Retrouvez l’assertion (ii)) en utilisant (i)) et
• {E (A ∪ B) = {E A ∩ {E B (duale)
ii) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) (duale) les lois de De Morgan.

Démonstration. Cela résulte des lois de De Morgan pour

les assertions. Démonstration. Cela résulte de la distributivité de ET par
rapport à OU et de la distributivité de OU par rapport à
ET.

1.5.4 Récapitulatif : ensembles / propriétés caractéristiques

Soit E un ensemble, A et B deux sous-ensembles de E de propriétés caractéristiques respectives PA et PB .

• A ⊂ B signifie : ∀x ∈ E, PA (x) =⇒ PB (x)
• A = B signifie : ∀x ∈ E, PA (x) ⇐⇒ PB (x)
Soit maintenant x un élement de E.
• x ∈ {E A signifie : NON (PA (x))
• x ∈ A ∩ B signifie : PA (x) ET PB (x)
• x ∈ A ∪ B signifie : PA (x) OU PB (x)

1.5.5 Ensemble des parties

Définition [Link].
Exercice [Link].

Soit E un ensemble. On appelle ensemble des parties de E et on note P(E)

Soit E := {a; b}. Déterminer P(E) puis P(P(E)).
l’ensemble des sous-ensembles de E.
Combien d’éléments possède E ? P(E) ? P(P(E)) ?
Propriété caractéristique : X ∈ P(E) ⇐⇒ X ⊂ E

Remarque [Link].

• L’existence d’un tel ensemble est assurée par l’un des 6 axiomes de la théorie des ensembles.
• On peut en démontrer l’unicité (considérer deux ensembles P et P 0 vérifiant cette propriété caractéristique et montrer qu’il sont égaux)

18
1.5.6 Ensembles de nombres
N Ensemble des entiers naturels
Z Ensemble des entiers relatifs
Exercice [Link].
D Ensemble des nombres décimaux
Q Ensemble des nombres rationnels
Soient a et b deux nombres réels avec a 6 b.
R Ensemble des nombres réels
Rappelez la définition des intervalles ci-dessous :
C Ensemble des nombres complexes [a; b] ]a; b] [a; b[ ]−∞; b] [a; +∞[ ]a; b[ ]−∞; b[
• On a les inclusions : N ⊂ Z ⊂ D ⊂ Q ⊂ R ⊂ C ]a; +∞[

• Notation R∗ : signifie R \ {0}

• Notation R+ : signifie {x ∈ R | x > 0} etc (N∗ , Z− , ...)

1.5.7 Produit cartésien

Définition [Link] (Produit cartésien).

1
Soient E et F deux ensembles.
On appelle produit cartésien de E et de F, et on note E × F l’en-
semble des couples (x; y) où x ∈ E et y ∈ F
Par définition, (a; b) = (a 0 ; b 0 ) signifie F := [0; 1]
 E × F = [1; 2] × [0; 1]
a = a0
b = b0

0 1 E := [1; 2] 2

Exercice [Link].

Exercice [Link].
Considérez d’une part (x; y) et d’autre part {x; y}. Que deviennent-ils chacun si
x = y ? Et si on échange x et y ?
Démontrez cette proposition.

Proposition [Link].

Exercice [Link].
(i) A × B = ∅ ⇐⇒ A = ∅ OU B = ∅
(ii) Si A 6= ∅ et B 6= ∅ alors A × B ⊂ A 0 × B 0 ⇐⇒ A ⊂ A 0 ET B ⊂ B 0 Ecrire l’ensemble (R × R) \ ([−1; 1] × [2; 3])
(iii) Si A 6= ∅ et B 6= ∅ alors A × B = A 0 × B 0 ⇐⇒ A = A 0 ET B = B 0 sous la forme d’une réunion de produits carté-
(iv) (A ∩ B) × C = (A × C) ∩ (B × C) siens.
(v) (A ∪ B) × C = (A × C) ∪ (B × C)

1.5.8 Produit cartésien généralisé

[Link] Familles finies

Il est identique de considérer (a; (b; c)) ou ((a; b); c).
Ainsi, nous pouvons identifier E × (F × G) et (E × F) × G, et cet ensemble peut être noté E × F × G : on a une propriété d’associativité du produit cartésien.
En généralisant, si A1 , . . . , An sont des ensembles on peut considérer l’ensemble A1 × · · · × An des n-uplets (a1 , . . . , an ) où ai ∈ Ai pour chaque
i ∈ {1; . . . ; n}.
Si tous les Ai sont égaux à un même ensemble A, alors on note An := A × · · · × A
| {z }
n fois
Exemple : R2 : ensemble des coordonnées des points du plan.

[Link] Famille d’éléments de E indexée par un ensemble I

• E3 = E × E × E contient des triplets de la forme (e1 ; e2 ; e3 ) avec ei ∈ E pour i = 1 . . . 3
• En = E × · · · × E contient des n-uplets de la forme (e1 ; · · · ; en ) avec ei ∈ E pour i = 1 . . . n
| {z }
n fois

• En généralisant : EI contient des familles de la forme (ei )i∈I avec ei ∈ E pour i ∈ I

Exemple : RN est l’ensemble des suites réelles. La suite réelle constante (un )n∈R définie par : ∀n ∈ N, un = 1 est un élément de RN .

Remarque. On pourrait considérer e := (ei )i∈I comme une application de I dans E : alors on noterait e : I → E au lieu de (ei )i∈I et e(i) au lieu de ei . Ainsi
une suite réelle (un )n∈N est une application u de N dans R.

19
20