Cours de Logique et Théorie des Ensembles PDF

Chapitre 1 Éléments de logique et de théorie des ensembles 1.1 Ensembles 1.1.1 Généralités Un ensemble est une collection d’objets appelés ses éléments. Si a est un élément et E est un ensemble, on note — a ∈ E si a est un élément de E, — a∈ / E sinon. Remarque : — Lorsqu’on...

Chapitre 1 Éléments de logique et de théorie des ensembles 1.1 Ensembles 1.1.1 Généralités Un ensemble est une collection d’objets appelés ses éléments. Si a est un élément et E est un ensemble, on note — a ∈ E si a est un élément de E, — a∈ / E sinon. Remarque : — Lorsqu’on fait la liste des éléments d’un ensemble, l’ordre ne compte pas : {a, b} = {b, a}. — La notation E = {a1 ,... , ap } ne nécessite pas que les éléments a1 ,... , ap soient distincts. On appelle cardinal de E le nombre d’éléments distincts de E. On le note card E. — Il y a un seul ensemble qui n’a pas d’éléments, il est appelé l’ensemble vide et se note ∅. 1.1.2 Définir un ensemble On a plusieurs façons de définir un ensemble, voyons trois des principales. — On peut définir un ensemble par la liste de ses éléments, par exemple {1, 2, 4}. — On peut définir un ensemble par une propriété, par exemple {x ∈ E : P (x)} où E est un ensemble et P une propriété qui dépend d’un élément x de E. Dans ce cas l’ensemble contient tous les éléments x de E qui vérifient la propriété P (x). — On peut définir un ensemble par une formule, par exemple {f (x) : x ∈ E} où E est un ensemble, et f est une fonction définie sur E. On dira aussi qu’il s’agit de l’image de E par la fonction f. Exemple 1.1. Définissons E = {0, 50, 100} de chacune des façons plus haut. — On énumère les éléments de E, E = {0, 50, 100}. 1 2 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES — On définit E comme l’ensemble des nombres entiers qui sont entre 0 et 100 et multiples de 50, E = {x ∈ N : P (x)} avec P (x) la propriété « x est entre 0 et 100 et x est un multiple de 50 ». — On définit E comme la multiplication par 50 des nombres {0, 1, 2}, dans ce cas E = {50n : n ∈ {0, 1, 2}}. 1.1.3 Inclusion, égalité d’ensembles Définition 1.1. Soit E et F deux ensembles. On dit que F est un sous-ensemble ou une partie de E lorsque tout élément de F est aussi un élément de E. On dit que E et F sont égaux, et l’on note E = F si E et F contiennent exactement les mêmes éléments. Remarque : — On dit aussi que F est inclus dans E et l’on note F ⊂ E. — E = F revient à dire que tous les éléments de E sont des éléments de F et vice-versa, autrement dit E = F équivaut à E ⊂ F et F ⊂ E. Exemple 1.2. Soit E, F et G des ensembles. Montrer que si E ⊂ F et F ⊂ G, alors E ⊂ G. 1.2 Vocabulaire et notations 1.2.1 Ensembles de nombres On rappelle les notations des ensembles de nombres usuels. — Les entiers naturels : 0, 1, 2,... , 23461,.... L’ensemble des entiers naturels est noté N. On note N∗ l’ensemble des entiers ⩾ 1. — Les entiers relatifs : ce sont les entiers naturels et leurs opposés. L’ensemble des entiers relatifs est noté Z. On note Z∗ l’ensemble des entiers relatifs privé de 0. — Les nombres rationnels : il s’agit des quotients de la forme pq avec p ∈ Z, q ∈ N et q ̸= 0. On note l’ensemble des nombres rationnels Q. On pourra supposer qu’un nombre rationnel pq est écrit sous forme irréductible, i.e. que p et q sont premiers entre eux, c’est-à-dire que le seul diviseur (positif) commun à p et q est 1. — Les nombres réels : on admet la construction des nombres réels, on n’en donne pas une définition. On note l’ensemble des nombres réels R. Il existe d’autres ensembles de nombres, notamment les nombres complexes, notés C mais on ne les abordera pas cette année. Remarque : On a les inclusions suivantes N ⊂ Z ⊂ Q ⊂ R. 1.2.2 Comparaison des réels Inégalités L’ensemble R est muni des relations de comparaison ⩽ et qui se lisent “supérieur” et “strictement supérieur”. On a x < y si, et seulement si, x ⩽ y et x ̸= y. Lorsque l’on compare les nombres avec 0, on utilise une terminologie propre : — un réel x est dit positif (respectivement strictement positif ) lorsque x ⩾ 0 (respectivement x > 0). — un réel x est dit négatif (respectivement strictement négatif ) lorsque x ⩽ 0 (respectivement x < 0). L’ensemble des réels positifs est noté R+ , celui des réels négatifs R− , celui des réels privé de 0 se note R∗ et la notation pour priver 0 s’étend à R∗+ et R∗−. Ces notations s’étendent aussi à Q. Intervalles de R Soit a et b deux réels tels que a ⩽ b. On note : [a, b] = {x ∈ R : a ⩽ x ⩽ b} [a, +∞[ = {x ∈ R : a ⩽ x} , [a, b[ = {x ∈ R : a ⩽ x < b} ] − ∞, b] = {x ∈ R : x ⩽ b} , ]a, b] = {x ∈ R : a < x ⩽ b} ]a, +∞[ = {x ∈ R : a < x} , ]a, b[ = {x ∈ R : a < x < b} ] − ∞, b[ = {x ∈ R : x < b}. Remarque : — L’ensemble R est aussi appelé la droite réelle. — L’ensemble vide est un intervalle puisque, par exemple, ∅ =]1, 1[. — Les quatre intervalles de la colonne de droite sont appelés des demi-droites. — Tout intervalle I a des extrémités inférieures et supérieures, qui peuvent éventuel- lement être +∞ ou −∞. — R est l’intervalle ] − ∞, +∞[ et ses extrémités sont −∞ et +∞. — L’intervalle [a, b] est appelé segment [a, b]. — Les intervalles ouverts de R sont ceux qui ne contiennent pas leurs extrémités, ils sont donc R, ∅ ou de la forme ]a, b[ , ] − ∞, b[ ou encore ]a, +∞[. — Les intervalles fermés de R sont ceux qui contiennent leurs extrémités finies, ils sont donc R, ∅ ou de la forme [a, b] , ] − ∞, b] ou encore [a, +∞[. — Les intervalles qui ne sont pas ouverts ni fermés, par exemple [a, b[ sont parfois appelés semi-ouverts ou semi-fermés. — Seuls ∅ et R sont à la fois ouverts et fermés. — Attention ! Les extrémités de l’ensemble vide ne sont pas très bien définies. Il y a des raisons pour dire que son extrémité inférieure est +∞ est sont extrémité supérieure −∞, mais cela est un peu bizarre. Autant retenir que l’ensemble vide est un intervalle ouvert et fermé. 4 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES — L’intérieur d’un intervalle I est l’intervalle ouvert de même extrémités de I. — Un point x ∈ I est dit intérieur s’il appartient à l’intérieur de I. — Par la suite, on dira “Soit I un intervalle d’intérieur non vide” pour parler d’un intervalle d’extrémités différentes. Ceci permet de dire que I contient deux points différents et donc une infinité d’éléments. On dira aussi que c’est un intervalle “non trivial”. Ayant rappelé ce qu’est un intervalle, en voici la définition. Définition 1.2 (Intervalle). Un ensemble I est un intervalle lorsque pour tout a, b ∈ I et x ∈ R tel que a ⩽ b on a l’implication suivante : si a ⩽ x ⩽ b alors x ∈ I. Ceci se réécrit : pour tout a, b ∈ I tel que a ⩽ b, alors [a, b] ⊂ I. Droite numérique achevée Définition 1.3. On appelle droite numérique achevée l’ensemble R = R ∪ {−∞, +∞}. On étend la relation ⩽ à R en posant −∞ ⩽ x ⩽ +∞ pour tout x ∈ R (voir fiche annexe). Partie entière Définition 1.4. La partie entière d’un réel x est le plus grand entier relatif n tel que n ⩽ x. On le note ⌊x⌋. Remarque : — On a donc, pour tout x ∈ R : ⌊x⌋ ⩽ x < ⌊x⌋ + 1 ou encore x − 1 < ⌊x⌋ ⩽ x. — On a même plus que cela. Soit n ∈ Z, n est la partie entière de x si, et seulement si, n⩽x b, par exemple dans le cas J1, nK pour n = 0. Dans ces cas, il s’agit de l’ensemble vide. 1.3 Logique et raisonnement 1.3.1 Assertions et modes de raisonnement Assertions La notion d’assertion est la notion élémentaire en logique. Intuitivement, il s’agit d’un énoncé mathématique qui est soit vrai soit faux. Exemple 1.3. “57 est un nombre premier” est une assertion (fausse). Exemple 1.4. “Tout entier naturel pair supérieur ou égal à 4 est la somme de deux nombres premiers” est une assertion dont on ne sait pas actuellement si elle est vraie ou fausse. 1 Une assertion P peut dépendre de paramètres, comme dans “n est un nombre premier”. Dans ce cas, pour rappeler que l’assertion dépend du paramètre n, on la notera P (n). Exemple 1.5. L’assertion “f(x)=3” dépend de f et de x. Convention Soit P une assertion. On dira et écrira : “supposons P ” au lieu de “supposons que P soit vraie” “montrons P ” au lieu de “montrons que P est vraie”. Connecteurs Définition 1.5. Soit P et Q deux assertions. On appelle : — négation de P , et l’on note ¬ P , toute assertion qui est vraie lorsque P est fausse et fausse sinon ; — conjonction de P et Q, et l’on note P ∧ Q, toute assertion qui est vraie lorsque les assertions P , Q sont toutes les deux vraies, et fausse sinon ; 1. On pense qu’elle est vraie (conjecture de Goldbach). 6 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES — disjonction de P et Q, et l’on note P ∨ Q, toute assertion qui est vraie lorsqu’au moins l’une des deux assertions P, Q est vraie, et fausse sinon ; — équivalence entre P et Q, et l’on note P ⇔ Q, toute assertion qui est vraie lorsque les assertions P, Q sont toutes les deux vraies ou toutes les deux fausses, et fausse sinon ; — implication de Q par P , que l’on note P ⇒ Q, toute assertion qui est fausse lorsque P est vraie et Q est fausse, et vraie dans tous les autres cas. Remarque : On pose la convention que ¬ a la priorité sur ∧ et ∨ , c’est-à-dire que ¬ P ∧ P ′ = (¬ P ) ∧ P ′. Il est souvent pratique de condenser la valeur d’une assertion constituée d’autres assertions en fonction des valeurs de celles-ci. En pratique, si deux assertions P et P ′ permettent de définir une troisième assertion P ′′ à partir des opérations naturelles, on construit la table de vérité de P ′′ comme le tableau qui contient une ligne pour chaque valeur possible des assertions P et P ′ et donne en dernière colonne les valeurs de P ′′ correspondantes. On notera plus simplement 1 la valeur vraie et 0 la valeur faux. On peut ainsi visualiser ces définitions à l’aide de tables de vérité : P Q ¬P P ∧Q P ∨Q P ⇔Q P ⇒Q 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1 1 1 Remarque : — Le connecteur ∨ n’est pas exclusif, contrairement à ce qui arrive souvent dans le langage courant, comme lorsqu’on dit qu’un menu contient “entrée ou dessert”. — Lorsqu’on a P ⇔ Q, on dit que P et Q sont équivalentes. — Lorsqu’on a P ⇒ Q, on dit que P implique Q. — Par abus on dit “la” négation de P ; bien qu’une assertion puisse avoir plusieurs négations, toutes ces négations sont équivalentes. Par exemple la négation de x = 0 peut s’écrire x ̸= 0 mais aussi x2 > 0. Exemple 1.6. Soit x un réel. (i) La négation de “x ⩾ −1” est “x < −1”. (ii) La négation de “x ⩽ 1” est “x > 1”. (iii) L’assertion “x2 − 1 = 0” est équivalente, pour x réel, à “(x = 1) ∨ (x = −1)”. (iv) L’assertion “−1 ⩽ x ⩽ 1” est équivalente à “(x ⩾ −1) ∧ (x ⩽ 1)”. Propriétés élémentaires sur les conjonction et les disjonctions Soit P , Q et R trois assertions. On a les propriétés suivantes qui peuvent se vérifier avec une table de vérité : (i) l’assertion P ∧ (¬ P ) est fausse ; 1.3. LOGIQUE ET RAISONNEMENT 7 (ii) l’assertion P ∨ (¬ P ) est vraie (principe du tiers exclu) ; (iii) si deux assertions sont équivalentes, alors leurs négations le sont aussi ; (iv) les assertions ¬ (¬ P ) et P sont équivalentes ; (v) les assertions ¬ (P ∧ Q) et (¬ P ) ∨ (¬ Q) sont équivalentes ; (vi) les assertions ¬ (P ∨ Q) et (¬ P ) ∧ (¬ Q) sont équivalentes ; (vii) les assertions (P ∧ Q) ∧ R et P ∧ (Q ∧ R) sont équivalentes ; (viii) les assertions (P ∨ Q) ∨ R et P ∨ (Q ∨ R) sont équivalentes. D’après les deux derniers points, on notera P ∧ Q ∧ R et P ∨ Q ∨ R sans parenthèses. Proposition 1.6. Soit P, Q et R trois assertions. (i) Les assertions P ∧ (Q ∨ R) et (P ∧ Q) ∨ (P ∧ R) sont équivalentes. (ii) Les assertions P ∨ (Q ∧ R) et (P ∨ Q) ∧ (P ∨ R) sont équivalentes. Démonstration. On fait une table de vérité à 8 lignes. Propriétés élémentaires sur l’implication et l’équivalence Soit P et Q deux as- sertions. Les propriétés suivantes se démontrent à l’aide d’une table de vérité : (i) l’assertion P ⇒ Q est équivalente à (¬ P ) ∨ Q ; (ii) la négation de P ⇒ Q est donc P ∧ (¬ Q) ; (iii) les assertions P ⇒ Q et (¬ Q) ⇒ (¬ P ) sont équivalentes ; (iv) les assertions P ⇔ Q et Q ⇔ P sont équivalentes ; (v) les assertions P ⇔ Q et (¬ P ) ⇔ (¬ Q) sont équivalentes ; (vi) les assertions P ⇔ Q et (P ⇒ Q) ∧ (Q ⇒ P ) sont équivalentes. Remarque : Par définition, l’assertion P ⇒ Q est fausse lorsque P est vraie et Q est fausse, et uniquement dans ce cas. Donc : — si P est fausse alors P ⇒ Q est vraie ; — si P ⇒ Q est vraie et si P est vraie, alors Q est vraie, et on obtient le sens intuitif de l’implication : si P est vraie, alors Q est vraie. Ainsi, pour démontrer P ⇒ Q : — si P est fausse, il n’y a rien à faire. — si P est vraie, on doit montrer que Q l’est aussi. Pour démontrer que P ⇒ Q est vraie, on peut commencer par supposer P et essayer de prouver Q, ce qui se rédige : “Supposons P et montrons Q”. Exemple 1.7. Soit P, Q, R trois assertions telles que P ⇒ Q et Q ⇒ R. Montrons que P ⇒ R. Remarque : — L’assertion P ⇒ Q peut être vraie même lorsque Q est fausse. Cela peut paraître bizarre à première vue, surtout si l’on a l’habitude d’utiliser “⇒” comme une abré- viation pour “donc”. — Écrire “P donc Q” ou “P implique Q” ne signifie pas la même chose. Dans la première version, l’assertion P est vraie alors que dans la seconde ce n’est pas forcément le cas. 8 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES Autres formulations Soit P et Q deux assertions. — Au lieu de dire “on a P ⇒ Q”, on peut dire indifféremment : — pour que Q soit vraie, il suffit que P le soit ; — pour que P soit vraie, il faut que Q le soit ; — P est une condition suffisante pour que Q soit vraie ; — Q est une condition nécessaire pour que P soit vraie. — Au lieu de dire “on a P ⇔ Q”, on peut dire indifféremment : — P est vraie si et seulement si Q l’est ; — pour que Q soit vraie, il faut et il suffit que P le soit ; — P est une condition nécessaire et suffisante pour que Q soit vraie. Modes de raisonnement Raisonnement par contraposée Définition 1.7. Soit P et Q deux assertions. L’assertion ¬ Q ⇒ ¬ P est appelée la contraposée de l’implication P ⇒ Q. On a vu qu’une implication et sa contraposée sont équivalentes. Pour montrer qu’une implication P ⇒ Q est vraie, on peut montrer sa contraposée. On dit alors que l’on raisonne par contraposée. Exemple 1.8. Soit n un entier. Montrons que si n2 est pair, alors n l’est aussi. Rai- sonnons par contraposée, en montrant (n impair) ⇒ (n2 impair). Supposons que n est impair, montrons que n2 l’est aussi. Comme n est impair, par définition, il existe k ∈ Z tel que n = 2k + 1. Alors, n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1. On a donc n2 = 2ℓ + 1 pour un certain entier ℓ. D’où le résultat. Raisonnement par double implication Pour montrer que P et Q sont équivalentes, on peut montrer les implications P ⇒ Q et Q ⇒ P. On dit alors que l’on raisonne par double implication. Exemple 1.9. Soit n un entier. Montrer que n2 est pair si, et seulement si, n l’est. — On a déjà montré par contraposée (n2 pair) ⇒ (n pair). Montrons sa réciproque. — Si n est pair, alors il existe un entier k tel que n = 2k. Ainsi n2 = 4k 2 = 2(2k 2 ), ce qui prouve que n2 est pair. En conclusion, n2 est pair si, et seulement si, n l’est aussi. Autrement dit n et n2 ont la même parité. Remarque : Q ⇒ P est appelée l’implication réciproque de P ⇒ Q. 1.3. LOGIQUE ET RAISONNEMENT 9 Raisonnement par disjonction de cas Pour démontrer un résultat, il peut être in- téressant d’étudier séparément les différents cas de figure. En général, si on veut mon- trer un prédicat P et l’on veut se servir d’une hypothèse supplémentaire Q, on montre (P ∩ Q) ∨ (P ∩ ¬ Q) plutôt que montrer P. Exemple 1.10. Soit n un entier. Montrons que n(n+1) 2 est un entier. Procédons par dis- jonction de cas. — Si n est pair, il existe un entier k tel que n = 2k, alors n(n + 1) 2k(2k + 1) = = k(2k + 1). 2 2 Ce qui est bien un nombre entier. — Si n est impair, il existe un entier k tel que n = 2k + 1, alors n(n + 1) (2k + 1)(2k + 2) = = (2k + 1)(k + 1). 2 2 Ce qui est bien un nombre entier. Cela conclut car, dans les deux cas, on a montré que n(n+1) 2 est un entier. Raisonnement par l’absurde Pour prouver qu’une assertion P est vraie, on peut supposer qu’elle est fausse et en déduire une contradiction. √ Exemple 1.11. Montrons que 2 est irrationnel. √ Raisonnons par l’absurde en √ supposant que 2 est rationnel. Il existe alors deux entiers p et q, avec q non nul, tels que 2 = pq. Quitte à simplifier la fraction, on peut supposer que p et q sont premiers entre eux. En particulier, cela veut dire que tous les deux ne sont pas pairs. On élève au carré l’égalité précédente pour obtenir 2q 2 = p2. Ainsi, p2 est pair, ce qui veut dire que p l’est aussi. On a donc p = 2k. On remplace p dans l’équation précédente, puis on divise par 2 dans les deux membres pour obtenir, q 2 = 2k 2. On a montré que q 2 est pair, ce qui montre que q l’est aussi. Ceci contredit le fait que p et q ne sont pas tous les deux pairs. √ L’hypothèse de départ est donc fausse, ce qui montre que 2 est irrationnel. Raisonnement par analyse-synthèse Lorsque l’on cherche l’ensemble des éléments x de E qui vérifient une propriété P (x), on peut procéder par analyse-synthèse. — Dans la phase analyse, on considère un élément x de E vérifiant P (x) et l’on en déduit des propriétés de x. Grâce à ces conditions nécessaires, on limite la liste des candidats. — Dans la syntèse, on détermine, parmi les candidats obtenus dans l’analyse, lesquels vérifient P (x). 10 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES Exemple 1.12. Déterminons les réels x tels que 1 + x ⩾ 0 et (1.1) √ 1 − x2 = 1 + x , (1.2) √ Analyse. Supposons que x soit un réel vérifiant 1 + x ⩾ 0 et 1 − x2 = 1 + x. Alors 2 (1 − x2 )2 = 1 + x, ce qui s’écrit aussi (1 − x)2 (1 + x)2 = 1 + x, ou encore   (1 + x) (1 + x)(1 − x)2 − 1 = 0 et enfin (1 + x)x(x2 − x − 1) = 0. On en déduit que les candidats possibles pour x sont les éléments dans ( √ √ ) 1+ 5 1− 5 −1, 0, ,. 2 2 Il suffit maintenant de voir si ces nombres vérifient (1.1) et (1.2) 3. Synthèse. — On vérifie facilement que −1 et 0 vérifient (1.1) et (1.2). Ils sont donc solutions. √ — Si x = 1−2 5 , on remontant les calculs précédents, on a (1 − x2 )2 = 1 + x. Comme 1 + x ⩾ 0 et 1 − x2 ⩾ 0, on a bien (1.2). Ainsi x est solution. √ — Si x = 1+2 5 , on a bien (1.1) mais en suivant le raisonnement ci-dessus, on observe que 1 − x2 < 0 et donc x n’est pas solution. √ Conclusion. Il y a 3 solutions : −1, 0 et 1−2 5. On peut résumer le raisonnement par analyse-synthèse à analyse :“Si x a la propriété que je veux, qu’est ce que cela me dit sur x ?” suivi de synthèse : “Parmi mes candidats possibles, lesquels vérifient vraiment tout ce que je veux ?”. 1.3.2 Quantificateurs On admettra qu’un ensemble est une “collection d’objets” qui sont des “éléments” de cet ensemble. On détaillera cela dans la partie suivante. Si a est un élément et E un ensemble : — l’assertion a ∈ E, qui se lit “a appartient à E” ou “E contient a”, est vraie si a est un élément de E, fausse sinon ; — lorsque a n’est pas élément de E, on écrit a ∈ / E. On admet qu’il existe un ensemble, appelé ensemble vide et noté ∅, qui ne contient aucun élément. 1.3.3 Quantificateurs universel et existentiel Définition 1.8. Soit P (x) une assertion dépendant d’une variable x appartenant à un ensemble E 4. 2. Cette étape est la seule qui n’est pas une équivalence. 3. En fait il suffit de vérifier 1 − x2 ⩾ 0. 4. Ce qu’on veut dire ici c’est que l’assertion P (x) est bien définie (ou encore “a du sens”) pour n’importe quel x dans E. Par exemple si P (x) est “x2 est pair”, cela a du sens pour tout x dans E = Z mais pas pour E l’ensemble des suites réelles. 1.3. LOGIQUE ET RAISONNEMENT 11 — On note “∀x ∈ E P (x)” l’assertion qui est vraie si, pour tout élément x de E, l’assertion P (x) est vraie. — On note “∃x ∈ E P (x)” l’assertion qui est vraie s’il existe un élément x apparte- nant à E tel que l’assertion P (x) soit vraie. — On note “∃!x ∈ E P (x)” l’assertion qui est vraie s’il existe un unique élément x appartenant à E tel que l’assertion P (x) soit vraie. Remarque : — L’assertion “∀x ∈ E P (x)” se lit “pour tout x dans E, on a P (x)”. — L’assertion “∃x ∈ E P (x)” se lit “il existe x dans E tel que P (x)”. — L’assertion “∃!x ∈ E P (x)” se lit “il existe un unique x dans E tel que P (x)”. Par convention, l’assertion “∀x ∈ ∅ P (x)” est vraie, et ce indépendamment de l’assertion P. Exemple 1.13. ∃x ∈ R 2x + 1 = 0 est une assertion vraie. Exemple 1.14. ∃n ∈ Z 2n + 1 = 0 est une assertion fausse. Exemple 1.15. ∀n ∈ Z (n > 3 ⇔ n ⩾ 4) est une assertion vraie. Exemple 1.16. ∀x ∈ R (x > 3 ⇔ x ⩾ 4) est une assertion fausse. Attention — Malgré les apparences, l’assertion “∀x ∈ E P (x)” ne dépend pas de x. La lettre x figurant des cette assertion a le statut de variable muette. En effet cette assertion peut aussi s’écrire sans utiliser le symbole x sans en changer le sens : “∀y ∈ E P (y)”. On pourrait l’exprimer aussi “tous les éléments de E vérifient P ”. — Il en est de même pour les assertions “∃x ∈ E P (x)” et “∃!x ∈ E P (x)”. Exemple 1.17. Soit f une fonction de R dans R. L’assertion “∀x ∈ R f (x) ⩾ 0” signifie “la fonction f est positive”. La reformulation en français ne fait pas intervenir la variable muette x. Comment se démontrer une assertion avec un quantificateur ? Pour démontrer une assertion du type : ∀x ∈ E P (x) La façon de procéder est de prendre un élément x quelconque de E et de démontrer P (x). La rédaction est alors : “ Soit x ∈ E. Montrons P (x)”. Exemple 1.18. Soit f la fonction R dans R définie par : f (x) = x2 + x + 1. Démontrons que : ∀x ∈ R f (x) > 0. Soit x ∈ R. Montrons que f (x) > 0. On a :  2 1 3 f (x) = x + + , 2 4 3 et donc f (x) ⩾ 4 > 0. D’où le résultat. Remarque : Dans le cas particulier où E = N, pour prouver une assertion du type ∀n ∈ N P (x), on peut évidemment penser à utiliser une démonstration par récurrence. Pour démontrer une assertion du type : ∃x ∈ E P (x) 12 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES — Si l’on dispose d’un candidat évident, il suffit de l’exhiber. — Si un tel élément n’est pas évident à trouver, on peut commencer par une phase d’analyse. On suppose qu’un tel élément existe, et on en déduit certaines de ses propriétés. Ceci nous donne des conditions nécessaires. Cette étape peut rester au brouillon. D’est qu’on trouve un élément qui convient l’assertion est démontrée. Exemple 1.19. Soit f la fonction de R dans R définie par f (x) = x2 + x + 1. Montrer que ∃x ∈ R f (x) > 2. (Exhiber x = 1). Exemple 1.20. Montrer qu’il existe un rationnel x tel que 3x3 + 4x2 + 4x + 1 = 0. Faire une analyse-synthèse. Sur une copie, il suffit de rédiger la partie de vérification du candidat qui est bon. Pour démontrer une assertion du type : ∃!x ∈ E P (x) Cette méthode de démonstration sert lorsque l’on veut montrer l’existence et l’unicité d’une décomposition. On l’énonce souvent ainsi “Montrer que x ∈ E se décompose de façon unique selon [...]”. Dans ce cas on procède de façon similaire, voici le résumé. — On commence toujours par montrer qu’il existe au plus une telle décomposition. On procède en supposant que l’on a deux décompositions et on montre qu’elles sont égales. Souvent la décomposition que l’on cherche est un couple (y, z) tel que x = y + z, avec des propriétés bien particulières sur y et z. La première idée est d’écrire y1 − y2 = z2 − z1 , où les deux décompositions sont (y1 , z1 ) et (y2 , z2 ). On se sert des propriétés de y et z pour montrer que y1 − y2 = 0 ou z2 − z1 = 0. — Pour la partie existence, on procède par analyse-synthèse. On se sert du fait que l’on a montré l’unicité en premier. Dans l’étape d’analyse, on suppose x = y + z, et on veut isoler y en utilisant des opérations usuelles (il faut se servir des différences entre les propriétés de y et z). Si on trouve y comme une fonction de x, alors on peut passer à la synthèse, où il suffit de vérifier que le y que l’on a trouvé et z = x − y vérifient les propriétés voulues et on conclut. Exemple 1.21. Soit f : R → R une fonction de R dans R. Montrons qu’il existe un unique couple (g, h) de fonctions de R dans R telles que : g est paire, h est impaire et pour tout x réel, f (x) = g(x) + h(x). On suit le procédé ci-dessus. — Montrons d’abord l’unicité. Soit (g1 , h1 ) et (g2 , h2 ) deux telles décompositions. Alors, pour tout x réel, g1 (x) − g2 (x) = h2 (x) − h1 (x) ou encore (g1 − g2 )(x) = (h2 − h1 )(x) , où l’on définit la somme de deux fonctions point par point. Notons ℓ = g1 − g2. Comme g1 et g2 sont paires, pour tout x ∈ R on a g1 (x) − g2 (x) = g1 (−x) − g2 (−x), ainsi ℓ est paire. De même, comme h1 et h2 sont impaires, h2 −h−1 est aussi impaire. Or par l’égalité ci-dessus, on obtient que ℓ est une fonction paire et impaire. Ainsi, pour tout x ∈ R, parité imparité ℓ(x) = ℓ(−x) = −ℓ(x). Ceci montre que ℓ(x) = 0. La fonction ℓ est constante égale à zéro, ce qui implique les égalités de fonctions g1 = g2 et h1 = h2. D’où l’unicité. 1.3. LOGIQUE ET RAISONNEMENT 13 — Montrons maintenant l’existence par analyse-synthèse. Analyse. Supposons que f = g + h avec g paire et h impaire. Pour isoler g, on doit utiliser le fait que h est impaire. Calculons f (x) + f (−x) et utilisons les hypothèses, f (x) + f (−x) = g(x) + h(x) + g(−x) + h(−x) = 2g(x). f (x)+f (−x) Ainsi on trouve g(x) = 2. Ce qui termine notre étape d’analyse. Synthèse. Par définition, pour tout x ∈ R, g(−x) = f (−x)+f 2 (x) = g(x), ainsi g est paire. De plus, posons h = f − g, ce qui équivaut à dire, pour tout x ∈ R, f (x) − f (−x) h(x) =. 2 Montrons que h est impaire. Soit x ∈ R, h(−x) = f (−x)−f 2 (x) = −h(x), ce qui était voulu. En conclusion on a trouvé une décomposition f = g + h avec g paire et h impaire. La puissance d’avoir fait l’unicité avant est que l’on sait que si on isole y en fonction de x avec la bonne propriété (dans l’exemple c’était g en tant que fonction de f ), on est sûrs que c’est la seule possibilité. En général, l’unicité est plus simple, et on aime bien aussi commencer par la partie la plus simple. Pour utiliser une hypothèse du type : ∀x ∈ E P (x) On peut dans ce cas utiliser P (x) pour n’importe quel x dans E. La plupart du temps, il suffit de choisir un bon élément, dépendant du but recherché. Exemple 1.22. Soit a et b deux réels et f la fonction de R dans R définie par f (x) = ax2 + b. Montrons que (∀x ∈ E, f (x) = 0) ⇒ a = b = 0. Supposons donc ∀x ∈ E, f (x) = 0. — Pour x = 0, on obtient que b = 0. — Puis, pour x = 1, on obtient que a = 0. On en déduit a = b = 0, ce qui termine la démonstration. Remarque : L’hypothèse était vraie pour une infinité de points, mais deux points nous ont suffit pour conclure ! Pour utiliser une hypothèse du type : ∃x ∈ E P (x) Dans ce cas, on peut introduire un élément x ∈ E qui vérifie P (x), mais il faut l’introduire par une phrase du type “Prenons x ∈ E tel que P (x)”. Il faudra faire avec cet élément donné qui, sans justification supplémentaire, n’a pas d’autres propriétés. Exemple 1.23. Soit a et b deux réels non nuls et soit f la fonction définie par ( R → R f:. x 7→ ax2 + b Montrons que si la fonction f s’annule, alors les réels a et b vérifient ab < 0. Supposons que f s’annule. Autrement dit ∃x ∈ R, f (x) = 0. Soit x ∈ R tel que f (x) = 0, i.e. ax2 + b = 0. — Comme b ̸= 0, on a x ̸= 0. 14 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES — En multipliant l’équation par a et en réordonnant les termes, on a ab = −(ax)2. Or a ̸= 0 et x ̸= 0, donc −(ax)2 < 0 ce qui donne le résultat. Remarque : Le nombre réel fourni par l’hypothèse étant a priori quelconque, on a dû justifier x ̸= 0 avant de conclure. Exemple 1.24. Soit a et b deux entiers naturels. On suppose : (∃n ∈ N, a = bn) et (∃n ∈ N, b = an). Montrer que a = b Attention, dans l’hypothèse ci-dessus, rien ne précise que l’entier n vérifiant a = bn est égal à l’entier n vérifiant b = an. La variable n est muette dans la première partie de la proposition, on pourrait l’écrire aussi avec deux variables muettes différentes. 1.3.4 Propriétés élémentaires des quantificateurs Négation de quantificateurs Si P (x) est une assertion dépendant d’une variable x ∈ E, alors : — la négation de “∀x ∈ E, P (x)” est “∃x ∈ E, ¬ P (x)”. — la négation de “∃x ∈ E, P (x)” est “∀x ∈ E, ¬ P (x)”. Exemple 1.25. La négation de “∀x ∈ E A(x) ⇒ B(x)” est ∃x ∈ E A(x) ∧ (¬ B(x)). En effet l’implication s’écrit aussi (¬ A(x)) ∨ B(x). Exemple 1.26. Comment écrire la négation de ∀x ∈ E (A(x) ⇔ B(x)) ? Action des quantificateurs sur une conjonction ou une disjonction Soit P (x) et Q(x) deux assertions dépendant d’une variable x ∈ E. On a les équivalences suivantes : — (∀x ∈ E P (x) ∧ Q(x)) ⇔ (∀x ∈ E P (x)) ∧ (∀x ∈ E Q(x)), — (∃x ∈ E P (x) ∨ Q(x)) ⇔ (∃x ∈ E P (x)) ∨ (∃x ∈ E Q(x)). On a aussi les implications suivantes, — (∃x ∈ E P (x) ∧ Q(x)) ⇒ (∃x ∈ E P (x)) ∧ (∃x ∈ E Q(x)), — (∀x ∈ E P (x) ∨ Q(x)) ⇐ (∀x ∈ E P (x)) ∨ (∀x ∈ E Q(x)). On pourra se servir de l’exemple suivant : E = R, P (x) : x ⩽ 0 et Q(x) : x > 0. Succession de quantificateurs On peut quantifier plusieurs variables sur une même assertion, par exemple “tout entier naturel est le carré d’un entier naturel” s’écrit avec des quantificateurs : ∀n ∈ N, ∃p ∈ N, n = p2. Quelle est sa négation ? Parfois on va quantifier seulement certaines des variables : ∀x ∈ Rf (x) ⩾ f (a) signifie “f admet un minimum en a. Et dans ces cas, quantifier les autres autres variables change le sens de 1.4. RÉCURRENCE 15 l’assertion, en général. Par exemple : ∃a ∈ R∀x ∈ Rf (x) ⩾ f (a) signifie “f admet un minimum”. Inversion de quantificateurs Soit P (x, y) une assertion dépendant de deux variables x ∈ E et y ∈ F. Alors (∀x ∈ E , ∀y ∈ F , P (x, y)) ⇔ (∀y ∈ F , ∀x ∈ E , P (x, y)) , (∃x ∈ E , ∃y ∈ F , P (x, y)) ⇔ (∃y ∈ F , ∃x ∈ E , P (x, y)). On dit que deux quantificateurs ∀ successifs commutent et que deux quantificateurs ∃ successifs commutent. Les autres quantificateurs ne peuvent pas s’échanger en général, par exemple ∃x ∈ R ∀y ∈ R y = x + 1. 1.4 Récurrence On admettra la propriété suivante Proposition 1.9. Toute partie non vide de N possède un plus petit élément. 1.4.1 Récurrence simple Dans la suite, P sera une propriété définie sur N, i.e. P (n) est une assertion pour tout n. Théorème 1.10. Si P (0) est vraie et si ∀n ∈ N P (n) ⇒ P (n + 1) , (1.3) alors P (n) est vraie pour tout entier n. Démonstration. Raisonnons par l’absurde en supposant que P n’est pas vraie sur tout N. On pose A = {n ∈ N : P (n) est fausse}. Par hypothèse, cette partie de N est non vide. Donc elle admet un plus petit élément n0. — Comme P (0) est vraie par hypothèse, alors 0 ∈ / A est donc n0 > 0. Ainsi n0 − 1 ∈ N. — Par construction de n0 , l’entier n0 − 1 n’appartient pas à A, et donc P (n0 − 1) est vraie. Par l’autre hypothèse (1.3), on a que P (n0 ) est vraie et donc n0 ∈ / A. Contradiction. D’où le résultat. On écrit une récurrence en trois étapes : — On explicite l’assertion P (n) que l’on veut montrer, — Initialisation : on prouve P (0), — Hérédité : on montre que ∀n ∈ N P (n) ⇒ P (n + 1). Exemple à faire à la maison en relisant son cours Exemple 1.27. Soit f une fonction strictement croissante de N dans N. Montrons par récurrence que ∀n ∈ N f (n) ⩾ n. Récurrence à partir d’un certain rang 16 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES Corollaire 1.11. Soit n0 un entier. Si P (n0 ) est vraie et si ∀n ⩾ n0 P (n) ⇒ P (n + 1) , alors la propriété P (n) est vraie pour tout entier n ⩾ n0. Démonstration. On applique le théorème précédent avec la propriété P (n0 + n) Exemple : voir DM. 1.4.2 Récurrence double Parfois, pour montrer P (n), on a besoin de P (n − 1) et P (n − 2). Alors on fait une récurrence double ou récurrence d’ordre 2, fondée sur le résultat suivant. Corollaire 1.12. Si P (0) et P (1) sont vraies et si : ∀n ∈ N (P (n) ∧ P (n + 1)) ⇒ P (n + 2) , alors la propriété P (n) est vraie pour tout n ∈ N. Démonstration. On applique le théorème précédent à la propriété H(n) : P (n) ∧ P (n + 1). Lors de la rédaction d’une récurrence d’ordre deux, on n’oubliera pas de démontrer P (0) et P (1) à l’étape d’initialisation. 1.5 Récurrence forte Il arrive parfois que la justification de P (n) nécessite toutes les propriétés P (k) pour k entier entre 0 et n − 1. On fait alors une récurrence forte. Corollaire 1.13. Si P (0) est vraie et si : ∀n ∈ N∗ (P (0) ∧ · · · ∧ P (n − 1)) ⇒ P (n) , alors la propriété P (n) est vraie pour tout n ∈ N. Démonstration. On montre par une récurrence simple à partir du rang 1 que la propriété H(n) : ∀k ∈ {0,... , n} P (k) , est vraie pour tout n ∈ N∗. Exemple à la maison : “Tout entier naturel supérieur ou égal à 2 possède (au moins) un diviseur premier.” On posera P (n) : n possède une diviseur premier. 1.5. RÉCURRENCE FORTE 17 1.5.1 Récurrences finies Corollaire 1.14 (Récurrence finie). Soit r ∈ N. Si P (0) est vraie et si : ∀n ∈ {0,... , r − 1} P (n) ⇒ P (n + 1) , alors P (n) est vraie pour tout n ∈ {0,... , r}. Démonstration. Appliquer le théorème de la récurrence simple à H(n) : (n > r) ∨ P (n). En effet la partie (n > r) est fausse dans la partie qui nous intéresse et devient vraie lorsque P n’a plus de certitude d’être vraie. Corollaire 1.15 (Récurrence finie descendante). Soit r ∈ N. Si P (r) est vraie et si ∀n ∈ {1,... , r} P (n) ⇒ P (n − 1) , alors P (n) est vraie pour tout n ∈ {0,... , r}. Démonstration. Appliquer le corollaire précédent à la propriété H(n) = P (r − n). On peut combiner récurrence forte et descendante, ou finie. 18 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE ET DE THÉORIE DES ENSEMBLES