不完全性定理
メモ
数理論理学において不完全性定理と呼ばれるものは，実際には次の形で述べられる2つの現象のことを表していると言ってもそんなに誤りでもない． #不完全性定理は現象か？
適当な条件を満たす理論が無矛盾のとき，〇〇は出来ない．
なお，ここでの理論とは命題の有限 / 可算無限の集合である．
特に可算無限の場合，以下に述べられる適切な条件には可算無限がどの程度まで許されるか？というのが重要であり，大体の場合，再帰的可算集合（または計算可能集合）であることが要請される．
技術的には，不完全性定理は再帰的理論上で証明されるが，Craigのトリックと呼ばれる方法によって再帰的可算理論は再帰的理論（更に原始再帰的理論にも）に帰着させることができる．
重要な注意
この「適切な条件」をどう設定するかによって，似たような結論について様々な形で述べ直すことができるため，一口に第1/第2不完全性定理と言ってもこれだというものが無い．
第1不完全性定理 / Gödelの第1不完全性定理もしくはGödel-Rosserの第1不完全性定理
適当な条件を満たす無矛盾（もしくはΣ₁健全 / ω無矛盾）な理論は，理論の完全性を持てない．（すなわち不完全である）．
ここで，理論の完全性とは，任意の文$ \sigmaについて$ T \vdash \sigmaまたは$ T \vdash \lnot \sigmaであることを指す．
より端的に次の形で述べることもある．
理論が無矛盾なら，Gödel文$ Gと呼ばれる文が存在し，その文は証明も反証もできない．
第2不完全性定理 / Gödelの第2不完全性定理
適当な条件を満たすΣ₁健全な理論は，自己の無矛盾性を表す文を証明も反証も出来ない．
ここで，Σ₁健全性は無矛盾性より強い条件ということに注意せよ．
実際には，Σ₁健全性は非反証性について述べるときに必要であって，非可証性について述べる時は無矛盾性でもよい．
この定理の証明には，全てのGödel文は自己の無矛盾性を表す文と同値という補題を証明し，第1定理より直ちに得るのが常套手段である．（と思う）
メモ: 不完全性定理と真偽
不完全性定理を真偽，すなわち意味論に触れている形で述べることもある．すなわち
真なのに証明が出来ない文が存在する：$ \mathfrak{M} \models \sigmaかつ$ T \nvdash \sigma
これについは前原昭二の注意なども参照．
この形で述べられる定理として，
Chaitinの不完全性定理
詳しくはページ参照．
$ aのKolmogorov複雑度が$ L以上ということを指す命題$ L \leq K(a)について，$ L \leq K(a)は正しいにもかかわらずその事実が証明できなくなるような下界$ Lが存在する．
すなわち，適切な設定/形式化のもとで，
「任意の$ aについて$ \mathfrak{M} \vDash L \leq K(a)だが$ T \nvdash L \leq K(a)」となる$ Lが存在する．