쿠라토프스키의 폐포-여집합 문제

쿠라토프스키의 폐포-여집합 문제(Kuratowski's closure-complement problem)는 한 집합에 폐포와 여집합을 취하여 서로 다른 집합을 몇 개까지 만들 수 있는지 묻는 문제이다. 1922년 카지미에시 쿠라토프스키가 문제를 소개하였다.^[1]

진술

Question — 한 집합에 폐포와 여집합 연산을 사용해 만들 수 있는 서로 다른 집합의 개수는 얼마인가?

풀이

정의 1. 위상공간 $X$ 에 대해, ${\mathsf {k}},{\mathsf {c}}:{\mathcal {P}}(X)\to {\mathcal {P}}(X)$ 를 다음과 같이 정의하자.

{\mathsf {k}}A={\overline {A}},\quad {\mathsf {c}}A=X\setminus A

이때 ${\overline {A}}$ 는 $A$ 의 폐포이다.

명제 2. ${\mathsf {kk}}={\mathsf {k}},\quad {\mathsf {cc}}=\epsilon .$ 이때 $\epsilon :{\mathcal {P}}(X)\to {\mathcal {P}}(X)$ 는 $\epsilon A=A$ 로 정의된다.

Proof

자명하다(폐포, 여집합 문서를 참고하라).

정의 3. 위상공간 $X$ 에 대해, ${\mathsf {i}}:{\mathcal {P}}(X)\to {\mathcal {P}}(X)$ 를 다음과 같이 정의하자.

{\mathsf {i}}A=\operatorname {int} A

이때 $\operatorname {int} A$ 는 $A$ 의 내부이다.

명제 4. ${\mathsf {ii}}={\mathsf {i}}.$

Proof

자명하다(내부 문서를 참고하라).

명제 5. ${\mathsf {kiki}}={\mathsf {ki}}.$

Proof

임의의 $A\subset X$ 에 대해 ${\mathsf {kiki}}A={\mathsf {ki}}A$ 임을 보이면 된다.

Claim 1. ${\mathsf {kiki}}A\subset {\mathsf {ki}}A.$

내부의 정의에 의해

{\mathsf {iki}}A\subset {\mathsf {ki}}A

이다. 그러면 명제 2에 의해

{\mathsf {kiki}}A\subset {\mathsf {kki}}A={\mathsf {ki}}A

을 얻는다.

Claim 2. ${\mathsf {kiki}}A\supset {\mathsf {ki}}A.$

폐포의 정의에 의해

{\mathsf {ki}}A\supset {\mathsf {i}}A

이므로, 명제 4에 의해

{\mathsf {iki}}A\supset {\mathsf {ii}}A={\mathsf {i}}A

이고 따라서

{\mathsf {kiki}}A\supset {\mathsf {ki}}A

이다.

명제 6. ${\mathsf {i}}={\mathsf {ckc}}.$

Proof

Claim. ${\mathsf {kc}}={\mathsf {ci}}.$

먼저 ${\mathsf {i}}A\subset A$ 이므로 ${\mathsf {c}}A\subset {\mathsf {ci}}A$ 이고, 따라서

{\mathsf {kc}}A\subset {\mathsf {kci}}A={\mathsf {ci}}A

이다. 이제 ${\mathsf {kc}}A\supset {\mathsf {ci}}A$ 임을 보이자. $x\in {\mathsf {ci}}A$ 를 하나 고르자. 그러면 $x\notin {\mathsf {i}}A$ 이므로, $x$ 를 포함하는 임의의 열린집합은 ${\mathsf {c}}A$ 의 원소를 적어도 하나 가지는데, 이는 곧 $x\in {\mathsf {kc}}A$ 를 의미한다. 따라서 ${\mathsf {ci}}A\subset {\mathsf {kc}}A$ 이다.

Claim으로부터 명제 2에 의해

{\mathsf {ckc}}={\mathsf {cci}}={\mathsf {i}}

임을 안다.

명제 7. ${\mathsf {kckckckc}}={\mathsf {kckc}}.$

Proof

명제 5와 6에 의해,

{\mathsf {kckckckc}}={\mathsf {kiki}}={\mathsf {ki}}={\mathsf {kckc}}.

명제 8. ${\mathsf {kckckck}}={\mathsf {kck}}.$

Proof

명제 2와 7에 의해,

{\mathsf {kckckck}}={\mathsf {kckckckcc}}={\mathsf {kckcc}}={\mathsf {kck}}.

명제 9. ${\mathsf {k}},{\mathsf {c}}$ 의 임의의 유한 번 합성을 모은 집합의 원소의 개수는 14를 넘지 않는다.

Proof

명제 2에 의해, $\epsilon$ 을 제외한 ${\mathsf {k}},{\mathsf {c}}$ 의 임의의 유한 번 합성은 다음 꼴 중 하나이다:

${\mathsf {k(ck}}\dots {\mathsf {ck)}}$

(1)

${\mathsf {kc}}\dots {\mathsf {kc}}$

(2)

${\mathsf {ck}}\dots {\mathsf {ck}}$

(3)

${\mathsf {c(kc}}\dots {\mathsf {kc)}}$

(4)

그런데 명제 7, 8에서 ${\mathsf {kckckckc}}={\mathsf {kckc}}$ 이고 ${\mathsf {kckckck}}={\mathsf {kck}}$ 이므로 (1)은

{\mathsf {k}},{\mathsf {kck}},{\mathsf {kckck}}

중 하나이며, (2)는

{\mathsf {kc}},{\mathsf {kckc}},{\mathsf {kckckc}}

중 하나이고, (3)은

{\mathsf {ck}},{\mathsf {ckck}},{\mathsf {ckckck}}

중 하나이고, (4)는

{\mathsf {c}},{\mathsf {ckc}},{\mathsf {ckckc}},{\mathsf {ckckckc}}

중 하나이다. 따라서 ${\mathsf {k}},{\mathsf {c}}$ 의 임의의 유한 번 합성은 $1+3\times 3+4=14$ 개를 넘지 않는다.

예시

명제 9에서 한 집합에 폐포와 여집합 연산으로 만들어낼 수 있는 서로 다른 집합의 수가 14 이하임을 보였다. 그렇다면 폐포와 여집합 연산으로 만들어낼 수 있는 서로 다른 집합의 수가 14인 집합이 존재하는가? 답은 "예"이다.

예 10. $\mathbb {R}$ 의 부분집합

A=(-\infty ,1)\cup (1,2)\cup ((2,4)\cap (\mathbb {R} \setminus \mathbb {Q} ))\cup \{5\}

이 주어졌다고 하자. 이때 ${\mathsf {k}},{\mathsf {c}}$ 의 유한 번 합성을 계산한 결과는 다음과 같다.^[2]

집합	결과	집합	결과
$A$	$(-\infty ,1)\cup (1,2)\cup ((2,4)\cap (\mathbb {R} \setminus \mathbb {Q} ))\cup \{5\}$	${\mathsf {c}}A$	$\{1\}\cup \{2\}\cup ((2,4)\cap \mathbb {Q} )\cup [4,5)\cup (5,\infty )$
${\mathsf {k}}A$	$(-\infty ,4]\cup \{5\}$	${\mathsf {kc}}A$	$\{1\}\cup [2,\infty )$
${\mathsf {ck}}A$	$(4,5)\cup (5,\infty )$	${\mathsf {ckc}}A$	$(-\infty ,1)\cup (1,2)$
${\mathsf {kck}}A$	$[4,\infty )$	${\mathsf {kckc}}A$	$(-\infty ,2]$
${\mathsf {ckck}}A$	$(-\infty ,4)$	${\mathsf {ckckc}}A$	$(2,\infty )$
${\mathsf {kckck}}A$	$(-\infty ,4]$	${\mathsf {kckckc}}A$	$[2,\infty )$
${\mathsf {ckckck}}A$	$(4,\infty )$	${\mathsf {ckckckc}}A$	$(-\infty ,2)$

정의 11. 예 10의 집합 $A$ 와 같이 폐포와 여집합을 취해 서로 다른 14개의 집합을 만들 수 있는 집합을 쿠라토프스키 14 집합(Kuratowski 14-set)이라고 한다.

변형 문제

문제를 일반화하여 한 집합에 폐포, 내부, 여집합, 합집합, 교집합 중 일부를 취해 만들 수 있는 서로 다른 집합의 개수를 물을 수도 있을 것이다.

일반적으로, 한 집합 $A$ 의 모든 자기사상의 집합에 합성함수 연산을 부여하면 모노이드가 된다. 이 모노이드를 ${\mathsf {End}}(A)$ 라 하자. 그러면 ${\mathsf {k}},{\mathsf {c}},{\mathsf {i}}\in {\mathsf {End}}({\mathcal {P}}(X))$ 이다.

정의 12. 위상공간 $X$ 에 대해 $\wedge ,\vee :{\mathsf {End}}(X)\times {\mathsf {End}}(X)\to {\mathsf {End}}(X)$ 를 다음과 같이 정의하자.

(\varphi \wedge \psi )A=\varphi A\cap \psi A,\quad (\varphi \vee \psi )A=\varphi A\cup \psi A

다음 표는 한 집합에 연산을 취해 얻을 수 있는 서로 다른 집합의 최댓값을 정리한 것이다.^[3]

연산	$\{\epsilon \}$	$\{\wedge \}$	$\{\vee \}$	$\{\wedge ,\vee \}$
$\{\epsilon \}$	1	1	1	1
$\{{\mathsf {i}}\}$	2	2	2	2
$\{{\mathsf {k}}\}$	2	2	2	2
$\{{\mathsf {c}}\}$	2	4	4	4
$\{{\mathsf {i}},{\mathsf {k}}\}$	7	13	13	35
$\{{\mathsf {i}},{\mathsf {c}}\}=\{{\mathsf {k}},{\mathsf {c}}\}=\{{\mathsf {k}},{\mathsf {i}},{\mathsf {c}}\}$	14	∞	∞	∞