Countable

 안녕하세요. 이번 포스팅은 집합의 Countable 개념에 대해서 설명하려고 합니다.

Countable 개념은 집합론(Set theory)의 창시지안 칸토어(Georg Cantor)가 고안해 낸 개념으로, 무한집합들의 크기(?)를 비교하는 것입니다. 우리가 보통 유한집합들은 원소의 갯수가 유한하므로 일일히 세어서 그 갯수 가지고 크기를 가늠할 수 있습니다. 무한집합들도 그 들 사이에 크기가 있어서 더 큰 집합이 있다는 것입니다. 우리가 잘 알고 있는 자연수와 실수만 비교해봐도, 1, 2, 3, ... 이렇게 듬성듬성 되어 있는 이산(discrete)적인 자연수 집합과, 빽빽하게 들어 차 있는 연속(continuous)적인 실수 집합은 확실히 실수 집합이 더 커 보입니다.

 가산(Countable)의 정의는 말 그대로 '셀 수 있다'는 것입니다. 우리가 물건을 셀 때, 하나 둘 셋 이렇게 세는 것을 수학적으로 표현한 것이죠. 이것은 함수로 표현할 수 있습니다. 자연수 집합 $J=\{1,2,3,\cdots\}$와 일대일 대응(1-1 correspondence)을 만드는 것입니다. 이렇게 두 집합 사이에, 일대일 대응을 만들 수 있으면 두 집합은 equivalent하다고 하고, 기호로

$$A\sim B$$

와 같이 표기합니다. 즉 어떤 set A가 자연수 집합과 일대일 대응관계가 있을 때, 즉 $A\sim J$일 때 집합 A는 countable하다고 말합니다. 그렇지 않으면 uncountable하다고 합니다. 자연수 집합이 무한집합(infinite)이기 때문에, countable set 또한 무한입니다. 일대일 대응관계가 존재한다는 말은 집합 A에 있는 모든 원소들이 자연수에 각각 대응되므로 하나 둘 셋 이렇게 셀 수 있다는 말이 되겠죠. 그러면 인제 이렇게 하나 둘 셋 세면은 집합 A에 있는 원소들에게도 이름을 붙일 수 있습니다.

$$1 \to a_1, 2 \to a_2, \cdots $$

이렇게 자연수 집합에서 어떤 집합 A로 가는 함수를 수열(sequence)으로 볼 수 있습니다. 수열은 $\{a_n\}$로 표시하고 각각의 A의 원소들을 항(term)이라고 합니다. 그러면 Countable set은 J와 일대일 대응이 존재하므로 Countable set은 수열로 표시할 수 있다는 것이죠.

 이제 다음의 정리를 살펴봅시다.

 Theorem. Countable set의 무한 부분집합은 countable하다.

증명의 아이디어는 위에서 언급했듯이 countable set을 수열로 표시할 수 있다는 것입니다. countable set A는 수열 $\{a_n\}$으로 표시할 수 있고, A의 부분집합을 E라고 하면, 이 수열의 항들 중 E에 들어가는 원소 중에 가장 작은 것부터 시작해서 새로운 수열을 만들 수 있습니다. 따라서 countable한 것이죠. 따라서 우리는 무한집합 중에서도 "가장 작은 무한은 Countable한 무한이다"라고 말할 수 있습니다.

 그러면 자연수보다 '많아 보이는' 집합인 유리수는 어떨까요? 유리수는 정수 (m, n)의 쌍으로 나타날 수 있습니다. 정수는 자연수와 일대일 대응이 존재하기 때문에, countable이 됩니다. 이제 n을 고정시키고 n만 생각하면 (m,1)은 정수 집합하고 일대일 대응이 존재하므로 countable이 되죠. (m, 2)도 마찬가지 입니다. 즉, countable set을 무한 개 합집합 한 것이 유리수입니다. 기호로는

$$Q=\bigcup _{n=1}^\infty \{ (m, n) : m\in Z\}$$

로 표시할 수 있습니다. 또는 일반적으로 정수 집합이 아니라도 countable set의 무한 개 합집합에 대해서 논할 수 있습니다. 이 무한 개의 집합 중에 n = 1에 해당하는 첫 번째 집합의 원소를 수열로 쓸 수 있으니까, $\{ x_{1k}\}$로 놓고 첫 번째 행에 적습니다. n = 2인 두 번째 집합을 같은 방법으로 두 번째 행에 적고 반복하면

와 같이 적을 수 있습니다. 이는 모든 Q의 원소들을 포함하겠죠(일반적으로는 모든 무한 개의 countable set의 원소). 이제 화살표 방향으로 '셀 수 있어' 다음과 같은 수열을 만들 수 있씁니다.

$$x_{11},x_{21},x_{12},x_{31},x_{22},x_{13},\cdots$$

그러면 수열로 만들 수 있으니까 countable set이 되겠죠. 따라서 유리수와 자연수는 크기가 같다고 말할 수 있습니다! dense한 성질을 가지고 있는 유리수조차 countable하다는 결론을 얻습니다.

 마지막으로 실수는 어떨까요? 결론부터 말하자면 실수는 uncountable합니다. 실수가 유리수나 자연수 보다는 크기가 더 크다는 것이죠. 즉, 우리가 해석학에서 관심있어 하는 Real number의 성질에 하나를 더 추가시킬 수 있겠네요. 증명은 대략 다음과 같습니다. '1과 0으로만 이루어진 모든 수열들의 집합'을 생각하고, 그 집합이 uncountable임을 보이는 것이죠. 그러면 실수는 이진법으로 나타내면 1과 0으로 나타내어진 수열과 같으므로 실수가 uncountable하다는 것을 알 수 있습니다.

 1과 0으로만 이루어진 모든 수열들의 집합 A의 countable 부분집합 E를 생각합니다. 그러면 E는 countable하니까 E의 원소들을 수열 $s_1, s_2, s_3, \cdots$로 표시할 수 있습니다. 이제 1과 0으로만 이루어진 새로운 수열 $\{ x_n\}$을 하나 생각합니다. 당연히 이 수열도 A의 원소입니다. 이 수열을 어떻게 만드냐 하면, 수열의 k번째 항 $x_k$는 $s_k$의 k번째 항과 반대로 하는 것이죠. 가령,

$$s_1 = 0, 1, 0, 1, 1\cdots \\ s_2 = 1, 1, 0 ,1, 0\cdots \\ s_3 = 1, 0, 0, 0, 0\cdots$$

이라고 하면 $x_1 = 1, x_2 = 0, x_3 = 1$과 같이 잡습니다. 그러면 이 새로운 수열은 E의 어떤 원소와도 다르기 때문에 E는 A의 진부분집합(proper subset)입니다. 어떤 countable 부분집합을 가져와도 이런 일이 발생하기 때문에, A는 uncountable입니다. 만약 A가 countable이라면 A는 A의 진부분집합이 되어 모순이 발생합니다.

 Cantor가 처음 발견한 이 방법으로 무한집합들에게도 크기가 있다는 생각이 생겨나게 되었고, 멱집합(power set) 등을 이용해 집합의 크기를 계속 늘려나갈 수 있다는 것을 알아냈습니다. 집합의 크기가 계속 늘어난다는 말은 uncountable set, 즉 실수와도 일대일 대응 관계가 존재하지 않도록 더 큰 set을 만들 수 있다는 뜻입니다. 그래서 결국 uncountable set중에 가장 작은 것은 무엇인가? 하는 질문에 도달하게 되었고 실수보다 크기가 작은 uncountable한 집합이 있을까 하는 생각이 바로 연속체 가설입니다.

 다음번 포스팅 때는 해석학의 무대인 Metric Space와 Compact Set을 살펴보려고 합니다. 읽어주셔서 감사합니다.