皆の本棚にあるタグ「不完全性定理」の本

不完全性定理
『ゲーデルの不完全性定理』より : ゲーデルの不完全性定理(ゲーデルのふかんぜんせいていり、独: Gödelscher Unvollständigkeitssatz)又は単に不完全性定理とは、数学基礎論における重要な定理の一つで、クルト・ゲーデルが1930年に証明したものである。 第1不完全性定理 自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。 第2不完全性定理 自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない。 ゲーデルの定理でいう証明不能命題Gは、「Gは証明できない」という命題と同値である。Gはゲーデル文と呼ばれる。 Gが証明可能であれば、Σ1完全性により命題「Gは証明できる」もまた証明可能である。一方Gは命題「Gは証明できない」と同値であることが証明可能であるので、両者から矛盾が導かれる。 つまり 「Gが証明できる」ならば「矛盾が証明できる」 ... (A)したがって、対偶を取れば 「矛盾が証明できない」ならば「Gが証明できない」 ... (B)となる。