분리합집합

1. 개요

분리합집합은 두 집합의 원소들이 서로 구별되도록 각 원소에 추가적인 정보를 부여하여 합집합을 만드는 방법이다. 두 집합 A와 B의 분리합집합은 A×{0} ∪ B×{1}로 정의되며, 일반적으로 집합족 {Ai}i∈I의 분리합집합은 ⋃i∈I(Ai×{i})로 정의된다. 분리합집합의 원소는 순서쌍 (x, i)로 표현되며, 여기서 i는 원소 x가 어떤 집합 Ai에서 왔는지를 나타내는 꼬리표 역할을 한다. 분리합집합은 집합의 크기, 범주론적 성질 등 다양한 성질을 가지며, 데이터 구조, 전산학 등 여러 분야에 응용된다.

2. 정의

두 집합 $A$와 $B$의 분리 합집합 $A\backslash sqcup\; B$은 각 집합의 원소에 꼬리표를 붙여 만든 새로운 집합들의 합집합으로, 다음과 같이 두 곱집합의 합집합으로 정의된다.

:$A\backslash sqcup\; B=(A\backslash times\backslash \{0\backslash \})\backslash cup(B\backslash times\backslash \{1\backslash \})$

일반적으로, 집합들의 집합 $\backslash \{A\_i\backslash \}\_\{i\backslash in\; I\}$의 분리 합집합 $\backslash bigsqcup\_\{i\backslash in\; I\}A\_i$은 각 원소 $(a,i)$에 꼬리표 $i$를 추가하여 만든 집합이며, 다음과 같다.

:$\backslash bigsqcup\_\{i\backslash in\; I\}A\_i=\backslash bigcup\_\{i\backslash in\; I\}\{(A\_i\backslash times\backslash \{i\backslash \})\}$

각 집합 $A\_i$는 집합 $A\_i^*\; =\; \backslash left\backslash \{(x,i)\; :\; x\; \backslash in\; A\_i\backslash right\backslash \}$와 표준적으로 동형이며, 이 동형 사상을 통해 원래 집합 $A\_i$가 분리합집합에 포함되어 있다고 간주할 수 있다. $i\; \backslash neq\; j$에 대해, 집합 $A\_i^*$와 $A\_j^*$는 $A\_i$와 $A\_j$가 서로소 집합이 아니더라도 서로소이다.

모든 $A\_i$가 어떤 고정된 집합 $A$와 같은 경우, 분리합집합은 $A$와 $I$의 데카르트 곱이 된다.

:$\backslash bigsqcup\_\{i\; \backslash in\; I\}\; A\_i\; =\; A\; \backslash times\; I.$

범주론에서 분리합집합은 집합 범주에서의 코곱이며, 관련된 보편 성질을 만족한다.

2.1. 꼬리표(tag)

분리 합집합의 핵심은 각 원소가 어느 집합에서 왔는지 구별하는 것이다. 이를 위해 각 원소에 꼬리표(tag)를 붙인다. 꼬리표는 보통 정수나 집합의 인덱스를 사용하며, 순서쌍 $(a,\; i)$ 형태로 표현한다. 여기서 $i$는 $a$가 원래 어느 집합에 속했는지를 나타내는 보조 색인 역할을 한다.

예를 들어, 집합 $A\_0\; =\; \backslash \{5,\; 6,\; 7\backslash \}$과 $A\_1\; =\; \backslash \{5,\; 6\backslash \}$이 있을 때, 각 원소에 꼬리표를 붙여 다음과 같이 표현할 수 있다.

* $A\_0^*\; =\; \backslash \{(5,\; 0),\; (6,\; 0),\; (7,\; 0)\backslash \}$
* $A\_1^*\; =\; \backslash \{(5,\; 1),\; (6,\; 1)\backslash \}$

이때, 각 순서쌍의 두 번째 요소는 해당 원소가 원래 속했던 집합의 아래 첨자와 일치한다. 즉, $(5,\; 0)$의 $0$은 $A\_0$의 아래 첨자 $0$과 같다.

이와 같이 꼬리표를 사용하면, 원래 집합들이 서로소 집합이 아니더라도 꼬리표가 붙은 집합들은 서로소 집합이 된다. 예를 들어, $A\_i$와 $A\_j$ ($i\; \backslash ne\; j$)가 서로소가 아니더라도, $A\_i^*$와 $A\_j^*$는 항상 서로소이다.

3. 성질

임의의 집합 $A\_i$는 $\backslash bigsqcup\_\{i\backslash in\; I\}A\_i$로 매장된다. 이는 다음과 같은 함수로 표현된다.

:$\backslash iota\backslash colon\; A\_i\backslash hookrightarrow\backslash bigsqcup\_\{i\backslash in\; I\}A\_i$
:$\backslash iota\backslash colon\; a\backslash mapsto(a,i)$

각 집합 $A\_i$는 다음 집합과 표준적으로 동형이다.

:$A\_i^*\; =\; \backslash left\backslash \{(x,i)\; :\; x\; \backslash in\; A\_i\backslash right\backslash \}$

이 동형 사상을 통해, $A\_i$가 분리합집합에 표준적으로 포함되어 있다고 간주할 수 있다. $i\; \backslash neq\; j$이면, 집합 $A\_i^*$와 $A\_j^*$는 $A\_i$와 $A\_j$가 서로소 집합이 아니더라도 서로소이다.

집합족 $A\_i$가 서로소이면, 즉 $i\; \backslash ne\; j$이면 $A\_i\; \backslash cap\; A\_j\; =\; \backslash empty$를 만족할 때, 자연스러운 동형 $\backslash bigsqcup\_i\; A\_i\; \backslash to\; \backslash bigcup\_i\; A\_i$가 존재한다.

3.1. 집합의 크기(cardinality)

집합들의 분리 합집합의 크기는, 그 집합들의 크기의 합이다. 즉, 다음과 같다.

:$\backslash left|\backslash bigsqcup\_\{i\backslash in\; I\}A\_i\backslash right|=\backslash sum\_\{i\backslash in\; I\}|A\_i|$

일반적으로, 기수 산술은 비상호 합집합의 기수로 주어지며, 고정된 집합 의 로 인덱싱된 반복적인 비상호 합집합 는 와 의 데카르트 곱이다. 특히, 기수(농도)에 대해 이다.

3.2. 범주론적 성질

범주론에서, 분리합집합은 집합의 범주에서의 쌍대곱이다. 따라서 관련된 보편 성질을 만족한다. 즉, \(\iota_k \colon A_k \hookrightarrow \bigsqcup_i A_i\)를 \(\iota_k(x) = (x,k)\)로 정의하면, 임의의 집합 \(X\)와 함수들의 모임 \(\{f_i \colon A_i \to X\}\)에 대해, \(f_i = f \circ \iota_i\)를 만족하는 \(f \colon \bigsqcup_i A_i \to X\)가 유일하게 존재한다. 이는 또한 분리합집합이 데카르트 곱 구성의 범주론적 쌍대임을 의미한다.

4. 예시

두 집합 $A=\backslash \{a,b\backslash \}$, $B=\backslash \{b,c,d\backslash \}$의 분리 합집합은 $A\backslash sqcup\; B=\backslash \{(a,0),(b,0),(b,1),(c,1),(d,1)\backslash \}$이며, 그 크기는 5이다.

집합 $A\_0\; =\; \backslash \{5,\; 6,\; 7\backslash \}$과 $A\_1\; =\; \backslash \{5,\; 6\backslash \}$을 생각해 보자. 집합 요소들을 집합의 기원에 따라 색인할 수 있으며, 관련 집합을 다음과 같이 형성할 수 있다.

:$$
\begin{align}
A^*_0 & = \{(5, 0), (6, 0), (7, 0)\} \\
A^*_1 & = \{(5, 1), (6, 1)\}, \\
\end{align}


여기서 각 쌍의 두 번째 요소는 기원 집합의 아래 첨자와 일치한다 (예를 들어, $(5,\; 0)$의 $0$은 $A\_0$의 아래 첨자와 일치한다). 그 다음 분리 합집합 $A\_0\; \backslash sqcup\; A\_1$은 다음과 같이 계산할 수 있다.

:$A\_0\; \backslash sqcup\; A\_1\; =\; A^*\_0\; \backslash cup\; A^*\_1\; =\; \backslash \{(5,\; 0),\; (6,\; 0),\; (7,\; 0),\; (5,\; 1),\; (6,\; 1)\backslash \}.$

집합 $A\_0\; =\; \backslash \{1,\; 2,\; 3\backslash \}$ 와 $A\_1\; =\; \backslash \{1,\; 2\backslash \}$ 의 분리합집합 $A\_0\; \backslash sqcup\; A\_1$ 또는 $A\_0\; \backslash cup^*\; A\_1$는
:$$
\begin{align}
A^*_0 & = \{(1, 0), (2, 0), (3, 0)\} \\
A^*_1 & = \{(1, 1), (2, 1)\}
\end{align}

를 사용하여
:$$
A_0 \sqcup A_1 = A_0 \cup^* A_1 := A^*_0 \cup A^*_1 = \{(1, 0), (2, 0), (3, 0), (1, 1), (2, 1)\}

와 같이 계산된다.

5. 표기법

분리 합집합은 여러 가지 기호로 표현된다. 예를 들어, 집합족 $\backslash left(A\_i\; :\; i\; \backslash in\; I\backslash right)$의 분리합집합은 $\backslash bigsqcup\_\{i\backslash in\; I\}A\_i$ 또는 $\backslash sum\_\{i\backslash in\; I\}A\_i$로 나타낼 수 있다. 두 집합 A와 B의 분리합집합은 $A+B$로 표기하기도 한다. 이러한 표기법은 분리합집합의 기수가 각 집합의 기수의 합과 같다는 사실을 보여준다.

범주론에서는 분리합집합을 집합 범주에서의 코곱으로 정의하며, 이때 쌍대곱을 나타내는 기호인 $\backslash coprod$를 사용하기도 한다. 이는 분리합집합이 데카르트 곱의 범주론적 쌍대임을 의미한다.

6. 응용

분리합집합은 주어진 원소들을 겹치지 않는 부분 집합으로 나누는 자료구조로, 다음과 같은 다양한 분야에서 응용된다.

* 최소 신장 트리 (Minimum Spanning Tree) 알고리즘: 크루스칼 알고리즘은 분리합집합을 이용하여 그래프에서 최소 신장 트리를 찾는 데 사용된다. 간선들을 가중치 순으로 정렬한 후, 분리합집합을 이용하여 사이클을 형성하지 않는 간선들을 추가하는 방식으로 동작한다.
* 그래프 연결성 판별: 분리합집합을 이용하여 그래프 내의 두 노드가 연결되어 있는지 여부를 효율적으로 판별할 수 있다. 두 노드에 대해 `find` 연산을 수행하여 같은 집합에 속하는지 확인하면 된다.
* 이미지 처리: 이미지 분할(image segmentation) 알고리즘에서 픽셀들을 묶어 영역을 구분하는 데 사용될 수 있다.
* 네트워크 분석: 소셜 네트워크 등에서 서로 연결된 그룹을 찾거나, 네트워크의 연결성을 분석하는 데 활용될 수 있다.