プレスバーガー算術
プレスバーガー算術の言語は0と1、加法と解釈される二項関数+からなる。公理は以下の論理式を全称閉包したものである。
¬(0 = x + 1)
x + 1 = y + 1 → x = y
x + 0 = x
x + (y + 1) = (x + y) + 1
P(x)をプレスバーガー算術の言語による自由変数xを含む一階述語論理式とする。このとき次の論理式は公理である。
(P(0) ∧ ∀x(P(x) → P(x + 1))) → ∀y P(y).
(5) は数学的帰納法の公理型であり、無限個の公理を表している。 (5) は有限の公理で置き換えることができないためプレスバーガー算術は有限公理化不可能である。
プレスバーガー算術は因数分解に関する規則や素数のような概念を形式化できない。 一般的に乗法に関する自然数の概念は不完全性と決定不可能性につながることからプレスバーガー算術では定義することはできない。 しかし、個々の論理式としては形式化可能である。例えば次は証明可能である。"任意のxに対して、あるyが存在し : (y + y = x) ∨ (y + y + 1 = x)" これは、すべての自然数は偶数もしくは奇数のどちらかであることを意味する。