검색결과 리스트
괴델에 해당되는 글 1건
- 2009/04/28 괴델의 불완전성 정리
글
'골드바흐와 페르마의 문제'는 각각 '골드바흐의 추측'과 '페르마의 마지막 정리'를 가리킨다. 골드바흐는 "2보다 큰 모든 짝수는 두 소수의 합으로 표현된다."고 추측했다. 페르마의 마지막 정리는 "n이 3이상의 자연수일 때, x^n + y^n = z^n을 만족시키는 x,y,z의 정수해는 존재하지 않는다."이다. 페르마의 마지막 정리는 1991년 프린스턴대학교의 앤드루 와일즈에 의해 증명되었다. 무려 150쪽에 걸쳐.. 하지만 골드바흐의 추측은 아직 증명되지 않았다. 괴델은 참인지는 알 수 있지만 형식체계 안에서는 증명불능인 명제의 한 예를 직접 만들어 냄으로써 유명한 불완전성 정리의 증명을 완성했다.
제1불완전성정리 : 전반적 전략
"이 문장은 거짓이다."
이 문장은 오직 그것이 거짓일 때만 참이며, 논리적으로 볼 때 이는 좋지 않은 상황이다. 괴델의 전략은 이 역설적 문장과 비슷한 명제를 생각하는 데에서 출발한다.
"이 문장은 이 체계 안에서는 증명불능이다." 이 문장을 G라고 부르자.
"G는 이 체계 안에서 증명할 수 없다."
"G의 부정"은 다음과 같다.
"G는 이 체계 안에서 증명할 수 있다."
만일 G를 증명할 수 있다면 G의 부정은 참이다. 그런데 만일 어떤 명제의 부정이 참이라면 명제 자체는 거짓이므로, 이 관점에서 볼 때 G를 증명할 수 있다면 G는 거짓이다.
그러나 G를 증명할 수 있다면 이는 곧 G가 참이란 뜻이다. 이 체계가 무모순이라고 가정할 때(모순이라면 무엇이든 증명할 수 있으므로) 이 증명은 이밖에 다른 것을 보여 줄 수는 없다. 따라서 이 체계가 무모순이라는 가정 아래에서는, G를 증명할 수 있다면 이것은 참이면서 거짓이라는 모순이 나오며, 이런 뜻에서 G는 증명할 수 없다.
다시 말해서 이 체계가 무모순이면 G는 그 안에서 증명할 수 없다. 그리고 이것은 바로 G의 내용 자체이므로 G는 참이다. 그러므로 G는 참이면서 증명불능이며,
이것이 곧 유명한 괴델의 결론, 다시 말해서 만일 어떤 계가 무모순이면 그 안에서 표현이 가능한 참이면서 증명불능인 명제가 존재한다는 것이 불완전성정리이다.
