Arithmétique De Presburger


Arithmétique 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 Arithmétique De Presburger de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • 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 …   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

  • Mojzesz Presburger — Mojżesz Presburger (1904 1943) est un mathématicien polonais, logicien et philosophe. Élève de Tarski, il est connu pour avoir démontré la décidabilité de l arithmétique de Presburger. Il n a pas soutenu de thèse, a repris la gestion de l… …   Wikipédia en Français

  • Entier naturel — Pour les articles homonymes, voir Entier (homonymie). En mathématiques, un entier naturel est un nombre positif ou nul permettant fondamentalement de dénombrer des objets comptant chacun pour un. Un tel nombre entier peut s écrire avec une suite… …   Wikipédia en Français

  • Decidabilite et indecidabilite — Décidabilité et indécidabilité En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L indécidabilité est la négation de la décidabilité. Dans les deux cas il s …   Wikipédia en Français

  • Décidabilité — En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L indécidabilité est la négation de la décidabilité. Dans les deux cas il s agit de formaliser l idée qu… …   Wikipédia en Français

  • Décidabilité Et Indécidabilité — En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L indécidabilité est la négation de la décidabilité. Dans les deux cas il s agit de formaliser l idée qu… …   Wikipédia en Français

  • Décidabilité et indécidabilité — En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L indécidabilité est la négation de la décidabilité. Dans les deux cas il s agit de formaliser l idée qu… …   Wikipédia en Français

  • Décidable — Décidabilité et indécidabilité En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L indécidabilité est la négation de la décidabilité. Dans les deux cas il s …   Wikipédia en Français