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

어떤 집합이 가산, 비가산임을 증명하는 법

1편에서는 가산, 비가산집합과 집합의 가산성에 대한 기본 성질에 대해 알아보았으니, 이제 여러 가지 집합들이 가산인지 비가산인지 살펴보자. 이 글에서 살펴볼 집합은 정수 전체의 집합 \(\mathbb{Z}\), 유리수 전체의 집합 \(\mathbb{Q}\), 그리고 실수 전체의 집합 \(\mathbb{R}\)이다.

가산집합임을 보이는 법

어떤 집합 \(S\)가 가산임을 보이기 위해서는 어떻게 해야 할까? 1편에 나왔던 가산집합의 정의를 그대로 사용하면 된다. 즉 \(S\)에서 자연수 전체의 집합 \(\mathbb{N}\)으로 가는 일대일함수가 존재한다면 \(S\)는 가산이 된다. 이 경우 가장 많이 쓰이는 증명 방법은 이러한 일대일함수 하나를 만드는 것이다. 이러한 증명 방법을 예제를 통한 증명(proof by construction)이라고 한다.

비가산집합임을 보이는 법

그렇다면 \(S\)가 비가산임을 보이기 위해서는 어떻게 해야 할까? 이 때는 \(S\)의 원소들을 하나, 둘, 셋, … 하며 세는 방법이 없음을 보여야 하기 때문 예제를 통한 증명이 사실상 불가능하다. 이 경우에는 귀류법(proof by contradiction)을 많이 사용한다. \(S\)의 원소들을 하나, 둘, 셋, … 하며 세는 방법이 있다고 가정하고, 이를 이용해 수학적으로 발생할 수 없는 상황(모순)을 만들어내는 것이다.

\(\mathbb{Z}\)는 가산집합

\(\mathbb{Z}\)는 가산집합이다. 앞서 살펴보았듯이 이를 증명하기 위해서는 \(\mathbb{Z}\)에서 \(\mathbb{N}\)으로 가는 일대일함수 하나를 만들면 된다. 여기에서 문제가 발생하는데, \(\mathbb{Z}=\{\cdots, -2, -1, 0, 1, 2, \cdots\}\)와 같이 양쪽으로 무한대로 뻗어 있지만 \(\mathbb{N}=\{1, 2, 3, \cdots\}\)와 같이 한 쪽 끝은 막혀 있고 한 쪽으로만 뻗어 있다는 것이다. 이 상태로는 \(\mathbb{Z}\)에서 \(\mathbb{N}\)으로 가는 일대일함수를 만들기 힘들어 보인다.

이를 해결하기 위해서는 \(\mathbb{Z}\)의 원소를 적당히 재배열하여 \(\mathbb{N}\)과 같이 한 쪽으로만 뻗어 있는 형태로 만들어야 한다. 다음과 같이 \(\mathbb{Z}\)의 원소를 나열해 주면 된다.

$$ \mathbb{Z}=\{0, -1, 1, -2, 2, \cdots\} $$

이제 이 상태로 처음부터 각각 \(1, 2, 3, 4, 5, \cdots\)에 대응시켜주면 \(\mathbb{N}\)으로 가는 일대일함수가 된다.

\(\mathbb{Z}\)에서 \(\mathbb{N}\)으로 가는 일대일함수. 이렇게 \(\mathbb{Z}\)의 모든 원소를 하나하나 세는 방법이 있기 때문에 \(\mathbb{Z}\)는 가산집합이라고 할 수 있다.

이러한 함수 \(f\)를 수식으로 나타내면 다음과 같다. 이는 일대일함수가 된다는 사실을 쉽게 알 수 있다.

$$ f(n)=\left\{\begin{array}{ll} 2n+1 & (n\geq0) \\ -2n & (n<0) \end{array}\right. $$

\(\mathbb{Q}\)는 가산집합

\(\mathbb{Z}\)가 가산임을 보일 때와 마찬가지로 \(\mathbb{Q}\)가 가산임을 보이기 위해서는 \(\mathbb{Q}\)의 원소들을 적당히 재배열하여 어느 한 원소부터 시작하여 한쪽으로만 무한히 뻗어 나가는 형태를 만들면 된다. \(\mathbb{Q}\)가 가산임을 보이기 위해 일단 유리수의 정의부터 살펴보도록 하자.

\(\mathbb{Q}\)의 정의

\(\mathbb{Q}\)는 다음과 같이 정의된다.

$$ \mathbb{Q}=\left\{\frac{n}{m}:n, m\in\mathbb{Z}, m\neq0\right\} $$

\(\mathbb{Z}^2\)로의 확장

\(\mathbb{Q}\)에서 \(\mathbb{Z}^2\)로의 대응

\(\mathbb{Q}\)를 정의하는 데에는 두 개의 정수가 쓰인다. 그러면 \(\mathbb{Q}\)의 각 원소들을 다음과 같이 분자, 분모를 상징하는 정수의 순서쌍으로 생각할 수 있을 것이다.

$$\begin{array}{rcl}1/2&\rightarrow&(1,2)\\-4/7&\rightarrow&(-4,7)\\1&\rightarrow&(1,1)\\0&\rightarrow&(0,1)\end{array}$$

이렇게 생각하면 하나의 유리수에 대응될 수 있는 순서쌍의 수는 매우 많다. 예를 들어 \(1/2\)는 \((1,2)\)에도 대응될 수 있지만 \((-1,-2)\)에도, \((2,4)\)에도, \((3,6)\)에도 대응될 수 있다. 또한 \(0\)은 \((0, 1\))에도 대응될 수 있지만 \((0, -1\))에도, \((0, 2\))에도, \((0, 999\))에도 대응될 수 있다.

반대로 하나의 정수 순서쌍은 분모가 0인 경우를 제외하면 반드시 하나의 유리수에 대응된다. 예를 들어 유리수 \(1/2\)는 \((1, 2)\), \((-1, -2)\), \((2, 4)\), \((3, 6)\)에 모두 대응될 수 있지만 \((1, 2)\)는 오로지 하나의 유리수 \(1/2\)에 대응된다. \((-1, -2)\), \((2, 4)\), \((3, 6)\)도 마찬가지이다. 분모가 0인 경우는 어떤 유리수에도 대응되지 않을 것이다.

지금까지의 대응 관계를 그림으로 나타내면 다음과 같다.

\(\mathbb{Q}\)와 \(\mathbb{Z}\)의 대응 관계.

크기 비교

이제 이렇게 생각해보자. 유리수의 집합 \(\mathbb{Q}\)와 정수의 순서쌍들을 모두 모아 놓은 집합

$$ \mathbb{Z}^2=\{(x, y):x, y\in\mathbb{Z}\} $$

둘 중 어느 것이 더 크다고 할 수 있을까? 물론 두 집합을 비교해 봤을 때 어느 한 쪽이 다른 쪽에 포함되지는 않는다. 하지만 \(\mathbb{Q}\)의 각 원소를 대응 가능한 \(\mathbb{Z}^2\)의 수많은 원소들 중 하나씩에만 대응시킨다면 아래 그림처럼 \(\mathbb{Q}\)에서 \(\mathbb{Z}^2\)의 적당한 부분집합으로 가는 일대일대응을 만들 수 있다.

\(\mathbb{Q}\)의 각 원소를 대응 가능한 \(\mathbb{Z}^2\)의 수많은 원소들 중 하나에 대응시킨 그림. 이를 통해 \(\mathbb{Q}\)의 크기가 \(\mathbb{Z}^2\)보다 크지 않음을 이해할 수 있다.

즉 \(\mathbb{Q}\)는 \(\mathbb{Z}^2\)의 어떤 부분집합 \(S\)와 같은 것으로 해석할 수 있다.

\(\mathbb{Q}\)에서 \(\mathbb{Z}^2\)의 부분집합 \(\mathbb{S}\)로의 일대일대응. \(\mathbb{Q}\)가 \(\mathbb{Z}^2\)보다 크지 않은 집합이므로 (\mathbb{Z}^2\)가 가산이라면 \(\mathbb{Q}\)도 가산이 된다.

따라서, \(\mathbb{Z}^2\)가 가산임을 보인다면 1편부분집합과 가산성 (1)에서 살펴보았던 성질에 의해 \(S\)도 가산이 되고, \(\mathbb{Q}\)는 \(S\)와 같은 것으로 해석할 수 있으므로 \(\mathbb{Q}\)도 가산이 된다. 비록 \(\mathbb{Q}\)가 \(\mathbb{Z}^2\)의 부분집합인 것은 아니지만, 적당한 \(\mathbb{Z}^2\)의 부분집합에 일대일대응되므로 비슷한 뉘앙스로 이해할 수 있게 되는 것이다.

\(\mathbb{Z}^2\)는 가산집합

이제 마지막으로 \(\mathbb{Z}^2\)가 가산임을 보이면 증명이 끝난다. 사실 \(\mathbb{Z}^2\)는 좌표평면 위 모든 격자점들의 집합이다. 따라서 \(\mathbb{Z}^2\)가 가산이라는 것은 적당한 점에서 출발하여 좌표평면 위의 모든 격자점들을 하나하나 셀 수 있는 방법이 존재한다는 것이다.

아래 그림과 같이 원점을 출발로 하여 시계방향으로 격자점들을 순회한다면 좌표평면 위의 모든 격자점들을 셀 수 있고, \(\mathbb{Z}^2\)는 가산이 된다.

좌표평면 위의 모든 격자점들을 순회하는 방법. 이를 통해 \(\mathbb{Z}^2\)에서 \(\mathbb{N}\)으로의 일대일함수가 존재함을 보일 수 있다.

정리

지금까지 길고 긴 과정을 거쳐 \(\mathbb{Q}\)가 가산집합임을 증명하였다. 이렇게 긴 증명을 공부할 때는 항상 큰 그림이 무엇인지 이해해야 한다. \(\mathbb{Q}\)가 가산임을 보이는 과정을 정리하며 이 절을 마치고자 한다.

  1. 각각의 유리수는 정수의 순서쌍에 대응시킬 수 있다. 이때 각각의 유리수에 대응시킬 수 있는 순서쌍의 수는 매우 많다.
  2. 각 유리수를 대응시킬 수 있는 수많은 정수의 순서쌍들 중 하나씩에만 대응시킨다면 유리수의 집합 \(\mathbb{Q}\)에서 정수 순서쌍의 집합 \(\mathbb{Z}^2\)의 한 부분집합 \(S\) 사이의 일대일대응을 만들 수 있다.
  3. \(\mathbb{Z}^2\)는 가산이다.
  4. 따라서 그의 부분집합인 \(S\)도 가산이고, 이와 일대일대응되는 \(\mathbb{Q}\)도 가산이다.

\(\mathbb{R}\)은 비가산집합

우리는 지금까지 \(\mathbb{Z}\), \(\mathbb{Q}\)가 가산임을 보였지만, 그보다 한 단계 위인 실수 전체의 집합 \(\mathbb{R}\)은 가산집합이 아니다.

증명

\(\mathbb{R}\)이 비가산집합임을 보이기 위해 열린 구간 \((0, 1)\)을 사용할 것이다. 만약 \((0, 1)\)이 비가산이라면, \((0, 1)\subseteq\mathbb{R}\)이므로 1편의 부분집합과 가산성 (2)에서 살펴본 성질로 인해 \(\mathbb{R}\)도 비가산이 된다. 따라서 \((0, 1)\)이 비가산집합임을 보이면 증명이 끝난다.

\((0, 1)\)은 비가산

귀류법으로 \((0, 1)\)이 가산집합이라고 가정하자. 이는 \((0, 1)\)의 원소를 하나, 둘, 셋, … 하며 셀 수 있음을 의미한다. 따라서 \((0, 1)\)을 원소나열법으로 다음과 같이 쓸 수 있다.

$$ (0, 1)=\{x_1, x_2, x_3, \cdots, x_n, \cdots\} $$

그런데 각각의 \(x_i\)들은 0과 1 사이의 수이므로, 소수(decimal)로 나타내면 다음과 같이 쓸 수 있다.

$$ \begin{array}{rcl} x_1 & = & x_{11}x_{12}x_{13}\cdots x_{1n}\cdots \\ x_2 & = & x_{21}x_{22}x_{23}\cdots x_{2n}\cdots \\ x_3 & = & x_{31}x_{32}x_{33}\cdots x_{3n}\cdots \\ & \vdots & \\ x_n & = & x_{n1}x_{n2}x_{n3}\cdots x_{nn}\cdots \\ & \vdots & \end{array} $$

이때 새로운 수 \(x’\)을 정의할 건데, 이 \(x’\)은 원래 집합인 \((0, 1)\)에 있어야 하지만 어떤 \{x_i\}와도 달라 \((0, 1)\)에 존재하지 않는, 모순을 발생시키는 역할을 하는 수이다. 우리는 \(x’\)을 다음과 같이 똑같은 소수 표기로 정의할 것이다.

$$ x’=0.x_1’x_2’x_3’\cdots x_n’\cdots $$

이때 각각의 \(x_i’\)을 다음과 같이 정의해보자.

$$ x_i’=\left\{\begin{array}{ll} 2  & (x_{ii}=1) \\ 1 & (x_{ii}\neq1) \end{array}\right. $$

그러면 다음과 같은 두 가지 사실을 얻는다.

  1. 모든 자연수 \(i\)에 대해 \(x_i’\neq x_{ii}\)
  2. \(0<x'<1\)

1번에 의해 \(x’\)은 \(x_i\)와 소수점 아래 \(i\)번째 자리가 다르므로 \(x_i\)와 다르다. 이 사실이 모든 자연수 \(i\)에 대해 성립하므로, \(x’\)은 어느 \(x_i\)와도 같지 않고, 그것이 \((0, 1)\)의 원소 전부라고 가정했으므로 \(x’\)은 \((0, 1)\)의 원소가 아니다. 하지만 2번에 의해 \(x’\)은 \((0, 1)\)의 원소여야 한다. 수학적으로 발생할 수 없는 일, 즉 모순이 발생하였다.
왜 이런 일이 발생한 것일까? 지금까지의 논리에는 틀린 게 없으므로 문제는 맨 처음의 가정에 있다. 즉 \((0, 1)\)이 가산이라는 가정 자체가 틀렸다고 볼 수 있는 것이다. 따라서 \((0, 1)\)은 비가산이다.

Leave a Comment