집합(Set)

정의1

소박한 집합론(naive set theory)의 집합 : 

어떤 대상(object)들의 모임을 집합으로 정의한다.

공리적 집합론(axiomatic set theory)의 집합 :

아래 원소 관계 $\in$ 또는 어떤 관계에 대한 일련의 공리(axiom)들을 만족할때 집합이라고 한다.

순수 집합론(pure set theory) :

수학에서 다루는 대상이 모두 집합일때 순수 집합론이라 한다.

집합의 원소(element) : 

어떤 $x$가 집합 $A$에 존재하면 $x$를 $A$의 원소라고 하고 $x$는 $A$에 속한다고 하여 $x \in A$ 또는 $(x \in A) \equiv \mathbf{T}$로 표기한다.

어떤 $x$가 집합 $A$에 존재하지 않으면 $\neg$$ (x \in A) $ $\equiv$ $ x \notin A$라 표기하고 $x$는 $A$에 속하지 않는다고 한다.

집합의 부분집합(subset) :

집합 $A$의 모든 원소 $x \in A$가 $x \in B$로 집합 $B$에 속한다면 $A \subseteq B$ 또는 $B \supseteq A$로 표기하고 

$A$는 $B$의 부분집합이다 또는 $A$는 $B$에 포함된다라고 한다.

$A\subseteq B$이기 위한 필요충분조건은 항상 $(x \in A) $ $\to$ $ (x \in B) \equiv \mathbf{T}$인 것이다.

집합의 진부분집합(prober subset) :

$A \subseteq B$이지만 $x \notin A$ 이고 $x \in B$인 원소 $x$가 적어도 하나 존재하면 $A \subset B$ 또는 $B \supset A$로 표기하고 

$A$는 $B$의 진부분집합이라고 한다.

$A\subset B$이기 위한 필요충분조건은

$(x \in A) \to (x \in B) \equiv \mathbf{T}$이고 $(b \in B) \to (b \in A) \equiv \mathbf{F}$인 $b \in B$가 존재하는 것이다.

 

 

 

정의2

ZF 공리계(Zermelo–Fraenkel set theory) :

집합이 아래 공리들을 만족하는 공리적 집합론을 ZF 공리계라고 정의한다.

다른 공리계임을 명시하지 않으면 집합은 선택공리를 포함한 ZFC 공리를 만족한다고 가정하고

다른 수학이론임을 명시하지 않으면 집합 외에 다른 대상을 다루지 않는 순수 집합론을 가정한다.

또 다루는 명제함수의 범위를 일차논리의 논리식으로 제한한다.

외연 공리(extensionality axiom) 또는 집합의 상등(equality of sets) :

임의의 집합 $A,B$가 동일한 원소를 가져

모든 $x \in A$에 대해 $x \in B$이고 모든 $y \in B$에 대해 $y \in A$이면 $A$와 $B$는 같다고 하고 $A = B$로 표기한다.

$A = B$이기 위한 필요충분조건은 항상 $(x \in A) $ $\to$ $ (x \in B) \equiv \mathbf{T}$이고 $(x \in B) \to (x \in A) \equiv \mathbf{T}$인 것이다.

$A$와 $B$가 같지 않으면 $A \ne B$로 표기한다.

공집합 공리(empty set axiom) :

어떠한 원소도 갖지 않는 집합을 공집합 $\emptyset$으로 정의하고 공집합이 존재한다고 가정한다.

공집합은 모든 집합 $x$에 대해 $(x \notin \emptyset ) \equiv \mathbf{T}$이다.

짝 공리(pairing axiom) :

임의의 $a,b$에 대해 두 원소집합(pair set) $\{ a,b \}$가 존재하여

$s \in \{ a,b \}$이기 위한 필요충분조건은 $s = a$이거나 $s = b$인 것이다.

분류 공리(specification axiom) :

집합 $S$의 원소에 대한 명제함수 $P$가 참이 되는 집합을 $\{ x \in S  : P(x) \equiv \mathbf{T} \}$로 정의할때

$\{ x \in S  : P(x) \equiv \mathbf{T} \}$가 존재하여 

$s \in \{ x \in S :  P(x) $ $\equiv$ $ \mathbf{T} \}$이기 위한 필요충분조건은 $s \in S$이고 $P(s) \equiv \mathbf{T}$인 것이다.

합집합 공리(union axiom) : 

집합 $\mathcal{F}$의 모든 원소의 원소들로 이루어진 $\displaystyle \bigcup \mathcal{F} = \{ x : \text{ 어떤 } S \in \mathcal{F} \text{ 에 대해 } x \in S \}$인 집합이 존재하여

$\displaystyle x \in \bigcup \mathcal{F}$이기 위한 필요충분조건은 $x \in S$인 $S \in \mathcal{F}$가 존재하는 것이다.

멱집합 공리(power set axiom) : 

임의의 집합 $A$의 모든 부분집합들만 원소로 갖는 집합 $\mathcal{P}(A)$를 $A$의 멱집합으로 정의하고

멱집합 $\mathcal{P}(A)$가 존재하여

$X \in \mathcal{P}(A)$이기 위한 필요충분조건은 $X \subseteq A$인 것이다.

치환 공리(replacement axiom) : 

변수 $x,y$에 대한 명제함수가 $P(x,y)$일때

집합 $A$의 모든 원소 $a \in A$마다 $P(a,y_a) \equiv \mathbf{T}$가 되는 $y_a$가 유일하게 존재하면

집합 $F = \{ y : \text{어떤 } x \in A \text{ 에 대해 } P(x,y) \equiv \mathbf{T} \}$가 존재하여

$z \in F$이기 위한 필요충분조건은 $P(x,z) \equiv \mathbf{T}$인 $x \in A$가 존재하는 것이다.

정칙성 공리(regularity axiom) :

집합 $A$가 공집합이 아니면 $A \cap x = \emptyset$인 $x \in A$가 존재한다.

무한 공리(infinity axiom) :

$\emptyset \in A$이고 모든 $x \in A$에 대해 $(x \cup \{ x \}) \in A$인 집합 $A$를 귀납집합(inductive set)으로 정의하고

어떤 귀납집합 $A$가 존재한다고 가정한다.

 

 

 

정리14(ZF 공리계에서 러셀의 역설[Russell's paradox])

모든 집합 $x$에 대해 $x\in V$인 집합 $V$는 존재하지 않는다.

증명

$V$가 집합이라고 가정하면

분류 공리로 집합 $R = \{ x\in V: x\notin x\}$이 존재하여 $V$의 정의로 $R\in V$인데

$R\in R$이면 $R$의 정의로 $R\notin R$이므로 모순이고

$R\notin R$이면 $R\in V$이므로 $R$의 정의로 $R\in R$이 되어 모순이다.

따라서 모든 집합 $x$에 대해 $x\in V$인 집합 $V$는 존재하지 않는다.

 

 

 

정의6

단일 원소집합(singleton set) :

임의의 $a$에 대해 모든 $s \in \{ a \}$가 $s = a $인 집합 $\{ a\}$를 단일 원소집합으로 정의한다.

유한 교집합(intersection) :

임의의 집합 $A, B$에 대해 집합 $A \cap B = \{ x \in A : (x \in B) \equiv \mathbf{T} \}$를 $A$와 $B$의 교집합으로 정의하고

$x \in A\cap B$이기 위한 필요충분조건은 $(x\in A) $ $\land$ $ (x \in B)$인 것이다.

$A \cap B = \emptyset$이면 $A$와 $B$를 서로소(disjoint)라고 정의한다.

유한 여집합(complement) :

임의의 집합 $A,B$에 대해 집합 $A \setminus B = \{ x \in A : (x \notin B) \equiv \mathbf{T} \}$를 $A$에 대한 $B$의 여집합으로 정의하고

$x \in A \setminus B$이기 위한 필요충분조건은 $(x \in A)$ $\land$ $(x \notin B)$인 것이다.

유한 합집합 :

임의의 집합 $A,B$에 대해 집합 $\displaystyle \bigcup \{ A, B \} = A\cup B$를 $A$와 $B$의 합집합으로 정의하고

$x \in A\cup B$이기 위한 필요충분조건은 $(x\in A) $ $\lor$ $ (x \in B)$인 것이다.

 

 

 

정리7

다음이 성립한다.

단일 원소집합의 존재성 : 임의의 $a$에 대해 단일 원소집합 $\{ a\}$가 존재한다.

유한 교집합의 존재성 : 임의의 집합 $A,B$에 대해 유한 교집합 $A\cap B$가 존재한다.

유한 여집합의 존재성 : 임의의 집합 $A,B$에 대해 유한 여집합 $A\setminus B$가 존재한다.

유한 합집합의 존재성 : 임의의 집합 $A,B$에 대해 유한 합집합 $A\cup B$가 존재한다.

증명

단일 원소집합의 존재성

임의의 $a,b$에 대해 짝 공리로 두 원소집합 $\{ a,b \}$가 존재하여 $a =b$이면

모든 $s \in \{ a,b\}$는 $s = a$이거나 $s = b$이므로 $s = a =b$가 되어 $\{ a ,b \} = \{ a \}$인 단일 원소집합이 존재한다.

유한 교집합의 존재성

분류 공리로 $A \cap B = \{ x \in A : (x \in B) \equiv \mathbf{T} \}$인 집합이 존재하여

모든 $x \in A \cap B$가 $x \in A$이고 $x \in B$인 교집합 $A \cap B$가 존재한다.

유한 여집합의 존재성

분류 공리로 $A \setminus B = \{ x \in A : (x \notin B) \equiv \mathbf{T} \}$인 집합이 존재하여

모든 $x \in A \cap B$가 $x \in A$이고 $x \notin B$인 여집합 $A\setminus B$가 존재한다.

유한 합집합의 존재성

짝 공리로 두 원소집합 $\{ A, B \}$가 존재하고 합집합 공리로 $\displaystyle \bigcup \{ A ,B \}$인 집합이 존재하여

$\displaystyle x \in \bigcup \{ A ,B \}$이면 $x \in S$인 $S \in \{ A,B \}$가 존재하므로

짝 공리로 $S$는 $S = A$이거나 $S = B$임에 따라 $x \in A$이거나 $x \in B$가 되어 합집합 $\displaystyle \bigcup \{ A ,B \} = A\cup B$가 존재한다.

 

 

 

정리5

임의의 집합 $A,B,C$에 대해 다음이 성립한다.

부분집합 관계의 반사성 : $A \subseteq A$

부분집합 관계의 반대칭성 : $A = B$이기 위한 필요충분조건은 $A \subseteq B$이고 $B \subseteq A$인 것이다.

부분집합 관계의 추이성 : 

1. $A \subseteq B$이고 $B \subseteq C$이면 $A \subseteq C$이다.

2. $A \subset B$이고 $B \subset C$이면 $A \subset C$이다.

3. $A \subset B$이고 $B \subseteq C$이면 $A \subset C$이다.

4. $A \subseteq B$이고 $B \subset C$이면 $A \subset C$이다.

집합 상등의 반사성 : $A = A$

집합 상등의 대칭성 : $A = B$이면 $B = A$이다.

집합 상등의 추이성 : $A = B$이고 $B = C$이면 $A = C$이다.

증명

부분집합 관계의 반사성

명제 연산 정리와 조건 명제 정리로

$\begin{align*} (x \in A) \to (x \in A) \equiv \neg (x \in A) \lor (x \in A) \equiv \mathbf{T} \end{align*}$이므로 위 정의로 $A \subseteq A$이다

부분집합 관계의 반대칭성

$A = B$이면

집합의 상등으로 $(x \in A) \to (x \in B) \equiv \mathbf{T}$이고 $(x \in B) \to (x \in A) \equiv \mathbf{T}$이므로

위 정의로 $A \subseteq B$이고 $B \subseteq A$이다.

역으로 $A \subseteq B$이고 $B \subseteq A$이면

위 정의로 $(x \in A) \to (x \in B) \equiv \mathbf{T}$이고 $(x \in B) \to (x \in A) \equiv \mathbf{T}$이므로

집합의 상등으로 $A = B$이다.

부분집합 관계의 추이성

1.

$A \subseteq B$이고 $B \subseteq C$이면

위 정의로 $(x \in A) \to (x \in B) \equiv \mathbf{T}$이고 $(x \in B) \to (x \in C) \equiv \mathbf{T}$이므로

명제 연산 정리와 조건 명제 정리로

$\begin{align*} (x\in A) \to (x \in C) & \equiv \neg (x\in A) \lor (x \in C) \\[0.5em] & \equiv \neg (x\in A) \lor \mathbf{T} \lor (x \in C) \\[0.5em] & \equiv \neg (x\in A) \lor ((x \in B) \lor \neg (x\in B) ) \lor (x \in C) \\[0.5em] & \equiv (\neg (x\in A) \lor (x \in B)) \lor (\neg (x\in B) \lor (x \in C)) \\[0.5em] & \equiv ((x\in A) \to (x \in B)) \lor ((x\in B) \to (x \in C)) \\[0.5em] & \equiv \mathbf{T} \lor \mathbf{T} \\[0.5em] & \equiv \mathbf{T} \text{ 가 되어} \end{align*}$

위 정의로 $A\subseteq C$이다.

2.

위 정의로 $A\subset B$는 $(b \in B) \to (b\in A) \equiv \mathbf{F}$인 $b \in B$가 존재하고

위 정의로 $B\subset C$는 $(b \in B) \to (b\in C) \equiv \mathbf{T}$가 되어 조건문의 정의로 $(b \in C) \equiv \mathbf{T}$이다.

따라서 위 정의와 1번으로 $A\subseteq C$이고

$(b \in B) \equiv \mathbf{T}$이므로 $(b \in B) \to (b\in A) \equiv \mathbf{F}$는 조건문의 정의로 $(b \in A) \equiv \mathbf{F}$가 되어

$(b \in C) \to (b\in A) \equiv \mathbf{F}$이고 위 정의로 $A\subset C$이다.

3.

2번 증명과 같다.

4.

위 정의로 $B\subset C$는 $(c \in C) \to (c \in B) \equiv \mathbf{F}$인 $c \in C$가 존재하여 조건문의 정의로 $(c \in B) \equiv \mathbf{F}$이고

위 정의로 $A \subseteq B$는 $(c \in A) \to (c \in B) \equiv \mathbf{T}$이므로 조건문의 정의로 $(c \in A) \equiv \mathbf{F}$이다.

따라서 조건문의 정의로 $(c \in C) \to (c \in A) \equiv \mathbf{F}$이고 위 정의와 1번으로 $A\subseteq C$이므로 $A \subset C$이다.

집합 상등의 반사성

부분집합 관계의 반사성으로 $A\subseteq A$이므로 부분집합 관계의 반대칭성으로 $A = A$이다.

집합 상등의 대칭성 

$A = B$이면 부분집합 관계의 반대칭성으로 $A \subseteq B$이고 $B \subseteq A$이므로

명제 정리로 $B \subseteq A$이고 $A \subseteq B$가 되어 다시 부분집합 관계의 반대칭성으로 $B = A$이다.

집합 상등의 추이성 

$A = B$이고 $B = C$이면

부분집합 관계의 반대칭성으로 $A\subseteq B$이고 $B\subseteq C$이므로 부분집합 관계의 추이성으로 $A \subseteq C$이다.

또 부분집합 관계의 반대칭성으로 $B\subseteq A$이고 $C\subseteq B$이므로

명제 정리로 $C\subseteq B$이고 $B\subseteq A$가 되어 부분집합 관계의 추이성으로 $C \subseteq A$이고

부분집합 관계의 반대칭성으로 $A = C$이다.

 

 

 

정리8

임의의 집합 $A,B,C$에 대해 다음이 성립한다.

1. $A \cup B = B \cup A$

2. $A\cup (B\cup C) = (A \cup B) \cup C$

3. $A \cap B = B \cap A$

4. $A\cap (B \cap C) = (A\cap B) \cap C$

5. $A \setminus A = \emptyset$

증명

1.

명제 정리로 $(x \in A) $ $\lor$ $ (x \in B) $ $\equiv$ $ (x \in B) \lor (x \in A)$이므로

합집합의 정의로 모든 $x \in A\cup B$는 $x \in B \cup A$이고 모든 $x \in B \cup A$는 $x \in A \cup B$가 되어

집합의 상등으로 $A \cup B = B \cup A$이다.

2.

합집합의 정의로 $(x\in B\cup C) \equiv (x \in B)\lor (x \in C)$이고 $(x\in A\cup B) \equiv (x \in A)\lor (x \in B)$이므로

명제 정리로

$\begin{align*}(x\in A) \lor (x \in B\cup C) & \equiv (x\in A) \lor ((x\in B) \lor (x \in C)) \\[0.5em] & \equiv ((x\in A) \lor (x\in B))\lor (x \in C) \\[0.5em] & \equiv (x \in A\cup B) \lor (x \in C) \text{ 가 되어 } \end{align*}$

집합의 상등으로 $A\cup (B\cup C) = (A \cup B) \cup C$이다.

3.

명제 정리로 $(x \in A) $ $\land$ $ (x \in B) $ $\equiv$ $ (x \in B) \land (x \in A)$이므로

교집합의 정의로 모든 $x \in A\cap B$는 $x \in B \cap A$이고 모든 $x \in B \cap A$는 $x \in A \cap B$가 되어

집합의 상등으로 $A \cup B = B \cup A$이다.

4.

교집합의 정의로 $(x\in B\cap C) \equiv (x \in B)\land (x \in C)$이고 $(x\in A\cap B) \equiv (x \in A)\land (x \in B)$이므로

명제 정리로

$\begin{align*}(x\in A) \land (x \in B\cap C) & \equiv (x\in A) \land ((x\in B) \land (x \in C)) \\[0.5em] & \equiv ((x\in A) \land (x\in B))\land (x \in C) \\[0.5em] & \equiv (x \in A\cap B) \land (x \in C) \text{ 가 되어 } \end{align*}$

집합의 상등으로 $A\cap (B\cap C) = (A \cap B) \cap C$이다.

5.

명제 정리로 $(x \in A) $ $\land$ $ (x \notin A) $ $\equiv$ $ (x \in A) \land \neg (x \in A) \equiv \mathbf{F} \equiv (x \in \emptyset)$이므로

여집합의 정의와 공집합 공리로 $A \setminus A = \emptyset$이다.

 

 

 

정리4

공집합 $\emptyset$과 임의의 집합 $A$에 대해 다음이 성립한다.

1. 공집합은 모든 집합의 부분집합이다.

2. 공집합은 유일하다. 

3. $A \subseteq \emptyset$이면 $A = \emptyset$이다.

4. $A \cup \emptyset = A$

5. $A \cap \emptyset = \emptyset$

6. $A \setminus \emptyset = A$

7. $A \ne \emptyset$이기 위한 필요충분조건은 $x \in A$가 존재하는 것이다.

증명

1.

$\emptyset \subseteq A$임을 보이기 위해선 위 정의로 '$x \in \emptyset$이면 $x \in A$이다.' 라는 명제가 참이어야 한다.

위 명제는 $(x \in \emptyset) \equiv \mathbf{F}$로 가정이 거짓이므로 공허하게 성립하여 $\emptyset \subseteq A$이다.

2.

공집합 $\emptyset_1, \emptyset_2$가 존재하면

1번으로 $\emptyset_1 \subseteq \emptyset_2$이고 $\emptyset_2 \subseteq \emptyset_1$이므로 위 정리로 $\emptyset_1 = \emptyset_2$이다.

3.

$A \subseteq \emptyset$일때 $A \ne \emptyset$이라고 하면

$x \in A$가 존재하여 모든 $x \in A$에 대해 $x \in \emptyset$인데 공집합의 정의로 $x \notin \emptyset$이므로 모순이다.

따라서 $A \subseteq \emptyset$이면 $A = \emptyset$이다.

4.

명제 정리로 $ (x \in A) $ $\lor$ $(x \in \emptyset) \equiv (x \in A) \lor \mathbf{F} \equiv (x \in A)$이므로

합집합의 정의와 집합의 상등으로 $A \cup \emptyset = A$이다.

5.

명제 정리로 $ (x \in A) $ $\land$ $(x \in \emptyset) \equiv (x \in A) \land \mathbf{F} \equiv \mathbf{F}$이므로

교집합의 정의와 공집합 공리로 $A \cap \emptyset = \emptyset$이다.

6.

명제 정리로 $ (x \in A) $ $\land$ $(x \notin \emptyset) \equiv (x \in A) \land \mathbf{T} \equiv (x\in A)$이므로

여집합의 정의와 집합의 상등으로 $A \setminus \emptyset = A$이다.

7. 

$A \ne \emptyset$일때 $a \in A$가 존재하지 않는다고 가정하면

항상 $(x \notin A) \equiv \mathbf{T}$가 되어 공집합 공리로 $A = \emptyset$이므로 모순이다.

따라서 $A \ne \emptyset$이면 $x \in A$가 존재한다.

역으로 $a \in A$일때 $A = \emptyset$이라고 가정하면

공집합 공리로 항상 $(x \notin A) \equiv \mathbf{T}$인데 $(a \in A) \equiv \mathbf{T}$이므로 모순이다.

따라서 $a \in A$이면 $A\ne \emptyset$이다.

 

 

 

정리1

집합 $A$와 $B$와 $X$에 대해 다음이 성립한다.

1. $A \subseteq X$이기 위한 필요충분조건은 $A \cap X = A$인 것이다.

2. $A \subseteq X$이기 위한 필요충분조건은 $A \cup X = X$인 것이다.

3. $A\subseteq X$이고 $X \setminus A = \emptyset$이기 위한 필요충분조건은 $A = X$인 것이다.

4. $A\subseteq X$이고 $B \subseteq X$일때 $X\setminus A = X\setminus B$이기 위한 필요충분조건은 $A = B$인 것이다.

5. $A\subseteq X$이면 $X\setminus (X \setminus A) = A$이다.

6. $A\subseteq X$일때 $A\cap B = \emptyset$이기 위한 필요충분조건은 $A \subseteq X\setminus B$인 것이다.

7. $A\subseteq X$이면 $A\cap (X\setminus B) = A\setminus (A\cap B)$이다.

8. $A\subseteq X$이고 $B \subseteq X$일때 $A\cap B = \emptyset$이고 $A\cup B = X$이면 $A = X\setminus B$이고 $B = X\setminus A$이다.

증명

1.

$A \subseteq X$이면

위 정의로 모든 $x \in A$는 $x \in X$이므로 교집합의 정의로 $x \in A \cap X$이고 위 정의로 $A \subseteq A \cap X$이다.

또 $x \in A \cap X$일때는 교집합의 정의로 $x \in A$이므로 $A \cap X \subseteq A$이고 위 정리로 $A \cap X = A$가 된다.

역으로 $A \cap X = A$이면

모든 $x \in A =A \cap X$는 교집합의 정의로 $x \in X$이므로 위 정의로 $A \subseteq X$이다.

2.

$A \subseteq X$일때

모든 $x \in X$는 합집합의 정의로 $x \in A \cup X$가 되어 위 정의로 $X \subseteq A \cup X$이고

모든 $x \in A \cup X$는 합집합의 정의로 $x \in A$이거나 $x \in X$인데

$A \subseteq X$이므로 위 정의로 모든 $x \in A$는 $x \in X$가 되어 $A \cup X  \subseteq X$이고 위 정리로 $A\cup X = X$이다.

역으로 $A \cup X = X$일때

모든 $x \in A$는 합집합의 정의로 모든 $x \in A \cup X = X$이므로 위 정의로 $A \subseteq X$이다.

3.

$A = X$이면 위 정리로 $A \subseteq X$이고 위 정리로 $X\setminus A = X\setminus X = \emptyset$이다.

역으로 $A \subseteq X$이고 $X \setminus A = \emptyset$이면

여집합의 정의와 공집합의 정의와 명제 연산 정리와 조건 명제 정리로

$\begin{align*} (x \in X) \to (x \in A) & \equiv \neg (x \in X) \lor (x \in A) \\[0.5em] & \equiv \neg(\neg(\neg (x\in X) \lor (x\in A))) \\[0.5em] & \equiv \neg ( (x \in X) \land \neg (x \in A) ) \\[0.5em] & \equiv \neg ( (x \in X) \land (x \notin A)) ) \\[0.5em] & \equiv \neg ( x \in X \setminus A ) \\[0.5em] & \equiv \neg ( x \in \emptyset ) \\[0.5em] & \equiv \mathbf{T} \text{ 가 되어}  \end{align*}$

위 정의로 $X \subseteq A$이고 위 정리로 $A = X$이다.

4.

$X\setminus A = X\setminus B$일때 $A \ne B$라고 가정하면

$x \in A$이고 $x \notin B$인 $x \in X$가 존재하여 $x \in X\setminus B $인데 $x \in X\setminus B = X\setminus A$이므로 $x\notin A$가 되어 모순이다.

역으로 $A = B$이면

모든 $x \in X\setminus A$는 여집합의 정의로 $x\in X$이고 $x\notin A$이므로 $x \notin B$가 되어 $x \in X\setminus B$이고 $X\setminus A\subseteq X\setminus B$이다.

비슷하게 $X\setminus B\subseteq X\setminus A$이므로 위 정리로 $X\setminus A= X\setminus B$이다.

5.

1번으로 $X\cap A = A$이므로 명제 정리와 여집합의 정의로

$\begin{align*} x \in X\setminus (X \setminus A) & \equiv (x\in X) \land (x\notin X\setminus A) \\[0.5em] & \equiv (x\in X) \land \neg (x \in X\setminus A) \\[0.5em] &\equiv (x \in X) \land \neg ((x \in X) \land (x\notin A)) \\[0.5em] & \equiv (x\in X) \land ( \neg (x\in X) \lor (x \in A)) \\[0.5em] & \equiv ((x\in X) \land \neg (x\in X) ) \lor ((x\in X) \land (x \in A)) \\[0.5em] & \equiv \mathbf{F} \lor ((x\in X) \land (x \in A)) \\[0.5em] & \equiv x \in X\cap A \\[0.5em] & \equiv x \in A \text{ 가 되어} \end{align*}$

$X\setminus (X \setminus A) = A$이다.

6.

$A \subseteq X$이므로 $\mathbf{T} \equiv (x\in A) \to (x \in X)$가 되어 명제 연산 정리와 조건 명제 정리로

$ \begin{align*} (x \in A) \to (x \in X\setminus B) & \equiv \neg (x \in A) \lor (x \in X\setminus B) \\[0.5em] & \equiv \neg (x \in A) \lor ((x \in X) \land (x\notin B)) \\[0.5em] & \equiv \neg (x \in A) \lor ((x \in X) \land \neg (x\in B)) \\[0.5em] & \equiv (\neg (x \in A) \lor (x \in X)) \land ( \neg (x \in A) \lor \neg (x\in B)) \\[0.5em] & \equiv ((x \in A) \to (x \in X)) \land \neg ( (x \in A) \land (x\in B)) \\[0.5em] & \equiv \mathbf{T} \land \neg (x \in A \cap B) \\[0.5em] & \equiv x \notin A \cap B \text{ 이므로} \end{align*} $

$A\cap B = \emptyset$이기 위한 필요충분조건은 $A \subseteq X\setminus B$인 것이다.

7.

$A\subseteq X$이므로 1번으로 $A\cap X = A$이고 명제 연산 정리로

$\begin{align*} x\in A \setminus (A\cap B) &\equiv (x\in A) \land (x\notin A\cap B) \\[0.5em] & \equiv (x\in A) \land \neg (x\in A\cap B) \\[0.5em] & \equiv (x\in A) \land \neg ((x\in A) \land (x\in B)) \\[0.5em] & \equiv (x\in A) \land (\neg (x\in A) \lor \neg (x\in B)) \\[0.5em] & \equiv ((x\in A) \land \neg (x\in A)) \lor ((x\in A) \land \neg (x\in B)) \\[0.5em] & \equiv \mathbf{F} \lor ((x\in A\cap X) \land \neg (x\in B)) \\[0.5em] & \equiv (x\in A)\land (x\in X) \land \neg (x\in B) \\[0.5em] & \equiv (x\in A)\land ((x\in X) \land (x\notin B)) \\[0.5em] & \equiv (x\in A)\land (x\in X \setminus B) \\[0.5em] & \equiv x\in A\cap (X \setminus B) \text{ 가 되어} \end{align*}$

$A\cap (X\setminus B) = A\setminus (A\cap B)$이다.

8.

$B\subseteq X$이고 $A\cap B = \emptyset$이므로 6번으로 $B \subseteq X\setminus A$이고

$A\cup B = X$이므로 아래 정리와 위 정리와 위 정리로

$X\setminus A = (A\cup B)\setminus A = (A\setminus A)\cup (B\setminus A) =\emptyset \cup (B\setminus A)= B\setminus A \subseteq B$가 되어

위 정리로 $B = X\setminus A$이고 $A\subseteq X$이므로 5번으로 $A =X\setminus (X\setminus A) = X\setminus B$이다.

 

 

 

정의4

집합족(family of sets) :

집합들의 집합임을 명시할때 집합을 집합족으로 표기한다.

집합족의 합집합 : 

$\mathcal{F}$가 집합족일때

$\displaystyle \bigcup \mathcal{F} = \bigcup_{A \in \mathcal{F}}A = \{x  : \text{ 어떤 } A\in \mathcal{F} \text{ 에 대해 } x \in A \}$를 $\mathcal{F}$의 합집합으로 정의하고

$\displaystyle x \in \bigcup \mathcal{F}$이기 위한 필요충분조건은 $x \in S$인 $S \in \mathcal{F}$가 존재하는 것이다.

집합족의 교집합 : 

$\mathcal{F}$가 집합족일때 임의의 $B \in \mathcal{F}$에 대해

$\displaystyle \bigcap \mathcal{F} = \bigcap_{A \in \mathcal{F}}A = \{x  \in B : \text{모든 } A \in \mathcal{F}  \text{ 에 대해 } x \in A \}$를 $\mathcal{F}$의 교집합으로 정의하고

$\displaystyle x \in \bigcap \mathcal{F}$이기 위한 필요충분조건은 모든 $A \in \mathcal{F}$에 대해 $x \in A$인 것이다.

색인된 집합(indexed sets) : 

집합 $I$와 어떤 명제함수 $P$에 대해 모든 $i \in I$마다 $P(i,A) \equiv \mathbf{T}$인 $A$가 유일하게 존재할때

집합 $I$를 색인 집합(index set)으로 정의하고

$\mathcal{F}_I = \{A  : \text{어떤 } i\in I \text{ 에 대해 }P(i,A) \equiv \mathbf{T} \} = \{ A_i  : i \in I\}$를 $I$에 대해 색인된 집합(indexed set)으로 정의한다.

$A \in \mathcal{F}_I$이기 위한 필요충분조건은 $P(i,A)\equiv \mathbf{T}$인 $i \in I$가 존재하는 것이다.

색인된 집합족의 합집합 : 

$\mathcal{F}_I =\{A_i : i \in I \}$가 색인 집합 $I$에 대해 색인된 집합족일때 

$\displaystyle \bigcup \mathcal{F}_I = \bigcup_{i \in I}A_i = \{x  : \text{ 어떤 } i \in I \text{ 에 대해 } x \in A_i \in \mathcal{F}_I \}$를 $\mathcal{F}_I$의 합집합을 정의하고

$\displaystyle x \in \bigcup \mathcal{F}_I$이기 위한 필요충분조건은 어떤 $i \in I$에 대해 $x \in A_i$인 $A_i \in \mathcal{F}_I$가 존재하는 것이다.

색인된 집합족의 교집합 : 

$\mathcal{F}_I =\{A_i : i \in I \}$가 색인 집합 $I$에 대해 색인된 집합족일때 임의의 $j \in I$에 대해

$\displaystyle \bigcap \mathcal{F}_I = \bigcap_{i \in I}A_i = \{x \in A_j : \text{ 모든 } i \in I \text{ 에 대해 } x \in A_i \in \mathcal{F}_I \}$를 $\mathcal{F}_I$의 교집합을 정의하고

$\displaystyle x \in \bigcap \mathcal{F}_I$이기 위한 필요충분조건은 모든 $i \in I$에 대해 $x \in A_i$인 $A_i \in \mathcal{F}_I$가 존재하는 것이다.

자연수집합의 부분집합에 대해 색인된 집합족의 합집합과 교집합 : 

임의의 자연수 $n, m \in \mathbb{N}$에 대해 색인집합이 $I = \{ i \in \mathbb{N} : n \le i \le m \}$이고

$I$에 대해 색인된 집합족 $\mathcal{F}_I =\{A_i : i \in I \} = \{ A_i : n \le i \le m \}$일때

$\mathcal{F}_I$의 합집합을 $\displaystyle \bigcup \mathcal{F}_I = \bigcup_{i \in I} A_i = \bigcup_{i = n}^m A_i$로 정의하고

$\mathcal{F}_I$의 교집합을 $\displaystyle \bigcap \mathcal{F}_I =\bigcap_{i \in I} A_i = \bigcap_{i = n}^m A_i$로 정의한다.

색인집합 $I = \{ i \in \mathbb{N} : n \le i  \}$에 대해 색인된 집합족이 $\mathcal{F}_I =\{A_i : i \in I \} = \{ A_i : n \le i \}$일때

$\mathcal{F}_I$의 합집합을 $\displaystyle \bigcup \mathcal{F}_I = \bigcup_{i \in I} A_i = \bigcup_{i = n}^\infty A_i$로 정의하고

$\mathcal{F}_I$의 교집합을 $\displaystyle \bigcap \mathcal{F}_I  = \bigcap_{i \in I} A_i= \bigcap_{i = n}^\infty A_i$로 정의한다.

 

 

 

정리10

$\mathcal{F}$가 집합족이고 색인 집합 $I$에 대해 색인된 집합족이 $\mathcal{F}_I$일때 다음이 성립한다.

집합족의 합집합의 존재성 : $\mathcal{F}$의 합집합이 존재한다.

집합족의 교집합의 존재성 : $\mathcal{F}$의 교집합이 존재한다.

색인된 집합의 존재성 : 색인 집합 $I$에 대해 색인된 집합족이 $\mathcal{F}_I$가 존재한다.

색인된 집합족의 합집합의 존재성 : $\mathcal{F}_I$의 합집합이 존재한다.

색인된 집합족의 교집합의 존재성 : $\mathcal{F}_I$의 교집합이 존재한다.

증명

집합족의 합집합의 존재성

합집합 공리로 $\mathcal{F}$의 합집합 $\displaystyle \bigcup \mathcal{F}$가 존재한다.

집합족의 교집합의 존재성

분류 공리로 임의의 $B \in \mathcal{F}$에 대해 $x\in B$이고 모든 $A \in \mathcal{F}$에 대해 $x \in A$인 $\mathcal{F}$의 교집합 $\displaystyle \bigcap \mathcal{F}$가 존재한다.

색인된 집합의 존재성

색인 집합의 정의로 어떤 명제함수 $P$에 대해 모든 $i \in I$마다 $P(i,A) \equiv \mathbf{T}$인 $A$가 유일하게 존재하므로

치환 공리로 $A \in \mathcal{F}_I$이기 위한 필요충분조건이 $P(i,A)\equiv \mathbf{T}$인 $i \in I$가 존재하는 것인

$I$에 대해 색인된 집합 $\mathcal{F}_I$가 존재한다.

색인된 집합족의 합집합의 존재성

합집합 공리로 $\mathcal{F}_I$의 합집합 $\displaystyle \bigcup \mathcal{F}_I $가 존재하여 $\displaystyle x \in \bigcup \mathcal{F}_I$이면 $x \in A$인 $A \in \mathcal{F}_I $가 존재하고

색인된 집합의 정의로 $A \in \mathcal{F}_I $는 $A = A_i$인 $i \in I$가 존재하므로 색인된 집합족의 합집합 $\displaystyle \bigcup \mathcal{F}_I = \bigcup_{i \in I} A_i $가 존재한다.

색인된 집합족의 교집합의 존재성

임의의 $j \in I$에 대해 색인된 집합의 정의로 $A_j \in \mathcal{F}_I$가 존재하므로

분류 공리로 $x \in A_j$이고 모든 $i \in I$에 대해 $x \in A_i$인 $A_i \in \mathcal{F}_I$가 존재하는

색인된 집합족의 교집합 $\displaystyle \bigcap \mathcal{F}_I = \bigcap_{i \in I} A_i$가 존재한다.

 

 

 

정리2

집합 $A,B,C$에 대해 다음이 성립한다.

1. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

2. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

 

임의의 $n \in $ $\mathbb{Z}^+$에 대해 $B_1,B_2,\cdots, B_n$이 집합일때 다음이 성립한다.

3. $ \displaystyle A \cap \left (\bigcup_{i = 1}^n B_i \right ) = (A\cap B_1)\cup (A\cap B_2)\cup \cdots \cup (A\cap B_n)$이다.

4. $ \displaystyle A \cup \left (\bigcap_{i = 1}^n B_i \right ) = (A\cup B_1)\cap (A\cup B_2)\cap \cdots \cap (A\cup B_n)$이다.

증명

1.

위 정의에 따라 $A \cap (B \cup C)$는 

명제 $(x \in A) \land ((x \in B)  \lor  (x \in C)) $가 참이 되는 $x$의 집합으로 표현되어

분배 법칙으로 $(x \in A) \land ((x \in B)  \lor  (x \in C)) \equiv ((x\in A) \land (x \in B)) \lor ((x\in A) \land (x\in C))$이므로

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$이다.

2.

위 정의에 따라 $A \cup (B \cap C)$는 

명제 $(x \in A) \lor (( x \in B) \land ( x \in C)) $가 참이 되는 $x$의 집합으로 표현되어

분배 법칙으로 $(x \in A) \lor ((x \in B)  \land  (x \in C)) \equiv ((x\in A) \lor (x \in B)) \land ((x\in A) \lor (x\in C))$이므로

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$이다.

3.

$n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 1$일땐 자명하게 성립하므로 모든 $k \in \mathbb{Z}^+$에 대해 성립한다 가정할때

집합족의 합집합의 정의로 $\displaystyle x\in \bigcup_{i = 1}^{k+1} B_i$는 $x \in B_i$이고 $1\le i\le k+1$인 $i \in \mathbb{Z}^+$가 존재하여

$\displaystyle x\in \bigcup_{i = 1}^{k} B_i$이거나 $x \in B_{k+1}$이므로

유한합집합의 정의로 $\displaystyle x\in \left (\bigcup_{i = 1}^{k} B_i\right) \cup B_{k+1}$가 되어 $\displaystyle \bigcup_{i =1}^{k+1} B_i \subseteq \left (\bigcup_{i = 1}^{k} B_i\right) \cup B_{k+1}$이고

$\displaystyle \left (\bigcup_{i = 1}^{k} B_i\right) \cup B_{k+1}\subseteq \bigcup_{i = 1}^{k+1} B_i$임은 자명하므로 반대칭성으로 $\displaystyle \left (\bigcup_{i = 1}^{k} B_i\right) \cup B_{k+1} =\bigcup_{i = 1}^{k+1} B_i$이다.

따라서 1번과 귀납가정으로 

$ \begin{align*} A \cap \left ( \bigcup_{i = 1}^{k+1} B_i \right ) &  = A \cap \left (  \left ( \bigcup_{i = 1}^k B_i \right ) \cup B_{k+1} \right ) \\[0.5em]  & = (A \cap \left ( \bigcup_{i = 1}^k B_i \right )) \cup (A \cap B_{k+1}) \\[0.5em] & =  (A\cap B_1)\cup (A\cap B_2)\cup \cdots \cup (A\cap B_k) \cup (A\cap B_{k+1}) \text{ 이므로} \end{align*}$

모든 $n \in \mathbb{Z}^+$에 대해 성립한다.

4.

$n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 1$일땐 자명하게 성립하므로 모든 $k \in \mathbb{Z}^+$에 대해 성립한다 가정할때

집합족의 교집합의 정의로 $\displaystyle x\in \bigcap_{i = 1}^{k+1} B_i$는 $1\le i\le k+1$인 모든 $i \in \mathbb{Z}^+$에 대해 $x \in B_i$가 되어

$\displaystyle x\in \bigcap_{i = 1}^{k} B_i$이고 $x \in B_{k+1}$이므로

유한교집합의 정의로 $\displaystyle x\in \left (\bigcap_{i = 1}^{k} B_i\right) \cap B_{k+1}$가 되어 $\displaystyle \bigcap_{i =1}^{k+1} B_i \subseteq \left (\bigcap_{i = 1}^{k} B_i\right) \cap B_{k+1}$이고

$\displaystyle \left (\bigcup_{i = 1}^{k} B_i\right) \cap B_{k+1}\subseteq \bigcap_{i = 1}^{k+1}B_i$임은 자명하므로 반대칭성으로 $\displaystyle \left (\bigcap_{i = 1}^{k} B_i\right) \cap B_{k+1} =\bigcap_{i = 1}^{k+1}B_i$이다.

따라서 2번과 귀납가정으로 

$ \begin{align*} A \cup \left ( \bigcap_{i = 1}^{k+1} B_i \right ) &  = A \cup \left (  \left ( \bigcap_{i = 1}^k B_i \right ) \cap B_{k+1} \right ) \\[0.5em]  & = (A \cup \left ( \bigcap_{i = 1}^k B_i \right )) \cap (A \cap B_{k+1}) \\[0.5em] & =  (A\cup B_1)\cap (A\cup B_2)\cap \cdots \cap (A\cup B_k) \cap (A\cup B_{k+1}) \text{ 이므로} \end{align*}$

모든 $n \in \mathbb{Z}^+$에 대해 성립한다.

 

 

 

정리3

집합 $A,B,C$에 대해 다음이 성립한다.

1. $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C) = (A \setminus B) \setminus C$

2. $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$

3. $(B \cup C) \setminus  A = (B \setminus A) \cup (C \setminus A)$

4. $(B \cap C) \setminus  A = (B \setminus A) \cap (C \setminus A)$

 

임의의 $n \in $ $\mathbb{Z}^+$에 대해 $B_1,B_2,\cdots, B_n$이 집합일때 다음이 성립한다.

5. $ \displaystyle A \setminus \left (\bigcup_{i = 1}^n B_i \right ) = (A\setminus B_1)\cap (A\setminus B_2)\cap \cdots \cap (A\setminus B_n)$

6. $ \displaystyle A \setminus \left (\bigcap_{i = 1}^n B_i \right ) = (A\setminus B_1)\cup (A\setminus B_2)\cup \cdots \cup (A\setminus B_n)$

7. $ \displaystyle \left (\bigcup_{i = 1}^n B_i \right ) \setminus A = (B_1\setminus A)\cup (B_2\setminus A)\cup \cdots \cup (B_n\setminus A)$

8. $ \displaystyle \left (\bigcap_{i = 1}^n B_i \right ) \setminus A = (B_1\setminus A)\cap (B_2\setminus A)\cap \cdots \cap (B_n\setminus A)$

증명

1.

위 정의로 $ A \setminus (B \cup C)$는 명제 $(x \in A) \land ( x \notin B \cup C) $가 참이 되는 $x$의 집합으로 표현되고

드 모르간 법칙으로

$ x \notin B \cup C \equiv \neg (x \in B \cup C) \equiv \neg ((x \in B) \lor (x \in C)) \equiv \neg (x\in B) \land \neg (x \in C) \equiv (x \notin B ) \land (x \notin C)$이므로

명제 정리들로

$(x \in A) \land ( x \notin B \cup C) \equiv (x \in A) \land ( (x \notin B) \land (x \notin C) ) \equiv ((x\in A) \land (x \notin B)) \land ((x\in A) \land (x \notin C)) \text{ 가 되어}$

$A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$이다.

위 정의로 $(A \setminus B) \setminus C$는

명제 $((x \in A) \land ( x \notin B) ) \land (x \notin C) $가 참이 되는 $x$의 집합으로 표현되고

명제 정리들로

$\begin{align*} ((x \in A) \land ( x \notin B) ) \land (x \notin C) & \equiv (x \in A) \land ( (x\notin B) \land (x\notin C) ) \\[0.5em] & \equiv (x \in A) \land ( \neg (x \in B) \land \neg (x \in C) ) \\[0.5em] & \equiv (x \in A) \land \neg ( (x \in B) \lor (x \in C)) \\[0.5em] & \equiv (x \in A ) \land \neg (x \in B\cup C) \\[0.5em] & \equiv (x \in A) \land ( x \notin B\cup C) \text{ 가 되어} \end{align*}$

$A \setminus (B \cup C) = (A \setminus B) \setminus C$이다.

2.

위 정의로 $A \setminus (B \cap C) $는 명제 $(x \in A) \land ( x \notin B \cap C)$가 $x$의 참이 되는 집합으로 표현되고

드 모르간 법칙으로

$ x \notin B \cap C \equiv \neg (x \in B \cap C) \equiv \neg ((x \in B) \land (x \in C)) \equiv \neg (x\in B) \lor \neg (x \in C) \equiv (x \notin B ) \lor (x \notin C)$이므로

분배 법칙으로

$(x \in A) \land ( x \notin B \cap C) \equiv (x \in A) \land ( (x \notin B) \lor (x \notin C) ) \equiv ((x\in A) \land (x \notin B)) \lor ((x\in A) \land (x \notin C)) \text{ 가 되어}$

$A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$이다.

3.

위 정의와 명제 정리로

$\begin{align*} x \in ((B\cup C) \setminus A) & \equiv (x \in B\cup C) \land (x \notin A) \\[0.5em] & \equiv ((x \in B) \lor (x\in C)) \land (x \notin A) \\[0.5em] & \equiv ((x \in B) \land (x \notin A)) \lor ((x\in C)\land (x \notin A) ) \\[0.5em] & \equiv (x \in B\setminus A) \lor (x\in C \setminus A ) \\[0.5em] & \equiv x \in ((B\setminus A) \cup (C \setminus A )) \text{ 이므로} \end{align*}$

$(B \cup C) \setminus  A = (B \setminus A) \cup (C \setminus A)$이다.

4.

위 정의와 명제 정리로

$\begin{align*} x \in ((B\cap C) \setminus A) & \equiv (x \in B\cap C) \land (x \notin A) \\[0.5em] & \equiv ((x \in B) \land (x\in C)) \land (x \notin A) \land (x\notin A) \\[0.5em] & \equiv ((x \in B) \land (x \notin A)) \land ((x\in C)\land (x \notin A) ) \\[0.5em] & \equiv (x \in B\setminus A) \land (x\in C \setminus A ) \\[0.5em] & \equiv x \in ((B\setminus A) \cap (C \setminus A )) \text{ 이므로} \end{align*}$

$(B \cap C) \setminus  A = (B \setminus A) \cap (C \setminus A)$이다.

5.

$n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 1$일땐 자명하게 성립하므로 모든 $k \in \mathbb{Z}^+$에 대해 성립한다 가정할때

집합족의 합집합의 정의로 $\displaystyle x\in \bigcup_{i = 1}^{k+1} B_i$는 $x \in B_i$이고 $1\le i\le k+1$인 $i \in \mathbb{Z}^+$가 존재하여

$\displaystyle x\in \bigcup_{i = 1}^{k} B_i$이거나 $x \in B_{k+1}$이므로

유한합집합의 정의로 $\displaystyle x\in \left (\bigcup_{i = 1}^{k} B_i\right) \cup B_{k+1}$가 되어 $\displaystyle \bigcup_{i =1}^{k+1} B_i \subseteq \left (\bigcup_{i = 1}^{k} B_i\right) \cup B_{k+1}$이고

$\displaystyle \left (\bigcup_{i = 1}^{k} B_i\right) \cup B_{k+1}\subseteq \bigcup_{i = 1}^{k+1} B_i$임은 자명하므로 반대칭성으로 $\displaystyle \left (\bigcup_{i = 1}^{k} B_i\right) \cup B_{k+1} =\bigcup_{i = 1}^{k+1} B_i$이다.

따라서 1번과 귀납가정으로 

$ \begin{align*} A \setminus \left ( \bigcup_{i = 1}^{k+1} B_i \right ) &  = A \setminus \left (  \left ( \bigcup_{i = 1}^k B_i \right ) \cup B_{k+1} \right ) \\[0.5em]  & = (A \setminus \left ( \bigcup_{i = 1}^k B_i \right )) \cap (A \setminus B_{k+1}) \\[0.5em] & =  (A\setminus B_1)\cap (A\setminus B_2)\cap \cdots \cap (A\setminus B_k) \cap (A\setminus B_{k+1}) \text{ 이므로} \end{align*}$

모든 $n \in \mathbb{Z}^+$에 대해 성립한다.

6.

$n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 1$일땐 자명하게 성립하므로 모든 $k \in \mathbb{Z}^+$에 대해 성립한다 가정할때

집합족의 교집합의 정의로 $\displaystyle x\in \bigcap_{i = 1}^{k+1} B_i$는 $1\le i\le k+1$인 모든 $i \in \mathbb{Z}^+$에 대해 $x \in B_i$가 되어

$\displaystyle x\in \bigcap_{i = 1}^{k} B_i$이고 $x \in B_{k+1}$이므로

유한교집합의 정의로 $\displaystyle x\in \left (\bigcap_{i = 1}^{k} B_i\right) \cap B_{k+1}$가 되어 $\displaystyle \bigcap_{i =1}^{k+1} B_i \subseteq \left (\bigcap_{i = 1}^{k} B_i\right) \cap B_{k+1}$이고

$\displaystyle \left (\bigcup_{i = 1}^{k} B_i\right) \cap B_{k+1}\subseteq \bigcap_{i = 1}^{k+1}B_i$임은 자명하므로 반대칭성으로 $\displaystyle \left (\bigcap_{i = 1}^{k} B_i\right) \cap B_{k+1} =\bigcap_{i = 1}^{k+1}B_i$이다.

따라서 2번과 귀납가정으로 

$ \begin{align*} A \setminus \left ( \bigcap_{i = 1}^{k+1} B_i \right ) &  = A \setminus \left (  \left ( \bigcap_{i = 1}^k B_i \right ) \cap B_{k+1} \right ) \\[0.5em]  & = (A \setminus \left ( \bigcap_{i = 1}^k B_i \right )) \cup (A \setminus B_{k+1}) \\[0.5em] & =  (A\setminus B_1)\cup (A\setminus B_2)\cup \cdots \cup (A\setminus B_k) \cup (A\setminus B_{k+1}) \text{ 이므로} \end{align*}$

모든 $n \in \mathbb{Z}^+$에 대해 성립한다.

7.

$n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 1$일땐 자명하게 성립하므로 모든 $k \in \mathbb{Z}^+$에 대해 성립한다 가정할때 3번과 귀납가정으로 

$ \begin{align*}  \left ( \bigcup_{i = 1}^{k+1} B_i \right ) \setminus A &  =  \left (  \left ( \bigcup_{i = 1}^k B_i \right ) \cup B_{k+1} \right ) \setminus A \\[0.5em]  & = ( \left ( \bigcup_{i = 1}^k B_i \right ) \setminus A) \cup ( B_{k+1} \setminus A) \\[0.5em] & =  ( B_1 \setminus A)\cup (B_2\setminus A)\cup \cdots \cup (B_k\setminus A) \cup (B_{k+1}\setminus A) \text{ 이므로} \end{align*}$

모든 $n \in \mathbb{Z}^+$에 대해 성립한다.

8.

$n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 1$일땐 자명하게 성립하므로 모든 $k \in \mathbb{Z}^+$에 대해 성립한다 가정할때 4번과 귀납가정으로 

$ \begin{align*}  \left ( \bigcap_{i = 1}^{k+1} B_i \right ) \setminus A &  =  \left (  \left ( \bigcap_{i = 1}^k B_i \right ) \cup B_{k+1} \right ) \setminus A \\[0.5em]  & = ( \left ( \bigcap_{i = 1}^k B_i \right ) \setminus A) \cap ( B_{k+1} \setminus A) \\[0.5em] & =  ( B_1 \setminus A)\cap (B_2\setminus A)\cap \cdots \cap (B_k\setminus A) \cap (B_{k+1}\setminus A) \text{ 이므로} \end{align*}$

모든 $n \in \mathbb{Z}^+$에 대해 성립한다.

 

 

 

정의3

순서쌍(ordered pair) :

임의의 $a,b$에 대해 $(a,b) = \{ \{ a \}, \{ a,b \} \}$를 순서쌍으로 정의한다.

데카르트 곱(cartesian product) : 

임의의 집합 $A, B$에 대해 $A,B$의 데카르트 곱을 $ A \times B = \{ (a,b) : a \in A , b \in B \}$로 정의하고

$x \in A \times B$이기 위한 필요충분조건은 $x = (a,b)$인 $a \in A$와 $b \in B$가 존재하는 것이다.

 

 

 

정리9

다음이 성립한다.

순서쌍의 존재성 : 임의의 $a,b$에 대해 순서쌍 $(a,b)$가 존재한다.

순서쌍의 상등 : 임의의 $a,b,c,d$에 대해 $(a,b) = (c,d)$이기 위한 필요충분조건은 $a = c$이고 $b = d$인 것이다.

데카르트곱의 존재성 : 임의의 집합 $A,B$에 대해 데카르트곱 $A \times B$가 존재한다.

증명

순서쌍의 존재성

단일 원소집합의 존재성과 짝 공리로 $\{ a\}$와 $\{ a, b\}$가 존재하므로 다시 짝 공리로 $(a,b) = \{ \{ a \}, \{ a,b \} \}$가 존재한다.

순서쌍의 상등

$a = c$이고 $b = d$이면

집합의 상등으로 $\{ a\} = \{ c\}$이고 $\{a,b \} = \{ c,d\}$이므로

다시 집합의 상등으로 $ (a,b)=\{ \{ a \}, \{ a,b \} \} =\{ \{ c\} , \{ c,d\} \} =(c,d)$이다.

역으로 $ \{ \{ a \}, \{ a,b \} \} = (a,b) = (c,d) = \{ \{ c\} , \{ c,d\} \}$이면 짝 공리로

$ x \in \{ \{ a \}, \{ a,b \} \} $는 $x = \{ a\}$이거나 $x = \{ a,b\}$이고 $ y \in \{ \{ c\} , \{ c,d\} \}$는 $y = \{ c \}$이거나 $y = \{ c,d\}$이다.

$\{ a\} = \{ c\}$이고 $\{ a ,b\} = \{ c , d\}$이면

$\{ a\} = \{ c\}$는 단일 원소집합의 정의로 $a = c$가 되어

집합의 상등으로 $\{ c ,b\}  = \{ a , b\}= \{ c , d\}$이므로 짝 공리와 집합의 상등으로 $b =d$이다.

$\{ a\} = \{ c, d \}$이고 $\{ c\} = \{ a,b\}$이면

$\{ a\} = \{ c, d \}$는 단일 원소집합의 정의로 $ c = a= d$이고

$\{ c\} = \{ a,b\}$도 단일 원소집합의 정의로 $a = c =b$이므로 $a = b= c=d$가 되어 $a= c$이고 $b =d$이다.

데카르트곱의 존재성

임의의 $a \in A$에 대해 치환 공리로 집합 $a \times B = \{ x : \text{어떤 } b \in B \text{ 에 대해 } x = (a,b)  \}$가 존재하고

다시 치환 공리로 집합족 $\mathcal{F} = \{ X : \text{어떤 } a \in A \text{ 에 대해 } X = a\times B \}$가 존재하므로

집합족의 합집합 $\displaystyle \bigcup \mathcal{F} = \{ x : \text{어떤 } X \in \mathcal{F} \text{ 에 대해 } x \in X \}$가 존재한다.

$\displaystyle x \in \bigcup \mathcal{F}$이면

$x \in X$인 $X \in \mathcal{F}$가 존재하여 $X = a \times B$인 $a \in A$가 존재하고 $x = (a,b) \in a\times B = X$인 $b \in B$가 존재하므로

$A,B$의 데카르트곱 $\displaystyle \bigcup \mathcal{F} = A \times B$가 존재한다.

 

 

 

정리6

임의의 집합 $A,B,C$에 대해 다음이 성립한다.

1. $A = \emptyset $이거나 $B = \emptyset$이기 위한 필요충분조건은 $A \times B = \emptyset$인 것이다.

2. 임의의 $n,m \in \mathbb{Z}^+$에 대해 $\mathbb{Z}_{n\cdot m} = \{ 0,1,2,\cdots, n\cdot m-1 \}$과 $\mathbb{Z}_n \times \mathbb{Z}_m$사이의 전단사함수가 존재한다.

3. 임의의 $n,m \in \mathbb{Z}^+$에 대해 $\mathbb{N}_{n\cdot m} = \{1,2,\cdots, n\cdot m\}$과 $\mathbb{N}_n \times \mathbb{N}_m$사이의 전단사함수가 존재한다.

4. $A,B$가 각각 $n, m \in $ $\mathbb{N}$개의 원소를 가지는 유한집합이면 $A \times B$는 $n\cdot m$개의 원소를 갖는 유한집합이다.

5. $A \times (B\times C)$와 $(A\times B) \times C$사이의 전단사함수가 존재한다.

6. $A \times (B \cap C) = (A\times B) \cap (A \times C)$이고 $(A\cap B )\times C = (A\times C) \cap (B \times C)$이다.

7. $A \times (B \cup C) = (A\times B) \cup (A \times C)$이고 $(A\cup B )\times C = (A\times C) \cup (B \times C)$이다.

8. $A \times (B \setminus C) = (A\times B) \setminus (A \times C)$이고 $(A \setminus B) \times C = (A\times C) \setminus (B \times C)$이다.

증명

1.

일반성을 잃지 않고 $A = \emptyset $이라고 가정할때

데카르트곱의 정의로 $x \in A \times B$이기 위한 필요충분조건은 $x = (a,b)$인 $a \in A$와 $b \in B$가 존재해야 하는데

$a \in A = \emptyset$인 $a$가 존재하지 않으므로 $x \in A \times B$는 존재하지 않고 $A\times B = \emptyset \times B = \emptyset$이다.

역은 대우로 증명한다.

$A \ne \emptyset $이고 $B \ne \emptyset$이면 위 정리로 $a \in A$와 $b \in B$가 존재하여

$(a,b) \in A\times B$이므로 다시 위 정리로 $A \times B \ne \emptyset$이다.

2.

$0\le x \le n-1$이고 $0\le y \le m-1$이면

$ 0= n\cdot 0 \le n\cdot y \le n\cdot (m-1) $이고 $  0  \le n\cdot y +x \le n\cdot (m-1) + (n-1) = n \cdot m-1 $이므로

모든 $(x,y) \in \mathbb{Z}_{n} \times \mathbb{Z}_m$에 대해 $h(x,y) = n \cdot y + x$인 함수 $h : \mathbb{Z}_n \times \mathbb{Z}_m \to \mathbb{Z}_{n\cdot m}$를 정의한다.

$h$가 단사임을 보이기 위해 임의의 $(x_1, y_1) , (x_2,y_2) \in \mathbb{Z}_n \times \mathbb{Z}_m$가 $(x_1, y_1) \ne (x_2,y_2)$라고 가정하면

$x_1 < x_2$일때 $y_1 < y_2$ 또는 $y_1 = y_2$ 또는 $y_1 > y_2$이고

$x_1 = x_2$일때 $y_1 < y_2$ 또는 $y_1 > y_2$이고

$x_1 > x_2$일때 $y_1 < y_2$ 또는 $y_1 = y_2$ 또는 $y_1 > y_2$이다.

$x_1 < x_2$일때

$n = 1$이면 $x_1,x_2 \in \mathbb{Z}_1 = \{ 0 \}$이고 $x_1= x_2$가 되어 모순이므로 $1< n$이다.

$y_1 \le y_2$이면

$ x_1 -x_2  < 0 \le y_2 - y_1 \le n\cdot (y_2 - y_1) $이므로

$h(x_1,y_1) =  n\cdot y_1 + x_1 <  n\cdot y_2+ x_2 = h(x_2,y_2)$이다.

$y_2 < y_1$이면

$-n < -(n -1) \le x_2 - x_1 \le n-1 < n$이고 $ x_2 - x_1 < n \le n\cdot (y_1 - y_2)$이므로

$h(x_2,y_2) =  n\cdot y_2 + x_2 <  n\cdot y_1 + x_1 = h(x_1,y_1)$이다.

$x_1 = x_2$일때

$y_1 < y_2$이면

$ n\cdot y_1 <  n\cdot y_2$이므로 $h(x_1,y_1) =  n\cdot y_1  + x_1 <  n\cdot y_2 + x_2 = h(x_2,y_2)$이고

$y_2 < y_1$이면

$ n\cdot y_2  <  n\cdot y_1 $이므로 $h(x_2,y_2) =  n\cdot y_2 + x_2 <  n\cdot y_1 + x_1 = h(x_1,y_1)$이다.

$x_1 > x_2$일때는 $x_1 < x_2$일때와 비슷하게 증명되므로

$(x_1, y_1) \ne (x_2,y_2)$인 모든 $(x_1, y_1) , (x_2,y_2) \in \mathbb{Z}_n \times \mathbb{Z}_m$에 대해 $h(x_1,y_1) \ne  h(x_2,y_2)$가 되어 $h$는 단사이다.

$h$가 전사임을 보이기 위해 임의의 $k \in \mathbb{Z}_{n\cdot m}$에 대해 나눗셈 정리로 사용하면

$0\le k \le n\cdot m - 1$인 $k$는 $k = n\cdot q +r$이고 $0\le r \le n-1$인 $q,r \in \mathbb{Z}$이 존재한다.

$q < 0$이라 가정하면

$q \le -1$이고 $n\cdot q \le n \cdot (-1) = -n $이므로 $k = n\cdot q +r  \le -n +n-1 = -1 $이 되어 모순이고 $0\le q$이다.

$m  \le q$이라 가정하면

$k \le n\cdot m - 1 < n\cdot m \le n\cdot q$이므로 $k\le n\cdot m -1 < n\cdot q + r = k$가 되어 모순이고 $q < m $이다.

$0\le q \le m -1$이고 $0\le r \le n-1$이므로 모든 $k \in \mathbb{Z}_{n\cdot m}$에 대해

$k = n\cdot q + r = h(r, q)$인 $(r,q) \in \mathbb{Z}_{n} \times \mathbb{Z}_m$가 존재하여 $h$는 전사이다.

따라서 $h : \mathbb{Z}_n \times \mathbb{Z}_m \to \mathbb{Z}_{n\cdot m}$는 전단사이고 함수 정리로 역함수 $h^{-1} : \mathbb{Z}_{n\cdot m} \to \mathbb{Z}_n \times \mathbb{Z}_m$도 전단사이므로

$\mathbb{Z}_{n\cdot m}$과 $\mathbb{Z}_n \times \mathbb{Z}_m$사이의 전단사함수가 존재한다.

3.

2번으로 모든 $(x,y) \in \mathbb{Z}_{n} \times \mathbb{Z}_m$에 대해 $h(x,y) = n \cdot y + x$인 함수 $h : \mathbb{Z}_n \times \mathbb{Z}_m \to \mathbb{Z}_{n\cdot m}$는 전단사이므로

모든 $(u,v) \in \mathbb{N}_n \times \mathbb{N}_m$에 대해

$f(u,v) = h(u-1,v-1) +1 = (v-1)\cdot n + (u-1) +1 = (v-1)\cdot n + u$인 함수 $f : \mathbb{N}_n \times \mathbb{N}_m \to \mathbb{N}_{n\cdot m}$는

임의의 $(u_1,v_1),(u_2,v_2) \in \mathbb{N}_n \times \mathbb{N}_m$에 대해 $f(u_1,v_1) = f(u_2,v_2)$이면

$h(u_1-1,v_1-1) +1 =f(u_1,v_1) = f(u_2,v_2) = h(u_2-1,v_2-1) +1$이므로

$h(u_1-1,v_1-1) = h(u_2-1,v_2-1) $가 되어 $h$가 단사임에 따라 $u_1 -1 = u_2 -1$이고 $v_1 -1 = v_2-1$이므로

$u_1  = u_2 $와 $v_1 = v_2$가 성립하여 $(u_1,v_1) = (u_2,v_2) $이고 $f$는 단사이다.

또 모든 $k \in \mathbb{Z}_{n\cdot m}$에 대해 $h(x,y) = k$인 $(x,y) \in \mathbb{Z}_n \times \mathbb{Z}_m$가 존재하여

모든 $k +1 \in \mathbb{N}_{n\cdot m}$에 대해 $f(x+1,y+1) = h(x,y) +1 = k+1$인 $(x+1,y+1) \in \mathbb{N}_n \times \mathbb{N}_m$이 존재하므로

$f$는 전사가 되어 $f$는 전단사이고 함수 정리로 역함수 $f^{-1} : \mathbb{N}_{n\cdot m} \to \mathbb{N}_n \times \mathbb{N}_m$도 전단사이므로

$\mathbb{N}_{n\cdot m}$과 $\mathbb{N}_n \times \mathbb{N}_m$사이의 전단사함수가 존재한다.

4.

$n = 0$ 또는 $m  = 0$이면

유한집합의 정의로 $A =\emptyset$ 또는 $B =\emptyset$이므로 1번으로 $A \times B = \emptyset$이 되어

유한집합의 정의로 $A \times B$는 $n\cdot m = 0$개의 원소를 갖는다.

$n \ge 1$ 이고 $m  \ge 1$일때

$A$와 $B$가 각각 $n,m$개의 원소를 갖는 유한집합이므로 전단사함수 $f : \mathbb{Z}_n \to A$와 $g : \mathbb{Z}_m \to B$가 존재한다.

모든 $(x,y) \in \mathbb{Z}_n \times \mathbb{Z}_m$에 대해 $h(x,y) = (f(x),g(y))$인 함수 $h : \mathbb{Z}_n \times \mathbb{Z}_m \to A\times B$를 정의할때

모든 $(x_1,y_1), (x_2,y_2) \in \mathbb{Z}_n \times \mathbb{Z}_m$에 대해 $(f(x_1),g(y_1)) = h(x_1,y_1) = h(x_2,y_2) = (f(x_2),g(y_2))$이면

$f(x_1) = f(x_2)$이고 $g(y_1) = g(y_2)$이므로 $f,g$가 단사임에 따라 $x_1 = x_2$이고 $y_1 = y_2$가 되어

$(x_1,y_1) = (x_2,y_2)$이므로 $h$는 단사이다.

또 모든 $(a,b) \in A\times B$에 대해

$f,g$가 전사임에 따라 $h(x,y) =(f(x),g(y)) = (a,b)$인 $(x,y) \in \mathbb{Z}_n \times \mathbb{Z}_m$가 존재하므로 $h$는 전사이다.

따라서 $h$는 전단사이고 2번으로 전단사함수 $\phi : \mathbb{Z}_{n\cdot m} \to \mathbb{Z}_n \times \mathbb{Z}_m$가 존재하므로

함수정리로 $h \circ \phi : \mathbb{Z}_{n\cdot m} \to A\times B$는 전단사가 되어 유한집합의 정의로 $A \times B$는 $n\cdot m$개의 원소를 갖는다.

5.

임의의 $a \in A$와 $b \in B$와 $c \in C$에 대해

$f( \, (a,(b,c))\,) = ((a,b), c)$인 함수 $f : A \times(B\times C) \to (A\times B) \times C$를 정의한다.

$f$가 단사임을 보이기 위해

임의의 $(a_1,(b_1,c_1)) , (a_2,(b_2,c_2)) \in A \times(B\times C) $가 $(a_1,(b_1,c_1)) \ne (a_2,(b_2,c_2))$라고 가정하면

$a_1 \ne a_2$일때 $(b_1,c_1) \ne (b_2,c_2)$ 또는 $(b_1,c_1) = (b_2,c_2)$이고

$a_1 = a_2$일때 $(b_1,c_1) \ne (b_2,c_2)$이다.

$a_1 \ne a_2$일때

$(a_1, b_1) \ne (a_2, b_2)$이므로 $f(\; (a_1 , (b_1,c_1) ) \,) = ((a_1, b_1) ,c_1)\ne ((a_2, b_2), c_2) = f(\, (a_2,(b_2,c_2)) \,)$이다.

$a_1 = a_2$일때

$(b_1,c_1) \ne (b_2,c_2)$이므로 $b_1 \ne b_2$ 또는 $c_1 \ne c_2$가 되어

$b_1 \ne b_2$이면 $(a_1, b_1) \ne (a_2, b_2)$이고

$c_1 \ne c_2$이면 $ ((a_1, b_1) ,c_1)\ne ((a_2, b_2), c_2)$이므로

$f(\; (a_1 , (b_1,c_1) ) \,) = ((a_1, b_1) ,c_1)\ne ((a_2, b_2), c_2) = f(\, (a_2,(b_2,c_2)) \,)$이다.

$(a_1,(b_1,c_1)) \ne (a_2,(b_2,c_2))$인 모든 $(a_1,(b_1,c_1)) , (a_2,(b_2,c_2)) \in A \times(B\times C) $에 대해

$f(\; (a_1 , (b_1,c_1) ) \,) \ne  f(\, (a_2,(b_2,c_2)) \,)$이므로 $f$는 단사이다.

또 모든 $ ((a,b), c) \in (A\times B) \times C$에 대해

$f( \, (a,(b,c))\,) = ((a,b), c)$인 $(a,(b,c)) \in A \times (B\times C)$가 존재하므로 $f$는 전사이다.

따라서 $f : A \times(B\times C) \to (A\times B) \times C$는 전단사이고

함수 정리로 역함수 $f^{-1} : (A\times B) \times C \to A \times(B\times C)$도 전단사이므로

$A \times (B\times C)$와 $(A\times B) \times C$사이의 전단사함수가 존재한다.

6.

$(a,x) \in A \times (B \cap C)$이면 

데카르트곱의 정의로 $a \in A$이고 $x \in B\cap C$이므로 교집합의 정의로 $(a,x) \in A \times B$이고 $(a,x) \in A\times C$가 되어

$(a,x) \in (A\times B) \cap (A \times C)$이므로 $A \times (B \cap C) \subseteq (A\times B) \cap (A \times C)$이다.

$(a,x) \in (A\times B) \cap (A \times C)$이면

교집합의 정의로 $(a,x) \in A \times B$이고 $(a,x) \in A\times C$이므로 데카르트곱의 정의로 $a \in A$이고 $x \in B\cap C$가 되어

$(a,x) \in A \times (B \cap C)$이므로 $ (A\times B) \cap (A \times C) \subseteq A\times (B \cap C)$이다.

따라서 위 정리로 $A \times (B \cap C)=(A\times B) \cap (A \times C)$이다.

$(x,c) \in (A \cap B) \times C$이면

데카르트곱의 정의로 $x \in A \cap B$이고 $c \in C$이므로 교집합의 정의로 $(x,c) \in A\times C$이고 $(x,c) \in B \times C$가 되어

$(x,c) \in (A\times C) \cap (B \times C)$이므로 $(A\cap B )\times C \subseteq (A\times C) \cap (B \times C)$이다.

$(x,c) \in (A\times C) \cap (B \times C)$이면

교집합의 정의로 $(x,c) \in A\times C$이고 $(x,c) \in B \times C$이므로 데카르트곱의 정의로 $x\in A \cap B$이고 $c \in C$가 되어

$(x,c) \in (A\cap B) \times C$이므로 $(A\times C) \cap (B \times C) \subseteq (A \cap B) \times C$이다.

따라서 위 정리로 $(A\cap B )\times C = (A\times C) \cap (B \times C)$이다.

7.

$(a,x) \in A \times (B \cup C)$이면 

데카르트곱의 정의로 $a \in A$이고 $x \in B\cup C$이므로 합집합의 정의로 $(a,x) \in A \times B$ 또는 $(a,x) \in A\times C$가 되어

$(a,x) \in (A\times B) \cup (A \times C)$이므로 $A \times (B \cup C) \subseteq (A\times B) \cup (A \times C)$이다.

$(a,x) \in (A\times B) \cup (A \times C)$이면

합집합의 정의로 $(a,x) \in A \times B$ 또는 $(a,x) \in A\times C$이므로 데카르트곱의 정의로 $a \in A$이고 $x \in B\cup C$가 되어

$(a,x) \in A \times (B \cup C)$이므로 $ (A\times B) \cup (A \times C) \subseteq A\times (B \cup C)$이다.

따라서 위 정리로 $A \times (B \cup C)=(A\times B) \cup (A \times C)$이다.

$(x,c) \in (A \cup B) \times C$이면

데카르트곱의 정의로 $x \in A \cup B$이고 $c \in C$이므로 합집합의 정의로 $(x,c) \in A\times C$ 또는 $(x,c) \in B \times C$가 되어

$(x,c) \in (A\times C) \cup (B \times C)$이므로 $(A\cup B )\times C \subseteq (A\times C) \cup (B \times C)$이다.

$(x,c) \in (A\times C) \cup (B \times C)$이면

합집합의 정의로 $(x,c) \in A\times C$ 또는 $(x,c) \in B \times C$이므로 데카르트곱의 정의로 $x\in A \cup B$이고 $c \in C$가 되어

$(x,c) \in (A\cup B) \times C$이므로 $(A\times C) \cup (B \times C) \subseteq (A \cup B) \times C$이다.

따라서 위 정리로 $(A\cup B )\times C = (A\times C) \cup (B \times C)$이다.

8.

$(a,x) \in A \times (B \setminus C)$이면 

데카르트곱의 정의로 $a \in A$이고 $x \in B\setminus C$이므로 여집합의 정의로 $(a,x) \in A \times B$이고 $(a,x) \notin A\times C$가 되어

$(a,x) \in (A\times B) \setminus (A \times C)$이므로 $A \times (B \setminus C) \subseteq (A\times B) \setminus (A \times C)$이다.

$(a,x) \in (A\times B) \setminus (A \times C)$이면

여집합의 정의로 $(a,x) \in A \times B$이고 $(a,x) \notin A\times C$이므로 데카르트곱의 정의로 $a \in A$이고 $x \in B\setminus C$가 되어

$(a,x) \in A \times (B \setminus C)$이므로 $ (A\times B) \setminus (A \times C) \subseteq A\times (B \setminus C)$이다.

따라서 위 정리로 $A \times (B \setminus C)=(A\times B) \setminus (A \times C)$이다.

$(x,c) \in (A \setminus B) \times C$이면

데카르트곱의 정의로 $x \in A \setminus B$이고 $c \in C$이므로 여집합의 정의로 $(x,c) \in A\times C$이고 $(x,c) \notin B \times C$가 되어

$(x,c) \in (A\times C) \setminus (B \times C)$이므로 $(A\setminus B )\times C \subseteq (A\times C) \setminus (B \times C)$이다.

$(x,c) \in (A\times C) \setminus (B \times C)$이면

여집합의 정의로 $(x,c) \in A\times C$이고 $(x,c) \notin B \times C$이므로 데카르트곱의 정의로 $x\in A \setminus B$이고 $c \in C$가 되어

$(x,c) \in (A\setminus B) \times C$이므로 $(A\times C) \setminus (B \times C) \subseteq (A \setminus B) \times C$이다.

따라서 위 정리로 $(A\setminus B )\times C = (A\times C) \setminus (B \times C)$이다.

 

 

 

정의5

$n$-순서쌍(n-tuple) :

$n\ge 2$인 임의의 양의 정수 $n \in \mathbb{Z}^+$과 임의의 $a_{1},a_{2}, \cdots ,a_{n},a_{n+1}$에 대해

$2$-순서쌍을 순서쌍 $(a_1,a_2)$로 정의하고

$n$-순서쌍이 $(a_1,a_2,\cdots, a_n)$으로 귀납적으로 정의될때

$n+1$-순서쌍을 $(a_1,a_2,\cdots, a_n)$와 $a_{n+1}$의 순서쌍 

$(a_1,a_2,\cdots, a_n, a_{n+1})= ((a_1,a_2,\cdots, a_n),a_{n+1})$로 정의한다.

$a_{1},a_{2}, \cdots ,a_{n}$을 $n$-순서쌍 $(a_{1},a_{2}, \cdots ,a_{n})$의 성분(component)으로 정의한다.

$a_{1},a_{2}, \cdots ,a_{n}$에 대해 $1$-순서쌍은 $(a_1)= a_1$로 정의한다.

$n$-데카르트곱 :

$n\ge 2$인 임의의 양의 정수 $n \in \mathbb{Z}^+$과 임의의 집합 $ A_1, A_2, \cdots, A_n,A_{n+1}$에 대해

$2$-데카르트곱을 데카르트곱 $A_1\times A_2$로 정의하고

$n$-데카르트곱이 $A_1\times A_2 \times \cdots \times A_n$으로 귀납적으로 정의될때

$n+1$-데카르트곱을 $A_1\times A_2 \times \cdots \times A_n$와 $A_{n+1}$의 데카르트곱 

$A_1\times A_2 \times \cdots A_n \times A_{n+1}= (A_1\times A_2 \times \cdots \times A_n)\times A_{n+1}$로 정의한다.

$n$-데카르트곱을

$\displaystyle A_1 \times A_2 \times \cdots \times A_n =  \prod_{i= 1}^n A_i = \{ (a_1, a_2, \cdots, a_n) : \text{ 모든 } i = 1,2,\cdots , n \text{ 에 대해 } a_i \in A_i \}$로 표기할 수 있고

$x \in A_1\times  \cdots \times A_n$이기 위한 필요충분조건은 모든 $i \in I$에 대해 $a_i \in A_i$가 존재하여 $x = (a_1,\cdots, a_n)$인 것이다.

$ A_1, A_2, \cdots, A_n$에 대해 $1$-데카르트곱은 $\displaystyle \prod_{i = 1}^1 A_i = A_1$로 정의한다.

$n$-데카르트곱의 거듭제곱 :

$A_1 = A_2 =  \cdots = A_n = A$일때 $A^n = A_1\times A_2 \times \cdots \times A_n$을 $A$의 $n$-데카르트곱으로 정의하고

$x \in A^n$이기 위한 필요충분조건은 모든 $i \in I$에 대해 $a_i \in A$가 존재하여 $x = (a_1,a_2,\cdots, a_n)$인 것이다.

$A$의 $1$-데카르트곱은 $A^1 = A$로 정의한다.

 

 

 

정리11

$n\ge 2$인 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해 다음이 성립한다.

$n$-순서쌍의 존재성 :

임의의 $a_{1},a_{2}, \cdots ,a_{n}$에 대해 $n$-순서쌍 $(a_1,a_2,\cdots,a_n)$이 존재한다.

$n$-순서쌍의 상등 :

$(a_1,a_2,\cdots,a_n) = (b_1,b_2,\cdots, b_n)$이기 위한 필요충분조건은 $1 \le i\le n$인 모든 $i \in \mathbb{Z}^+$에 대해 $a_i = b_i$인 것이다.

$n$-데카르트곱의 존재성 :

임의의 집합 $ A_1, A_2, \cdots, A_n$에 대해 $n$-데카르트곱 $A_1\times A_2 \times \cdots \times A_n$이 존재한다.

$n$-데카르트곱의 유한선택 :

임의의 집합 $ A_1, A_2, \cdots, A_n$에 대해

$A_i =\emptyset$인 $i \in \mathbb{Z}^+$가 존재하기 위한 필요충분조건은 $A_1\times A_2 \times \cdots \times A_n = \emptyset$인 것이다.

$n$-데카르트곱의 원소개수 :

유한집합 $A_1,A_2, \cdots, A_m$이 각각 $n_1, n_2, \cdots, n_m \in $ $\mathbb{N}$개의 원소를 가지면

$A_1\times A_2 \times \cdots \times A_m$은 $n_1\cdot n_2 \cdot \; \cdots \; \cdot n_m$개의 원소를 갖는 유한집합이다.

증명

$n$-순서쌍의 존재성

$n\ge 2$인 $n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 2$일때 $2$-순서쌍은 순서쌍이므로 위 정리로 $2$-순서쌍이 존재한다.

$k\ge 2$인 모든 $k \in \mathbb{Z}^+$에 대해 $(a_1,a_2,\cdots,a_k)$가 존재하면 

$k+1$-순서쌍은 $(a_1,a_2,\cdots,a_k)$와 $a_{k+1}$의 순서쌍이므로

위 정리로 $(a_1,a_2,\cdots, a_k, a_{k+1})= ((a_1,a_2,\cdots, a_k),a_{k+1})$이 존재한다.

따라서 $n\ge 2$인 모든 $n \in \mathbb{Z}^+$에 대해 정리가 성립한다.

$n$-순서쌍의 상등

$n\ge 2$인 $n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 2$일때

$2$-순서쌍은 순서쌍이므로 위 정리로 $(a_1,a_2) = (b_1,b_2)$이기 위한 필요충분조건은 $a_1= b_1$이고 $a_2 =b_2$인 것이다.

$k\ge 2$인 모든 $k \in \mathbb{Z}^+$에 대해 정리가 성립할때

$(a_1,a_2,\cdots, a_k, a_{k+1})$은 $(a_1,a_2,\cdots,a_k)$와 $a_{k+1}$의 순서쌍이고

$(b_1,b_2,\cdots, b_k, b_{k+1})$은 $(b_1,b_2,\cdots,b_k)$와 $b_{k+1}$의 순서쌍이므로

귀납가정으로 

$(a_1,a_2,\cdots,a_k) = (b_1,b_2,\cdots, b_k)$이기 위한 필요충분조건은 $1\le i\le k$인 모든 $i \in \mathbb{Z}^+$에 대해 $a_i = b_i$인 것이고

위 정리로 $((a_1,a_2,\cdots,a_k),a_{k+1}) = ((b_1,b_2,\cdots, b_k),b_{k+1})$ 이기 위한 필요충분조건은

$(a_1,a_2,\cdots,a_k) = (b_1,b_2,\cdots, b_k)$이고 $a_{k+1} =b_{k+1}$인 것이므로

$(a_1,a_2,\cdots,a_k,a_{k+1}) = (b_1,b_2,\cdots, b_k,b_{k+1})$이기 위한 필요충분조건은

$1\le i\le k+1$인 모든 $i \in \mathbb{Z}^+$에 대해 $a_i = b_i$인 것이다.

따라서 $n\ge 2$인 모든 $n \in \mathbb{Z}^+$에 대해 정리가 성립한다.

$n$-데카르트곱의 존재성

$n\ge 2$인 $n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 2$일때 $2$-데카르트곱은 데카르트곱이므로 위 정리로 $2$-데카르트곱이 존재한다.

$k\ge 2$인 모든 $k \in \mathbb{Z}^+$에 대해 $A_1\times A_2 \times \cdots A_k$가 존재하면 

$k+1$-데카르트곱은 $A_1\times A_2 \times \cdots \times A_k$와 $A_{k+1}$의 데카르트곱이므로

위 정리로 $A_1\times A_2 \times \cdots A_k \times A_{k+1}= (A_1\times A_2 \times \cdots \times A_k)\times A_{k+1}$이 존재한다.

따라서 $n\ge 2$인 모든 $n \in \mathbb{Z}^+$에 대해 정리가 성립한다.

$n$-데카르트곱의 유한선택

$n\ge 2$인 $n \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$n = 2$일때 $2$-데카르트곱은 데카르트곱이므로 위 정리로 성립한다.

$k \ge 2$인 모든 $k \in \mathbb{Z}^+$에 대해 정리가 성립한다 가정하고

$A_1, A_2, \cdots, A_k,A_{k+1}$에 대해 $A_i =\emptyset$이고 $1\le i \le k+1$인 $i \in \mathbb{Z}^+$가 존재할때

$k+1$-데카르트곱은 $A_1\times A_2 \times \cdots \times A_k$와 $A_{k+1}$의 데카르트곱이므로

$1 \le i \le k$이면 귀납가정으로 $A_1\times A_2 \times \cdots \times A_k =\emptyset$이고 $i = k+1$이면 $A_{k+1} = \emptyset$이 되어

위 정리로 $A_1\times A_2 \times \cdots \times A_k \times A_{k+1}= (A_1\times A_2 \times \cdots \times A_k)\times A_{k+1} =\emptyset$이다.

역으로 $(A_1\times A_2 \times \cdots \times A_k) \times A_{k+1}= A_1\times A_2 \times \cdots \times A_k\times A_{k+1} =\emptyset$이면

위 정리로 $A_1\times A_2 \times \cdots \times A_k =\emptyset$이거나 $A_{k+1} = \emptyset$이므로

귀납가정과 위 정리로 $A_i =\emptyset$이고 $1\le i \le k+1$인 $i \in \mathbb{Z}^+$가 존재한다.

따라서 $n\ge 2$인 모든 $n \in \mathbb{Z}^+$에 대해 정리가 성립한다.

$n$-데카르트곱의 원소개수

$m\ge 2$인 $m \in \mathbb{Z}^+$에 대한 귀납법을 사용한다.

$m = 2$일땐 $2$-데카르트곱은 데카르트곱이므로 위 정리로 성립한다.

$k \ge 2$인 모든 $k \in \mathbb{Z}^+$에 대해

$A_1\times A_2 \times \cdots \times A_k$가 $n_1\cdot n_2 \cdot \; \cdots \; \cdot n_k$개의 원소를 갖는다고 가정하면

$k+1$-데카르트곱은 $A_1\times A_2 \times \cdots \times A_k$와 $A_{k+1}$의 데카르트곱이므로

위 정리와 귀납가정으로

$A_1\times A_2 \times \cdots \times A_k \times A_{k+1}= (A_1\times A_2 \times \cdots \times A_k)\times A_{k+1}$은 $n_1\cdot n_2 \cdot \; \cdots \; \cdot n_k \cdot n_{k+1}$개의 원소를 가지므로

$m\ge 2$인 모든 $m \in \mathbb{Z}^+$에 대해 정리가 성립한다.

 

 

 

정의7

선택공리(choice axiom) :

모든 $i \in I$에 대응되는 집합 $A_i$가 유일하게 존재하여

색인집합 $I$에 대해 색인된 집합족이 $\mathcal{F}_I = \{ A_i : i \in I \}$일때

모든 $i \in I$에 대해 $A_i \ne \emptyset$이면 $f(i) = x_i \in A_i$인 함수 $f : I \to \displaystyle \bigcup_{i \in I} A_i$가 존재한다.

이때 $f$를 선택함수(choice function)라고 정의한다.

ZFC 공리계(Zermelo–Fraenkel set theory with the axiom of choice) :

집합이 ZF공리계와 선택공리를 만족하는 공리적 집합론을 ZFC 공리계라고 한다.

 

 

 

정리13

임의의 집합이 $X,Y$이고 $x\in X$와 $y \in Y$에 대한 명제함수가 $P$일때 다음이 성립한다.

1. 모든 $x \in X$에 대해 $P(x,y)$가 참이 되는 $y \in Y$가 존재하면

모든 $x \in X$에 대해 $P(x,f(x))$가 참이 되는 함수 $f :X\to Y$가 존재한다.

2. 어떤 $x \in X$에 대해 $P(x,y)$가 참이 되는 $y \in Y$가 존재하면

$P(x,f(x))$가 참이 되는 함수 $f :\{ x\}\to Y$가 존재한다.

증명

1.

임의의 $x \in X$에 대해

분류공리로 $Y_x = \{ y\in Y : P(x,y) \equiv \mathbf{T} \}$인 집합이 유일하게 존재하고 가정으로 $Y_x$는 공집합이 아니다.

따라서 선택공리로 $g(x) = y_x \in Y_x$인 선택함수 $g: X\to \displaystyle \bigcup_{x \in X}Y_x$가 존재하고 $ \displaystyle \bigcup_{x \in X}Y_x\subseteq Y$이므로

모든 $x \in X$에 대해 $f(x) = g(x)$인 함수 $f :X\to Y$를 정의하면

모든 $x \in X$에 대해 $P(x,f(x))$가 참이 되는 함수 $f :X\to Y$가 존재한다.

2.

위 정리로 $x\in X$에 대해 단일 원소집합 $\{x\}$가 존재하므로 $P(x,y)$가 참이 되는 $y \in Y$가 존재하면

모든 $x \in \{ x\}$에 대해 $P(x,y)$가 참이 되는 $y \in Y$가 존재하여 1번으로 함수 $f :\{ x\}\to Y$가 존재한다.

 

 

 

정의8

일반 데카르트곱(generalized cartesian product) :

임의의 집합 $I$의 모든 $i \in I$마다 유일한 집합 $A_i$가 존재할때 

$\displaystyle \prod_{i \in I} A_i = \{ f \in \mathcal{P}(I \times \bigcup_{i \in I} A_i) :\text{ 모든 } i \in I \text{에 대해 } f(i) \in A_i \text{인 함수 } f : I \to \bigcup_{i \in I}A_i  \}$인 집합을

일반 데카르트곱으로 정의한다.

$\displaystyle x\in \prod_{i \in I} A_i $이기 위한 필요충분조건은 모든 $i \in I$에 대해 $x(i) \in A_i$인 함수 $x : I \to \displaystyle \bigcup_{i \in I} A_i$가 존재하는 것이다.

무한 데카르트곱(infinite cartesian product) :

$I$가 무한집합이면 일반 데카르트곱 $\displaystyle \prod_{i \in I} A_i$를 무한 데카르트곱으로 정의한다.

 

 

 

정리12

임의의 집합 $I$의 모든 $i \in I$마다 유일한 집합 $A_i$가 존재할때 다음이 성립한다.

일반 데카르트곱의 존재성 : 

일반 데카르트곱 $\displaystyle \prod_{i \in I} A_i$가 존재한다.

$n$-데카르트곱과 일반 데카르트곱의 관계 :

$n\ge 2$인 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해 $I = \{ i \in \mathbb{Z}^+ : 1 \le i \le n \}$일때

일반 데카르트곱 $\displaystyle \prod_{i \in I} A_i$와 $n$-데카르트곱 $\displaystyle \prod_{i = 1}^{n} A_i = A_1 \times A_2 \times \cdots \times A_n$사이의 전단사함수가 존재한다.

일반 데카르트곱의 선택 :

$A_i =\emptyset$인 $i \in I$가 존재하기 위한 필요충분조건은 $\displaystyle \prod_{i \in I} A_i =\emptyset$인 것이다.

증명

일반 데카르트곱의 존재성

모든 $i \in I$마다 유일한 집합 $A_i$가 존재하므로 $I$는 색인집합이고

위 정리로 $I$에 대해 색인된 집합족 $\mathcal{F}_I$가 존재하여 $\mathcal{F}_I$의 합집합 $\displaystyle \bigcup \mathcal{F}_I = \bigcup_{i \in I} A_i$가 존재한다.

따라서 위 정리로 데카르트곱 $\displaystyle I \times \bigcup_{i \in I} A_i$가 존재하여 멱집합 공리로 $\displaystyle \mathcal{P}(I \times \bigcup_{i \in I} A_i)$가 존재하고

분류 공리로 $I$에서 $\displaystyle \bigcup_{i \in I} A_i$로의 함수들의 집합

$\displaystyle \prod_{i \in I} A_i = \{ f \in \mathcal{P}(I \times \bigcup_{i \in I} A_i) :\text{ 모든 } i \in I \text{에 대해 } f(i) \in A_i \text{인 함수 } f : I \to \bigcup_{i \in I}A_i  \}$이 존재하여

$\displaystyle \prod_{i \in I} A_i$는 일반 데카르트곱이다.

$n$-데카르트곱과 일반 데카르트곱의 관계

일반 데카르트곱의 정의와 색인된 집합족의 정의로

$\displaystyle x \in \prod_{i \in I} A_i $이면 모든 $i \in I$에 대해 $x(i) \in A_i$인 함수 $x : I \to \displaystyle \bigcup_{i =1}^n A_i$가 존재하므로

$F(x) = (x(1),x(2),\cdots, x(n)) \in A_1 \times A_2 \times \cdots \times A_n$인 함수 $\displaystyle F : \prod_{i \in I}A_i \to A_1\times A_2\times \cdots \times A_n$를 정의한다.

$F$가 단사임을 보이기 위해

임의의 $\displaystyle x,y \in \prod_{i \in I} A_i $에 대해 $(x(1),x(2),\cdots, x(n)) = F(x) = F(y) = (y(1),y(2),\cdots, y(n))$을 가정하면

$n$-순서쌍의 상등으로 모든 $i \in I$에 대해 $x(i) = y(i)$이므로 함수의 상등으로 $x =y$이고 $F$는 단사이다.

또 임의의 $(a_1,a_2,\cdots, a_n) \in A_1 \times A_2 \times \cdots \times A_n$에 대해 $x(i) = a_i \in A_i$인 함수 $x : I \to \displaystyle \bigcup_{i =1}^n A_i$를 정의하면 

$\displaystyle x \in \prod_{i \in I} A_i $이고 $F(x) = (x(1),x(2),\cdots, x(n)) = (a_1,a_2,\cdots, a_n)$이므로 $F$는 전사이다.

따라서 $\displaystyle F : \prod_{i \in I}A_i \to A_1\times A_2\times \cdots \times A_n$는 전단사이고

함수 정리로 역함수 $\displaystyle F^{-1} :  A_1\times A_2\times \cdots \times A_n \to \prod_{i \in I} A_i$도 전단사이므로

$\displaystyle \prod_{i \in I} A_i$와 $\displaystyle \prod_{i = 1}^{n} A_i = A_1 \times A_2 \times \cdots \times A_n$사이의 전단사함수가 존재한다.

일반 데카르트곱의 선택

$A_j =\emptyset$인 $j \in I$가 존재할때 $\displaystyle \prod_{i \in I} A_i \ne \emptyset$이라고 가정하면

일반 데카르트곱의 정의로 $\displaystyle x \in \prod_{i \in I} A_i$가 존재하여 모든 $i \in I$에 대해 $x(i) \in A_i$인데 $x(j) \in A_j = \emptyset$이므로 모순이다.

따라서 $A_j =\emptyset$인 $j \in I$가 존재하면 $\displaystyle \prod_{i \in I} A_i = \emptyset$이다.

역은 대우로 증명한다.

모든 $i \in I$에 대해 $A_i \ne \emptyset$이면 선택공리로 $f(i) = x_i \in A_i$인 선택함수 $f : I \to \displaystyle \bigcup_{i \in I} A_i$가 존재하여

$\displaystyle f \in \prod_{i \in I} A_i$이므로 $\displaystyle \prod_{i \in I} A_i \ne \emptyset$이다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/4#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/4#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

Robert G. Bartle - Introduction to real analysis - 9788993543766

Fred H. Croom - Principles of Topology - 9791156646402

Terence Tao - Analysis 1 - 9791156646662

Herbert B. Enderton - Elements of Set Theory - 9780122384400

Peter J. Cameron - Sets, Logics and Categories - 9791196120375

You-Feng Lin - Set Theory : An Intuitive Approach - 9788961053778