Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
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 (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...) 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 éventuellement...), donc un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une...) 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'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 lui être ajouté, en un sens qu'il faut préciser dans chaque...) 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...) 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...) 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 Henri...) 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...), 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
Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.
Archives des News
  Juillet 2018
  Juin 2018
  Mai 2018
  Avril 2018
  Toutes les archives

Samedi 14 Juillet 2018 à 12:00:17 - Multimédia - 1 commentaire
» L'Internet des Objets spatial décolle
Page générée en 0.032 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