Arithmétique de Presburger
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la...) de Peano, moins les axiomes de la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .), 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 (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...), donc un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) 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 (En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique.), contrairement à cette dernière.

Mojzesz Presburger a démontré en 1929 que son arithmétique qui est cohérente[1] et complète[2]. Cela est impossible pour l'arithmétique de Peano, en vertu du théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est à distinguer...) d'incomplétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut...) de Gödel. Comme une théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur...) 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 (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive...) a une complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par...) intrinsèque doublement exponentielle (La fonction exponentielle est l'une des applications les plus importantes en analyse, ou plus généralement en mathématiques et dans ses domaines d'applications. Il existe plusieurs définitions équivalentes : un morphisme continu de...), ce qui devrait rendre tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) algorithme inefficace, mais en pratique il existe des implantations qui fonctionnent bien.

  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
Page générée en 0.035 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - Informations légales