Logique mathématique : introduction.Paul RozièreParis 7 – MT306229 septembre 2004(version provisoire — 17: 36)1Introduction.La logique est souvent associée à « l’art de raisonner ». Elle étudie un certain type de discoursargumenté, étude qui a commencé très tôt. Ainsi Aristote ( 300 av JC), dégage certaines figuresde raisonnement(les syllogismes)qui sontvalides indépendamment des assertionsqu’elles mettenten oeuvre. C’est exactement le terrain d’étude de la logique : ce qui dans le raisonnement estindépendant du sujet étudié.Trèstôtégalementlalogiqueestassociéeauxmathématiques,commeterraind’étudeprivilégié.Déjà l’ambition des mathématiciens grecs de l’antiquité est effet de présenter leur science commepurement déductive : les théorèmes se déduisent d’autres théorèmes et ultimement de certainsaxiomes bien identifiés considérés comme évidents. Les chaînes de déductions sont purement for-melles : elles peuvent être établies indépendamment du sujet étudié. Les éléments d’Euclide ( 300av JC) en sontl’exemple le plus achevé, puisqu’il va constituer le cadre formel des mathématiqueseuropéennes jusqu’au XVIIième siècle.Cependant, sans négliger les apports antérieurs, on peut dire que la logique moderne – celleque nous allons étudier – date essentiellement de la deuxième moitié du XIXième siècle, avec lestravaux fondateurs de George Boole, Augustus De Morgan, Charles S. Peirce et surtout GottlobFrege.Le développement du calcul intégral et du calcul ...
Logique mathématique : introduction.
Paul Rozière
Paris 7 – MT3062
29 septembre 2004
(version provisoire — 17: 36)
1Introduction.
La logique est souvent associée à « l’art de raisonner ». Elle étudie un certain type de discours
argumenté, étude qui a commencé très tôt. Ainsi Aristote ( 300 av JC), dégage certaines figures
de raisonnement(les syllogismes)qui sontvalides indépendamment des assertionsqu’elles mettent
en oeuvre. C’est exactement le terrain d’étude de la logique : ce qui dans le raisonnement est
indépendant du sujet étudié.
Trèstôtégalementlalogiqueestassociéeauxmathématiques,commeterraind’étudeprivilégié.
Déjà l’ambition des mathématiciens grecs de l’antiquité est effet de présenter leur science comme
purement déductive : les théorèmes se déduisent d’autres théorèmes et ultimement de certains
axiomes bien identifiés considérés comme évidents. Les chaînes de déductions sont purement for-
melles : elles peuvent être établies indépendamment du sujet étudié. Les éléments d’Euclide ( 300
av JC) en sontl’exemple le plus achevé, puisqu’il va constituer le cadre formel des mathématiques
européennes jusqu’au XVIIième siècle.
Cependant, sans négliger les apports antérieurs, on peut dire que la logique moderne – celle
que nous allons étudier – date essentiellement de la deuxième moitié du XIXième siècle, avec les
travaux fondateurs de George Boole, Augustus De Morgan, Charles S. Peirce et surtout Gottlob
Frege.
Le développement du calcul intégral et du calcul infinitésimal introduits par Isaac Newton
et Gottfried Leibniz au cours du XVIIième siècle, a conduit à sortir du cadre de la géométrie
d’Euclide. C’est au cours du XIXème siècle que l’on définit formellement les notions qui fondent
l’analysemoderne comme celles de limite, et de continuité. L’ambition de certainsmathématiciens
comme Richard Dedekind et Georg Cantor est alors de redonner des fondements axiomatiques
sûrs aux mathématiques, en partant non plus de la géométrie mais de l’arithmétique, puis de la
notion d’ensemble.
1Parallèlement l’ambition de certains logiciens de l’époque est de mathématiser la logique, de
l’axiomatiser de la même façon qu’une théorie mathématique, et ils utilisent pour cela des notions
et des notations, comme la notation fonctionnelle, les variables, apparues en mathématique.
Lepremiersystèmelogiqueàlafoisentièrementformaliséetsuffisammentrichepourformaliser
les mathématiques (mais ce n’était pas sa seule ambition) est dû à Frege en 1879.
Fregesouhaite donnerdes fondements purementlogiquesaux mathématiques. Il rejointen cela
Cantor qui fonde les mathématiques sur la théorie des ensembles (mais ne cherche pas à forma-
liser la logique elle même). La notion d’ensemble est en effet très proche de de la notion logique
de “prédicat” (une propriété définit l’ensemble des objets ayant cette propriété). La théorie des
ensembles est d’ailleurs considérée actuellement comme une branche de la logique mathématique.
Le développement de la logique a permis ensuite de clarifier puis de reformuler ces axioma-
tisations, après la découverte de paradoxes dans les théories de Cantor et Frege. L’élaboration
de la logique comme discipline mathématique a permis au début du XXième siècle de poser de
façon précise un certain nombre de problèmes relatifs aux fondements des mathématiques (c’est
le cas d’un certain nombre des “problèmes futurs des mathématiques” listés en 1900 par David
Hilbert). Ainsi Kurt Gödel a pu démontrer en 1931 le premier théorème d’incomplétude, qui fixe
les limites des axiomatisations, à savoir que dans toute théorie axiomatique “raisonnable”, c’est
à dire pour laquelle il est possible de reconnaître mécaniquement les axiomes parmi les énoncés
2de la théorie et “suffisamment expressive”, c’est à dire permettant de développer l’arithmétique ,
il restera toujours des énoncés qui ne sont pas conséquences de la théorie en question et dont la
négation n’est pas non plus conséquence de la théorie. Dit d’une façon plus platonicienne, il existe
des énoncés “vrais” de l’arithmétique qui ne sont démontrables dans aucune théorie axiomatique
“raisonnable”.
Ce cours est un cours d’introduction. On s’efforcera d’abord de faire saisir les notions fon-
damentales comme celles de démontrabilité et de vérité. Le théorème le plus élaboré que nous
démontrerons, le théorème de complétude de Gödel, fera justement le rapport entre ces deux no-
tions. On verra également dans quelle mesure on peut axiomatiser les mathématiques et de quelle
1Le premier à poser un tel programme est le mathématicien et philosophe du XVIIième siècle Leibniz
2il est tout à fait possible de donner un sens précis à ces deux hypothèses
2façon. On ne démontrera pas le théorème d’incomplétude de Gödel cité au paragraphe précédent,
mais au moins son énoncé devrait devenir plus compréhensible.
Afin d’éviter les malentendus, précisons que ce cours ne traite que de logique mathématique.
Bien-sûr la logique ne se réduit pas à la logique mathématique. Cette dernière a quelques ca-
ractéristiques très particulières. Elle est bien plus pauvre que la logique naturelle : la logique
mathématique classique n’a que deux valeurs de vérités, un énoncé est vrai ou faux, il n’y a pas
de notion d’incertain, de possible, de nécessaire, le temps n’intervient pas ... Mais en un autre
sens la logique mathématique estbien plus richeque la logique naturelle : les énoncés peuventêtre
beaucoup plus complexes, certains raisonnements comme le raisonnement par l’absurde semblent
surtout utilisés en mathématique, les chaînes de déductions sont beaucoup plus longues...
Ce cours ne sera pas non plus un apprentissage de «l’art de raisonner» en mathématique.
La logique des mathématiques repose sur le présupposé d’une aptitude commune à raisonner qui
nous permet de communiquer et de convaincre qu’un raisonnement est correct. S’il existe bien un
raisonnement mathématique, il s’élabore sur une spécialisation du raisonnement commun dans le
contexte des mathématiques. Ses spécificités s’acquièrent d’abord ... par la pratique des mathé-
matiques (y compris bien-sûr la pratique de la logique mathématique), même si nous espérons que
la formalisation de la logique que nous allons donner permettra de clarifier et de préciser cette
pratique.
31 Une présentation informelle du langage de la logique ma-
thématique.
Il n’est bien-sûr pas question d’étudier la langue mathématique en général.
Tout d’abord un texte mathématique contient quasi forcément des éléments de nature non
mathématique, annotations utiles à la compréhension d’une preuve, mais aussi rappels historiques
et bien d’autres choses.
Ensuite le langageformel que nous allons décrire est artificiel et ne couvre pas tous les énoncés
mathématiques tels quels. Par exemple nous n’accepterons pas directement la formulation «Tout
entiernaturel estpairou impair»,que l’on considèrecomme une abréviationde «∀x∈N(pair(x)∨
impair(x))», àsupposerquepair etimpair aientétéintroduits dansle langageformel.L’avantage
est que ce langage artificiel peut être présenté de façon précise et étudié mathématiquement.
L’étude du langage mathématique en général serait un travail (difficile) de linguistique.
Nous allons commencer de décrire, assez informellement pour le moment, un langage formel
pour lesmathématiques, en isolantet précisantun certainnombrede notationsdu langagemathé-
matique usuel. Il y a un peu d’arbitraire dans certains des choix de formalisation : nous essayons
d’être compatibles avec l’assistant de preuves Phox qui sera utilisé en travaux pratiques.
Les notations que nous allons utiliser (∀, ∃, ⇒...), ne sont pas celles introduites par Gottlob
Frege qui ont eu peu de succès, entre autre à cause de leur complexité. Elles sont essentiellement
dues à Giuseppe Peano (1894) (à quelques questions de graphie près), et ont été popularisées par
les “Principia mathematica” de Bertrand Russell et Alfred Whitehead (1910). Elles sont pour la
plupart assez communes dans les mathématiques actuelles.
1.1 Les objets, les énoncés, les preuves.
En mathématiques on traite d’objets : les nombres, les points, les droites, les ensembles, etc.
On énonce des propriétés de ces objets — les énoncés mathématiques — de façon