Cours

I. Rudiment de la logique

Définition : Quantificateurs

Les quantificateurs sont des symboles utilisés pour raccourcir une phrase mathématique.

Le quantificateur "\(\exists\)" correspond à "il existe ... tel que", et le quantificateur "\(\forall\)" à "pour tout ...,".

Exemple

"Une fonction \(f : \mathbb{R} \longrightarrow \mathbb{R}\) s'annule" s'écrit symboliquement

\[\exists x\in \mathbb{R}, \quad f(x) = 0.\]

Attention

Nous n'utilisons pas les quantificateurs en guise d'abrévation.

Exemple

Il n'est pas rigoureux d'écrire "\(\forall x\) réel, nous avons \(x^2\) positif".

Remarque

Nous rencontrerons également le symbole "\(\exists !\)" correspondant à "il existe un unique ... tel que".

Exemple

La phrase "Pour tout réel \(x\), il existe un unique entier relatif \(n\) tel que \(n\leq x< n+1\)." s'écrit avec des quantificateurs

\[\forall x\in \mathbb{R}, \quad \exists ! n\in \mathbb{Z}, \quad n\leq x<n+1.\]

Il s'agit ici de la partie entière d'un réel.

Remarque

Dans une phrase mathématique écrite avec des quantificateurs, nous pouvons intervertir les symboles identiques et uniquement les symboles identiques. Autrement dit nous ne pouvons pas intervertir les symboles "\(\forall\)" et "\(\exists\)".

Exemple

La phrase

\[\forall y\in \mathbb{R}_+, \quad \exists x \in \mathbb{R}, \quad y = x^2\]

signifie que tout réel positif admet une racine carrée. Alors que la phrase

\[\exists x\in \mathbb{R}, \quad \forall y \in \mathbb{R}_+, \quad y = x^2\]

signifie que tout les réels positifs sont égaux.

Définition : Assertion

Une assertion est une phrase mathématique qui peut être vraie ou fausse.

Exemple

L'assertion "2 est paire" est vraie et l'assertion "0 est la partie entière de \(- \frac{1}{2}\)" est fausse.

Définition : Implication

Une implication est une relation par laquelle une assertion \(A\) en implique une autre \(B\). On le note \(A \Longrightarrow B\).

Exemple

\[ \forall x \in \mathbb{R}, \quad x \geq 1 \quad \Longrightarrow \quad x^2 \geq 1.\]

Définition : Equivalence

Une équivalence est une relation par laquelle une assertion \(A\) en implique une autre \(B\) qui implique également la première assertion \(A\). On le note \(A \Longleftrightarrow B\).

Exemple

\[ \forall x\in \mathbb{R}, \quad x\geq 0 \quad \Longleftrightarrow \quad e^x \geq 1.\]

Remarque

Pour démontrer une équivalence on peut raisonner par équivalences successives ou par double implications.

Exemples

Par équivalences successives

Soit \(x \in \mathbb{R}\). Alors on peut montrer par équivalences successives que \(2x + 3 \geq 4 \Longleftrightarrow x \geq \dfrac{1}{2}\). En effet

\[2x + 3 \geq 4 \quad \Longleftrightarrow \quad 2x \geq 4 - 3 = 1 \quad \Longleftrightarrow \quad x \geq \dfrac{1}{2}.\]

Par double implications

On peut montrer par double implication que, pour \(m\in \mathbb{R}\), la fonction \(f\), définie par \(f(x) = mx + 1\) pour tout \(x\in \mathbb{R}\), garde un signe constant sur \(\mathbb{R}\) si et seulement si \(m = 0\).

Si $ m = 0$ alors \(f = 1\). Donc la fonction \(f\) est toujours positive. Donc la fonction \(f\) garde un signe constant.

Récriproquement si la fonction \(f\) garde un signe constant sur \(\mathbb{R}\). Or \(f(0) = 1 \geq 0\), donc la fonction \(f\) est toujours positive sur \(\mathbb{R}\). Ainsi pour tout \(x\in \mathbb{R}^*\), \(0\leq f(x) = mx + 1\) et \(0\leq f(-x) = -mx+1\). Donc \(m\geq - \dfrac{1}{x}\) et \(m\leq \dfrac{1}{x}\). Donc \(m \in \cap_{x\in \mathbb{R}^*} \left[ -\dfrac{1}{x}, \dfrac{1}{x} \right] = \{0\}\), d'où \(m=0\).

On aurait aussi pu montrer la seconde implication par contraposée : Si \(m\neq 0\) alors la fonction \(f\) change de signe.

Définition : Négation (ou contraire)

On considère une assertion \(A\). Alors la négation de l'assertion \(A\) est le contraire de l'assertion \(A\) et on la note \(non(A)\). Autrement dit l'assertion \(non(A)\) est vraie si et seulement si l'assertion \(A\) est fausse.

Exemple

La négation de "\(0\) est un nombre pair" est "\(0\) est un nombre impair".

Proposition : Opérations logiques

On considère deux assertions \(A\) et \(B\). Alors les assertions suivantes sont vraies :

• \(A \text{ et } (B \text{ ou } C) \Longleftrightarrow (A \text{ et } B) \text{ ou } (A \text{ et } C),\)

• \(A \text{ ou } (B \text{ et } C) \Longleftrightarrow (A \text{ ou } B) \text{ et } (A \text{ ou } C),\)

• \(non(non(A)) \quad \Longleftrightarrow \quad A,\)

• \(non(A \text{ et } B) \quad \Longleftrightarrow \quad [non(A) \text{ ou } non(B)],\)

• \(non(A \text{ ou } B) \quad \Longleftrightarrow \quad [non(A) \text{ et } non(B)],\)

• \([A \Longrightarrow B] \quad [non(A) \text{ ou } B]\),

• \(non(A \Longrightarrow B) \quad \Longleftrightarrow \quad [A \text{ et } non(B)].\)

Démonstration

• On suppose que l'assertion \(non(non(A))\) est vraie. Donc l'assertion \(non(A)\) est fausse. Donc l'assertion \(A\) est vraie.

Réciproquement on suppose que l'assertion \(A\) est vraie. Donc l'assertion \(non(A)\) est fausse. Donc l'assertion \(non(non(A))\) est vraie. Par conséquent nous avons montré l'équivalence par double implication.

• On suppose que l'assertion \(non(A \text{ et } B)\) est vraie. Alors l'assertion "\(A \text{ et } B\)" est fausse. Donc l'assertion \(A\) ou l'assertion \(B\) est fausse. Donc l'assertion "\(non (A) \text{ ou } non(B)\)" est vraie.

Réciproquement on suppose que l'assertion "\(non(A) \text{ ou } non(B)\)" est vraie. Alors l'assertion \(non(A)\) ou l'assertion \(non(B)\) est vraie. Donc l'assertion \(A\) ou l'assertion \(B\) est fausse. Donc l'assertion "\(A \text{ et } B\) est fausse. Donc l'assertion \(non(A \text{ et } B)\) est vraie. Par conséquent nous avons montré le résultat par double implication.

• On procède de même.

• On suppose que l'assertion \(A \Longrightarrow B\) est vraie. Procédons par disjonction de cas. Si l'assertion \(A\) est fausse alors l'assertion "\(non(A) \text{ ou } B\)" est vraie. De même si l'assertion \(A\) est vraie alors, d'après \(A \Longrightarrow B\) vraie, l'assertion \(B\) est vraie donc l'assertion "\(non(A) \text{ ou } B\)" est également vraie.

Réciproquement on suppose que l'assertion "\(non(A) \text{ ou } B\)" est vraie. On suppose l'assertion \(A\) vraie. Alors l'assertion \(non(A)\) est fausse et, comme l'assertion "\(non(A) \text{ ou } B\)" est vraie, l'assertion \(B\) est vraie. Nous avons donc bien montré que l'assertion \(A\Longrightarrow B\) est vraie.

Exemple

On considère un entier relatif \(n\in \mathbb{Z}\), l'assertion \(A\) : "\(n\) est un multiple de 4" et l'assertion B : "\(n\) est un multiple de 2".

Alors l'assertion \(A \Longrightarrow B\) est vraie, autrement dit l'assertion \(non(A \Longrightarrow B)\) est fausse. Qu'en est-il de l'assertion "\(A \text{ et } non(B)\)" ? Cette correspond à "\(n\) est un multiple de 4 et n'est pas un multiple de \(2\)" ce qui est une assertion également fausse.

Proposition : Négation avec des quantificateurs

On considère une assertion de la forme

\[\forall x\in E, \quad \exists y \in F, \quad A(x,y),\]

avec \(E\) et \(F\) deux ensembles et \(A\) une assertion dépendant de \(x\) et \(y\). Alors la négation de cette assertion est l'assertion suivante :

\[\exists x\in E, \quad \forall y \in F, \quad non(A(x,y)).\]

Autrement dit pour nier une assertion avec des quantificateurs, il suffit de transformer les "\(\forall\)" en "\(\exists\)" et inversement et de nier la conclusion.

Démonstration

Procédons étape par étape. Pour \(x \in E\), on note \(B(x)\) l'assertion "\(\exists y \in F, \quad A(x,y)\)". Alors la négation de l'assertion "\(\forall x\in E, \quad B(x)\)" est

\[\exists x\in E, \quad non(B(x)).\]

Puis la négation de \(B(x)\) pour tout \(x\in E\), est donnée par

\[\forall y\in F, \quad non(A(x,y)).\]

On en déduit le résultat souhaité en combinant ces deux résultats.

Exemple

La négation de l'assertion "la fonction \(f : \mathbb{R} \longrightarrow \mathbb{R}\) s'annule" est symboliquement

\[\forall x\in \mathbb{R}, \quad f(x) \neq 0.\]

Définition : Contraposée

La contraposée d'une implication de \(B\) par \(A\) est l'implication de \(non(A)\) par \(non(B)\).

Exemple

Le théorème de Pythagore est : si un triangle est rectangle alors le carré de la longueur du grand côté est égal à la somme des carrés des longueurs des deux autres côtés. Donc la contraposée du théorème de Pythagore est : si le carré de la longueur du grand côté n'est pas égal à la somme des carrés des longueurs des deux autres côtés alors le triangle n'est pas rectangle.

Proposition : Démonstration par contraposée

On considère \(A\) et \(B\) deux assertions. Alors nous avons l'équivalence suivante :

\[ [A \quad \Longrightarrow \quad B] \quad \Longleftrightarrow \quad [non(B) \quad \Longrightarrow \quad non(A)].\]

Autrement dit pour montrer une implication, il peut être intéressant de monstrer sa contraposée.

Démonstration

On suppose l'implication \(A \Longrightarrow B\). On souhaite montrer l'implication \(non(B) \Longrightarrow non(A)\). On suppose alors que l'assertion \(non(B)\) est vraie et on souhaite montrer que l'assertion \(non(A)\) est vraie. On suppose par l'absurde que l'assertion \(non(A)\) est fausse, autrement dit que l'assertion \(A\) est vraie. Alors, d'après l'implication \(A \longrightarrow B\), l'assertion \(B\) est vraie ce qui est contradictoire avec notre supposition que l'assertion \(non(B)\) est vraie. Par conséquent l'assertion \(non(A)\) est vraie. Nous avons donc bien montré que \(non(B) \Longrightarrow non(A)\). Réciproquement on suppose l'implication \(non(B) \Longrightarrow non(A)\). Alors, d'après ce qui précède, \(non(non(A)) \Longrightarrow non(non(B))\). Or \(non(non(A)) = A\) et \(non(non(B))\), donc \(A \Longrightarrow B\).

Exemple

On considère un entier naturel \(n\in \mathbb{N}\). Nous pouvons montrer par contraposée que si l'entier \(n^2\) est pair alors l'entier \(n\) est pair également. La contraposée est si l'entier \(n\) est impair alors son carré l'est également. En effet si l'entier \(n\) est impair alors il existe un entier \(k\in \mathbb{N}\) tel que \(n = 2k+1\). Ainsi, par identité remarquable,

\[n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + = 2k'+1,\]

où l'on a noté l'entier \(k' = 2k^2 + 2k \in \mathbb{N}\). Ainsi l'entier \(n^2\) est impair.

Définition : Raisonnement par disjonction de cas

Lorsque la démonstration d'une propriété dépend de la valeur d'une variable, il est parfois utile de séparer le raisonnement suivant toutes les valeurs que peut prendre la variable.

Exemple

On considère un entier naturel \(n\in \mathbb{N}\). Alors on peut montrer par disjonction de cas que les entiers \(n\) et \(n^2\) ont la même parité. Les deux cas possibles sont soit l'entier \(n\) est pair soit l'entier \(n\) est impair. Si l'entier \(n\) est pair alors il existe \(k\in \mathbb{N}\) tel que \(n=2k\), ainsi \(n^2 = 4k^2 = 2(2k^2)\) est également un entier pair. Et si l'entier \(n\) est impair alors, d'après l'exemple précédent, l'entier \(n^2\) est également impair.

Définition : Raisonnement par l'absurde

Le raisonnement par l'absurde consiste à supposer qu'une propriété est fausse et d'arriver à une contradiction ce qui montre que la propriété est vraie.

Exemple

On peut montrer par un raisonnement par l'absurde que le nombre réel \(\sqrt{2}\) n'est pas rationnel \(\sqrt{2} \notin \mathbb{Q}\). En effet si l'on suppose par l'absurde que le nombre réel \(\sqrt{2}\) est rationnel alors il existe deux entiers \(p\in \mathbb{Z}\) et \(q\in \mathbb{N}^*\) tels que

\[\sqrt{2} = \dfrac{p}{q}.\]

On considère le plus grand commun diviseur \(d\) (PGCD) entre les entiers \(p\) et \(q\). Alors il existe deux entiers \(p'\in \mathbb{Z}\) et \(q' \in \mathbb{N}^*\) premiers entre eux tels que \(p = dp'\) et \(q = dq'\). Ainsi

\[\sqrt{2} = \dfrac{dp'}{dq'} = \dfrac{p'}{q'}.\]

Donc, en élevant au carré,

\[2 = \dfrac{{p'}^2}{{q'}^2}.\]

Autrement dit

\[{p'}^2 = 2 {q'^2}.\]

Ainsi, d'après l'exemple précédent, l'entier \(p'\) est pair : il existe un entier \(p''\in \mathbb{Z}\) tel que \(p' = 2p''\). Donc

\[2 = \dfrac{4 {p''}^2}{{q'}^2} = 2 \dfrac{2{p''}^2}{{q'}^2}.\]

Autrement dit, après simplification par 2,

\[{q'}^2 = 2 {p''}^2.\]

Donc, encore d'après l'exemple précédent, l'entier \(q'\) est pair. Nous sommes donc arrivés à la contradiction : \(p'\) et \(q'\) sont deux entiers pairs premiers entre eux. Par conséquent l'hypothèse faite au début \(\sqrt{2}\in \mathbb{Q}\) est fausse. Donc \(\sqrt{2} \notin \mathbb{Q}\).

Remarque

Un raisonnement par l'absurde est souvent similaire à un raisonnement par contraposée. Si l'on souhaite montrer l'implication \(A \Longrightarrow B\) par l'absurde alors on suppose \(A\) et \(non(B)\) et on essaye d'arriver à une contradiction comme par exemple \(non(A)\). Cela revient au même que de le montrer par contraposée en supposant \(non(B)\) et en essayant d'arriver à montrer \(non(A)\).

Définition : Raisonnement par analyse-synthèse

Un raisonnement par analyse-synthèse consiste à rechercher des conditions nécessaires et suffisantes sur notre objet pour qu'il vérifie notre problème. Ceci en deux étapes.

• Analyse : On suppose notre objet vérifie notre problème puis on aboutit à des conditions nécessairement verifiées par notre objet.

• Synthèse : On suppose que notre objet vérifie les conditions trouvées à l'analyse puis on vérifie que notre objet vérifie alors notre problème.

Exemple

Pour déterminer les solutions réelles de l'équation

\[x^2 - 3x + 2 = 0,\]

nous pouvons raisonner par analyse-synthèse.

• Analyse : On considère un réel \(x\in \mathbb{R}\) tel que \(x^2 - 3x + 1 = 0\). Or, par utilisation du discriminant ou par reconnaissance de racines évidentes,

\[x^2 - 3x +2 = (x-1)(x-2).\]

Donc, comme un produit est nul si et seulement si l'un des termes est nul, \(x = 1\) ou \(x = 2\).

• Synthèse : Les réels 1 et 2 vérifient l'équation souhaitée :

\[1^2 - 3\times 1 + 2 = 1 - 3 +2 = 0, \quad 2^2 - 3 \times 2 +2 = 4 - 6 +2 = 0.\]

En conclusion les solutions de l'équation \(x^2 - 3x +2 = 0\) sont exactement 1 et 2. Nous aurions également pu résoudre cette équation par équivalences successives. Soit \(x\in \mathbb{R}\). Alors

\[\begin{array}{cl} & 0 = x^2 - 3x+1 \\ \Longleftrightarrow & 0 = (x-2)(x-1) & \\ \Longleftrightarrow & x = 1 \text{ ou } x = 2 \end{array}\]

Remarque

Le raisonnement par analyse-synthèse est très pratique quand on souhaite montrer l'existence et l'unicité d'une solution à un problème. L'étape de l'analyse montre l'unicité en aboutissant à la condition que l'objet cherché doit exactement être tel objet. L'étape de la synthèse montre l'existence en vérifiant que le ou les objets trouvés à l'analyse vérifient le problème.

Exemple

On cherche la solution au problème

\[\begin{cases} x^2 & + & y & = & 2 \\ x^2 & - & y & = & -1 \end{cases}, \quad (x,y)\in \mathbb{R}_+\]

On raisonne par analyse-synthèse :

• Analyse : On considère \((x,y) \in \mathbb{R}_+^2\) vérifiant le système précédent. Alors

\[1 = 2 - 1 = x^2+y + x^2-y = 2x^2.\]

Donc \(x = \dfrac{1}{\sqrt{2}}\) ou \(x = - \dfrac{1}{\sqrt{2}}\). Or \(x\geq 0\), donc \(x = \dfrac{1}{\sqrt{2}}\). Puis

\[y = 2 - x^2 = 2 - \dfrac{1}{2} = \dfrac{3}{2}.\]

• Synthèse : Le couple \(\left( \dfrac{1}{\sqrt{2}}, \dfrac{3}{2} \right)\) vérifie bien le problème. La première égalité est vérifiée par le calcul précédent et la seconde égalité par

\[x^2 - y = \dfrac{1}{2} - \dfrac{3}{2} = -1.\]

Par conséquent l'unique solution du problème est le couple \(\left( \dfrac{1}{\sqrt{2}}, \dfrac{3}{2} \right)\).

Remarque

L'étape de la synthèse ne doit pas être oubliée.

Exemple

On cherche la solution au problème

\[\begin{cases} x^2 & + & y & = & 2 \\ x^2 & - & y & = & -1 \\ x & + & 2y & = & 1 \end{cases}, \quad (x,y)\in \mathbb{R}_+\]

On raisonne par analyse-synthèse :

• Analyse : D'après l'analyse effectué à l'exemple précédent, nous arrivons à la condition nécessiaire \((x,y) = \left( \dfrac{1}{\sqrt{2}}, \dfrac{3}{2} \right)\).

• Synthèse : Le couple \(\left( \dfrac{1}{\sqrt{2}}, \dfrac{3}{2} \right)\) vérifie bien les deux premières équations du problème mais pas la troisième.

Par conséquent le problème n'admet pas de solution.

Proposition : Raisonnement par récurrence

On considère une assertion \(P(n)\) qui dépend de \(n \in \mathbb{N}\). Si l'assertion \(P(0)\) est vraie (initialisation) et si

\[\forall n \in \mathbb{N}, \quad P(n) \quad \Longrightarrow \quad P(n+1),\]

(hérédité) alors l'assertion \(P(n)\) est vraie pour tout \(n\in \mathbb{N}\).

Démonstration

On suppose l'initialisation et l'hérédité. On considère l'ensemble \(S\) des entiers \(n \in \mathbb{N}\) tels que l'assertion \(P(n)\) soit fausse. On suppose par l'absurde que cet ensemble \(S\) est non vide. Alors l'ensemble \(S\) est un ensemble non vide d'entiers positifs, donc admet un plus petit élément \(n_0\). Ainsi l'assertion \(P(n_0-1)\) est vraie et l'assertion \(P(n_0)\) est fausse par définition du plus petit élément. Ceci est absurde d'après l'hérédité. Par conséquent l'ensemble \(S\) est vide ce qui montre que la propriété \(P(n)\) est vraie pour tout entier \(n\in \mathbb{N}\).

Exemple

On peut montrer par récurrence sur \(n\in \mathbb{N}\) l'assertion \(\mathcal{P}(n)\) : "\(7^n - 1\) est un multiple de 6".

• Initialisation : Pour \(n = 0\), nous avons \(7^0 - 1 = 1 - 1 = 0 = 0\times 6\), donc l'assertion \(\mathcal{P}(0)\) est vraie.

• Hérédité : On considère \(n\in \mathbb{N}\) et on suppoe que l'assertion \(\mathcal{P}(n)\) est vraie. Il existe alors un entier \(k\in \mathbb{N}\) tel que \(7^n - 1 = 6k\). Ainsi

\[7^{n+1} - 1 = 7^{n+1} - 7^n + 7^n - 1 = 7^n(7 - 1) + 6k = 7^n \times 6 + 6k = 6(7^n + k).\]

Donc \(7^n - 1\) est également un multiple de \(6\) ce qui montre que l'assertion \(\mathcal{P}(n+1)\) est également vraie.

Le principe de récurrence permet de conclure.

Remarque

Il est possible d'initialiser la récurrence à \(n_0 \in \mathbb{N}^*\). Dans ce cas la propriété \(P(n)\) sera vérifiée pour tout entier \(n\geq n_0\).

Exemple

On peut montrer par récurrence sur \(n\geq 4\) l'assertion $\mathcal{P}(n) : \(n^2 \leq 2^n\). En effet le résultat est vrai pour les entiers 0, 1 zt 2 mais faux pour l'entier 3 car

\[0^2 = 0 \leq 1 = 2^0, \quad 1^2 = 1 \leq 2 = 2^1, \quad 2^2 = 4 \leq 4 = 2^2, \quad 3^2 = 9 > 8 = 2^3.\]

Puis pour les entiers \(n\geq 4\) :

• Initialisation : L'assertion \(\mathcal{P}(4)\) est vraie car

\[4^2 = 16 \leq 16 = 2^4.\]

• Hérédité : On considère un entier \(n\geq 4\) et on suppose que l'assertion \(\mathcal{P}(n)\) est vraie : \(n^2 \leq 2^n\). Alors, en multipliant par \(2\), nous obtenons \(2 n^2 \leq 2^{n+1}\). Pour conclure nous pouvons montrer que \((n+1)^2 \leq 2n^2\). En effet par identité remarquable nous avons

\[2n^2 - (n+1)^2 = (\sqrt{2}n - (n+1))(\sqrt{2} n + n+1) = ((\sqrt{2}-1)n - 1)((\sqrt{2}+1)n +1),\]

avec \((\sqrt{2}+1)n + 1 \geq 0\) et

\[(\sqrt{2}-1)n - 1 \geq (\sqrt{2}- 1)\times 4 - 1 = 4\sqrt{2} - 5 = 4\left(\sqrt{2} - \dfrac{5}{4} \right) \geq 0.\]

Donc \(2n^2 - (n+1)^2 \geq 0\). Ainsi on obtient

\[2^{n+1} \geq 2n^2 \geq (n+1)^2\]

ce qui montre l'assertion \(\mathcal{P}(n+1)\).

Le principe de récurrence permet de conclure.

Proposition : Raisonnement par récurrence double

On considère une assertion \(P(n)\) qui dépend de \(n \in \mathbb{N}\). Si les assertions \(P(0)\) et \(P(1)\) sont vraies (initialisation double) et si

\[\forall n \in \mathbb{N}, \quad [P(n) \text{ et } P(n+1)] \quad \Longrightarrow \quad P(n+2),\]

(hérédité double) alors l'assertion \(P(n)\) est vraie pour tout \(n\in \mathbb{N}\).

Démonstration

On suppose l'initialistion double et l'hérédité double. On considère l'ensemble \(S\) des entiers naturels \(n \in \mathbb{N}\) tels que l'asserton \(P(n)\) soit fausse. On suppose par l'absurde que cet ensemble \(S\) est non vide. Alors l'ensemble \(S\) admet un plus petit élément \(n_0 \in \mathbb{N}\). D'après l'initialisation double, nous avons \(n_0\geq 2\). Puis, par définition de l'entier \(n_0\), l'assertion $P(n_0) est fausse et les assertions \(P(n_0-2)\) et \(P(n_0-1)\) sont vraies. Ainsi, d'après l'hérédité double, l'assertion \(P(n_0)\) est également vraie ce qui est contradictoire. Par conséquent l'ensemble \(S\) est vide et pour tout entier \(n\), l'assertion \(P(n)\) est vraie.

Exemple

On considère la suite \((u_n)_{n\in \mathbb{N}}\) définie par \(u_0 = u_1 = - 1\) et par

\[\forall n \in \mathbb{N}, \quad u_{n+2} = 5 u_{n+1} - 6u_n.\]

Alors on peut montrer par récurrence double que

\[\forall n \in \mathbb{N}, \quad u_n = 3^n - 2^{n+1}.\]

En effet pour \(n\in \mathbb{N}\), on note \(P(n)\) l'assertion \(u_n = 3^n - 2^{n+1}\).

• Initialisation double : Les assertions \(P(0)\) et \(P(1)\) sont vraies car

\[3^0 - 2^1 = - 1 = u_0, \quad 3^1 - 2^2 = - 1 = u_1.\]

• Hérédité double : On considère un entier \(n\in \mathbb{N}\) et on suppose que les assertions \(P(n)\) et \(P(n+1)\) sont vraies. Alors, d'après la définition de la suite \((u_n)_{n\in \mathbb{N}}\), nous avons

\[u_{n+2} = 5 u_{n+1} - 6 u_n = 5 \times 3^{n+1} - 5 \times 2^{n+2} - 6 \times 3^n + 6 \times 2^{n+1} = (15 - 6)3^n - (20 - 12) 2^n = 3^{n+2} - 2^{n+3},\]

ce qui montre que l'assertion \(P(n+2)\) est également vraie.

Le principe de récurrence double permet de conclure.

Proposition : Raisonnement par récurrence forte

On considère une assertion \(P(n)\) qui dépend de \(n \in \mathbb{N}\). Si l'assertion \(P(0)\) est vraie (initialisation) et si

\[\forall n \in \mathbb{N}, \quad [P(0) \text{ et } ... \text{ et } P(n)] \quad \Longrightarrow \quad P(n+1),\]

(hérédité forte) alors l'assertion \(P(n)\) est vraie pour tout \(n\in \mathbb{N}\).

Démonstration

On suppose l'initialistion et l'hérédité forte. On considère l'ensemble \(S\) des entiers naturels \(n \in \mathbb{N}\) tels que l'asserton \(P(n)\) soit fausse. On suppose par l'absurde que cet ensemble \(S\) est non vide. Alors l'ensemble \(S\) admet un plus petit élément \(n_0 \in \mathbb{N}\). D'après l'initialisation, nous avons \(n_0\geq 1\). Puis, par définition de l'entier \(n_0\), l'assertion $P(n_0) est fausse et les assertions \(P(0)\), ..., \(P(n_0-1)\) sont vraies. Ainsi, d'après l'hérédité forte, l'assertion \(P(n_0)\) est également vraie ce qui est contradictoire. Par conséquent l'ensemble \(S\) est vide et pour tout entier \(n\), l'assertion \(P(n)\) est vraie.

Exemple

On considère la suite \((u_n)_{n\in \mathbb{N}}\) définie par \(u_0 = 1\) et

\[\forall n\in \mathbb{N}, \quad u_{n+1} = u_0 + ... + u_n = \sum_{k=0}^n u_k.\]

Alors on peut montrer par récurrence forte que pour tout \(n\in \mathbb{N}^*\), \(u_n = 2^{n-1}\). En effet, pour \(n\in \mathbb{N}^*\), on note \(P(n)\) l'assertion \(u_n = 2^{n-1}\).

• Initialisation : Pour \(n= 1\), nous avons \(u_1 = u_0 = 1 = 2^{1-1}\).

• Hérédité forte : On considère \(n\in \mathbb{N}^*\) et on suppose que les assertions \(P(1), ..., P(n)\) sont vraies. Alors, d'après la définition de la suite \((u_n)_{n\in \mathbb{N}}\) et l'hypothèse de récurrence forte,

\[u_{n+1} = \sum_{k=0}^n u_k = 1 + \sum_{k=1}^n u_k = 1 + \sum_{k=1}^n 2^{k-1} = 1 + \sum_{l=0}^{n-1} 2^l,\]

où la dernière égalité est un changement d'indice \(k-1 = l\). On reconnaît alors une somme géométrique de raison 2. Donc

\[u_{n+1} = 1 + \dfrac{1 - 2^n}{1-2} = 1 - 1 + 2^n = 2^{n+1-1},\]

ce qui montre bien que l'assertion \(P(n+1)\) est vraie.

Le principe de récurrence forte permet de conclure.

II. Ensembles

Définition : Ensemble

Un ensemble \(E\) est une collection d'objets appelés éléments de \(E\). Si l'objet \(x\) est un élément de \(E\) alors on note \(x \in E\), sinon on écrit \(x\notin E\).

Exemple

Le nombre \(\pi\) appartient à l'ensemble des nombres réels \(\mathbb{R}\) mais pas à l'ensemble des nombres rationnels \(\mathbb{Q}\) :

\[\pi \in \mathbb{R}, \quad \pi \notin \mathbb{Q}\]

Définition : Ensemble vide

L'ensemble vide est l'ensemble qui ne contient aucun élément. On le note \(\emptyset\).

Exemple

\[ \{x\in \mathbb{R}, \quad x^2 < 0\} = \emptyset \]

Remarque

Un ensemble à un élement \(x\) est appelé un singleton et est noté \(\{x\}\), un ensemble à deux éléments \(x,y\) un couple \(\{x,y\}\), un ensemble à trois éléments \(x,y,z\) un triplet \(\{x,y,z\}\). On utilisera bien la notation avec des guillemets \(\{\}\) où l'ordre des éléments n'a pas d'importance et non la notation avec des parenthèses définie dans la suite où l'ordre a de l'importance.

Définition : Partie (ou sous-ensembles)

On dit qu'un ensemble \(F\) est une partie (ou sous-ensemble) d'un ensemble \(E\) si tout élément de l'ensemble \(F\) appartient à l'ensemble \(E\), autrement dit si

\[\forall x\in F, \quad x\in E.\]

On le note \(F\subset E\).

Exemple

Les entiers naturels forment une partie de l'ensemble des entiers relatifs : \(\mathbb{N} \subset \mathbb{Z}\).

Remarque

Pour montrer une égalité entre deux ensembles \(E\) et \(F\), on peut procéder par double inclusion : si \(E\subset F\) et \(F\subset E\) alors \(E = F\).

Exemple

Nous avons l'égalité suivante dans \(\mathbb{R}^2\)

\[\{(t,t), \quad t\in \mathbb{R}\} = \{(x,y) \in \mathbb{R}^2, \quad y = x\}\]

En effet, en notant \(A\) la première partie et \(B\) la seconde, nous procédons de la manière suivante. Soit \((x,y) \in A\). Alors, par définition de la partie \(A\), il existe \(t \in \mathbb{R}\) tel que \(x = t\) et \(y = t\). Donc \(y = x\), d'où, par définition de la partie \(B\), \((x,y) \in B\).

Réciproquement soit \((x,y) \in B\). Alors, par définition de la partie \(B\), nous avons \(y = x\). On considère alors \(t = x\) pour avoir \(t = x = y\), d'où \((x,y) = (t,t)\) ce qui montre bien que \((x,y) \in A\).

Finalement, par double inclusion nous avons montré l'égalité \(A = B\).

Remarque

Un ensemble \(E\) peut être décrit :

• explicitement en énumérant ses éléments s'ils sont en nombre fini,

• par une condition \(A\),

• par paramétrisation de ses éléments.

Exemples

• Soit \(n\in \mathbb{N}\). Alors l'ensemble des entiers compris entre 0 et \(n\) s'écrit

\[\{0, 1, ..., n-1, n\}.\]

• L'ensemble des nombres stricitement positifs se note et s'écrit

\[\mathbb{R}_+^* = \{x\in \mathbb{R}, \quad x>0\}.\]

• La diagonale \(D_1\) du plan \(\mathbb{R}^2\) s'écrit

\[D_1 = \{(t,t), \quad t\in \mathbb{R}\}.\]

Théorème : Le paradoxe de Russel

L'ensemble des ensembles n'est pas un ensemble.

Démonstration

On suppose par l'absurde que l'ensemble \(\mathcal{E}\) de tous les ensembles est un ensemble. Alors nous pouvons considérer la partie \(A\) de l'ensemble \(\mathcal{E}\) définie par

\[A = \{E\in \mathcal{E}, E\notin E\}.\]

Alors l'ensemble \(A\) vérifie ...

Définition : Opérations ensemblistes

On considère un ensemble \(E\) et deux parties \(A\) et \(B\) de l'ensemble \(E\). Alors on définit les opérations suivantes :

• la réunion (ou union) \(A \cup B\) : l'ensemble des éléments de l'ensemble \(E\) appartenant à la partie \(A\) ou à la partie \(B\)

\[ A\cup B = \{ x\in E, \quad x\in A \text{ ou } x\in B\}, \]

• l'intersection \(A \cap B\) : l'ensemble des éléments de l'ensemble \(E\) appartenant à la partie \(A\) et à la partie \(B\)

\[A\cap B = \{ x\in E, \quad x\in A \text{ et } x\in B\},\]

• la différence \(A\backslash B\) : l'ensemble des éléments de l'ensemble \(E\) appartenant à la partie \(A\) mais pas à la partie \(B\)

\[A\backslash B = \{ x\in E, \quad x\in A \text{ et } x\notin B\},\]

• le complémentaire \(A^c\) : l'ensemble des éléments de l'ensemble \(E\) n'appartenant pas à la partie \(A\)

\[A^c = \{ x\in E, \quad x\notin A \}.\]

Exemple

On considère l'ensemble des chiffres $E = {0,..., 9} et les parties \(A,B,C\) définies par

\[A = \{0,2,4,6,8\}, \quad B = \{1,3,5,7,9\}, \quad C = \{0,3,6,9\}.\]

Alors

\[A\cup B = E, \quad A\cup C = \{0,2,3,4,6,8,9\}, \quad B\cup C = \{0,1,3,5,6,7,9\},\]

\[A\cap B = \emptyset, \quad A\cap C = \{0\}, \quad B \cap C = \{3,9\},\]

\[A\backslash B = A, \quad A\backslash C = \{2,4,8\}, \quad B\backslash A = B, \quad B\backslash C = \{1,5,7\}, \quad C\backslash A = \{3,9\}, \quad C\backslash B = \{0,6\},\]

\[A^c = B, \quad B^c = A, \quad C^c = \{1,2,4,5,7,8\}.\]

Remarque

Concernant le complémentaire d'une partie \(A\) d'un ensemble \(E\), il existe d'autres notations usuelles

\[A^c = \overline{A} = E\backslash A.\]

Remarque

L'ordre des termes pour une réunion ou une intersection n'a pas d'importance mais l'ordre des termes pour une différence ne peut pas être changé.

Exemple

On considère l'ensemble \(C(\mathbb{R})\) des fonctions réelles continues sur $\mathbb{R} et la partie \(D(\mathbb{R})\) des fonctions dérivables sur \(\mathbb{R}\). Alors \(C(\mathbb{R}) \backslash D(\mathbb{R}) \neq \emptyset\) car par exemple la fonction valeur absolue \(|\cdot | \in C(\mathbb{R}) \backslash D(\mathbb{R})\), mais \(D(\mathbb{R}) \backslash C(\mathbb{R}) = \emptyset\) car une fonction dérivable est continue.

Remarque

On définit de même la réunion et l'intersection d'une famille de parties \((A_i)_{i\in I}\) :

\[\bigcup_{i\in I} A_i = \{x \in E, \quad \exists i\in I, \quad x\in A_i\},\]

\[\bigcap_{i\in I} A_i = \{x\in E, \quad \forall i\in I, \quad x\in A_i\}.\]

Exemple

On considère les parties réelles

\[A_n = \left[0, 1 - \dfrac{1}{n}], \quad n\in \mathbb{N}^*.\]

Alors

\[\bigcup_{n\in \mathbb{N}^*} A_n = [0,1[,\]

et

\[\bigcap_{n\in \mathbb{N}^*} A_n = \{0\}.\]

Proposition : Quelques règles des opérations ensemblistes

On considère un ensemble \(E\) et trois parties \(A,B\) et \(C\) de l'ensemble \(E\). Alors nous avons les égalités suivantes :

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

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

• \((A\cup B) \backslash C = (A\backslash C)\cup (B\backslash C),\)

• \((A\cap B) \backslash C = (A\backslash C) \cap (B\backslash C),\)

• \((A^c)^c = A,\)

• \(A \cup A^c = E,\)

• \(A \cap A^c = \emptyset,\)

• \((A \cup B)^c = A^c \cap B^c,\)

• \((A \cap B)^c = A^c \cup B^c.\)

Démonstration

• On procède par double inclusion.

Soit \(x \in (A\cup B) \cap C\). Alors \(x \in A\) ou \(x\in B\) mais dans les deux cas \(x\in C\). Donc \(x\in A\cap C\) ou \(x\in B\cap C\). Ainsi \(x\in (A\cap C) \cup (B\cap C)\). Ce qui montre que \((A\cup B) \cap C \cup (A\cap C) \cup (B\cap C)\).

Réciproquement soit \(x\in (A\cap C) \cup (B\cap C)\). Alors \(x\in A\cap C\) ou \(x\in B\cap C\). Continuons par distinction des cas. Si \(x\in A\cap C\) alors \(x \in A\subset A\cup\) et \(x\in C\). Si \(x\in B\cap C\) alors \(x\in B\subset B\cup C\) et \(x\in C\). Donc, dans les deux cas, \(x\in A\cup B\) et \(x\in C\). Ainsi \(x\in (A\cup B) \cap C\). Ce qui montre que \((A\cap C) \cup (B\cap C) \subset (A\cup B) \cap C\).

Par conséquent nous avons bien l'égalité souhaitée.

• On procède de même pour les autres égalités.

Définition : Produit cartésien

On considère deux ensembles \(E\) et \(F\). Alors le produit cartésien de \(E\) et \(F\) est l'ensemble noté \(E \times F\) défini par

\[E\times F = \{(x,y), \quad x\in E, x\in F\}.\]

De même si l'on considère \(n\) ensembles \(E_1, ..., E_n\) alors leur produit cartésien noté \(E_1 \times ... \times E_n\) est défini par

\[E_1 \times ... \times E_n = \{(x_1, ..., x_n), \quad x_1\in E_1, ..., x_n\in E_n\}.\]

Exemple

Le plan \(\mathbb{R}^2\) est le produit cartésien de \(\mathbb{R}\) avec lui-même.

Proposition : Quelques règles d'opérations

On considère deux ensembles \(E\) et \(F\), deux parties \(A\) et \(B\) de l'ensemble \(E\) et \(C\) une partie de l'ensemble \(F\). Alors nous avons les égalités ensemblistes suivantes :

• \((A\cup B) \times C = (A\times C) \cup (B\times C),\)

• \((A\cap B) \times C = (A\times C) \cap (B\times C),\)

• \((A\backslash B)\times C = (A\times C) \backslash (B\times C),\)

• $A^c \times C^c \subset (A\times C)^c et l'inclusion réciproque est fausse en général.

Démonstration

• On procède par double inclusion classiquement.

• On procède par double inclusion classiquement.

• On procède par double inclusion.

Soit \((x,y)\in (A\backslash B) \times C\). Alors \(x \in A, x\notin B\) et \(y \in C\). Ainsi \((x,y) \in A\times C\) et \((x,y) \notin B\times C\). Donc \((x,y) \in (A\times C) \backslash (B\times C)\). Ce qui montre l'inclusion \((A\backslash B)\times C \subset (A\times C)\backslash (B\times C)\).

Réciproquement soit \((x,y) \in (A\times C) \backslash (B\times C)\). Alors \((x,y) \in A\times C\) et \((x,y) \notin B\times C\). Donc \(x\in A, y\in C\) et \(x\notin B\) ou \(y\notin C\). Sauf que \(y \in C\), donc il ne reste plus que la possibilité \(x\notin B\). Ainsi \(x\in A\backslash B\) et \(y\in C\). Donc \((x,y) \in (A\backslash B)\times C\). Ce qui montre l'inclusion \((A\times C)\backslash (B\times C) \subset (A\backslash B)\times C\).

Par conséquent nous avons bien montré l'égalité souhaitée.

• Soit $(x,y) \in A^c\times C^c. Alors \(x\notin A\) et \(y\notin C\). Donc \((x,y)\notin A\times C\). Ce qui montre l'inclusion $A^c \times C^c \subset (A\times C)^C.

Réciproquement on peut considérer les ensembles \(E = F = \mathbb{R}\) et les parties \(A = C = [0,1]\). Alors la partie \((A\times C)^c\) est le plan \(E = \mathbb{R}^2\) privé du carré \(A\times C\), alors que la partie \(A^c \times C^c\) est la réunion disjointe de quatre carrés infinis du plan.

Remarque

Contrairement aux opérations \(\cup\) ou \(\cap\), l'ordre des ensembles dans le produit cartésien ne peut pas être échangé.

Exemple

Le produit cartésion \(\mathbb{R} \times \mathbb{R}_+\) correspond au demi-plan au dessus de l'axe des abscisses alors que le produit cartésien \(\mathbb{R}_+ \times \mathbb{R}\) correspond au demi-plan à droite de l'axe des ordonnées.

Définition : Ensembles des parties d'un ensemble

On considère un ensemble \(E\). L'ensemble des parties de l'ensemble \(E\) est noté \(\mathcal{P}(E)\) est défini comme l'ensemble des ensembles \(A\) incluses dans l'ensemble \(E\)

\[\mathcal{P}(E) = \{A\subset \mathcal{P}(E)\}.\]

Exemple

Si \(E = \{0,1,2\}\) alors \(\mathcal{P}(E)\) est composé de \(\emptyset, E,\) des singletons \(\{0\},\{1\},\{2\}\) et des couples \(\{0,1\}, \{0,2\}, \{1,2\}\). Ainsi

\[\mathcal{P}(E) = \{\emptyset, E, \{0\},\{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}\}.\]

Remarque

Pour un ensemble \(E\), nous avons toujours \(\emptyset \in \mathcal{P}(E)\) et \(E \in \mathcal{P}(E)\).

Remarque

Attention aux notations, pour un ensemble \(E\) et un objet \(A\) :

• \(A \in E\) signifie que l'objet \(A\) est un élément de l'ensemble \(E\),

• \(A \subset E\) ou \(A \in \mathcal{P}(E)\) siginfie que l'objet \(A\) est une partie de l'ensemble \(E\),

• \(A \subset \mathcal{P}(E)\) signifie que l'objet \(A\) est un ensemble de parties de l'ensemble \(E\).

Définition : Partition (ou recouvrement disjoint)

On considère un ensemble \(E\) et \(A_1, ..., A_n\) des parties de l'ensemble \(E\). Alors on dit que les parties \(A_1, ..., A_n\) forment une partition (ou recouvrement disjoint) de l'ensemble \(E\) si :

• les parties \(A_1, ..., A_n\) sont disjointes :

\[\forall (i,j) \in \{1, ..., n\}^2, \quad i\neq j \quad \Longrightarrow \quad A_i \cap A_j = \emptyset,\]

• la réunion des \(A_1, ..., A_n\) est égale à l'ensemble \(E\) :

\[\bigcup_{i=1}^n A_i = A_1 \cup ... \cup A_n = E.\]

On note alors

\[E = \bigsqcup_{i=1}^n A_i.\]

Exemple

L'ensemble \(E = \{0,1\,2\}\) admet plusieurs partitions :

\[E = \{0,1,2\} = \{0\} \sqcup \{1\} \sqcup \{2\} = \{0\} \sqcup \{1,2\} = \{1\} \sqcup \{0,2\} = \{2\} \sqcup \{0,1\}.\]

III. Applications

Définition : Application

On considère deux ensembles \(E\) et \(F\). Alors une application \(f\) de l'ensemble \(E\) dans l'ensemble \(F\) est un procédé qui à tout élément \(x \in E\) associe un unique élément \(f(x) \in F\). On la note

\[\begin{array}{rcl} f : E & \longrightarrow & F \\ x & \longmapsto & f(x) \end{array}.\]

De plus on note \(F^E\) (ou \(\mathcal{F}(E,F)\)) l'ensemble des applications de l'ensemble \(E\) dans l'ensemble \(F\).

Exemple

On considère un ensemble \(E\). Alors l'application identité de l'ensemble \(E\) est l'application \(\text{id}_E\) définie par

\[\text{id}_E : \begin{array}{rcl} E & \longrightarrow & E \\ x & \longmapsto & x \end{array} .\]

Exemple

On considère un ensemble \(E\). Alors le passage au complémentaire est une application de \(\mathcal{P}(E)\) dans $\mathcal{P}(E) :

\[\begin{array}{rcl} \mathcal{P}(E) & \longrightarrow & \mathcal{P}(E) \\ A & \longmapsto & A^c \end{array}.\]

Remarque

Dans ce cas, on appelle \(E\) l'ensemble de départ de l'application \(f\) et \(F\) son ensemble d'arrivée.

Pour tout \(x\in E\), l'élément \(f(x)\) est appelé image de l'élément \(x\) par l'application \(f\).

Et pour tout \(y \in F\), s'il existe \(x\in E\) tel que \(y = f(x)\), alors on dit que l'élément \(x\) est un antécédent de l'élément \(y\) par l'application \(f\).

Définition : Applications égales

On considère deux applications \(f_1 : E_1 \longrightarrow F_1\) et \(f_2 : E_2 \longrightarrow F_2\). Alors on dit que les applications \(f_1\) et \(f_2\) sont égales, ce que l'on note \(f_1 = f_2\), si \(E_1 = E_2\) et

\[\forall x\in E_1 = E_2, \quad f_1(x) = f_2(x).\]

Exemples

Applications égalesApplications non égales

Les applications valeur absolue \(|\cdot|\) et \(\begin{array}{rcl} f : \mathbb{R} & \longrightarrow & \mathbb{R} \\ x & \longmapsto & \sqrt{x^2} \end{array}\) sont égales.

Les applications identité \(\text{id}_\mathbb{R}\) et \(f\) ne sont pas égales parce que \((\text{id}_{\mathbb{R}})(-1) = -1 \neq 1 = f(-1)\). De même les applications \(\text{id}_{\mathbb{R}_+}\) et \(f\) ne sont pas égales car les ensembles de départ ne sont pas égaux \(\mathbb{R}_+ \neq \mathbb{R}\).

Définition : Graphe d'une application

On considère une application \(f : E \longrightarrow F\). Alors le graphe de la fonction \(f\) est la partie \(\Gamma_f\) de \(E\times F\) définie par

\[\Gamma_f = \{(x,f(x)), \quad x\in E\}.\]

Exemple

On considère la fonction

\[\begin{array}{rcl} \mathbb{R}_+^* & \longrightarrow & \mathbb{R} \\ x & \longmapsto & \ln(x) \end{array}.\]

Alors le graphe de la fonction \(f\) est sa courbe représentative dans \(\mathbb{R}^2\)

Fonction indicatrice d'une partie

On considère un ensemble \(E\) et une partie \(A\) de l'ensemble \(E\). Alors la fonction indicatrice de la partie \(A\) est l'application \(\mathbb{1}_A : E \longrightarrow \{0,1\}\) définie par

\[\forall x \in E, \quad \mathbb{1}_A(x) = \begin{cases} 1 & \text{si} & x \in A \\ 0 & \text{si} & x\notin A \end{cases} .\]

Exemple

Nous pouvons nous servir des fonctions indicatrices pour écrire l'application valeur absolue :

\[\forall x\in \mathbb{R}, \quad |x| = x\mathbb{1}_{\mathbb{R}_+}(x) - x \mathbb{1}_{\mathbb{R}_+^*}(x).\]

Proposition : Fonction indicatrice d'opérations ensemblistes

On considère un ensemble \(E\) et deux parties \(A\) et \(B\) de l'ensemble \(E\). Alors nous avons les égalités suivantes :

• \(\mathbb{1}_{A^c} = 1 - \mathbb{1}_A\),

• \(\mathbb{1}_{A\cap B} = \mathbb{1}_A \times \mathbb{1}_B\),

• \(\mathbb{1}_{A\cup B} = \mathbb{1}_A + \mathbb{1}_B - \mathbb{1}_{A\cap B}\),

• \(\mathbb{1}_{A\backslash B} = \mathbb{1}_A - \mathbb{1}_{A\cap B}\).

Démonstration

On procède par disjonction des cas.

Définition : Restriction d'une application

On considère une application entre deux ensembles \(f : E \longrightarrow F\) et une partie \(A\) de l'ensemble \(E\). Alors la restriction de l'application \(f\) à la partie \(A\) est l'application \(f_{|A}\) définie par

\[\begin{array}{rcl} f_{|A} : A & \longrightarrow & F \\ x & \longmapsto & f(x) \end{array}.\]

Exemple

Nous avons l'égalité \(|\cdot|_{|\mathbb{R}_+} = \text{id}_{\mathbb{R}}\).

Définition : Prolongement d'une application

On considère une application entre deux ensembles \(f : E \longrightarrow F\), une partie \(A\) de l'ensemble \(E\) et une application \(g : A \longrightarrow F\). Alors on dit que l'application \(f\) est un prolongement de l'application \(g\) si l'application \(g\) est la restriction de l'application \(f\) à la partie \(A\).

Exemple

On considère \(x\in \mathbb{R}_+^*\). Alors l'application

\[\begin{array}{rcl} \mathbb{R} & \longrightarrow & \mathbb{R} \\ \alpha & \longmapsto & x^\alpha = e^{\alpha \ln(x)} \end{array}\]

est un prolongement de l'application

\[\begin{array}{rcl} \mathbb{Z} & \longrightarrow & \mathbb{R} \\ n & \longmapsto & x^n \end{array}.\]

Définition : Image directe

On considère une application entre deux ensembles \(f : E\longrightarrow F\) et une partie \(A\) de l'ensemble \(E\). Alors l'image directe de la partie \(A\) par l'application \(f\) est la partie \(f(A)\) de l'ensemble \(F\) définie par

\[f(A) = \{f(x), \quad x\in A\}.\]

De plus l'ensemble image de l'application \(f\) est l'image directe de l'ensemble \(E\) tout entier

\[\text{Im}(f) = f(E) = \{f(x), \quad x\in E\}.\]

Exemple

On considère l'application \(\exp : \mathbb{R} \longrightarrow \mathbb{R}\) et la partie \(\mathbb{R}_+\). Alors

\[\exp(\mathbb{R}_+) = [1,+\infty[, \quad \text{Im}(\exp) = \mathbb{R}_+^*.\]

Remarque

Il ne faut pas confondre l'ensemble d'arrivée \(F\) d'une application \(f : E \longrightarrow F\) et l'ensemble image \(\text{Im}(f)\). Nous avons \(\text{Im}(f) \subset F\) mais en général pas l'égalité.

Définition : Image réciproque

On considère une application entre deux ensembles \(f : E \longrightarrow F\) et une application \(B\) de l'ensemble \(F\). Alors l'image réciproque de la partie \(B\) par l'application \(f\) est la partie \(f^{-1}(B)\) de l'ensemble \(E\) définie par

\[f^{-1}(B) = \{x\in E, \quad f(x) \in B\}.\]

Exemple

On considère l'application \(f : \mathbb{R} \longrightarrow \mathbb{R}\) définie par

\[\forall x\in \mathbb{R}, \quad f(x) = x^2 + x - 2.\]

Alors le noyau \(\text{Ker}(f)\) de l'application \(f\) est l'image réciproque de la partie \(\{0\}\) par l'application \(f\) :

\[\text{Ker}(f) = f^{-1}(\{0\}) = \{x\in \mathbb{R}, \quad f(x) = 0\} = \{1,-2\}.\]

Proposition : Images directes et réciproques d'opérations ensemblistes

On considère une application entre deux ensembles \(f : E\longrightarrow F\), deux parties \(A\) et \(B\) de l'ensemble \(E\) et deux parties \(C\) et \(D\) de l'ensemble \(F\). Alors nous avons :

• \(f(A\cap B) \subset f(A) \cap f(B)\) et l'inclusion réciproque n'est pas vérifiée en général,

• \(f(A \cup B) = f(A) \cup f(B)\),

• \(f^{-1}(C\cap D) = f^{-1}(C) \cap f^{-1}(D)\),

• \(f^{-1}(C \cup D) = f^{-1}(C) \cup f^{-1}(D)\),

• \(A \subset f^{-1}(f(A))\) et l'inclusion réciproque n'est pas vérifiée en général,

• \(f(f^{-1}(C)) = C \cap \text{Im}(f) \subset C\).

Démonstration

On raisonne par inclusion ou double inclusion.

• Soit \(y \in f(A\cap B)\). Alors il existe \(x\in A\cap B\) tel que \(y = f(x)\). Donc \(x \in A\) et \(y\in f(A)\). De même \(x\in B\) et \(y \in f(B)\). Ainsi \(y\in f(A) \cap f(B)\). Par conséquent \(f(A\cap B) \subset f(A) \cap f(B)\).

Réciproquement si l'on considère l'application \(f : \begin{array}{rcl} \mathbb{R} & \longrightarrow & \mathbb{R} \\ x & \longmapsto & x^2 \end{array}\) et les ensembles \(A = \mathbb{R}_+\) et \(B = A^c = \mathbb{R}_-^*\). Ainsi

\[f(A\cap B) = f(\emptyset) = \emptyset \neq \mathbb{R}_+^* = f(A) \cap f(B).\]

• Soit \(y \in f(A\cup B)\)? Alors il existe \(x\in A\cup B\) tel que \(y = f(x)\). Donc soit \(x\in A\) et dans ce cas \(y \in f(A)\), soit \(x\in B\) et dans ce cas \(y\in f(B)\). Ainsi \(y \in f(A) \cup f(B)\) ce qui montre que \(f(A\cup B) \subset f(A) \cup f(B)\).

Réciproquement soit \(y \in f(A) \cup f(B)\). Alors soit \(y \in f(A)\) et dans ce cas il existe \(x\in A\subset A\cup B\) tel que \(y= f(x) \in f(A\cup B)\), soit \(y\in f(B)\) et dans ce cas il existe \(x\in B\subset A\cup B\) tel que \(y = f(x) \in f(A\cup B)\). Ainsi \(y \in f(A\cup B)\) ce qui montre que \(f(A) \cup f(B) \subset f(A\cup B)\).

• Soit \(x \in f^{-1}(C\cap D)\). Alors \(f(x)\in C\cap D\). Donc \(f(x) \in C\) et \(f(x)\in D\). Ainsi \(x\in f^{-1}(C)\) et \(x\in f^{-1}(D)\). Par conséquent $x \in f^{-1}(C) \cap f^{-1}(D) ce qui montre que $f^{-1}(C\cap D) \subset f^{-1}(C) \cap f^{-1}(D).

Réciproquement soit \(x \in f^{-1}(C) \cap f^{-1}(D)\). Alors \(f(x) \in C\) et \(f(x) \in D\). Donc \(f(x) \in C\cap D\), d'où \(x\in f^{-1}(C\cap D)\) ce qui montre que \(f^{-1}(C) \cap f^{-1}(D) \subset f^{-1}(C\cap D)\).

• Soit \(x\in f^{-1}(C\cup D)\). Alors \(f(x) \in C\cup D\). Donc \(f(x) \in C\) ou \(f(x) \in D\). Ainsi \(x\in f^{-1}(C)\) ou \(x\in f^{-1}(D)\). Donc \(x\in f^{-1}(C) \cup f^{-1}(D)\) ce qui montre que \(f^{-1}(C\cup D) \subset f^{-1}(C) \cup f^{-1}(D)\).

Réciproquement soit \(x\in f^{-1}(C) \cup f^{-1}(D)\). Alors soit \(x\in f^{-1}(C)\) et dans ce cas \(f(x) \in C\), soit \(x\in f^{-1}(D)\) et dans ce cas \(f(x) \in D\). Ainsi \(f(x) \in C\cup D\) puis \(x\in f^{-1}(C\cup D)\) ce qui montre que \(f^{-1}(C) \cup f^{-1}(D) \subset f^{-1}(C\cup D)\).

• Soit \(x \in A\). Alors \(f(x) \in f(A)\). Donc \(x\in f^{-1}(f(A))\).

Réciproquement on considère encore la fonction carrée précédente et la partie \(\mathbb{R}_-\). Alors

\[f^{-1}(f(\mathbb{R}_-)) = f^{-1}(\mathbb{R}_+) = \mathbb{R} \neq \mathbb{R}_-.\]

• Soit \(y \in f(f^{-1}(C))\). Alors il existe \(x\in f^{-1}(C)\) tel que \(y = f(x)\in C\) et \(y\in \text{Im}(f)\) ce qui montre l'inclusion \(f(f^{-1}(C)) \subset C\cap \text{Im}(f)\).

Réciproquement soit \(y \in C \cap \text{Im}(f)\). Alors il existe \(x\in E\) tel que \(f(x) = y \in C\). Donc \(x\in f^{-1}(C)\) puis $y\in f(f^{-1}(C)) ce qui montre l'inclusion \(C\cap \text{Im}(f) \subset f(f^{-1}(C))\).

Définition : Composition d'applications

On considère deux applications entre des ensembles \(f : E\longrightarrow F\) et \(g : F\longrightarrow G\). Alors la composée des applications \(g\) et \(f\) est l'application \(g\circ f\) définie par

\[\begin{array}{rcl} g\circ f : E & \longrightarrow & G \\ x & \longmapsto & g(f(x)) \end{array}.\]

Exemple

L'application réelle

\[F : \begin{array}{rcl} \mathbb{R} & \longrightarrow & \mathbb{R} \\ x & \longmapsto & x^2 \exp(x) \end{array}\]

est la composition de trois applications

\[f : \begin{array}{rcl} \mathbb{R} & \longrightarrow & \mathbb{R} \\ x & \longmapsto & x^2 \end{array}, \quad g : \begin{array}{rcl} \mathbb{R} & \longrightarrow & \mathbb{R} \\ x & \longmapsto & \exp(x) \end{array}, \quad h : \begin{array}{rcl} \mathbb{R}^2 & \longrightarrow & \mathbb{R} \\ (x,y) & \longmapsto & x\times y \end{array}.\]

En effet nous avons \(F = h\circ (g, f)\).

Remarque

Dans ce cas seule la composée \(g\circ f\) a du sens, on ne peut pas les composer dans l'autre sens. De façon générale, même si nous avons \(f : E \longrightarrow F\) et \(g : F\longrightarrow E\) alors nous n'avons pas forcément \(g\circ f = f\circ g\).

Exemple

On considère les applications \(f : \begin{array}{rcl} \mathbb{R} & \longrightarrow & \mathbb{R} \\ x & \longmapsto & x^2 \end{array}\) et \(g = \exp\). Alors \(f\circ g\neq g\circ f\) car, par exemple \((\exp(1))^2 = e^2 \neq e = \exp(1^2)\).

Proposition

On considère trois applications \(f : E \longrightarrow F, g : F \longrightarrow G, h : G \longrightarrow H\). Alors composer avec l'identité à droite ou à gauche ne change pas l'application :

\[f \circ \text{id}_E = f, \quad \text{id}_F \circ f = f,\]

et la composition est associative :

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

Démonstration

Définition : Injection

On considère une application entre deux ensembles \(f : E \longrightarrow F\). Alors on dit que l'application \(f\) est injective (ou une injection) si l'application \(f\) n'envoie jamais deux éléments distincts de l'ensemble \(E\) sur le même élément de l'ensemble \(F\). Autrement dit si

\[\forall (x,y) \in E^2, \quad x\neq y \quad \Longrightarrow \quad f(x) \neq f(y).\]

Exemple

Une fonction \(f : [0,1] \longrightarrow \mathbb{R}\) strictement monotone (strictement croissante ou strictement décroissante) est injective.

(insérer une image)

Définition : Surjection

On considère une application entre deux ensembles \(f : E \longrightarrow F\). Alors on dit que l'application \(f\) est surjective (ou une surjection) si tout élément de l'ensemble d'arrivée \(F\) admet au moins un antécédent par l'application \(f\). Autrement dit si

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

Exemple

L'application \(\begin{array}{rcl} f : \mathbb{R} & \longrightarrow & \mathbb{R}_+ \\ x & \longmapsto & x^2 \end{array}\) est surjective mais non injective. Tout \(y \in \mathbb{R}_+\) admet exactement deux antécédents par l'application \(f\), il s'agit de \(\sqrt{y}\) et \(-\sqrt{y}\).

Remarque

L'application associée \(f : E \longrightarrow \text{Im}(f)\) est surjective.

Proposition : Composition d'injections ou de surjections

On considère deux applications entre des ensembles \(f : E\longrightarrow F\) et \(g : F\longrightarrow G\). Si les applications \(f\) et \(g\) sont injectives (respectivement surjectives) alors leur composée \(g\circ f\) est également injective (respectivement surjective).

Démonstration

Proposition : Composée injective ou surjective d'applications

On considère deux applications \(f : E \longrightarrow F\) et \(g : F \longrightarrow G\). Si la composée \(g\circ f\) est injective (respectivement surjective) alors l'application \(f\) est injective (respectivement l'application \(g\) est surjective).

Démonstration

Définition : Bijection

On considère une application entre deux ensembles \(f : E \longrightarrow F\). Alors on dit que l'application est une bijection (ou bijective) si tout élément de l'ensemble d'arrivée \(F\) admet un unique antécédent par l'application \(f\). Autrement dit si l'application \(f\) est injective et surjective.

Exemple

L'application \(\begin{array}{rcl} f : \mathbb{R} & \longrightarrow \mathbb{R} \\ x & \longmapsto & x^3 \end{array}\) est bijective car strictement croissante et tout \(y \in \mathbb{R}\) admet \(^3\sqrt{y}\) comme antécédent par l'application \(f\).

Proposition : Caractérisation

On considère une application entre deux ensembles \(f : E \longrightarrow F\). Alors les assertions suivantes sont équivalentes :

1. L'application \(f\) est bijective.

2. Il existe une application \(g : F\longrightarrow E\) telle que

\[g\circ f = \text{id}_E, \quad g\circ f = \text{id}_F.\]

Démonstration

Définition : Bijection réciproque

On considère une application bijective entre deux ensembles \(f : E \longrightarrow F\). Alors l'application \(g ; F\longrightarrow E\) de la proposition précédente est appelée la bijection réciproque de l'application et est notée \(f^{-1} = g\).

Exemple

La bijection réciproque de l'application \(\exp : \mathbb{R} \longrightarrow \mathbb{R}_+^*\) est l'application \(\ln : \mathbb{R}_+^* \longrightarrow \mathbb{R}\).

Remarque

La notation est cohérente avec les images réciproques par l'application \(f\) et les images directes par l'application $f^{-1}. En effet en considérant une application bijective \(f : E \longrightarrow F\) et une partie \(B\) de l'ensemble \(F\). Alors nous avons égalité entre $f^{-1}(B) l'image réciproque de la partie \(B\) par l'application \(f\) et \(f^{-1}(B)\) l'image directe de la partie \(B\) par l'application \(f^{-1}\).

Proposition : Composition de bijection

On considère deux applications bijectives entre des ensembles \(f: E\longrightarrow F\) et \(g : F \longrightarrow G\). Alors leur composée \(g\circ f : E \longrightarrow F\) est également bijective.

Démonstration

Corollaire : Bijection réciproque d'une composée

Dans ce cas la bijection réciproque de la composée \(g\circ f\) est l'application \((g\circ f)^{-1} = f^{-1} \circ g^{-1} : G \longrightarrow E\).

Démonstration

IV. Relations

Définition : Relation binaire sur un ensemble

On considère un ensemble \(E\). Alors une relation binaire dans l'ensemble \(E\) est une partie \(\mathcal{G}\) du produit cartésien \(E\times E\). Pour tout \((x,y)\in E\times E\), si \((x,y) \in \mathcal{G}\) alors on dit que l'élément \(x\) est en relation avec l'élément \(y\) et on le note \(x\mathcal{R}y\).

Exemple

L'inégalité stricte \(<\) sur l'ensemble \(E = \{0,1,2\}\) est une relation binaire définie par

\[\mathcal{G} = \{(0,1), (1,2), (0,2)\} \subset E\times E.\]

Définition : Relation d'équivalence sur un ensemble

On considère une relation binaire \(\mathcal{R}\) sur un ensemble \(E\). Alors on dit que la relation binaire \(\mathcal{R}\) est une relation d'équivalence si elle vérifie les propriétés suivantes :

• Réflexitivité : \(\forall x\in E, \quad x\mathcal{R}x\),

• Symétrie : \(\forall (x,y) \in E^2, \quad x\mathcal{R}y \quad \Longrightarrow \quad y\mathcal{R}x\),

• Transitivité : \(\forall (x,y,z)\in E^3, \quad [x\mathcal{R}y \text{ et } y\mathcal{R}z] \quad \Longrightarrow x\mathcal{R}z\).

Exemples

La relation d'égalité est une relation d'équivalence. La relation de congruence sur \(\mathbb{R}\) modulo un réel \(a\) est une relation d'équivalence définie par

\[\forall x,y\in \mathbb{R}, \quad x\equiv y[a] \quad \Longleftrightarrow \quad \exists k\in \mathbb{Z}, x=y+ka.\]

De même pour la relation de congruence sur \(\mathbb{Z}\) modulo un entier.

Définition : Classes d'équivalence

On considère une relation d'équivalence \(\mathcal{R}\) sur un ensemble \(E\) et un élément \(x\in E\). Alors la classe d'équivalence de l'élément \(x\) est la partie \(\mathcal{C}_x\) de l'ensemble \(E\) définie par l'ensemble des éléments \(y\in E\) en relation avec l'élément \(x\) :

\[\mathcal{C}_x = \{y\in E, \quad x\mathcal{R}y\}\]

Exemple

On considère la relation de congruence sur \(\mathbb{R}\) modulo \(2\pi\) et un réel \(x\in \mathbb{R}\). Alors sa classe d'équivalence est

\[C_x = \{x + 2k\pi, \quad k\in \mathbb{Z}\} = x + 2\pi \mathbb{Z}.\]

Proposition

On considère une relation d'équivalence \(\mathcal{R}\) sur un ensemble \(E\). Alors l'ensemble des classes d'équivalences forme un recouvrement de l'ensemble \(E\) :

\[E = \bigcup_{x\in E} \mathcal{C}_x.\]

De plus il existe une partie \(I\) et une famille d'éléments \((x_i)_{i\in I}\) de l'ensemble \(E\) telles qu'on est la partition

\[E = \bigsqcup_{x\in E} \mathcal{C}_{x_i}.\]

Démonstration

Soit \(x\in E\). Alors \(x\mathcal{R}x\) par reflexivité, donc \(x\in \mathcal{C}_x\) ce qui montre que \(E \subset \bigcup_{x\in E} \mathcal{C}_x\). Réciproquement nous avons par définition \(\bigcup_{x\in E} \mathcal{C}_x \subset E\). Ainsi par double inclusion nous avons la première égalité souhaitée.

Puis, par axiome du choix, nous choisissons un système de représentants \((x_i)_{i\in I}\) dans l'ensemble \(E\) pour la relation \(\mathcal{R}\). Pour se faire nous choisissons un premier élément \(x_0\in E\) et on considère sa classe d'équivalence \(C_{x_0}\). Soit \(C_{x_0} = E\) soit \(C_{x_0} \neq E\) et dans ce cas nous choisissons $x_1\in E\backslash C_{x_0} et on considère sa classe d'équivalence \(C_{x_1}\). Soit \(C_{x_0} \cup C_{x_1} = E\) soit \(C_{x_0} \cup C_{x_1} \neq E\) et dans ce cas nous choisissons \(x_2 \in E\backslash (C_{x_0} \cup C_{x_1})\). Puis, par axiome du choix nous pouvons répéter ce processus jusqu'à obtenir une famille \((x_i)_{i\in I}\) vérifiant

\[\bigcup_{i\in I} C_{x_i} = E,\]

et pour tout \(i,j\in I\) distincts \(x_i \notin C_{x_j}\), d'où \(C_{x_i} \cap C_{x_j} = \emptyset\). En effet supposons par l'absurde que \(C_{x_i} \cap C_{x_j} \neq \emptyset\), alors il existe \(x\in C_{x_i} \cap C_{x_j}\), d'où \(x\mathcal{R}x_i\) et \(x\mathcal{R}x_j\) ce qui implique par transitivité et symétrie de la relation d'équivalence \(\mathcal{R}\), \(x_i\mathcal{R} x_j\) ce qui ne peut pas. Par conséquent nous avons bien la partition souhaitée.

Définition : Relation d'ordre

On considère une relation binaire \(\mathcal{R}\) sur un ensemble \(E\). Alors on dit que la relation binaire \(\mathcal{R}\) est une relation d'ordre si elle vérifie les propriétés suivantes :

• Réflexitivité : \(\forall x\in E, \quad x\mathcal{R}x\),

• Antisymétrie : \(\forall (x,y) \in E^2, \quad [x\mathcal{R}y \text{ et } y\mathcal{R}x] \quad \Longrightarrow \quad x = y\),

• Transitivité : \(\forall (x,y,z)\in E^3, \quad [x\mathcal{R}y \text{ et } y\mathcal{R}z] \quad \Longrightarrow \quad x\mathcal{R}z\).

On dit alors que l'ensemble \(E\) est ordonné pour la relation d'ordre \(\mathcal{R}\).

Exemple

La relation \(\leq\) est une relation d'ordre sur l'ensemble des réels \(\mathbb{R}\) alors que la relation \(<\) n'en est pas une car n'est ni réflexive ni antisymétrique.

Définition : Relations d'ordre totale et partielle

On considère une relation d'ordre \(\mathcal{R}\) sur un ensemble \(E\). Aors on dit que la relation d'ordre \(\mathcal{R}\) est totale si tous les éléments sont en relation. Autrement dit si

\[\forall (x,y) \in E^2, \quad x\mathcal{R}y \text{ ou } y\mathcal{R}x.\]

Dans le cas contraire on dit que la relation d'ordre \(\mathcal{R}\) est partielle.

Exemple

Relation d'ordre totaleRelation d'ordre partielle

La relation d'ordre \(\leq\) est totale sur l'ensemble des réels \(\mathbb{R}\).

La relation \(\subset\) sur l'ensemble \(\mathcal{P}(E)\) des parties d'un ensemble \(E\) est une relation d'ordre partielle en général.

Exemple

On considère la relation \(\preceq\) sur l'ensemble \(\mathbb{R}^2\) définie par, pour tout \(x,y\in \mathbb{R}^2\), \(x\preceq y\) si \(x_1 \leq y_1\) et \(x_2\leq y_2\). Alors la relation \(\preceq\) est une relation d'ordre partielle sur l'ensemble \(\mathbb{R}^2\).

Définition : Majorant, minorant, plus grand élément, plus petit élément

On considère un ensemble \(E\) ordonné pour la relation d'ordre \(\mathcal{R}\), une partie \(A\) de l'ensemble \(E\) et deux éléments \(m,M \in E\). Alors on dit que :

• L'élément \(M\) est un majorant de la partie \(A\) si

\[\forall x\in A, \quad x\mathcal{R} M.\]

• L'élément \(m\) est un minorant de la partie \(A\) si

\[\forall x\in A, \quad m \mathcal{R} x.\]

• L'élément \(M\) est un plus grand élément de la partie \(A\) si l'élément \(M\) est un majorant de la partie \(A\) et \(M \in A\).

• L'élément \(m\) est un plus petit élément de la partie \(A\) si l'élément \(m\) est un minorant de la partie \(A\) et \(m \in A\).

Exemples

Un majorant du singleton \(\{A\}\) de l'ensemble \(\mathcal{P}(E)\) muni de la relation d'inclusion est la partie \(A\) elle-même. Il s'agit de plus d'un plus grand élément. De même un minorant est l'ensemble vide \(\emptyset\) et il s'agit d'un plus petit élément.

Remarque

Un majorant (respectivement un minorant) n'est pas nécessairement un plus grand élément (respectivement un plus petit élément).

Exemple

L'élément \(1\) (respectivement \(0\)) est un majorant (respectivement minorant) de la partie \(]0,1[\) mais n'est pas un plus grand (respectivement petit) élément de cette partie.

Proposition

On considère un ensemble \(E\) ordonné pour la relation d'ordre \(\mathcal{R}\) et une partie \(A\) de l'ensemble \(E\). Si la partie \(A\) admet un plus grand élément \(M \in A\) (respectivement un plus petit élément \(m \in A\)) alors il est unique. On le note alors \(M = \max (A)\) (respectivement \(m = \min (A)\)).

Démonstration

Théorème : Axiomes de Péano

L'ensemble des entiers naturels \(\mathbb{N}\) est un ensemble totalement ordonné pour la relation d'ordre \(\leq\) et vérifie :

• Toute partie non vide admet un plus petit élément.

• Toute partie non vide majorée admet un plus grand élément.

• L'ensemble \(\mathbb{N}\) n'admet pas de majorant.

Remarque

Nous nous servons du premier axiome pour démontrer les raisonnements par récurrence.