16/06/10 23:03:29.17 SzOTDmNl.net
>>479
"数学的帰納法は、公理だったんだ。"を補強しておこう
ロビンソン算術
URLﾘﾝｸ(ja.wikipedia.org)
(抜粋)
数理論理学においてロビンソン算術(英: Robinson arithmetic)あるいはQとはペアノ算術(PA)の有限部分理論であり、Robinson (1950)において最初に導入された。
Qは本質的にはPAから帰納法の公理図式を取り除いたものである。それゆえQはPAよりも弱いが同一の言語を持つ不完全な理論である。Qは重要かつ興味深い対象である。
というのもQは本質的決定不能かつ有限公理化可能なPAの部分理論だからである。
Qの特徴は帰納法の公理図式の不在にある。すなわちQはしばしば個々の具体的な自然数に対する事実を証明することが可能であるが、任意の自然数に対する普遍的な事実の多くを証明できない。
例えば 5 + 7 = 7 + 5 はQで証明可能だが、一般的な言明 x + y = y + x は証明できない。同様に Sx ≠ x は証明できない(Burgess (2005))。