Arithmetique de Presburger

Arithmétique de Presburger

L'arithmétique de Presburger est une théorie du premier ordre, dans le langage de l'arithmétique de Peano sans la multiplication, c’est-à-dire avec seulement l'addition (et éventuellement l'ordre), en plus du zéro et de l'opération successeur. L'axiomatisation est essentiellement la même que celle de l'arithmétique de Peano, moins les axiomes de la multiplication, et avec la différence essentielle que, si le schéma d'axiomes de récurrence semble s'énoncer de la même façon, il ne couvre plus que les formules du langage de l'arithmétique de Presburger, donc un ensemble de propriétés beaucoup moins riche. Cette restriction rend l'arithmétique de Presburger beaucoup moins puissante que l'arithmétique de Peano, mais la rend également complète et décidable, contrairement à cette dernière.

Mojzesz Presburger a démontré en 1929 que son arithmétique, qui est cohérente[1], est complète[2]. Cela est impossible pour l'arithmétique de Peano, en vertu du théorème d'incomplétude de Gödel. Comme une théorie axiomatique récursivement axiomatisable et complète est décidable, on en déduit l'existence d'un algorithme qui décide, au vu d'une proposition du langage de l'arithmétique de Presburger, si celle-ci est démontrable ou non. Là encore, cela est impossible pour l'arithmétique de Peano (voir problème de la décision). En revanche, Michael J. Fisher et Michael O. Rabin ont démontré que le problème de la décision a une complexité intrinsèque doublement exponentielle, ce qui devrait rendre tout algorithme inefficace, mais en pratique il existe des implémentations qui fonctionnent bien.

Notes et références

  1. On ne peut démontrer l'absurde, ou encore il existe un modèle, en fait le modèle standard des entiers naturels.
  2. Toute proposition est démontrable ou sa négation est démontrable.
  • Portail des mathématiques Portail des mathématiques
  • Portail de la logique Portail de la logique
Ce document provient de « Arithm%C3%A9tique de Presburger ».

Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • Arithmétique De Presburger — L arithmétique de Presburger est une théorie du premier ordre, dans le langage de l arithmétique de Peano sans la multiplication, c’est à dire avec seulement l addition (et éventuellement l ordre), en plus du zéro et de l opération successeur. L… …   Wikipédia en Français

  • Arithmétique de presburger — L arithmétique de Presburger est une théorie du premier ordre, dans le langage de l arithmétique de Peano sans la multiplication, c’est à dire avec seulement l addition (et éventuellement l ordre), en plus du zéro et de l opération successeur. L… …   Wikipédia en Français

  • Arithmétique de Presburger — L arithmétique de Presburger est une théorie du premier ordre, dans le langage de l arithmétique de Peano sans la multiplication, c’est à dire avec seulement l addition (et éventuellement l ordre), en plus du zéro et de l opération successeur. L… …   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 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 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èmes 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 (en) « Sur… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

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