1, 2, 3, 4, ...

그리고 짝수인 양의 정수들의 집합 E 는 다음과 같은 목록에 의해 열거될 수 있다 :

         2, 4, 5, 8, ...

물론 이 목록들 속의 항목들은 정수들이 아니라 정수들의 이름들이다. 어떤 집합의 원소들의 목록을 만들 때, 우리는 구체적 사물들이 아니라 그 사물들의 이름들을 사용한다. (예를 들어 미국 상원의원들의 집합의 구성원들의 목록을 만들 때, 우리는 미국 상원의원들을 일렬로 세우지 않고 그들의 이름들을 알파벳순으로 목록 속에 배열할 것이다.)

관례상, 우리는 원소를 갖지 않는 공집합 Φ 도 열거가능한 집합으로 간주한다. (공집합은 오로지 하나 있다. 공집합이란 용어는 빈 용기들을 연상시켜 여러 개 있을 수 있다는 오해의 소지를 안고 있다. 그러나 집합들은 내용물에 관한 것이라고 생각해야 더 적절하며, 모든 빈 용기들은 동일한 내용물, 즉 빈 내용물을 가지고 있다고 생각해야 한다.)

어떤 집합을 열거하고 있는 목록은 유한할 수도 끝이 없을 수도 있다. 이 중에서 원소들을 열거할 수 있는 무한 집합을 열거가능한 무한 (denumerable 또는 enumerably infinite) 집합이라 부르자. 이제 어떤 것이 무한 목록으로 간주될 수 있으며, 어떤 것이 간주될 수 없는지 명확히 하자. 양의 정수들은 위에서 본 바와 같이 하나의 무한 목록 속에 배열될 수 있다. 그러나 아래와 같은 것은 양의 정수들의 목록으로 받아들여질 수 없다 :

1, 3, 5, 7, ..., 2, 4, 6, 8, ...

여기서는 모든 홀수인 양의 정수들이 먼저 배열된 후, 모든 짝수인 양의 정수들이 배열되었다. 이것은 만족스럽지 못하다. 어떤 목록이 받아들여질 수 있기 위해서는 각 원소들이 조만간 목록 속에 어떤 유한한 n 번째 항목으로서 나타나야만 한다. 그러나 위와 같은 부적절한 배열에서는 짝수인 양의 정수들은 어느 것도 그러한 방식으로 표시되고 있지 않다. 그것들은 말하자면 ∞+1번째, ∞+2번째 등등의 항목들로서 나타나고 있다.

이 점을 아주 분명하게 하기 위해서, 우리는 집합의 열거를 단순히 목록의 작성으로 정의하지 않고 그 집합의 각 원소가 양의 정수들 1, 2, 3, ... 중의 하나와 대응되는 배열로서 정의할 수도 있다. 사실 목록이 바로 그러한 배열이다. 목록에서 첫번째 항목에 의해 지칭되는 것은 양의 정수 1 과 대응하며, 두번째 항목에 의해 지칭되는 것은 양의 정수 1 과 대응하며, 두번째 항목에 의해 지칭되는 것은 양의 정수 2 와 대응하며, 일반적으로, n 번째 항목에 의해 지칭되는 것은 양의 정수 n 과 대응한다.

어떤 집합의 원소들의 목록을 작성함으로써 그 집합을 열거할 때, 그 집합의 한 원소가 그 목록 속에 두 번 이상 나타나더라도 그것은 아무런 문젯거리가 되지 않는다. 단지 각 원소가 적어도 한 번은 나타나야 한다는 것만 지키면 된다. 다시 말해 목록이 중복적이어도 문제가 없다. 그 목록이 완전해야 한다는 것만이 요구될 뿐이다. 실제로 중복적인 목록은 항상 중복이 되는 항목들을 목록에서 삭제함으로써 중복이 안 되는 목록으로 만들 수 있다. (각 항목을 차례로 그 항목에 앞서 나왔던 유한한 항목들과 비교, 검사하라. 만일 그 항목이 앞에 나온 어떤 항목과 동일하다면 그 항목을 지워라.)

수학적 용어로 말해 보면, 어떤 집합의 무한 목록은 양의 정수들을 투입값 (argument) 으로, 그 집합의 원소들을 산출값 (value) 으로 갖는 하나의 함수 (이것을 'f' 라 부르자) 를 결정한다. 투입값 n 에 대한 함수 f 의 산출값은 'f(n)' 으로 나타낸다. 이 산출값은 목록의 n 번째 항목에 의해 지시되는 것이다. 따라서 짝수인 양의 정수들의 집합 E 를 열거하는 다음과 같은 목록

2, 4, 6, 8, ...

은 아래와 같은 함수 f 를 결정한다 :

f(1) = 2, f(2) = 4, f(3) = 6, f(4) = 8, ...

그리고 역으로, 함수 f 는 어떤 기호법을 채택할 것이냐 하는 문제만을 제외하고 하나의 목록을 결정한다. (짝수인 양의 정수들의 목록은 위와 같은 십진법 표기 방식 이외에 다음과 같은 이진법 표기 방식에 의해서도 작성될 수 있다 : 10, 100, 110, 1000, ...) 따라서 우리는 모든 양의 정수 n 에 대해 f 의 산출값 f(n) 이 2n 이라고 말함으로써, 즉 f(n) = 2n 이라고 말함으로써 함수 f 를 먼저 정의하고, 그러한 연후에 각 양의 정수 n 에 대해 목록의 n 번째 항목이 수 f(n) 의, 즉 수 2n 의 십진법 표기 숫자라고 말함으로써 목록을 기술할 수도 있다.

그러면 우리는 집합이 목록뿐만 아니라 함수에 의해서도 열거된다고 말할 수 있다. 홀수인 양의 정수들을 목록 1, 3, 5, 7, ... 에 의해 열거하는 대신, 우리는 그것들을 각 양의 정수 n 에 2n – 1 을 산출값으로 할당하는 함수에 의해 열거할 수 있다. 그리고 모든 양의 정수들의 집합 P 를 목록 1, 2, 3, 4, ... 에 의해 열거하는 대신, 각 양의 정수 n 에 n 자체를 산출값으로 할당하는 함수에 의해 열거할 수 있다. (이것이 항등 함수 (identity function) 이다. 그것을 'i' 라고 부르면, 각 양의 정수 n 에 대해 i(n) = n 을 얻는다.)

만일 한 함수가 어떤 비공집합을 열거한다면, 어떤 다른 함수도 그 비공집합을 열거할 수 있다. 실제로 무수히 많은 다른 함수들이 그 비공집합을 열거할 수 있다. 그러므로 양의 정수들의 집합은 함수 i 에 의해서 뿐만이 아니라, 아래와 같은 목록에 의해서 결정되는 함수 (이것을 'g' 라 부르자) 에 의해서도 열거된다 :

         2, 1, 4, 3, 6, 5, ...

이 목록은 목록 1, 2, 3, 4, 5, 6, ... 에서 인접한 홀수항과 짝수항을 서로 바꿈으로써 얻어진 것이다. 이 목록은 좀 이상한 것이긴 하나 집합 P 의 완전히 받아들여질 수 있는 열거로서 손색이 없다. 왜냐하면 모든 양의 정수가 이 목록 속에 조만간 나타나기 때문이다. 이 목록에 대응되는 함수 g 는 아래와 같이 정의될 수 있다.

이 정의는 f(n) = 2n 이나 i(n) = n 과 같은 정의들만큼 깔끔하지는 못하다. 그러나 이 정의는 P 의 유일한 한 원소만을 각 양의 정수 n 과 대응시키기 때문에 그 구실을 충분히 해 내고 있다. 그리고 이렇게 정의된 함수 g 는 실제로 P 를 열거한다. 즉 P 의 각 원소 m 에 대해 g(n) = m 을 만족하는 양의 정수 n 이 존재한다.

우리는 어떤 집합을 열거하는 목록이 중복적이어도 전혀 문제가 없다고 했다. 왜냐하면 원하기만 한다면, 우리는 반복해서 나타나는 것을 삭제하여 언제든지 중복적 목록을 비중복적인 목록으로 만들 수 있기 때문이다. 그리고 목록이 그 속에 빈 틈을 가지고 있어도 또한 전혀 문제가 없다. 왜냐하면 우리들은 그 틈을 차례로 메워 나갈 수 있기 때문이다. 따라서 아래와 같은 빈 틈을 갖고 있는 목록도 전혀 손색이 없는 양의 정수들의 열거이다 :

1, -, 2, -, 3, -, 4, -, 5, -, 6, -, ...

위의 목록에 대응하는 함수 (이것을 'h' 라고 부르자) 는 첫째, 셋째, 다섯째, ... 등의 항목에는 그것에 상응하는 값을 할당하나, 둘째, 넷째, 여섯째, ... 등의 빈틈에 해당하는 항목에는 어떠한 값도 할당하지 않는다. 따라서 우리는 h(1) = 1 이라는 결과를 얻으나 h(2) 로부터는 어떠한 것도 얻지 못한다. 왜냐하면 함수 h 는 투입값 2 에 대해서는 정의되어 있지 않기 때문이다. 마찬가지로 h(3) = 2 이지만 h(4) 는 정의되어 있지 않다. 또 h(5) = 3 이지만 h(6) 은 정의되어 있지 않다. 등등. h 는 양의 정수들의 부분함수 (partial function) 이다. 즉, h 는 오로지 양의 정수인 투입값에 대해서만 정의되어 있으나 양의 정수인 모든 투입값에 대해서 정의된 것은 아니다. 우리는 부분함수 h 를 명백히 아래와 같이 정의할 수도 있을 것이다 :

         h(n) = (n + 1)/2,     만약 n 이 홀수이면.

또는, h 가 짝수인 양의 정수들에 무슨 값을 할당하는지에 대해 말하는 것을 잊지 않았다는 것을 분명히 하기 위해, h 의 정의를 아래와 같이 쓸 수도 있다.

이제 이 부분함수 h 는 좀 이상한 것이기는 하지만 양의 정수들의 집합 P 의 열거로서 아무런 손색이 없다.

간단한 함수인 i 대신 h 를 P 의 열거로서 선택하는 것은 쓸데없는 고집일 것이다. 그러나 부분함수들에 의해 열거할 때 가장 자연스럽게 열거되는 집합들도 있다. 예를 들면 짝수인 양의 정수들의 집합 E 는 짝수인 투입값에 대해서는 i 와 일치하고 홀수인 투입값에 대해서는 정의되지 않는 부분함수 (이것을 'j' 라고 부르자) 에 의해 간편하게 열거된다.

이 함수에 대응하는 빈 틈이 있는 목록을 (십진법 표기를 이용하여) 나타내면

         -, 2, -, 4, -, 6, -, 8, ...

이다. 물론 모든 양의 정수 n 에 대해

         f(n) = 2n

에 의해 정의된 함수 f 도 역시 E 의 열거로서 손색이 없으며, 이 f 에 대응하는 빈틈이 없는 목록은 다음과 같다 :

         2, 4, 6, 8, ...

양의 정수들의 어떠한 집합 S 도 아래와 같이 정의되는 부분함수 s 에 의해 매우 쉽게 열거될 수 있다 :

그래서 수들 1, 2, 5 로 구성된 집합 {1, 2, 5} 는 아래와 같이 정의되는 부분함수 k 에 의해 열거된다 :

우리는 다음 장에서 양의 정수들을 원소로 갖는 모든 집합은 열거가능하지만, 어떤 종류의 집합들은 열거가능하지 않다는 것을 알게 될 것이다. 집합 A 가 열거가능하다고 말하는 것은 다음과 같은 조건을 만족하는 함수 f 가 존재한다고 말하는 것이다 : f 의 모든 투입값들이 양의 정수들이고 f 의 모든 산출값들이 A 의 원소들이며 또 역으로 A 의 각 원소가 모두 f 의 산출값이다. 여기서 A 의 각 원소가 모두 어떤 함수의 산출값이라 하는 것은 A 의 각 원소 a 에 대해 그 함수가 a 를 자신의 산출값으로 할당하는 적어도 하나의 양의 정수 n 이 투입값으로 존재한다는 것이다. 이 정의에서 A 가 양의 정수들의 집합이어야 한다는 것이 요구되지 않는다는 점에 주의하라. A 는 사람들의 집합일 수도 있으며 (예를 들어, 미국 상원의원들의 집합), 부호들의 집합일 수도 있으며 (예를 들어, 우리가 인접한 단어들 사이의 빈칸을 하나의 부호로 간주할 때, 문법적으로 올바른 모든 영어 문장들의 집합), 또는 A 가 집합 {P, E, Φ} 일 때처럼 A 의 원소들 자신이 집합일 수도 있다. 집합 A 가 {P, E, Φ} 인 경우, A 는 세 원소를 가진 집합이며, A 의 각각의 원소 역시도 집합이다. A 의 한 원소는 모든 양의 정수들의 무한집합 P 이며, 다른 원소는 모든 짝수인 양의 정수들의 무한집합 E 이며, 그리고 또 다른 나머지 원소는 공집합 Φ 이다. 집합 A 가 열거가능하다는 것은 분명하다. 예를 들어 다음과 같은 유한 목록에 의해 열거가능하다 :

         P, E, Φ

이 목록의 각 항목은 A 의 원소의 이름이다. 그리고 A 의 모든 원소는 이 목록 속에 조만간 그 이름이 나타난다. 이 목록은 다음과 같은 세 진술에 의해 정의될 수 있는 하나의 함수 (이것을 'f' 라 부르자) 를 결정한다 :

         f(1) = P, f(2) = E, f(3) = Φ.

정확히 말해, f 는 3 보다 큰 숫자에 대해서는 정의가 되지 않은 양의 정수들의 부분함수이다. 여기서 우리는 다음과 같은 교훈을 얻을 수 있다 : 양의 정수들의 함수는 이것이 부분함수이든 전체함수이든 산출값으로 어떠한 집합의 원소라도 가질 수 있다. 다시 말해, 함수의 투입값은 모두 양의 정수들이어야만 하나, 그 산출값은 양의 정수들일 필요가 없다.

영어 알파벳 자모들의 모든 유한한 나열 (string) 들의 집합이 양의 정수들의 집합이 아니면서 열거가능한 무한집합의 한 예가 된다. 이 집합은 열거가능하다. 왜냐하면 그 원소들이 하나의 목록 속에 배열될 수 있기 때문이다. 실제로 원소들이 배열된 목록을 만들어 보는 대신, 그 목록의 원소 배열 내용을 기술하여 보면, 처음 26 개 항목들은 일상적인 순서로 배열된 영어 알파벳의 26 개의 글자들이다. 그 다음 676(= 26²) 개 항목들은 사전적인 순서로 배열된 두 글자의 나열들이다. 그 다음 17576(=26³) 개 항목들은 사전적인 순서로 배열된 세 글자의 나열들이다. 이러한 방식으로 끝없이 계속된다. 종이, 연필, 그리고 끈기가 있다면 위와 같은 방식으로 당신은 당신이 관심을 갖고 있는 모든 유한한 글자 나열의 위치를 목록속에서 결정할 수 있다. 이로써 사실상 우리는 문제의 집합을 열거하는 양의 정수들의 함수를 정의한 것이다. 이 정의는 수학적 등식의 형식을 갖지 않았지만, 투입값으로서의 각 양의 정수와 산출값으로서의 그 집합의 한 원소를 대응시키는 자신의 임무를 잘 수행하고 있기 때문에 정의로서 아무런 손색이 없다. 함수의 정의는 그것이 분명하고 애매하지만 않다면 수학적 기호법 대신 일상 언어를 사용하여도 문제가 되지 않는다.

모든 유한한 글자 나열들의 집합의 원소들은 연필이나 펜 등으로 쓰여진 구체적 문자들이므로, 우리는 그 원소들 자체를 목록 속에 배열한다고 말한다고 해도 문제될 것이 없다. 그러나 우리는 집합을 열거할 때 목록 속에 배열되는 것은 그 집합의 원소들의 이름들이라는 주장을 일관되게 하기 위해서 목록 속의 항목들이 구체적 문자들 자체라기보다 그 자신들의 이름들이라고 말할 수도 있다.

마지막으로 우리의 용어들을 정리해 보자.

함수란 투입값에 산출값을 할당하는 것을 말한다. 산출값이 할당된 모든 투입값들의 집합은 함수의 (투입값) 영역 (domain) 이라고 불리며 투입값에 할당된 모든 산출값들의 집합은 (산출값) 범위 (range) 라고 불린다. 함수들의 투입값들이 양의 정수들인 경우에 우리는 전체함수들과 부분함수들을 구분할 수 있다. 양의 정수들의 전체함수는 그것의 투입값 영역이 양의 정수들의 전체집합 P 인 함수이다. 양의 정수들의 부분함수는 그것의 투입값 영역이 양의 정수들의 전체집합 P 에 미달하는 함수이다. 이제부터 우리가 단순히 양의 정수들의 함수라고 말할 때, 우리는 그 함수가 전체함수일 수도 있고 부분함수일 수도 있다고 이해해야 한다. 이것은 (양의 정수들의) '함수' 가 항상 전체함수를 뜻한다는 일반적인 용어법에서 벗어난 것이다. 또한 이제부터 우리는 투입값 영역이 공집합 Φ 인 이상인 함수 e 를 양의 정수들의 부분함수로 간주할 것이다. 이 함수 e 는 모든 투입값에 대해 정의가 되지 않은 함수이다! 이제 어떤 집합이 어떤 양의 정수들의 함수의 산출값 범위인 경우 그리고 오직 그 경우에만 그 집합은 열거가능하다. 공집합은 e 의 산출값 범위이므로 열거가능하다.

보기. 양의 유리수들의 집합은 열거가능하다.

양의 유리수는 양의 정수들의 비율로 표현될 수 있는 수이다. 즉, m 과 n 이 양의 정수일 때 m/n 의 형태로 표현될 수 있다. 양의 유리수를 열거하기 위한 준비 과정으로서 그것을 도표 1(a) 와 같은 지가각형 모양으로 배열하여 보자.

모든 양의 유리수는 이 배열 어딘가에서 표현된다. 따라서 수 m/n 은 m 번째 열, n 번째 행에서 표현된다. 실제로 그런 모든 수는 무한히 여러 번 표현될 수 있다. m/n, 2m/2n, 3m/3n, ... 이 모두 같은 수를 표현하기 때문이다. 특히 수 1 은 도표 1(a) 의 중심 대각선에 있는 모든 항목들에 의해 표현된다. 즉, 첫째 행 첫째 열, 그리고 둘째 행 둘째 열, 등등이 그것이다.

도표 1

양의 유리수가 열거가능하다는 것을 보이기 위해서 우리는 도표 1(a) 를 하나의 목록으로 배열해야만 한다. 이것을 할 수 있는 방식은 여러 가지인데, 이를테면 도표 1(b) 에서 보여지는 양식이 그 한 가지 보기이다. 도표 1(b) 의 각 위치에 있는 수는 그것과 대응되는 위치에 있는 도표 1(a) 의 항목이 목록에서 몇 번째에 있는지를 나타낸다. 그렇다면 목록에는 각 양의 유리수가 무한하게 여러 번 표현될 수 있는데, 그 목록은 다음과 같다 :

         1/1, 2/1, 2/2, 1/2, 3/1, ...

도표 1 의 두 배열은 또한 양의 유리수들을 열거하는 양의 정수들의 함수 (이것을 'r' 이라고 부르자) 도 만족스럽게 정의해 준다. 그래서 우리는 다음과 같이 말할 수 있다 :

         r(1) = 1/1, r(2) = 2/1, r(3) = 2/2, r(4) = 1/2, r(5) = 3/1, ...

또는 더 간단히 다음과 같이 말할 수 있다 :

         r(1) = 1, r(2) = 2, r(3) = 1, r(4) = 1/2, r(5) = 3, ...

함수 r 은 두 배열에 의해서 아주 적절하게 정의된다. 즉 어떤 양의 정수 n 이 주어지면, 그 수 n 이 두번째 배열에서 나올 때까지 두 배열을 만들어서 산출값 r(n) 을 찾는 것은 아주 간단한 작업이다. 그러면 산출값 r(n) 은 n 에 대응되는 첫번째 배열의 항목에 의해 주어질 것이다. 그런데 꼭 필요한 것은 아니지만 더 수학적인 형태를 띤 r 의 정의를 해 보는 것도 재미있을 것 같다. 만약 당신이 그런 정의를 해보고 싶다면 여기에 힌트가 있다 : 모든 양의 정수 n 은 한 완전 제곱수와 그 다음 완전 제곱수 사이의 어딘가에 있다. 즉, 각 n 에 대해서 (m – 1)² < n ≤ m² 이 만족되는 m 이 정확히 하나 있다. 여기서 투입값 n 에 산출값 m 을 할당하는 함수를 'sq' 라는 기호로 쓰자. 당신이 아래의 정의에서 물음표를 n 과 sq 를 포함하는 수학적 표현으로 바꾸기만 하면 된다 :

그러나 이런 종류의 일이 당신에게 너무 힘들다면 그것 때문에 골치를 썩지는 말라. 만약 풀어 보고 싶다면, 당신의 답을 아래의 연습문제 1 의 풀이와 맞춰 볼 수 있을 것이다.

연습문제

1. 자신의 제곱이 n 보다 크거나 같은 수들 중 가장 작은 수를 sq(n) 이라고 할 때 함수 r 을 위에서 보여준 방식대로 정의하여라. 힌트 : 우선 도표 1 의 m 번째 행과 m 번째 열에서 맨 앞에 나오는 항목들을 몇 개 써 보아라.

2. 정수 ..., -2, -1, 0, 1, 2, ... 가 열거가능하다는 것을, 시작은 있지만 끝은 없는 단일한 무한 목록 속에 배열함으로써 보여라. 그리고 그 목록에 대응되는 함수에 대한 수학적 정의를 적어라.

3. 모든 유리수들 (양수, 음수, 영) 의 집합이 열거가능하다는 것을, 모든 유리수들을 열거하는 (시작은 있지만 끝은 없는) 단일한 무한 목록을 기술함으로써 보여라.

4. 양의 부호 (+) 와 음의 부호 (-) 의 모든 유한한 나열 (일련체) 들의 집합이 열거가능함을, 그 나열 (일련체) 들을 열거하는 단일한 목록을 기술함으로써 보여라.

5. 그 다음에 양의 정수들의 모든 유한한 집합들의 집합이 열거가능함을, 양의 부호와 음의 부호의 유한한 나열들이 양의 정수들의 유한한 집합들의 이름으로 쓰일 수 있는 방식을 기술함으로써 보여라.

6. D 를 다음과 같은 양의 정수들의 집합들의 집합이라고 하자 : 양의 정수들의 집합이 유한한 수의 우리말 글자들로 정의될 수 있을 경우 그리고 오직 그 경우에만 그 집합은 D 에 속한다. 따라서 다음 집합들은 유한한 수의 우리말 글자들로 정의될 수 있기 때문에 D 에 속한다.

E : Φ : {1, 2} : {1, ..., 999} :

모든 짝수인 양의 정수들의 집합 (13 글자). 원소를 하나도 갖지 않는 집합 (12 글자). 일과 이만을 원소로 갖는 집합 (12 글자). 천보다 작은 양의 정수들의 집합 (13 글자).

등등. 집합 D 가 열거가능하게 무한하다는 것을 보여라.

풀이

1. m = sq(n) 이라는 것을 생각해 보면 도표 1 의 m 번째 행과 열은 다음과 같다 :

(a)	sq(n)/1 sq(n)/2 sq(n)/3 . . .
1/sq(n)        2/sq(n)        3/sq(n)        ... sq(n)/sq(n) ...

 

 

 

 

(b)	(sq(n)-1)2+1 (sq(n) -1)2+2 (sq(n) -1)2+3 . . .
(sq(n))2-0    (sq(n))2-1    (sq(n))2-2    ... (sq(n)-1)2+m ...

 

 

 

 

   그렇다면 요구한 정의는 다음과 같은 꼴이 될 것이다.

  이것은 기발하기는 하지만 도표 1 의 배열을 이용하여 내린 r 의 정의보다 더 많은 것을 말해 주지는 않는다.

2. 가장 간단한 목록은 다음과 같다 : 0, 1, -1, 2, -2, 3, -3, ... 이 때 해당함수를 'f' 라고 부른다면 f(1) = 0, f(2) = 1, f(3) = -1, f(4) = 2 등이 된다. 수학적 형태를 띤 f 의 정의는 다음과 같다 :

3. 여러분은 이미 양의 유리수들을 무한한 단일 목록에 어떻게 배열하는지를 알아보았다. 이 목록 앞에 '0' 을 쓰고, 양의 유리수들 앞에 음의 기호를 붙여 가면서 '0' 앞에 역순으로써 나가라. 그러면 다음과 같은 것이 생긴다 :

..., -3, -1/2, -1, -2, -1, 0, 1, 2, 1, 1/2, 3, ...

마지막으로 이것을 적절한 목록으로 바꾸기 위해 연습문제 2 의 방법을 써라 :

0, 1, -1, 2, -2, 1, -1, 1/2, -1/2, 3, -3, ...

4. 열거는 다음과 같다 :

         +, -, ++, +-, -+, --, +++, ++-, +-+, +--, -++, ...

이 목록을 기술해 보면 다음과 같다 : 먼저 길이가 1 인 일련체들을 배열하고 그 다음에 길이가 2 인 일련체들을 배열하고 그 다음에 길이가 3 인 일련체들을 배열하고 등등. 각 일련체들의 그룹에서 '+' 를 '-' 보다 앞에 오는 알파벳으로 생각해서 일련체들을 사전 순으로 정렬하라. (따라서 그 다음 여섯 개 항목은 -+-, --+, ---, ++++, +++-, ++-+ 가 된다.)

5. 일련체 속에 n 번째 기호가 있고 그것이 양의 기호이면 그 유한한 일련체를 수 n 이 속하는 집합의 이름이라고 해석하라. 그리고 일련체 속에 기호들이 n 개보다 적거나 n 번째 기호가 있지만 그것이 음의 기호라면 그 유한한 일련체를 수 n 이 속하지 않는 집합의 이름이라고 해석하라. 이제 양의 정수들의 모든 유한한 집합은 이름을 갖게 된다. 실제로 각 집합은 무한히 많은 이름들을 갖게 되는데, 이를테면 공집합 Φ 는 '-' 와 '---' 등등의 이름을 갖고, 집합 {1, 2, 5} 는 '++--+' 와 '++--+-' 와 '++--+--' 등등의 이름을 갖는다.

6. 집합 D 는 다음과 같은 집합들을 무한히 많이 원소로 가질 수 있기 때문에 확실히 무한하다 :

    {1} : 원소가 오직 1 뿐인 집합
{2} : 원소가 오직 2 뿐인 집합
              .
              .
모든 양의 정수는 우리말로 이름을 가질 수 있으므로 D 의 이 부분집합은 무한하고 따라서 D 자체가 무한하다. 집합 D 가 열거가능하다는 사실은, 양의 정수들의 집합에 대해 우리말로 내린 모든 정의가 유한한 개수의 글자들로 이루어져 있고 그 글자들은 각각 24 개의 한글 자모로 이루어져 있거나 (구두점은 무시하자) 25 번째 자모로 취급할 수 있는 (인접한 낱말들을 구분해 주는) 빈 칸으로 이루어져 있다는 사실로부터 따라나온다. (구두점을 쓰고 싶다면 적절한 기호를 이 자모들에 보태라. 자모들은 더 많아지긴 했어도 여전히 유한하다.) 이제 확장된 자모로 된 유한한 기호들의 일련체들을 열거할 수 있다. 우선 길이가 1 인 일련체들을 배열하고 그 다음에는 길이가 2 인 일련체들을 배열하고, 등등. 각 일련체들의 그룹 안에서는 일련체들을 (보탠 자모에 대해서도 사전의 순서를 임의적으로 준 다음에) 사전 순으로 정렬하라. 이렇게 열거해 놓고 보면 대부분의 항목들은 아무 뜻도 없는 자모들의 나열이거나, 무슨 뜻이 있는 경우에도 양의 정수들의 집합들의 정의가 되지 못할 것이다. 그런 항목들은 모두 지워라. 그러면 양의 정수들의 집합들을 우리말로 정의한 것을 모두 열거한, 빈 틈이 있는 목록이 남게 된다.