서로소 집합

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

서로소 집합은 두 집합의 교집합이 공집합일 때의 관계를 의미하며, 집합론에서 중요한 개념이다. 집합 A와 B가 서로소일 조건은 A ∩ B = ∅이다. 집합족의 경우, 임의의 두 집합이 서로소이거나 같으면 서로소 집합족이라고 한다. 두 집합의 교집합이 특정 기수보다 작으면 거의 서로소 집합이라고 부르기도 한다. 서로소 집합은 분할, 분리합집합 등의 개념과 관련 있으며, 컴퓨터 과학에서 서로소 집합 데이터 구조 및 분할 세분화 등의 응용 분야가 있다. 위상수학에서는 폐포 또는 근방이 서로소인 경우를 포함하여 서로소보다 더 엄격한 분리 집합의 개념을 사용한다.

서로소 집합

📚 더 읽어볼만한 페이지

집합족 - 가측 공간
가측 공간은 집합과 그의 멱집합의 부분 시그마 대수로 이루어진 순서쌍으로, 시그마 대수는 여집합과 가산 합집합에 대해 닫혀 있는 성질을 가지며, 가측 공간과 가측 함수는 구체적 범주를 이룬다.
집합족 - 집합의 분할
집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것이며, 동치 관계와 밀접하게 관련되어 있고, 벨 수로 표현되며, 플레잉 카드를 나누는 것과 같은 예시가 있다.
집합론의 기본 개념 - 치역
치역은 함수에서 정의역의 모든 원소에 대한 함숫값들의 집합으로, 공역의 부분집합이며, 함수의 상을 의미하거나 공역 전체를 의미하기도 한다.
집합론의 기본 개념 - 항등 함수
항등 함수는 집합 X의 각 원소를 자기 자신에게 대응시키는 함수로서, 정의역과 공역이 같은 집합 X에서 단사 함수이자 전사 함수이며, 함수 합성에서 항등원의 역할을 수행하는 중요한 개념이다.

1. 개요
2. 정의
- 2.1. 일반화
3. 성질
4. 예
5. 관련 개념
6. 컴퓨터 과학 응용

2. 정의

두 집합 $A,B$ 가 $A\cap B=\varnothing$ 을 만족시키면, 서로소 집합이라고 한다. 집합족 $\mathcal A$ 가 임의의 $A,B\in\mathcal A$ 에 대하여 $A=B$ 이거나 $A\cap B=\varnothing$ 이면, 서로소 집합족(disjoint family of sets^영어)이라고 한다.

기수 $\kappa$ 에 대하여, 두 집합 $A,B$ 가 $|A\cap B|<\kappa$ 를 만족시키면, $\kappa$ -거의 서로소 집합( $\kappa$ -almost disjoint sets^영어)이라고 한다. 비슷하게 $\kappa$ -거의 서로소 집합족( $\kappa$ -almost disjoint family of sets^영어)을 정의할 수 있다. 여기서 $\kappa=1$ 을 취하면 서로소 집합 및 서로소 집합족의 개념을 얻는다.

2.1. 일반화

서로소 집합의 정의는 집합족 및 집합의 인덱스족으로 확장될 수 있다. 집합족 $\mathcal{F}$ 가 쌍별 서로소라고 불릴 때 두 가지 정의가 가능하다. 첫 번째 정의에 따르면, 집합족의 각 두 집합이 동일하거나 서로소인 경우 서로소이다. 이 정의는 동일한 집합의 반복된 복사본을 허용한다. 두 번째 정의에 따르면, 집합족의 각 두 집합은 서로소여야 하며, 반복된 복사본은 허용되지 않는다. 예를 들어, 집합족 { {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, ... }는 두 정의 모두에 따라 서로소이다. 그러나 10개의 멤버를 가진 집합족 $(\{n + 2k \mid k\in\mathbb{Z}\})_{n \in \{0, 1, \ldots, 9\}}$ 는 두 개의 서로소 집합 각각에 대해 다섯 번의 반복이 있으므로 첫 번째 정의에 따라 쌍별 서로소이지만 두 번째 정의에 따라 그렇지 않다.

두 집합의 교집합이 어떤 의미에서 작으면 준 서로소 집합이라고 한다. 예를 들어, 교집합이 유한 집합인 두 개의 무한 집합은 거의 서로소라고 할 수 있다.

3. 성질

* 모든 집합은 공집합과 서로소이다.
* 자기 자신과 서로소일 필요충분조건은 공집합이다.
* 서로소 집합족이 둘 이상의 집합으로 이루어졌다면, 그 교집합은 공집합이다.
* 공집합은 서로소 집합족이지만, 그 교모임은 모든 집합을 포함하는 고유 모임이다.
* 하나의 집합으로 이루어진 집합족은 서로소 집합족이지만, 그 교집합은 공집합이 아닐 수 있다.
* 교집합이 공집합인 집합족은 서로소 집합족이 아닐 수 있다. 예를 들어, 집합족 의 교집합은 공집합이지만, 이는 서로소 집합족이 아니다.

4. 예

--
--
--

5. 관련 개념

분할은 합집합이 전체 집합이 되는 서로소 집합들의 모임이다. 모든 분할은 하나의 동치 관계와 대응한다.

분리합집합은 서로소 집합들의 합집합이거나, 서로소가 아닌 경우 서로소가 되게끔 변형한 뒤 합집합을 취하는 것을 의미한다.

위상수학에서 서로 분리된 집합은 서로소보다 더 엄격한 조건을 가진다. 예를 들어, 서로소인 폐포를 가지거나 서로소인 근방을 가진 두 집합을 서로 분리된 집합이라고 할 수 있다.

거리공간에서 양수로 분리된 집합은 0이 아닌 거리로 분리된 두 집합을 뜻한다.

헬리 족은 교집합이 공집합인 최소 부분집합족은 모두 서로소인 집합족이다.

6. 컴퓨터 과학 응용

서로소 집합 자료 구조와 분할 세분화는 컴퓨터 과학에서 집합의 분할을 효율적으로 유지하기 위한 기술로, 각각 합집합 및 세분화 연산을 지원한다.