Presburger算術
表記
Pressburger算術$ \mathbf{P}_+
言語
Pressburger算術の言語$ \mathscr{L}_{\mathbf{P}_+} := \lang =,\leq,s,+,0\rang
公理
Peano算術$ \mathbf{PA}の公理から乗算を引いたもの
ではないが
性質
完全性を持つ
すなわち，任意の論理式$ \varphiで$ \mathbf{P}_+ \vdash \varphiまたは$ \mathbf{P}_+ \vdash \lnot\varphi
計算可能$ \Delta_1