Diskussion:Presburger-Arithmetik

Axiome/Funktionssymbol

Hallo Eulenspiegel/IP, es gibt da in der mathematischen Logik verschiedene Varianten in der Prädikatenlogik erster Stufe. In weiten Teilen heute üblich ist es, explizit schon bei der Definition der Sprache zwischen Funktions- und Relationssymolen zu unterscheiden. Für ein Funktionssymbol $f$ ist dann $\forall x\exists yy=f(x)$ bereits ein Axiom des Kalküls oder durch Schlussregeln garantiert, muss also zur Axiomatisierung einer Theorie nicht mehr erwähnt werden. Daneben gibt es den minimalistischeren Ansatz, nur von Relations-/Prädikatensymbolen zu sprechen. Ich habe nichts gegen letzteren Ansatz, dieser Artikel scheint jedoch nach ersterem zu verfahren. Andernfalls wäre es ja etwa möglich, dass für jedes $x$ zwei Nachfolger $x+1$ existieren, solch eine Baumstruktur wäre von den Axiomen nicht ausgeschlossen. Irreführend erscheint mir hier auch, dass in der Einleitung Gleichheit als Teil der Signatur erwähnt wird, was suggeriert, dass mit Prädikatenlogik ohne Gleichheit gearbeitet würde, da bezweifel ich, dass man da nicht mehr Axiome bräuchte. Ich werde jetzt erst einmal löschen und dann Literatur zu Rate ziehen. Grüße --Chricho ¹ ² ³ 17:46, 19. Okt. 2012 (CEST)

Also MathWorld, das Handbook of Mathematical Logic (S. 603) und die angegebenen Quellen A mathematical introduction to logic (S. 197) und Super-Exponential Complexity of Presburger Arithmetic definieren die Presburger-Arithmetik nicht über Axiome, sondern als Theorie der Struktur der natürlichen Zahlen mit der Addition. Klar, da die Theorie rekursiv ist, existiert natürlich auch ein rekursives und somit vollständiges Axiomensystem. Eine explizite Form für ein solches habe ich jedoch nirgends gefunden. Es ist damit im Moment nicht einmal belegt, dass die Presburger-Arithmetik Teilmenge der Peano-Arithmetik ist. Leider ist die Originalveröffentlichung kaum aufzutreiben. --Chricho ¹ ² ³ 18:39, 19. Okt. 2012 (CEST)