집합의 기수와 무한집합 1 - 집합의 기수와 전단사 함수

Post 1 - 집합의 기수와 전단사 함수

안녕하세요! 세 개의 포스팅에 걸쳐 집합의 기수에 대해 소개를 맡은 공우 12기 Jubby입니다. 자유전공학부에서 수리과학과 컴퓨터공학을 전공하고 있습니다. 지난 극한의 수학적 정의에 대한 포스팅과 비슷하게 본 포스팅 또한 수학적인 정의와 개념에 치우친 포스팅이 될 텐데요.

우선 앞으로의 글에서 다룰 내용을 간단히 소개하고, 본 포스팅에서 다루는 내용이 왜 중요한지 간략하게 설명드리고자 합니다. 본 포스팅에서는

1. 집합의 원소의 개수에 해당하는 개념인 기수(Cardinality)를 소개하고
2. 무한집합과 유한집합, 가산집합과 비가산집합의 개념을 소개하고
3. 보다 심화된 내용인 칸토어(Cantor) 집합과 베른슈타인 정리 등 기타 응용에 대해 소개하는 것

이 목표라고 할 수 있겠습니다.

무한집합에 대한 본격적인 논의는 칸토어(Georg Cantor)에 의해 처음 시작되었다고 볼 수 있다고 합니다. 칸토어는 당시 신학적으로 금기되어있던 무한집합에 대해 연구하면서 무한을 다룰 수 있는 초석을 마련하였다고 평가받습니다.

특히 칸토어는 무한이라는 개념 사이에도 '크기’가 존재한다는 것을 처음 밝혔으며, 이에 대해서 여전히 풀리지 않은 난제인 '연속체 가설’등도 존재하는 등, 여전히 학문적으로도 연구가 활발히 이루어지고 있는 분야로 알려져 있습니다.

무한을 다루면 유한집합을 다룰 때와 달리 상당히 많은 반직관적인 일들이 벌어지곤 합니다. 이 중, 후에 소개할 칸토어 집합은 특히 부자연스러운 일이 많이 발생하여, 수학에서 많은 반례를 잡을 때 사용된다고 하는데요. 칸토어 집합은 르벡 적분을 활용하는 실해석학, 그리고 확률론 분야에 필수적인 개념인 '측도(measure)'라는 개념이 탄생하게 된 계기이기도 합니다.

이러한 이유 외에도 앞으로 소개할 내용들의 증명들은 상당히 흥미롭고 신기한 내용이 많습니다. 처음 볼 때는 머리만 아프고, 직관적으로 와닿지 않는 내용이 될 확률이 높습니다만, 그럴 일 없도록 최대한 쉽게 설명하도록 해보겠습니다. 그럼, 오늘 다룰 내용인 집합의 기수와 전단사 함수의 내용을 소개하도록 하겠습니다.

전단사 함수 (Bijective Functions)

집합의 기수에 대해 논하기 앞서 필요한 한 가지 도구인 전단사 함수에 대해 소개하도록 하겠습니다. 전단사 함수에 대해서는 다들 알고 계시리라 생각하지만, 앞으로의 논의에 필요하기 때문에 한 번 엄밀하게 정의하고 넘어가도록 하겠습니다.

Definition) 함수 $f : X \rightarrow Y$에 대해, $f$가 전사이고 단사이면 $f$는 전단사 함수이다.

Definition) 함수 $f : X \rightarrow Y$에 대해, 다음 조건을 만족하는 $f$는 단사이다.
$$\forall x_1, x_2 \in X, f(x_1) = f(x_2) \rightarrow x_1=x_2$$
또는, 위 조건의 대우 명제인 $$\forall x_1, x_2 \in X, x_1 \neq x_2 \rightarrow f(x_1) \neq f(x_2)$$
를 활용하기도 합니다.

Definition) 함수 $f : X \rightarrow Y$에 대해, 다음 조건을 만족하는 $f$는 전사이다.
$$\forall y \in Y, \exist x \in X, f(x) = y$$

전단사 함수를 간혹 일대일 대응(one-to-one correspondence)라고 부르기도 하는데요. 함수가 되기 위해서는 하나의 $x \in X$에 대해 정확히 하나의 $y \in Y$가 대응되어야 함을 기억하면, 전단사 함수의 다른 이름이 왜 일대일 대응인지 쉽게 이해하실 수 있으실 것이라 생각합니다.

집합의 기수를 논함에 있어 전단사 함수가 중요한 까닭은, 집합의 기수는 전단사 함수를 이용한 집합간의 동치 관계(equivalence relation)으로 정의되기 때문입니다. 동치 관계가 무엇인지 본 포스팅에서 자세하게 설명하지는 않겠으나, 어떠한 관계가 1) reflexivity, 2) symmetricity, 3) transitivity를 만족하면 그러한 관계를 동치 관계라 부릅니다. 전단사 함수들의 집합에, 함수의 합성으로 그 관계를 줄 경우 합성에 의한 관계는 동치 관계가 됩니다.

이러한 방식으로 전단사 함수들에 동치 관계를 부여하고 나면, 집합의 기수가 잘 정의되게(well-defined) 되고, 집합의 기수이 같은 집합들을 묶어줌으로써 집합을 분류할 수 있게 됩니다. 즉, 두 개의 기수가 '같다’는 개념을 정의한 것이라 볼 수 있습니다.

비슷한 방법으로 두 기수 간의 크기 개념 또한 정의할 수 있습니다. 구체적으로 내용을 설명하기 위해서는 많은 양의 사전 작업이 필요하여, 결과만 간략하게 소개하고자 합니다. 수학에서 어떠한 관계(relation)이 크기 관계를 가진다고 하기 위해서는 다음 세 가지 조건을 만족해야 합니다. 1) $x \leq x$, 2) $x \leq y, y \leq x \rightarrow x = y$, 그리고 3) $x \leq y, y \leq z \rightarrow x \leq z$. 그리고 기수의 크기는, 다음과 같이 정의합니다. 집합 $A$의 기수가 $\alpha$, 집합 $B$의 기수가 $\beta$ 일 때, $$\alpha \leq \beta \iff \exist f: X \rightarrow Y, f \text{, an injection}$$
위와 같은 방법으로 크기 관계를 정의하였을 때, 크기가 가져야 하는 세 가지 성질이 모두 만족됨을 보일 수 있습니다. 하지만 두 번째 조건인 $x \leq y, y \leq x \rightarrow x = y$는 그 증명이 non-trivial한데요. 이 조건이 성립함을 보여주는 것이 슈뢰더-베른슈타인의 정리입니다. 즉, 두 개의 집합의 기수가 같음을 보이기 위해서는 하나의 집합에서 다른 집합으로 가는 단사 함수를 각각 잡음으로써 보일 수 있다는 의미를 함축하고 있습니다. 다음 포스트에서 보겠지만, 단사 함수 두 개를 잡는 것이, 두 집합 사이의 전단사 함수를 잡는 것 보다 훨씬 간단하고 쉬운 경우가 많아서, 아주 powerful한 정리라고 볼 수 있습니다. 증명에 대해 궁금하신 분은 집합론 기초 교재를 살펴보시면 됩니다만, 많은 양의 사전 지식이 필요하고 증명의 난이도가 높아서 생략하고, 그 결과만을 이용하는 것으로 하겠습니다.

이제 마지막으로 기수의 개념에 대해 간략하게 소개하고 본 글을 마무리하려고 합니다. 기수를 엄밀하게 정의하는 것 또한 상당히 어렵고, 많은 사전 논의가 필요하여 간략하게만 소개하고자 합니다.

우리가 사용하는 자연수, 즉 $1, 2, 3, ...$등의 숫자에는 크게 두 가지 기능이 있습니다. 그 첫 기능은 '순서’를 부여한다는 것이고, 두 번째 기능은 '개수’를 셀 수 있게 해준다는 것입니다. 즉, 집합 $A = \{a, b\}$ 의 원소의 개수는 $2$개이고, 집합 $A$와는 다르지만, 집합 $B = \{x, y\}$의 원소의 개수 또한 $2$개가 될 것입니다. 여기서 중요한 점은, 집합 $A$와 $B$는 다르지만, $A$부터 $B$로의 전단사 함수가 존재한다는 것이 핵심입니다. 즉, 집합 $A$의 기수를 $\alpha$로 두고, 집합 $B$의 기수를 $\beta$로 두었을 때, $A$부터 $B$로의 전단사 함수가 존재하면, 위의 논의로부터 $\alpha = \beta$라고 쓸 수 있다는 것입니다.

앞으로 우리는 이러한 방식으로 집합을 분류하기 시작할 것입니다. 집합을 구성하는 원소의 이름, 혹은 집합의 이름에 구애받는 것이 아닌, 순전히 그 집합에 몇 개의 다른 원소가 포함되어 있는지를 기준으로 분류할 것이고, 같은 크기를 가지는 집합들의 개수를 나타내주는 하나의 ‘수’ 역할을 하는 것을, 그러한 집합들의 '기수(cardinality)'라고 부를 것입니다.

하지만 이러한 방식의 논의는 유한 집합의 경우 전혀 문제가 없으나, '자연수 전체의 집합’의 기수 등을 생각해보면 어떠한 자연수 하나로 해당 집합의 기수를 표현할 수 없음을 깨닫게 되실 겁니다. 다음 포스팅부터는 이러한 무한 세계에서의 기수의 예시를 살펴보고, 여러 특징들을 알아보도록 하겠습니다. 감사합니다 :)