거리공간에서의 쿠라토프스키 14개 집합 정리 ( Kuratowski's 14-Set Theorem for Metric Space; Kuratowski's Closure-Complement Problem for Metric Space )

이번 글에서는 저번 글에서 언급했던 문제인 쿠라토프스키 14개 집합 정리 (Kuratowski's 14-Set Theorem)에 대해 소개할 것이다. 쿠라토프스키 14개 집합 정리란, 거리공간 $X$가 주어질 때, $X$의 그 어떤 부분집합 $E$를 들고 와도, $A$에 closure 연산과 여집합 연산을 반복적으로 적용해서 얻을 수 있는 집합의 개수는 최대 14개라는 정리이다. 쿠라토프스키 14개 집합 정리는 쿠라토프스키 closure-complement 문제라고도 불리며, 이는 쿠라토프스키 모노이드라는 특이한 대수구조를 정의할 수 있도록 하며, 이를 통해 공간을 분류할 수 있다. 이에 대해서는 추후 위상수학을 다룰 때 포스팅하도록 하겠다. 그러면 이제 본론으로 들어가서 쿠라토프스키 14개 집합 정리가 무엇인지 알아보자.

 

Theorem 1. Kuratowski's 14-Set Theorem for Metric Space

거리공간 $X$가 주어졌으며, 다음과 같이 정의되는 두 함수 $k : \mathscr{P}(X) \to \mathscr{P}(X)$, $c : \mathscr{P}(X) \to \mathscr{P}(X)$가 주어졌다고 하자. $$ k : E \mapsto \overline{E} \\ c : E \mapsto E^\mathsf{c} $$ 그러면 임의의 $E \subseteq X$에 대하여 $\{ E \}$로부터 $k$와 $c$에 의해 생성된 집합의 원소의 개수의 최댓값은 14개이다.

 

Proof.

이번 증명에서는 서술의 편의를 위해 두 함수 $f$와 $g$의 합성 $f \circ g$를 $fg$와 같이 나타내도록 하겠다.
또한, 항등함수는 $\epsilon$으로 나타내도록 하겠다.

그러면 이 글의 Theorem 2에 의해 $kk = k$임이 자명하며, 여집합의 성질에 의해 $cc = \epsilon$임이 자명하다.

따라서 $k$와 $c$로 이루어진 문자열은 언제나 $k$가 두 번 연속으로 등장하지 않으며 $c$ 역시 두 번 연속으로 등장하지 않는 문자열로 환원될 수 있다. 단, 빈 문자열은 $\epsilon$으로 취급하자.

따라서 $k$와 $c$를 통해 만들어질 수 있는 변환은 $k$, $ck$, $kck$, $\cdots$의 꼴이거나 $c$, $kc$, $ckc$, $\cdots$의 꼴이거나 $\epsilon$이거나 셋 중 하나일 수밖에 없다.

만약 $\cdots ck$와 $\cdots kc$ 모두 더 짧은 길이의 문자열과 같은 변환을 나타낸다면 $k$와 $c$를 통해 만들어질 수 있는 변환의 개수가 유한하다.

이제 두 경우 모두 더 짧은 길이의 문자열과 같은 변환을 나타낸다는 것을 보이자.

먼저, 이 글의 Theorem 3에 의해 $ckc(E) = E^\mathsf{o}$임을 알 수 있다.

따라서 만약 $\overline{\left(\overline{E^\mathsf{o}}\right)^\mathsf{o}} = \overline{E^\mathsf{o}}$라면, $kckckckc = kckc$이며, $kckckck = kckckckcc = kckcc = kck$이므로 $\cdots ck$와 $\cdots kc$꼴의 변환의 개수가 유한하다.

이제 $\overline{\left(\overline{E^\mathsf{o}}\right)^\mathsf{o}} = \overline{E^\mathsf{o}}$임을 보이자.

먼저, 임의의 집합 $F$에 대하여 $F^\mathsf{o} \subseteq F$가 성립하므로 $\left( \overline{E^\mathsf{o}} \right)^\mathsf{o} \subseteq \overline{E^\mathsf{o}}$가 성립한다. 따라서 이 글의 Theorem 3에 의해 $\overline{\left( \overline{E^\mathsf{o}} \right)^\mathsf{o}} \subseteq \overline{E^\mathsf{o}}$이다.

또한, 임의의 집합 $F$에 대하여 $F \subseteq \overline{F}$가 성립하므로 $E^\mathsf{o} \subseteq \overline{E^\mathsf{o}}$이다. 따라서 이 글의 Theorem 3에 의해 $E^\mathsf{o} \subseteq \left( \overline{E^\mathsf{o}} \right)^\mathsf{o}$이며, 같은 이유로 $\overline{E^\mathsf{o}} \subseteq \overline{ \left( \overline{E^\mathsf{o}} \right)^\mathsf{o} }$이다.

따라서 $\overline{\left(\overline{E^\mathsf{o}}\right)^\mathsf{o}} = \overline{E^\mathsf{o}}$가 성립하며, 이로 인해 $k$와 $c$를 통해 만들어질 수 있는 변환은 아래의 $14$개 뿐이다.

$$\epsilon,\;k,\;ck,\;kck,\;ckck,\;kckck,\;ckckck,\;c,\;kc,\;ckc,\;kckc,\;ckckc,\;kckckc,\;ckckckc$$

따라서 $\{E\}$로부터 $k$와 $c$에 의해 생성된 집합의 원소의 개수는 아무리 많아야 $14$개를 넘을 수 없다.

이제 $\{E\}$로부터 $k$와 $c$에 의해 생성된 집합의 원소의 개수가 $14$개인 사례가 존재함을 보이면 정리가 증명된다.

$E \subseteq \mathbb{R}$를 다음과 같이 설정하면, $\{E\}$로부터 $k$와 $c$에 의해 생성된 집합의 원소의 개수가 $14$개이다.

$$E = \left( 0,1 \right) \cup \left( 1,2 \right) \cup \{ 3 \} \cup \left( \left[ 4, 5 \right] \cap \mathbb{Q} \right)$$

$\{E \}$로부터 $k$와 $c$에 의해 생성된 집합의 원소는 다음과 같다.

$$E = \left( 0,1 \right) \cup \left( 1,2 \right) \cup \{ 3 \} \cup \left( \left[ 4, 5 \right] \cap \mathbb{Q} \right) \\ k(E) = \left[ 0,2 \right] \cup \{ 3 \} \left[ 4,5 \right] \\ c(E) = \left( \right. -\infty,0 \left. \right] \cup \{ 1 \} \cup \left[ \right. 2,3 \left. \right) \cup \left( 3,4 \right) \cup \left( \left[ 4,5 \right] \cap \mathbb{Q}^\mathsf{c} \right) \cup \left( 5,\infty \right) \\ ck(E) = \left( -\infty,0 \right) \cup \left( 2,3 \right) \cup \left( 3,4 \right) \cup \left( 5,\infty \right) \\ kc(E) = \left( -\infty,0 \right) \cup \{ 1 \} \cup \left[ \right. 2, \infty \left. \right) \\ kck(E) = \left( \right. -\infty,0 \left. \right] \cup \left[ 2,4 \right] \cup \left[ \right. 5,\infty \left. \right) \\ ckc(E) = \left[ \right. 0,1 \left. \right) \cup \left( 1,2 \right) \\ ckck(E) = \left( 0,2 \right) \cup \left( 4,5 \right) \\ kckc(E) = \left[ 0,2 \right] \\ kckck(E) = \left[ 0,2 \right] \cup \left[ 4,5 \right] \\ ckckc(E) = \left( -\infty,0 \right) \cup \left( 2,\infty \right) \\ ckckck(E) = \left( -\infty,0 \right) \cup \left( 2,4 \right) \cup \left( 5,\infty \right) \\ kckckc(E) = \left( \right. -\infty,0 \left. \right] \cup \left[ \right. 2,\infty \left. \right) \\ ckckckc(E) = \left( 0,2 \right) $$

$\blacksquare$