가산집합(Countable Set)과 비가산집합(Uncountable Set) (1)

직관적 의미

가산집합

가산집합(可算集合)이란 무엇일까? 한자 뜻 그대로 해석해본다면 셈하는 게 가능하다, 즉 셀 수 있는 집합이라는 뜻이다. 예를 들어 아래의 집합을 생각해보자.

$$ A=\{1, 2, 3, 4, 5\} $$

집합 \(A\)의 원소는 다섯 개로, 하나, 둘, 셋, 넷, 다섯 하며 셀 수 있다. 이번에는 적당한 자연수 \(n\)에 대해, 다음 집합을 생각해보자.

$$ B=\{1, 2, \cdots, n\} $$

\(n\)의 값에 관계없이 \(B\)의 원소도 하나, 둘, … 하고 셀 수 있다. 다음 집합은 어떨까?

$$ C=\mathbb{N}=\{1, 2, \cdots, n, \cdots\} $$

\(C\)가 앞의 집합들과 달리 무한집합이다. 하지만 우리는 \(C\)의 원소들도 하나, 둘, … 하며 셀 수 있다. 단지 세는 데에 끝이 없을 뿐이다.

지금까지 살펴본 집합들은 모두 가산집합으로, 이는 그 원소들을 (세는 데 끝이 있던 없던) 하나, 둘, … 하면서 셀 수 있는 집합을 의미한다.

비가산집합

이제 다음 집합을 살펴보자.

$$ D=[0, 1]=\{x:0\leq x\leq 1\} $$

\(D\)의 모든 원소를 하나, 둘, … 하고 셀 수 있을까? 여기부터는 이야기가 조금 달라진다. 가령 \(D\)의 원소들을 작은 것부터 차근차근 세기 위해서 첫 원소를 0이라 하고, 두 번째 원소를 \(\epsilon\neq0\)이라고 했다 치자. 여기서 문제는 0과 \(\epsilon\) 사이에 엄청나게 많은 \(D\)의 원소가 있다는 것이다. 그것들을 세기 위해 세 번째 원소를 \(\epsilon/2\)로 잡았다면, 다시 0과 \(\epsilon/2\) 사이에는 엄청나게 많은 \(D\)의 원소가 존재하게 된다. 이러한 과정은 무한히 반복되고, 결국 \(D\)의 원소들은 하나, 둘 하며 세기에는 너무 많다는 결론을 내리게 될 것이다. 이렇게 원소들을 하나, 둘, … 하면서 세기에는 너무 많아 셀 수 없는 집합비가산집합이라고 한다.

정의

지금까지 가산, 비가산집합에 대한 직관적인 의미를 살펴보았는데, 이를 수학적으로 정의하기 위해서는 원소들을 “센다”는 개념을 어떻게 정의할 수 있을 지 생각해보아야 할 것이다. 그에 대한 해답은 다름 아닌 “하나, 둘, …”에 있다. 무슨 말인가 하면, 우리는 지금까지 \(A\), \(B\), \(C\)의 원소들을 세는 과정에서 무의식적으로 “하나(1), 둘(2), …” 하며 자연수의 일부 또는 전체에 대응시켰다는 것이다. 다시 말하자면, 우리가 \(A\), \(B\), \(C\)를 가산이라고 부를 수 있는 이유는 각각의 원소들을 자연수의 일부 또는 전체에 겹치지 않게 대응시킬 수 있기 때문이다.

\(A, B, C\)에서 \(\mathbb{N}\)으로의 대응을 나타낸 그림. \(A, B, C\)는 모두 \(\mathbb{N}\)으로의 일대일대응이 존재하기 때문에 모두 가산집합이다.

이 사실을 나타내는 수학 용어가 바로 일대일함수(단사함수)이다. 따라서 가산집합에 대한 정의를 다음과 같이 내릴 수 있을 것이다.

가산집합(countable set)이란 자연수 집합으로의 일대일함수가 존재하는 집합이다.

이를 정의한 순간 비가산집합에 대한 정의는 자연스럽게 내려진다.

비가산집합(uncountable set)이란 자연수 집합으로의 일대일함수가 존재하지 않는 집합이다.

기본 성질

수학자들이 새로운 개념을 정의한 후 가장 먼저 하는 일은 이와 관련된 기본적인 성질들을 찾고 증명하는 것이다. 이 글에서도 새로운 개념을 정의했으니 몇 가지 기본적인 성질들을 알아보자.

유한집합은 가산집합

어떤 유한집합 \(S\)의 원소의 개수가 \(n\)개라고 하자. \(S\)의 원소들을 임의로 일렬로 나열한 후 차례대로 1부터 \(n\)까지의 번호를 붙이면 그것이 바로 \(S\)에서 \(\mathbb{N}\)으로의 일대일함수가 된다. 따라서 유한집합은 가산집합이다. 사실 직관적으로 유한집합이면 당연히 원소들을 하나하나 셀 수 있고, 더불어 세는 과정은 언젠가 반드시 끝나게 된다.

부분집합과 가산성 (1)

만약 \(A\)가 가산집합이고 \(B\subseteq A\)이면 \(B\)도 가산일까? 직관적으로 \(A\)의 원소들을 셀 수 있으면 그것보다 작거나 같은 집합의 원소들은 당연히 셀 수 있으므로 \(B\)도 가산이 될 것 같고, 이 명제는 실제로도 참이다. 즉 가산집합의 부분집합은 항상 가산집합이다.

증명

증명도 굉장히 직관적이다. 위에서 사용한 notation을 그대로 빌려온다면, 우리에게 주어진 것은 \(A\)에서 \(\mathbb{N}\)으로 가는 일대일함수가 \(f\)가 있다는 것이고, 이를 통해 \(A\)의 부분집합 \(B\)에서 \(\mathbb{N}\)으로 가는 일대일함수가 있음을 보이면 된다. 이를 위해 함수 \(g\)를 다음과 같이 정의한다.

$$ g:B\rightarrow A,\quad g(x)=x $$

어차피 \(B\)는 \(A\)의 부분집합이므로 \(B\)의 각 원소를 \(A\)의 원소로 생각하겠다는 말이다. 이렇게 정의하면 \(f\circ g\)가 \(B\)에서 \(\mathbb{N}\)으로 가는 일대일함수가 된다.

합성함수 \(g circ f\)의 그림. \(g\)는 모든 원소를 자기 자신으로 보내는 함수이고 \(f\)는 일대일함수이므로 \(g\circ f\)도 일대일함수가 되고, 따라서 \(B\)는 가산집합이 된다.

이를 증명하기 위해서는 일대일함수의 정의를 사용하면 된다. 우리는 \(B\)의 원소 \(x, y\)에 대해

$$ (f\circ g)(x)=(f\circ g)(y) \Longrightarrow x=y $$

임을 보이면 된다. 우선 \(g(x)=x, g(y)=y\)이므로 위 명제는

$$ f(x)=f(y) \Longrightarrow x=y $$

가 되는데, 이는 \(f\)가 일대일함수이므로 당연히 성립한다. 따라서 \(f\circ g\)는 일대일함수이다.

부분집합과 가산성 (2)

이번에는 반대로 \(A\)가 비가산집합이고 \(B\)가 \(A\)보다 큰 집합, 즉 \(B\supseteq A\)라면 \(B\)도 비가산이 될까? 이번에도 정답은 “맞다”이다. 사실 이는 바로 위에서 증명한 명제의 대우이며, 직관적으로도 성립한다는 것을 쉽게 알 수 있다. 안 그래도 \(A\)의 원소도 너무 많아 셀 수 없는데, 그것보다 큰 집합인 \(B\)의 원소는 셀 수 없어야 하는 게 당연해 보인다. 즉 비가산집합의 초집합(superset)은 비가산집합이다.

다음 편인 가산집합과 비가산집합 (2)에서는 정수, 유리수, 실수의 집합이 가산인지 비가산인지 알아본다.

Leave a Comment