ゲーデル数化は、形式言語におけるすべての記号、数式、証明に固有の自然数(ゲーデル数)を割り当てる基礎的な手法です。この構文の算術化により、形式体系に関するメタ数学的記述(例:「この数式は証明可能である」)を数値に関する算術的記述として符号化することが可能になり、体系内でその記述について推論することができます。

(画像はイメージです)
ゲーデル数化は、形式言語におけるすべての記号、数式、証明に固有の自然数(ゲーデル数)を割り当てる基礎的な手法です。この構文の算術化により、形式体系に関するメタ数学的記述(例:「この数式は証明可能である」)を数値に関する算術的記述として符号化することが可能になり、体系内でその記述について推論することができます。
ゲーデル数化は、構文(形式言語の記号構造)と数論(整数の性質)の間のギャップを埋める独創的な仕組みです。このプロセスにより、論理に関する記述を数値に関する記述に変換することができます。この方法は、まず形式言語の各基本記号に一意の整数を割り当てることによって機能します(例:¬→1、∨→2、∀→3、x→4など)。
これらの記号の並びである数式には、固有の番号を割り当てることができます。ゲーデルの元の方法は素数を使用していました。 因数分解数列 [latex]s_1, s_2, …, s_k[/latex] の場合、公式のゲーデル数は [latex]2^{s_1} cdot 3^{s_2} cdot 5^{s_3} cdot dots cdot p_k^{s_k}[/latex] となります。ここで、[latex]p_k[/latex] は k 番目の素数です。 算術の定理 (一意の素因数分解)このマッピングは単射です。すべての式には一意の番号が割り当てられ、そのような番号から元の式を一意に復元できます。
最後に、証明(一連の式)も同様に、構成要素となる式のゲーデル数を取り、素数べき乗符号化を再度適用することで符号化できる。この完全な算術化により、「数列 F は式 P の有効な証明である」といった複雑なメタ数学的性質は、F と P のゲーデル数を含む純粋に算術的な述語となる。これにより、ゲーデルは自身の証明可能性を参照する式を構築することができ、これは彼の不完全性証明における重要なステップとなった。
ゲーデル数
(日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。)
フルサイズの画像とダウンロードは、登録会員のみが100%無料で利用できます。
> ログイン <