Definition. Gödel encoding [math-030A]

2023-08-30 · Lîm Tsú-thuàn

哥德爾數（Gödel number）是一種編碼方式，在一個算術系統裡面，當我們把每個字符都排成一個有限的列，我們可以幫每個字符都指定一個自然數。具體來說，我們可能會寫下

  1. ¬\neg 是 11，其後設意義為「否定」
  2. ∨\lor 是 22，其後設意義為「或」
  3. ∧\land 是 33，其後設意義為「且」

當有符號 si(i∈N)s_i (i \in \N)，其對應的哥德爾數為 nin_i。我們並不是真的關心具體的每個符號，我們做這件事的理由是為了表示哥德爾編碼。所以這裡要開始定義哥德爾編碼，首先先看一個簡單的例子：當有系統的公式符號排列 s1s10s4s_1 s_{10} s_4，我們說公式的哥德爾編碼為 2n1⋅3n10⋅5n42^{n_1}\cdot 3^{n_{10}}\cdot 5^{n_4}。

因此用函數 α(i)\alpha(i) 指示一個公式的每個位置 ii 符號的 Gödel number，則哥德爾編碼確切的定義是

∏i∈Ipinα(i)\prod_{i \in I}p_i^{n_{\alpha(i)}}

，也就是將質數以每個符號對應的哥德爾數為指數，將它們全部乘起來。這個辦法只是為了迫使每個公式有對應的編碼存在。我們用 G‾\overline{G} 記號表示公式 GG 的哥德爾數。

α\alpha 函數給出第 ii 個出現符號的在表中的位置。