\(\mathbb{N}\)으로부터 \(\mathbb{N}\)으로의 함수의 개수

풀이. 표기를 편하게 하기 위하여 정의역이 \(A\)이고 공역이 \(B\)인 함수의 모임을 \(B^A\)로 나타낸다.

1단계. 정의역이 \(\mathbb{N}\)이고 공역이 \(E = \left\{ 0,\,1 \right\}\)인 함수의 개수를 세어 보자. 즉 \(E^\mathbb{N}\)의 원소의 개수를 생각해 보자. \(f\in E^\mathbb{N}\)라고 하자. 그러면 각 자연수 \(n\)에 대하여 함숫값 \(f(n)\)은 \(0\) 또는 \(1\)이다. 이제 정수 부분이 \(0\)이고 소수점 아래 \(n\)째 자리의 숫자가 \(f(n)\)인 이진수를 생각하자. 그러면 함수 \(f\)는 다음과 같은 이진수에 대응된다. \[f \quad \mapsto \quad 0.f(1) f(2) f(3) \cdots \,_{(2)}\] 물론 이러한 대응이 일대일 대응은 아니다. 왜냐하면 \[0.110111 \cdots \,_{(2)} \,=\, 0.111 _{(2)}\] 와 같이 순환마디가 \(1\)인 순환소수는 유한소수와 같기 때문이다. [‘같다’라는 것은 값이 같다는 뜻이며, 동일한 형태의 소수라는 뜻은 아니다.]

여기서 순환마디가 \(1\)인 순환소수의 개수가 가산(countable)임을 보이자. 정수 부분이 \(0\)이고, 소수점 아래 \(k\)째 자리부터 모두 \(1\)인 순환소수들의 모임을 \(S_k\)라고 하자. [그러니까 \(S_k\)는 수의 모임이 아니라 수의 표현의 모임인 셈이다. 마치 ‘호랑이의 모임’과 ‘호랑이라는 글자의 모임’이 다른 것처럼 말이다.] 그러면 \(S_k\)의 서로 다른 두 원소는 소수점 아래 첫째자리부터 \((k-1)\)째자리까지만 다를 수 있고, 소수점 아래 \(k\)째 자리부터는 같다. 그러므로 \(S_k\)의 원소의 개수는 \(2^{k-1}\)이며, \(S_k\)는 유한집합이다. \[S = S_1 \cup S_2 \cup S_3 \cup \cdots\] 라고 하면 \(S\)는 순환마디가 \(1\)인 순환소수를 모두 모은 집합이다. 이때 \(S\)는 유한집합을 가산 번 합집합한 것이므로 \(S\) 자신도 가산집합이다.

지금까지 살펴본 바에 의하면 \(E^\mathbb{N}\)의 원소를 이진소수에 대응시켰을 때 서로 같은 값에 대응되는 경우까지 모두 따져본다 하더라도 \(E^\mathbb{N}\)의 원소의 개수는 정수 부분이 \(0\)인 이진소수로 표현되는 실수의 개수에 \(S\)의 원소의 개수를 더한 만큼밖에 되지 않는다. 정수 부분이 \(0\)인 이진소수로 나타나는 수 중에서 ‘순환마디가 \(1\)인 순환소수’가 아닌 수는 모두 실수구간 \([0,\,1)\)의 원소이므로, 그러한 이진소수의 개수는 \(\mathbb{R}\)의 원소의 개수와 같다. \(\mathbb{R}\)에 가산 개의 원소를 더한다한들 원소의 개수는 변함이 없다. 그러므로 \(E^\mathbb{N}\)의 원소의 개수는 \(\mathbb{R}\)의 원소의 개수와 같다.

2단계. \(\mathbb{N} \times \mathbb{N}\)의 부분집합들의 개수를 세어 보자. 그런데 \(\mathbb{N} \times \mathbb{N}\)과 \(\mathbb{N}\)은 모두 무한인 가산집합으로서 원소의 개수가 같으므로, \(\mathbb{N}\)의 부분집합의 개수를 세면 된다. 이 방법은 1단계와 동일하다. \(D\)가 \(\mathbb{N}\)의 부분집합이라고 하자. 이제 함수 \(f_D\)를 다음과 같이 정의하자. \[f_D(n) = \begin{cases} 1 \quad\quad &\text{if} \quad n \in D \\[6pt] 0 \quad\quad &\text{if} \quad n \notin D \end{cases}\] 그러면 각 자연수 \(n\)에 대하여 함숫값 \(f_D (n)\)은 \(0\) 또는 \(1\)이다. 그러므로 단계 1에서와 같은 방법으로 \(f_D\)의 개수는 실수의 개수와 같다. 그런데 \(\mathbb{N}\)의 부분집합 \(D\)와 함수 \(f_D\)는 일대일로 대응되므로 \(\mathbb{N}\)의 부분집합의 개수와 실수의 개수는 같다.

3단계.정의역과 공역이 모두 \(\mathbb{N}\)인 함수의 개수를 세어 보자. 먼저 1단계에서 밝힌 바와 같이 \(E^\mathbb{N}\)의 원소의 개수는 실수의 개수와 같다. 그런데 \(E^\mathbb{N}\)은 \(\mathbb{N}^\mathbb{N}\)의 부분집합이므로 \(\mathbb{N}^\mathbb{N}\)의 원소의 개수는 실수의 개수 이상이다.

한편 임의의 함수 \(f\in\mathbb{N}^\mathbb{N}\)의 그래프는 \(\mathbb{N} \times \mathbb{N}\)의 부분집합이다. 그런데 \(\mathbb{N} \times \mathbb{N}\)의 부분집합의 개수는 실수의 개수와 같다. \(\mathbb{N} \times \mathbb{N}\)의 모든 부분집합이 \(\mathbb{N}\)으로부터 \(\mathbb{N}\)으로의 함수의 그래프가 되는 것은 아니므로, \(\mathbb{N}^\mathbb{N}\)은 \(\mathbb{N} \times \mathbb{N}\)의 부분집합들의 모임의 진부분집합이다. 그러므로 \(\mathbb{N}^\mathbb{N}\)의 원소의 개수는 실수의 개수 이하이다.

이로써 \(\mathbb{N}^\mathbb{N}\)의 원소의 개수가 실수의 개수와 같음을 보였다.

풀이. 유리수의 개수와 자연수의 개수가 같으므로, 앞의 문제의 풀이에 의하여 곧바로 결론을 얻는다.