한 집합의 원소보다
그 부분집합이
언제나 더 많을까?

더 큰 집합은 어디까지
만들 수 있을까?

더 큰 무한의 의미, 러셀 역설과 다른 점, 집합론 공리의 역할을 검토하고 계산 예제와 풀이로 결론을 확인합니다.

11. 이 정리는 ‘무한에도 더 큰 무한이 있다’에서 어디까지 나아갈까요?

자연수 집합 N을 출발점으로 삼아 P(N)을 만들 수 있습니다. 그리고 P(P(N))을 다시 만듭니다. 첫 번째 멱집합 P(N)의 원소가 ‘자연수의 부분집합’이었다면, P(P(N))의 원소는 ‘자연수의 부분집합들을 골라 만든 집합’입니다. 원소가 맡는 역할이 한 번 더 달라집니다. 이 과정을 반복하면 N, P(N), P(P(N)), P(P(P(N))), …처럼 각 단계에서 앞 단계보다 큰 집합을 얻습니다.

이번 정리는 어느 특정한 무한집합에서만 성립하는 성질을 말하지 않습니다. 임의의 집합 A를 주면 그 멱집합 P(A)가 더 큽니다. 그래서 가능한 모든 집합 중 크기가 가장 큰 집합은 존재할 수 없습니다. 만약 가장 큰 집합이 있다면 그 멱집합이 더 크다는 정리와 충돌하기 때문입니다. 다만 이 표현의 논리적 전제는 집합의 존재를 허용하는 공리 체계입니다. 표준 집합론은 임의의 집합의 멱집합이 다시 집합임을 멱집합 공리로 받아들입니다.

‘멱집합이 더 크다’는 결과만으로 무한집합 사이의 모든 크기를 한 번에 분류한 것은 아닙니다. 특히 자연수의 크기와 실수의 크기 사이에 다른 크기가 있는지 묻는 연속체 가설은 별도의 문제입니다. 2의 거듭제곱을 뜻하는 2^|N|와 가장 작은 비가산 기수 사이의 정확한 관계는 멱집합 정리만으로 결정되지 않습니다. 무한의 크기가 계속 커진다는 결론과, 그 사이에 다른 크기가 전혀 없는가라는 질문은 구분해야 합니다.

12. 러셀의 역설과 같은 종류의 모순 아닌가요?

제07회에서는 ‘자기 자신을 원소로 갖지 않는 모든 집합을 모은다’고 했을 때 생기는 러셀의 역설을 살폈습니다. 여기서는 D={a∈A:a∉f(a)}라고 적습니다. 둘 다 ‘자기와 관련된 포함 여부를 뒤집는다’는 공통점이 있습니다. 그러나 어떤 집합을 만들 수 있다고 가정하는지에서 결정적인 차이가 있습니다.

러셀의 역설이 겨냥한 무제한적인 구성은 집합 전체를 대상으로 자기 포함 여부를 따져 만든 모임이 언제나 하나의 집합이 된다고 주장했습니다. 그렇게 만든 R에 R 자체를 대입하면 R∈R과 R∉R이 충돌합니다. 이것은 무제한적인 집합 구성 원리의 문제입니다. 반면 이번 증명에서는 이미 주어진 집합 A 안에 있는 원소만 골라 D를 만듭니다. D⊆A로 정의되므로 표준 집합론의 분리 공리꼴에서 허용됩니다.

모순의 역할도 다릅니다. 이번에는 f가 P(A)를 모두 출력한다고 가정했을 때에만 f(d)=D인 d를 잡을 수 있습니다. 이 가정을 부정하면 D의 존재와 모순은 함께 남지 않습니다. 즉 ‘D가 존재할 수 없어서’ 모순이 난 것이 아니라, D까지 포함한 모든 부분집합을 원소별 출력표로 빠짐없이 제공할 수 있다는 주장이 잘못된 것입니다. 칸토어의 정리는 집합론의 문제를 드러내는 동시에, 제한된 집합 구성 속에서 엄밀한 증명이 가능하다는 사실을 보여 줍니다.

13. 원소마다 부분집합 하나씩 지정했으니 결국 개수가 같지 않을까요?

‘원소마다 값을 하나씩 대응시켰다’는 사실은 함수가 잘 정의되었다는 뜻입니다. 함수가 전사인지 여부는 출력되지 않은 부분집합이 있는지에 따라 결정됩니다. 유한한 동아리 사례에서는 세 원소가 세 개의 출력값을 낼 뿐, 여덟 부분집합을 모두 출력하지 못합니다. 무한집합에서도 같은 문제를 정밀하게 증명해야 합니다. 각 자연수마다 하나의 자연수 부분집합을 지정할 수 있다는 사실과 모든 부분집합이 그중 하나로 등장한다는 주장은 전혀 다릅니다.

‘대응 규칙을 더 복잡하게 만들면 빠진 부분집합을 출력할 수 있지 않을까요?’라고 반문할 수도 있습니다. 어느 f를 선택하든 그 f에 맞추어 D를 정의할 수 있습니다. f를 고치면 D도 바뀝니다. 증명의 요지는 특정한 대응표 하나를 비판하는 데 있지 않습니다. 어떤 전사 후보를 제시해도 그 후보에서 빠지는 부분집합을 새로 정의할 수 있다는 일반성에 있습니다.

그렇다면 D가 f의 출력 목록에 빠져 있음을 확인하려면 무한한 표를 전부 검사해야 할까요? 그럴 필요도 없습니다. 전사라고 가정하면 D를 출력하는 입력 d가 반드시 있어야 한다는 단 하나의 조건을 활용하면 됩니다. 그리고 d가 D에 속하는지에 대해 예 또는 아니요라는 두 경우를 검토하여 둘 모두에서 모순을 얻습니다. 무한한 대상의 전체 내용을 하나씩 열거하지 않고도 전사가 불가능함을 증명하는 이유입니다.

14. 멱집합 공리는 이 증명에 어떤 자격을 부여하나요?

표준적인 체계인 체르멜로–프렝켈 집합론(ZF)은 임의의 집합 A가 주어졌을 때 그 모든 부분집합을 원소로 하는 집합 P(A)가 존재한다고 받아들입니다. 이것이 멱집합 공리입니다. 출발 집합 A가 정해졌을 때 그 안에서 성질에 맞는 원소만 골라 부분집합 D를 구성하는 것은 분리 공리꼴에 해당합니다. 이 두 규칙을 분리해서 이해하면, 증명이 어떤 집합의 존재에 근거하고 있는지 명확해집니다.

멱집합 공리를 ‘지나치게 큰 집합을 실제로 일일이 생성하는 컴퓨터 명령’으로 생각할 필요는 없습니다. 공리는 특정한 수학적 대상으로서 P(A)의 존재를 보장하는 명제입니다. 컴퓨터로 모든 무한 부분집합을 만들어 목록에 저장할 수 있다는 뜻이 아닙니다. 마찬가지로 칸토어의 정리가 실무적으로 큰 데이터를 저장하는 프로그램의 저장공간을 곧바로 계산해 주는 것도 아닙니다. 여기서 증명하는 것은 정해진 공리 체계에서 집합의 크기에 관해 따라 나오는 구조적 성질입니다.

선택공리와의 관계도 분명히 해 둡시다. 어떤 두 집합이든 반드시 단사 관계로 비교할 수 있는가 같은 일반적 크기 비교에는 선택공리가 영향을 미칠 수 있습니다. 그러나 A와 그 멱집합 사이에는 앞서 구성한 명시적인 단사가 있고, 전사가 없다는 사실을 직접 증명했습니다. 따라서 이 특정한 크기 비교에는 선택공리가 필요하지 않습니다.

15. 표 하나를 직접 계산하면 D가 어떻게 만들어질까요?

다시 A={가,나,다}로 돌아갑니다. 예시 함수가 f(가)={가,나}, f(나)={다}, f(다)=∅라고 합시다. 이제 각 원소가 자신에게 배정된 집합에 들어 있는지 검사합니다. 가는 {가,나}에 있으니 D에 넣지 않습니다. 나는 {다}에 없으니 D에 넣습니다. 다는 공집합에 없으니 D에 넣습니다. 따라서 D={나,다}입니다.

f의 세 출력값은 {가,나}, {다}, ∅입니다. 어느 것도 {나,다}와 같지 않습니다. 원소별로 자기 배정 집합과 포함 여부를 뒤집었기 때문입니다. 이 예시는 정리의 전체 증명은 아닙니다. 세 원소의 사례를 검사하는 것만으로 임의의 무한집합에 대한 사실을 입증할 수는 없습니다. 대신 D를 만드는 동작이 정확히 무엇인지 손으로 확인하는 작은 모형입니다.

독자가 직접 바꿔 볼 수도 있습니다. f(가)={가}, f(나)={가,나}, f(다)=∅라고 새로 지정하면 가는 자신의 배정 집합에 있으므로 제외, 나도 있으므로 제외, 다는 없으므로 포함합니다. 이번 D는 {다}입니다. 처음의 D와 달라졌습니다. 그렇지만 여전히 세 출력값인 {가}, {가,나}, ∅ 중 어느 것과도 같지 않습니다. 함수가 바뀌면 D도 함께 바뀌지만 빠진 출력이 반드시 있다는 구조는 유지됩니다.

16. 짧은 연습으로 증명을 다시 세워 봅시다

문제 1. A={1,2}일 때 P(A)의 원소를 모두 쓰고 그 수를 구해 보세요. 한 원소만 담는 집합과 전체 집합을 구별해야 합니다.

문제 2. A={가,나,다}에서 f(가)={나}, f(나)={나,다}, f(다)={가}일 때 D를 계산해 보세요. D={a∈A:a∉f(a)}를 그대로 사용합니다.

문제 3. ‘A에서 P(A)로 단사가 존재한다’는 명제와 ‘A에서 P(A)로 전사가 존재한다’는 명제의 차이를 자기 말로 설명해 보세요. 어느 쪽이 참이고 어느 쪽이 거짓인지 그 이유도 적어 보세요.

문제 4. 집합 A에 원소가 하나도 없을 때 칸토어의 정리가 성립할까요? 함수의 정의와 공집합의 멱집합을 이용해 확인해 보세요.

풀이 1. P(A)={∅,{1},{2},{1,2}}이고 원소 수는 4입니다. 원소 1과 {1}을 같은 대상으로 세면 틀립니다. A의 원소는 숫자 두 개이고 P(A)의 원소는 네 개의 집합입니다.

풀이 2. 가∉{나}이므로 가를 넣습니다. 나∈{나,다}이므로 나는 넣지 않습니다. 다∉{가}이므로 다를 넣습니다. 따라서 D={가,다}입니다. f의 출력값 {나}, {나,다}, {가} 가운데 D는 없습니다.

풀이 3. 단사는 서로 다른 입력이 서로 다른 출력을 갖도록 대응시키는 조건입니다. a↦{a}라는 규칙이 단사의 실제 예입니다. 전사는 P(A)의 모든 부분집합이 출력으로 나타나야 한다는 조건입니다. 전사라고 가정하면 D를 출력하는 입력 d에 대해 d∈D와 d∉D가 동치가 되는 모순이 생기므로 전사는 불가능합니다.

풀이 4. A=∅이면 P(A)={∅}입니다. 따라서 |A|=0, |P(A)|=1입니다. 공집합에서 {∅}으로 가는 함수는 입력 원소가 없기 때문에 출력 ∅을 실제로 만들지 못합니다. 전사가 아니고, 공집합을 정의역으로 하는 빈 함수는 단사입니다. 정리의 결론과 정확히 일치합니다.

17. 우리가 실제로 증명한 것은 무엇인가요?

이번 정리는 처음의 동아리 선택 문제를 무한의 세계까지 확장합니다. 원래 집합 A의 원소와 그 부분집합을 세는 기준을 먼저 구별했습니다. 유한집합에서는 각 원소를 고를지 말지 정하여 2ⁿ개의 부분집합을 얻었습니다. 무한집합에서는 단순한 수 세기 대신 함수의 단사와 전사 조건을 사용했습니다.

마지막 판단은 간결합니다. A에서 P(A)로 가는 임의의 함수 f를 잡고, 자신에게 배정된 부분집합에 들어 있지 않은 원소만 모은 D를 만듭니다. f가 D까지 출력한다고 가정하면, D를 출력하는 입력 d는 D에 들어 있는 동시에 들어 있지 않아야 합니다. 따라서 f는 P(A)를 전부 출력할 수 없습니다. 반면 a↦{a}라는 단사는 언제나 있습니다. 이 두 사실에서 |A|<|P(A)|가 따라옵니다.

여기에는 어떤 가장 큰 무한도 미리 가정되지 않습니다. 어떤 집합을 하나 정해도 그보다 큰 멱집합을 구성할 수 있기 때문입니다. 집합을 원소로 세는 일에서 집합의 부분집합들을 원소로 세는 일로 질문을 바꾸었을 뿐인데, 그 사이의 차이는 유한한 예시를 넘어 모든 집합에 적용되는 정리로 확장되었습니다. 독자에게 남는 다음 질문은 이것입니다. 원소가 더 많다는 사실을 증명했다면, 그보다 큰 집합을 논리적으로 어떤 조건 아래에서 만들 수 있을까요? 다음 연재에서는 수학적 구조의 ‘크기’와 그 구조를 기술하는 논리 언어의 표현력 사이에 생기는 또 다른 질문을 살펴봅니다.