ロッサーのからくり

数理論理学において、ロッサーのからくり () とは考慮中の理論のω無矛盾性を仮定することなしにゲーデルの不完全性定理を証明する手法である (Smorynski 1977, p. 840; Mendelson 1977, p. 160)。この手法はゲーデルが1931年に出版した元の不完全性定理の証明を改善するものとして、1936年にジョン・バークリー・ロッサーによって導入された。
ゲーデルによる元の証明は (非形式的に言えば)「この文は証明できない」と主張する文を使うが、ロッサーのからくりは「この文が証明可能ならば、この文の否定のより短い証明が存在する」と主張する論理式を使う。
背景.
ロッサーのからくりはゲーデルの不完全性定理と同様の仮定から始まる。実効的、無矛盾、かつ初頭算術の十分な断片を含む理論formula_1を選ぶ。
ゲーデルの証明は、任意のそのような理論に対してある論理式formula_2が存在し、その意図された意味はformula_3はある論理式の自然数のコード (ゲーデル数) であり、formula_4はformula_1の公理からformula_3によってコード化された論理式の証明へのゲーデル数であることを示す (以降本記事では、数formula_3とformula_3によってコード化された論理式を区別せず、論理式formula_9のコードである数をformula_10で表す)。加えて、論理式formula_11をformula_12と定義する。これはformula_1から証明可能な論理式の集合を定義することを意図している。
formula_1に課した仮定から、formula_3が論理式formula_9のコードならば、formula_17は論理式formula_18のコードであるという性質を持つ論理否定関数formula_17を定義できることも示せる。論理否定関数はどんな値であっても入力に取ることができる。入力が論理式のコードであるとは限らない。
理論formula_1のゲーデル文formula_9 (formula_22と表すこともある)は、formula_1がformula_9 ↔formula_25を証明できるような論理式である。ゲーデルの証明が示したことは以下の通りである。formula_1が無矛盾ならば、formula_1は自分自身のゲーデル文を証明できない。しかしゲーデル文の否定も証明できないことを示すためには、理論が単なる無矛盾ではなくω無矛盾であるという、より強い仮定を追加する必要がある。たとえば、理論formula_28 (ここでPAはペアノ算術) はformula_29を証明する。ロッサー (1936) はゲーデルの証明に使われたゲーデル文を置き換えることができる異なる自己言及文を構築し、ω無矛盾性の仮定を取り除いた。
ロッサー文.
ある固定された算術の理論formula_1に対し、formula_2とformula_32をそれぞれ関連付けられた証明述語と論理否定関数であるとする。
変更された証明述語formula_33は以下のように定義される:
formula_34
その意味は以下の通りである。
formula_35
この変更された証明述語は変更された可証性述語formula_36の定義に使う:
formula_37
非形式的にいうと、formula_36は以下のような主張である。formula_3はあるコード化された証明formula_4によって証明可能であり、formula_3の否定のより小さなコード化された証明は存在しない。formula_1が無矛盾であるという仮定のもとでは、各論理式formula_9ごとに、論理式formula_44が成り立つこととformula_45が成り立つことは同値である。なぜならば、もしformula_9の証明のコードが存在するならば、(formula_1の無矛盾性の仮定に従い) formula_18の証明のコードは存在しないからである。しかしながら、formula_45とformula_44はformula_1における証明可能性の観点からは異なる性質を持つ。
formula_1が十分な算術を含むなら、すべての論理式formula_9に対し、formula_54はformula_55を含意することを証明可能であることが、定義から直ちに従う。なぜならば、もしそうでなければ、2つの数formula_56が存在し、それぞれformula_9とformula_18の証明のコードであり、formula_59とformula_60の両方を満たすからである (実はformula_1に必要なのはそのような状況がいかなる2数に対しても起き得ないことの証明と、いくばくかの一階述語論理のみである)。
を使って、formula_62をformula_1がformula_62 ↔formula_65を証明可能であるような論理式であるとする。論理式formula_62は理論のロッサー文である。
ロッサーの定理.
formula_1を実効的で十分な算術を含む無矛盾な理論、そのロッサー文をformula_62とする。すると以下が成り立つ (Mendelson 1977, p. 160):
これを証明するために、まずある論理式formula_3およびある数formula_74について、formula_75が成り立つならば、formula_1はformula_75を証明することを示す。これはゲーデルが第一不完全性定理の証明で行ったことと似たやり方で示される: formula_1は2つの具体的な自然数の関係であるformula_79を証明する。それからformula_74より小さなすべての自然数formula_811つ1つにわたり、それぞれのformula_81について、formula_1はやはり具体的な2つの自然数の関係であるformula_84を証明する。
formula_1がその場合にformula_36を証明できることは、formula_1が十分な算術 (実際には、必要なのは基本的な一階述語論理である) を含むという仮定が保証する。
加えて、formula_1が無矛盾でformula_9を証明するならば、formula_1におけるその証明のコードである数formula_74が存在し、formula_1におけるformula_9の否定の証明のコードである数は存在しない。したがってformula_75が成り立ち、よってformula_1はformula_44を証明する。
(1)の証明はゲーデルによる第一不完全性定理の証明と似ている: formula_1がformula_62を証明すると仮定する; すると上記により、formula_1がformula_100を証明することが従う。よってformula_1はformula_72も証明する。しかしformula_1はformula_62を証明すると仮定したから、これはformula_1が無矛盾ならばありえない。formula_1はformula_62を証明しないと結論せざるをえない。
(2)の証明も特定の形のformula_108を使う。formula_1がformula_72を証明すると仮定する; すると上記により、formula_1がformula_112を証明することが従う。しかし前節で説明されたロッサーの可証性述語の定義から直ちにわかるように、formula_1はformula_114を証明することが従う。よってformula_1はformula_62も証明する。しかしformula_1はformula_72を証明すると仮定したから、これはformula_1が無矛盾ならばありえない。formula_1はformula_72を証明しないと結論せざるをえない。