김진섭 대표는 5월 30일(목) 제주대학교 경영정보학과 산업·직무 특화 전문가 특강에 참석, 괴델(Kurt Gödel)의 불완전성 정리가 나온 배경을 소개하고 증명의 핵심 아이디어를 수학과 메타수학(meta-mathematics), 괴델수(Gödel number), 그리고 메타수학의 수학화 3가지로 나누어 설명할 예정입니다. 정리한 슬라이드와 강의록을 미리 공유합니다. 초청해주신 현정석 교수님께 감사드립니다.
요약
18/19 세기 미적분학, 해석학의 발전으로, 수학은 점점 기존의 직관과 상식에서 벗어나 추상화되면서 많은 문제점들이 생겼다.
특히 무한의 개념을 엄밀하게 다룰 필요성이 있었는데, 칸토어(Georg Cantor)는 집합론의 논법으로 무한을 엄밀하게 정의하고 그것들의 크기를 비교하였다.
20세기 수학자들은 집합론을 이용, 수학의 기초를 구성하고 모순이 없는 수학체계를 만들 수 있다는 꿈으로 부풀어 있었으나, 러셀의 역설(Bertrand Russel’s paradox)로 대표되는 “자기언급의 역설”은 집합론의 기초를 위태롭게 하였다.
힐베르트(David Hilbert)는 “자기언급의 역설” 은 수학의 명제와 메타수학(meta-mathematics)의 명제를 구분하지 않아 일어나는 것으로 판단하였으며, 이를 잘 구분하는 공리계를 세심하게 설계할 수만 있다면 모순없는 수학체계를 만들 수 있다고 보았다.
그러나 괴델(Kurt Gödel)은 이 부분을 파고들어 메타수학의 명제를 수학의 명제로 바꾸는 괴델수(Gödel number) 라는 독창적인 아이디어를 제안, 메타수학의 명제를 수학 체계로 갖고 온 후 자기언급의 역설을 보여주었다. 즉, “자기언급의 역설” 을 피하기 위해 아무리 세심하게 공리계를 설계해도 그것을 피할 수는 없다는 것을 증명하였으며, 이것이 불완전성 정리이다.
불완전성 정리로 인해 “참이지만 증명불가능한 명제가 존재” 하고 나아가 “수학의 무모순성을 수학 자체적으로는 증명할 수 없음” 이 증명되어 모순없는 완전한 수학체계의 꿈은 결국 산산조각이 난다.
불완전성 정리를 인간 이성의 한계로만 해석하고 실의에 빠지지 말자. 어떤 기계보다도 더 복잡하고 정교한 인간의 정신구조와 능력을 긍정하며 창조적 이성의 힘을 인정할 때이다.
Slide
아래 슬라이드를 보거나 https://jinseob2kim.github.io/LectureGodel/ 를 클릭하면 볼 수 있다.
강의록
본 강의록은 과거 https://jinseob2kim.github.io/godel.html 에 정리했던 내용을 약간만 수정하였습니다.
서론
괴델의 불완전성 정리에 대한 많은 책들이 시중에 출판되어 있다. 허나 대부분이 역사와 증명의 의미에 치중되어 있고 실제 증명의 아이디어를 설명한 책은 거의 없으며, 있다고 하더라도 외국 서적을 번역하면서 난해한 표현이 많이 나와 이해하기가 어렵다. 이에 본 글에서는 불완전성 정리 증명의 핵심적인 아이디어를 크게 수학(mathematics)과 메타수학(meta-mathematics), 괴델수(Gödel number), 메타수학의 수학화의 3가지로 나누어 설명하겠다. 본 글이 불완전성정리의 아름다움을 느끼는 데 도움이 되길 바란다.
수학(mathematics)과 메타수학(meta-mathematics)
보통 불완전성 정리에 대한 책들에서는 간략하게 증명의 개요만 언급하는데 그것은 아래와 같다.
만약
수학 명제와 메타수학 명제의 차이점
아주 간단한 수학 명제 하나를 살펴보자.
이 표현은 수학에 속한 표현이다. 이제 다음 명제를 살펴보면
그러나 괴델은 이 부분을 파고들어 메타수학의 명제를 수학의 명제로 바꾸는 괴델수(Gödel number) 라는 독창적인 아이디어를 제안, 메타수학의 명제를 수학 체계로 갖고 온 후 자기언급의 역설을 보여주었다. 괴델수부터 차근차근 알아보도록 하자.
괴델수(Gödel number)
괴델수는 모든 기호, 변수, 명제, 명제묶음(증명)들에 유일한 숫자를 부여하는 것인데 몇가지 예를 들어보면 다음과 같다.
기호 | 괴델수 | 의미 |
---|---|---|
1 | 아니다 | |
2 | 또는 | |
3 |
|
|
4 |
|
|
5 | 같다 | |
0 | 6 | 영(0) |
s | 7 | 바로 다음 수 |
( | 8 | 왼쪽 괄호 |
) | 9 | 오른쪽 괄호 |
, | 10 | 쉼표 |
11 | 더하기 | |
12 | 곱하기 |
위의 표에 나와있는 기호들을 상항기호라고 하며, 이와 대응되는 개념은 변항(variable)기호인데 숫자 변항, 문장 변항, 술어 변항으로 나눌 수 있다. 숫자 변항에는 12보다 큰 소수, 문장 변항에는 12보다 큰 소수의 제곱수, 술어변항에는 12보다 큰 소수의 세제곱수를 부여하게 되며 예는 아래의 표와 같다.
변항 | 괴델수 | 대입 예 | |
---|---|---|---|
숫자변항 | 13 | 0 | |
17 | |||
19 | |||
문장변항 | |||
( |
|||
술어변항 |
|
||
이제 문장 (
마찬가지로 증명에 대해서도 괴델수를 부여할 수 있는데 예를들어 증명이 두 서술로 되어 있고 각 서술의 괴델수가
메타수학의 수학화
괴델은 괴델수를 이용하여 메타수학의 명제를 수학의 명제로 바꾸는 데 성공하였는데 간단한 예를 들어보겠다.
는 “0은 0이 아니다.” 라는 단순한 수학 명제인 반면
는 수학명제가 아니라 메타수학의 명제이다. 그런데 이 메타수학의 명제는 적당한 과정을 거치면 수학명제로 바꿀 수 있다. 편의상
와 같이 수학명제로 바뀌게 된다. 기호로 표현하기 위해 표현을 바꾸면 “
불완전성 정리
이제 불완전성 정리를 천천히 이해해보자. Dem/dem과 Sub/sub의 개념을 정의한 후 증명의 핵심 아이디어로 들어가 보겠다.
Dem
dem은 증명을 뜻하는 demonstration의 약자로 dem(
의 축약표현으로 정의한다. 예를 들어 “피타고라스 정리 증명”의 괴델수가
Sub
Sub은 치환 혹은 대입을 의미하며 소문자로 표현한 sub(
로 정의한다(17은
로 정의한다. 이해를 돕기 위해
가 된다. 이제
얼핏 보기에 문장의 괴델수를 문장 그 자체에 대입한다는 것이 순환논리같은 느낌을 주는데 이것이 바로 괴델의 핵심적인 아이디어 중 하나이다. 이제부터 본격적인 증명의 내용으로 들어가기로 하자.
불완전성 정리
불완전성 정리의 증명은 “괴델수
이 수학의 형식문은 “Sub(
마치며
필자는 고등학생때부터 괴델의 불완전성정리를 이해해보려고 괴델의 논문원본도 찾아보고 여러 교양서적을 많이 읽어보았었다. 그러나 논문을 다 보는것은 이해하기가 어렵고 교양서적은 겉핥기식으로만 나와있어서 최근까지도 증명의 핵심을 이해하지 못했었는데 출판사 승산에서 나온 괴델의 증명을 읽으면서 한층 이해수준을 올릴 수 있었다. 이 책은 외국서적을 번역한 것으로 번역하면서 생소한 단어와 표현들이 많이나와 읽기가 어려운 부분이 있어 이번기회에 잘 풀어서 설명해볼 목적으로 글을 쓰게 되었다. 본 글이 논문과 교양서적 사이에서 가교 역할을 하여 불완전성 정리를 이해하는데 도움이 되길 기대한다.
참고문헌
괴델, 에셔, 바흐 : 영원한 황금 노끈 / 지은이: 더글러스 호프스태터 ; 옮긴이: 박여성, 안병서
(호프스태터가 서문을 쓰고 개정한) 괴델의 증명 / 지은이: 어니스트 네이글, 제임스 뉴먼 ; 옮긴이: 곽강제, 고중숙
괴델 불완전성 정리 / 지은이: 요시나가 요시마사 ; 옮긴이: 임승원
Citation
@online{kim2019,
author = {Kim, Jinseob},
title = {괴델의 {불완전성} {정리}},
date = {2019-05-22},
url = {https://blog.zarathu.com/posts/2019-05-20-godelincompleteness/},
langid = {en}
}