Remerciez-le!

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

Logique mathématique Cours et exercices Il. Fonctions récursives, théorème de G

Logique mathématique Cours et exercices Il. Fonctions récursives, théorème de Gôdel, théorie des ensembles, théorie des modèles CHEZ LE MÊME ÉDITEUR Des mêmes auteurs : LOOIQUE MATHÉMATIQUE. COURS ET EXERCICES, parR. CORI et D. LASCAR. Préface de J.-L. KRIVINE. Collection Axiomes. Tome 1.- Calcul propositionnel, algèbres de Boole, calcul des prédicats. 1993,408 pages. Dans la même collection : LE THÉORÈME D'INCOMPLÉTIJDE DE GùDEL, par R.M. SMULL Y AN. Traduit de l'anglais par M. MARGENS1ERN. 1993, 160 pages environ, à paraître. Dans la collection Logique, Mathématiques, Informatique: SYSTÈMES FORMELS. INIRODUCTION À LA LOOIQUE ET À LA THÉORIE DES LANGAGES, par C. BENZAIŒN. 1991, 184 pages. ALGORITIIMIQUE ALGÉBRIQUE, avec exercices corrigés, par P. NAUDIN etC. QUITTÉ. 1992, 480 pages. MATHÉMATIQUES DISCRÈ1ES ET INFORMATIQUE, par N.H. XUONG. 1992, 432 pages. ALGORITHMES ET COMPLEXITÉ, par H.S. WILF. Traduit de l'anglais par P. ROUX. 1989, 208 pages. Dans la collection ER/ : LOOIQUE, RÉDUCTION, RÉSOLUTION, par R. LALEMENT. Préface de M. DEMAZURE. 1990, 384 pages. LAMBDA-CALCUL, TYPES ET MODÈLES, par J.-L. KRIVINE. 1990, 184 pages. LOGIQUE TEMPORELLE. Sémantique et validation de programmes parallèles, par E. AUDUREAU, P. ENJALBERT et L. FARINAS DEL CERRO. Préface de E. ENGELER. 1990, 240 pages. OUTILS LOGIQUES POUR LE TRAI1EMENT DU 1EMPS. De la linguistique à l'intelligence artificielle, par H. BESTOUGEFF et G. LIGOZAT. 1989, 272 pages. TRANSDUCTIONS RATIONNELLES. Application aux langages algébriques, par J.-M. AU1EBERT et L. BOASSON. 1988, 136 pages. Dans la collection MIM-Algorithmique, Programmation : PROGRAMMATION EN LOGIQUE, parC. J. HOGGER. Traduit de l'anglais parR. QUINIOU. Préface deR. KOWALSKI. 1987,296 pages. LOGIQUES POUR L'INTELLIGENCE ARTIFICIELLE, parR. TURNER. Traduit de l'anglais par Ph. BESNARD. 1987,296 pages. CALCULABILITÉ ET DÉCIDABILITÉ, par J.-M. AU1EBERT. 1992, 120 pages. Autres ouvrages : LES ARBRES ET LES REPRÉSENTATIONS DES PROXIMITÉS, par J.-P. BARTHÉLÉMY et A. GUÉNOCHE. Préface de M. MINOUX. Collection Méthode + Programmes. 1988, 256 pages. AXIOMES Collection de logique mathématique coordonnée par J. -L. KR/VINE Logique mathématique Cours et exercices Il. Fonctions récursives, théorème de Gôdel, théorie des ensembles, théorie des modèles René CORI Assistant à l'université Denis Diderot (Paris 7) Daniel LASCAR Directeur de recherches au CNRS Préface de J.-L. KRIVINE 2e tirage corrigé MASSON Paris Milan Barcelone 1994 Illustration de couverture : © Collection Viollet. Ouvrage rédigé avec le concours du ministère de la Recherche et de l'Espace (DIST). 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é que ce soit des pages publiées dans le présent ouvrage, faite sans l'autorisation de l'éditeur, est illicite et constitue une contrefaçon. Seules sont autorisées, d'une part, les reproductions strictement réservées à l'usage privé du copiste et non destinées à une utilisation collective, et d'autre part, les courtes citations justifiées par le caractère scientifique ou d'information de l'œuvre dans laquelle elles sont incorporées (art. 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'adres- ser au : Centre français d'exploitation du droit de copie, 3, rue Hautefeuille, 75006 Paris, tél. : 43.26.95 35. MASSON S.A. MASSON S.p.A. MASSON S.A. ©Masson, Paris, 1993 ISBN: 2-225-84080-6 ISSN : 1243-4264 120, bd Saint-Germain, 75280 Paris Cedex 06 Via Statuto 2/4, 20121 Milano Avenida Principe de Asturias 20,08012 Barcelona PREFACE La logique est, en France, une discipline traditionnellement négligée dans les études scientifiques universitaires. Cela tient, sans doute, à l'histoire récente des mathématiques dans notre pays, dominées pendant longtemps par l'école Bourbaki, dont, comme on sait, la logique n'était pas le fort. La logique part, en effet, d'une réflexion sur l'activité mathématique, et une réaction épidermique courante du mathématicien est de dire: «A quoi bon tout cela? nous ne sommes pas des philosophes, et ce n'est pas en se cassant la tête sur le modus panens ou le tiers exclu que l'on résoudra les grandes conjectures, ni même les petites». Voire ... Cependant un élément nouveau, et de taille, est venu clore ce débat un peu byzantin sur l'intérêt de la logique : l'explosion de l'informatique, dans tous les domaines de la vie économique et scientifique, dont l'onde de choc a fini par atteindre les mathématiciens eux-mêmes. Et petit à petit, une évidence se fait jour : pour cette nouvelle science en train de naître, les bases théoriques ne sont autres que cette discipline si discutée : la logique mathématique. Il est vrai que certains domaines de la logique ont été mis à contribution plus vite que d'autres. Le calcul booléen, bien sûr, pour la conception et l'étude des circuits ; la récursivité, qui est la théorie des fonctions calculables sur machine ; le théorème de Herbrand, la résolution et l'unification, qui sont à la base de la programmation dite «logique» (langage PRO LOG) ; la théorie de la démonstration, et les divers avatars du théorème de complétude, qui se révèlent de puissants outils d'analyse pour les langages de programmation évolués ... Mais, au train où vont les choses, on peut penser que le tour ne saurait tarder à venir, même pour des domaines restés encore complètement « purs », comme la théorie des ensembles, par exemple. Comme il se doit, l'interaction n'est pas à sens unique, loin de là, et un afflux d'idées et d'intuitions nouvelles et profondes, issues de l'informatique, est venu renouveler tous ces secteurs de la logique. Cette discipline est maintenant l'une des plus vivantes qui soient en mathématiques, et en évolution très rapide. Aussi l'utilité et l'actualité d'un ouvrage d'initiation générale en logique ne font-elles pas de doute, et ce livre vient donc à son heure. Issu d'un enseignement du D.E.A. de VI Préface Logique et fondements de l'Informatique à l'Université Paris 7, il couvre un vaste panorama: algèbre de Boole, récursivité, théorie des modèles, théorie des ensembles, modèles de l'arithmétique et théorèmes de Gôdel. La notion de modèle est un élément central de l'ouvrage, et c'est à fort juste titre, car elle a aussi une place centrale en logique : malgré (ou grâce à) son caractère simple et même élémentaire, elle en éclaire tous les domaines, y compris ceux qui en paraissent les plus éloignés. Comment comprendre, par exemple, une démonstration de consistance en théorie des ensembles, sans avoir d'abord maîtrisé le concept de modèle de cette théorie? comment saisir vraiment le théorème de Gôdel sans avoir une idée sur les modèles non standard de 1' arithmétique de Peano ? L'acquisition de ces notions sémantiques est, je le crois, caractéristique d'une véritable formation de logicien, à quelque niveau que ce soit. R. Cori et D. Lascar le savent fort bien, et leur livre va tout à fait dans ce sens. Qui plus est, ils ont réussi le difficile pari d'allier toute la rigueur nécessaire avec la clarté, le souci pédagogique et l'agrément de la lecture. Nous disposons donc là d'un outil remarquable pour l'enseignement de la logique mathématique, et, vu le développement de la demande en ce domaine, il devrait connaître un franc succès. C'est, bien sûr, tout ce que je lui souhaite. Paris, le 4 Novembre 1992 Jean-Louis Krivine TABLE DES MATIERES DU TOME 1 Préface . . . . . . . . . Table des matières du tome 1 Table des matières du tome II Contents Avant-propos Introduction . Mode d'emploi Chapitre 1 : Calcul propositionnel 1. Syntaxe . . . . . . . Les formules propositionnelles Démonstrations par induction sur l'ensemble des formules Arbre de décomposition d'une formule . . . . . Le théorème de lecture unique . . . . . . . . Définitions par induction sur l'ensemble des formules Substitutions dans une formule propositionnelle 2. Sémantique . . . . . . . . . . . . . . Distributions de valeurs de vérité, tables de vérité Tautologies, formules logiquement équivalentes Quelques tautologies . . . . . . . . . . . 3. Formes normales, sxstèmes complets de connecteurs Opérations dans {0,1} et formules . . . . . . · Formes normales . . . . . . Systèmes complets de connecteurs 4. Lemme d'interpolation . . . Théorème de définissabilité 5. Théorème de compacité Satisfaction d'un ensemble de formules Le théorème de compacité du calcul propositionnel Exercices . . . . . . . Chapitre 2 : Algèbres de Boole 1. Rappels d'algèbre et de topologie Algèbre . . . . . . . . . Topologie . . . . . . . . Application au calcul propositionnel 2. Définition des algèbres de Boole . . . . . Propriétés des anneaux de Boole, relation d'ordre . Les algèbres de Boole en tant qu'ensembles ordonnés v VIl x Xlii 1 3 11 15 17 17 21 23 25 28 29 32 32 38 42 46 46 50 53 55 57 59 59 62 68 79 81 81 84 90 91 91 95 VIII Table des matières du tome 1 3. Atomes dans une algèbre de Boole . . . . . 4. Homomorphismes, isomorphismes, sous-algèbres Homomorphismes et isomorphismes . . . . Sous-algèbres de uploads/Philosophie/ logique-mathematique-tome-ii-rene-cori.pdf