Logique Mathématique

Ce matériel couvre les notions fondamentales de la logique mathématique, en particulier la décidabilité, les systèmes formels, leur application au calcul des prédicats, ainsi que le théorème d’incomplétude de Gödel. Il s’adresse aux étudiants en mathématiques, informatique théorique ou logique, souhaitant comprendre les bases formelles de la démonstration et de la calculabilité.

Notion de décidabilité

Fonction récursive

Soit f une fonction partielle de ℕ dans ℕ. On dit que f est récursive (ou calculable) s'il existe un programme P tel que :

• P(n) = f(n) si n appartient au domaine de définition de f
• P(n) ne s'arrête pas (tourne indéfiniment) sinon

Une fonction récursive est donc une fonction que l'on peut programmer. Certaines fonctions ne sont pas récursives, c’est-à-dire non calculables (thèse de Church).

Ensemble récursif

Un ensemble A ⊆ ℕ est récursif si la fonction totale f : ℕ → ℕ définie par :

f(n) = 1 si n ∈ A
f(n) = 0 sinon

est récursive. Autrement dit, il existe un programme qui, pour toute donnée n, imprime "OUI" si n ∈ A, et "NON" sinon, en un temps fini.

Ensemble récursivement énumérable

Un ensemble A ⊆ ℕ est récursivement énumérable s'il existe une fonction récursive f telle que A = Dom(f), c’est-à-dire :

• Le programme imprime "OUI" en un temps fini si n ∈ A
• Le programme ne s'arrête jamais sinon

Autrement, il existe un programme sans entrée qui imprime tous les éléments de A.

Exemple : suite monotone et suite non monotone

Soit U = {u0, u1, u2, ...} une suite d'entiers naturels :

• Si U est monotone, alors l'ensemble U est récursif (on peut décider si n ∈ U).
• Si U est non monotone (exemple : suite de Goodstein), alors U est récursivement énumérable mais pas récursif. On peut énumérer ses éléments, mais il n’est pas possible de décider pour un n donné s’il appartient à U.

Suite de Goodstein

Définie pour m, n ∈ ℕ :

• u0 = m
• u1 : on écrit u0 en base 2, on remplace tous les 2 par 3, puis on enlève 1. Exemple pour m=9 : 9 = [2^2 + 1 + 1]_2, alors u1 = (3^3 + 1 + 1) - 1 = 81
• u2 : on procède de même en base 3, remplaçant tous les 3 par 4, puis on enlève 2. Exemple pour m=9 : u2 = 1023

Proposition : pour tout m ∈ ℕ, il existe n tel que un(m) = 0. La suite n’est pas monotone : elle croît rapidement puis décroît subitement.

Prédicat décidable

Un prédicat Q à k arguments est décidable (ou récursif) si l’ensemble des k-uplets pour lesquels Q est vrai est récursif. Autrement dit, il existe un programme qui, pour tout k-uplet (a1, ..., ak), imprime "OUI" si Q(a1, ..., ak) est vrai, et "NON" sinon.

Prédicat semi-décidable

Un prédicat Q est semi-décidable (ou récursivement énumérable) si l’ensemble des k-uplets pour lesquels Q est vrai est récursivement énumérable. Cela signifie qu’il existe un programme qui :

• Imprime "OUI" en un temps fini si Q(a1, ..., ak) est vrai
• Ne s’arrête jamais sinon

Ou encore, un programme sans entrée qui imprime tous les k-uplets satisfaisant Q.

Remarque importante : il est impossible de détecter la non-termination d’un programme (problème indécidable). La semi-décidabilité signifie qu’on peut reconnaître les cas positifs, mais pas forcément les négatifs.

Exemple : prédicat lié à une suite

• Si U est une suite monotone, le prédicat Q(x) = "x ∈ U" est décidable.
• Si U est non monotone, Q est semi-décidable.
• Le paradoxe du menteur (problème d’Épiménide) est ni décidable ni semi-décidable.

Cas de la logique des prédicats

• Dans le calcul propositionnel (CP0), la satisfiabilité et la validité sont décidables (par exemple via les tables de vérité).
• Dans le calcul des prédicats (CP1), la validité et la satisfiabilité sont indécidables (théorème de Church).
• Le calcul des prédicats est cependant semi-décidable : il existe des procédures qui répondent "oui" si une formule est valide, mais peuvent ne pas terminer sinon.

Introduction aux systèmes formels

Définition d’un système formel

Un système formel S est constitué de :

• Un alphabet ∑S (fini ou dénombrable)
• Un ensemble récursif FS ⊆ ∑S* des formules bien formées
• Un ensemble récursif AS ⊆ FS des axiomes
• Un ensemble fini RS de règles d’inférence (règles de déduction) r1, r2, ..., rn

Règles d’inférence

Une règle ri est notée :

A1, ..., Ap
---------
     B
ri

Ce qui signifie : à partir des formules A1, ..., Ap (prémisses), on déduit la formule B (conclusion).

Déduction

Une déduction à partir des formules A1, ..., An est une suite finie de formules B1, ..., Bp telle que chaque Bi est :

• Un axiome, ou
• Une des formules A1, ..., An, ou
• Obtenue par application d’une règle rk à des formules précédentes Bi0, ..., Bim

On note :

A1, ..., An ⊢S Bp

pour dire que Bp est déduit des hypothèses A1, ..., An dans le système S.

Théorème

Une formule A est un théorème du système S si elle admet une déduction à partir du vide (sans hypothèse) :

⊢S A

L’ensemble des théorèmes de S est noté TS.

Une déduction à partir du vide est aussi appelée preuve ou démonstration.

Propriétés des systèmes formels

• Consistance : S est consistant si aucune formule A et sa négation ¬A ne sont tous deux théorèmes de S.
• Cohérence : S est cohérent s’il existe des formules qui ne sont pas des théorèmes.
• Correction (soundness) : S est correct si TS ⊆ T, où T est l’ensemble des formules voulues comme théorèmes.
• Complétude : S est complet si T ⊆ TS.
• S est correct et complet si T = TS.
• Décidabilité : le problème de décision pour S est de savoir si TS est récursif, c’est-à-dire si le prédicat "t est un théorème de S" est décidable.

Résultats importants

• Un système formel correct est forcément consistant.
• Un système formel consistant et complet est forcément correct.
• Un système formel incomplet n’est pas décidable (généralement semi-décidable).
• Un système formel complet n’est pas forcément décidable (peut être semi-décidable).

Exemple : le jeu des allumettes

Règles :

• Un tas de n allumettes
• Deux joueurs A et B jouent à tour de rôle
• Chaque joueur retire 1 à 3 allumettes
• Le joueur qui retire la dernière allumette gagne

Le système formel JA modélise ce jeu :

• Alphabet ∑JA = {A, B} ∪ ℕ
• Formules FJA = mots de la forme (A|B)(A|B)^k avec k ∈ ℕ (ex. AB14, BB3)
• Sémantique : AB14 signifie "le joueur A est sûr de gagner si c’est au joueur B de jouer et qu’il reste 14 allumettes"
• Négation : non(AAk) = BAk, non(ABk) = BBk, etc.

Exemple de déduction :

• AA18 est un théorème (A gagne si c’est à A de jouer et 18 allumettes restantes)
• Déroulement possible : A retire 1, B retire 3, A retire 2, etc. jusqu’à ce que A gagne.

Le système JA est consistant, complet et correct.

Algorithme général d’application

Déduire-S(C, H)
/* déduire dans le système S la formule C à partir des hypothèses H */
début
  Ω := H
  répéter jusqu’à (condition d’arrêt)
    - choisir une règle ri ∈ RS et des formules A1, ..., Ak ∈ Ω telles que
      on peut déduire B par ri
    - ou choisir un axiome B ∈ AS
    - Ω := Ω ∪ {B}
fin

Remarques :

• Pour montrer qu’une formule est un théorème, on prend H = ∅.
• L’algorithme peut :
• Terminer avec C ∈ Ω (succès)
• Se bloquer (aucun choix possible, échec)
• Ne jamais terminer (boucle infinie)
• La stratégie de choix est cruciale pour la terminaison.
• Un système formel correct et qui termine est forcément complet.
• Cette procédure est appelée moteur d’inférence.

Application au calcul des prédicats

Pour montrer {H1, ..., Hn} ⊨ C ou ⊨ C, il faut un système formel correct et complet pour le calcul des prédicats (CP).

Soit CP un tel système, alors :

• {H1, ..., Hn} ⊨ C ssi H1, ..., Hn ⊢CP C
• ⊨ C ssi ⊢CP C

Correction :

Si H1, ..., Hn ⊢CP C alors {H1, ..., Hn} ⊨ C

Complétude :

Si {H1, ..., Hn} ⊨ C alors H1, ..., Hn ⊢CP C

Il existe plusieurs systèmes formels pour le calcul des prédicats :

• Méthodes déductives : système de Hilbert, système de Łukasiewicz, calcul des séquents (Gentzen)
• Méthode réfutationnelle (preuve par contradiction) : principe de résolution de Robinson

Différence :

• Méthode déductive : {hypothèses} ⊢ conclusion
• Méthode réfutationnelle : {hypothèses} ∪ {¬ conclusion} ⊢ contradiction

Théorème d’incomplétude de Gödel

Soit CP = (∑CP, FCP, ACP, RCP) un système formel correct et complet pour le calcul des prédicats.

Soit Th une théorie récursive, c’est-à-dire un ensemble récursif de formules closes formalisant une théorie mathématique (exemples : théorie des groupes, arithmétique de Peano, théorie des ensembles de Zermelo-Fraenkel).

On construit le système formel :

STh = (∑CP, FCP, ACP ∪ Th, RCP)

STh formalise la théorie Th (théorie axiomatique).

On a :

Th ⊢CP C ssi ⊢STh C

Remarque : les propriétés (consistance, complétude, etc.) de STh s’appliquent à Th.

Énoncé du théorème d’incomplétude de Gödel (1931)

1. Tout système formel consistant, formalisant l'arithmétique des entiers, est incomplet. Autrement dit, il existe une infinité d’énoncés vrais mais indémontrables dans ce système.
2. Aucun système formel consistant, formalisant l'arithmétique des entiers, ne peut prouver sa propre consistance.

Exemple : la conjecture de Fermat

« Pour tout entier n > 2, il n’existe aucun triplet d’entiers x, y, z tels que x^n + y^n = z^n »

Cette conjecture fut longtemps indémontrée, ce qui illustre la possibilité d’énoncés vrais mais indémontrables. Elle fut finalement démontrée par Andrew Wiles en 1995.

La deuxième partie du théorème répond négativement au problème de Hilbert sur la preuve de consistance de l’arithmétique à partir de ses axiomes seuls.

Gödel a ainsi montré que la démonstration mathématique ne peut être purement mécanique et que l’intuition reste nécessaire.

Biographie succincte de Kurt Gödel

• Né en 1906 à Brno, docteur à 23 ans à Vienne.
• Révolutionna les fondements logiques des mathématiques.
• Connu pour son article de 1931 sur l’indécidabilité formelle.
• Découvrit des résultats fondamentaux en théorie des ensembles (hypothèse du continu, axiome du choix).
• Étudia la relativité avec Albert Einstein et démontra la possibilité du voyage dans le passé selon la relativité générale.
• Décédé en 1978, considéré comme un des plus grands logiciens du XXe siècle.

David Hilbert et les 23 problèmes

• Mathématicien allemand, fondateur du formalisme rigoureux.
• Réussit à axiomatiser la géométrie euclidienne.
• Proposa 23 problèmes ouverts en 1900 pour guider la recherche mathématique.
• Certains problèmes liés à la décidabilité et à la complétude furent résolus négativement par Gödel et d’autres (ex. consistance de l’arithmétique).
• Exemples de problèmes : hypothèse du continu, distribution des nombres premiers, équations diophantiennes.

Glossaire des termes clés

• Fonction récursive : fonction calculable par un programme, définie sur un sous-ensemble de ℕ.
• Ensemble récursif : ensemble dont l’appartenance est décidée par une fonction récursive totale.
• Ensemble récursivement énumérable : ensemble dont les éléments peuvent être énumérés par un programme, mais dont l’appartenance n’est pas nécessairement décidée.
• Prédicat décidable : prédicat dont la vérité peut être décidée par un programme terminant toujours.
• Prédicat semi-décidable : prédicat dont la vérité peut être reconnue par un programme qui peut ne pas terminer sinon.
• Système formel : structure composée d’un alphabet, d’axiomes, de formules bien formées et de règles d’inférence.
• Déduction : suite finie de formules obtenues par axiomes, hypothèses ou règles d’inférence.
• Théorème : formule déductible à partir du vide (sans hypothèse).
• Consistance : absence de contradictions dans un système formel.
• Complétude : capacité d’un système à prouver toutes les formules vraies dans son modèle.
• Décidabilité : existence d’un algorithme qui détermine en un temps fini si une formule est un théorème.
• Théorème d’incomplétude de Gödel : résultat montrant que certains systèmes formels sont incomplets et ne peuvent prouver leur propre consistance.

Points clés à retenir

• La décidabilité distingue les problèmes pour lesquels on peut toujours déterminer la vérité en un temps fini des autres.
• Les systèmes formels permettent de formaliser la déduction mathématique via des règles et axiomes.
• Un système formel peut être consistant, complet, correct, mais pas nécessairement décidable.
• Le calcul propositionnel est décidable, mais le calcul des prédicats est indécidable et seulement semi-décidable.
• Le théorème d’incomplétude de Gödel établit les limites fondamentales de la formalisation des mathématiques.
• La démonstration mécanique des théorèmes est impossible dans certains systèmes complexes, l’intuition reste nécessaire.