형식논리

By | November 16, 2016

형식논리에서는 문자열 또는 주어진 문자들의 유한열에 대하여 다룬다. 여기서 문자열은 그 자체로서는 어떠한 의미도 갖지 않는다. '공리', '추론규칙', '정리', '증명' 등의 용어를 사용하지만 이러한 용어는 일반적인 수학적 의미와는 독립적으로 사용된다. '정리'가 '증명'될 수 있다는 사실이 우리가 실제로 다루는 수학의 체계에서 어떠한 역할을 하는지는 뒤에서 밝혀질 것이다.

형식계의 의미

형식계(formal system)는 다음 네 가지로 구성된 체계이다.

  • 알파벳 \(A\) : 알파벳은 기호(symbol)의 집합이다.
  • 논리식(formula)의 집합 : 각 논리식은 \(A\)에 속한 기호로 이루어진 문자열(string)이다. 그러나 모든 문자열이 논리식인 것은 아니다. 주어진 문자열이 논리식인지 여부를 판별하는 기계적 절차가 존재한다.
  • 공리(axiom)의 집합 : 각 공리는 논리식이다. 하나의 형식계에서 공리의 개수는 유한일 수도 있고 무한일 수도 있다. 모든 논리식이 공리인 것은 아니다. 주어진 논리식이 공리인지 여부를 판별하는 기계적 절차가 존재한다.
  • 추론규칙(rule of inference) : 각 추론규칙은 유한 개의 논리식을 입력받아 하나의 논리식을 출력한다. 추론규칙을 적용하는 기계적인 절차가 존재하며, 각각의 경우에 추론규칙이 바르게 적용되었는지 판별할 수 있다.

형식계에서 증명(proof)이란 논리식의 열인데, 열의 각 논리식은 공리이거나 이전 항에 등장한 논리식에 추론규칙을 적용하여 얻어지는 논리식이어야 한다. 증명의 마지막 항(논리식)을 정리(theorem)라고 부른다.

하나의 형식계에서 모든 정리는 순수하게 기계적인 절차에 의하여 얻어질 수 있다. 즉 공리에서 시작하여 추론규칙을 적용할 수 있는 모든 경우의 수를 고려하여 그 결과를 출력하는 컴퓨터 프로그램을 구상할 수 있다. 모든 정리는 출력된 결과물의 어딘가에 존재하게 된다. 그러나 정리의 개수는 유한이 아닐 수 있다. (보통은 유한이 아니다.) 그러므로 어떠한 논리식이 출력된 결과에 아직 나타나지 않았다면 그 논리식은 앞으로 출력될 결과에 나타날지(정리인지), 아니면 영원히 나타나지 않을지(정리가 아닐지) 알 수 없다. 일반적으로 주어진 논리식이 정리인지 아닌지를 판별하는 절차(decision procedure)는 존재하지 않는다. 형식계가 어떠한 특징을 가지고 있는지에 따라 주어진 논리식이 정리인지를 밝혀내는 것이 가능할 수도 있고 그렇지 않을 수도 있다.

하나의 형식계를 구성하면서 형식계 자체를 하나의 수학적 개체로 다룰 수 있으며, 그 결과로 초정리(metatheorem)를 얻을 수 있다. 초정리는 형식계 자체의 특성에 대한 정리로서, 형식계 내에서 얻어지는 정리와는 다른 개념이다. [하지만 군론의 정리와 위상수학의 정리를 구분하지 않고 '정리'라고 부르는 것처럼, 넓은 의미로 봤을 때 형식계의 초정리와 정리는 수학자의 입장에서는 모두 정리일 뿐이다.]

형식계의 예

형식계 자체를 수학적 개체로 다루어 초정리를 얻어내는 예로 Hofstadter의 MU-계(MU-system)를 들 수 있다.

MU-계에서 알파벳은 집합 \(\left\{ \mathrm{M},\, \mathrm{I},\, \mathrm{U}\right\}\)이며 논리식은 비어있지 않은 문자열이다.

공리는 단 하나 존재한다: \[\mathrm{M I}\] 추론규칙은 네 개가 존재한다:

  • 규칙 1.  \(\mathrm{I}\)로 끝나는 문자열에는 끝에 \(\mathrm{U}\)를 추가할 수 있다.
  • 규칙 2.  \(\mathrm{M}\)으로 시작하는 문자열 \(\mathrm{Mx}\)에 대하여 \(\mathrm{M}\) 뒤에 이어지는 문자열을 복제하여 끝에 추가하여 \(\mathrm{Mxx}\)를 얻을 수 있다.
  • 규칙 3.  문자열에 \(\mathrm{I}\) 세 개가 연달아 나타나면 그 세 개의 문자를 \(\mathrm{U}\)로 바꿀 수 있다.
  • 규칙 4.  문자열에 \(\mathrm{U}\) 두 개가 연달아 나타나면 그 두 개의 문자를 없앨 수 있다.

MU-계에서의 증명의 예로서 다음과 같은 것을 들 수 있다: \[\mathrm{MI,} \quad \mathrm{MII,} \quad \mathrm{MIIII,} \quad \mathrm{MUI,} \quad \mathrm{MUIU}\] 이 증명은 공리 \(\mathrm{MI}\)로부터 시작하여 규칙 2를 두 번 적용하고 규칙 3, 규칙 1을 이어서 적용한 것이다.

규칙을 적용하는 방법이 하나만 있는 것은 아니다. 예컨대 위 증명의 세 번째 단계에서 \(\mathrm{MIU}\)를 얻을 수도 있다. 또한 하나의 정리에 둘 이상의 증명이 존재할 수 있다. 공리 \(\mathrm{MI}\)에 규칙 1을 적용하여 \(\mathrm{MIU}\)를 한 번에 얻을 수도 있다.

이제 다음과 같은 질문의 답을 생각해보자.

Hofstadter의 질문 : "\(\mathrm{MU}\)는 정리인가?"

만약 \(\mathrm{MU}\)가 정리라면 그것의 증명이 존재하며, 증명을 찾고자 하는 노력이 의미를 가진다. 그러나 만약 \(\mathrm{MU}\)가 정리가 아니라면 그것의 증명이 존재하지 않으므로 증명을 하려고 노력해도 아무것도 얻을 수 없다.

사실 \(\mathrm{MU}\)는 정리가 아니다. \(\mathrm{MU}\)가 정리가 아니라는 사실은 초정리이며, 그것을 증명하기 위해서는 증명 길이에 대한 수학적 귀납법이라는 기술이 필요하다(induction on the length of the proof).

정리 1. MU-계의 정리에서 \(\mathrm{I}\)가 나타나는 횟수는 \(3\)의 배수가 아니다. (특히 \(0\)은 \(3\)의 배수이므로, 모든 정리는 \(\mathrm{I}\)를 포함한다.)

증명. 증명 길이, 즉 증명을 구성하는 논리식의 개수에 대한 수학적 귀납법을 사용하자. 가장 짧은 증명의 길이는 \(1\)이며, 그것은 하나의 공리로 이루어져 있다. 그런데 공리는 \(\mathrm{MI}\) 뿐이며, 여기에는 \(\mathrm{I}\)가 \(1\)개 포함되어 있고, \(1\)은 \(3\)의 배수가 아니므로 증명 길이가 \(1\)인 경우에 대해서 정리의 주장은 참이다.

이제 \(t\)가 정리이고 \(t\)의 증명 길이가 \(n\)이며, 길이가 \(n\)보다 짧은 증명을 가진 모든 정리에 대해서 정리의 주장이 참이라고 가정하자. \(n=1\)인 경우는 이미 증명하였으므로 \(n > 1\)인 경우만 고려하면 된다. \(n > 1\)이므로 \(t\)는 증명 길이가 \(n-1\)인 정리 \(s\)에 추론 규칙을 적용하여 얻어진 것이다. \(s\)에 나타나는 \(\mathrm{I}\)의 개수를 \(x\)라고 하자. 귀납적 가정에 의하여 \(x\)는 \(3\)의 배수가 아니다. \(t\)에 나타나는 \(\mathrm{I}\)의 개수를 \(y\)라고 하자. 그러면 \(s\)에 각각의 추론 규칙을 적용했을 때 \(x\)와 \(y\)는 다음과 같은 관계를 갖게 된다:

  • 규칙 1 :  \(y=x\)
  • 규칙 2 :  \(y=2x\)
  • 규칙 3 :  \(y=x-3\)
  • 규칙 4 :  \(y=x\)

각 경우에 \(y\)는 \(3\)의 배수가 아니다. 그러므로 \(t\)에 나타나는 \(\mathrm{I}\)의 개수는 \(3\)의 배수가 아니다.

이로써 수학적 귀납법에 의하여 정리가 증명되었다.

위 정리에 의하면, \(\mathrm{MU}\)에는 \(\mathrm{I}\)가 없으므로 \(\mathrm{MU}\)는 MU-계의 정리가 아니다.

Hofstadter가 만든 MU-계의 예는 우연히 구성된 것이 아니다. Hofstadter의 MU-계는 정리와 초정리를 구분하게 하기 위해 고안된 예인데, 다음과 같은 일화에서 착안하여 만들어진 것이다.

수도승이 선사(禪師)에게 물었다: "개가 불성을 가질 수 있습니까?"
선사는 대답했다: "Mu(無)."

선사의 대답인 'Mu(無)'는 'No(不)'와 발음이 비슷하지만 같은 뜻은 아니다. 즉 선사의 대답은 'Yes'도 아니고 'No'도 아니다. 선사의 대답은 "그 질문은 의미가 없다, 그 질문은 잘못된 마음에서 나온 것이다"라는 의미를 가진다. 'Yes'와 'No'는 수도승의 마음에 있는 체계 내에서의 답이며, 선사의 대답은 그 체계를 벗어난 답이다.

Leave a Reply