기수의 거듭제곱(Exponentiation of cardinal number)

이제 기수의 거듭제곱을 정의하려고 합니다. 거듭제곱이면 $b^a$ 와 같은 형태인데, 이는 $b$ 가 $a$ 번 곱해졌음을 뜻합니다. 그렇다면 기수가 $b^a$ 의 값을 가진다는 것은 어떤 뜻일까요? 

---

1. 기수의 거듭제곱

 

정의($S.T$) 4-10) 기수의 거듭제곱
$a,b$ 가 기수이고 집합 $A$ 와 $B$ 의 기수가 각각 $a,b$ 라 하자. $a\neq 0$ 일 때, $B^A$ 는 $A$ 에서 $B$ 로 가는 모든 함수의 집합으로 정의하여 $B^A:=\left\{ f\mid f:A\rightarrow B \right\}$ 로 표기한다. 이때, 기수의 거듭제곱을 $b^a:=\left| B^A \right|=\left| \left\{ f\mid f:A\rightarrow B \right\} \right|$ 로 정의한다.

 

수학에서 정의는 약속이기 때문에 받아들이는 것이 맞고, 따라서 외워야 합니다. 이 정의를 알고 있어야만 그를 바탕으로 정리를 유도해낼 수 있는 것이기 때문입니다.

 

하지만, 아주 간단한 용어나 개념, 기호가 아닌 위의 기수의 거듭제곱과 같이 다소 복잡한 개념을 정의할 때는 왜 그렇게 정의할지에 대해서도 의문점을 가져보는 것이 수학 공부에 있어 깊은 이해와 매끄럽게 연결될 수 있는 바람직한 태도입니다. 기수의 정의를, 왜 이렇게 두 집합 사이에 존재하는 함수의 집합의 기수로 정의할까요?

 

간단한 상황을 알아보기 위해 유한집합의 상황을 예를 들어 생각해 봅시다. 만일 집합 $A$ 의 기수가 2, 즉 원소의 개수가 2개이고, $B$ 는 3개라고 가정하겠습니다. 그렇다면 $A$ 에서 $B$ 로 갈 수 있는 함수의 개수는 중복순열을 이용하여 $_3\displaystyle\Pi_2$ 라는 것을 알고 있습니다. 집합 $A$ 의 각 원소들은 $B$ 에 존재하는 세 원소 중 하나를 택해서 대응되면 함수가 완성되기 때문입니다. 그리고 이 값은 $3^2$ 입니다.

 

이처럼, 집합과 집합 사이의 원소의 개수들 관계에 있어서 '지수(exponentiation)'의 개념은 '한 집합에서 다른 집합으로 가는 전체 함수의 갯수'와 관련이 있습니다. 그래서 기수의 거듭제곱을 정의하기 위해서 수학자들은 우리가 '지수' 즉 '거듭제곱'이라는 개념을 어떻게 받아들이고 있는지, 연결짓고 있는지를 떠올려 보았는데, 그것이 바로 집합에서 집합으로 가는 함수의 총 개수라는 사실이므로, 기수의 거듭제곱의 정의를 이와 같이 한 것입니다. 

 

정리하면 기수의 거듭제곱을 정의할 때 마구잡이로 그냥 함수의 개수 집합의 기수로 못 박은 것이 아니라, 거듭제곱이나 지수를 우리가 어떻게 이해하고 있는지의 직관적인 이해나 배경을 먼저 떠올린 다음, 이를 바탕으로 집합에서 집합으로 가는 함수의 개수가 거듭제곱 및 지수의 개념이니, 기수의 정의도 이와 같이 했다는 것입니다. 당연히 이러한 사실이 시험에 등장하지는 않겠지만, 왜 정의를 그렇게 했을까 호기심을 풀 수 있을 만한 요소로 생각해보시고 이를 이해했다면 기수의 거듭제곱 정의를 아주 빠르게 외울 수 있을 것입니다.^[각주:1] 그리고 주의할 것은 $B^A$ 는 $A$ 에서 $B$ 로 가는 모든 함수의 집합입니다. $B$ 에서 $A$ 로 가는 것이라 착오하지 않도록 조심합시다.

 

 

정리($S.T$) 4.23)
네 집합 $A,B,X,Y$ 에 대하여 $A\sim X$ 이고 $B\sim Y$ 이면, $B^A\sim X^Y$ 이다.

증명) 가정에 따라서 두 전단사함수 $g:A\sim X$ 와 $h : B\sim Y$ 를 생각하자. 그리고 새로운 함수 $\psi : B^A\rightarrow Y^X$ 를 각 $f:B^A$ 에 대하여 $\psi (f)=h\circ f \circ g^{-1}$ 으로 정의하자.

그러면

$$\begin{align*} \psi(f)=\psi(k)\;\;&\Leftrightarrow \;\; h\circ f\circ g^{-1}=h\circ k\circ g^{-1} \\\\& \Leftrightarrow  h^{-1}\circ \left( h\circ f\circ g^{-1} \right)=h^{-1}\circ\left(  h\circ k\circ g^{-1}\right) \\\\& \Leftrightarrow I_B\circ f\circ g^{-1}=I_B\circ k\circ g^{-1} \\\\& \Leftrightarrow f\circ g^{-1}=k\circ g^{-1} \\\\& \Leftrightarrow \left(  f\circ g^{-1}\right)\circ g=\left( k\circ g^{-1} \right)\circ g \\\\& \Leftrightarrow f\circ I_A = k\circ I_A \\\\& \Leftrightarrow f=k \end{align*}$$
이므로 $\psi$ 는 잘 정의되고 단사함수이다. 그러면 임의의 $\varphi\in Y^X$ 에 대하여 $\psi(h^{-1}\circ \varphi\circ g^{})=h\circ \left( h^{-1}\circ \varphi\circ g^{} \right)\circ g^{-1}=\varphi$ 를 만족하는 $h^{-1}\circ \varphi \circ g \in B^A$ 이 존재하므로, $\psi$ 는 전사이다. 결국 $\psi : B^A \rightarrow Y^X$ 는 전단사이므로 $B^A \sim Y^X$ 이다. $_\blacksquare$

 

 

---

예제 1) 임의의 집합 $A$ 에 대하여 $\left| \mathcal{P}(A) \right|=2^{\left| A \right|}$ 가 성립함을 증명하여라

 

Sol) 보여야 할 것은 집합 $\left| B \right|=2$ 에 대해 $h:\mathcal{P}(A)\sim B^A$ 인 함수 $h$ 가 존재하는 것이다.

 

우선$2^{\left| A \right|}$ 에서, 원소의 개수가 2개인 집합 $B$ 에서 $A$ 로 가는 함수의 개수를 고려해야 하므로 간단히 $B=\left\{ 0,1 \right\}$ 이라 놓자. 그리고 $B$ 에서 $A$ 로 가는 임의의 함수를 $f$ 라 표기하고 그 중 우리는 $D\subseteq A$ 에 대한 특성함수

 

$$\chi_D(x) = \left\{ \begin{array}{cl} 1 &(x\in D) \\ 0 &( x\in A-D) \end{array} \right.$$

 

를 고려할 것이다. 즉 $\chi_D(x) : A\rightarrow B$ 이다. 그러면 $h:\mathcal{P}(A)\rightarrow B^A$ 라는 함수는 모든 $D\in \mathcal{P}(A)$ 에 대해 $h(D)=\chi_D$ 로 정의되는 함수이다. 이제 $h$ 가 전단사인지 확인해보자.

 

1) $h$ 는 단사함수이다 : $f(D_1)=f(D_2)$ 라 가정하자. 그러면 자명히 $f(D_1)=f(D_2) \; \Leftrightarrow \; \chi_{D_1}=\chi_{D_2}$ 이고, 이때 $i=1,2$ 에 대해 $D_i=\chi_{D_i}^{-1}\left( \left\{ 1 \right\} \right)$ 가 성립하므로 결국 $\chi_{D_1}=\chi_{D_2} \; \Rightarrow \; D_1=D_2$ 가 성립한다.

 

2) $h$ 는 전사함수이다 : 임의의 $\chi_D\in B^A$ 인 $\chi_D : A\rightarrow B$ 를 하나 골랐을 때, 

$$\chi_D(x) = \left\{ \begin{array}{cl} 1 &(x\in D) \\ 0 &( x\in A-D) \end{array} \right.$$

와 같이 정의되므로 $D=\left\{ x\in A\mid f(x)=1 \right\}$ 로 잡으면 이러한 $D\in \mathcal{P}(A)$ 가 항상 존재한다. 즉 모든 $D\in \mathcal{P}(A)$ 에 대해 $h(D)=\chi_D$ 가 성립하므로 $h$ 는 단사함수이다.^[각주:2] $_\blacksquare$

정리($S.T$) 4.24) 기수의 거듭제곱에서의 지수법칙
임의의 기수 $a,x,y$ 에 대하여 다음이 성립한다.
① $a^xa^y=a^{x+y}$
② $(a^x)^y=a^{xy}$
③ $(ab)^x=a^xa^y$

증명)
③ $A,B,X$ 를 집합이라고 하고  이들 각각의 기수가 $a,b,x$ 라 하자. 함수 $\psi : (A\times B)^X\rightarrow A^X \times B^X$ 를 $f\in (A\times B)^X\;,\; f:X\rightarrow A\times B$ 에 대해서 다음 문단에서와 같이 정의하고, 최종적으로 이것이 전단사임을 보이면 된다.

$\psi$ 를 어떻게 정의할까? 우선 $k_A : A\times B \rightarrow A$ 라는 함수를 $(a,b)\mapsto a$ 로 정의하면 $k_A\circ f : X\rightarrow A\times B \rightarrow A$가 되고, $k_B : A\times B \rightarrow B$ 라는 함수는 $(a,b)\mapsto b$ 라 정의하면 $p_B\circ f : X\rightarrow A\times B \rightarrow B$ 가 된다. 그러면 $\psi (f)=(k_A\circ f, k_B\circ f) \in A^X\times B^X$ 가 된다. 이제 $\psi$ 가 전단사임을 보이자.

1) $\psi$ 가 단사이다 : $(g,h)\in A^X \times B^X$ 라 하자. $\psi(f_1)=(g_1,h_1)=\psi (f_2) = (g_2,f_2)$ 라 가정하면 $g_1=g_2$ 이고 $h_1=h_2$ 이므로, $f_1=f_2$ 에서 $\psi$ 는 단사이다.

2) $\psi$ 는 전사이다 : 임의의 $(g,h)\in A^X\times B^X$ 에 대하여, 모든 $x\in X$ 에 대해 $f(x):=(g(x),h(x))$ 라 정의하면, $\psi(f)=(g,h)$ 가 된다. 즉 치역의 모든 원소 $(g,h)$ 에 대하여 $\psi(f)=(g,h)$ 가 성립하는 $f\in (A\times B)^X$ 를 뽑을 수 있다. $_\blacksquare$

 

 

 

정리($S.T$) 4.25)
$2^{\aleph_0}=\mathfrak{c}$

따름정리($S.T$) 4.25.1)
$\aleph_0 < \mathfrak{c}$

증명) $\mathfrak{c}\leq 2^{\aleph_0}$ 이고 $\mathfrak{c} \geq 2^{\aleph_0}$ 임을 보이자.

1) $\mathfrak{c}\leq 2^{\aleph_0}$ 임을 먼저 보이자. $\left| \mathbb{Q} \right|=\aleph_0$ 이므로 $\left| \mathcal{P}(\mathbb{Q}) \right|=2^{\aleph_0}$ 이고, 고로 $\mathbb{R}$ 에서 $\mathcal{P}(\mathbb{Q})$ 의 부분집합으로 가는 전단사함수를 만들어야 한다. 함수 $f:\mathbb{R}\rightarrow \mathcal{P}(\mathbb{Q})$ 를 모든 $a\in \mathbb{R}$ 에 대하여 $a\mapsto f(a)=\left\{ x\in \mathbb{Q}\mid x< a \right\}$ 로 잡는다. 그리고 나서 $f$ 가 단사임을 보이기만 하면, ^[각주:3]$f(\mathbb{R}) \subseteq \mathcal{P}(\mathbb{Q})$ 즉 $f$ 의 치역이 $\mathcal{P}(\mathbb{Q})$ 의 부분집합이고 $\mathbb{R}\sim f(\mathbb{R})$ 이 되므로 증명이 끝난다.

i) $f$ 는 단사이다 : $a < b$, 즉 $a\neq b$ 라 하자. 일반성을 잃지 않고 둘 중 하나가 크다고 잡은 것이다. 그러면 유리수의 조밀성에 의하여 임의의 두 실수 사이에 유리수 $r\in \mathbb{Q}$ 가 $a<r<b$ 로 존재한다. 그러면 $r\in f(b)$ 이지만 $r\notin f(a)$ 가 되므로 $f(a)\neq f(b)$ 이다. 따라서 $f$ 는 단사이고, $\left| \mathbb{R} \right|\leq \left| \mathcal{P}(\mathbb{Q}) \right|$ 이다.

2) $2^{\aleph_0} \leq \mathfrak{c}$ 을 보이자. 함수 $\psi : \left\{ 0,1 \right\}^{\mathbb{N}}\rightarrow (0,1)\sim \mathbb{R}$ 을 잡고, 여기서 $f \in \left\{ 0,1 \right\}^{\mathbb{N}} \Leftrightarrow f:\mathbb{N}\rightarrow \left\{ 0,1 \right\}$ 일 때 $\psi(f)=0.f(1)f(2)f(3)\cdots$ 로 정의한다. 즉 $\psi(f)\in (0,1)$ 이다. 그러면 만일 두 함수 $f,g\in \left\{ 0,1 \right\}^{\mathbb{N}}$ 에 대해 $f\neq g$ 이면, 즉 $\sim\left( f(1)=g(1)\,\wedge f(2)=g(2) \,\wedge \, f(3)=g(3)\cdots\right)$ 라면 $\psi(f)\neq \psi(g)$^[각주:4]가 되므로 $\psi$ 는 단사이다. 즉 $\left\{ 0,1 \right\}^{\mathbb{N}}\sim S\subseteq(0,1)\sim \mathbb{R}$ 이므로 $2^{\aleph_0} \leq \mathfrak{c}$ 가 성립한다. 

따라서 1), 2)에 의해 $2^{\aleph_0}=\mathfrak{c}$ 가 성립한다. $_\blacksquare$

따름정리의 증명) 칸토어의 정리를 사용하면 아래 식에서 첫번째 부등호가 성립하고, 첫번째 등호는 예제 1)에서 했다. 그리고 마지막 등호는 위 정리($S.T$) 4.25) 에 의한다 : $\aleph_0< \left| \mathcal{P}(\aleph_0) \right|=2^{\aleph_0}=\mathfrak{c}$ 를 얻는다. $_\blacksquare$

 

 

 

정리($S.T$) 4.26) 여러가지 기수들의 곱과 거듭제곱 관계
① $\mathfrak{c}\mathfrak{c}=\mathfrak{c}$
② $\aleph_0\mathfrak{c} = \mathfrak{c}$ 
③ $n\geq 2$ 인 유한한 수일 때, $n^{\aleph_0}=\mathfrak{c}$
④ $\aleph_0^{\aleph_0}=\mathfrak{c}$

증명) 
① 위 정리($S.T$) 4.25) 와 기수의 거듭제곱의 지수법칙을 사용하면, $$\mathfrak{c}\mathfrak{c}=2^{\aleph_0}2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\mathfrak{c}\;\;_\blacksquare$$

② 함수 $f: (0,1)\times \mathbb{N} \rightarrow (0,1)$ 이 자연수 $n$ 과 $x,y\in (0,1)$ 에 대해 $(x,n)\mapsto y$ 으로 정의되었다고 하자. $f$ 가 전단사함수임을 보이면 증명이 끝난다.

1) $f$ 는 단사이다 : $a_i$ 와 $b_i$ 가 $0,1,2,\cdots ,9$ 중 하나일 때, $x=0.a_1a_2a_3\cdots$ 와 $n=b_1b_2b_3\cdots$ 와 같이 소수 표현으로 나타내보자. 이때 $f(x,n):=0.a_1b_1a_2b_2a_3b_3 \cdots$ 으로 정의한다.
$f$ 가 단사임을 보이기 위해서 $f(x,n)=f(y,m)$ 이라 가정하자. 그러면

$$\begin{align*} f(x,n)=f(y,m) \;&\Rightarrow\; 0.a_1b_1a_2b_2\cdots = 0.c_1d_1c_2d_2\cdots \\\\&\Rightarrow \; a_1=c_1,\; a_2=c_2, \; \cdots \; b_1=d_1,\; b_2=d_2,\; \cdots \\\\&\Rightarrow \;x=y\;\wedge \; n=m \\\\&\Rightarrow \; (x,n)=(y,m) \end{align*}$$
2) $f$ 는 전사다 : 임의의 $z\in (0,1)$ 에 대하여, $f(x,n)=z$ 를 만족하는 $(x,n)\in (0,1)\times \mathbb{N}$ 이 존재함을 보이면 된다. $z=0.e_1e_2e_3\cdots \in (0,1)$ 와 같이 표현되면, 이때 $x=0.e_1e_3e_5\cdots$ 이고 $n=0.e_2e_4e_6\cdots$ 이 되도록 선택하면 된다. 따라서 $f$ 는 전사이다.

이상에서 $f: (0,1)\times \mathbb{N} \rightarrow (0,1)$ 는 전단사이므로, $\mathbb{R}\times \mathbb{N}\sim \mathbb{R}$ 이다. 고로 $\aleph_0\mathfrak{c} = \mathfrak{c}$ 이다. $_\blacksquare$

③ 함수 $\psi : \mathbb{N}^{\mathbb{N}_k}=\left\{ f\mid f:\mathbb{N}\rightarrow \mathbb{N}_k \right\}\rightarrow \mathbb{R}\sim(0,1)$ 를 $f\mapsto \psi(f)=0.f(1)f(2)f(3)\cdots$ 로 정의하자. 그러면 $\psi$ 는 다음과 같은 과정을 통해 단사임을 확인할 수 있다.

$$\begin{align*} \psi(f)=\psi(g)\;&\;\Rightarrow \; 0.f(1)f(2)f(3)\cdots = 0.g(1)g(2)g(3)\cdots \\\\&\;\Rightarrow \; f(1)=g(1)\,\wedge \,f(2)=g(2)\,\wedge \, f(3)=g(3)\,\wedge \,\cdots \\\\&\;\Rightarrow \;f=g \;\;\;\;\;_\blacksquare \end{align*}$$
④ 부등호를 두 번 보이자.

1) $\aleph_0^{\aleph_0}\geq \mathfrak{c}$ 을 먼저 보이자. 함수 $\psi : \mathbb{R}\sim [0,1)\rightarrow \mathbb{N}^{\mathbb{N}}=\left\{ f\mid f:\mathbb{N}\rightarrow \mathbb{N} \right\}$ 를 $x=0.a_1a_2a_3\cdots \mapsto \psi(x)=f:=(a_1\;a_2\;a_3\;\cdots$ 와 같이 정의하자. $\psi$ 는 그러면 아래와 같은 과정을 통해 단사임을 확인할 수 있다.

$$\begin{align*} \psi(x_1)=\psi(x_2)\;&\;\Rightarrow \; f_1=f_2 \\\\&\;\Rightarrow \; \begin{pmatrix} a_1 & a_2 & a_3  &\cdots  \;\; \end{pmatrix}=\begin{pmatrix} b_1 & b_2 & b_3  &\cdots   \end{pmatrix} \\\\&\;\Rightarrow \;a_1=b_1\,\wedge \, a_2=b_2\,\wedge \, a_3=b_3\,\wedge \,\cdots \\\\& \;\Rightarrow 0.a_1a_2 \cdots = 0.b_1b_2\cdots  \\\\& \; \Rightarrow x_1=x_2 \end{align*}$$
2) $\aleph_0^{\aleph_0}\leq \mathfrak{c}$ 임을 보이자. 함수 $\psi : \mathbb{N}^{\mathbb{N}}=\left\{ f\mid f:\mathbb{N}\rightarrow \mathbb{N} \right\}\rightarrow \mathbb{R}\sim(0,1)$ 를 $f\mapsto \psi(f)=0.f(1)f(2)f(3)\cdots$ 으로 정의하자. 그러면 $\psi$ 는 다음과 같은 과정을 통해 단사임을 보일 수 있다.

$$\begin{align*} \psi(f)=\psi(g)\;&\;\Rightarrow \; 0.f(1)f(2)f(3)\cdots = 0.g(1)g(2)g(3)\cdots \\\\&\;\Rightarrow \; f(1)=g(1)\,\wedge \,f(2)=g(2)\,\wedge \, f(3)=g(3)\,\wedge \,\cdots \\\\&\;\Rightarrow \;f=g \;\;\;\;\;_\blacksquare \end{align*}$$

 

---

예제 2) 집합 $\left\{ f\mid f:\mathbb{R}\rightarrow \mathbb{R} \right\}$ 의 기수와 $\mathfrak{c}$ 의 크기를 비교하여라

 

Sol) 첫번째 등호와 두번째 등호는 기수의 거듭제곱의 정의 즉 정의($S.T$) 4.10) 에 의한 것이고, 네 번째 등호는 정리($S.T$) 4.25) 에 의하며, 다섯번째 등호는 정리($S.T$) 4.24), 그리고 마지막 등호는 예제 2) 에 의한 것이다.

 

$$\begin{align*} \left| \left\{ f\mid f:\mathbb{R}\rightarrow \mathbb{R} \right\} \right|&=\left| \mathbb{R}^{\mathbb{R}} \right| \\\\&=\left| \mathbb{R} \right|^{\left| \mathbb{R} \right|} \\\\&= \mathfrak{c}^\mathfrak{c} \\\\&= \left( 2^{\aleph_0} \right)^\mathfrak{c} \\\\&=2^{\aleph_0\mathfrak{c}} \\\\&=2^{\mathfrak{c}}>\mathfrak{c} \end{align*}$$

 

즉, 실수의 기수 $\mathfrak{c}$ 보다 큰 기수를 갖는 집합이 존재한다는 것이다. $_\blacksquare$

 

 

 

[참고문헌]

You-Feng Lin, Shwu-Yeng T,Lin - Set thoery

 

 

 

 

1. 원래 공부할 때는 가장 빠르게 이해하는 사람이 가장 빠르게 암기할 수 있는 것이지요. 교과서들을 보더라도 이 부분에 대한 구체적인 설명이 미비한 경우가 많은 듯 합니다. [본문으로]
2.   이 부분에 대한 논리가 다소 어려울 수 있습니다. 핵심은 치역의 임의의 원소인 $\chi_D$ 를 골랐을 때, 그에 대응되는  $D$ 가 반드시 존재하느냐를 보이는 것입니다. 임의의 $\chi_D$ 를 고르면, 이 함수에 따라 1로 가는 정의역의 원소들이 있을 것이고 그 원소들의 집합을 $D$ 라고 정의해주면, 정의역의 나머지 원소들은 $D^c\cap A$ 에 속하게 되고 이들은 자동적으로 치역의 다른 한 원소인 0으로 가게 됩니다. 즉, $\chi_D$ 를 하나 고르면, 그에 따라 반드시 $D$ 를 잡을 수 있습니다. 따라서 전사라는 논리입니다. [본문으로]
3. 해당 링크에서 따름정리($S.T$) 4.17.2) 를 참고하세요. [본문으로]
4. 여기서 $f\neq g$ 를 가정하는 이유는 단사의 정의의 대우명제를 증명하기 위함이고, $f\neq g$ 라는 것은 소수점 중에서 단 하나만 다르더라도 성립한다는 뜻이기 때문에 이와 같이 설명한 것입니다. [본문으로]