[특집편] 유명한 패러독스들 - The important paradoxes
독서경시대회도 끝나고, 2차시험도 끝났지만 시험공부 한다고 다른 책을 전혀 접하지 못한 탓에 이번에는 리뷰 대신 평소 정리해두고 싶었던 내용을 기록하고자 한다. 여기서는 학문적으로나 역사적으로 주목할만한 다양한 논리적 역설들을 살펴보고자 한다. 실질적으로 이런 역설들에 의해 논리학은 무궁무진한 발전을 이루었다고 봐도 과언이 아니다. 또한 아주 흥미로우면서 어렵지 않은 내용들이므로 심심풀이 땅콩으로 유식한 척 하기엔 딱 좋다. (물론, 내가 그런걸 즐긴다는 건 아니다)
1. 러셀의 패러독스 (1902)
아마도 논리학을 접하지 않은 일반인조차도 이 러셀의 패러독스나 이것의 변형된 버젼을 어디선가 접해봤을 것이다.
러셀의 패러독스의 형식적 버젼을 쓰기 전에 이해하기 쉽도록 예를 들어보자.
안암동에 사는 한 이발사가 있다. 그는 '자신이 직접 이발을 하지 않는 모든 사람'을 이발하는 사람이라고 한다. 그러면 그는 자기 자신을 직접 이발하는 사람인가? --- (*)
만약 그가 자기 자신을 직접 이발한다고 가정하면, 그는 직접 이발을 하지 않는 사람에 해당되므로 모순이 발생하고, 그가 자기 자신을 직접 이발하지 않는다고 가정하면 그는 그 자신을 이발해야만 하는 모순이 생긴다.
단순해 보이는 위의 (*)문장은 논리적으로 이해될 수 없는 결론에 도달하고 있다. 위의 문장을 수학의 집합을 이용하여 표현하면 다음과 같이 러셀의 패러독스 형식적 버젼을 얻는다.
R이란 집합이 위와 같이 자기 자신을 포함하지 않는 모든 집합을 포함하는 집합이라고 가정하면 R은 자기자신에 포함되면서 동시에 포함되지 않는 모순이 발생한다. 다시 말하면, R이 자기 자신에 포함된다고 가정하면, R의 성질에 의해 R은 자기자신에 포함되지 않아야만 하고, R이 자기자신에 포함되지 않는다고 가정하면 다시 R의 성질에 의해 R은 자기자신에 포함되는 집합이 된다.
이 러셀의 패러독스는 수학자 버드런트 러셀이 집합론 연구 중 발견한 논리적 역설로, 이로 인해 20세기 초에 대두된 소위 '수리기초론' -- 수학을 견고한 논리(그 당시, 집합론) 위에 다시 세우려는 일련의 시도들 -- 은 시작되기도 전부터 풍비박산이 날 지경이 되었다.
그러면 러셀의 패러독스가 나오는 원인은 무엇일까? 그것을 극복하는 방법이 있을까? 만약 많은 수학자와 논리학자들이 러셀의 패러독스를 극복하지 않았다면 무슨 근거로 우리는 현대 수학을 믿음직스럽다고 할 수 있었을까? 다행히도, 매우 단순한 방법으로 러셀의 패러독스를 극복(여기서는, 피해간다는 표현이 맞을듯 싶기도 하다)하는데, 그것은 위의 러셀의 패러독스의 형식적 버젼에서 등장하는 R과 같은 집합을 집합으로 인정하지 않음으로서 러셀의 패러독스 및 그 비스무레한 논의들(자기 자신을 언급하는 일련의 패러독스들)을 집합론으로부터 배제시키는 것이었다. 우리의 직관은 "모여있는 모든 것"을 뭐든지 집합으로써 인식할 수 있지만, 이것이 현실화되었을 때 그 집합의 존재를 관철시키는 것은 그리 녹록치 않다는 것이다. 여기서부터 이미 직관과 논리의 gap은 다소 구체화되고 있었다. 그리고 이 역설은 논리에서 문제가 되는 가장 큰 요인은 바로 '자기 자신에 대한 언급' 임을 암시하고 있었다.
2. 칸토어의 패러독스 (1899)
주어진 두 집합이 A = {1,2,3,4} , B = {5,6,7,8}과 같이 유한집합일 때, 우리는 A와 B의 원소의 개수를 셈으로써 A와 B가 같은 개수의 원소를 갖고 그러므로 두 집합의 크기가 같다는 것을 확인한다. 그러면 주어진 집합들이 무한인 경우는 어떻게 두 집합의 크기를 비교할 수 있을까? 단지 '둘다 무한이니까 어떤 것이 더 많은 원소를 가지는지는 알 수 없다' 고 말할 수도 있지만, 우리의 직관은 종종 그 이상을 암시한다. 예를 들면, 모든 자연수의 집합을 N이라고 하고 모든 유리수의 집합을 Q라고 하면, N은 Q에 속하고, N에 있지 않은 수많은 원소들(이를테면, 분수꼴의 수들)이 Q에 속해있기 때문에 Q의 집합의 크기는 N보다 크다는 걸 추론할 수 있다. 그러나 Q와 N은 모두 무한집합이라는 것을 주목하자. 우리는 방금 다음과 같은 명제를 참이라 생각하고 사용했다.
"A가 B에 속하면 B의 크기는 A와 같거나 더 크다."
이 명제는 확실히 A와 B가 유한집합일 때는 맞는 이야기이다. 원소의 개수를 일일이 세면 되기 때문이다. 그러나 이 명제가 무한집합에 대해서도 맞는지는 알 수 없다. 집합의 원소가 무한히 많기 때문이다. 19세기 수학자 칸토어가 세운 업적 중 가장 위대하게 평가받고 있는 것은 이러한 무한집합의 크기를 비교하는 방법론을 제시했던 일이다. 그 방법론은 다음과 같다.
처음에 보였던 예시로 돌아가보자. A = {1,2,3,4} , B = {5,6,7,8} 로 주어져 있을 때, 두 집합의 크기를 비교하기 위해서는 앞서 보았듯이 두 집합의 원소의 개수를 세볼 수도 있겠지만, 또 다른 방법이 있다. 두 집합의 원소를 둘씩 짝지어보자. 예를들어, 1과 5, 2와 6, 3과 7, 4와 8 을 서로 짝지으면 A와 B의 원소는 모두 빠짐없이 짝지어지게 된다. 한편 A = {1,2,3,4,5} , B = {5,6,7,8}로 주어져있고 방금과 같이 짝을 짓는다고 생각하면, A의 원소인 5는 B의 어떤것과도 짝지어지지 못하기 때문에, A의 크기가 B보다 더 크다고 말할 수 있다. 이 단순해보이는 방법론이 무한집합의 크기를 비교하는데 이용된다.
모든 자연수의 집합을 N이라 하고 모든 짝수 집합을 Ne 라고 하자. 즉, N = {1,2,3,4, ...} 이고 Ne = {2,4,6,8,...}이다. 직관적으로 볼 때, N의 크기는 Ne보다 클 것 같다. 그러나 우리는 다음과 같이 N과 Ne의 원소를 남김없이 짝지을 수 있다.
N Ne
1 - > 2
2 - > 4
3 - > 6
4 - > 8
.... - > ....
그런데 왜 이렇게 짝을 지으면 서로간에 남는 원소가 없다고 확정지을 수 있을까? 그것은 우리가 짝을 짓는 원소들 사이에 존재하는 규칙성 때문이다. N의 주어진 원소 n에 대하여 2n 에 해당하는 원소가 항상 Ne에 존재하기 때문이다. 이러한 짝짓기를 다음과 같이 함수를 포함한 문장으로 표현할 수 있겠다.
"N과 Ne 사이에는 일대일대응함수인 f가 존재한다."
이에 따라 칸토어는 집합의 상등(相等)(크기가 같음)을 다음과 같이 정의한다.
"A와 B가 상등일 필요충분조건은 A와 B사이에 일대일 대응인 함수 f가 존재하는 것이다."
집합의 상등을 위와같이 정의하는 동시에 아주 신기한 일들이 발생하는데, 방금 예시에서 보았듯이 짝수 전체의 집합인 Ne 에 비해 N은 직관적으로 볼 때 두배나 많은 원소를 가지고 있음에도 불구하고 두 집합은 서로 크기가 같다. 심지어 N과 Q사이에도 적절한 일대일 대응함수가 존재함을 증명할 수 있기 때문에(자세한 증명은 생략한다) N과 Q의 크기도 서로 같다. 이쯤 되면 이런 생각이 들 수 있다. '무한집합끼리는 모두 다 크기가 같은 것 아냐?'
그러나 칸토어의 대각정리(Cantor's Diagonal Theorem)에 의해 실수 집합 R은 자연수의 집합 N보다 크기가 더 크다. 칸토어의 대각정리는 시간이 허락하면 증명을 적어보기로 하겠다. 왜냐하면 증명의 내용은 중학생이 이해할 수 있을정도로 쉬운데다가 그 아이디어가 독창적이며 수학적으로 매우 중요한 방법론 중 하나이기 때문이다.
이제 칸토어의 패러독스를 설명할 차례다. 칸토어는 더 나아가 다음과 같은 사실을 밝혔다.
"임의의 집합 A에 대하여 그 멱집합(Power set) P(A)의 크기가 더 크다." --- (**)
멱집합이란 주어진 집합의 모든 부분집합을 포함하고 있는 집합이다. 예를들면, A = {1,2,3} 이라고 주어졌을 때 P(A) = { ø, {1} , {2} , {3} , {1,2} , {2,3} , {1,3} , {1,2,3} } 이다. 위의 명제 역시 당연히 유한집합에서는 성립한다는 걸 눈으로 확인할 수 있다. 그러나 위의 명제가 무한집합에 대해서 성립하는지는 증명이 필요하다. 어쨌든, 칸토어는 어렵지 않게 위의 사실을 증명할 수 있었는데, 문제는 그 다음이었다.
"모든 집합의 집합" 을 U라고 하자. 즉, U에는 모든 집합이 다 포함되어 있다. (**)에 의해 (1)그것의 멱집합인 P(U)는 위의 명제에 따라 자기 자신인 U보다 크기가 크다. (2)한편 U는 모든 집합의 집합이기 때문에 P(U)는 U에 속하게 된다.
또한 임의의 집합 A와 B에 대하여 A가 B에 속하면 이 둘이 무한집합이더라도 A의 크기가 B의 크기보다 클 수는 없다는 것이 알려져있다. 그러므로 U의 크기는 P(U)보다 크거나 같다. 정리하면,
(1) [U의 크기] < [P(U)의 크기]
(2) [U의 크기] >= [P(U)의 크기]
가 된다. 서로 모순되는 결론이 동시에 도출되고 마는 것이다. 이를 칸토어의 패러독스 라고 한다.
그러면 이 패러독스는 어떻게 해결되었을까? 논리학자들은 골치아픈 문제들을 다루면서도 골치를 썩는 것을 매우 싫어하기 때문에 이번에도 역시 이 문제를 정면돌파하기 보다는 이러한 문제와 만나지 않도록 우회하는 것을 선택한다. 즉, '모든 집합의 집합' 인 U와 같은 집합을 집합으로 인정하지 않음으로써 그런 집합을 논리적으로 다룰 일이 없도록 한 것이었다.
이러한 패러독스들의 첫 종착지는 대략 "괴델의 불완전성 정리" 라고 볼 수 있다. (계속...)
