Theoreme de Lob

Theoreme de Lob

Théorème de Löb

En logique mathématique, le théorème de Löb, démontré par Martin Hugo Löb (31 mars 1921 - 21 août 2006), est une variante du second théorème d'incomplétude de Gödel. Il dit que dans toute théorie T satisfaisant les conditions de ce dernier — l'arithmétique de Peano par exemple —, pour toute formule P, s'il est démontrable que « si P est démontrable alors P », alors P est démontrable. En d'autres termes :

si T\vdash Dem_T(\ulcorner P\urcorner) \rightarrow P, alors T\vdash P

où DemT(⌈P⌉) signifie que la formule P, de nombre de Gödel ⌈P⌉, est démontrable dans T.

En résumé, l'hypothèse qu'un énoncé est démontrable dans une théorie donnée n'aide en rien la démonstration de cet énoncé dans cette même théorie.

Les théories auxquelles s'applique le théorème de Löb sont les mêmes que celles auxquelles s'applique le second théorème d'incomplétude : des théories arithmétiques (ou capables de représenter l'arithmétique) et qui peuvent représenter les démonstrations et leur combinatoire, comme l'arithmétique de Peano, et a fortiori les théories des ensembles usuelles, mais aussi une théorie arithmétique faible comme l'arithmétique primitive récursive.

Sommaire

Théorème de Löb et théorème de Gödel

Le second théorème d'incomplétude de Gödel est le cas particulier du théorème de Löb pour la formule 0 = 1 (ou toute autre formule absurde). En effet DemT(⌈0 = 1⌉)→ 0 = 1 exprime bien que 0 = 1 n'est pas démontrable, c'est-à-dire la cohérence de la théorie T, et le théorème de Löb énonce alors que si celle-ci est démontrable, alors 0 = 1 est démontrable, c'est-à-dire que la théorie est contradictoire : c'est exactement le second théorème d'incomplétude de Gödel.

Mais réciproquement on déduit assez directement le théorème de Löb pour une théorie T et un énoncé A du second théorème d'incomplétude pour la théorie T + ¬A : il suffit de remarquer que la démontrabilité de A dans la théorie T équivaut à la non cohérence de la théorie T + ¬A, et que cette équivalence très simple, qui n'est autre que le raisonnement par l'absurde, se démontre dans la théorie T (sous les hypothèses déjà nécessaires pour le théorème), c'est-à-dire que :

DemT(⌈A⌉) ≡T DemT+ ¬A(⌈0=1⌉) .

Si DemT(⌈A⌉) → A est démontrable dans T, alors dans la théorie T+ ¬A, on démontre ¬ DemT+ ¬A(⌈0=1⌉), c'est-à-dire la cohérence de cette théorie. La théorie T+ ¬A est donc contradictoire par le second théorème d'incomplétude, et donc A est démontrable dans T.

Le théorème de Löb's en logique de la démontrabilité

La logique de la démontrabilité s'abstrait des détails de l'encodage utilisé dans le théorème d'incomplétude de Gödel, exprimant la notion de démontrabilité de φ dans un système donné dans le langage de la logique modale, par le biais d'une modalité \Box.

Dans ce cadre, on peut formaliser le théorème de Löb par l'axiome suivant, connu sous le nom d'axiome GL, pour Gödel-Löb.

\Box(\Box P\rightarrow P)\rightarrow \Box P,

Cet axiome est parfois utilisé sous la forme d'une règle d'inférence :

\frac{\Box P\rightarrow P}{\Box P}

La logique GL de la démontrabilité, résultant de l'ajout de l'axiome GL à une logique modale K4, est le système de logique de démontrabilité le plus étudié.

Notes et références

  • (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Löb's theorem ».

Voir aussi

Liens externes

Bibliographie

  • (en) (en) Hinman, P., Fundamentals of Mathematical Logic, A K Peters, 2005 
  • Portail de la logique Portail de la logique
Ce document provient de « Th%C3%A9or%C3%A8me de L%C3%B6b ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Theoreme de Lob de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Théorème de Löb — En logique mathématique, le théorème de Löb, démontré par Martin Hugo Löb (31 mars 1921 21 août 2006), est une variante du second théorème d incomplétude de Gödel. Il dit que dans toute théorie T satisfaisant les conditions de …   Wikipédia en Français

  • Theoreme d'incompletude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude — de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les… …   Wikipédia en Français

  • Théorème d'incomplétude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude de Gödel — Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les propositions …   Wikipédia en Français

  • Théorème d'incomplétude de gödel — Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les propositions …   Wikipédia en Français

  • Théorème d'indécidabilité — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème de Gödel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème de Goodstein — En mathématiques, et plus précisément en logique mathématique, le théorème de Goodstein est un énoncé arithmétique portant sur les suites de Goodstein, des suites d entiers à la croissance initiale extrêmement rapide, et il établit (en dépit des… …   Wikipédia en Français

  • Indéterminabilité — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”