가산집합

가산성은 집합의 크기에 해당하는 개념이라고 할 수 있다. 무한집합에서는 원소의 개수를 따질 수 없기 때문이다. 원소의 개수가 뜻밖에도… 무한하니까. 집합의 크기는 기수(카디널리티)라고도 한다.

무한집합의 크기

유한집합의 크기를 정하는 것은 간단하다. 원소의 개수를 세면 된다. 그래서 집합 M = {a, b, c, d, e}의 크기는 5이고, |M| = 5라고 쓴다.

무한집합은 훨씬 복잡하다. 무한집합의 크기는 어떻게 비교할까? 비교할 수 있기는 할까, 아니면 무한집합은 모두 “크기가 같을까”?

예로 자연수의 집합과 짝수인 자연수의 집합을 보자. 집합 ℕ = {1, 2, 3, 4, 5, 6, …}과 S = {2, 4, 6, …}이 있다. 자연수의 집합이 짝수의 집합보다 크다고 말하고 싶어진다. 자연수에는 짝수가 모두 들어 있고, 게다가 다른 원소, 즉 홀수도 더 들어 있기 때문이다.

그래서 S ⊂ ℕ, 즉 집합 S는 집합 ℕ의 진부분집합이라고 쓸 수 있다. 그리고 S ⊂ ℕ이므로 집합 ℕ이 더 크다고, 집합 S보다 원소가 더 많다고 말할 수도 있을 것이다.

집합의 크기를 부분집합 관계로 잴 수 없는 이유 가운데 하나는, 어느 쪽도 다른 쪽의 부분집합이 아닌데도 크기가 다른 집합이 있다는 것이다. 유한집합으로도 보일 수 있다. A = {1, 3, 4, 9}와 B = {b, u, r, z, m}을 보자. |A| = 4이고 |B| = 5이다. 집합 B가 집합 A보다 크지만 A ⊂ B는 성립하지 않는다. 무한집합에서는 짝수와 홀수에서 이를 볼 수 있다. 어느 쪽도 다른 쪽의 부분집합이 아니다.

그러니 부분집합 관계는 한 집합이 다른 집합보다 큰지를 판단하는 데 알맞은 도구가 아니다.

일대일대응

다른 방법을 써 보자. 두 집합 A와 B가 있다. 두 집합 사이에 일대일대응(전단사 함수)이 있으면 두 집합의 크기가 같다고 할 수 있다. 무슨 뜻일까? 집합 A에서 원소 하나, 집합 B에서 원소 하나를 꺼내 쌍 (a, b)를 만든다. 이 원소들을 집합에서 지우고 계속한다. 두 집합을 모두 “비울” 수 있으면 일대일대응을 찾은 것이다.

유한집합의 예로 A = {a, b, c}와 B = {1, 2, 3}을 보자. 첫 번째 쌍은 (a, 1), 다음은 (b, 2), 마지막은 (c, 3)이 될 수 있다. 두 집합의 원소를 모두 썼으므로 일대일대응을 찾았다. 중요한 것은 이것이 유일한 일대일대응이 아니라는 점이다. (a, 3), (b, 1), (c, 2)도 올바른 답이다.

무한집합에서는 조금 더 흥미로워진다. 홀수인 자연수와 짝수인 자연수를 보자. 직관적으로 둘은 개수가 같아야 할 것 같다. 확인해 보자. 첫 번째 홀수를 첫 번째 짝수에 대응시킨다. (1, 2)이다. 다음으로 두 번째 홀수와 두 번째 짝수를 대응시킨다. (3, 4)이다. 이렇게 계속한다. 그러면 쌍 (1, 2), (3, 4), (5, 6), (7, 8), …을 얻는다. 모든 홀수 l은 짝수 l + 1에 대응하고, 모든 짝수 s는 홀수 s − 1에 대응한다고 쓸 수 있다. 모든 홀수와 모든 짝수에 대해 그 수를 포함하는 쌍이 있다. 따라서 홀수의 집합과 짝수의 집합은 크기가 같다.

짝수와 자연수

이번에는 같은 방법으로 자연수의 집합과 짝수의 집합을 비교해 보자. 집합 ℕ = {1, 2, 3, 4, 5, 6, …}과 S = {2, 4, 6, …}이 있다. 직관적으로는 자연수의 집합이 더 클 것 같다.

그런데 일대일대응을 찾아보자. 모든 자연수 n을 그 두 배인 2n에 대응시킬 수 있다. 그러면 쌍 (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), …을 얻는다. 모든 자연수 n에 대해 쌍 (n, 2n)이 있고, 모든 짝수 s에 대해 쌍 (s/2, s)가 있다. 일대일대응을 찾았으므로 짝수의 집합과 자연수의 집합은 크기가 같다. 즉 기수가 같다.

혼란스러워 보일 수 있다. 자연수에는 분명히 짝수보다 원소가 더 많은 것 같기 때문이다. 자연수에는 짝수가 모두 들어 있고, 게다가 홀수도 모두 들어 있다. 그래도 일대일대응을 찾을 수 있으므로 두 집합은 크기가 같다.

자연수와 비교하기

사실 자연수는 무한집합의 가장 작은 크기를 정한다. 어떤 집합이 자연수의 집합과 크기가 같은지는 꽤 쉽게 알아낼 수 있는 경우가 많다. 자연수와의 일대일대응을 찾으면 된다. 실제로는 주어진 집합 M의 원소에 번호를 매겨 차례대로 늘어놓을 수 있으면 된다.

즉 집합의 원소를 늘어놓아서 어느 원소가 첫 번째, 두 번째, 세 번째, 네 번째, 열 번째 등인지 정할 수 있으면 그 집합은 ℕ과 크기가 같다. 이런 집합을 가산집합이라고 한다.

짝수인 자연수와 홀수인 자연수가 가산집합이라는 것은 쉽게 알 수 있다. 첫 번째, 두 번째, 세 번째 짝수나 홀수를 정할 수 있기 때문이다. 짝수인 정수는 어떨까? 즉 집합 S = {…, −4, −2, 0, 2, 4, …}이다. 이 수들을 늘어놓을 수 있을까? 있다. 앞에서와 같은 순서를 쓰되, 양의 짝수 바로 뒤에 그 음수를 쓰면 된다. S = {0, 2, −2, 4, −4, 6, −6, …}이다. 예를 들어 정수도 마찬가지이다.

유리수의 크기

더 흥미로운 예는 유리수, 즉 분수이다. 유리수를 늘어놓을 수 있을까? 있지만 조금 더 복잡하다. 행과 열이 무한히 많은 표를 만든다. 각 칸에는 분수가 들어간다. n번째 열과 m번째 행에는 분수 n/m을 넣는다. 즉 1열 2행에는 $\frac{1}{2}$이, 3열 4행에는 3/4이 있다.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

이제 이 수들을 어떻게 늘어놓고 번호를 매길까? 행이나 열을 따라 번호를 매길 수는 없다. 그러면 한 행이나 한 열에 빠져서 영영 나오지 못하기 때문이다. 그 대신 대각선을 따라 수를 고른다. (첫 번째 대각선:) 1/1, (두 번째 대각선:) 2/1, 1/2, (세 번째 대각선:) 3/1, 2/2, 1/3, (네 번째 대각선:) 4/1, 3/2, 2/3, 1/4, … 값이 같은 분수가 여러 번 나오지만 상관없다. 더 문제가 되는 것은 음수가 없다는 것이다. 이 문제는 간단히 해결된다. 분수를 하나 쓸 때마다 바로 뒤에 그 음수를 쓰면 된다. 그러면 맨 앞에 0만 빠진다. 이것으로 끝이다. 모든 유리수를 하나의 수열로 늘어놓았다.

전체적으로 다음 수열을 얻는다. 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

실수의 크기

실수는 자연수와 크기가 같을까? 이 문제는 유리수보다도 더 복잡하다. 귀류법을 쓴다. 실수가 가산집합이고 자연수와의 일대일대응이 있다고 가정하자. 즉 실수를 늘어놓을 수 있다고 가정한다. 그리고 다음 대응이 바로 그 순서라고 하자.

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

표에는 이 순서에서 처음 일곱 개의 실수가 있다. 물론 이 순서는 아무렇게나 정해도 된다. 크기 순서대로 늘어놓을 필요는 없다.

가정에 따르면 이 무한한 표에 모든 실수가 늘어서 있다. (이 표도 무한하고, 여기에는 처음 일곱 개만 보인다.) 이제 실수이지만 이 표에 없는 수를 찾아서, 아니 만들어 보자. 그런 수를 찾으면 표에 모든 실수가 있다는 가정에 모순이고, 따라서 실수의 집합은 가산집합이 아니라고 결론지을 수 있다.

표에 없는 수는 다음과 같이 만든다.

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

먼저 0,…이라고 쓴다. 새로운 실수는 처음에 이런 모습이다. 소수 첫째 자리에는 이 순서에서 첫 번째 실수의 첫째 자리에 없는 숫자를 쓴다(표에서 상자로 표시했다). 그 자리에는 숫자 3이 있으므로 예를 들어 1을 골라서 0.1…을 얻는다.

계속하자. 둘째 자리에는 두 번째 실수의 둘째 자리에 없는 숫자를 쓴다. 그 자리에는 9가 있으므로 예를 들어 2를 쓴다. 그러면 0.12…를 얻는다. 셋째 자리에는 세 번째 실수의 셋째 자리 숫자와 다른 숫자를 쓴다. 그 자리에는 3이 있으므로 예를 들어 7을 고른다. 그러면 0, 127…을 얻는다.

이렇게 계속한다. 새로운 수의 n번째 자리에는 언제나 이 순서에서 n번째 수의 n번째 자리 숫자와 다른 숫자를 쓴다.

이렇게 해서 무엇을 얻을까? 이 순서에 있는 모든 수와 적어도 한 자리가 다른 수를 얻는다. 마지막 중간 결과 0.127…을 보자. 이 수는 이 순서의 첫 번째 수와 적어도 첫째 자리가 다르다. 그렇게 만들었기 때문이다. 두 번째 수와는 적어도 둘째 자리가 다르다. 세 번째 수와는 셋째 자리가 다르다. 일반적으로 이 새로운 수는 순서에서 n번째에 있는 수와 적어도 n번째 자리가 다르다.

따라서 새로 만든 이 수는 자연수와 실수 사이의 일대일대응을 나타낸다던 표에 없다. 그러므로 실수는 자연수보다 많다. 실수는 가산집합이 아니라 비가산집합이다.

더 읽을거리

• Are there more odd or even numbers?(영어)