不完全性定理、その最短の証明 - Qiita

スマリヤン先生の『ゲーデルの不完全性定理』という本に、第一不完全性定理の証明とタルスキの真理述語の定義不可能性定理が極めて一般的かつ明瞭かつ簡潔に説明されていて感動したのでメモを残します。 natの世界とUの世界: nat型である自然数の世界と、U型である記号列の世界があり、U→natな全単射な写像$g$が存在することを要請します1。記号列の世界に $\mathcal S$ と呼ばれる集合、および$\mathcal P, \mathcal T$という2つの$\mathcal S$の部分集合の存在を要請します。$\mathcal S$の要素を文、$\mathcal P$の要素を証明可能な文、$\mathcal T$の要素を真な文と呼称します。健全性のため$\mathcal P$が $\mathcal T$の部分集合であることを要請します。なお、$g$で作られた数をゲーデル数と呼称します。 述