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

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

진술

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}}$의 유한 번 합성을 계산한 결과는 다음과 같다.

집합	결과	집합	결과
$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)이라고 한다.

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$?

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

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \mathcal{B}=\{\emptyset,\{1\},\{6\},\{1,2\},\{3,4\},\{5,6\}\}}

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

집합	결과	집합	결과
$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 집합이고 $|A|=3$이다. 그러나 $|E|<3$인 경우는 존재하지 않는다.

변형 문제

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

일반적으로, 한 집합 $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$

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

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

외부 링크

• Bowron, Mark; Weisstein, Eric W. “Kuratowski's Closure-Complement Problem”. 《Wolfram Mathworld》. 2017년 5월 1일에 확인함.