대각화

모든 집합들이 열거가능한 것은 아니다. 어떤 집합들은 너무 크다. 그 한 예가 양의 정수들의 모든 집합들의 집합이다. 이 집합 (이것을 'P' 라고 부르자) 은 자신의 원소로서 양의 정수들의 유한한 그리고 무한한 모든 집합들을 포함하고 있다. 다시 말해, 공집합 Φ 와 모든 양의 정수들의 집합 P 그리고 이 양 극단 집합들 사이에 있는 모든 집합들을 포함하고 있다.

P^* 가 열거가능하지 않다는 것을 (게오르그 칸토르 (Georg Cantor) 의 방식에 따라) 보이기 위해, 우리는 양의 정수들의 집합들의 어떠한 목록 L 이 주어지더라도, 이 목록에 들어 있지 않은 양의 정수들의 집합  을 항상 찾아낼 수 있는 방법을 제시한다. 만일 당신이 주어진 목록 L 의 첫 자리에다  을 덧붙임으로써 결점을 보완한 목록 L' 을 만들려고 한다면, 똑 같은 방법을 이 보완된 목록 L' 에 적용하여 L' 에 들어 있지 않은 새로운 양의 정수들의 집합  를 찾아낼 수 있다!

그 방법은 다음과 같다. 임의의 양의 정수들의 집합들의 무한 목록,

                                                                                   (L)

이 주어지면, 우리는 이 목록에 대해 집합  을 다음과 같이 정의한다 :

         각 양의 정수 n 에 대하여, 만일 n 이 S_n 의 원소가 아닌 경우
         그리고 오직 그 경우에만 n 은  의 원소이다.                           (*)

'' 이라는 기호법이 나타내듯이, 집합  의 구성은 목록 L 의 구성에 의존해 있으며, 따라서 목록 L 이 따르면 집합  이 다르게 될 수 있다. 그리고 위의 진술 (*) 는 진정으로 어떤 하나의 집합  의 정의로서 손색이 없다. 왜냐하면 임의의 양의 정수 n 이 주어지면, 우리는 n 이 목록 L 속의 n 번째 집합의 원소인지 아닌지를 알 수 있으므로, n 이  의 원소인지 아닌지도 역시 알 수 있기 때문이다. 예를 들어, 만일 S₃ 이 짝수인 양의 정수들의 집합 E 라면, 3 이라는 수는 S₃ 의 원소가 아니며 따라서  의 원소이다.

이 방법으로 산출한 집합  이 주어진 목록 L 속에 결코 들어가 있지 않다는 것을 보이기 위해 귀류법을 사용하자. 곧,  이 목록 L 의 어디엔가, 이를테면 목록의 m 번째에 나타난다고 가정하고 이로부터 모순을 유도해 냄으로써 그러한 가정이 잘못되었음을 밝히자. 가정 : 어떤 양의 정수 m 에 대해,

         .

(따라서 만일 m 이 127 이라면, 우리는 '' 과 'S₁₂₇' 이 동일한 하나의 집합의 두 이름이라고 가정하고 있는 것이다. 다시 말해, 만일 어떤 양의 정수가 목록 L 의 127 번째 집합의 원소인 경우 그리고 오직 그 경우에만 이 양의 정수가  의 원소라고 가정하는 것이다.) 이 가정으로부터 모순을 이끌어 내기 위해서 우리는 정의 (*) 를 특정한 양의 정수 m 에 적용한다. n = m 이라면, 정의 (*) 는 다음과 같이 된다.

         m 이 S_m 의 원소가 아닌 경우 그리고 오직 그 경우에만 m 은  의 원소이다.

S_m 과  은 동일한 한 집합이기 때문에, 이로부터 우리는 아래와 같은 모순을 이끌어 낼 수 있다.

         m 이  의 원소가 아닌 경우 그리고 오직 그 경우에만
         m 은  의 원소이다.

이것은 분명히 자기 모순이기 때문에, 우리의 가정이 잘못된 것임에 틀림없다. 그러므로 어떠한 양의 정수 m 에 대해서도  일 수는 없다. 다시 말해 집합  은 목록 L 속의 어디에서도 찾아볼 수 없다.

따라서 이 방법은 훌륭히 목적을 수행해 낸다. 우리는 양의 정수들의 집합들의 어떠한 목록에 이 방법을 적용하더라도, 그 목록 속에 들어가 있지 않은 어떤 양의 정수들의 집합을 항상 산출할 수 있다. 따라서 어떠한 목록으로도 양의 정수들의 모든 집합들을 열거할 수는 없다. 곧, 양의 정수들의 모든 집합들의 집합인 P^* 는 열거불가능한 집합이다.

이 방법은 흔히 '대각화 방법' (the method of diagonalization) 이라 불리는데, 매우 중요하므로 목록 L 속의 항목들을 더 시각화하여 보여줄 수 있는 약간 다른 각도에서 다시 한 번 고찰하여 보는 것이 좋을 것이다. 우선 목록 L 속의 항목들인 양의 정수들의 집합  등을 다시 한번 살펴보자. 집합  들은 0 이나 1 을 산출값으로 갖는 양의 정수들의 함수  등에 의해 표시될 수 있다. 집합 S_n 과 그것에 대응하는 함수 S_n 이 갖는 관계는 다음과 같다 : 각각의 양의 정수 p 에 대하여,

그러면 목록 L 은 아래의 도표 1 과 같은 0 과 1 들의 무한한 직사각형 종횡 배열로 시각화할 수 있다.

도표 1

이 종횡 배열의 n 번째 행은 함수 s_n 을 표시하며, 따라서 집합 S_n 을 표시한다. 다시 말해 n 번째 행

        

는 0 과 1 의 일련체이며, 이 가운데 p 번째 항목 s_n(p) 는 수 p 가 집합 S_n 의 원소이냐 아니냐에 따라 1 또는 0 의 값을 갖는다. 또한 위의 종횡 배열에서 왼쪽 위에서 오른쪽 아래를 잇는 대각선 위에 있는 아래와 같은 항목들의 배열도 0 과 1 의 일련체이다 :

        

이 대각선 위의 0 과 1 의 일련체 ('대각선 일련체') 가 대각선 위의 양의 정수들의 집합 ('대각선 집합') 을 결정하며, 이 대각선 위의 양의 정수들의 집합은 당연히 목록 L 속의 어디엔가에 들어 있을 수 있다. 다시 말해, 목록 L 의 d 번째 집합 S_d 가 다름 아닌 대각선 위의 양의 정수들의 집합인 그러한 양의 정수 d 가 충분히 있을 수 있다. 만약 그러한 양의 정수 d 가 있다면, 위의 종횡 배열 도표의 d 번째 행에 나타난 0 과 1 의 일련체는 대각선 위에 나타난 일련체와 다음과 같이 항목 항목별로 일치할 것이다. :

대각선 위의 양의 정수들의 집합은 목록 L 의 구체적인 구성 내용에 따라, 그 목록 속에 나타날 수도 있고 나타나지 않을 수도 있다. 우리가 원하는 것은 목록 L 이 어떻게 구성되든지 간에 관계없이 목록 L 속에 항상 나타나지 않는 양의 정수들의 집합이다. 이제 우리는 이러한 집합을 손쉽게 얻을 수 있는 단계에 왔다. 이 집합은 대각선 위에 있는 양의 정수들의 집합에 원소로서 들어가 있지 않은 양의 정수들만을 원소로 하여 구성된 반대각 집합 (adtidiagonal set) 이다. 이에 상응하는 반대각 일련체 (antidiagonal sequence) 는 대각선 위에 있는 일련체 각각의 값을 0 은 1 로 1 은 0 으로 바꿈으로써 얻어진다. 우리는 이러한 변형의 결과를 1 에서 대각선 위에 있는 일련체 각각의 값을 뺌으로써 얻을 수 있으므로 반대각 일련체는 다음과 같이 표기될 수 있다 :

이 반대각 일련체는 위의 도표를 어떠한 행에도 나타나지 않는다. 왜냐하면 만약 이 반대각 일련체가 어디엔가, 예를 들어 m 번째 행에 나타난다고 가정하면, 아래와 같은 모순이 유발되기 때문이다 :

틀림없이 위의 등식들의 m 번째 항목은 성립할 수 없다. (증명 : s_m(m) 은 0 이거나 1 이어야만 한다. 만약 0 이라면 m 번째 등식은 0 = 1 이 된다. 만약 1 이라면, m 번째 등식은 1 = 0 이 된다.) 결국 반대각 일련체는 위의 종횡 배열의 어떠한 행과도 다르며, 따라서 반대각 집합은 목록 L 속의 어떠한 집합과도 다르다. 이것은 새로운 사실이 아니다. 왜냐하면 이 반대각 집합이 바로 앞서 정의한 집합  이기 때문이다. 우리는 지금까지 단순히 위의 도표 1 의 도움을 얻어  이 목록 L 속의 어디에도 나탄지 않는다는 사실을 다시 한 번 반복해서 증명했을 뿐이다.

물론 무한 집합의 원소들이 하나의 무한 목록 속에 '배열될 수 있다' 고 말하는 것은 다소 기이하다. 누구에 의해서? 분명히 어떠한 인간에 의해서도 아니다. 왜냐하면 시간이나 종이가 그렇게 많은 사람은 아무도 없기 때문이다. 그리고 비슷한 제약들이 기계들에도 적용된다. 실제로, 어떤 집합을 열거가능하다고 부르는 것은 단순히 그 집합이 양의 정수들의 어떤 함수의 (산출값) 범위라고 말하는 것일 뿐이다. 따라서, 짝수인 양의 정수들의 집합 E 는 E 를 자신의 (산출값) 범위로 하는 양의 정수들의 함수가, 예를 들어 각 양의 정수 n 에 대해 f(n) = 2n 인 함수 f 가 존재하므로 ㅇ열거가능하다. 그러한 함수는 모두 어떤 초인간적인 열거자가 집합의 원소들을 단일한 목록 속에 배열하기 위해서 따라야 할 프로그램으로 생각할 수 있다. 더 명료히 말해, 그 프로그램 (지시 사항들의 집합) 은 다음과 같다 :

         1 부터 세기 시작하여 결코 중단하지 말라. 당신이 각 수 n 에 다다를 때마다, f(n) 의 이름을 당신의 목록 속에 적어 넣어라. (f(n) 이 정의되지 않았을 때, n 번째 항목은 빈 칸으로 남겨 놓아라.)

그러나 이러한 목록이나 초인간적 열거자를 끌어들일 필요가 없다. 열거가능성에 관해 말할 필요가 있는 것은 모두 다 함수 자체를 통해 말할 수 있기 때문이다. 예를 들어, P^* 열거가능하지 않다고 말하는 것은 단순히 P^* 를 자신의 (산출값) 범위로 갖는 양의 정수들의 함수가 존재하지 않는다는 것을 말할 뿐이다.

물론 목록이나 초인간적 열거자와 같은 생생한 얘기는 상상에 도움이 될 것이다. 그러나 그러한 용어들로 표현한 열거가능성과 대각화 일론은 수학적 신학 (mathematical theology) 속에 나오는 한 장처럼 보일 것이다. 어쨌든 전능한 신의 현존을 믿는 사람들의 감정을 혹시라도 상하게 하는 것을 막기 위해, 우리는 전체 얘기의 배경을 고대 그리스로 옮겨 놓을 수 있을 것이다. 칸토르는 제우스 (Zeus) 신이 아무리 빨리, 아무리 오랫동안 (무한히 오랫동안인 경우에 조차도) 작업을 하여도, 제우스 신조차도 열거할 수 없는 집합들이 존재한다는 것을 증명하였다.

만약 어떤 집합이 열거가능하다면, 제우스는 무한한 목록을 시간이 감에 따라 더욱 빨리 씀으로써 1 초만에 그 집합을 열거할 수 있다. 그는 목록 속의 첫 항목을 쓰는 데 1/2 초를 소비하고, 두번째 항목을 쓰는 데 1/4 초를 소비하고, 세번째 항목을 쓰는 데 1/8 초를 소비하고, 그리고 일반적으로, 각 항목을 쓰는 데 그가 바로 앞 항목을 쓰는 데 소비했던 시간의 반을 소비한다. 1 초 안의 어떠한 시점에서도 그는 전체 목록을 완성하지 못한다. 그러나 1 초가 지나는 순간, 그 목록은 완성된다! 눈금 간격이 1/16 초인 시간 자를 이용하면 제우스의 열거 과정은 도표 2 와 같이 표시할 수 있다.

도표 2

(예를 들어, 십진법의 표기법으로 된 모든 양의 정수들의) 무한 목록을 얘기하는 것은 제우스와 같은 열거자가 위와 같이 시간이 감에 따라 더욱 빨리 쓰거나, 또는 그 목록을 완성하는 데 (아마도, 매초마다 한 항목씩을 써넣어) 무한한 시간을 모두 사용하는 것을 얘기하는 것이다. 진정으로 제우스는 그가 하려고만 한다면 단 일초만에 무한 목록들의 무한 일련체를 써내는 자신의 임무도 또한 완수할 수 있을 것이다. 단순히 첫 1/2 초를 첫번째 무한 목록을 쓰는 일에 할당하고 (이 첫번재 무한 목록의 첫번째 항목에 1/4 초를 할당하고, 두번째 항목에 1/8 초를 할당하고, 등), 그 다음 1/4 초를 두번째 무한 목록을 쓰는 일에 할당하고 (이 두번째 무한 목록의 첫번째 항목에 1/8 초를 할당하고, 두번재 항목에 1/16 초를 할당하고, 등), 그리고 일반적으로 제우스는 각 무한 목록을 쓰는 데 자신이 바로 앞 무한 목록을 쓰는 데 할당했던 시간의 반을 할당한다. 이렇게 함으로써 제우스는 단 1 초만에 모든 목록들 속에 있는 모든 항목들을 순서대로 써낸다. 그러나 그 결과는 우리가 받아들이고 있는 의미의 무한 목록으로 간주할 수 없다. 우리가 받아들일 수 있는 목록 속에서는 각 항목이 어떤 특정한 유한 번째 자리에 나와야만 한다.

제우스는 무한히 많은 무한 목록들을 열거할 때, 우리가 용어 '목록' 을 사용하는 바와 같이 한 항목 다음에 또 한 항목을 씀으로써 목록을 작성하지 않았다. 그러나 그는 우리가 1 장에서 양의 유리수들을 열거하기 위해 사용하였던 것과 같은 방식을 사용함으로써 모든 목록들 속에 들어 있는 항목들을 빠짐없이 열거하고 있는 진정한 목록을 작성할 수 있다. 그는 각 양의 정수 n 에 대해, n 번째 행이 바로 자신이 열거하려고 하는 n 번째 무한 목록인 그러한 무한한 직사각형의 종횡 배열을 상상하기만 하면 된다. 그리고 제우스는 자신이 열거하고자 하는 원래 목록들의 각 목록 속에 들어 있는 모든 항목이 처음부터 세어 어떤 특정한 유한 번째에 나타나는 단일한 목록을 얻기 위해 도표 3 에 표시된 바와 같은 두 순서 가운데 한 순서대로 다양한 목록들로부터 다양한 항목들을 끄집어내어 써 내려가면 된다.

도표 3

그러나 칸토르의 대각선 논변은 양의 정수들의 모든 집합들을 단일한 무한 목록 속에 배열할 수 있는 어떠한 방식도 신에게조차 주어질 수 없다는 것을 보여준다. 그러한 목록은 둥근 사각형이 불가능한 것과 마찬가지로 불가능하다. 다시 말해, 양의 정수들의 모든 집합들을 열거하는 것은 둥근 사각형을 그리는 것과 마찬가지로 제우스에게 조차도 절대적으로 불가능하다.

연습문제

1. 집합  의 목록 L 이 주어졌을 때 집합 D(L) 을 다음과 같이 정의하라.

    각 양의 정수 n 에 대하여 n 이 D(L) 에 있을 경우 그리고 오직 그 경우에만 n 은 S_n 에 있다.

   연습문제 5 의 풀이에서 주어졌던 양의 정수들의 유한한 집합들의 열거를 L 이라고 가정하자. (a) D(L) 은 무엇인가? (b) D(L) 은 L 에 있는가? (c)  은 무엇인가?

2. 대각선 논법 (도표 1 을 보라) 을 응용하여 0 부터 1 사이에 있는 실수들의 집합이 열거가능하지 않다는 것을 증명하라. 힌트 : 그런 각각을 소수점 이하에 0 부터 9 까지의 숫자들이 무한히 뒤따르도록 십진법으로 표시할 수 있는 방법은 한 가지 또는 두 가지가 있다. 예를 들면, 0.5 = 0.5000... = 0.4999..., 또 0.123 = 0.123000... = 0.122999... 이다. 그러나 소수점 이하에 0 이나 9 가 한 번도 나오지 않으면 (1 부터 8 까지의 숫자가 무한히 나열된 것으로서) 십진법 표기는 유일��.

3. 양의 정수들만을 산출값으로 갖는 양의 정수들의 모든 전체함수들과 부분함수들의 집합은 열거가능하지 않다는 것을 대각선 논법에 의해 증명하라.

4. 열거가능하게 무한한 알파벳  로부터 만든 글자들의 임의의 유한한 나열을 낱말이라고 정의하자. 다음과 같은 각 집합이 열거가능함을 증명하여라 :

    (a) 두 글자짜리 낱말들,
(b) 세 글자짜리 낱말들,
(c) 임의의 그러나 고정된 n 에 대해서, n 글자짜리 낱말들,
(d) 길이에 상관없이 (유한한) 모든 낱말들.

풀이

1. L 의 연속적인 항목들은 , 등등이다. 아랫첨자 n 은 S_n 의 가장 큰 원소보다도 훨씬 더 빨리 커지기 때문에 (가장 큰 원소라도 양의 기호와 음의 기호로 된 해당 부호의 길이보다 더 크지 않다) n = 1 인 경우에만 n 이 S_n 에 속한다. 그러면
(a) D(L) = {1}
(b) D(L) 은 L 에 있다. D(L) = S₁ 과 D(L) = S₄ 가 그 보기이다.
(c)  = {2, 3, 4, ...}. 이 집합은 무한하고 그래서 대각선 논법에 의해 우리가 알고 있듯이 L 에 있지 않다.

2. 각 항목이 소수점 이하에 0 부터 9 까지의 부호가 끝없이 뒤따르는 숫자로 표시된 임의의 목록을 L 이라고 하자. 특히 n 번째 항목의 연속적인 숫자를  이라고 가정하면 L 의 항목들은 도표 1 의 행들이 된다 (이제 도표의 각 위치에는 '0' 부터 '9' 까지의 숫자 가운데 아무거나 하나를 표시할 수 있다). D 가 0 부터 9 까지의 열 개의 숫자 가운데 하나일 때

    

    라고 정의하자. (이 정의의 본질적인 특징은 0 ≠ d' ≠ d 라는 것이다.) 이제  의 연속적인 숫자들을  라고 하자. 이것은 도표 1 에 있는 어떠한  이 되고 이것은 연산 ' 의 정의에 의해 불가능하기 때문이다. 그렇다면  이 0 이나 9 를 포함하지 않기 때문에 그것이 표시하는 수는 L 의 어떠한 항목에 의해서도 표시되지 않는다. 따라서 0 부터 1 사이에 속한 실수들의 어떠한 목록 L 도 그 원소들을 다 열거할 수가 없다.

3. L = f₁, f₂, .... 이 그런 함수들을 열거한 것이라고 하자. 반대가 함수  를 다음과 같이 정의하라 :

    그러면 u 는 양의 정수만을 산출값으로 갖는 양의 정수들의 잘 정의된 전체함수이다. 그러나 u 는 L 에 있을 수 없다. 그 까닭은 이렇다. 만약 (가령) u = f_m 이면 정의에 따라

    이 된다. 그러면 f_m 이 투입값 m 에 산출값을 부여하든지 않든지 간에 모순이 생긴다. 즉 f_m(m) 이 정의되지 않으면 그것은 정의되고 (그래서 1 과 같고), 반면에 정의가 되어 (가령) n 과 같다면 n = n + 1 이 된다.

4. 직접적인 풀이는 양의 유리수들을 열거하는 데 썼던 기법과 같은 기법을 (반복해서) 사용한다.
(a) 도표 4(a) 에서처럼 모든 두 글자짜리 낱말들을 직사각형 꼴로 배열한 다음, 단일한 목록을 얻기 위해 그 낱말들을 방식대로 하나씩 짚어 나가라. 이를테면 도표 3(b) 에서처럼 삼각형 형태로 짚어 나가면,

의 단일한 목록이 얻어진다.

도표 4

    (b) 세 글자짜리 낱말들은 두 글자짜리 낱말들 다음에 한 글자짜리 낱말을 써서 얻을 수 있다는 것에 주목하라. 도표 4(b) 와 같은 꼴로 만들어서 삼각형 형태로 하나씩 짚어 나가면

    와 같은 목록을 얻게 된다.

    (c) 네 글자짜리 낱말들의 목록을 만들기 위해서는 세 글자짜리 낱말들을 맨 윗줄에 놓고 한 글자짜리 낱말들을 맨 왼쪽에 놓은 종횡 배열을 만들고 각 낱말들을 하나씩 짚어 나가면 된다. 등등. 그 과정을 충분히 많이 반복하면 어떠한 특정 n 에 대해서도 n 글자짜리 낱말들의 목록을 얻을 수 있다.

    (d) 임의의 유한한 길이를 가진 모든 낱말들의 목록을 만들기 위해서는 첫번째 행이 한 글자짜리 낱말들의 목록인 a₁, a₂, ... 이고, 두번째 행이 두 글자짜리 낱말들의 목록인 (a) 이고, 세번째 행이 세 글자짜리 낱말들의 목록인 (b) 이고, 등등인 종횡 배열을 만들어 그 배열 속의 낱말들을 하나씩 짚어 나가면 된다.

    그러나 알파벳 a₁, a₂, ...  으로 된 임의의 유한한 길이를 가진 모든 낱말들의 빈틈이 있는 목록을 더욱 간단하고 직접적으로 얻을 수 있는 방법이 있다. 그런 낱말들 중 임의의 것이 목록에서 차지하는 위치를 결정하기 위해서 그 목록에서 a₁ 이 나올 때 마다 '12' 로 바꿔 쓰고, a₂ 가 나올 때마다 '122' 로 바꿔 쓰고, 일반적으로 a_n 이 나올 때마다 하나의 '1' 과 n 개의 '2' 가 연속해서 써진 숫자로 바꿔 써라. 그 결과로 생긴 숫자들을 십진법으로 읽어보면 그것이 목록에서 그 낱말이 차지하는 위치가 된다. (그렇다면 그 목록은 열한 개의 빈 칸으로 시작한다. 첫번째 항목은 열두번째 위치에 있는 한 글자짜리 낱말 a₁ 이다. 그 다음 항목은 위치가 122 번째인 낱말 a₂ 이다. 세번째 항목은 위치가 1212 번째인 낱말 a₁a₁ 이다. 네번째 항목은 위치가 1222 번째인 낱말 a₃ 이다.) 임의의 고정된 n 에 대해서 n 글자짜리 낱말들의 목록은 비슷하게 (그리고 더 간단하게) 얻을 수 있다.