Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

(V",",W iN '$ ., Sil""." au SS:UhJiOiUSUa INITIATION AU RAISONNEMENT MATHÉMATIQ

(V",",W iN '$ ., Sil""." au SS:UhJiOiUSUa INITIATION AU RAISONNEMENT MATHÉMATIQUE Logique et théorie des ensembles ~ ARMAND COLIN 1> I~p 1 1 Tous droits de traduction, d'adaptation et de reproduction par tous procédés, réser- vés pour tous pays. Toute reproduction ou représentation intégrale ou partielle, par quelque procédé q,:e ce soit, des pages publiées dans le présent ouvrage, faite sans l'autorisation de l'édI- teur est illicite et constitue une contrefaçon. Seules sont autorisées, d'une part, les repro- ductions strictement réservées à l'usage privé du copiste et non destinées à une utilisa- tion collective, et d'autre part, les courtes citations justifiées par le caractère scientifI- que ou d'information de l'œuvre dans laquelle elles sont incorporées (L. 122-4, L. 122-5 et L. 335-2 du Code de la propriété intellectuelle). Des photocopies payantes peuvent être réalisées avec l'accord de l'éditeur. S'adr~ ser au Centre Français d'exploitation du droit de copie, 3, rue Hautefeuille, 75006 pans Tél. : 43.26.95.35. N216284 © Armand Colin Éditeur, Paris, 1993 ISBN; 2-200-21376-X Armand Colin f."diteur, 103, boulevard Saint-Micllel, 75240 Paris Cedex 05. TABLE DES MATIÈRES INTRODUCTION .................................................................................................. 5 1. ELÉMENTS DE LOGIQUE 1.1. le calcul propositionnel ou calcul assertionnel .......................... 7 a. But du calcul assertionnel ................................................................ 7 b. Assertions équivalentes ................................................................... 9 c. Négation d'une assertion ................................................................. 9 d. Connecteurs binaires usuels ......................................................... 10 e. Quelques règles logiques .............................................................. 14 1.2. Notion de prédicat ou d'''assertlon'' .............................................. 17 a. Définitions et exemples .................................................................. 17 b. Quantificateurs .............................................................................. 19 c. Quelques remarques sur l'utilisation des quantificateurs .............. 25 d. Sur les avantages à utiliser les quantificateurs .............................. 27 2. LOGIQUE DU RAISONNEMENT MATHÉMATIQUE MÉTHODES USUELLES DE DÉMONSTRATION 2.1. la démonstration en mathématique .............................................. 31 2.2. les démonstrations élémentaires directes ................................. 38 a. Méthodes de démonstration des propositions P A Q, P vQ .............................................................................................. 39 b. Une méthode de démonstration de la proposition (\;1 x E D, P(x)) ............................................................................... 39 c. Une méthode de démonstration de la proposition (3 x E D, P(x)}. la notion de contre-exemple .............................. 41 d. Utilisation itérée des méthodes précédentes ................................. 45 2.3. les démonstrations indirectes ....................................................... 47 a. La démonstration de (P ~ Q) par contraposition ........................ 47 b. La démonstration par l'absurde ..................................................... 47 c. La démonstration par disjonction des cas ...................................... 49 2.4. la démonstration par récurrence .................................................. 50 3. NOTIONS FONDAMENTALES DE LA THÉORIE DES ENSEMBLES 3.1. Généralités sur les ensembles ........................................................ 53 a. Eléments et parties d'un ensemble ••..•...•....••...•••...••.•.•.••.••............ 53 b. Inclusion ........................................................................................ 56 c. Opérations sur les ensembles ....................................................... 56 cl. Généralisation de l'intersection et de la réunion ............................ 59 3.2. Relations entre ensembles .............................................................. 60 a. Généralités .................................................................................... 60 b. Relations d'équivalence sur un ensemble ..................................... 62 C. Relations d'ordre sur un ensemble ................................................ 63 3.3. Applications d'un ensemble dans un autre ................................ 66 a. Généralités sur les applications ..................................................... 66 b. Applications surjectives. injectives et bijectives ............................. 71 c. Image directe et image réciproque de sous-ensembles ................ 73 3.4. ComparaIson des ensembles notions sur les cardinaux ................................................................ 75 4. EN GUISE DE CONCLUSION ••• .. ............................................................. 79 5. FICHES D'EXERCICES FICHE N° 1 - Connecteurs, règles logiques, démonstration de (P ~ Q), définitions et exemples de prédicats Enoncés ............................................................................................. 81 Indications et réponses ...................................................................... 86 FICHE W 2 - Prédicats ou "assertions" Enoncés ............................................................................................. 96 Indications et réponses .................................................................... 1 02 FICHE N° 3 - Raisonnements élémentaIres Enoncés ........................................................................................... 1 08 Indications et réponses .................................................................... 111 FICHE N° 4 - Raisonnements par contraposltlon. par l'absurde, par disjonction des cas et par récurrence Enoncés ........................................................................................... 123 Indications et réponses .................................................................... 125 FICHE N° 5 - Encore quelques exercices ... Enoncés ........................................................................................... 132 Indications et réponses .................................................................... 135 INDEX TERMINOLOGIQUE .............................................................................. 143 INDEX DES NOTATIONS .................................................................................. 144 r INTRODUCTION Ce livre fournit une méthodologie en Mathématique. Il est donc recommandé aux étudiants des cursus scientifiques universitaires. Il peut être utilisé au fur et à mesure des besoins durant les deux premières années, mais aussi en entrée ou prérentrée de première année, en introduction aux cours d'algèbre, d'analyse, et de langage de programmation. Nous le destinons également aux étudiants-professeurs des Instituts Universitaires de Formation des Maîtres; nous espérons aussi que nos collègues, enseignants de premier cycle, y trouveront une motivation pédagogique supplémentaire. Il a servi de base à un enseignement de prérentrée, de 30 heures, pour 300 étudiants d'une section de première année de DEUG A (Sciences) de l'Institut des Sciences et Techniques de l'Université de Valenciennes et du Hainaut Cambrésis. Depuis plusieurs années, nous cherchons les raisons des blocages et échecs en Mathématique; nous sommes maintenant persuadés que la raison principale est le manque de connaissances de base: écriture et lecture insuffisantes du langage mathématique (par exemple, utilisation incorrecte des quantificateurs et du symbole "=>" d'implication), mais aussi méconnaissance des méthodes élémentaires de démonstration qui paralyse l'étudiant lorsqu'il commence un exercice. Nous avons également constaté que les étudiants en difficulté ne sont pas ceux qui travaillent le moins: ce sont peut-être ceux qui ont besoin de supports écrits en logique. Il faut bien reconnaître que ces supports manquent; si les ouvrages, pour la plupart, comportent maintenant une initiation convenable à la théorie des ensembles, ils sont, par contre, fort concis et imprécis en ce qui concerne l'initiation à la logique du raisonnement: cette initiation se fait donc, malheureusement, uniquement oralement, par bribes et redites durant de nombreuses années. C'est précisément cette tradition orale que nous aimerions faire passer ici sur papier: travail ingrat (comment expliquer des "évidences", expliquer "l'inexplicable" ?) mais aussi travail enthousiasmant quand le but visé est d'aider certains étudiants à jouer avec les Mathématiques et à ne pas les subir. Nous ne prétendons pas amener tout de suite chaque étudiant au "sommet" car la résolution de certains problèmes nécessite beaucoup d'expérience et d'intuition (voir l'exemple du 2.3.b ); mais l'expérience semble prouver qu'un étudiant possédant les bases logiques parvient largement à la moyenne dans la 5 plupart des examens et concours. En outre, une manipulation rigoureuse des objets mathématiques facilite la compréhension des domaines connexes comme la physique et l'informatique. Cet ouvrage ne comporte que des notions bien connues de tout enseignant de Mathématique. Désirant nous limiter à la seule logique utile aux Mathématiques des deux premières années de l'enseignement supérieur, nous avons évité les rapprochements avec les langages, les systèmes formels, l'informatique ou l'automatique. Ainsi, pour ne pas donner au lecteur des habitudes trop éloignées du langage mathématique usuel, nous avons, comme partout, accepté un langage assez simple: par exemple, nous dirons indifféremment montrons P ou montrons qu'on a P ou encore montrons que P est vraie; le lecteur veîllera cependant à ne pas confondre considérons P avec considérons qu'on a P, ou soit l'assertion (P ~ Q) avec supposons (P => Q) . Nous avons toutefois signalé la différence entre les prédicats (ou fonctions assertionnelles) et les assertions qui sont les prédicats constants; mais très vite, pour rejoindre les Mathématiques usuelles, nous avons appelé le prédicat. "assertion" (avec guillemets); le lecteur n'aura qu'à retirer les guillemets pour rejoindre l'appellation usuelle. Nous avons aussi été amenés à distinguer une assertion (qui peut être vraie ou fausse) d'une proposition (qui est toujours vraie) : cela n'est pas en accord avec la tradition qui, le plus souvent, utilise, à tort sans doute, la seule appellation proposition. Il nous a semblé utile de présenter, au chapitre 3, les notions fondamentales de la théorie des ensembles nécessaires à tout enseignement de mathématiques de l'enseignement supérieur. Dans un premier temps, le lecteur ne s'y reportera qu'en cas de besoin lorsqu'une notation, rencontrée par ailleurs. lui semblera devoir être précisée. Le lecteur trouvera en fin d'ouvrage cinq fiches d'exercices qui lui permettront d'assimiler les connaissances développées dans le cours. Nous remercions vivement tous les collègues qui ont favorisé ce projet; en particulier, B. Dussart et A. Kabila pour leur participation active et enthousiaste à l'expérience et leur contibution aux fiches d'exercices. B. Sodaigui pour son apport d'une partie des énoncés des exercices de la fiche n° 4, ainsi que A. Fréville et J. M, Raviart, directeur et directeur-adjoint de l'Institut des Sciences, grâce à qui ce cours est enseigné à l'Université de Valenciennes. Nos remerciements vont également à tous les étudiants et collègues qui par leurs remarques nous ont permis d'améliorer le manuscrit. Puisse cet ouvrage permettre de jouer aux Mathématiques! Les auteurs - Juin 1993 6 ELÉMENTS DE LOGIQUE a 1.1. Le calcul propositionnel ou calcul assertionnel a. But du calcul assertionnel Dans le cadre d'une théorie 1 mathématique "G donnée, une assertion est une phrase2 mathématique à laquelle on peut attribuer une et une seule valeur de vérité, à savoir vrai (Ven abrégé) ou faux (F en abrégé). Toutes les phrases d'une théorie ne sont pas des assertions; il en existe auxquelles il est impossible d'attacher une valeur de vérité; elles sont dites indécidables. Sans aborder cette question ici, signalons qu'il ne faut pas confondre "indécidable" et ·sans signification"; nous ne rencontrerons que peu de phrases indécidables; nous ne rencontrerons dans les exercices et exemples que des assertions vraies ou fausses, et des expressions sans signification mathématique. uploads/Philosophie/ dupin-introduction-to-set-theory-pdf.pdf