独立命題とはなにか
数理論理学に於いて公理系$T$の独立命題 (independent statement) あるいは決定不能命題 (undecidable statement) は以下のような命題$\varphi$である。
$\varphi$を$T$に於いて証明することはできず、また$\varphi$でないこと、すなわち$\lnot\varphi$も$T$に於いて証明することができない。
独立命題は数理論理学の中心的な話題の一つである。独立命題の具体例として以下のようなものが挙げられるだろう。
- 群の公理$\mathsf{Grp}$に於ける可換性$(\forall x)(\forall y)[xy=yx]$。
- Peano算術$\mathsf{PA}$に於けるGoodsteinの定理。
- Zermelo–Fraenkelの集合論$+$選択公理$\mathsf{ZFC}$に於ける連続体仮説$\mathsf{CH}$。
- Zermelo–Fraenkelの集合論$+$選択公理$\mathsf{ZFC}$に於けるGrothendieck宇宙の存在。
この記事では上の表現が間違っていると断定できる訳ではないが、誤解を生みやすい表現である、ということを解説する。
メタの公理系とは
さて上では独立命題の例を挙げたのだが、「命題$\varphi$は$T$に於いて独立である」ということがどの公理系で証明されているかが問題となる。よって今から「命題$\varphi$は$T$に於いて独立である」かどうかを考えるメタの公理系を$MT$と置こう。
メタの公理系が何であるか、ということはとても重要になる。例えば$MT$が$0=1$、すなわち矛盾とすれば任意の命題が証明可能になってしまう。よって$MT$に於いて、任意の公理系$T$と論理式$\varphi$に対して「$\varphi$は$T$に於ける独立命題である」ということが言えてしまうのである。よって基本的に$MT$は無矛盾だと信じる理論を使うことが多い。また特に$MT$を言及しない場合$\mathsf{ZFC}$のこととすることが多い。
独立性証明
独立性の証明には完全性定理 (completeness theorem) が用いられることが多い。以下にステートメントを述べよう。
任意の公理系$T$に対して以下の命題は同値である。
- $T$は無矛盾である。
- $T$はモデルを持つ。
ここで公理系$T$のモデル (model) は$T$の公理を全て満たす構造のことである。例えば群の公理$\mathsf{Grp}$のモデルとは、すなわち群のことである。
この完全性定理にて重要な点は無矛盾性というフレーズが出てくることである。実は独立性は無矛盾性のことばを用いて表現することができる。
任意の公理系$T$、任意の論理式$\varphi$に対して以下は同値である。
- $T$で$\varphi$を証明することができない。
- $T+\lnot\varphi$は無矛盾である。
この事実から特に以下も同値になる。
- $T$に於いて$\varphi$は独立である。
- $T+\varphi$と$T+\lnot\varphi$は無矛盾である。
以上に挙げた命題から$T$に於いて$\varphi$が独立であることを示すためには以下を示せば良いことが分かるであろう。
$T+\varphi$と$T+\lnot\varphi$、どちらのモデルも存在する。
これを使うことで最初に挙げた例の1.を示すことができる。
群の公理系$\mathsf{Grp}$に於いて$(\forall x)(\forall y)[xy=yx]$は独立である。
$\mathsf{Grp}+(\forall x)(\forall y)[xy=yx]$のモデルの存在を示す。整数$\mathbb{Z}$は加法に対して可換であり、また群となる為良い。
$\mathsf{Grp}+\lnot(\forall x)(\forall y)[xy=yx]$のモデルの存在を示す。対称群$S_3$がそのようなモデルになっている。今$(1,2),(2,3)\in S_3$に対して$(1,3,2)=(1,2)(2,3)\neq(2,3)(1,2)=(1,2,3)$となり非可換となる。
ここで重要なこととしてメタの公理系$\mathsf{ZFC}$に於いて$\mathsf{Grp}$のモデルの存在が示せる、ということである。
第二不完全性定理と「暗黙の無矛盾性」
さて次に3.の例「$\mathsf{ZFC}$に於いて連続体仮説$\mathsf{CH}$が独立」も1.の例と同様にモデルを取って示そうとすると以下の第二不完全性定理 (second incompleteness theorem) が問題になる。
公理系$T$が十分に強い算術 (例えば初等再帰算術$\mathsf{EA}$) などを含み、かつ計算可能であり無矛盾であるとする。このとき$MT$に於いて、$T$の無矛盾性を表現する論理式$\mathsf{Con}(T)$を証明することはできない。
仮定に技術的な単語が何個か含まれるが、$MT$を$\mathsf{ZFC}$としたとき$MT$が無矛盾なら、Gödelの第二不完全性定理(この第二不完全性定理はメタの更にメタの公理系で示されていることに注意)の仮定を満たす。よって$\mathsf{ZFC}$の無矛盾性を示せず、完全性定理から$\mathsf{ZFC}$のモデルの存在すら分からない、という問題が発生する。より強く、メタの公理系である$\mathsf{ZFC}$で「$\mathsf{ZFC}$に於いて連続体仮説が独立である」ことが示せるならば、メタの公理系が矛盾することが分かってしまうのである。
よって「$\mathsf{ZFC}$に於いて連続体仮説$\mathsf{CH}$が独立」というのは$\mathsf{ZFC}$の定理には成り得ない。これはどういうことであろうか？実は集合論などで「$\mathsf{ZFC}$に於いて連続体仮説$\mathsf{CH}$が独立」と主張するとき暗黙の内に$\mathsf{ZFC}$の無矛盾性を仮定しているのである。すなわち、「$\mathsf{ZFC}$に於いて連続体仮説$\mathsf{CH}$が独立」という主張を正確に表すと「$\mathsf{ZFC}$が無矛盾であるならば$\mathsf{ZFC}$に於いて連続体仮説$\mathsf{CH}$が独立」となる。
もっと複雑な例として4.の例「$\mathsf{ZFC}$に於いてGrothendieck宇宙の存在が独立」を考えよう。メタの公理系を$\mathsf{ZFC}$とすると、上と同様に「暗黙の無矛盾性」を仮定する必要があることは分かるであろう。すなわち「$\mathsf{ZFC}$が無矛盾であるならば$\mathsf{ZFC}$に於いてGrothendieck宇宙の存在が独立」がメタの$\mathsf{ZFC}$で示せるであろうか。
残念ながらこれは成り立たない。まず「$\mathsf{ZFC}$が無矛盾であるならば$\mathsf{ZFC}$に於いてGrothendieck宇宙の存在が独立」は以下の二つの命題が成立つこととして分解できる。
- $\mathsf{ZFC}$が無矛盾なら$\mathsf{ZFC}+\lnot\mathsf{UA}$のモデルが存在する。
- $\mathsf{ZFC}$が無矛盾なら$\mathsf{ZFC}+\mathsf{UA}$のモデルが存在する。
ここで$\mathsf{UA}$を「Grothendieck宇宙が存在する」という命題とする。
まず1.はしっかり成り立つことが分かる。$\mathsf{ZFC}$の無矛盾性の仮定から$\mathsf{ZFC}$のモデル$\mathcal{M}$の存在が言えて、$\mathcal{M}$が$\mathsf{UA}$のモデルなら、最小のGrothendieck宇宙$U$を取ることができ、$\mathcal{M}$の中で$U$に含まれるもの全体が$\mathsf{ZFC}+\lnot\mathsf{UA}$のモデルになっているからであり、$\mathsf{ZFC}+\lnot\mathsf{UA}$のモデルになっているならば、そのままで良い。
問題は2.である。まずGrothendieck宇宙が$\mathsf{ZFC}$のモデルになることから、メタの公理系$\mathsf{ZFC}$に於いて「$\mathsf{ZFC}+\mathsf{UA}$が無矛盾なら$\mathsf{ZFC}+\mathsf{Con}(\mathsf{ZFC})$も無矛盾」であることが示せる。
次にメタの公理系$\mathsf{ZFC}$に於いて「$\mathsf{ZFC}$が無矛盾なら$\mathsf{ZFC}+\mathsf{UA}$のモデルが存在する」ことはメタの公理系$\mathsf{ZFC}+\mathsf{Con}(\mathsf{ZFC})$に於いて「$\mathsf{ZFC}+\mathsf{UA}$のモデルが存在する」ことと同値である。
よってメタの公理系$\mathsf{ZFC}$に於いて「$\mathsf{ZFC}$が無矛盾なら$\mathsf{ZFC}+\mathsf{UA}$のモデルが存在する」ならばメタの公理系$\mathsf{ZFC}+\mathsf{Con}(\mathsf{ZFC})$に於いて「$\mathsf{ZFC}+\mathsf{Con}(\mathsf{ZFC})$は無矛盾である」ということが成り立ち、第二不完全性定理に矛盾してしまう。
結論として「$\mathsf{ZFC}$が無矛盾であるならば$\mathsf{ZFC}$に於いてGrothendieck宇宙の存在が独立」はメタの公理系$\mathsf{ZFC}$では示すことができないのである。一方、問題となっていたのは2.の部分であるので「$\mathsf{ZFC}+\mathsf{UA}$が無矛盾であるならば$\mathsf{ZFC}$に於いてGrothendieck宇宙の存在が独立」ことはメタの公理系$\mathsf{ZFC}$で成り立つ。
結語
最初に挙げた例を正確に書くと以下のようになる。
- メタの公理系$\mathsf{ZFC}$にて「群の公理$\mathsf{Grp}$にて可換性$(\forall x)(\forall y)[xy=yx]$は独立である」ことが示せる。
- メタの公理系$\mathsf{ZFC}$にて「Peano算術$\mathsf{PA}$にてGoodsteinの定理は独立である」ことが示せる。
- メタの公理系$\mathsf{ZFC}$にて「$\mathsf{ZFC}$が無矛盾であるならば$\mathsf{ZFC}$にて連続体仮説$\mathsf{CH}$は独立である」ことが示せる。
- メタの公理系$\mathsf{ZFC}$にて「$\mathsf{ZFC}+\mathsf{UA}$が無矛盾であるならば$\mathsf{ZFC}$にてGrothendieck宇宙が存在すること$\mathsf{UA}$は独立である」ことが示せる。
このように独立性などに言及する場合は言及されていなくてもメタ理論がなのことであるかしっかり確認することが必要である。場合によっては独立性を表す文のそのものが独立になってします場合もある。もっと言えば数理論理学に於いて、「その定理はどの公理系で証明されているか」ということを確認することは非常に重要である。
以下は余談であるが、上ではモデルを用いた独立性証明を紹介したが、モデルを用いない、証明を直接扱うような証明も考えられる。例えば2.などの例はそういう手法で最初証明された。また連続体仮説の独立性の証明はアイデアとしては上のモデルの存在を用いるものと同じであるが、もっと技術的に複雑になってくる。その点をこの記事では曖昧にあつかったが容赦して頂きたい。
参考文献
- T. Arai, Ordinal Analysis with an Introduction to Proof Theory, Springer, 2020.
- K. Kunen, Set Theory: An Introduction to Independence Proofs, North Holland, 1983. 邦訳: 藤⽥博司. 集合論‒独⽴性証明への案内, ⽇本評論社, 2008.
- 新井敏康. 数学基礎論, 岩波書店, 2011.
- y., 独立命題かどうかが独立な命題について (pdf注意) 2019. (最終閲覧⽇: 2020年12⽉21⽇).
