(집합론) 집합족과 곱집합

※수식이 깨질 경우 새로고침해주세요.※

 

1. 집합족, 첨수족

 집합족은 집합을 원소로 하여 구성된 집합입니다. 주로 $\mathcal F$로 나타냅니다. 일례로, $\mathcal F=\{\{1,2\},\{3\},\{4,5\},\{6\}\}$는 모든 원소가 집합이므로 집합족입니다. 멱집합(어떤 집합의 모든 부분 집합을 원소로 가지는 집합; 중학교 과정이라 다들 웬만하면 아실테지만 그래도 혹시모르니 적어둡니다. . .)은 집합족의 대표적인 예시입니다.  

 

 첨수족은 첨수(번호)가 부여된 대상들로 이루어진 집합입니다. 가령 $\{a_{1},a_{2},a_{3}\}$같은 것입니다. 첨수족은 집합족을 표현하는 또다른 방법이 될 수 있습니다. 위의 집합족 $\mathcal F=\{\{1,2\},\{3\},\{4,5\},\{6\}\}$을 첨수족으로 표현하면(이를 첨수화한다고 합니다.) 다음과 같습니다.

 

첨수집합 $I=\{1,2,3,4\}$에 대해

$$\begin{align} A_{1} &=\{1,2\} \\ A_{2} &=\{3\} \\ A_{3} &=\{4,5\} \\ A_{4} &=\{6\} \\ \end{align}$$

라고 하면 $~\mathcal F=\{A_{i}|i\in I\}=\{A_{1},A_{2},A_{3},A_{4}\}$ 을 얻습니다. 이렇게 만들어진 $\mathcal F=\{A_{i}|i\in I\}$ 가 첨수화된 집합족입니다. 보시면 아시겠지만, 첨수족은 첨수집합을 정의역으로 하는 함수와 수학적으로 동등합니다. 

 

2. 집합족의 연산

• 집합족의 합집합과 교집합은 다음과 같이 정의합니다. $$ \bigcup \mathcal F =\bigcup_{i\in I} A_{i} = \bigcup_{A\in\mathcal F} A = \{x|\exists A\in\mathcal F,~x\in A\} $$ $$ \bigcap \mathcal F = \bigcap_{i\in I} A_{i} =  \bigcap_{A\in\mathcal F} A = \{x|\forall A\in\mathcal F,~x\in A\} $$
• (이 내용은 (집합론) 공집합을 참고하시기 바랍니다.) 만약 $A_{i}\subset U$에 대해, $I=\varnothing$ 이라면 $$ (1)~~~~~\bigcup_{i\in I} A_{i}= \varnothing $$ $$ (2)~~~~~\bigcap_{i\in I} A_{i}=U $$

(2) 증명 $$ \begin{align} U\subseteq \bigcap_{i\in I}A_{i} & \equiv \forall x\in U,~x\in\bigcap_{i\in I} A_{i} \\ & \equiv \forall i\in I,~x\in A_{i}\\ & \equiv i\in I \to x\in A_{i}\\ \end{align}$$ 이때 $I=\varnothing$이므로 $i\in I$는 거짓, 가정이 거짓인 조건문은 항상 참이므로 $i\in I \to x\in A_{i}$ 또한 참. 따라서 이와 동치인 $\displaystyle U\subseteq \bigcap_{i\in I}A_{i}$ 또한 참.

 

$A_{i}\subset U$라 하였으므로 자명하게 $\displaystyle\bigcap_{i\in I}A_{i}\subseteq U$. $~~~\displaystyle\therefore \bigcap_{i\in I}A_{i} = U$

 

(1)의 내용은 직관적이므로 증명은 생략.

• 드모르간 법칙 $$ (3)~~~~~(\bigcup_{A\in \mathcal F} A)^{c}= \bigcap_{A\in\mathcal F} A^{c} $$ $$ (4)~~~~~(\bigcap_{A\in \mathcal F} A)^{c}= \bigcap_{A\in\mathcal F} A^{c} $$

(3) 증명 $$ \begin{align} x\in (\bigcup_{A\in\mathcal F}A)^{c} &\equiv \lnot(x\in \bigcup_{A\in\mathcal F} A)\\ & \equiv \lnot(\exists i\in I,~x\in A_{i})\\ & \equiv \forall i\in I,~x\notin A_{i}\\ & \equiv \forall i\in I,~x\in A_{i}^{c}\\ & \equiv x\in \bigcap_{A\in\mathcal F} A^{c}\\ \end{align}$$ 

(4) 증명은 생략.

 

• 분배법칙 $$ (5)~~~~~A\cap \bigcup_{B\in\mathcal F} B = \bigcup_{B\in\mathcal F} (A\cap B) $$ $$ (6)~~~~~A\cup \bigcap_{B\in\mathcal F} B = \bigcap_{B\in\mathcal F} (A\cup B) $$

(5) 증명 $$ \begin{align} x\in A\cap\bigcup_{B\in\mathcal F} B & \equiv x\in A \wedge x\in\bigcup_{B\in\mathcal F} B\\ & \equiv x\in A \wedge \exists B\in\mathcal F,~x\in B\\ & \equiv \exists B\in\mathcal F,~ x\in A \wedge x\in B\\ & \equiv \exists B\in\mathcal F,~x\in(A\cup B)\\ & \equiv x\in \bigcup_{B\in\mathcal F} (A\cap B)\\ \end{align} $$

(6)증명은 생략.

 

3. 곱집합

 곱집합은 각 집합의 각 집합의 원소를 각 성분으로 하는튜플의 집합입니다. 데카르트 곱, 카테시안 곱이라고도 합니다. 여기서 튜플이란, (엄밀한 설명은 아니지만) 순서쌍의 확장된 버전이라고 생각하시면 됩니다. 예를 들어 (2,3),(3,5,2,1),(7,3,3)같은 것들입니다. 

 

 두 집합 $A,B$의 곱집합 $A\times B$는 $\{(x,y)|x\in A \wedge y\in B\}$입니다. 예를 들어 $A=\{1,2\}$,$~B=\{3,4\}$라 하면 두 집합의 곱집합$A\times B$은 $\{(1,3),(1,4),(2,3),(2,4)\}$이며 $A\times A$는 $\{(1,1),(1,2),(2,1),(2,2)\}$입니다. 참고로 $A\times A$처럼 자기자신에 대한 곱집합의 경우 $A^2$라 나타내기도 합니다. 

 

4. 곱집합의 연산

• $A\times \varnothing = \varnothing \times A = \varnothing$
• 분배법칙 $$\begin{align} &(1)~~~~~A\times (B\cap C)=(A\times B)\cap (A\times C) \\ & (2)~~~~~A\times (B\cup C)=(A\times B)\cup (A\times C) \\ & (3)~~~~~A\times (B-C)=(A\times B)-(A\times C) \\ \end{align} $$

(1) 증명 $$ \begin{align} & (x,y)\in A\times (B\cap C) \\ & \equiv x\in A \wedge y\in (B\cap C)\\ & \equiv x\in A \wedge y\in B \wedge y\in C\\ & \equiv x\in A \wedge y\in B \wedge x\in A \wedge y\in C \\ & \equiv (x,y)\in (A\times B) \wedge (x,y)\in (A\times C) \\ & \equiv (x,y)\in (A\times B)\cap(A\times C) \\ \end{align} $$

증명에서 $x\in A$가 갑자기 복사되는 것에 의문을 느끼시는 분들도 계실텐데요. (4번째 줄) 곰곰히 생각해 보면, 사실 당연한 논리임을 알 수 있습니다. 같은 말을 반복한다고 해서 그 의미가 달라지지는 않죠. '사과가 1개 있다'를 아무리 많이 말하더라도 사과가 2개 있다는 의미는 될 수 없습니다. (사과가 1개 있고 사과가 1개 있다, 사과가 1개 있거나 사과가 1개 있다.....)

(2) 증명은 생략

 

(3) 증명 $$\begin{align} & (x,y)\in A\times (B-C) \\ &\equiv x\in A \wedge y\in (B-C) \\ & \equiv x\in A \wedge y\in B \wedge y\notin C \\ & \equiv x\in A \wedge y\in B \wedge x\in A \wedge y\notin C \\ & \equiv (x,y)\in (A\times B) \wedge (x,y)\notin (A\times C) \\ & \equiv (x,y)\in(A\times B)-(A\times C) \\ \end{align} $$

 

(보충 설명) 분량상 따로 뺐습니다. 4번째 줄과 5번째 줄이 동치임이 단번에 이해되지 않을실 것 같아 설명드립니다. $$ \begin{align} & (x,y)\in (A\times B) \wedge (x,y)\notin (A\times C) \\ & \equiv (x\in A \wedge y\in B) \wedge ((x\notin A \wedge y\in C) \vee (x\notin A \wedge y\notin C) \vee (x\in A \wedge y\notin C)) \\ & \equiv c \vee c \vee ((x\in A \wedge y\in B) \wedge (x\in A \wedge y\notin C))~~\textbf{(c는 모순명제)} \\ & \equiv x\in A \wedge y\in B \wedge x\in A \wedge y\notin C \\ \end{align} $$

 

5. 집합족과 곱집합

 임의의 집합족 $\mathcal F$가 첨수집합 $I$에 의하여 첨수화 된 첨수족 $\{A_{i}|i\in I\}$의 곱집합 $\displaystyle\prod_{i\in I} A_{i}$는 다음과 같습니다. $$\prod_{i\in I} A_{i} = \{(a_{i})_{i\in I}|\forall i\in I,~a_{i}\in A_{i}\}$$

예를 들어 집합족 $\mathcal F=\{\{a,b\},\{c,d\}\}$가 첨수집합 $I=\{1,2\}$에 의해 첨수화된 첨수족 $\{A_{1},A_{2}\}$에 대해 $\displaystyle\prod_{i\in I} A_{i}$는 $\{(a_{i})_{i\in I}|\forall i\in I,~a_{i}\in A_{i}\}=\{(a_{1},a_{2})|a_{1}\in A_{1},~a_{2}\in A_{2}\}=\{(a,c),(a,d),(b,c),(b,d)\}=A_{1}\times A_{2}$ 입니다.