Math Logic Intuitionism

수리논리의 세계 로 돌아가기

비고전 논리의 세계 : 직관주의 논리

앞에서는 주로 고전논리의 세계를 보았다. 여기서는 브라우어의 주장을 따른 직관주의 논리학을 세계를 보자. 브라우어의 수리 논리에 대한 철학적 입장에 대해서는 깊이 다루지 않겠다. 앞에서 소개한 정도로 만족하기로 한다. 직관주의 논리학의 철학적 입장을 따르느냐 따르지 않느냐에 관심을 갖는 것이 아니라, 고전주의 수리논리와 비교해봄으로써 기초적인 논리 법칙이 어떻게 전체 논리체계에 영향을 주는지 확인해보기 위해서다.

직관주의 명제 논리

핵심만 이야기하면 가장 기초적 법칙이라 할 수 있는 'A 가 아니다의 아니다'는 'A 이다' 라는 법칙을 따르지 않고 '제 3 의 가능성을 배제하는 법칙'을 당연한 것으로 받아들이지 않는다. 직관주의적 논리학의 주장한 브라우어 는 고전 논리의 수학 세계의 여러분야에서도 확실한 족적을 남긴 사람이다. 그 중 가장 유명한 정리가 토폴로지에서 "부동점 정리(A fixed point theorem)"이다. 19세기 중후반부터 집합론이 탄생하면서 수학의 전분야를 통합해서 말할 수 있는 탄탄한 기초를 다지게 되었다. 그런데 예상치 않은 모순들이 발견되었다. 버리기에는 집합론은 매우 매력적이고 수학적인 의미가 컸다. 집합론의 위기는 수학의 기초에 대한 위기였고 따라서 일군의 수학자들은 '모순'의 원인을 진단하고 나름대로 피해갈 수 있는 방안들을 구축해갔다. 브라우어는 모순의 원인 수학의 기초에서 함부로 믿어서는 안되는 논리적 법칙이 적용되고 있기 때문이라는 입장에 섰다. 정리를 발견하고 증명하는 과정에서 당연한 것으로 받아들여서는 안되는 논리적 법칙들이 있다는 것이다. 그중 가장 기초적인 것이 바로 '제 3 의 가능성을 배제하는 법칙' 이나 '아니다의 아니다는 이다'라는 고전적 사고'가 문제라고 주장했다.

브라우어는 그 자신의 철학적 입장을 주장하되 새로운 수학 자체를 만들 계획은 하지 않았다. 그런데 그의 제자였던 헤이팅(Arend Heyting ; 1898 – 1980 ) 이 수리 논리와 산술 분야에서 직관주의를 실현하게 된다. 또한 독일 출신의 베일(Hermann Weyl ; 1885 – 1955) , 러시아의 꼴모고로프(Andrey N. Kolmogorov ; 1903 - 1987) 도 독립적으로 직관주의적 논리학을 발전시켰다. 마르꼬프(Andrey A.Markov ; 1903 — 1979) 도 수정된 형태인 '구성주의(constructivism)' 에 기초한 방향으로 발전시킨다. 이후 지금까지 직관주의는 여러가지 변형된 형태로 수리논리와 산술과 같은 수학의 기초분야에서 발전해간다. 직관주의적 논리의 태도는 수리논리와 산술 분야에서 새로운 수학을 탄생시켜나가면서 수학의 다른 분야로 확대해나지만, 결국 힐버트가 예상했던대로 '제 3의 가능성 배제의 법칙'을 버리고, 그에 따라 '간접 증명을 받아들이지 않음으로써, 새로운 수학을 하기에는 힘겨운 길을 간다. 그렇지만, 수학의 기초를 엄격하게 다지고, 수학 연구의 여러 새로운 길을 트게 되는 계기가 되었다.

앞에서 이미 보았다시피, 직관주의적 논리의 입장은, 어떤 명제식 A 에 대해서도, $\neg \neg A\rightarrow A$ 의 법칙과 $\neg A\lor A$ 가 믿을만한 기초로 받아들이지 않는다. 수학의 이론이라면 누구나 받아들일만한 '모순 배제의 원칙 ,$\neg (\neg A\And A)$ 으로부터 $\neg A\lor A$ 가 파생되어 나올 수 있기 때문에 근본적으로 $\neg \neg A\rightarrow A$ 을 공리로 받아들이지 않게된다. 그것을 빼고는 명제논리에서는 큰 차이가 없다.

직관주의 명제 논리의 법칙들

직관주의적 입장이나 고전주의적 논리의 입장이나 모두 법칙으로 증명되는 것들이 있고 그렇지 않은 것들이 있다. 이것을 더 정확하게 이해하기 위해서는 고전주의와 직관주의의 공리적 체계와 논리 연산에 대한 해석을 점검해야 한다. 공리 체계를 직접적으로 드러내기 전에 우선 $\neg A$ 에 대해 더 생각해보자. 이미 진리표 에서 나왔지만, 상수인 명제로 항상 거짓임을 뜻하는 $\bot$ 를 염두한다면, $\neg A$ 를 보이는 것은 A 이면 거짓(모순)이 나올 수 밖에 없다는 것을 뜻한다. 이 부분은 직관주의나 고전주의나 다를 것이 없다. 그럴 때 다음의 명제들을 이끌어내보자. 물론 고전주의에서는 아래 문장들이 모두 법칙(정리)가 된다.

고전주의에서도 통했던 법칙들

• $(A\rightarrow B)\rightarrow (\neg B\rightarrow \neg A)$

위의 명제는 명제 $A\rightarrow B$ 과 $\neg B$ 으로부터 $\neg A$ 를 유도할 수 있음을 보이면 된다. 이때, $\neg \neg A\rightarrow A$ 의 법칙과 $\neg A\lor A$ 법칙을 쓰지 않아야 한다. $\neg A$ 를 보인다는 것은 A 를 받아들이면 거짓(모순) 이 나올 수 밖에 없다는 것을 보이면 된다. 실제로 그렇다. 왜냐하면 A 를 받아들이면 $A\rightarrow B$ 과 함께 모더스 포넌스에 의해, B 가 나오고, 우리에겐 이미 $\neg B$ 가 있으므로 a모순이 된다.

• $A\rightarrow \neg \neg A$

이것을 보이기 위해서는 A 를 이미 받아들였을 때, $\neg \neg A$ 를 보여야 하고, 이는 다시 말하면 $\neg A$ 이면 모순이 나온다는 것을 보이면 된다. A 가 이미 있을 때 $\neg A$ 를 가정하면 모순이 나온다는 것은 분명하다.

• $\neg \neg \neg A\leftrightarrow \neg A$

이미 앞에서 $(A\rightarrow B)\rightarrow (\neg B\rightarrow \neg A)$ 는 받아들일 수 있다는 것을 보였다. 여기에 B 가 $\neg \neg A$ 라고 하자. 그러면 $(A\rightarrow \neg \neg A)\rightarrow (\neg \neg \neg A\rightarrow \neg A)$ 다. 바로 앞에서 $A\rightarrow \neg \neg A$ 를 보였기 때문에 모더스 포넌스에 따라 $\neg \neg \neg A\leftrightarrow \neg A$ 를 얻는다.

반대 방향은 증명은 $A\rightarrow \neg \neg A$ 에 A 를 $\neg A$ 로 하면 된다.

• $[(A\lor B)\rightarrow C]\leftrightarrow [(A\rightarrow C)\And (B\rightarrow C)]$

여기서 보이지는 않겠다. 고전주의에서 이것을 보일 때도 $\neg \neg A\rightarrow A$ 의 법칙과 $\neg A\lor A$ 법칙을 쓰지 않는다. (믿어달라. 또는 직접 증명해보라.직접 증명해보면 물론 더 낫다.)

• $\neg (A\lor B)\leftrightarrow (\neg A\And \neg B)$

이것을 받아들이기 위해서는 $[(A\lor B)\rightarrow \bot ]\leftrightarrow [(A\rightarrow \bot )\And (B\rightarrow \bot )]$ 를 보이는 것으로 충분하다. 앞의 식에서 C 대신 $\bot$ 를 대입하면 된다.

• $\neg \neg (A\lor \neg A)$

앞의 드 모르강의 법칙에 따라 이 식은 $\neg (\neg A\And \neg \neg A)$ 다. 이것은 '모순 배제의 법칙' 에 따라 $A\And \neg \neg A$ 는 모순이 될 수 밖에 없다.

이것들 뿐만 아니라 고전주의 논리에서 이끌어낼 수 있었던 $\And ,\lor$ 연산에 대해 교환, 결합, 분배 법칙에 모두 $\neg \neg A\rightarrow A$ 의 법칙과 $\neg A\lor A$ 법칙을 쓰지 않는다.

고전주의에서 통했으나 ...

아래의 식들은 고전주의 명제논리에서는 이끌어낼 수 있지만, $\neg \neg A\rightarrow A$ 의 법칙과 $\neg A\lor A$ 법칙이거나 이것들 없이는 증명안되는 법칙들이다. 아래 p, q 는 단순 명제들이라고 하자. 다시 말해 명제식에서 이것을 대신해서 다른 명제를 대입해서 쓸 수 없다.

$\neg \neg p\rightarrow p$

$p\lor \neg p$

$p\lor \neg \neg p$

($\neg q\rightarrow \neg p)\rightarrow (p\rightarrow q)$

만약 대입할 수 있다면 p 대신 $\neg A$ 라는 명제식을 대입하면 위에서 보았듯이 성립한다.

직관주의 명제 논리의 모델

직관주의 명제 논리가 어떤 철학적 입장이고 믿음이라고 하지만 과연 실체가 있을까? 진리표를 부여해서 명제들의 참과 거짓 또는 제 3 의 진리값을 지정할 수 있지만 그것은 여전히 실체가 없다. 고전논리의 경우는 수천년을 이어오면서 형성되고 발전해온 논리체계인데, 직관주의는 고전주의에 대한 비판으로 등장했지만, 과연 그것이 현실 속에서 느껴질만한 무엇일 수 있을까? 여기서도 기하학의 발전 역사를 되새겨볼 필요가 있다. 수천년을 이어온 고전 유클리드 기하학은 중세와 근대로 넘어오면서 inversion geometry 나 projective geomtery 와 같은 '그 이상의' 기하학들을 발전시켜왔다. "주어진 직선을 지나지 않는 한 점을 지나면서 주어진 직선과 평행한 것은 단 하나다" 라는 유클리드 5 번 공준이 증명될 수 있는 것인가 라는 문제는 유클리드 기하학의 오랜 숙제였다. 마침내 러시아의 로바체프스키와 헝가리의 보야이가 5 번 공준을 부정하는 명제를 공리로 받아들인 새로운 기하학을 탄생시켰다. 그러나 당시의 분위기로는 믿기 힘든 사실이었다. 주장은 있지만 느껴지지 않았다. 그러나 벨트라미, 클라인, 푸앙카레 등이 로바체프스키 기하학에 옷을 입혀 눈에 보이도록 모델을 제시하면서 상황은 급변한다.

직관주의 명제 논리의 세계에서도 비슷한 상황이 발생했다. 브라우어의 주장 하였지만, 아직 직관주의 수학도 없었고, 직관주의 논리를 해석할만한 실체가 없었다. 헤이팅을 비롯한 수학자-논리학자들은 직관주의에 기초하여 논리와 수학을 발전시켰다. 마침내 직관주의 논리에를 해석할만한 실체, 모델이 등장하면서 직관주의 논리는 더 납득할만한 것으로 받아들여진다. 브라우어-헤이팅-꼴모고로프의 모델(BHK 모델), 클리니의 실현 가능성(realizability) 같은 모델들이 등장하였고 왕성하게 연구되고 있다. 여기서는 예로, 미국의 크립케가 제시한 모델을 본다. 이 모델은 직관주의 명제의 참과 거짓, 그리고 아직 참과 거짓을 말할 수 없는 것에 대해 매우 단순하고 명확하게 말해준다. 1960년대에야 이것이 등장하였다는 것이 오히려 이상할 지경이다.

크립케 틀 모델

크립케의 틀 모델을 이해하기 위해서는 두 개념이 가장 기초적으로 등장한다.

• $<W,\leq >$ (세계의 집합 ; set of worlds ) : 어떤 '세계'들이 있다고 하자. 그리고 여기서 W 에 있는 세계들은 '더 발전된 세계' 든 ' 그 이후의 세계' 든 어떤 식으로건, 순서를 지울 수 있다고 하자. 그 세계들은 순서를 $\leq$ 로 쓰자. 그렇다면 '세계의 집합'은 순서가 있는 집합 이므로 $<W,\leq >$ 으로 나타내기로 한다.
• $v\Vdash p$ (w 세계에서 p 는 참): 그 세계들 중 어떤 세계에서는 단순 명제들이 참이라는 것을 분명히 밝힐 수 있다. 그 세계 w 는 W 의 원소일 것이다. w 세계에서 단순 명제 p 가 참이면 $w\Vdash p$ 라고 쓰기로 하자. 그리고 W 의 세계들인 w 와 v 에 대해 만약 $w\leq v$ 고 $w\Vdash p$ 라면, $v\Vdash p$ 라 하자. 이것은 충분히 납득할 수 있다. 순서가 더 내용적으로 더 풍요로운 고차원을 뜻할 수도 있고, 시간적으로 그 이후를 나타낼 수도 있다. 그렇다면 저차원의 세계에서 참이라고 하는 알려진 단순 명제는 고차원의 세계에서도 참이라 해보는 것이다. 또는 과거에 참으로 이미 받아들여진 것은 그 이후에도 참으로 계속 받아들인다는 뜻이다.

이제 명제식의 참을 크립케 틀로 정해줄 수 있다.

$w\Vdash A$ 이고 $w\Vdash A$ 라면, $w\Vdash A\And B$

$w\Vdash A$ 거나 $w\Vdash A$ 라면, $w\Vdash A\lor B$

$w\Vdash A$ 인 세계 w 에 대하여, 모든 그 너머 ($w\leq v$)의 세계 v 에서 $v\Vdash B$ 라면, $w\Vdash A\rightarrow B$

어떤 세계 w 너머의 모든 세계 v 에 대하여, 다시 말해 $w\leq v$ 인 v 에서, A 가 참일 수 없다면 $v\Vdash \neg A$

어떤가? 충분히 합리적이라고 할 수 있지 않은가? 물론, 크립케의 세계는 진리는 항상 진리로 남는 축적되는 세계라 이런 철학에 동의하지 않는 사람은 이 모델을 적용하지 않으면 된다. 그러나 분명히 이 철학적 입장은 나름의 합리성을 가지고 있다. 어떤 명제식이 참이라는 것을 분명하게 정의하자.

정의 (명제의 참) : 모든 세계에서 어떤 명제식 A 이 참이면 , 명제 A 는 참이라고 한다.

먼저 가장 기본적인 법칙인 모더스 포넌스에 의해서 유도되는 문장을 보자.

${\frac {A,\ A\rightarrow B}{A}}$

모든 세계에서 $A\rightarrow B$ 와 A 가 참이라면, 모더스 포넌스 규치을 적용해서 새로 얻은 B 도 모든 세계에서 참이라고 말할 수 있을까? 과연 그럴까? 그렇다. $w\Vdash A\rightarrow B$ 의 정의로 부터 당연하다.

공리라고 받아들일만한 명제식을 두개만 보자. 예를들어,

$A\rightarrow (B\rightarrow A)$

A 가 어떤 세계 w 에서 참이었다하자. 그렇다면 A 는 그 너머의 모든 세계에서도 참이다. 따라서 $B\rightarrow A$ 도 그 이후의 세계에서 항상 참이 될 수 밖에 없다.

$(A\And B)\rightarrow A$

$A\And B$ 가 어떤 세계 w 에서 참이었다고 하자. 정의에 따라 w 에서 A 도 B 도 참이다. 따라서 그 이후의 어떤 세계에서도 항상 A 는 참이다.

직관주의 논리세계에서 받아들일 수 없는 예는 참이 아닐까? $p\lor \neg p$ 는 모든 세계에서 참이라고 말할 수 없다. 이런 세계를 생각해보자.

p 가 w 에서 최초로 참이 되었다. 그런데 w 이전의 세계도 있다고 하자. 그렇다면 그 이전의 세계에는 결코 $\neg p$ 가 참일 수 없다. 이 말은 겨우 w 세계에서야 비로서 $p\lor \neg p$ 가 참이 된다. 이 말은 $p\lor \neg p$ 가 모든 세계에서는 참이 아니라는 말이다.

논리 계산과 모델

공리와 모더스 포넌스와 같은 법칙으로부터 믿을만한 명제식들을 얼마든지 이끌어낼 수 있다. 이 명제식들이 우리가 기대했던대로 항상 참이면 좋을 것이다. 그것은 최소한의 조건이다. 우리가 '참'에 대해 충분히 합리적인 모델을 설정했는데 논리적으로 엄격하게 세워가는 명제식들이 참이 아니라면 그것은 우리가 공리라고 할 수 없는 것을 받아들였을 가능성이 높다. 우리의 논리 체계가 그만큼 건강하거나 건전하지 못한 것이다. 따라서 어떤 합리적 모델을 세울 때 반드시 점검해야할 사항이 있다. 다시 말해 증명되는 문장은 항상 참인가? 라는 질문이다. 직관주의 논리 체계에서 증명할 수 있는 모든 명제식들은 크립케 모델에서 참이다.

정리 (크립게 모델에 대한 직관주의 논리 체계의 건전성 ) : 직관주의 논리 체계의 공리와 법칙들로 부터 유도되어 나온 모든 정리들은 항상 크립케 모델에서 참이다.

논리 체계가 처음에 도입한 공리가 모두 참인지 검토하고, 새로운 정리를 이끌어내는 데 쓰이는 모더스 포넌스 같은 규칙들로 나온 문장들이 항상 참이라는 것을 보이면 될 것이다. 하지만 이것으로는 모델의 역할이 충분하지 않다. 과연 (어떤 모델에서) 참인 모든 명제들을 항상 논리체계에서 이끌어 낼 수 있을까? 라는 문제에 답해야 한다. 이것은 (어떤 모델에서) 참인 명제는 항상 증명가능할까? 라는 문제다. 이것의 증명은

정리 (크립게 모델에 대한 직관주의 논리 체계의 완전성 ) : 크립케 모델에서 참인 모든 명제들은 직관주의 논리 체계의 공리와 법칙들로 부터 유도될 수 있다.

완전성 증명은 건전성 증명에 비해 보통 훨씬 복잡하다. 어떤 명제식 $F(p_{1},p_{2},\dots ,p_{n})$ 이 논리체계에서 이끌어질 수 없을 때, $F(p_{1},p_{2},\dots ,p_{n})$ 이 거짓일 수 밖에 없는 단순 명제들 $p_{1},p_{2},\dots ,p_{n}$ 의 진리값이 있다는 것을 보인다.

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia