실수 집합이 비가산임을 증명하는 두 가지 방법

By | October 12, 2016

\(E\)가 집합이고 \(E\)로부터 \(\mathbb{N}\)에로의 일대일 함수가 존재할 때 \(E\)를 가산집합(countable set)이라고 부른다. 또한 가산집합이 아닌 집합을 비가산집합(uncountable set)이라고 부른다. 즉 임의의 집합은 원소의 개수에 따라 다음과 같이 분류할 수 있다.

  • 유한집합
  • 무한인 가산집합(가부번집합)
  • 비가산집합

(물론 비가산집합은 집합의 기수(cardinality)에 따라 여러 가지로 구분할 수 있지만 여기서 논하는 바는 아니다.)

자연수 집합 \(\mathbb{N},\) 정수 집합 \(\mathbb{Z},\) 유리수 집합 \(\mathbb{Q}\)는 모두 가산집합이다. 그러나 실수 집합 \(\mathbb{R}\)는 비가산집합이다. 여기서는 \(\mathbb{R}\)가 비가산집합임을 증명하자.

열린구간 \(I = (0,~1)\)은 실수 집합 \(\mathbb{R}\)에 포함된다. 그러므로 \(I\)가 비가산집합임을 증명하면 \(\mathbb{R}\)가 비가산집합임이 증명된다. 일단 \(I\)는 무한집합 \[\left\{ 2^{-n} ~|~ n \in \mathbb{N} \right\}\] 을 포함하므로 \(I\) 또한 무한집합이다. 따라서 \(I\)는 무한 가산집합이거나 비가산집합이다. 이제 두 가지 방법을 통해 \(I\)가 비가산집합임을 증명하자.

Cantor의 대각법을 이용한 증명

결론에 반하여 \(I\)가 가산집합이라고 가정하자. 그러면 \(I\)는 가산인 무한집합이므로 \(I\)의 원소를 다음과 같이 한 줄로 빠짐 없이 나열할 수 있다.

\(x_1 ,\)  \(x_2 ,\)  \(x_3 ,\)  \( \cdots , \)  \(x_n ,\)  \( \cdots \)

\(x_n\)을 10진 소수 전개로 나타냈을 때 소수점 아래 \(m\)째 자리 숫자를 \(x_{(n,m)}\)이라고 나타내기로 하자. 단, \(x_n\)이 유한소수인 경우 마지막 자리의 숫자에서 \(1\)을 빼고 그 밑으로 \(9\)를 이어 적음으로써 \(x_n\)을 무한소수로 나타내기로 하자. 예컨대 \(0.3\)은 \(0.2999 \cdots \)로 나타낸다.

이제 임의의 자연수 \(n\)에 대하여 \(y_n\)을 다음과 같이 정의하자. \[y_n := \begin{cases} 1~~ &\mbox{if} ~~ x_{(n,n)} \ne 1 \\ \\ 2 ~~ &\mbox{if} ~~ x_{(n,n)} = 1 \end{cases} \] 그리고 정수 부분이 \(0\)이고 소수점 아래 \(n\)째 자리의 숫자가 \(y_n\)인 10진수를 \(y\)라고 하자. 즉 \(y\)는 다음과 같이 나타나는 수이다. \[y ~=~ 0 ~.~ y_1 ~ y_2 ~ y_3 ~ \cdots \tag{1} \] 그러면 임의의 자연수 \(n\)에 대하여 \(y_n \ne x_{(n,n)}\)이므로 \(y \ne x_n \)이다. 즉 \(y\)와 \(x_n\)은 소수점 아래 \(n\)째 자리의 숫자가 다르므로 서로 다른 수이다. 그런데 \(x_n\)은 \(I\)에 속하는 모든 수를 나열한 것이므로 \(y \notin I \)이다. 한편 (1)에 의하여 \(0 < y < 1 \)이다. 이것은 모순이므로 \(I\)의 원소를 한 줄로 나열하는 것은 불가능하다. 즉 \(I\)는 비가산집합이다.

실수계의 완비성을 이용한 증명

결론에 반하여 \(I\)가 가산집합이라고 가정하자. 그러면 \(I\)는 가산인 무한집합이므로 일대일 대응 \(f : \mathbb{N} \to I\)가 존재한다. 실수계의 조밀성에 의하여

\( f (1) \notin \left( a_1 ,~ b_1 \right) \)  그리고  \( 0 < a_1 < b_1 < 1 \)

을 만족시키는 \(a_1 \)과 \(b_1 \)이 \(I\)에 존재한다.

이제 \(n\)이 자연수이고 \(a_n \)과 \(b_n \)이 실수이며 \[0 < a_n < b_n < 1 \] 이 성립한다고 가정하자. 그러면 실수계의 조밀성에 의하여 \[f(n+1) \notin \left( a_{n+1} ,~ b_{n+1} \right) \tag{2} \] 그리고 \[0 < a_n < a_{n+1} < b_{n+1} < b_n < 1 \] 을 만족시키는 실수 \(a_{n+1}\)과 \(b_{n+1}\)이 \(I\)에 존재한다.

이제 임의의 자연수 \(n\)에 대하여 \(a_n\)과 \(b_n\)이 귀납적으로 정의되었다. 특히 (2)에 의하여 임의의 \(n\)에 대하여 다음을 얻는다. \[f(n) \notin \left( a_n ,~ b_n \right) \] 집합 \(A := \left\{ a_n ~|~ n \in \mathbb{N} \right\}\)은 공집합이 아니고 위로 유계이므로 상한 \[r := \mathrm{s u p} \left\{ a_n ~|~ n \in \mathbb{N} \right\}\] 이 존재한다. 마찬가지로 집합 \(B := \left\{ b_n ~|~ n \in \mathbb{N} \right\}\)은 공집합이 아니고 아래로 유계이므로 하한 \[s := \mathrm{i n f} \left\{ b_n ~|~ n \in \mathbb{N} \right\}\] 이 존재한다. \(b_1\)은 \(A\)의 상계이므로 \[0 < a_1 \le r \le b_1 < 1 \] 이 성립한다. 즉 \(r \in I \)이다. 마찬가지로 \(s \in I\)이다.

임의의 \(n\)에 대하여 \(b_n\)은 \(A\)의 상계이므로 임의의 \(n\)에 대하여 \(r \le b_n \)이다. 또한 \(r\)는 \(B\)의 하계이므로 \(r \le s\)이다.

\( f(n) = r\)를 만족시키는 자연수 \(n\)이 존재한다고 가정하자. 그러면 \[f(n) \notin \left( a_n ,~ b_n \right) \tag{3} \] 이 성립한다. 그런데 \(a_n < r < b_n \)이므로 (3)은 모순이다. 따라서 \( f(n) = r\)를 만족시키는 자연수 \(n\)은 존재하지 않는다. 이것은 \(f\)가 \(\mathbb{N}\)으로부터 \(I\)에로의 일대일 대응이라는 사실에 모순이다. 그러므로 \(\mathbb{R}\)는 비가산집합이다.

추가로 조금 독특한 증명을 하나 소개한다.

Baire의 범주를 이용한 증명

\(\mathbb{R}\)가 가산집합이라고 가정하자. 명백히 \(\mathbb{R}\)는 유한집합이 아니므로 \(\mathbb{R}\)의 원소를 다음과 같이 한 줄로 빠짐 없이 나열할 수 있다.

\(x_1 ,\)  \(x_2 ,\)  \(x_3 ,\)  \( \cdots , \)  \(x_n ,\)  \( \cdots \)

\(\mathbb{R}\)가 고립점을 갖지 않으므로 임의의 자연수 \(n\)에 대하여 \(\left\{ x_n \right\}\)은 어느 곳에서도 조밀하지 않다. 즉 \(\mathbb{R}\)는 어느 곳에서도 조밀하지 않은 집합들의 가산합집합으로 표현되므로 \(\mathbb{R}\)는 \(\mathbb{R}\)에서 제 1 범주의 집합이다. 그러나 \(\mathbb{R}\)는 공집합이 아닌 완비거리공간이므로 Baire의 범주 정리에 의하여 \(\mathbb{R}\)는 \(\mathbb{R}\)에서 제 2 범주의 집합이다. 이것은 모순이므로 \(\mathbb{R}\)는 비가산집합이다.

그러나 이와 같은 증명 방법은 좋지 않다. 왜냐하면 Baire의 범주 정리를 증명하기 위해 실수계의 성질을 너무 많이 사용하기 때문이다.

Leave a Reply