증명이란 무엇인가?

 

괴델 : 불완전성 정리 : 요시나가 요시마사 지음, 임승원 옮김, 전파과학사, 1993, page 142~162

 

1. 힐베르트의 프로그램

     (1) 「산술의 무모순성」을 증명할 수 있는가?

     (2) 네 가지 근본 문제에서 프로그램으로

     (3) 형식화 - 공리나 정리를 기호로 표현

     (4) 초수학 또는 증명론

     (5) 유한의 입장

2. 논리학과 수학

     (1) 논리학의 형식화에서 수학의 형식화로

     (2) 논리학에서는 전제가 허위이면 결론은 모두 진실이다!?

     (3) '논리적인 올바름' 과 '수학적인 올바름' 과는 일치하지 않는다.

     (4) 아카만, 술어논리의 무모순성을 증명

3. 술어논리의 완전성 정리

     (1) 먼저 기호의 설명을 잠깐

     (2) '항', '논리식' 의 정의와 논리 법칙

     (3) '증명' 과 '해석'

     (4) 무모순성과 완전성의 정식화

     (5) 괴델에 의한 완전성 정리의 증명

 

1. 힐베르트의 프로그램

이 II 부에서는 I 부에서 말해 온 시대배경과 기초지식에 입각하여 괴델과 그 이론을 테마로 채택한다. 완전성 정리와 불완전성 정리의 의미에 대한 정확한 이해 및 불완전성 정리의 증명에 대한 본질을 아는 것이 여기서의 목적이다.

그를 위해서는 이제까지는 이야기의 흐름이 끊기지 않도록 굳이 그 내용에는 언급해 오지 않았던 논리학과 초수학에 대해서 암만해도 깊이 파고든 해석을 해 가지 않으면 안된다. 아마 많은 독자는 익숙하지 못한 기호의 홍수에 당황할 것이다. 그러한 경우 처음에는 너무 기호에 구애받지 말고 읽어 나아가 이야기의 큰 줄거리의 이미지를 포착토록 하기 바란다. 괴델도 다음과 같이 난해한 이론을 읽는 비결을 교시하고 있다.

우선은 「힐베르트의 프로그램」의 구체적인 내용 설명부터 이야기를 시작한다.

(1) 「산술의 무모순성」을 증명할 수 있는가?

유클리드 기하학에서 외적인 절대적 진리성의 가면을 벗겨서 그것을 단순한 "맥주조까지의 게임" 으로 바꿔 버린 힐베르트와 현대 수학에 있어서, 수학이라고 하는 학문이 유일하게 의지할 곳은 공리화된 체계의 무모순성의 보증이고 수학의 진리성은 그 이외의 어디에도 구해야 할 것도 없는 것이었다.

수학이란 원래 가장 보편적이고 동시에 포괄적인 관념의 학문이고 생각할 수 있는 것이라면 현실에 존재할 수 있는지 아닌지를 불문하고 그 모두를 대상으로 할 수 있는 자유성을 갖고 있다. 그 자유성이 물리학이나 화학, 생물학 등 일반의 자연과학과 수학이 근본적으로 상이한 점이고, 역으로 말하면 수학이 "사고의 형식" 에 관한 이론으로서 온갖 자연과학에 응용될 수 있는 이유이다.

칸토어의 말대로 '수학의 본질은 자유성에 있다' 라고 하는 것인데 바야흐로 수학은 그 절대적 자유를 하나의 근본적인 제약에 맡기게 된 것이다. 즉 '생각하는 것이 가능한 것' 이란 단순한 공상의 산물이나 관념의 놀이 등은 결코 아니고 수학적으로는 '무모순인 대상' 에 대한 것이라는 제약이다.

그래서 무한에 대한 생산적인 사고를 가능케 한 집합론이라고 하는 이름의 '칸토어의 낙원' 을 사수해야 할 집합론과 전수학의 무모순성에 관한 절대적 증명을 입수하는 것이 그 후 힐베르트의 - 따라서 또 현대 수학의 - 강박관념으로 되었다. 세기가 바뀌는 때에 해당되는 1900 년의 국제수학자회의에서 힐베르트가 20 세기 수학의 최고의 과제의 하나로서 '산술의 무모순성의 증명' 을 내세운 것도 그 때문이다.

그러나 이때 힐베르트는 아직 낙관적인 전망을 갖고 있었던 것 같다. 산술의 무모순성만 증명되면 그 증명은 쉽게 실수론의 무모순성의 증명으로 개변되고 그것은 동시에 그가 이미 증명하고 있는 사실에 따라서 유클리드 기하학과 비유클리드 기하학의 무모순성의 보증으로 된다. 이리하여 전수학은 새로운 의미에서의 즉 내적이고 자기완결적인 의미에서의 절대적 진리성을 쟁취할 것이다라고 하는 시나리오이다.

그런데 「러셀의 패러독스」가 가져온 "수학의 위기" 는 이 "힐베르트의 꿈" 앞에 어두운 구름으로 되어 가로막고, 그 근본적인 수정을 강요한다. 집합론이나 논리학과 같은 수학의 밑바탕에 있는 '가장 간단하고 가장 중요한 연역적 방법 더구나 가장 보통이고 또 결실이 많은 개념이 그 기반을 위협당한' (힐베르트) 것이다.

이러한 배경 아래에서 힐베르트는 1904 년 수학사상 처음으로 증명 바로 그것을 수학적 연구의 테마로 해야 할 것을 제안한다. 종전에는 증명이란 전통적인 논리학의 여러 법칙에 따른 추론에 대한 것이었으나 거기에는 이미 증명해야 할 집합론이나 산술의 내용이 선취되어 있거나 해서 '원고리 속을 돌고 있다' 는 것을 힐베르트는 깨닫게 된 것이다. 여기에 「힐베르트의 프로그램」의 단서, 그 최초의 아이디어가 탄생했다고 보아도 될 것이다.

그러나 보다 구체적인 제안이 나오는 데에는 1917 년까지 기다리지 않으면 안되었다. 이때에는 이미 1908 년의 체르멜로에 의한 공리적 집합론의 시도로 시작되는 집합론의 공리화에 대한 연구도 진전하고 있었다. 집합론의 공리화는 1922 년에 체르멜로의 작업을 발전시킨 프렌켈 (Fraenkel) 의 연구에 의해서 거의 완성되고 그 뒤 여러 가지 확장이나 간소화는 있었다 하되 그 시점에서 오늘날과 같은 집합론에 대한 대강의 줄거리가 만들어졌다고 해도 될 것이다. 이 집합론은 「체르멜로 - 프렌켈의 집합론」또는 두 사람의 머리문자를 따서 간결하게 「ZF 집합론」이라고 부르고 있다. 그리고 ZF 집합론 이후 '현대 수학은 모두 집합론 속에서 전개할 수 있다. 즉 현대 수학은 집합론의 부분 체계로 생각할 수 있다' (다케우치 가이시 교수) 라는 견해가 정착한다.

 

(2) 네 가지 근본 문제에서 프로그램으로

이야기를 러시아 혁명의 해인 1917 년으로 되돌린다. 이 해에 힐베르트는 츄리히에서의 강연에서 네 가지 근본 문제를 제기하고 있다. 「힐베르트의 프로그램」의 원형이라고 일컬어지고 있는 제안이다. 그 네 가지란 다음과 같은 것이었다.

이러한 문제의 제출방법으로 보아 당시 힐베르트의 머리 속에는 아직 막연한 전략밖에는 없었던 것같이 생각된다. 힐베르트의 첨예한 전략과 전술이 구체적인 형태로 돼서 나타나는 것은 1922 년의 일이다. 이때 「힐베르트의 프로그램」이 완전한 형태로 제안된 것이다.

이하 완전판의 형태로 「힐베르트의 프로그램」의 요지를 설명해 보자. 요점은 세 가지가 있다. '형식화', '초수학' (또는 '증명론') 그리고 '유한의 입장' 의 세 가지다. 이들 개념이 직관주의나 논리주의와의 투쟁 속에서 차츰 단련되어 가는 것은 그 역사적 경위에 준거해서 앞장에서 상세히 소개한 대로이다.

 

(3) 형식화 - 공리나 정리를 기호로 표현

먼저 형식화에 대한 것인데 힐베르트는 집합론이나 자연수론을 포함하는 전수학을 형식화하여 그 무모순성을 증명해야 한다고 제안하였다. 즉 온갖 수학 이론을 유클리드 기하학에서 이루어진 것처럼 공리화해서 그 내용인 공리나 정리를 모두 기호로 표현하자는 것이다.

그때 공리의 모임인 소위 공리계는 그것이 적용되는 대상에 대한 규정뿐만 아니라 그 운용규칙인 추론의 논리법칙도 스스로의 안에 포함하고 있지 않으면 안된다.

이와 같이 현상학의 용어로 말하면 '노에마 (Noema)' 에 해당하는 "대상" 과 '노에시스 (Noesis)' 에 해당하는 "작용" 을 1 조로 한 시스템이 공리계인데 이 공리계에서 규정되는 형식적인 연역체계가 다름아닌 「형식적 체계」바로 그것이다.

형식적 체계는 「힐베르트의 프로그램」ㄹ에 잇어서도 논리주의와 마찬가지로 기호논리 (정확히 말하면 제 1 계 술어논리) 로 기술된다. 그러나 논리주의가 논리법칙을 절대적인 것으로 간주한 것에 반해서 형식주의에서는 이것을 어디까지나 "게임의 룰" 로밖에는 생각하지 않는다. 희망한다면 얼마든지 변경가능한 것으로서 이것은 말하자면 "작용 (노에시스)" 으로부터의 의미 박탈이다.

한편 형식적 체계에서는 "대상 (노에마)" 으로부터도 의미가 뽑아내져 있다. 공리화된 유클리드 기하학에 있어서는 '평면' 을 '맥주조끼' 로 바꿔 읽는 것이 가능하였던 것과 같은 이치로 형식적 체계의 대상은 단순하고 무의미한 기호에 지나지 않는다. 이것은 직관주의자가 형식주의를 향하여 '일반적으로 받아들여지고 있는 수학에 있어서 많은 경우에 참된 의미를 갖지 않는 명제가 통용되고 있다' 라는 문제를 제기한 것에 대한 형식주의측의 회답이었다. 즉 형식주의는 이 논의의 전제인 '의미' 라고 하는 것을 처음부터 완전히 폐기시킴으로써 직관주의의 공격을 피한 것이다.

그림 1  초수학과 형식적 수학, 비형식적 수학의 관계

 

(4) 초수학 또는 증명론

다음으로 '초수학' 또는 '증명론' 에 대한 이야기를 진행하자.

형식적 체계에서는 기호도 추론법칙도 그 자체에는 의미가 없으나 그것들이 형성하는 체계 바로 그것의 구조에는 의미가 있다. 즉 형식적 체계에 있어서의 '증명' 은 하나의 기호열로서 표시되어 이 기호열을 수학적 고찰의 새로운 대상으로 할 수가 있는 것이다. 이 새로운 수학을 초수학이라 부른다. "초" 는 '슈퍼 (super)' 나 '울트라 (ultra)' 가 아니고 '메타 (meta)' 의 뜻이다. 통상의 의미에서의 수학을 논하는 것이 아니고 그것을 '초월해서' 형식화된 체계의 구조를, 말하자면 "초월론적" 으로 고찰한다라는 의미일 것이다. '우수한 수학' 의 의미가 아니라는 것은 말할 것도 없다.

힐베르트의 고향인 쾨니히스베르크에 사는, 대선배인 칸트는 그 주요 저서 『순수이성비판』속에서 인식론에 있어서의 '사실문제' 와 '권리문제' 와의 준별을 설명하였다. 초월론적 철학의 과제는 '사실문제' 가 아니고 '권리문제' 이다라고 칸트는 말하고 있다. 법률용어에서 빌린 이들의 말을 사용한다면 통상의 수학이 '사실문제' 의 해명을 전념할 일로 삼고 있다면 초수학의 관심사는 '권리문제' 의 탐구에 있다고 해도 좋을 것이다.

그러나 이러한 '초수학' 의 목적은 어디까지나 원래의 즉 현실의 수학의 무모순성에 대한 증명에 있기 때문에 이 학문은 '증명론' 이라고도 부른다. 이것도 '증명하는 방법' 의 의미가 아니고 하위수준의 증명의 구조와 타당성을 상위의 즉 메타레벨에서 '증명' 하는 학문의 의미이다.

'초수학' 의 위치 부여와 역할을 정리하면 다음과 같이 된다.

 

(5) 유한의 입장

마지막으로 '유한의 입장' 인데 이것은 '초수학' 의 방법론을 규정하는 개념이다. 힐베르트의 말로는 이렇게 된다.

간단히 말하면 유한개의 기호열을 대상으로 유한회의 조작에 의해서 실행가능한 사실만을 기초로 함으로써 '초수학' 의 확실성을 보증하려고 하는 뜻이다.

'유한의 입장' 은 직관주의의 근본사상과 통하는 거싱고 직관주의로부터의 비판에 대답하는 형태로 채용된, 또는 직관주의의 주장을 받아들인 것이다라고 흔히 일컬어진다. 확실히 그것도 사실일 것이다. 그러나 힐베르트는 당초부터 '유한의 입장' 을의 지향이 있었던 것처럼 생각한다. 이러한 것은 「힐베르트의 프로그램」이 싹트기 이전인 그 1900 년의 강연 속에서 힐베르트는 이미 다음과 같이 명확히 지적하고 있었기 때문이다.

물론 여기서의 유한회의 프로세스에 대한 강조는 비형식적 체계 속에서의 엄밀성에 대한 것에 지나지 않으나 '유한의 입장' 은 사상을 형식적 체계에 대한 초수학으로까지 확장한 것이다라고도 해석할 수 있는 것이 아닐지.

덧붙여 말하면 힐베르트의 "동료" 였던 철학자 후설에게도 『엄밀한 학문으로서의 철학』이라는 저작이 있다. "엄밀성" 이 아직도 최고의 가치를 가질 수 있었던 옛날의 좋은 시대가 나에게는 부럽게 생각된다.

 

2. 논리학과 수학

(1) 논리학의 형식화에서 수학의 형식화로

다케우치 가이시, 일리노이대학 교수는 유명한 저서 『집합이란 무엇인가』속에서 「힐베르트의 프로그램」을 다음과 같이 3 단계로 나누어서 정식화하고 있다.

여기서 논리학과 수학에 대한 프로그램이 분명히 나누어져 있는 데에는 매우 중요한 의미가 있다. 이러한 것은 괴델에 대한 "풍설" 속에서 흔히 다음과 같은 야지기타 [역주 : 서로 짝이 맞는 한쌍의 익살꾼, 원래 일본 근세의 유머통속소설 『도카이도츄히자구리게』의 주인공 야지로베에, 기타하치의 이름에서 온 말] 적인 회화를 듣기 때문이다.

확실히 괴델은 1930 년에 완전성 정리의 증명을, 1931 년에 불완전성 정리의 증명을 발표하였다. 그러나 이것은 모순되는 것은 아니다. 왜냐하면 전자는 논리학 (제 1 계 술어논리) 의 형식적 체계에 대해서, 후자는 수학 (페아노의 산술의 공리계를 포함하는 무모순인 공리계) 의 형식적 체계에 대한 정리이고 양자는 근본적으로 상이한 것에 대한 언급이었기 때문이다.

그러나 야지로베에 씨도 날카로운 곳을 찌르고 있다. 만일 불완전성 정리가 완전성 정리의 단순한 부정이고 누군가가 그 양쪽을 증명했다라고 하는 것이라면 그이 (그녀) 는 사기꾼 이외의 아무것도 아니기 때문이다.

 

(2) 논리학에서는 전제가 허위이면 결론은 모두 진실이다!?

이것은 이미 「천재와 나폴레옹의 어머니」의 예문을 들어서 이야기한 것이나 - 기억하고 있는지? - 중요한 것이기 때문에 반복을 마다않고 다시 한번 확인해 둔다. 논리학적으로 말하면 전제가 '허위' 이면 결론은 어떠한 것이라도 '진실' 이다. 예컨대 「말은 하마이다」라면 「개미는 코끼리보다 크다」도 「1999 년에 세계가 파멸한다」도 어떠한 명제라도 논리적으로는 올바른 귀결로서 얻어진다. 물론 「개미는 코끼리보다 작다」도 진실이다. 더구나 「개미는 코끼리보다 크고」동시에 「개미는 코끼리보다 작다」라면 「개미는 코끼리와 같은 크기이다」도 진실이다. 이렇게 해서 「이상한 나라의 앨리스」의 세계가 재현된다고 하는 의도였다.

형식적 체계의 공리계에 대해서도 전적으로 같은 것을 말할 수 있다. 한번 공리계가 모순을 안아 버리면 그 공리계로부터는 어떠한 명제도 유도해낼 수 있는 것이다. 공리계의 무모순성 즉 거기에서 서로 모순되는 명제를 증명하는 것에 대한 불가능성이 엄격히 요구되는 까닭이다. 이 '무모순' 이라고 하는 용어는 영어로 말하면 'consistency' 즉 일상용어로서는 '시종일관, 정합성, 언행일치' 를 의미하는 말이다.

I 부의 3 장에서 언급한 것처럼 의미가 있고 동시에 생산적인 공리계에는 '무모순성' 이외에 '완전성'. '독립성' 이라고 하는 나머지 두 가지의 중요한 성질이 요구된다. '완전성' 이란 형식적 체계의 모든 올바른 정리가 그 공리계로부터 증명가능한 것이다.

무모순성과 완전성과는 밀접하게 결부되어 있고 공리계를 강하게 하면 증명할 수 있는 명제가 증가해서 완전성을 얻을 수 있게 되나 그때 너무 지나치게 강하면 어떤 명제와 그 부정 명제의 양쪽이 증명되어 버릴지도 모른다. 즉 무모순성이 깨져 버리는 것이다.

역으로 공리계를 약화시켜서 모순을 없애면 증명가능한 명제가 극단적으로 감소되어 버린다. 배중률을 공리계에서 제거한 직관주의가 그 좋은 예이다. 이와 같이 공리계의 조정은 상당히 스릴 넘치는 게임이라고 말할 수 있다.

그런데 방금 '완전성이란 모든 올바른 정리가 증명가능한 것이다' 라고 말했다. 이 정의에서도 알 수 있는 것처럼 '올바른' 이라는 것과 '증명가능' 하다는 것과는 어떻게 다른 것인가 하는 점이 완전성 문제를 생각할 때의 요점으로 된다. 더구나 실제의 수학의 구체적인 명제에 대해서는 진위가 분명하게 되어 있는 것이기 때문에 이 경우는 '진실이다' 라는 것과 '올바르다' 라는 것과의 구별이 또한 문제가 된다. 이 언저리를 확실히 파악해 두지 않으면 앞에서 말한 야지기타가 서로 주고받는 이야기가 되어 버리는 셈이다.

이하의 전개를 위해서 개요를 미리 대충 살펴 두자.

 

(3) '논리적인 올바름' 과 '수학적인 올바름' 과는 일치하지 않는다.

괴델의 완전성 정리는 논리학의 형식적 체게에 대해서 증명된 사항이다. 우리들이 사용하고 있는 논리학의 체계는 완전하다. 즉 '논리적으로 올바른' 명제라면 어떠한 것이라도 그 체계 내에서 '증명가능' 하다라는 것이다. 우리들의 "상식적" 인 논리적 직관에는 초수학적인 뒷받침이 있었던 것이다라고 말해도 될 것이다.

논리의 다음으로는 수학이 문제로 되는데 여기서는 '수학적으로 올바르다' 는 것이 '논리적으로 올바르다' 는 것과는 반드시 일치하는 것은 아니다. 논리적인 올바름이란 어떠한 대상에 대해서도 적용되는 추론의 올바름에 대한 것을 말한다. 예컨대 「A 이면 A」가 그 좋은 예이고 A 가 진실이든 허위이든 이 추론 바로 그것은 올바르다고 말할 수 있다. 이러한 추론을 '항진명제' 또는 '토톨러지' 라 부른다. 토톨러지는 일상용어로는 '동어반복' 이라고 번역되어 있다.

수학적인 올바름은 이것과는 달리 사항의 진위가 추궁된다. 즉 수학에 있어서의 명제는 수학적인 내용을 갖는 이상 원리적으로는 진위가 미리 결정되어 있을 것이다 (다만 소위 '자유변수' 를 갖지 않는 경우). 그래서 수학의 형식적 체계에 대한 완전성의 요청이란 '모든 참된 명제가 그 체계 내에서 증명될 수 있는 것' 으로 된다. 어쩐지 자명한 것으로 생각되나 그것이 자명하기는 커녕 잘못된 것이라는 것을 증명해 버린 것이 괴델의 불완전성 정리였던 것이다.

이 정리의 증명이 얼마나 충격적인 사건이었는가는 이 정도의 설명으로도 다소는 알게 되었을 것으로 생각한다. 이 사실은 수학의 무모순성에 대한 증명 자체도 사실대로 말해 버리면 그 원리적인 불가능성을 암시하여 「힐베르트의 프로그램」에 어떤 의미에서의 인도를 넘겨 주는 결과가 되는 것이나 이것 이상 언급하면 개요를 넘어서 버리기 때문에 나머지는 불완전성 정리를 주제로 거론하는 다음장에서 이야기하자.

 

(4) 아카만, 술어논리의 무모순성을 증명

그러면 여기서 논리학으로 되돌아가서 이제까지 언급해 온 것을 조금 상세하고 구체적으로 설명해 보자. 여기서 거론하는 것은 1928 년에 초판이 간행된 힐베르트와 아카만의 공저 『수리논리학의 기초』이다. 기호논리학의 공리화는 1910~1913 년의 『프린키피아 마테마티카』를 시초로 정력적으로 연구가 진행되었으나 수학을 기술할 수 있는 소위 「제 1 계 술어논리」의 형식적 체계가 완성된 모습으로 나타난 것은 이 책에서였다고 일컬어지고 있다.

여기서 아카만은 술어논리의 무모순성을 증명하고 완전성의 결정을 미해결 문제로서 제시하여 그 정부를 추궁하고 있다. 괴델이 이에 응답해서 완전성 정리를 증명한 것은 1929 년 가을 약관 23 세 때였다. 논문은 1930 년에 발표되고 이것에 의해서 동년 2 월 6 일에 괴델은 빈대학으로부터 학위를 받고 있다.

기호의 나열을 시작하기 전에 이 책의 공저자인 힐베르트의 공동연구자 빌헬름 아카만에 관한 에피소드를 하나 소개해 둔다. 힐베르트는 젊고 유능한 제자가 결혼하는 것에 늘 강하게 반대하고 있었다. 자기의 경험 때문인지, 단순한 확신 때문인지는 모르나 아무튼 결혼하면 수학을 할 수 없게 된다고 믿고 있었던 것 같다. 이 편견 때문에 가장 희생된 것이 다름아닌 아카만이었다.

아카만이 결혼 후, 힐베르트는 격노해서 그이가 대학에서의 연구자로서의 지위를 얻지 못하게 되어 버린다. 결국 아카만은 할 수 없이 고교교사로 만족할 수 밖에는 없었다. 그러나 결혼생활은 행복했던 것 같고 그 뒤 얼마 안가서 아카만 부처는 아기를 갖게 된다.

이 소식을 듣자 힐베르트는 다시 없는 공을 세운 듯이 기고만장하게 흥분해서 이렇게 말했다고 한다. "그것은 굉장한 소식이다. 결혼한 것만도 어떤가 생각하고 있었는데 아기까지 만들다니, 이런 어이없는 사나이에게는 이제부터라도 일체 아무것도 해 주지 않을 거야."

어떠한 위인에게도 보통 사람으로서는 이해불가능한 편굴한 일면이 하나쯤은 있는 것이다

3. 술어논리의 완전성 정리

(1) 먼저 기호의 설명을 잠깐

술어논리의 형식화는 모든 대상과 논리법칙 (공리) 의 기호화로부터 시작된다. 「처음에 기호 있다」이다.

기본 기호는 그림 1 의 여섯 종류이다.

이 중, '자유변수' 란 불특정의 대상, '속박변수' 란 논리기호 ∀ 과 ∃ 의 어느 것인가와 함께 사용하는 변수를 나타낸다.

(1) 대상기호(상수)               ···············

(2) 함수기호                      ···············

(3) 술어기호                      ·············

(4) 자유변수                      ··············

(5) 속박변수                      ·············

(6) 논리기호                      ∨, ∧, →, ￢, ∀, ∃

그림 1  기본기호

어느 것인가와 함께 사용하는 변수를 나타낸다. ∀ 과 ∃ 는 '속박기호' 또는 '양기호' 라 부르고 ∀ 를 '전칭기호', ∃ 를 '존재기호' 라고 말한다.

이 ∀ 와 ∃ 를 포함하지 않는 논리 체계가 『프린키피아 마테마티카』에서 처음으로 체계화된 '명제논리학' 이다. 이 쪽은 벌써 1920 년에 그 무모순성과 완전성이 당시 컬럼비아대학의 학생에 지나지 않았던 E. L. 포스트에 의해서 증명되고 있다.

논리기호는 초수학에 있어서는 추상적인 단순한 기호에 지나지 않는다. 그러나 근원을 밝히면 그것들에는 원래 각각 고유의 의미가 있다. 즉 「￢」는「……이 아니다」, 「∨」는 「또는」, 「∧」는 「동시에」, 「→」는 「이라면」, 「∀」는 「모든」, 「∃」는 「어떤 ……가 존재한다」의 의미이다.

이 해석으로 말하면 대상이 유한집합의 경우는 술어논리도 명제논리로 환원할 수 있다. ∀ 과 ∃ 는 무한집합을 대상으로 할 때 비로소 의미를 갖는 논리기호이다. 수학은 본질적으로 무한집합을 대상으로 하고 있기 때문에 술어논리는 수학의 논리로 되어 있는 것이다.

그러나 지금은 이러한 유래를 제외하고 형식적 체계만을 문제로 삼고 있기 때문에 당분간 기호의 의미는 잊어 버려도 상관없다. 오히려 적극적으로 잊어 버려 기호의 조작에만 전념하려고 하는 것이 초수학의 기본 방침이다.

    (1) 대상 기호와 자유변수는 항이다.

    (2) f 가 n 변수의 함수기호이고 t1, t2, ……, tn 이 항이라면 f(t1, t2, ……, tn) 은 항이다.

    (3) (1) 과 (2) 로 얻어지는 것만이 항이다.

그림 2  '항' 의 정의

 

    (1) P 가 n 변수의 술어기호이고 t1, t2, ……, tn 이 항이라면 P(t1, t2, ……, tn) 은 논리식이다.

    특히 이것을 「원시논리식」이라 부른다.

    (2) A, B 가 논리식일 때

    ￢A, A∨B, A∧B, A→B 도 논리식이다.

    (3) A(a) 가 자유변수 a 를 포함하는 논리식이고 x 가 A(a) 속에 나타나지 않는 속박변수일 때

    ∀xA(x), ∃xA(x) 는 논리식이다.

    (4) (1), (2), (3) 에 의해서 얻어지는 것만이 논리식이다.

    (덧붙여 말하면 ∀xA(x) 는 「모든 x 는 A 를 충족시킨다」, ∃xA(x) 는 「A 를 충족시키는 x 가 존재한다」라고 해석한다.

그림 3  '논리식' 의 정의

 

    공리

      (1) A → (B → A)

      (2) (A → B) → ((A → (B → C)) → (A → C))

      (3) A → (B → A ∧ B)

      (4) A ∧ B → A, A ∧ B → B

      (5) A → A ∨ B, B → A ∨ B

      (6) (A → C) → ((B → C) → (A ∨ B → C))

      (7) (A → B) → ((A → ∠B) → ∠A))

      (8) ￢￢A → A

      (9) A(t) → ∃xA(x) (t 는 항)

      (10) ∀xA(x) → A(t) (t 는 항)

     

    추론 규칙

1.

A, A → B

 

 

B

 

2.

A(a) → C

 

 

∃xA(x) → C

 

3.

C → A(a)

 

 

C → ∀xA(X)

 

  (다만 A, B, C, ……, ∀xA(X) …… 등은 모두 논리식으로 한다.

그림 4  추론을 행하기 위한 논리법칙 (힐베르트 - 아카만의 공리계에 따른다)

 

(2) '항', '논리식' 의 정의와 논리 법칙

기호가 갖추어진 곳에서 추론의 대상이 되는 '항' 을 그림 2 와 같이 정의한다.

다음으로 이 항을 사용해서 '논리식' 을 항의 정의 아래의 그림 3 과 같이 정의한다.

그러면 다음은 이들 논리식을 사용해서 추론을 행하기 위한 논리법칙의 설정인데 힐베르트 - 아카만의 공리계에서는 그림 4 의 추론을 행하기 위한 논리법칙과 같이 되어 있다.

 

(3) '증명' 과 '해석'

이만큼 준비가 된 곳에서 '증명가능' 의 개념을 다음과 같이 정의한다.

논리식 A 가 B1, B2, ……, Bn 을 가정했을 때 증명할 수 있다면

라고 쓴다.

또한 A 가 술언논리의 공리만을 사용해서 증명 가능할 때는

라고 쓴다.

 

그림 5  A → A 의 증명도

지금 「├ A → A 」(A → A 는 증명 가능) 을 공리로부터 유도해 보자 (그림 5).

통상의 해석으로는 「A → A」는 요컨대 「A 이면 A」라는 것 바로 그것이기 때문에 "자명한 이치" 처럼 생각된다. 그러나 여기서 채용한 공리에 「A → A」는 들어가 있지 않기 때문에 형식적으로는 증명의 가능성은 보증되어 있지 않고 보는 바와 같이 상당히 복잡한 절차를 밟아 증명하지 않으면 안된다.

주의해야 할 것은 여기서 말하는 '증명' 이란 '의미' 의 해석을 행하지 않는 한에는 증명도의 겹쳐 쌓음이고 더 단적으로 말하면 논리식의, 따라서 기본 기호의 유한 개의 배열에 지나지 않는다는 사실이다. 역으로 말하면 술어논리의 형식적 체계란 증명 가능한 논리식의 형식적인 겹쳐 쌓음으로 정의되고 생성되는 체계여서 거기서는 당장은 아무런 "의미" 도 추궁되고 있지 않다는 것이다.

이와 같은 무의미한 기호열에 술어로서의, 즉 무언가의 의미를 가진 언명으로서의 직관적 내용을 부여하는 것이 아까부터 설명을 빼고 사용해 온 '해석' 이라는 작업이다. 어떠한 해석 아래에서 증명 가능한 논리식이 모든 참된 명제를 나타낼 때 이 해석은 '모델' 을 정한다고 말한다. 다만 수학의 논리인 술어논리의 경우는 단순한 논리학을 위한 논리에 지나지 않는 명제논리와는 달라서 변수가 가질 수 있는 영역이 본질적으로 추궁된다. 구체적인 예로 보는 것이 이야기가 빠를 것이다.

실례를 두 가지 대비시켜서 보여 주자.

예컨대 논리식,

는 「모든 x 에 대해서 y 가 존재하고 y 는 x 보다 작다」라고 해석할 수 있다. 이 해석 아래에서는 실수의 영역이면 모델로 되나 자연수의 영역에서는 모델로 되지 않는다. 자연수로 x 를 0 으로 잡으면 그것보다 작은 자연수 y 는 이미 존재하지 않기 때문이다.

대비적인 실례로서 논리식,

를 취하자. 그 해석은 「어떤 x 가 존재하고 모든 y 에 대해서 y 는 x 와 같거나 x 보다 크다」로 된다. 이것은 자연수가 모델이라면 0 이라는 최소수가 존재하기 때문에 진실로 되나 실수의 모델에서는 허위로 되는 논리식이다.

그래서 모든 해석에 대해서 진실이 되는 논리식을 '항진식' 또는 '토톨러지' 라 부르고 A 가 토톨러지일 때

라고 쓰기로 한다. 이 토톨러지다는 것이 '논리적으로 올바르다' 라는 것에 대한 형식적인 표현이다.

 

(4) 무모순성과 완전성의 정식화

술어논리의 형식적 체계에 대한 무모순성의 정식화는 이러하다.

이 사실이 아카만에 의해서 증명된 것은 이미 언급하였다.

한편 완전성의 정식화는 이러하다.

여기서 폐논리식이란 자유변수를 포함하지 않는, 따라서 진위가 확정된 논리식을 말한다. 또한 이 정식화는 다음의 주장과 같은 값으로 된다.

즉 논리적으로 올바른 것 (토톨러지) 은 증명 가능하다는 것의 필요충분조건이라는 것이다. 필요조건 쪽은 명백하다. 이것을 「만인의 건전성 정리」라고도 부른다.

(5) 괴델에 의한 완전성 정리의 증명

괴델은 이것이 충분조건이기도 하다는 것을 보여 주었다. 즉 「괴델의 완전성 정리」다.

이리하여 술어논리의 체계는 무모순일 뿐만 아니고 완전이기도 하다는 것을 보여 준 것이다. 논리는 이것으로 태평무사이다. 「힐베르트의 프로그램」의 제 1 단계는 성공리에 끝났다.

그러면 다음은 마침내 수학 본체의 무모순성과 완전성을 추궁하는 차례이다.