쿠라토프스키의 폐포-여집합 문제(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)는
중 하나이다. 따라서 의 임의의 유한 번 합성은 개를 넘지 않는다.
쿠라토프스키 14 집합
명제 9에서 한 집합에 폐포와 여집합 연산으로 만들어낼 수 있는 서로 다른 집합의 수가 14 이하임을 보였다. 그렇다면 폐포와 여집합 연산으로 만들어낼 수 있는 서로 다른 집합의 수가 14인 집합이 존재하는가? 답은 "예"이다.
예 10. 의 부분집합
이 주어졌다고 하자. 이때 의 유한 번 합성을 계산한 결과는 다음과 같다.[2]
집합 |
결과 |
집합 |
결과
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
정의 11. 예 10의 집합 와 같이 폐포와 여집합을 취해 서로 다른 14개의 집합을 만들 수 있는 집합을 쿠라토프스키 14 집합(Kuratowski 14-set) 또는 간단히 14 집합(14-set)이라고 한다.
2012년 Mark Bowron은 Mathematics Magazine에 다음 문제를 제시하였다.[3]
위상공간 의 부분집합 에 폐포와 여집합을 어떤 순서로 반복적으로 적용해 서로 다른 집합 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인 위상공간에서 찾을 수 있다. 집합 에 다음 집합
를 기저로 하는 위상을 부여하자. 그러면 는 이고,
집합 |
결과 |
집합 |
결과
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
이므로 쿠라토프스키 14 집합이다.[4] 그러나 인 경우는 존재하지 않는다.[5][6]
변형 문제
문제를 일반화하여 한 집합에 폐포, 내부, 여집합, 합집합, 교집합 중 일부를 취해 만들 수 있는 서로 다른 집합의 개수를 물을 수도 있을 것이다.
일반적으로, 한 집합 의 모든 자기사상의 집합에 합성함수 연산을 부여하면 모노이드가 된다. 이 모노이드를 라 하자. 그러면 이다.
정의 12. 위상공간 에 대해 를 다음과 같이 정의하자.
다음 표는 한 집합에 연산을 취해 얻을 수 있는 서로 다른 집합의 최댓값을 정리한 것이다.[7]
연산 |
|
|
|
|
|
1 |
1 |
1 |
1
|
|
2 |
2 |
2 |
2
|
|
2 |
2 |
2 |
2
|
|
2 |
4 |
4 |
4
|
|
7 |
13 |
13 |
35
|
|
14 |
∞ |
∞ |
∞
|
쿠라토프스키 모노이드
각주
외부 링크