読者です 読者をやめる 読者になる 読者になる

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

ゲーデルの対角化定理の厳密な証明を対角線論法と対比する

前原昭二「数学基礎論入門」「8.5ゲーデルの対角化定理-定理8.3」の証明を対角線論法との対比を明確にしようとがんばった結果。

(1) <記号の定義>
 *n* :自然数nに対応する対象式(論理記号としてのn)
 『A』 :論理式Aのゲーデル数に対応する対象式(論理記号)
 An(ξ) :ξを自由変数に含むゲーデル数がnの論理式

(2) 写像
  Φ:n |--> F(『An(*n*)』)
は意味論的にnの関数。ただし右項は対象式(論理記号)としての*n*以外に実際の自然数nが入っているので論理式では無い。
※ An(*n*)は対角線論法と対比させた時の対角要素からなる一変数関数に相当。

(3) この右項をnの数値別に表現する論理式G(ξ)が存在すると仮定する。つまり、
  ∀n∈Dom(Φ);|-F(『An(*n*)』)←→G(*n*) −−− <1>

(4) ここで特にnとしてG(ξ)のゲーデル数を選択すると、 G(ξ)はAn(ξ)と一致する。従って、G(*n*)はAn(*n*)と一致する。よって、<1>より、
  |-F(『An(*n*)』)←→An(*n*)

結局、対角化定理の厳密な証明は、<1> の証明に帰着することになる。