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

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

문제와 풀이

문제

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

풀이

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

${\mathsf {k}}A={\overline {A}},\quad {\mathsf {c}}A=X\setminus A,\quad {\mathsf {i}}A=\operatorname {int} A$

이때 ${\overline {A}}$는 $A$의 폐포, $\operatorname {int} A$는 $A$의 내부이다.

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

Proof

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

명제 3. ${\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$

이므로, 명제 2에 의해

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

이고 따라서

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

이다.

명제 4. ${\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}}$

임을 안다.

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

Proof

명제 3와 4에 의해,

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

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

Proof

명제 2와 5에 의해,

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

명제 7. ${\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)

그런데 명제 5, 6에서 ${\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$개를 넘지 않는다.

명제 7와 같은 방법으로 다음 명제를 증명할 수 있다.

명제 8. ${\mathsf {k}},{\mathsf {i}}$의 임의의 유한 번 합성을 모은 집합의 원소의 개수는 7을 넘지 않는다. 구체적으로 나열하면 다음과 같다.

$\{\epsilon ,{\mathsf {i}},{\mathsf {k}},{\mathsf {ik}},{\mathsf {ki}},{\mathsf {iki}},{\mathsf {kik}}\}$

쿠라토프스키 14 집합

정의와 예시

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

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

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

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

집합	결과	집합	결과
$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)$

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

정리 11. $\mathbb {R}$의 부분집합 $A$가 쿠라토프스키 14 집합일 필요충분조건은 열린구간 $I$가 존재해 $A$와 ${\mathsf {c}}A$가 $I$에서 조밀하고, $A$와 ${\mathsf {c}}A$가 공집합이 아니고 상대적으로 열린집합이며 조밀한 곳이 없는 $\mathbb {R}$의 부분집합을 포함하는 것이다.

최대-최소 문제

2012년 Mark Bowron은 Mathematics Magazine에 다음 문제를 제시하였다.

위상공간 $X$의 부분집합 $E$에 폐포와 여집합을 어떤 순서로 반복적으로 적용해 서로 다른 집합 14개를 얻을 수 있으면 $E$를 쿠라토프스키 14 집합이라고 한다. $|E|=3$인 쿠라토프스키 14 집합 $E$가 존재한다는 것은 알려져 있다. $|E|<3$인 경우가 존재하는가?
A subset $E$ of a topological space $X$ is called a Kuratowski 14-set if 14 distinct sets can be obtained by repeatedly applying closure and complement to $E$ in some order. It is known that Kuratowski 14-sets $E$ with $|E|=3$ exist. Do any exist with $|E|<3$?

예 12. $|E|=3$인 경우는 원소 수가 7인 위상공간에서 찾을 수 있다. 집합 $X=\{1,2,3,4,5,6,7\}$에 다음 집합

${\mathcal {B}}=\{\emptyset ,X,\{1\},\{6\},\{1,2\},\{3,4\},\{5,6\}\}$

를 기저로 하는 위상을 부여하자. 그러면 $A=\{1,3,5\}$는 $|A|=3$이고,

집합	결과	집합	결과
$A$	$\{1,3,5\}$	${\mathsf {c}}A$	$\{2,4,6,7\}$
${\mathsf {k}}A$	$\{1,2,3,4,5,7\}$	${\mathsf {kc}}A$	$\{2,3,4,5,6,7\}$
${\mathsf {ck}}A$	$\{6\}$	${\mathsf {ckc}}A$	$\{1\}$
${\mathsf {kck}}A$	$\{5,6,7\}$	${\mathsf {kckc}}A$	$\{1,2,7\}$
${\mathsf {ckck}}A$	$\{1,2,3,4\}$	${\mathsf {ckckc}}A$	$\{3,4,5,6\}$
${\mathsf {kckck}}A$	$\{1,2,3,4,7\}$	${\mathsf {kckckc}}A$	$\{3,4,5,6,7\}$
${\mathsf {ckckck}}A$	$\{5,6\}$	${\mathsf {ckckckc}}A$	$\{1,2\}$

이므로 쿠라토프스키 14 집합이다. 그러나 $|E|<3$인 경우는 존재하지 않는다.

정리 13. 위상공간 $X$의 부분집합 $E$가 쿠라토프스키 14 집합이면,

• $|E|\geq 3$이다.
• $|X|\geq 7$이다.

정리 14. 유한 T₀ 공간의 집합에 폐포와 여집합을 취해 만들 수 있는 서로 다른 집합의 수는 최대 10개이고, 따라서 쿠라토프스키 14 집합을 가지지 않는다.

부분순서 구조

집합 $A$의 모든 자기사상의 집합을 ${\mathsf {End}}(A)$라 하자. 그러면 ${\mathsf {k}},{\mathsf {c}},{\mathsf {i}}\in {\mathsf {End}}({\mathcal {P}}(X))$이다.

정의 15. ${\mathsf {End}}({\mathcal {P}}(X))$ 위의 관계 $\leq$를 다음과 같이 정의하자.

$\varphi \leq \psi \Longleftrightarrow \varphi A\subset \psi A,\;\forall A\in {\mathcal {P}}(X)$

정리 16. $({\mathsf {End}}({\mathcal {P}}(X)),\leq )$는 부분순서집합이다.

폐포와 내부의 기본적인 성질로부터 다음 명제를 이끌어낼 수 있다.

명제 17. 임의의 $\varphi ,\psi \in {\mathsf {End}}({\mathcal {P}}(X))$에 대해 다음이 성립한다.

• ${\mathsf {i}}\leq \epsilon \leq {\mathsf {k}}$
• ${\mathsf {i}}\varphi \leq \varphi$
• $\varphi \leq {\mathsf {k}}\varphi$
• $\varphi \leq \psi$이면 ${\mathsf {i}}\varphi \leq {\mathsf {i}}\psi$이다.
• $\varphi \leq \psi$이면 ${\mathsf {k}}\varphi \leq {\mathsf {k}}\psi$이다.

명제 18. 명제 17에 의해 다음 식이 성립한다.

${\mathsf {i}}\leq {\mathsf {iki}}\leq {\mathsf {ki}}\leq {\mathsf {kik}}\leq {\mathsf {k}}$

(1)

${\mathsf {i}}\leq {\mathsf {iki}}\leq {\mathsf {ik}}\leq {\mathsf {kik}}\leq {\mathsf {k}}$

(2)

한편, 예 9, 12로부터 일반적으로

• ${\mathsf {iki}}\not \leq \epsilon$, $\epsilon \not \leq {\mathsf {iki}}$
• ${\mathsf {ki}}\not \leq {\mathsf {ik}}$, ${\mathsf {ik}}\not \leq {\mathsf {ki}}$, ${\mathsf {ki}}\not \leq \epsilon$, $\epsilon \not \leq {\mathsf {ki}}$, ${\mathsf {ik}}\not \leq \epsilon$, $\epsilon \not \leq {\mathsf {ik}}$
• ${\mathsf {kik}}\not \leq \epsilon$, $\epsilon \not \leq {\mathsf {kik}}$

임을 안다. 그러므로 $(\{\epsilon ,{\mathsf {i}},{\mathsf {k}},{\mathsf {ik}},{\mathsf {ki}},{\mathsf {iki}},{\mathsf {kik}}\},\leq )$의 하세 도형은 다음과 같다.

$(\{\epsilon ,{\mathsf {c}},{\mathsf {k}},{\mathsf {ck}},{\mathsf {kc}},{\mathsf {ckc}},{\mathsf {kck}},{\mathsf {ckck}},{\mathsf {kckc}},{\mathsf {ckckc}},{\mathsf {kckck}},{\mathsf {ckckck}},{\mathsf {kckckc}},{\mathsf {ckckckc}}\},\leq )$의 하세 도형은 다음과 같다.

변형 문제

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

정의 19. 위상공간 $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$

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

연산	$\{\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	∞	∞	∞

예 20. 위상공간의 집합에 연산 ${\mathsf {k}},{\mathsf {i}},\vee$를 적용해 만들 수 있는 서로 다른 집합의 개수의 최댓값은 13이다. 실제로 $\mathbb {R}$의 부분집합 $A$를

$A=\left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup (\mathbb {Q} \cap (2,3))\cup (3,4)\cup (4,5)$

로 정의하면,

집합	결과	집합	결과
$A$	$\left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup (\mathbb {Q} \cap (2,3))\cup (3,4)\cup (4,5)$	$A\cup {\mathsf {kik}}A$	$\left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup [2,5]$
${\mathsf {k}}A$	$\{0\}\cup \left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup [2,5]$	$A\cup {\mathsf {ik}}A$	$\left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup (2,5)$
${\mathsf {ik}}A$	$(2,5)$	$A\cup {\mathsf {ki}}A$	$\left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup (\mathbb {Q} \cap (2,3))\cup [3,5]$
${\mathsf {kik}}A$	$[2,5]$	$A\cup {\mathsf {iki}}A$	$\left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup (\mathbb {Q} \cap (2,3))\cup (3,5)$
${\mathsf {i}}A$	$(3,4)\cup (4,5)$	$A\cup {\mathsf {ki}}A\cup {\mathsf {ik}}A$	$\left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup (2,5]$
${\mathsf {ki}}A$	$[3,5]$	${\mathsf {ki}}A\cup {\mathsf {ik}}A$	$(2,5]$
${\mathsf {iki}}A$	$(3,5)$

임을 안다.

예 21. 위상공간의 집합에 연산 ${\mathsf {k}},{\mathsf {i}},\wedge$를 적용해 만들 수 있는 서로 다른 집합의 개수의 최댓값은 13이다. 실제로 $\mathbb {R}$의 부분집합 $A$를

${\begin{aligned}A=&\left\{{\frac {1}{n}}:n\in \mathbb {N} \right\}\cup \left([2,4]-\left\{3+{\frac {1}{n}}:n\in \mathbb {N} \right\}\right)\\&\cup \left((5,7]\cap \left(\mathbb {Q} \cup \bigcup _{n=1}^{\infty }\left(6+{\frac {1}{2n\pi }},6+{\frac {1}{(2n-1)\pi }}\right]\right)\right)\end{aligned}}$

로 정의해 확인해보라.

링크

• Bowron, Mark; Weisstein, Eric W. “Kuratowski's Closure-Complement Problem”. 《Wolfram Mathworld》. 2017년 5월 1일에 확인함. 
• “Kuratowski's Closure-Complement Problem”. 《ProofWiki》. 2017년 5월 6일에 확인함. 
• “Kuratowski's closure-complement problem”. 《Wikipedia, The Free Encyclopedia》. 2017년 5월 6일에 확인함. 
• “쿠라토프스키 모노이드”. 《위키백과, 우리 모두의 백과사전》. 2017년 5월 6일에 확인함. 
• “Kuratowski’s Closure-Complement Cornucopia”. 2017년 6월 11일에 확인함.