쿠라토프스키의 폐포-여집합 문제(Kuratowski's closure-complement problem)는 한 집합에 폐포와 여집합을 취하여 서로 다른 집합을 몇 개까지 만들 수 있는지 묻는 문제이다. 1922년 카지미에시 쿠라토프스키가 문제를 소개하였다.[1]
진술
Question — 한 집합에 폐포와 여집합 연산을 사용해 만들 수 있는 서로 다른 집합의 개수는 얼마인가?
풀이
정의 1. 위상공간
에 대해,
를 다음과 같이 정의하자.
![{\displaystyle {\mathsf {k}}A={\overline {A}},\quad {\mathsf {c}}A=X\setminus A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4dc218555c4d5adf5f4ca86698bf80ecd70eaba)
이때
는
의 폐포이다.
명제 2.
이때
는
로 정의된다.
정의 3. 위상공간
에 대해,
를 다음과 같이 정의하자.
![{\displaystyle {\mathsf {i}}A=\operatorname {int} A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2d906ad3721f38f57798d7018f357e16affe4b0)
이때
는
의 내부이다.
명제 4. ![{\displaystyle {\mathsf {ii}}={\mathsf {i}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f07482d820f12e922aa2c609fba25209ea969ce2)
명제 5. ![{\displaystyle {\mathsf {kiki}}={\mathsf {ki}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3a411ade79e2e59718a893419a61fe11f04dce5)
Proof
임의의
에 대해
임을 보이면 된다.
Claim 1.
내부의 정의에 의해
![{\displaystyle {\mathsf {iki}}A\subset {\mathsf {ki}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a55bd4809f3fec33ef2968184ede0a936225ccc)
이다. 그러면 명제 2에 의해
![{\displaystyle {\mathsf {kiki}}A\subset {\mathsf {kki}}A={\mathsf {ki}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a383d9d055dd9ec5bc4e5b1e6ab85c26be1e9633)
을 얻는다.
Claim 2.
폐포의 정의에 의해
![{\displaystyle {\mathsf {ki}}A\supset {\mathsf {i}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5043273a0964162860ee3e6bfba3a2932b62db05)
이므로, 명제 4에 의해
![{\displaystyle {\mathsf {iki}}A\supset {\mathsf {ii}}A={\mathsf {i}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/799c41c558728f6b8c03f40143f5bda425839979)
이고 따라서
![{\displaystyle {\mathsf {kiki}}A\supset {\mathsf {ki}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31b13da71706e86d6f417a6b07355a2fa094f0ff)
이다.
명제 6. ![{\displaystyle {\mathsf {i}}={\mathsf {ckc}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba5c399b005743c973a200a806e1ce080077339c)
명제 7. ![{\displaystyle {\mathsf {kckckckc}}={\mathsf {kckc}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c66e5b662181466ea0317b730cf4b990a65131c8)
Proof
명제 5와 6에 의해,
![{\displaystyle {\mathsf {kckckckc}}={\mathsf {kiki}}={\mathsf {ki}}={\mathsf {kckc}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cdfe1cb370ee3ee861017c54c6092ec3291133f)
명제 8. ![{\displaystyle {\mathsf {kckckck}}={\mathsf {kck}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9052ac19b2fd3edeedb3b301c053883f91103406)
Proof
명제 2와 7에 의해,
![{\displaystyle {\mathsf {kckckck}}={\mathsf {kckckckcc}}={\mathsf {kckcc}}={\mathsf {kck}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/082b46ac76814f449e847063f333e043a738b2d9)
명제 9.
의 임의의 유한 번 합성을 모은 집합의 원소의 개수는 14를 넘지 않는다.
Proof
명제 2에 의해,
을 제외한
의 임의의 유한 번 합성은 다음 꼴 중 하나이다:
-
![{\displaystyle {\mathsf {k(ck}}\dots {\mathsf {ck)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ad3ec364aa403dea3d4cbf9e831d28ad9d4deaa)
|
|
(1)
|
-
![{\displaystyle {\mathsf {kc}}\dots {\mathsf {kc}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49ea552f303c6d7be99ab7bf9aed622c1b93298b)
|
|
(2)
|
-
![{\displaystyle {\mathsf {ck}}\dots {\mathsf {ck}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc2e55665b1cf8c479d7d38ffb5fc6c6a43eff5b)
|
|
(3)
|
-
![{\displaystyle {\mathsf {c(kc}}\dots {\mathsf {kc)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3cf950433730a6abd58a12e5cf43bbc7445d1196)
|
|
(4)
|
그런데 명제 7, 8에서
이고
이므로 (1)은
![{\displaystyle {\mathsf {k}},{\mathsf {kck}},{\mathsf {kckck}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59f383ad0bdbc3ff6c6af84fcf422876212db08d)
중 하나이며, (2)는
![{\displaystyle {\mathsf {kc}},{\mathsf {kckc}},{\mathsf {kckckc}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e58faa9865a137624937d0ff842a7082f42c620c)
중 하나이고, (3)은
![{\displaystyle {\mathsf {ck}},{\mathsf {ckck}},{\mathsf {ckckck}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/011c4a8438ceae2cb6a6d96d78e9bd97a0f7483b)
중 하나이고, (4)는
![{\displaystyle {\mathsf {c}},{\mathsf {ckc}},{\mathsf {ckckc}},{\mathsf {ckckckc}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/661f0cd975035581f065af8cdc6cb674e4f28a30)
중 하나이다. 따라서
의 임의의 유한 번 합성은
개를 넘지 않는다.
쿠라토프스키 14 집합
명제 9에서 한 집합에 폐포와 여집합 연산으로 만들어낼 수 있는 서로 다른 집합의 수가 14 이하임을 보였다. 그렇다면 폐포와 여집합 연산으로 만들어낼 수 있는 서로 다른 집합의 수가 14인 집합이 존재하는가? 답은 "예"이다.
예 10.
의 부분집합
![{\displaystyle A=(-\infty ,1)\cup (1,2)\cup ((2,4)\cap (\mathbb {R} \setminus \mathbb {Q} ))\cup \{5\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/868899a93ac1af317d73f9acdad34650b37526d0)
이 주어졌다고 하자. 이때
의 유한 번 합성을 계산한 결과는 다음과 같다.[2]
집합 |
결과 |
집합 |
결과
|
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3) |
![{\displaystyle (-\infty ,1)\cup (1,2)\cup ((2,4)\cap (\mathbb {R} \setminus \mathbb {Q} ))\cup \{5\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e55486d327d98c15f165a32f47ee82492a381bf) |
![{\displaystyle {\mathsf {c}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ca294d4dec0af35926bf0324ab523172672b98a) |
|
![{\displaystyle {\mathsf {k}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/031206065491dc6538f47445ae8ad43ec76e1edf) |
![{\displaystyle (-\infty ,4]\cup \{5\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0bbc8fb01896653cd66c77bd38fc20f952d8600) |
![{\displaystyle {\mathsf {kc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f3a6e4019892b514a3a27788a5d3a267fb3bcd5) |
|
![{\displaystyle {\mathsf {ck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9337e5aae4c4e65b12d9aa9fcb0951a46508aae0) |
![{\displaystyle (4,5)\cup (5,\infty )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4b4d8a5bd764514877175eb6440020a5cde1395) |
![{\displaystyle {\mathsf {ckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4385e3beed1ae7984e6f8c2ab052d5d8ddd8bb21) |
|
![{\displaystyle {\mathsf {kck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92ffc2b5601b3b574fb0b6e3322b5a1e56d7492d) |
![{\displaystyle [4,\infty )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7721ea88bccfe5687a9ff007b4c88fc1941a63c9) |
![{\displaystyle {\mathsf {kckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ab9c0a58ea687f6e338c646cb31ce1b8dc76914) |
|
![{\displaystyle {\mathsf {ckck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/160692dfdf4f36573786eca21dc2d49ff673cf3b) |
![{\displaystyle (-\infty ,4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4956f735442174051b617339e8d42305a1e5d626) |
![{\displaystyle {\mathsf {ckckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/219debd4d907eb5fa211c93ae441bdfcd3f0e767) |
|
![{\displaystyle {\mathsf {kckck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d48b26976c38df98a0e72643e0cd81def794aff) |
![{\displaystyle (-\infty ,4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93ed16d829c5538f73aa8c144287a1500f31b3e8) |
![{\displaystyle {\mathsf {kckckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a409a2963fc668ad039c5248bc5ba032b90ce89) |
|
![{\displaystyle {\mathsf {ckckck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b17989df13662245bea544edad5b4a923a7324f) |
![{\displaystyle (4,\infty )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a4d340b505ea81f1d2bf12eeffeb00a3d7bf367) |
![{\displaystyle {\mathsf {ckckckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71ca209070d787607f52ef62b401dc3112f82bf2) |
|
정의 11. 예 10의 집합
와 같이 폐포와 여집합을 취해 서로 다른 14개의 집합을 만들 수 있는 집합을 쿠라토프스키 14 집합(Kuratowski 14-set) 또는 간단히 14 집합(14-set)이라고 한다.
정리 12.
의 부분집합
가 쿠라토프스키 14 집합일 필요충분조건은 열린구간
가 존재해
와
가
에서 조밀하고,
와
가 공집합이 아니고 상대적으로 열린집합이며 조밀한 곳이 없는
의 부분집합을 포함하는 것이다.[3]:367, Theorem 4
2012년 Mark Bowron은 Mathematics Magazine에 다음 문제를 제시하였다.[4]
위상공간
의 부분집합
에 폐포와 여집합을 어떤 순서로 반복적으로 적용해 서로 다른 집합 14개를 얻을 수 있으면
를 쿠라토프스키 14 집합이라고 한다.
인 쿠라토프스키 14 집합
가 존재한다는 것은 알려져 있다.
인 경우가 존재하는가?
A subset
of a topological space
is called a Kuratowski 14-set if 14 distinct sets can be obtained by repeatedly applying closure and complement to
in some order. It is known that Kuratowski 14-sets
with
exist. Do any exist with
?
인 경우는 원소 수가 7인 위상공간에서 찾을 수 있다. 집합
에 다음 집합
![{\displaystyle {\mathcal {B}}=\{\emptyset ,X,\{1\},\{6\},\{1,2\},\{3,4\},\{5,6\}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5c82955468b4a84582432a767e36703ab8a05cb)
를 기저로 하는 위상을 부여하자. 그러면
는
이고,
집합 |
결과 |
집합 |
결과
|
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3) |
![{\displaystyle \{1,3,5\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2dff31162647fd4911bca0b34f555de99928d1cb) |
![{\displaystyle {\mathsf {c}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ca294d4dec0af35926bf0324ab523172672b98a) |
|
![{\displaystyle {\mathsf {k}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/031206065491dc6538f47445ae8ad43ec76e1edf) |
![{\displaystyle \{1,2,3,4,5,7\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6949c663e35877b656f84fa7ebd3e72a5c89164c) |
![{\displaystyle {\mathsf {kc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f3a6e4019892b514a3a27788a5d3a267fb3bcd5) |
|
![{\displaystyle {\mathsf {ck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9337e5aae4c4e65b12d9aa9fcb0951a46508aae0) |
![{\displaystyle \{6\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc84ad359e51ec16471952fc6113daab9da9a37a) |
![{\displaystyle {\mathsf {ckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4385e3beed1ae7984e6f8c2ab052d5d8ddd8bb21) |
|
![{\displaystyle {\mathsf {kck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92ffc2b5601b3b574fb0b6e3322b5a1e56d7492d) |
![{\displaystyle \{5,6,7\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d6281e3b45de7ceba291bc23b22de7ab57d9cc) |
![{\displaystyle {\mathsf {kckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ab9c0a58ea687f6e338c646cb31ce1b8dc76914) |
|
![{\displaystyle {\mathsf {ckck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/160692dfdf4f36573786eca21dc2d49ff673cf3b) |
![{\displaystyle \{1,2,3,4\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebf4ca66fd59843b349aed8ffa7655c1aae77625) |
![{\displaystyle {\mathsf {ckckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/219debd4d907eb5fa211c93ae441bdfcd3f0e767) |
|
![{\displaystyle {\mathsf {kckck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d48b26976c38df98a0e72643e0cd81def794aff) |
![{\displaystyle \{1,2,3,4,7\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53e9fa093328323671199a317cb1b9f6216149d9) |
![{\displaystyle {\mathsf {kckckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a409a2963fc668ad039c5248bc5ba032b90ce89) |
|
![{\displaystyle {\mathsf {ckckck}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b17989df13662245bea544edad5b4a923a7324f) |
![{\displaystyle \{5,6\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b77c583e394de8643072aeabf0bb46b0cbab75ae) |
![{\displaystyle {\mathsf {ckckckc}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71ca209070d787607f52ef62b401dc3112f82bf2) |
|
이므로 쿠라토프스키 14 집합이다.[5] 그러나
인 경우는 존재하지 않는다.[6][7]
변형 문제
문제를 일반화하여 한 집합에 폐포, 내부, 여집합, 합집합, 교집합 중 일부를 취해 만들 수 있는 서로 다른 집합의 개수를 물을 수도 있을 것이다.
일반적으로, 한 집합
의 모든 자기사상의 집합에 합성함수 연산을 부여하면 모노이드가 된다. 이 모노이드를
라 하자. 그러면
이다.
정의 13. 위상공간
에 대해
를 다음과 같이 정의하자.
![{\displaystyle (\varphi \wedge \psi )A=\varphi A\cap \psi A,\quad (\varphi \vee \psi )A=\varphi A\cup \psi A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33476a4d42f116bf121c82856988f7ab1bc814ab)
다음 표는 한 집합에 연산을 취해 얻을 수 있는 서로 다른 집합의 최댓값을 정리한 것이다.[8]
연산 |
![{\displaystyle \{\epsilon \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/085f82785ac59606de3cdfd3336a7eb31a04f4e4) |
![{\displaystyle \{\wedge \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e17b8839fe626192d8a4826ee32b97b3357bde0c) |
![{\displaystyle \{\vee \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0da05c677a3bb20ee3b1b9a74409f98618ccb07) |
|
![{\displaystyle \{\epsilon \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/085f82785ac59606de3cdfd3336a7eb31a04f4e4) |
1 |
1 |
1 |
1
|
![{\displaystyle \{{\mathsf {i}}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51e0885080ca4c76b6c2a7fb2a07c2d70b4e17f3) |
2 |
2 |
2 |
2
|
![{\displaystyle \{{\mathsf {k}}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffe21718659b8db8c668f63a2ef165d9ce2b028f) |
2 |
2 |
2 |
2
|
![{\displaystyle \{{\mathsf {c}}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43deece4ec24dc7db7933c6536e7d9a7f829c44c) |
2 |
4 |
4 |
4
|
![{\displaystyle \{{\mathsf {i}},{\mathsf {k}}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5381b6f432d8fb6791d74709880d2c99a0d33025) |
7 |
13 |
13 |
35
|
![{\displaystyle \{{\mathsf {i}},{\mathsf {c}}\}=\{{\mathsf {k}},{\mathsf {c}}\}=\{{\mathsf {k}},{\mathsf {i}},{\mathsf {c}}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fcdb5b69204bfe1f5be94e406797801eb7decf6) |
14 |
∞ |
∞ |
∞
|
쿠라토프스키 모노이드
각주
외부 링크