괴델 넘버링

Kurt Goedel이 불완전성정리를 증명하기 위해서 도입한 개념.

구체적으로, 괴델 넘버링 \phi는 수식과 같은 수학적 객체와 자연수의 부분집합 사이에 정의된 임의의 일대일 관계로 그 변환과 역변환 과정이 모두 함수로 정의되어야 한다. 꼭 그래야 하는 건 아니지만 변환 및 역변환 함수가 원시재귀함수인 편이 좀 더 다양한 활용이 가능할 듯.

괴델 자신은 소인수분해의 유일성을 이용해서 2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots 같은 식으로 함수를 구축했다고 한다.