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 expressive 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
- ↑ On ne peut démontrer l'absurde, ou encore il existe un modèle, en fait le modèle standard des entiers naturels.
- ↑ Toute proposition est démontrable ou sa négation est démontrable.
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
