쿠라토프스키의 폐포-여집합 문제(Kuratowski's closure-complement problem)는 한 집합에 폐포와 여집합을 취하여 서로 다른 집합을 몇 개까지 만들 수 있는지 묻는 문제이다. 1922년 카지미에시 쿠라토프스키가 문제를 소개하였다.[1]
진술
Question — 한 집합에 폐포와 여집합 연산을 사용해 만들 수 있는 서로 다른 집합의 개수는 얼마인가?
풀이
정의 1. 위상공간 에 대해, 를 다음과 같이 정의하자.
이때 는 의 폐포이다.
명제 2. 이때 는 로 정의된다.
정의 3. 위상공간 에 대해, 를 다음과 같이 정의하자.
이때 는 의 내부이다.
명제 4.
명제 5.
Proof
임의의 에 대해 임을 보이면 된다.
Claim 1.
내부의 정의에 의해
이다. 그러면 명제 2에 의해
을 얻는다.
Claim 2.
폐포의 정의에 의해
이므로, 명제 4에 의해
이고 따라서
이다.
명제 6.
명제 7.
Proof
명제 5와 6에 의해,
명제 8.
Proof
명제 2와 7에 의해,
명제 9. 의 임의의 유한 번 합성을 모은 집합의 원소의 개수는 14를 넘지 않는다.
Proof
명제 2에 의해, 을 제외한 의 임의의 유한 번 합성은 다음 꼴 중 하나이다:
-
|
|
(1)
|
-
|
|
(2)
|
-
|
|
(3)
|
-
|
|
(4)
|
그런데 명제 7, 8에서 이고 이므로 (1)은
중 하나이며, (2)는
중 하나이고, (3)은
중 하나이고, (4)는
중 하나이다. 따라서 의 임의의 유한 번 합성은 개를 넘지 않는다.
예시
명제 9에서 한 집합에 폐포와 여집합 연산으로 만들어낼 수 있는 서로 다른 집합의 수가 14 이하임을 보였다. 그렇다면 폐포와 여집합 연산으로 만들어낼 수 있는 서로 다른 집합의 수가 14인 집합이 존재하는가? 답은 "예"이다.
예 10. 의 부분집합
이 주어졌다고 하자. 이때 의 유한 번 합성을 계산한 결과는 다음과 같다.[2]
집합 |
결과 |
집합 |
결과
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
변형 문제
쿠라토프스키 모노이드
각주
외부 링크