Die Presburger Arithmetik unterscheidet sich von der Peano-Arithmetik in einer wichtigen Einschränkung,. Die beiden Axiome zur Festlegung der Multiplikation wurden weggelassen. Die Presburger Arithmetik beschäftigt sich also mit natürlichen Zahlen und deren Addition, aber nicht mit deren Multiplikation. Der Begriff Primzahl ist beispielsweise in der Presburger Arithmetik nicht definierbar.
Die Presburger Arithmetik kann nicht alle berechenbaren Funktionen der natürlichen Zahlen darzustellen. Das beudetet, dass das Representation Theorem in ihr nicht gültig ist. Der Gödels Unvollständigkeitssatz ist hier daher nicht anwendbar. Dem Mathematiker Mojzesz Presburger gelang es 1929 zu beweisen, dass die Presburger Arithmetik vollständig und widerspruchsfrei ist. Jede wohlgeformte Aussage der Presburger Arithmetik lässt sich in endlich vielen Schritten entweder beweisen oder widerlegen. In dem formalen System ist also die Frage nach der Beweisbarkeit eines vorgegebenen Ausdrcuks entscheidbar.
Literatur zum Thema:
M. Presburger. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. Warschau, 1930.
|
Glossar 
Forschungsprojekte 
Anbieterverzeichnis 
Datenbanksuche 
Highlights 
Eintrag kommentieren