[계산이론] #07. Countable Set

Countable Set

이번 글은 조금 수학적인 이야기로 시작할 텐데요, 다들 아시겠지만 간단한 정의부터 먼저 짚고 넘어갑시다. 아래와 같이  $A$에서 $B$로의 함수 $f$가 있다고 합시다.

이때, 함수 $f$가 $\forall a_1, a_2 \in A\; s.t\; a_1\neq a_2 \to f\left ( a_1 \right )\neq f\left ( a_2 \right )$를 만족하면 $f$를 One-to-one, Injective, 한국어로는 단사라고 부릅니다. 수학적 표현을 말로 고치면 $A$의 모든 원소가 $B$의 서로 다른 원소에 대응됨을 의미합니다.

또, 함수 $f$가 $\forall b\in B,\exists a\in A \; s.t\;  f\left ( a \right )=b$를 만족하면 $f$를 Onto, Surjective, 한국어로는 전사라고 부릅니다. 말로 고치면 $B$의 모든 원소가 대응되는 값이 $A$에 있음을 의미합니다.

마지막으로 함수 $f$가 단사이면서 전사일 경우, $f$를 Bijection, 한국어로는 전단사라고 부릅니다.

 

여기서  만약 $A$와 $B$가 전부 유한한 집합이면서 $A$에서 $B$로의 전단사 함수 $f$가 존재한다면, $A$와 $B$는 같은 개수의 원소를 갖는다는 사실을 쉽게 알 수 있습니다. 근데 재밌는 사실은 위 사실은 두 집합이 무한 집합이어도 성립한다는 것입니다.

2개의 무한 집합 $\mathbb{N}=\left\{1, 2, 3,\cdots \right\}$과 $\mathbb{N}_0=\left\{0, 1, 2,\cdots \right\}$이 존재한다고 생각합시다. 이 두 집합은 같은 크기를 가질까요? 그렇습니다. 왜냐하면 $\mathbb{N}$에서 $\mathbb{N}_0$으로의 전단사 함수 $f\left ( n \right )=n-1$이 존재하기 때문이죠.

 

만약 집합 $A$가 유한 집합이거나, $\left|A \right|=\left|\mathbb{N} \right|$일 경우 $A$를 Countable이라고 합니다.

예를 들어 모든 정수의 집합 $\mathbb{Z}$는 Countable입니다. 이를 증명하기 위해서는 $\mathbb{N}$에서 $\mathbb{Z}$로의 전단사 함수가 존재함을 보여야 합니다. 대표적인 예시로 $\mathbb{N}$의 원소 $n$에 대해서 $n$이 짝수일 경우 $\frac{n}{2}$, $n$이 홀수일 경우 $-\frac{n-1}{2}$를 출력하는 함수가 있겠죠? 따라서 $\mathbb{Z}$은 Countable입니다.

다르게 생각하면, $\mathbb{Z}=\left\{0, 1, -1, 2, -2, 3, -3, \cdots \right\}$처럼 $\mathbb{Z}$를 나열할 수 있기 때문에 $\mathbb{Z}$가 Countable이라고 말할 수도 있을 것입니다.

 

같은 방법으로 생각해서, 유리수의 집합 $\mathbb{Q}$ 역시 Countable입니다. 먼저 아래와 같은 Cartesian Product $\mathbb{N} \times \mathbb{N}$이 Countable임을 알 수 있습니다.

먼저 두 수의 합이 2인 순서쌍을 먼저 나열합니다. (1, 1)

그리고 나서 두 수의 합이 3인 순서쌍을 나열합니다. (1, 1), (1, 2), (2, 1)

그다음에는 두 수의 합이 4인 순서쌍을 나열합니다.  (1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1)

이렇게 $\mathbb{N} \times \mathbb{N}$의 모든 원소를 나열한 List를 만들 수 있기 때문에, $\mathbb{N}$에서 $\mathbb{N} \times \mathbb{N}$으로의 전단사 함수가 존재함을 확인할 수 있습니다.

이제 위 집합의 원소 (p, q)를 분수 $\frac{p}{q}$에 대응시키면 아래와 같은 List가 만들어집니다.

$$\left\{\frac{1}{1}, \frac{1}{2},\frac{2}{1},\frac{1}{3}, \frac{2}{2},\frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \cdots \right\}$$

여기서 이미 $\frac{2}{2}$는 앞에 나왔던 $\frac{1}{1}$과 중복이고, $\frac{2}{4}$는 $\frac{1}{2}$과 중첩이므로, 이런 것들만 삭제해 주면 아래와 같습니다.

$$\left\{\frac{1}{1}, \frac{1}{2},\frac{2}{1},\frac{1}{3}, \frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \cdots \right\}$$

따라서 위와 같이 원소들을 나열할 수 있다는 사실은 $\mathbb{N}$에서 $\mathbb{Q}$로의 전단사 함수가 존재함을 의미하므로, $\mathbb{Q}$ 역시 Countable Set입니다.

 

Cantor's Diagonalization Principle

그럼 이제 Uncountable한 무한집합의 예시를 한번 보겠습니다. $\mathbb{N}$에서 $\left\{0, 1\right\}$으로의 함수의 집합 $B$를 한번 생각해 보겠습니다.

이해를 돕기 위해 예시를 들자면, $n$이 짝수이면 0, 홀수이면 1을 출력하는 함수 $g$가 있다고 생각합시다. 이 함수는 문자열 10101010... 에 대응됩니다.

그러면 이 함수 $g$는 $B$의 원소가 됩니다.

이제부터 이러한 집합 $B$가 Uncountable임을 증명할 건데요, $B$가 Countable 하다고 가정한 뒤 모순임을 보여서 증명해 보도록 하겠습니다. $B=\left\{b_1, b_2, b_3, \cdots \right\}$ 라고 두겠습니다. 이를 표로 나타내면 대략적으로 이러한 모습이겠죠?

함수 $b_1$은 아까 예시로 들었던 $g$와 같은 함수이며, 1010101010... 에 대응됩니다. 함수 $b_2$는 그냥 임의로 정한 함수입니다. 001001101... 에 대응됩니다. 이렇게 $B$의 원소를 나타낸 표에서, 정확히 대각선에 위치한 원소들만 한번 보겠습니다.

101100011... 이 문자열을 뒤집으면 010011100... 이 됩니다. 여기서 생각을 해봅시다. 010011100... 에 대응되는 함수가 위의 표에 존재할 수 있을까요? 불가능합니다.

왜? 010011100... 과 $b_1$에 대응되는 문자열을 비교해 보면 첫번째 원소가 항상 다릅니다. 대각선에 있는 원소를 나열한 101100011...의 첫번째 원소는 $b_1$의 첫번째 원소와 항상 같은데, 이 문자열을 뒤집어서 010011100...이 된 것이기 때문이죠. 마찬가지로, 010011100...과 $b_2$에 대응되는 문자열을 비교해보면 두번째 원소가 항상 다르고, $b_3$에 대응되는 문자열과 비교해보면 세 번째 원소가 항상 다릅니다.

엄밀한 표현으로, 아래와 같은 함수 $d:\mathbb{N}\to \left\{0, 1 \right\}$을 정의하겠습니다.

$$d\left (n  \right )=1-b_n\left ( n \right )=\left\{\begin{matrix} 0 & if\; b_n\left ( n \right )=1 \\ 1 & if\; b_n\left ( n \right )=0 \\ \end{matrix}\right.$$

이렇게 정의된 함수 $d$는 절대 $b_n$과 같을 수 없으므로 모순이 발생합니다. 이런 증명 방식을 Cantor's Diagonalization Principle이라고 합니다.

 

또 다른 예시를 한번 보겠습니다. 실수의 집합 $\mathbb{R}$은 Countable일까요? 그렇지 않습니다. 

$A=\left\{x\in \mathbb{R}:0\leq x<1 \right\}$라고 두고, $A$가 Uncountable임을 증명하겠습니다. 그러면 $A$는 $\mathbb{R}$의 부분집합이므로 $\mathbb{R}$ 역시 Uncountable임이 증명됩니다.

만약 $A$가 Countable이라고 가정하겠습니다. 그러면 $A$를 아래와 같이 표현할 수 있습니다.

$$A=\left\{f\left ( 1 \right ), f\left ( 2 \right ), f\left ( 3 \right ), \cdots \right\}$$

각 $f\left(n\right)$는 $f\left ( n \right )=0.d_{n_1}d_{n_2}d_{n_3}\cdots$를 의미한다고 생각하면 됩니다. 그러면 이때, 아래와 같은 실수 $x$를 생각할 수 있습니다.

$$x=0.d_1d_2d_3\cdots$$

$$d_n=\left\{\begin{matrix} 4 & if\; d_{n_n}\neq 4 \\ 5 & if\; d_{n_n}\neq 4 \\ \end{matrix}\right.$$

그러면 이 실수 $x$는 0 이상 1 이하이며 실수이지만 $A$에 포함되지 않습니다. 왜냐? $x\in A$이려면 $f\left(n\right)=x$인 $n$이 존재해야 하는데, $f\left(n\right)$의 소수점 $n$번째 자리수는 $x$의 소숫점 $n$번째 자릿수와 항상 다르기 때문입니다. 따라서 모순이 발생, $A$는 Uncountable입니다. 따라서 $\mathbb{R}$ 역시 Uncountable입니다.

 

Power Set의 Countability

집합 $A$에 대해서, 이의 Power Set은 아래와 같이 정의되죠.

$$P\left ( A \right )=\left\{B:B\subseteq A \right\}$$

여기서 $A$의 모든 원소 $a$에 대해 $\left\{ a \right\}$는 항상 $P\left( A\right)$의 원소이기 때문에, $P\left( A\right)$는 적어도 $A$의 크기보다는 크다고 생각할 수 있습니다. 이에 대한 증명을 해보겠습니다.

먼저 $A$가 유한 집합일 경우, $\left|P\left ( A \right ) \right|=2^{\left|A \right|}$이므로 쉽게 증명할 수 있습니다.

무한 집합일 경우에는 $P\left( A\right)$와 $A$가 같은 크기를 가진다고 가정한 뒤에, 모순임을 보여서 증명해 보도록 하겠습니다. $P\left( A\right)$와 $A$가 같은 크기를 가진다는 것은 $A$에서 $P\left( A\right)$으로의 전단사 함수 $g$가 존재한다는 것을 의미합니다.

이때, 집합 $B$를 $B=\left\{a\in A: a\notin g\left ( a \right ) \right\}$ 라고 정의하겠습니다. 그러면 $B$는 당연하게도 $A$의 부분집합이므로 $P\left(A\right)$의 원소입니다. $g$는 전사 함수이기 때문에, $g\left ( a \right )=B$인 $a\in A$가 항상 존재하게 됩니다.

만약 이 $a$가 $B$의 원소라고 생각해 봅시다. 그러면 $g\left ( a \right )=B$이므로 $a\in g\left ( a \right )$가 되는데, 이는 모순입니다. B의 정의에 의해서 $a$는 $B$의 원소가 될 수 없기 때문이죠.

반대로 $a$가 $B$의 원소가 아닐 경우 $g\left ( a \right )=B$이므로 $a\notin g\left ( a \right )$가 되는데, 이 역시 모순이 됩니다.

따라서, 이러한 전단사 함수 $g$는 존재할 수 없으며, 이는 $P\left( A\right)$와 $A$가 같은 크기를 가질 수 없음을 의미합니다.

 

이 전 글에서 아래와 같은 Language $Halt$가 Undecidable임을 보였습니다.

$$Halt=\left\{\left<P,w \right>:P\ is\ C + + \ programm\ that\ terminates\ w \right\}$$

이를 이번에는 살짝 다른 방법으로 증명해 보겠습니다. 먼저, 모든 C++ 프로그램은 Countable이라는 사실에서 출발하겠습니다. 왜냐하면 모든 C++ 프로그램은 Binary String $\left<P\right>$로 표현 가능하고, 길이가 $n$인 Binary String의 개수는 $2^n$개로 고정되어 있기 때문에 모든 C++ 프로그램을 List 할 수 있기 때문이죠.

이제 $Halt$가 Decidable이라고 가정하고, 모순임을 보여 $Halt$는 Undecidable임을 보이도록 하겠습니다. 모든 C++ 프로그램이 정확히 한 번씩 포함된 Infinite List $P_1, P_2, P_3, \cdots$를 생각합시다. 그러면 $Halt$ 자체가 해결 가능한지, 불가능한지를 판단하는 C++ 프로그램, $H$가 존재할 것입니다.

이러한 프로그램 $H$는 $\left<P, w \right>$를 입력받아 $P$가 $w$를 실행할 수 있으면 True를, $P$가 $w$를 실행할 수 없으면 False를 출력합니다.

여기서 $\left< P_n\right>$를 입력받아 아래와 같은 작업을 수행하는 C++ 프로그램 $D$를 생각합시다.

1. $H$에 $\left<P_n, \left<P_n\right> \right>$를 집어넣는다.
2. $H$가 True를 반환하면 무한루프로 보낸다.
3. $H$가 False를 반환하면 $D$는 True를 출력하고 계산을 종료(Terminate)한다.

 

말로 풀어서 설명하겠습니다. $D$에 $\left< P_n \right>$를 넣었을 때

1. $H$에 $\left< P_n, \left< P_n \right> \right>$을 넣은 값이 False이면 (= $P_n$이 $\left< P_n \right>$을 입력받았을 때 Terminate 되지 않으면) $D$는 Terminate 됩니다.
2. $H$에 $\left< P_n, \left< P_n \right> \right>$을 넣은 값이 True이면 (= $P_n$이 $\left< P_n \right>$을 입력받았을 때 Terminate 되면) $D$는 Terminate 되지 않습니다.

 

그리고 이 $D$는 C++ 프로그램이므로, $D=P_n$인 어떤 $n$이 존재합니다. 따라서, $D$는 $D$를 입력받았을 때, $D$가 $D$를 입력받았았을 때 Terminate되지 않으면 Terminate 됩니다. 역시 말이 안 되기 때문에 모순이 발생, $Halt$가 Undecidable임을 다시 한번 보일 수 있었습니다.

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.