[발췌] 황제의 새 마음 / 2024-05-28 / P는 재귀함수다. 하지만 P는 재귀 집합이 아니다. 이것에 괴델 정리다.

 

 

 

p.196

1. 현대 수리철학의 세 가지 주류로써 형식주의, 직관주의, 플라톤주의를 살펴보았다. 플라톤주의에서 수학적 진리를 절대적이고, 외향적이며, 영원하고, 인간이  만든 척도에 좌우되지 않는다. 
2. 어떤 증명이 과연 진정한 증명인지 아닌지를 완전히 기계적이고 미리 결정된 방식으로 검증할 수 있어야만, 즉 증명을 검증할 알고리즘이 있어야만 한다는 것이다. 
3. P와 같이 특정한 알고리즘에 의하여 생성될 수 있는 집합을 재귀적 열거 기능 집합 recursive enumerable set이라 부른다.

4. 집합 중에 그 자신과 여집합을 모두 재귀적으로 열거할 수 있는 집합을 재귀 함수 recursive set이라 부른다. 물론 재귀 집합의 여집합도 재귀 집합이다.
5. 우리가 선정한 형식 체계가 완전하기 않음을 보여준다. 즉, 체계 내에서도 입증도 반증도 할 수 없는 명제가 존재한다는 것이다. 
6. 재귀적으로 열거 가능하다는 사실을 이미 알고 있기 때문에 P는 재귀 함수가 된다. 그러나 P는 재귀 집합이 아니다. 이것이 괴델 정리의 주제인 것이다.