박현천님이 구조론을 응용하여 증명에 성공한 수학의 4색문제

지도를 색으로 칠하여 구분할 때 서로 인접한 두 나라는 다른 색으로 칠하는 것이 보통이다. 그런데 ［그림］과 같은 경우로 알 수 있는 바와 같이 최소한 4색이 필요하다. 한편, 경험에 의하면 4색으로 칠하여 구분할 수 없는 지도는 아직 발견되지 않았다.   따라서, 다음 문제가 남게 된다. 즉, ‘어떠한 지도라도 4색을 써서 칠하여 구분할 수 있다는 것을 증명하여라’는 문제이다. 이것을 4색문제라고 한다. 단, 인접한 나라라고 하는 것은 어떤 길이의 경계에 따라 인접하고 있는 것을 말하고, 점에서 접해 있을 경우를 말하지 않는 것으로 한다.

이 문제는 1840년 A.F.뫼비우스 (1790∼1868), 1850년 A.드모르간(1806∼1871), 1878년 A.케일리(1821∼1895)에 의하여 제출되어 수학상의 난문제로 유명해졌다. 1890년 P.J.히우드가 ‘어떠한 지도라도 5색으로 칠하면 구분할 수 있다’는 것을 증명했다. 그러나 4색문제는 여전히 난문제로 남아 있었다. 즉, 나라의 수가 38 이하이면 어떠한 지도라도 4색으로 칠하여 구분할 수 있다는 것은 그 후에 증명되었으나, 일반적인 경우의 4색문제의 해결만은 방대한 계산을 필요로 하는 것으로 생각되어 왔다. 그러나 이 4색문제는 미국의 일리노이대학의 K.아펠과 W.하켄 양 교수에 의하여 1976년 8월 해결되었다.   그들의 방법은 먼저 지도를 그 특징에 따라 약 1,879개의 경우로 분류하고, 그 각각의 경우가 4색으로 칠하여 구분할 수 있다는 것을 전자계산기를 써서 수학적 귀납법으로서 증명을 완성하였다. 그들은 그러기 위해서 전자계산기를 1,200시간 가동시켜야만 했다고 한다. [네이버 검색]

페르마의 마지막 정리와 맞먹는 수준의 문제라고 한다. 지난 수백년간 어떤 수학자도 제대로 풀지 못했다는 문제이다. 구조론으로 간단히 해결된다.

예의 일리노이대학에서 컴퓨터를 사용한 방법은 편법일 뿐 아니라 귀납적 증명이므로 이는 안쳐주는 거다. 연역적으로 증명해야 한다. 구조론으로만이 가능하다.

4색문제는 국가 간의 경계를 나타낼 뿐 국가에 속하지 않는 바다나 공중을 나타내지 않고 있다. 그 부분까지 나타낸다면 최소 5색이 필요하다.

구조론에 따르면 물리공간은 점, 선, 면(각), 입체, 공간의 다섯가지 유형의 중복성을 가지고 있다. 모든 중복을 제거했을 대 끝까지 남는 것은 이 다섯 뿐이다.

점(국가에 속하지 않은 바다나 공중 등의 중복성을 제거한다.)

선(앞과 뒤의 반복적인 전개에서 중복을 제거한다.)

면(각에서 성립하는 위와 아래의 전개에서 중복을 제거한다.)

입체(입체에서 성립하는 겉과 속의 전개에서 중복을 제거한다.)

공간(입체의 전개방향을 뒤집었을 때 성립하는 중앙과 주변의 전개에서 중복을 제거한다.)

물리공간이 중복을 제거했을 때 몇가지 필수적인 경계를 가지는가 하는 문제이다. 여기서 점은 어느 국가에도 속하지 않는 바다나 공중과의 경계를 나타내므로 제외하고 국가들 간의 경계를 나타낼 때는 4가지 중복되지 않는 경계로 나타낼 수 있다.

선, 면, 입체, 공간의 대표들 즉  앞, 위, 밖, 주변만 나타내면 된다.

구조론은 연역의 방법으로 위에서 아래로, 밖에서 안으로 범위를 좁혀들어가면서 포위하여 들어가므로 모든 중복이 제거되는 것이다. 그러므로 4가지 색 만으로 모든 국가의 경계를 나타낼 수 있다.

점, 선, 면, 입체, 공간에 대한 구조론적 엄밀한 정의의 방법을 통하여 연역적 증명이 가능하다. 이를 플래시 만화처럼 차례로 보여주는 방법을 사용하여 더 쉬운 이해를 구할 수도 있다.

이를 수학적으로 증명하고 각각이 무엇을 의미하는지 정확한 분류를 해주는 일이 중요하다. 이는 수학영역 안에서 새로운 학문 하나를 만들어내는 일이 된다.

4색 문제란 무엇인가? [검색으로 발췌]

그것은 경계가 단순한 영역을 갖는 모든 평면지도는,

길이가 0이 아닌 경계를 공유하는 두 영역을 같은 색으로 칠하지 않는다면,

4색으로 칠할 수 있다는 것이다.

이 정리는 컴퓨터의 도움으로 1976년에 Appel, Haken에 의해 최초로 증명이 되었다.

1879년 켐프(A. Kempe)는 수학적 귀납법과,

네 가지 형태의 기본 지도에 대해 "사슬 논법 (chain argument)"이라고

불리는 교묘한 논법을 사용하여 색칠을 함으로, 4색문제를 증명했다고 선언했다.

하지만, 약 10여년 후, 그 증명에 오류가 있음이 밝혀졌다.

1969년, 헤슈(Heesch)는 다른 종류의 제안을 하였다.

만일 4색 문제에 반례가 있다면, 자신은 4색으로 채색이 불가능하지만,

그 지도의 모든 부분지도는 4색으로 칠할 수 있는 '최소반례'가 있을 것이다.

먼저 이들은, 이러한 최소반례들은 특정한 종류의 기본꼴의 지도를

반드시 포함해야 한다는 것을 증명하였다.

이리하여, 켐프의 증명에 사용되었던 네개의 지도를 대신할

약 8900개의 지도를 만들고, 이들을 4색으로 색칠하면 충분하다는 것을 보였다.

하지만, 지도가 너무 많아서 사람이 모두 칠해볼 수는 없었다.

1976년, 아펠(Appel)과 하켄(Haken)은, 직관력과 시행 착오 끝에,

8900개의 그림을 약 2000개로 줄이는데 성공하였고,

코흐(Koch)의 도움으로 작성한 프로그램을 가지고,

일리노이 대학의 컴퓨터 여러 대를 합계 1200시간이나 돌려 일일이 검사한 끝에

마침내 4색문제를 증명했습니다.

원리적으로만 본다면, 컴퓨터의 증명을 사람이 할 수는 있다.

하지만, 시간이 너무 많이 걸려서 실제로 이 증명을 검증할 수가 없었다.

따라서, 컴퓨터를 써서 증명한, 이 4색문제의 증명을

수학적인 증명으로 받아들일 것인가에 대한 논란이 일어났다.

그런데, 최근 Robertson, Sanders, Seymour, Thomas는 상당한 단순화를 통해,

Appel과 Haken의 원래 증명의 방법은 이용하면서,

기본꼴의 개수를 상당히 줄임으로써, 이 문제에 대하여 상당히 진전을 이루었다.