北田 発見への道 8章

8章 証明の再帰性

本書では、ロッサー文を使った証明でゲーデルの不完全性定理を導いた。その際に前提となっている再帰性/帰納性を議論する。

まず、再帰的関数の定義を行い、これを用いると、再帰的述語および再帰的関係を定義することができる。実際、「普通の」関係ないし述語が再帰的であることが示される。

これまで「有限の立場で」という但し書きで使われるような場面では再帰的であることと同等である、ということかな。