합집합과 교집합

Family of sets

Index set $I$와, 집합들의 집합 $\mathcal{S}$가 주어졌다 하자. 그럼 $I$에서 $\mathcal{S}$로의 함수 $f=(F,I,\mathcal{S})$는 각각의 $i\in I$마다 $\mathcal{S}$의 원소, 즉 집합을 대응시킨다. 기존에는 이를 $(f_i)_{i\in I}$와 같이 쓰기로 하였으나, 집합을 대문자로 적는 관례를 유지하기 위해 이를 $(F_i)_{i\in I}$로 적기로 한다.

Family $(A_i)_{i\in I}$의 모든 집합들이 어떤 집합 $A$의 부분집합이라 하자. 그럼 이 함수의 target $\mathcal{S}$를 $\mathcal{P}(A)$로 둘 수 있다. 이렇게 집합 $A_i$들을 $A$의 부분집합으로 보고 싶을 때는 $(A_i)_{i\in I}$를 집합 $A$의 부분집합들의 family와 같이 표현한다.

합집합과 교집합

§ZFC 공리계에서 우리는 합집합이 존재한다는 것을 공리로 받아들였다. 이 공리를 도입했을 때 사용한 표기법보다는 다음의 표기법이 좀 더 자주 쓰인다.

정의 1 $(A_i)_{i\in I}$가 집합들의 family라 하자. 그럼 적어도 하나의 $A_i$에 속해있는 $x$들을 모두 모아둔 집합을 이 family의 합집합_union이라 하고, 이를 $\bigcup_{i\in I}A_i$로 적는다.

즉 합집합은 논리식

\[\exists i(i\in I\wedge x\in A_i)\]

를 만족하는 $x$들의 집합이다. 따라서 $I=\emptyset$이라면 $\bigcup_{i\in I} A_i=\emptyset$이다. 어렵지 않게 합집합은 $(A_i)_{i\in I}$의 target $\mathcal{S}$에 의존하지 않는 것을 확인할 수 있다.

정의 2 $(A_i)_{i\in I}$가 집합들의 family이고, $I$가 공집합이 아니라 하자. 그럼 모든 $A_i$에 속해있는 $x$들의 집합을 이 family의 교집합_intersection이라 하고 $\bigcap_{i\in I}A_i$로 적는다.

교집합은 논리식

\[\forall i(i\in I\implies x\in A_i)\]

를 만족하는 $x$들의 모임이다. 만일 $I=\emptyset$이라면 $i\in I$가 거짓이 되어 전체 문장이 $x$에 관계없이 참이 되고 $\bigcap_{i\in\emptyset} A_i$는 전체집합이 되어야 하므로 모순이다. (§ZFC 공리계, ⁋예시 4) $(A_i)_{i\in I}$의 target $\mathcal{S}$를 잘 정해준다면 이러한 모순을 피해 교집합을 정의할 수 있다.

정의 3 집합들의 family $(A_i)_{i\in I}$가 집합 $A$의 부분집합들의 family라 하자. 그럼 $A$의 원소이면서 동시에 모든 $A_i$에 속해있는 $x$들의 집합을 이 family의 교집합이라 부르며, $\bigcap_{i\in I}A_i$로 적는다.

이번에는 만일 $I=\emptyset$이더라도 조건이

\[(x\in A)\wedge (\forall i(i\in I\implies x\in A_i))\]

이 되므로 $\bigcap_{i\in I} A_i=A$이다. 앞으로 모든 명제에서, 집합들의 family의 교집합을 택할 일이 있을 경우는 $I$가 공집합이 아니거나 주어진 family가 어떠한 집합의 부분집합들의 family임을 가정한다.

명제 4 집합들의 family $(A_i)_{i\in I}$와 전사함수 $f:K\rightarrow I$를 생각하자. 그럼 다음의 두 식

\[\bigcup_{k\in K}A_{f(k)}=\bigcup_{i\in I}A_i,\qquad \bigcap_{k\in K}A_{f(k)}=\bigcap_{i\in I}A_i\]

이 성립한다.

증명

우선 $x\in\bigcup_{i\in I} A_i$라 하자. 즉 어떤 $i_0\in I$에 대하여 $x\in A_{i_0}$이다. 그런데, $f$는 전사함수이므로 어떤 $k_0\in K$가 존재하여 $i_0=f(k_0)$이고, 따라서 $x\in A_{f(k_0)}$이므로 $x\in\bigcup_{k\in K}A_{f(k)}$이다.

반대로, 만일 $x\in\bigcup_{k\in K}A_{f(k)}$가 성립한다면, 어떤 $k_0\in K$에 대하여 $x\in A_{f(k_0)}$이다. 그런데 $f(k_0)\in I$이므로, $A_{f(k_0)}$는 $(A_i)_{i\in I}$를 구성하는 집합 중 하나이고 따라서 $x\in \bigcup_{i\in I} A_{i}$이다.

이제 두 번째 식을 보여야 한다. 우선 $x\in\bigcap_{i\in I}A_i$라 하자. 그럼 모든 $i\in I$에 대하여 $x\in A_i$이다. 임의의 $k_0\in K$에 대하여 $f(k_0)\in I$이므로, 모든 $k\in K$에 대하여 $x\in A_{f(k)}$이고 따라서 $x\in \bigcap_{k\in K}A_{f(k)}$이다.
반대로 만일 모든 $k\in K$에 대하여 $x\in A_{f(k)}$라면, $f$는 전사이므로 모든 $i\in I$에 대해 $x\in A_{f(k)}$이기도 하다.

특별히 $(A_k)_{k\in K}$가 임의의 $k,k’\in K$에 대하여 $A_k=A_{k’}$를 만족한다고 하자. 임의의 $k_0\in K$를 하나 택하여 $I=\{k_0\}$라 하고, 전사함수 $f:K\rightarrow I$에 위의 명제를 적용하면, 모든 $k$에 대해 $A_k=A_{k_0}=A_{f(k)}$이므로

\[\bigcup_{k\in K} A_k=\bigcup_{k\in K} A_{f(k)}=\bigcup_{i\in I}A_i=A_{k_0},\qquad \bigcap_{k\in K}A_k\bigcap_{k\in K}A_{f(k)}=\bigcap_{i\in I}A_i=A_{k_0}\]

가 성립한다.

이제 합집합과 교집합의 성질들을 조금 더 살펴보자. 만일 같은 index를 갖는 두 family $(A_i)_{i\in I}$와 $(B_i)_{i\in I}$가 주어졌고, $B_i\subseteq A_i$가 모든 $i\in I$에 대해 성립한다면

\[\bigcup_{i\in I} B_i\subset\bigcup_{i\in I} A_i,\qquad \bigcap_{i\in I} B_i\subset\bigcap_{i\in I} A_i\]

임은 자명하다. 또, 주어진 family $(A_i)_{i\in I}$와 $I$의 부분집합 $J$에 대하여,

\[\bigcup_{j\in J}A_j\subset\bigcup_{i\in I} A_i,\qquad\bigcap_{j\in J}A_j\supset\bigcap_{i\in I} A_i\]

임도 거의 자명하다.

결합법칙

집합의 연산들은 결합법칙을 만족한다.

명제 5 $(A_i)_{i\in I}$가 집합들의 family고, index set $I$가 family $(J_k)_{k\in K}$들의 합집합이라 하자. 그럼

\[\bigcup_{i\in I} A_i=\bigcup_{k\in K}\left(\bigcup_{j\in J_k} A_j\right),\quad \bigcap_{i\in I}A_i=\bigcap_{k\in K}\left(\bigcap_{j\in J_k} A_j\right)\]

가 성립한다.

증명

우선 합집합에 관한 식부터 보이자. 만일 $x\in \bigcup_{i\in I}A_i$라면, 어떠한 $i_0\in I$에 대하여 $x\in A_{i_0}$이다. 이제 $I=\bigcup_{k\in K} J_k$이므로, 어떤 $k_0$가 존재하여 $i_0\in J_{k_0}$이다. 그럼

\[A_{i_0}=\bigcup_{i\in \{i_0\}}A_i\subset\bigcup_{j\in J_{k_0}} A_j=\bigcup_{k\in\left\{k_0\right\}}\left(\bigcup_{i\in J_k} A_i\right)\subseteq \bigcup_{k\in K}\left(\bigcup_{j\in J_k} A_j\right)\]

이므로 $x\in A_{i_0}\subseteq \bigcup_{k\in K}\left(\bigcup_{j\in J_k} A_j\right)$이다.

반대로 만일 $x\in \bigcup_{k\in K}\left(\bigcup_{j\in J_k} A_j\right)$이라면, 어떠한 $k_0\in K$에 대하여 $x\in \bigcup_{j\in J_{k_0}}A_j$이고, 따라서 다시 어떤 $i_0\in J_{k_0}$에 대하여 $x\in A_{i_0}$이다. 이제 $i_0\in I$이므로 $x\in\bigcup_{i\in I} A_i$이다.

이와 비슷하게 두 번째 식도 보일 수 있다. 만일 $x\in\bigcap_{i\in I} A_i$라면, 모든 $i\in I$에 대하여 $x\in A_i$이다. 임의의 $k\in K$에 대하여 $J_{k}\subseteq I$이므로, 모든 $i\in I$에 대하여 위의 식이 성립한다는 말은 모든 $j\in J_{k}$에 대하여 $x\in A_j$가 성립한다는 말이기도 하다. 임의로 선택된 $k$에 대하여 이것이 성립하므로, 이는 정확히 $x\in\bigcap_{k\in K}\left(\bigcap_{j\in J_{k}}A_j\right)$를 의미한다.

합집합, 교집합의 상

다음과 같이 합집합이나 교집합의 image도 생각해 볼 수 있다.

명제 6 $(A_i)_{i\in I}$가 집합 $A$의 부분집합의 family고 $(R,A,B)$가 이항관계라 하자. 그럼

\[R\left(\bigcup_{i\in I} A_i\right)=\bigcup_{i\in I}R(A_i),\quad R\left(\bigcap_{i\in I} A_i\right)\subset\bigcap_{i\in I}R(A_i)\]

증명

우선 첫 번째 식을 보이자. 만일 $y\in R\left(\bigcup_{i\in I}A_i\right)$라면, 적당한 $x\in \bigcup_{i\in I}A_i$가 존재하여 $(x,y)\in R$이다. 이제 $x\in A_j$라 하면 $y\in R(A_j)$이므로 $y\in\bigcup_{i\in I}R\left(A_i\right)$가 성립한다. 반대로 만일 $y\in \bigcup_{i\in I}R\left(A_i\right)$라면 어떤 $j$에 대하여 $y\in R\left(A_j\right)$이므로, 적당한 $x\in A_j$가 존재하여 $(x,y)\in R$이다. 따라서 $y\in R\left(\bigcup_{i\in I} A_i\right)$가 성립한다.

두 번째 식은 한쪽 방향만 보이면 충분하다. $y\in R\left(\bigcap_{i\in I}A_i\right)$라 하자. 그럼 어떤 $x\in\bigcap_{i\in I}A_i$가 존재하여 $(x,y)\in R$이다. $x$는 모든 $A_i$에 속하므로, 우리는 $(x,y)\in R(A_i)$가 모든 $A_i$에 대해 성립하는 것을 안다. 즉 $y\in \bigcap_{i\in I}R\left(A_i\right)$이다.

위의 명제의 두 번째 식의 반대쪽 포함관계는 일반적으로 성립하지 않지만, $R$이 함수의 역관계라면 등호가 성립한다.

명제 7 $f:A\rightarrow B$가 함수라 하고 $(B_i)_{i\in I}$가 $B$의 부분집합들의 family라 하자. 그럼

\[f^{-1}\left(\bigcap_{i\in I} B_i\right)=\bigcap_{i\in I} f^{-1}(B_i)\]

가 성립한다.

증명

한쪽 포함관계는 더 일반적인 경우에서 증명하였으므로, 반대쪽 포함관계만 증명하면 충분하다.

임의의 $x\in\bigcap_{i\in I} f^{-1}(B_i)$가 주어졌다 하자. 그럼 모든 $i$에 대하여 $x\in f^{-1}(B_i)$이다. 즉, 모든 $i$에 대해 $(x,y_i)\in F$이도록 하는 $y_i\in B_i$가 존재한다. 그런데 $f$가 함수이므로 그러한 $y_i$는 유일하다. 이 공통된 값을 $y$라 하면 모든 $i\in I$에 대해 $y\in B_i$이므로 $y\in\bigcap_{i\in I} B_i$이고, 따라서 $f(x)=y$에서 $x\in f^{-1}\left(\bigcap_{i\in I} B_i\right)$이다.

드 모르간 법칙

명제 8 (De Morgan’s law) 집합 $A$의 부분집합들의 Family $(A_i)_{i\in I}$에 대하여,

\[A\setminus \left(\bigcup_{i\in I}A_i\right)=\bigcap_{i\in I}(A\setminus A_i),\quad A\setminus\left(\bigcap_{i\in I} A_i\right)=\bigcup_{i\in I} (A\setminus A_i)\]

가 성립한다.

증명

첫 번째 식을 보이기 위해 우선 $x\in A\setminus\left(\bigcup_{i\in I} A_i\right)$라 하자. 그럼 $x\in A$이고 $x\not\in\left(\bigcup_{i\in I} A_i\right)$이다. 따라서 모든 $i$에 대하여 $x\not\in A_i$이므로, $x\in (A\setminus A_i)$가 모든 $i$에 대하여 성립한다. 즉 $x\in\bigcap_{i\in I}(A\setminus A_i)$이다.
반대로 만일 $x\in\bigcap_{i\in I} (A\setminus A_i)$라면, 임의의 $i\in I$에 대하여 $x\in A\setminus A_i$이고, 따라서 모든 $i\in I$에 대하여 $x\not\in A_i$이다. 이제 $x\not\in\bigcup_{i\in I} A_i$이므로 $x\in A\setminus\bigcup_{i\in I} A_i$이다.

두 번째 식은 등식 $A\setminus(A\setminus X)=X$가 모든 $X\subseteq A$에 대해 성립하므로 첫 번째 식으로부터 자명.

---

참고문헌

[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

---