[집합론] 4. 집합의 개념(2: 합집합, 교집합, 여집합)

[집합론] 4. 집합의 개념(2: 합집합, 교집합, 여집합)

임의의 두 집합 \(A,\,B\)에 대하여 

(a) 적어도 \(A,\,B\)각각에 속하는 원소들의 집합을 \(A\)와 \(B\)의 합집합이라 하고 \(A\cup B\)로 나타낸다. 즉 \(x\in A\wedge x\in B\,\Leftrightarrow\,x\in A\cup B\)

(b) \(A,\,B\)각각에 동시에 속하는 원소의 집합을 \(A\)와 \(B\)의 교집합이라 하고 \(A\cap B\)로 나타낸다. 즉 \(A\cap B=\{x\,|\,x\in A\wedge x\in B\}\) 또는 \(A\cap B=\{x\in A\,|\,x\in B\}\) 

특히 \(A\cap B=\phi\)일 때 \(A\)와 \(B\)는 서로소(disjoint)라고 한다.

예를들어 \(A=\{1,\,2,\,3,\,4\}\), \(B=\{3,\,4,\,5\}\)일 때 \(A\cup B=\{1,\,2,\,3,\,4,\,5\}\), \(A\cap B=\{3,\,4\}\)이다. 

집합 \(X\)의 부분집합 \(A,\,B,\,C\)에 대하여 다음이 성립한다. 

(a) 항등법칙(unities): \(A\cup\phi=A\), \(A\cap X=A\) 

(b) 멱등법칙(idempotency laws): \(A\cup A=A\), \(A\cap A=A\)

(c) 교환법칙(commutative laws): \(A\cup B=B\cup A\), \(A\cap B=B\cap A\)

(d) 결합법칙(associative laws): \(A\cup(B\cup C)=(A\cup B)\cup C\), \(A\cap(B\cap C)=(A\cap B)\cap C\)

(e) 분배법칙(distributive laws): \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\), \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\) 

증명: 

(d)$$\begin{align*}x\in A\cup(B\cup C)&\Leftrightarrow x\in A\vee(x\in B\cup C)\\&\Leftrightarrow x\in A\vee(x\in B\vee x\in C)\\&\Leftrightarrow(x\in A\vee x\in B)\vee x\in C\\&\Leftrightarrow x\in A\cup B\vee x\in C\\&\Leftrightarrow x\in(A\cup B)\cup C\end{align*}$$그러므로 \(x\in A\cup(B\cup C)\Leftrightarrow\,x\in(A\cup B)\cup C\)이고 따라서 \(A\cup(B\cup C)=(A\cup B)\cup C\)이다.

(e)$$\begin{align*}x\in A\cap(B\cup C)&\Leftrightarrow x\in A\wedge x\in B\cup C\\&\Leftrightarrow x\in A\wedge(x\in B\vee x\in C)\\&\Leftrightarrow(x\in A\wedge x\in B)\vee(x\in A\wedge x\in C)\\&\Leftrightarrow x\in A\cap B\vee x\in A\cap C\\&\Leftrightarrow x\in(A\cap B)\cup(A\cap C)\end{align*}$$그러므로 \(\Leftrightarrow\)에 대한 추이율에 따라 \(x\in A\cap(B\cup C)\Leftrightarrow x\in(A\cap B)\cup(A\cap C)\)이고 따라서 \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\)이다.

*하나의 동치 \(p\Leftrightarrow\,q\)에 대하여 \(q\)를 \(p\)이기 위한 필요조건(necessary condition), \(p\)를 \(q\)이기 위한 충분조건(sufficient condition)이라고 한다.

집합 \(A,\,B\)에 대하여 \(A\)의 원소이나 \(B\)의 원소가 아닌 원소들의 집합을 \(A\)에 대한 차집합(relative complement)이라 하고 \(A-B\)로 나타낸다. 즉 \(A-B=\{x\in A\,|\,x\notin B\}\)이다.

예를들어 \(A=\{a,\,b,\,c,\,d\}\), \(B=\{c,\,d,\,e,\,f\}\)일 때, \(A-B=\{a,\,b\}\)이다.(참고: \(A-(A\cap B)=\{a,\,b\}\))

전체집합 \(U\)에 대한 \(A\)의 차집합 \(U-A\)를 \(A\)의 여집합(complement)이라 하고 \(A^{c}\)로 나타낸다.  

예를들어 \(U=\mathbb{R}\)에 대하여 \(\mathbb{Q}^{c}=\mathbb{R}-\mathbb{Q}=\{x\,|\,x\,\text{is irrational number}\}\)

\(A-B=A\cap B^{c}\)임을 다음과 같이 보일 수 있다.$$\begin{align*}x\in A\cap B^{c}&\equiv x\in A\wedge x\in U-B\\&\equiv x\in A\wedge(x\in U\wedge x\notin B)\\&\equiv(x\in A\wedge x\in U)\wedge x\notin B\\&\equiv x\in A\cap U\wedge x\notin B\\&\equiv x\in A\wedge x\notin B\\&\equiv x\in A-B\end{align*}$$그러므로 \(x\in A\cap B^{c}\equiv x\in A-B\)이고 \(x\in A-B\equiv x\in A\cap B^{c}\)이므로 따라서 \(A-B=A\cap B^{c}\)이다. 

임의의 집합 \(A,\,B\)에 대하여  

(a) \((A^{c})^{c}=A\) 

(b) \(\phi^{c}=U\), \(U^{c}=\phi\)

(c) \(A\cap A^{c}=\phi\), \(A\cup A^{c}=U\)

(d) \(A\subset B\)일 필요충분조건은 \(B^{c}\subset A^{c}\)     

증명:

(d):$$\begin{align*}A\subset B&\equiv(x\in A\,\Rightarrow\,x\in B)\\&\equiv(x\notin B\,\Rightarrow\,x\notin A)\\&\equiv(x\in B^{c}\,\Rightarrow\,x\in A^{c})\\&\equiv B^{c}\subset A^{c}\end{align*}$$그러므로 \(A\subset B\,\Leftrightarrow\,B^{c}\subset A^{c}\)이다. 

드 모르간의 정리(De Morgan's theorem)

임의의 두 집합 \(A,\,B\)에 대하여  

(a) \((A\cup B)^{c}=A^{c}\cap B^{c}\), (b) \((A\cap B)^{c}=A^{c}\cup B^{c}\)

증명:

(a):$$\begin{align*}x\in(A\cup B)^{c}&\equiv(\sim x\in A\cup B)\\&\equiv\sim(x\in A\cup x\in B)\\&\equiv\sim(x\in A)\wedge\sim(x\in B)\\&\equiv x\in A^{c}\wedge x\in B^{c}\\&\equiv x\in(A^{c}\cap B^{c})\end{align*}$$이므로 \(x\in (A\cup B)^{c}\equiv x\in(A^{c}\cap B^{c})\)이고 따라서 \((A\cup B)^{c}=A^{c}\cap B^{c}\)이다. 

임의의 집합 \(A,\,B,\,C\)에 대해 등식 \(A\cap(B-C)=(A\cap B)-(A\cap C)\)가 성립한다.

증명:$$\begin{align*}(A\cap B)-(A\cap C)&=(A\cap B)\cap(A\cap C)^{c}\\&=(A\cap B)\cap(A^{c}\cup B^{c})\\&(A\cap B\cap A^{c})\cup(A\cap B\cap C^{c})\\&=(A\cap A^{c}\cap B)\cup(A\cap B\cap C^{c})\\&=(\phi\cap B)\cup(A\cap B\cap C^{c})\\&=\phi\cup[A\cap(B\cap C^{c})]\\&=A\cap[(B\cap C^{c})]\\&=A\cap(B-C)\end{align*}$$그러므로 \((A\cap B)-(A\cap C)=A\cap(B-C)\)이고 따라서 \(A\cap(B-C)=(A\cap B)-(A\cap C)\)이다.  

참고자료:

집합론, You-Feng Lin, Shwu-Yeng T. Lin 저, 이흥천 옮김, 경문사