ロッサーのからくり

素数のまばらさに関する定理については「ロッサーの定理」をご覧ください。

数理論理学において、ロッサーのからくり (英: Rosser's trick) とは考慮中の理論のω無矛盾性を仮定することなしにゲーデルの不完全性定理を証明する手法である (Smorynski 1977, p. 840; Mendelson 1977, p. 160)。この手法はゲーデルが1931年に出版した元の不完全性定理の証明を改善するものとして、1936年にジョン・バークリー・ロッサーによって導入された。

ゲーデルによる元の証明は (非形式的に言えば)「この文は証明できない」と主張する文を使うが、ロッサーのからくりは「この文が証明可能ならば、この文の否定のより短い証明が存在する」と主張する論理式を使う。

背景

ロッサーのからくりはゲーデルの不完全性定理と同様の仮定から始まる。実効的、無矛盾、かつ初頭算術の十分な断片を含む理論${\displaystyle T}$ を選ぶ。

ゲーデルの証明は、任意のそのような理論に対してある論理式${\displaystyle \operatorname {Proof} _{T}(x,y)}$ が存在し、その意図された意味は${\displaystyle y}$ はある論理式の自然数のコード (ゲーデル数) であり、${\displaystyle x}$ は${\displaystyle T}$ の公理から${\displaystyle y}$ によってコード化された論理式の証明へのゲーデル数であることを示す (以降本記事では、数${\displaystyle y}$ と${\displaystyle y}$ によってコード化された論理式を区別せず、論理式${\displaystyle \phi }$ のコードである数を${\displaystyle \#\phi }$ で表す)。加えて、論理式${\displaystyle \operatorname {Pvbl} _{T}(y)}$ を${\displaystyle \exists x\operatorname {Proof} _{T}(x,y)}$ と定義する。これは${\displaystyle T}$ から証明可能な論理式の集合を定義することを意図している。

${\displaystyle T}$ に課した仮定から、${\displaystyle y}$ が論理式${\displaystyle \phi }$ のコードならば、${\displaystyle {\text{neg}}(y)}$ は論理式${\displaystyle \neg \phi }$ のコードであるという性質を持つ論理否定関数${\displaystyle {\text{neg}}(y)}$ を定義できることも示せる。論理否定関数はどんな値であっても入力に取ることができる。入力が論理式のコードであるとは限らない。

理論${\displaystyle T}$ のゲーデル文${\displaystyle \phi }$  (${\displaystyle G_{T}}$ と表すこともある)は、${\displaystyle T}$ が${\displaystyle \phi }$  ↔${\displaystyle \neg \operatorname {Pvbl} _{T}(\#\phi )}$ を証明できるような論理式である。ゲーデルの証明が示したことは以下の通りである。${\displaystyle T}$ が無矛盾ならば、${\displaystyle T}$ は自分自身のゲーデル文を証明できない。しかしゲーデル文の否定も証明できないことを示すためには、理論が単なる無矛盾ではなくω無矛盾であるという、より強い仮定を追加する必要がある。たとえば、理論${\displaystyle T={\text{PA}}+\neg {\text{G}}_{PA}}$  (ここでPAはペアノ算術) は${\displaystyle \neg G_{T}}$ を証明する。ロッサー (1936) はゲーデルの証明に使われたゲーデル文を置き換えることができる異なる自己言及文を構築し、ω無矛盾性の仮定を取り除いた。

ロッサー文

ある固定された算術の理論${\displaystyle T}$ に対し、${\displaystyle \operatorname {Proof} _{T}(x,y)}$ と${\displaystyle {\text{neg}}(x)}$ をそれぞれ関連付けられた証明述語と論理否定関数であるとする。

変更された証明述語${\displaystyle \operatorname {Proof} _{T}^{R}(x,y)}$ は以下のように定義される:

$${\displaystyle \operatorname {Proof} _{T}^{R}(x,y)\equiv \operatorname {Proof} _{T}(x,y)\land \lnot \exists z\leq x[\operatorname {Proof} _{T}(z,\operatorname {neg} (y))],}$$

 

その意味は以下の通りである。

$${\displaystyle \lnot \operatorname {Proof} _{T}^{R}(x,y)\equiv \operatorname {Proof} _{T}(x,y)\to \exists z\leq x[\operatorname {Proof} _{T}(z,\operatorname {neg} (y))].}$$

 

この変更された証明述語は変更された可証性述語${\displaystyle \operatorname {Pvbl} _{T}^{R}(y)}$ の定義に使う:

$${\displaystyle \operatorname {Pvbl} _{T}^{R}(y)\equiv \exists x\operatorname {Proof} _{T}^{R}(x,y).}$$

 

非形式的にいうと、${\displaystyle \operatorname {Pvbl} _{T}^{R}(y)}$ は以下のような主張である。${\displaystyle y}$ はあるコード化された証明${\displaystyle x}$ によって証明可能であり、${\displaystyle y}$ の否定のより小さなコード化された証明は存在しない。${\displaystyle T}$ が無矛盾であるという仮定のもとでは、各論理式${\displaystyle \phi }$ ごとに、論理式${\displaystyle \operatorname {Pvbl} _{T}^{R}(\#\phi )}$ が成り立つことと${\displaystyle \operatorname {Pvbl} _{T}(\#\phi )}$ が成り立つことは同値である。なぜならば、もし${\displaystyle \phi }$ の証明のコードが存在するならば、(${\displaystyle T}$ の無矛盾性の仮定に従い) ${\displaystyle \neg \phi }$ の証明のコードは存在しないからである。しかしながら、${\displaystyle \operatorname {Pvbl} _{T}(\#\phi )}$ と${\displaystyle \operatorname {Pvbl} _{T}^{R}(\#\phi )}$ は${\displaystyle T}$ における証明可能性の観点からは異なる性質を持つ。

${\displaystyle T}$ が十分な算術を含むなら、すべての論理式${\displaystyle \phi }$ に対し、${\displaystyle \operatorname {Pvbl} _{T}^{R}(\phi )}$ は${\displaystyle \neg \operatorname {Pvbl} _{T}^{R}({\text{neg}}(\phi ))}$ を含意することを証明可能であることが、定義から直ちに従う。なぜならば、もしそうでなければ、2つの数${\displaystyle n,m}$ が存在し、それぞれ${\displaystyle \phi }$ と${\displaystyle \neg \phi }$ の証明のコードであり、${\displaystyle n<m}$ と${\displaystyle m<n}$ の両方を満たすからである (実は${\displaystyle T}$ に必要なのはそのような状況がいかなる2数に対しても起き得ないことの証明と、いくばくかの一階述語論理のみである)。

(対角化補題)（英語版）を使って、${\displaystyle \rho }$ を${\displaystyle T}$ が${\displaystyle \rho }$  ↔${\displaystyle \neg \operatorname {Pvbl} _{T}^{R}(\#\rho )}$ を証明可能であるような論理式であるとする。論理式${\displaystyle \rho }$ は理論${\displaystyle T}$ .のロッサー文である。

ロッサーの定理

${\displaystyle T}$ を実効的で十分な算術を含む無矛盾な理論、そのロッサー文を${\displaystyle \rho }$ とする。すると以下が成り立つ (Mendelson 1977, p. 160):

1. ${\displaystyle T}$ は${\displaystyle \rho }$ を証明しない
2. ${\displaystyle T}$ は${\displaystyle \neg \rho }$ を証明しない

これを証明するために、まずある論理式${\displaystyle y}$ およびある数${\displaystyle e}$ について、${\displaystyle \operatorname {Proof} _{T}^{R}(e,y)}$ が成り立つならば、${\displaystyle T}$ は${\displaystyle \operatorname {Proof} _{T}^{R}(e,y)}$ を証明することを示す。これはゲーデルが第一不完全性定理の証明で行ったことと似たやり方で示される: ${\displaystyle T}$ は2つの具体的な自然数の関係である${\displaystyle \operatorname {Proof} _{T}(e,y)}$ を証明する。それから${\displaystyle e}$ より小さなすべての自然数${\displaystyle z}$ 1つ1つにわたり、それぞれの${\displaystyle z}$ について、${\displaystyle T}$ はやはり具体的な2つの自然数の関係である${\displaystyle \neg \operatorname {Proof} _{T}(z,{\text{(neg}}(y)))}$ を証明する。

${\displaystyle T}$ がその場合に${\displaystyle \operatorname {Pvbl} _{T}^{R}(y)}$ を証明できることは、${\displaystyle T}$ が十分な算術 (実際には、必要なのは基本的な一階述語論理である) を含むという仮定が保証する。

加えて、${\displaystyle T}$ が無矛盾で${\displaystyle \phi }$ を証明するならば、${\displaystyle T}$ におけるその証明のコードである数${\displaystyle e}$ が存在し、${\displaystyle T}$ における${\displaystyle \phi }$ の否定の証明のコードである数は存在しない。したがって${\displaystyle \operatorname {Proof} _{T}^{R}(e,y)}$ が成り立ち、よって${\displaystyle T}$ は${\displaystyle \operatorname {Pvbl} _{T}^{R}(\#\phi )}$ を証明する。

(1)の証明はゲーデルによる第一不完全性定理の証明と似ている: ${\displaystyle T}$ が${\displaystyle \rho }$ を証明すると仮定する; すると上記により、${\displaystyle T}$ が${\displaystyle \operatorname {Pvbl} _{T}^{R}(\#\rho )}$ を証明することが従う。よって${\displaystyle T}$ は${\displaystyle \neg \rho }$ も証明する。しかし${\displaystyle T}$ は${\displaystyle \rho }$ を証明すると仮定したから、これは${\displaystyle T}$ が無矛盾ならばありえない。${\displaystyle T}$ は${\displaystyle \rho }$ を証明しないと結論せざるをえない。

(2)の証明も特定の形の${\displaystyle \operatorname {Proof} _{T}^{R}}$ を使う。${\displaystyle T}$ が${\displaystyle \neg \rho }$ を証明すると仮定する; すると上記により、${\displaystyle T}$ が${\displaystyle \operatorname {Pvbl} _{T}^{R}({\text{neg}}\#(\rho ))}$ を証明することが従う。しかし前節で説明されたロッサーの可証性述語の定義から直ちにわかるように、${\displaystyle T}$ は${\displaystyle \neg \operatorname {Pvbl} _{T}^{R}(\#\rho )}$ を証明することが従う。よって${\displaystyle T}$ は${\displaystyle \rho }$ も証明する。しかし${\displaystyle T}$ は${\displaystyle \neg \rho }$ を証明すると仮定したから、これは${\displaystyle T}$ が無矛盾ならばありえない。${\displaystyle T}$ は${\displaystyle \neg \rho }$ を証明しないと結論せざるをえない。

出典

• Mendelson (1977), Introduction to Mathematical Logic（英語）
• Smorynski (1977), "The incompleteness theorems", in Handbook of Mathematical Logic, Jon Barwise, Ed., North Holland, 1982, ISBN (0-444-86388-5)（英語）
• Barkley Rosser (September 1936). “Extensions of some theorems of Gödel and Church”. Journal of Symbolic Logic 1 (3): 87–91. doi:10.2307/2269028. JSTOR 2269028. https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/extensions-of-some-theorems-of-godel-and-church/0461E34DC1F219C459EE84CC2FA89068. （英語）

外部リンク

• Avigad (2007), "Computability and Incompleteness", lecture notes.（英語）