Tag Archives: Gödel

괴델의 불완전성 증명

이 글은 한국 『SKEPTIC』 8권 140-157쪽에 실린 이광근 교수님 글 「튜링의 1935년 - 앨런 튜링은 정말로 천재인가」의 일부를 발췌하여 수정한 것입니다. 괴델의 불완전성 정리(Gödel's incompleteness theorem)를 직관적으로 표현하면 다음과 같다. “참이지만 기계적인 논리체계로는 증명 불가능한 것이 존재한다. 자연수에 대한 명제들의 세계로 국한되더라도 그런 것이 존재한다.” 괴델이 이것을 어떻게 증명했는지 살펴보자. 불완전성 정리를 증명하기 위해서는 다음 등식을 만족시키는 명제… Read More »

일계논리와 무모순성

Hilbert는 수학의 기초를 확립하는 단계에서 무모순성에 관한 형식적 증명을 찾아냄으로써 수학의 여러 모순을 제거하고자 하였다. 그 증명은 오직 유한 단계의 기계적 절차에 의해 행해질 수 있는 것이어야 했다. Hilbert는 수학적 개체의 존재성과 그 개체의 무모순성은 일치한다고 믿었다. 예컨대 Hilbert의 관점에서 보면 실수 범위에서 제곱하여 \(-1\)이 되는 성질은 자기모순적이므로 그러한 조건을 만족시키는 실수는 존재하지 않는다. Euclid 기하학은 실수 집합의… Read More »

일계논리와 Peano 산술

일계논리 문장의 집합 \(\varSigma\)가 완전하다(complete)는 것은 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha )\) 중 하나가 \(\varSigma\)의 논리적 귀결인 것이다. 완전성 정리에서는 형식계의 완전성을 말하기 때문에 완전성이라는 용어를 조금 다르게 사용한다. 그러나 두 상황에서 완전성이라는 개념은 서로 깊은 연관이 있다. 왜냐하면 \(\varSigma\)가 완전할 때 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha )\)가 \(\varSigma\)로부터 증명될 수 있기… Read More »