0664考える名無しさん
2018/08/23(木) 20:07:08.170モイジェシュ・プレスバーガーにより1929年に導入された。 プレスバーガー算術の
シグネチャには加法と等号のみが含まれ乗法は省かれる。 公理には数学的帰納法の
公理型を含む。
プレスバーガー算術は加法と乗法両方含むペアノ算術より弱い体系である。
ペアノ算術とは異なりプレスバーガー算術は決定可能である。
これはプレスバーガー算術の言語で書かれた任意の閉論理式が
プレスバーガー算術の公理で証明可能かどうかを判定するアルゴリズムが存在する
ことを意味する。 この決定問題の計算複雑性は漸近的に二重指数関数であることが
Fischer & Rabin (1974)で示されている。