ゲーデル数

$\mathcal{L}_A$ の各記号 $s$ に相異なる正の整数 $c(s)$ を割り当てる。記号列 $s_1s_2\cdots s_k$ に対し

（$p_i$ は $i$ 番目の素数）と定め、これをゲーデル数という。論理式の有限列（証明）に対しても、各項のゲーデル数を同じ方法で束ねて符号を与える。素因数分解の一意性により $\#$ は単射であり、$\#\varphi$ から $\varphi$ を機械的に復元できる。数項 $\overline{\#\varphi}$ を $\varphi$ の名前と呼ぶ。