Logique, ensembles et applications : cours de maths sup en PDF.

Une proposition est un énoncé qui est soit vrai, soit faux. À partir de deux propositions \(P\) et \(Q\), on forme :

• la négation \(\neg P\), vraie exactement quand \(P\) est fausse ;
• la conjonction \(P \wedge Q\) (« \(P\) et \(Q\) »), vraie quand les deux le sont ;
• la disjonction \(P \vee Q\) (« \(P\) ou \(Q\) »), vraie quand au moins l’une l’est ;
• l’implication \(P \Rightarrow Q\), fausse uniquement quand \(P\) est vraie et \(Q\) fausse ;
• l’équivalence \(P \Leftrightarrow Q\), vraie quand \(P\) et \(Q\) ont la même valeur de vérité.

Pour toutes propositions \(P\) et \(Q\) :

• \(\neg(P \wedge Q) \Leftrightarrow (\neg P \vee \neg Q)\) et \(\neg(P \vee Q) \Leftrightarrow (\neg P \wedge \neg Q)\) (lois de De Morgan) ;
• \((P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)\) : une implication équivaut à sa contraposée ;
• \((P \Leftrightarrow Q) \Leftrightarrow \big((P \Rightarrow Q) \wedge (Q \Rightarrow P)\big)\).

La réciproque de \(P \Rightarrow Q\) est \(Q \Rightarrow P\). Elle n’a aucun lien logique avec l’implication de départ. Par exemple, pour \(x\) réel, « \(x = 2 \Rightarrow x^2 = 4\) » est vraie, alors que sa réciproque est fausse pour \(x = -2\).

La phrase \(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x\) est vraie : on prend \(y = x + 1\), qui dépend de \(x\). En revanche, \(\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x\) est fausse : aucun réel ne majore tous les réels. Ainsi, dans la première phrase, \(y\) peut dépendre de \(x\) ; dans la seconde, il est choisi une fois pour toutes.

Pour nier une proposition quantifiée, on lit la phrase de gauche à droite :

• chaque \(\forall\) devient \(\exists\) et chaque \(\exists\) devient \(\forall\), sans changer l’ordre ni les ensembles ;
• la propriété finale est remplacée par sa négation ;
• une implication \(A \Rightarrow B\) finale devient \(A \wedge \neg B\).

Par exemple, « \(f\) est majorée » s’écrit \(\exists M \in \mathbb{R},\ \forall x \in \mathbb{R},\ f(x) \leq\, M\). Sa négation est donc \(\forall M \in \mathbb{R},\ \exists x \in \mathbb{R},\ f(x) > M\).

Montrons que, pour tout entier \(n\), le nombre \(n(n+1)\) est pair. Si \(n\) est pair, \(n = 2k\) et \(n(n+1) = 2k(2k+1)\) est pair. Sinon, \(n = 2k + 1\) et \(n(n+1) = 2(2k+1)(k+1)\) est pair. Les deux cas couvrent tous les entiers, d’où le résultat.

Soit \(n \in \mathbb{Z}\). Montrons que si \(n^2\) est pair, alors \(n\) est pair. Par contraposition, supposons \(n\) impair : \(n = 2k + 1\). Alors \(n^2 = 2(2k^2 + 2k) + 1\) est impair. La contraposée est prouvée, donc l’implication aussi.

Ensuite, montrons par l’absurde que \(\sqrt{2}\) est irrationnel. Supposons \(\sqrt{2} = \frac{p}{q}\) avec \(p\) et \(q\) entiers, \(q \neq 0\), la fraction étant irréductible. Alors \(p^2 = 2q^2\), donc \(p^2\) est pair, puis \(p\) est pair. On écrit \(p = 2p^{\prime}\), d’où \(q^2 = 2p^{\prime 2}\) : \(q\) est pair lui aussi. C’est absurde, car la fraction était irréductible.

Un raisonnement par analyse-synthèse se rédige en deux temps :

• Analyse : on suppose qu’une solution existe et on en déduit sa forme. On obtient des conditions nécessaires, donc l’unicité éventuelle.
• Synthèse : on vérifie que les candidats trouvés sont bien des solutions. On obtient ainsi l’existence.

Oublier la synthèse est une faute grave : l’analyse ne garantit jamais que le candidat convient.

Cherchons les fonctions \(f : \mathbb{R} \to \mathbb{R}\) telles que, pour tout réel \(x\), \(f(x) + f(-x) = 2x^2\) et \(f(x) – f(-x) = 4x\). Analyse : en additionnant les deux relations, \(2f(x) = 2x^2 + 4x\), donc \(f(x) = x^2 + 2x\). Synthèse : pour cette fonction, \(f(-x) = x^2 – 2x\), et les deux relations sont vérifiées. Il existe donc une unique solution.

Soit \(n_0 \in \mathbb{N}\) et \(\mathcal{P}(n)\) une propriété définie pour \(n \geq\, n_0\).

• Récurrence simple : si \(\mathcal{P}(n_0)\) est vraie et si \(\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)\) pour tout \(n \geq\, n_0\), alors \(\mathcal{P}(n)\) est vraie pour tout \(n \geq\, n_0\).
• Récurrence double : si \(\mathcal{P}(n_0)\) et \(\mathcal{P}(n_0 + 1)\) sont vraies et si \(\big(\mathcal{P}(n) \wedge \mathcal{P}(n+1)\big) \Rightarrow \mathcal{P}(n+2)\) pour tout \(n \geq\, n_0\), la conclusion est la même.
• Récurrence forte : si \(\mathcal{P}(n_0)\) est vraie et si, pour tout \(n \geq\, n_0\), la validité de \(\mathcal{P}(n_0), \ldots, \mathcal{P}(n)\) entraîne \(\mathcal{P}(n+1)\), la conclusion est encore la même.

Traitons la récurrence simple. Supposons par l’absurde que l’ensemble \(A\) des entiers \(n \geq\, n_0\) tels que \(\mathcal{P}(n)\) est fausse soit non vide. Il possède un plus petit élément \(m\). D’abord, \(m \neq n_0\) car \(\mathcal{P}(n_0)\) est vraie. Donc \(m – 1 \geq\, n_0\) et \(m – 1 \notin A\) par minimalité : \(\mathcal{P}(m-1)\) est vraie. L’hérédité donne alors \(\mathcal{P}(m)\), ce qui contredit \(m \in A\). Pour les récurrences double et forte, on applique la récurrence simple à la propriété \(\mathcal{Q}(n)\) : « \(\mathcal{P}(k)\) est vraie pour tout \(k\) entre \(n_0\) et \(n\) ».

Pour rédiger une récurrence proprement :

• énoncez \(\mathcal{P}(n)\) avec précision, sans quantificateur sur \(n\) à l’intérieur ;
• vérifiez l’initialisation, avec deux valeurs pour une récurrence double ;
• pour l’hérédité, fixez \(n\), écrivez l’hypothèse utilisée, puis prouvez \(\mathcal{P}(n+1)\) ;
• choisissez une récurrence forte quand \(\mathcal{P}(n+1)\) dépend d’un rang inférieur quelconque, par exemple d’un diviseur de \(n+1\).

Montrons par récurrence forte que tout entier \(n \geq\, 2\) est un produit de nombres premiers. Pour \(n = 2\), c’est vrai car \(2\) est premier. Soit \(n \geq\, 2\) tel que tous les entiers de \(2\) à \(n\) sont des produits de premiers. Si \(n + 1\) est premier, c’est fini. Sinon, \(n + 1 = ab\) avec \(2 \leq\, a, b \leq\, n\). Par hypothèse, \(a\) et \(b\) sont des produits de premiers, donc \(n + 1\) aussi.

On dit que \(A\) est inclus dans \(B\), et on note \(A \subset B\), si \(\forall x \in A,\ x \in B\). Deux ensembles sont égaux si \(A \subset B\) et \(B \subset A\). L’ensemble des parties de \(E\), noté \(\mathcal{P}(E)\), est l’ensemble dont les éléments sont les parties de \(E\).

Pour démontrer une inclusion \(A \subset B\), on écrit : « Soit \(x \in A\). » puis on montre que \(x \in B\). Pour démontrer une égalité d’ensembles, on prouve les deux inclusions, ou bien on raisonne par équivalences successives \(x \in A \Leftrightarrow \cdots \Leftrightarrow x \in B\).

Soit \(A\) et \(B\) deux parties d’un ensemble \(E\).

• La réunion est \(A \cup B = \{x \in E \mid x \in A \text{ ou } x \in B\}\).
• L’intersection est \(A \cap B = \{x \in E \mid x \in A \text{ et } x \in B\}\).
• La différence est \(A \setminus B = \{x \in E \mid x \in A \text{ et } x \notin B\}\).
• Le complémentaire de \(A\) dans \(E\) est \(\overline{A} = E \setminus A\).

Pour toutes parties \(A\), \(B\), \(C\) de \(E\) :

• \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) et \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) ;
• \(\overline{A \cup B} = \overline{A} \cap \overline{B}\) et \(\overline{A \cap B} = \overline{A} \cup \overline{B}\) (lois de De Morgan) ;
• \(A \setminus B = A \cap \overline{B}\) et \(\overline{\overline{A}} = A\).

Montrons la première loi de De Morgan. Soit \(x \in E\). On a \(x \in \overline{A \cup B}\) si et seulement si \(\neg(x \in A \vee x \in B)\). D’après les lois de De Morgan logiques, cela équivaut à \(x \notin A\) et \(x \notin B\), c’est-à-dire à \(x \in \overline{A} \cap \overline{B}\). Les autres égalités se prouvent de la même façon.

Le produit cartésien \(E \times F\) est l’ensemble des couples \((x, y)\) avec \(x \in E\) et \(y \in F\). Plus généralement, \(E_1 \times \cdots \times E_n\) est l’ensemble des \(n\)-uplets \((x_1, \ldots, x_n)\), et on note \(E^n = E \times \cdots \times E\).

Soit \((A_i)_{i \in I}\) une famille de parties de \(E\). C’est un recouvrement disjoint de \(E\) si les \(A_i\) sont deux à deux disjoints et si leur réunion vaut \(E\). C’est une partition de \(E\) si, de plus, chaque \(A_i\) est non vide.

Une application \(f\) de \(E\) dans \(F\) associe à chaque \(x \in E\) un unique élément \(f(x) \in F\). Son graphe est \(\Gamma_f = \{(x, f(x)) \mid x \in E\} \subset E \times F\). On note \(F^E\) ou \(\mathcal{F}(E, F)\) l’ensemble des applications de \(E\) dans \(F\).

Soit \(A \subset E\). La fonction indicatrice de \(A\) est l’application \(\mathbf{1}_A : E \to \{0, 1\}\) définie par \(\mathbf{1}_A(x) = 1\) si \(x \in A\) et \(\mathbf{1}_A(x) = 0\) sinon.

Pour toutes parties \(A\) et \(B\) de \(E\) : \(A = B \Leftrightarrow \mathbf{1}_A = \mathbf{1}_B\), puis

\[\mathbf{1}_{A \cap B} = \mathbf{1}_A \mathbf{1}_B, \qquad \mathbf{1}_{\overline{A}} = 1 – \mathbf{1}_A, \qquad \mathbf{1}_{A \cup B} = \mathbf{1}_A + \mathbf{1}_B – \mathbf{1}_A \mathbf{1}_B.\]

Soit \(x \in E\). Le produit \(\mathbf{1}_A(x) \mathbf{1}_B(x)\) vaut \(1\) si et seulement si les deux facteurs valent \(1\), c’est-à-dire si \(x \in A \cap B\). Ensuite, \(1 – \mathbf{1}_A(x)\) vaut \(1\) exactement quand \(x \notin A\). Enfin, \(\overline{A \cup B} = \overline{A} \cap \overline{B}\) donne \(1 – \mathbf{1}_{A \cup B} = (1 – \mathbf{1}_A)(1 – \mathbf{1}_B)\), et on développe.

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

• L’image directe de \(A\) est \(f(A) = \{f(x) \mid x \in A\}\). Ainsi, \(y \in f(A) \Leftrightarrow \exists x \in A,\ y = f(x)\).
• L’image réciproque de \(B\) est \(f^{-1}(B) = \{x \in E \mid f(x) \in B\}\). Ainsi, \(x \in f^{-1}(B) \Leftrightarrow f(x) \in B\).

La notation \(f^{-1}(B)\) a un sens pour toute application, bijective ou non. Elle ne suppose pas l’existence d’une application réciproque.

Soit \(f : \mathbb{R} \to \mathbb{R}\), \(x \mapsto x^2\). On a \(f([-1, 2]) = [0, 4]\). De plus, \(f^{-1}([1, 4]) = [-2, -1] \cup [1, 2]\), comme le montre la figure ci-dessous : on lit sur l’axe des abscisses les antécédents des valeurs comprises entre \(1\) et \(4\). Enfin, \(f^{-1}([-3, -1]) = \varnothing\).

Pour toutes parties \(A \subset E\) et \(B, B^{\prime} \subset F\) :

• \(f^{-1}(B \cup B^{\prime}) = f^{-1}(B) \cup f^{-1}(B^{\prime})\) et \(f^{-1}(B \cap B^{\prime}) = f^{-1}(B) \cap f^{-1}(B^{\prime})\) ;
• \(A \subset f^{-1}(f(A))\) et \(f(f^{-1}(B)) \subset B\), sans égalité en général.

Soit \(f : E \to F\) et \(A \subset E\). La restriction de \(f\) à \(A\) est l’application \(f_{|A} : A \to F\), \(x \mapsto f(x)\). Si \(E \subset E^{\prime}\), un prolongement de \(f\) à \(E^{\prime}\) est une application \(g : E^{\prime} \to F\) telle que \(g_{|E} = f\). Enfin, pour \(g : F \to G\), la composée \(g \circ f : E \to G\) est définie par \((g \circ f)(x) = g(f(x))\).

Soit \(f : E \to F\).

• \(f\) est injective si \(\forall (x, x^{\prime}) \in E^2,\ f(x) = f(x^{\prime}) \Rightarrow x = x^{\prime}\) : tout élément de \(F\) a au plus un antécédent.
• \(f\) est surjective si \(\forall y \in F,\ \exists x \in E,\ y = f(x)\) : tout élément de \(F\) a au moins un antécédent, autrement dit \(f(E) = F\).
• \(f\) est bijective si elle est injective et surjective : tout élément de \(F\) a exactement un antécédent.

L’application \(f : E \to F\) est bijective si et seulement s’il existe \(g : F \to E\) telle que \(g \circ f = \mathrm{id}_E\) et \(f \circ g = \mathrm{id}_F\). Dans ce cas, \(g\) est unique : c’est la bijection réciproque \(f^{-1}\), et \(f^{-1}\) est elle-même bijective, de réciproque \(f\).

Si \(f\) est bijective, on pose \(g(y)\) égal à l’unique antécédent de \(y\). Alors \(f(g(y)) = y\) par construction, et \(g(f(x)) = x\) car \(x\) est l’antécédent de \(f(x)\). Réciproquement, supposons qu’un tel \(g\) existe. Si \(f(x) = f(x^{\prime})\), on applique \(g\) : \(x = x^{\prime}\), donc \(f\) est injective. De plus, tout \(y \in F\) s’écrit \(y = f(g(y))\), donc \(f\) est surjective. Enfin, si \(g\) et \(h\) conviennent, \(g = g \circ (f \circ h) = (g \circ f) \circ h = h\).

Soit \(f : E \to F\) et \(g : F \to G\).

• Si \(f\) et \(g\) sont injectives (resp. surjectives), alors \(g \circ f\) l’est aussi.
• Si \(f\) et \(g\) sont bijectives, alors \(g \circ f\) est bijective et \((g \circ f)^{-1} = f^{-1} \circ g^{-1}\).

Supposons \(f\) et \(g\) injectives. Si \(g(f(x)) = g(f(x^{\prime}))\), l’injectivité de \(g\) donne \(f(x) = f(x^{\prime})\), puis celle de \(f\) donne \(x = x^{\prime}\). Le cas surjectif est analogue. Dans le cas bijectif, l’associativité donne \((f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ \mathrm{id}_F \circ f = \mathrm{id}_E\). De même, \((g \circ f) \circ (f^{-1} \circ g^{-1}) = \mathrm{id}_G\). Le théorème précédent conclut.

Pour montrer qu’une application est bijective et expliciter sa réciproque, on fixe \(y \in F\) et on résout l’équation \(f(x) = y\) d’inconnue \(x \in E\). S’il existe exactement une solution, alors \(f\) est bijective, et cette solution exprimée en fonction de \(y\) donne \(f^{-1}(y)\). Pour prouver une non-injectivité, il suffit d’exhiber \(x \neq x^{\prime}\) tels que \(f(x) = f(x^{\prime})\).

Soit \(f : \mathbb{R} \setminus \{1\} \to \mathbb{R} \setminus \{3\}\), \(x \mapsto \dfrac{3x}{x – 1}\). D’abord, \(f(x) = 3\) conduirait à \(3x = 3x – 3\), ce qui est impossible : \(f\) est bien à valeurs dans \(\mathbb{R} \setminus \{3\}\). Soit ensuite \(y \neq 3\). L’équation \(3x = y(x – 1)\) équivaut à \(x(y – 3) = y\), donc à \(x = \dfrac{y}{y – 3}\). Cette valeur est différente de \(1\). Ainsi, \(f\) est bijective et \(f^{-1}(y) = \dfrac{y}{y – 3}\).

La relation \(\mathcal{R}\) sur \(E\) est :

• réflexive si \(\forall x \in E,\ x \mathcal{R} x\) ;
• symétrique si \(\forall (x, y) \in E^2,\ x \mathcal{R} y \Rightarrow y \mathcal{R} x\) ;
• antisymétrique si \(\forall (x, y) \in E^2,\ (x \mathcal{R} y \wedge y \mathcal{R} x) \Rightarrow x = y\) ;
• transitive si \(\forall (x, y, z) \in E^3,\ (x \mathcal{R} y \wedge y \mathcal{R} z) \Rightarrow x \mathcal{R} z\).

Une relation d’équivalence est une relation réflexive, symétrique et transitive. La classe d’équivalence de \(x\) est \(\mathrm{cl}(x) = \{y \in E \mid x \mathcal{R} y\}\).

Les classes d’équivalence d’une relation d’équivalence sur \(E\) forment une partition de \(E\). De plus, \(x \mathcal{R} y\) si et seulement si \(\mathrm{cl}(x) = \mathrm{cl}(y)\).

Par réflexivité, \(x \in \mathrm{cl}(x)\) : chaque classe est non vide, et leur réunion vaut \(E\). Supposons \(x \mathcal{R} y\) et soit \(z \in \mathrm{cl}(y)\). Par transitivité, \(x \mathcal{R} z\), donc \(\mathrm{cl}(y) \subset \mathrm{cl}(x)\). Par symétrie, on obtient l’autre inclusion. Enfin, si deux classes ont un élément commun \(z\), alors \(x \mathcal{R} z\) et \(y \mathcal{R} z\), d’où \(x \mathcal{R} y\) et \(\mathrm{cl}(x) = \mathrm{cl}(y)\). Deux classes distinctes sont donc disjointes.

Soit \(n \in \mathbb{N}^{*}\). On dit que \(a\) et \(b\) sont congrus modulo \(n\), et on écrit \(a \equiv b \ [n]\), si \(n\) divise \(b – a\). C’est une relation d’équivalence sur \(\mathbb{Z}\). En effet, \(n\) divise \(0\), puis \(-(b-a)\) dès qu’il divise \(b – a\), et enfin \((c – b) + (b – a)\) s’il divise les deux termes. Il y a exactement \(n\) classes, celles de \(0, 1, \ldots, n-1\). La figure ci-dessous montre les trois classes modulo \(3\).

Une relation d’ordre est une relation réflexive, antisymétrique et transitive. Elle est totale si deux éléments quelconques sont toujours comparables : \(\forall (x, y) \in E^2,\ x \mathcal{R} y \vee y \mathcal{R} x\). Sinon, l’ordre est dit partiel.

L’ordre usuel \(\leq\,\) sur \(\mathbb{R}\) est total. En revanche, l’inclusion sur \(\mathcal{P}(E)\) est un ordre partiel dès que \(E\) a deux éléments \(a \neq b\) : \(\{a\}\) et \(\{b\}\) ne sont pas comparables. De même, la divisibilité sur \(\mathbb{N}^{*}\) est un ordre partiel, car \(2\) ne divise pas \(3\) et \(3\) ne divise pas \(2\). Sur \(\mathbb{Z}\), en revanche, la divisibilité n’est pas antisymétrique : \(2\) divise \(-2\) et \(-2\) divise \(2\).

Pour vérifier qu’une relation est une relation d’équivalence ou d’ordre, on contrôle une à une les trois propriétés, en citant à chaque fois les quantificateurs. Pour prouver qu’une propriété échoue, un seul contre-exemple explicite suffit.