유한집합(Finite set), 무한집합(Infinite set)

정의1

자연수집합 $\mathbb{N} = \{ 0,1,2,\cdots \}$의 어떤 원소 $n \in \mathbb{N}$에 대하여 

집합 $\mathbb{Z}_{n} =  \{ k \in \mathbb{N} : 0\le k < n \} = \{ 0,1,\cdots,n-1\}$에서 집합 $S$로의 전단사함수가 존재할때

$S$는 $n$개의 원소를 갖는다고 정의하고 $S$를 유한집합으로 정의한다.

$S$가 유한집합이 아니면 $S$를 무한집합으로 정의한다.

 

$\mathbb{Z}_0 = \emptyset $이고 공함수 정리로 $f: \mathbb{Z}_0 \to S$가 전단사이기 위한 필요충분조건은 $S = \emptyset$이므로

$S = \emptyset$이기 위한 필요충분조건은 $S$가 $0$개의 원소를 갖는 것이다.

 

 

 

정리1

$m>n$인 임의의 양의 정수 $m,n \in \mathbb{Z}^+$에 대해

$\mathbb{Z}_{m} = \left \{  0, 1, \; 2, \; \cdots , \; m -1 \right \}$에서 $\mathbb{Z}_{n}$으로의 단사함수는 존재하지 않는다

증명

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

$n = 1$일때

$m > 1$에 대해 $g : \mathbb{Z}_m \to \mathbb{Z}_1$는 함수이므로 $g(0) = g(1) = \cdots = g(m-1) = 0$이고 $g$는 단사가 아니다.

모든 $k \in \mathbb{Z}^+$에 대해 정리가 성립할때 $m > k+1$인 $h : \mathbb{Z}_m \to \mathbb{Z}_{k+1}$에 대해

$h(p) = k$인 $p \in \mathbb{Z}_m$가 존재하지 않으면

$h$에 의한 $\mathbb{Z}_m$의 상 $h(\mathbb{Z}_m)$에 대해 $h(\mathbb{Z}_m) \subseteq \mathbb{Z}_k \subset \mathbb{Z}_{k+1}$이므로 귀납가정에 의해 $h$는 단사가 아니다.

$h(p) = k$인 $p \in \mathbb{Z}_m$가 존재할때

$h(p_1) = k = h(p_2)$인 $p_1,p_2 \in \mathbb{Z}_m$가 $p_1 \ne p_2$이면 $h$는 단사가 아니다.

$h(p) = k$인 $p \in \mathbb{Z}_m$가 유일하면

모든 $q \in \mathbb{Z}_{m-1}$에 대해 $h_1(q) = \begin{cases} h(q) ,& q <p \text{ 일때} \\ h(q+1), &  p\le q  \text{ 일때} \end{cases}$인 함수 $h_1 : \mathbb{Z}_{m-1} \to \mathbb{Z}_k$은

$m > k+1$이므로 $m -1 > k$이고 귀납가정으로 $h_1$은 단사가 아니게 되어

$h_1(q_1) = h_1(q_2)$이고 $q_1\ne q_2$인 $q_1,q_2 \in \mathbb{Z}_{m-1}$가 존재한다.

$q_1<p$이고 $q_2<p$이면

$h(q_1)=h_1(q_1) = h_1(q_2) = h(q_2)$이고 $q_1\ne q_2$인 $q_1,q_2 \in \mathbb{Z}_{m-1} \subseteq \mathbb{Z}_{m}$가 존재한다.

$p\le q_1$이고 $p\le q_2$이면

$h(q_1+1)=h_1(q_1) = h_1(q_2) = h(q_2+1)$이고 $q_1+1\ne q_2 +1$인 $q_1+1,q_2+1 \in \mathbb{Z}_{m}$이 존재한다.

일반성을 잃지 않고 $q_1< p\le q_2$이면

$h(q_1)=h_1(q_1) = h_1(q_2) = h(q_2+1)$이고 $q_1< q_2 < q_2+1$인 $q_1,q_2+1 \in \mathbb{Z}_{m}$이 존재하여 $h$는 단사가 아니다.

따라서 모든 $n \in \mathbb{Z}^+$에 대해 $m>n$일때 $\mathbb{Z}_{m} $에서 $\mathbb{Z}_{n}$으로의 단사함수는 존재하지 않는다.

 

 

 

정리2(유일성 정리)

$S$가 유한집합이면 $S$의 원소개수는 자연수집합 $\mathbb{N}$에 속하는 유일한 수이다.

증명

$S $가 공집합일때

어떤 $k \in \mathbb{Z}^+$에 대해 $\mathbb{Z}_{k} = \left \{ 0, \; 1, \;2, \cdots , \; k -1 \right \}$에서 $S$로의 함수 $h : \mathbb{Z}_k \to S$가 존재하면

모든 $x \in \mathbb{Z}_k$에 대해 공집합 공리로 $h(x) \in \emptyset = S$가 존재하지 않으므로

$h$가 함수임에 모순이 되어 $S$는 $0 \in \mathbb{N}$개의 원소를 갖는 집합이다.

$S$가 공집합이 아닐때

$S$가 $m \in \mathbb{Z}^+$개의 원소를 갖는다면 위 정의로 전단사함수 $f : \mathbb{Z}_{m} \to S$가 존재하고

$S$가 $n \in \mathbb{Z}^+$개의 원소를 갖는다면 전단사함수 $g : \mathbb{Z}_{n} \to S$가 존재한다.

$f,g$가 전단사이므로 역함수 $f^{-1} : S \to \mathbb{Z}_{m}$와 $g^{-1} : S \to \mathbb{Z}_{n}$이 존재하고 함수정리로 전단사이다.

$m > n$이면 함수 정리로 $g^{-1} \circ f : \mathbb{Z}_{m} \to \mathbb{Z}_{n}$은 전단사이므로 위 정리에 모순이고

$n > m$일때도 마찬가지로 $f^{-1} \circ g : \mathbb{Z}_{n} \to \mathbb{Z}_{m}$은 전단사이고 위 정리에 모순이다.

따라서 $n = m \in \mathbb{Z}^+$으로 $S$의 원소개수는 유일하다.

 

 

 

정리3

$n \in $ $\mathbb{Z}^+$일때 자연수집합 $\mathbb{N}$에서 $\mathbb{Z}_{n} = \left \{  0, 1,  2, \cdots ,  n-1 \right \}$으로의 단사함수는 존재하지 않는다.

증명

$f : \mathbb{N} \to \mathbb{Z}_{n}$가 단사함수라고 가정하면

함수 정리로 $m>n$인 $m \in \mathbb{Z}^+$에 대해

정의역을 $\mathbb{Z}_{m} \subset \mathbb{N}$으로 축소한 함수 $f |_{\mathbb{Z}_{m}} : \mathbb{Z}_m \to \mathbb{Z}_n$도 단사이므로 위 정리에 모순이다.

따라서 $\mathbb{N}$에서 $\mathbb{Z}_{n}$으로의 단사함수는 존재하지 않는다.

 

 

 

정리4

자연수집합 $\mathbb{N}$은 무한집합이다.

증명

페아노 공리로 $0 \in \mathbb{N}$이므로 자연수 집합은 공집합이 아니다.

$\mathbb{N}$이 공집합이 아닌 유한집합이라고 가정하면

유일성 정리로 $f : \mathbb{Z}_{n} \to \mathbb{N}$가 전단사가 되는 유일한 수 $n \in \mathbb{Z}^+$이 존재한다.

$f$가 전단사이므로 역함수 $f^{-1} : \mathbb{N} \to \mathbb{Z}_{n}$이 존재하고 함수정리로 전단사이다.

하지만 위 정리에 모순이므로 $\mathbb{N}$은 무한집합이다.

 

 

 

정리5

다음이 성립한다.

1. $A,B$가 각각 $m,n\in $ $\mathbb{Z}^+$개의 원소를 갖는 유한집합일때

$A,B$가 서로소 $A \cap B = \emptyset$이면 합집합 $A \cup B$는 $m+n \in \mathbb{Z}^+$개의 원소를 갖는 유한집합이다.

2. $k \ge 2$인 $k \in \mathbb{Z}^+$에 대해 $A_1, A_2, \cdots, A_k$가 각각 $m_1,m_2, \cdots, m_k \in \mathbb{Z}^+$개의 원소를 유한집합이고

$i \ne j$인 모든 $i,j = 1,2,\cdots, k$에 대해 $A_i \cap A_j = \emptyset$이면 $\displaystyle \bigcup_{i = 1}^k A_i$는 $m_1 + m_2 +\cdots + m_k \in \mathbb{Z}^+ $개의 원소를 갖는다.

증명

1.

위 정의로 전단사함수 $f : \mathbb{Z}_{m} \to A$와 $g : \mathbb{Z}_{n} \to B$가 존재하고

함수 $h : \mathbb{Z}_{m + n} \to A\cup B$를 $i \in \mathbb{Z}_{m + n}$에 대해 $h(i) = \begin{cases} f(i) , & i < m \text{ 일때} \\  g(i-m) , & m \le i \text{ 일때} \end{cases} $  로 정의하면

$f,g$가 단사이므로 $i \ne j $인 임의의 $i, j \in \mathbb{Z}_{m + n}$에 대해

$ i < m$이고 $j < m$일때 $i \ne j $이므로 $h(i) = f(i) \ne f(j) = h(j)$이고

$m \le i$이고 $m \le j$일때 $i - m \ne j - m$이므로 $h(i) = g(i-m) \ne g(j-m) = h(j)$이고

$A \cap B = \emptyset$이므로 $i < m \le j$이면 $h(i) = f(i) \ne g(j-m) = h(j)$가 되어 $h$는 단사이다.

$f,g$가 전사이므로 모든 $x \in A\cup B$에 대해

$x \in A$이면 $h(i) = f(i) = x$이고 $i< m $인 $i \in \mathbb{Z}_{m + n}$가 존재하고

$x \in B$이면 $h(i) = g(i -m) =x$이고 $m \le i$인 $i \in \mathbb{Z}_{m + n}$가 존재하므로 $h$는 전사이다.

따라서 $h$는 전단사이고 위 정의로 $A \cup B$는 $m+n \in \mathbb{Z}^+$개의 원소를 갖는 유한집합이다.

2.

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

$k = 2$이면 1번으로 성립한다.

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

$A_1, A_2, \cdots, A_p, A_{p+1}$이 각각 $m_1,m_2, \cdots, m_p, m_{p+1} \in \mathbb{Z}^+$개의 원소를 유한집합이고

$i \ne j$인 모든 $i,j = 1,2,\cdots, p, p+1$에 대해 $A_i \cap A_j = \emptyset$이면

귀납가정으로 $\displaystyle \bigcup_{i = 1}^p A_i $는 $m_1 + m_2+ \cdots + m_p$개의 원소를 갖고 모든 $i= 1,2,\cdots, p$에 대해 $A_i \cap A_{p+1} = \emptyset$이므로

집합정리로 $\displaystyle \left ( \bigcup_{i = 1}^p A_i \right ) \cap A_{p+1} = (A_1 \cap A_{p+1}) \cup (A_2 \cap A_{p+1}) \cup \cdots \cup (A_p \cap A_{p+1})  = \emptyset$이 되어

1번으로 $\displaystyle \bigcup_{i = 1}^{p+1} A_i = \left (\bigcup_{i = 1}^p A_i \right ) \cup A_{p+1}$은 $m_1 + m_2 + \cdots + m_p + m_{p+1} \in \mathbb{Z}^+ $개의 원소를 갖는다.

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

 

 

 

정리6

$A$가 $m\in $ $\mathbb{Z}^+$개의 원소를 갖는 집합이고 $C \subset A$가 $m > n$인 $n \in \mathbb{Z}^+$개의 원소를 갖는 집합이면

여집합 $A \setminus C$는 $m-n \in \mathbb{Z}^+$개의 원소를 갖는 집합이다.

증명

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

$m > n = 1$일때

위 정의로 $f : \mathbb{Z}_{m} \to A$인 전단사함수가 존재하고 $C \subset A$이므로 $f(i) \in C$인 $i \in \mathbb{Z}_{m}$가 존재한다.

함수 $g : \mathbb{Z}_{m - 1} \to A\setminus C$를 $k \in \mathbb{Z}_{m -1}$에 대해 $g(k) = \begin{cases} f(k), & k< i \text{ 일때} \\ f(k+1) , & i \le k \text{ 일때}  \end{cases} $  로 정의하면

$g$는 전단사 함수이므로 $A\setminus C$는 $m-1 \in \mathbb{Z}^+$개의 원소를 갖는 집합이다.

모든 $k \in \mathbb{Z}^+$에 대해 $m > k$일때 정리가 성립한다고 가정한다.

$m > k + 1$일때 $\{c_1, c_2,\cdots, c_k,c_{k+1}\} = C_{k+1} \subset A$이면

$C_k = C_{k+1}\setminus \{ c_{k+1} \}$는 $k+1 > 1$이므로 위에서 보였듯이 $k+1 -1 = k \in \mathbb{Z}^+$개의 원소를 갖고

$m > k + 1>k$이므로 귀납가정으로 $A \setminus C_{k}$는 $m - k \in \mathbb{Z}^+$개의 원소를 갖는다.

또 $m > k+1$이므로 $m -k > 1$이 되어

$(A \setminus C_{k}) \setminus \{ c_{k+1} \}$은 위에서 보였듯이 $m - k - 1 = m - (k+1) \in \mathbb{Z}^+$개의 원소를 갖고

집합정리로 $(A \setminus C_{k}) \setminus \{ c_{k+1} \} = A \setminus (C_k \cup \{ c_{k+1} \})= A \setminus C_{k+1}$이다.

따라서 모든 $n \in \mathbb{Z}^+$에 대해 $m >n$이고 $C \subset A$일때 $A \setminus C$는 $m-n \in \mathbb{Z}^+$개의 원소를 갖는다.

 

 

 

정리13

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

1. $ (A \setminus B) \cap B = \emptyset$

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

증명

1.

$(A \setminus B) \cap B$는 교집합과 여집합의 정의로 

$( (x \in A) \land (x\notin B)) \land (x \in B )$인 명제가 참이 되는 $x$의 집합으로 표현되어 명제정리들로

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

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

2.

$ (A \setminus B) \cup B$는 합집합과 여집합의 정의로 

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

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

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

 

 

 

정리9

집합 $S,T$가 $T \subseteq S$일때 $S$가 유한집합이면 $T$도 유한집합이다.

이때 $S$가 $n \in $ $\mathbb{N}$개의 원소를 가지면 $T$는 $n \ge m \ge 0$인 $m \in \mathbb{N}$개의 원소를 갖는다.

증명

$S = \emptyset$이면 $T \subseteq S = \emptyset$이므로 집합정리로 $T = \emptyset$이고 $T$는 $0$개의 원소를 갖는다.

$S \ne \emptyset$일때 $T = \emptyset$이면 집합정리로 $T = \emptyset \subseteq S$이고 $T$는 $0$개의 원소를 갖는다.

$T \ne \emptyset$이고 $S \ne \emptyset$일때 $T \subseteq S$인 유한집합 $S$의 원소개수에 대한 귀납법을 사용한다.

$S$의 원소개수가 $1$개이면

유한집합의 정의로 전단사함수 $f : \mathbb{Z}_{1} \to S$가 존재하고 $T \ne \emptyset$이므로 $t \in T$가 존재한다.

모든 $x,y \in S$에 대해 $x = y$이고 $f(0) \in S$이므로 모든 $t \in T \subseteq S$는 $t = f(0)$이 되어

$f$는 $\mathbb{Z}_{1}$에서 $T$로의 전사이고 $f$는 단사이므로 유한집합의 정의로 $T$는 $1$개의 원소를 갖는 유한집합이다.

모든 $k\in \mathbb{Z}^+$에 대해 $S$가 $k$개의 원소를 갖을때

$T \ne \emptyset$이고 $T \subseteq S$인 $T$가 $1$개이상 $k$개이하의 원소를 갖는다고 가정한다.

$S$의 원소개수가 $k+1$개이면 유한집합의 정의로 전단사 함수 $f : \mathbb{Z}_{k+1}\to S$가 존재하고

위 정리로 $S \setminus \{ f(k+1) \}$은 $k+1 -1 = k$개의 원소를 갖는다.

$f(k+1) \notin T$이면 $T \subseteq (S \setminus \{ f(k+1)\})$이므로

귀납가정에 의해 $T$는 $1$개이상 $k$개이하의 원소를 갖는 유한집합이다.

$f(k+1) \in T$이면 $(T \setminus \{ f(k+1) \}) \subseteq (S \setminus \{ f(k+1)\})$이므로

귀납가정에 의해 $(T \setminus \{ f(k+1) \})$은 $1$개이상 $k$개이하의 원소를 갖는 유한집합이고 

위 정리로 $(T \setminus \left \{ f(k+1) \right \}) \cap \{ f(k+1) \} = \emptyset$이므로

위 정리로 $T = (T \setminus \{ f(k+1) \}) \cup \{ f(k+1) \}$는 $2$개이상 $k+1$개이하의 원소를 갖는 유한집합이다.

따라서 모든 $n \in \mathbb{N}$에 대해

$S$가 $n$개의 원소를 가지면 $T \subseteq S$인 $T$는 $n \ge m \ge 0$인 $m \in \mathbb{N}$개의 원소를 갖는 유한집합이다.

 

 

 

정리10

집합 $S,T$가 $T \subseteq S$일때 $T$가 무한집합이면 $S$도 무한집합이다.

증명

위 정리의 대우로 정리가 성립한다.

 

 

 

정리11

유한집합 $T,S$가 $T \subseteq S$일때 $T$와 $S$의 원소개수가 같다면 $T = S$이다.

증명

$T,S$의 원소개수가 $0$이면 유한집합의 정의로 $T = \emptyset = S$이다.

$T,S$의 원소개수가 $n \in \mathbb{Z}^+$개일때 $T \ne S$라고 가정하면

$T \subset S$이므로 $s_0 \notin T$이고 $s_0 \in S$인 $s_0$이 존재하여

$S_0 = S \setminus T = \{ s_0 \in S :  s_0 \notin T \}$의 원소개수는 $0$이 아니고

$S_0 \subseteq S$이므로 위 정리로 $S_0$은 $n \ge k \ge 1$인 $k \in \mathbb{Z}^+$개의 원소를 갖는다.

또 위 정리로 $S_0 \cap T = (S \setminus T) \cap T = \emptyset$이므로 위 정리로 $S_0 \cup T$는 $n + k> n$인 $n + k \in \mathbb{Z}^+$개의 원소를 갖는다.

따라서 모든 $x \in S_0 \cup T$는 $x \in S_0 \subseteq S$이거나 $x \in T \subset S$이므로 $S_0 \cup T \subseteq S$이고

모든 $x \in S$는 $x \notin T$이거나 $x \in T$이므로 $x \notin T$일때는 $x \in S_0$이 되어 $x \in S_0 \cup T$이므로 $S \subseteq S_0 \cup T$이고

집합정리로 $S_0 \cup T = S$인데 $S$는 $n \in \mathbb{Z}^+$개의 원소를 갖고 $S_0 \cup T$는 $n + k \in \mathbb{Z}^+$개의 원소를 갖으므로

유일성 정리에 모순이 되어 $T \subseteq S$일때 $T$와 $S$의 원소의 개수가 같다면 $T = S$이다.

 

 

 

정리16

$A$가 $m\in $ $\mathbb{N}$개의 원소를 갖는 집합이고 $C \subseteq A$가 $m \ge n$인 $n \in \mathbb{N}$개의 원소를 갖는 집합이면

여집합 $A \setminus C$는 $m-n \in \mathbb{N}$개의 원소를 갖는 집합이다.

증명

$m=n$이면

위 정리로 $A = C$이므로 집합정리로 $A \setminus C = A\setminus A = \emptyset$이 되어

유한집합의 정의로 $A \setminus C$는 $m-n = 0$개의 원소를 갖는 집합이다.

$n = 0$이면

유한집합의 정의로 $C =\emptyset$이므로 집합정리로 $A \setminus C = A\setminus \emptyset = A$가 되어

$A \setminus C$는 $m-n =  m$개의 원소를 갖는 집합이다.

$m>n \ge 1$일때

$A = C$이면 $m=n$이 되어 모순이므로 $A \ne C$이고 $C \subset A$가 되어

위 정리로 $A \setminus C$는 $m-n\in \mathbb{Z}^+$개의 원소를 갖는 집합이다.

 

 

 

정리12

$T$가 $n \in $ $\mathbb{N}$개의 원소를 갖는 유한집합일때

임의의 집합 $S$가 $n$개의 원소를 갖는 유한집합이기 위한 필요충분조건은 $T$와 $S$사이의 전단사함수가 존재하는 것이다.

증명

$n = 0$일때 유한집합의 정의로 $T = \emptyset$이고

$S$가 $0$개의 원소를 가지면 $S = \emptyset = T$이므로 공함수 정리로 공집합에서 공집합으로 전단사함수가 존재한다.

$T$와 $S$사이에 전단사함수가 존재할때 $S$가 공집합이 아니면

$S$에서 $T = \emptyset$으로 함수가 존재하지 않아 모순이므로 $S$는 공집합이고 $0$개의 원소를 갖는다.

$n \in \mathbb{Z}^+$일때 $T$가 $n \in \mathbb{Z}^+$개의 원소를 갖는 유한집합이므로

유한집합의 정의로 전단사함수 $f : \mathbb{Z}_n \to T$가 존재하고 역함수 정리로 역함수 $f^{-1} : T \to \mathbb{Z}_n$도 전단사이다.

$S$가 $n$개의 원소를 갖는 유한집합이면

유한집합의 정의로 전단사함수 $g : \mathbb{Z}_n \to S$가 존재하고 역함수 정리로 역함수 $g^{-1} : S \to \mathbb{Z}_n$도 전단사이다.

따라서 함수정리로 $g \circ f^{-1} : T \to S$와 $f \circ g^{-1} : S \to T$이 전단사이므로 정리가 성립한다.

역으로 전단사함수 $h : T \to S$가 존재하면

함수정리로 $h \circ f : \mathbb{Z}_n \to S$가 전단사이므로 유한집합의 정의로 $S$는 $n$개의 원소를 갖는 유한집합이다.

 

 

 

정리7

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

1. $A \cap B$는 $m\ge k \ge 0$이고 $n\ge k \ge 0$인 $k \in \mathbb{N}$개의 원소를 갖는 유한집합이다.

2. $A \cup B$는 $m + n \ge r \ge 0$인 $r \in \mathbb{N}$개의 원소를 갖는 유한집합이다.

3. $k \in $ $\mathbb{Z}^+$에 대해 $A_1, A_2, \cdots, A_k$가 각각 $m_1,m_2, \cdots, m_k \in \mathbb{N}$개의 원소를 유한집합이면

$\displaystyle \bigcup_{i = 1}^k A_i$는 $m_1 + m_2 +\cdots + m_k \ge r \ge 0$인 $r \in \mathbb{N}$개의 원소를 갖는 유한집합이다.

증명

1.

$A \cap B \subseteq A$이고 $A \cap B \subseteq B$이므로

위 정리로 $A \cap B$는 $m\ge k \ge 0$이고 $n\ge k \ge 0$인 $k \in \mathbb{N}$개의 원소를 갖는 유한집합이다.

2.

$m = 0$이면 유한집합의 정의로 $A = \emptyset$이므로 $A \cup B = B$는 $m+n = n$개의 원소를 갖는 유한집합이다.

$n = 0$이면 유한집합의 정의로 $B = \emptyset$이므로 $A \cup B = A$는 $m+n = m$개의 원소를 갖는 유한집합이다.

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

$A \cap B = \emptyset$이면 위 정리로 $A \cup B$은 $m+n \in \mathbb{Z}^+$개의 원소를 갖는 유한집합이다.

$A \cap B \ne \emptyset$일때 $A \cap B$의 원소개수는 $0$이 아니므로 1번으로 $m\ge k \ge 1$이고 $n\ge k \ge 1$인 $k \in \mathbb{Z}^+$개이다.

$m = k \ge 1$이면

$A \cap B \subseteq A$이므로 위 정리로 $ A \cap B = A$이고 집합정리로 $A\subseteq B$가 되어

모든 $x \in A \cup B$는 $x \in A \subseteq B$이거나 $x \in B$이므로 $A\cup B \subseteq B$이고

모든 $x \in B$는 당연히 $x \in A \cup B$이므로 $B \subseteq A \cup B$이고 집합정리로 $A \cup B = B$가 되어

$A\cup B$는 $m + n > n \ge 1$인 $n \in \mathbb{Z}^+$개의 원소를 갖는 유한집합이다.

$m > k \ge 1$이면

$A\setminus (A \cap B)$는 위 정리로 $m -k \ge 1$인 $m-k \in \mathbb{Z}^+$개의 원소를 갖고

집합정리와 위 정리로

$(A\setminus (A \cap B))\cap B = ((A \setminus A) \cup (A \setminus B)) \cap B  = (A \setminus B) \cap B= \emptyset$이고

$(A\setminus(A \cap B))\cup B = (A \setminus B) \cup B = A\cup B$이므로

위 정리로 $A \cup B$는 $m + n > m+n - k \ge 2$인 $m+n - k \in \mathbb{Z}^+$개의 원소를 갖는 유한집합이다.

3.

$k = 1$이면 자명하게 성립하므로 $k\ge 2$인 $k \in \mathbb{Z}^+$에 대해 귀납법을 사용한다.

$k = 2$이면 2번으로 성립한다.

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

$A_1, A_2, \cdots, A_p, A_{p+1}$이 각각 $m_1,m_2, \cdots, m_p, m_{p+1} \in \mathbb{N}$개의 원소를 유한집합이면

귀납가정으로 $\displaystyle \bigcup_{i = 1}^p A_i$는 $m_1 + m_2 +\cdots + m_p \ge r_1 \ge 0$인 $r_1 \in \mathbb{N}$개의 원소를 갖는 유한집합이므로

2번으로 $\displaystyle \bigcup_{i = 1}^{p+1} A_i = \left (\bigcup_{i = 1}^p A_i \right ) \cup A_{p+1}$은

$m_1 + m_2 + \cdots + m_p + m_{p+1} \ge r_1 + m_{p+1} \ge r_2 \ge 0$인 $r_2 \in \mathbb{N}$개의 원소를 갖는다.

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

 

 

 

정리8

$A$가 무한집합이고 $B$가 유한집합이면 $A \setminus B$는 무한집합이다.

증명

$A \setminus B$가 유한이라 가정하면

위 정리로 $ (A \setminus B) \cap B = \emptyset$이고 가정으로 $B$가 유한이므로 위 정리로 $ (A \setminus B) \cup B = A \cup B$는 유한인데

$A \subseteq A \cup B$이고 가정으로 $A$가 무한이므로 위 정리에 모순이 되어

$A$가 무한집합이고 $B$가 유한집합이면 $A\setminus B$는 무한집합이다.

 

 

 

정리14

$n \in \mathbb{N}$개의 원소를 갖는 유한집합 $A$의 멱집합 $\mathcal{P}(A)$는 $2^n$개의 원소를 갖는 유한집합이다.

증명

$n = 0$이면 유한집합의 정의로 $A =\emptyset$이고 집합정리로 $\emptyset$의 부분집합은 $\emptyset$뿐이므로

$\mathcal{P}(A)$는 $2^0 = 1$개의 원소를 갖는 유한집합이다.

$n \in \mathbb{Z}^+$에 대해서는 귀납법을 사용하여 증명한다.

$n = 1$이면 $a \in A$에 대해 $A = \{ a\}$이므로 $A$의 멱집합은 $\mathcal{P}(A) = \{ \emptyset, \{ a \} \}$로 $2^1 = 2$개의 원소를 갖는 유한집합이다.

모든 $k \in \mathbb{Z}^+$에 대해 정리가 성립할때 $A$가 $k +1$개의 원소를 갖는 유한집합이면

임의의 $a \in A$에 대해 $\{ a\}$는 $1$개의 원소를 갖는 유한집합이고 $k +1 \ge 2 > 1$이므로

위 정리로 $A\setminus \{ a\}$는 $k$개의 원소를 갖는 유한집합이 되어 귀납가정으로 $\mathcal{P}(A\setminus \{ a\})$는 $2^k$개의 원소를 유한집합이다.

임의의 $B \in \mathcal{P}(A\setminus \{ a\})$에 대해 $B\cup \{ a\}$는 $A$의 부분집합이므로 $B\cup \{ a\} \in \mathcal{P}(A)$이고

치환공리로 집합 $X_{a} = \{ C :  \text{어떤 }B\in \mathcal{P}(A\setminus \{a\})\text{에 대해 } C = B\cup \{ a\}  \}$를 정의할때

$f_a(B) = B\cup \{ a\}$인 함수 $f_a : \mathcal{P}(A\setminus \{ a\}) \to X_a$는

임의의 $B_1,B_2$에 대해 $B_1\cup \{ a \}= f_a(B_1) =f_a(B_2) = B_2 \cup \{ a\}$이면 $B_1 = B_2$이므로 단사이고 

모든 $C \in X_a$에 대해 $f_a(C\setminus \{a\}) = C$인 $C\setminus \{ a\} \in \mathcal{P}(A\setminus\{a\})$가 존재하므로 전사가 되어

$f_a$는 전단사이므로 위 정리로 $X_a$는 $2^k$개의 원소를 갖는다.

또 $\mathcal{P}(A\setminus \{ a\}) \cap X_a$가 공집합이 아니라고 가정하면

$C\in \mathcal{P}(A\setminus \{ a\}) \cap X_a$가 존재하여 어떤 $B \in \mathcal{P}(A\setminus \{ a\})$에 대해 $C = B\cup \{a\}\in \mathcal{P}(A\setminus \{a\})$인데

$B\cup \{ a\}$는 $A\setminus \{a\}$의 부분집합이 아니므로 모순이 되어 $\mathcal{P}(A\setminus \{ a\}) \cap X_a = \emptyset$이다.

따라서 위 정리로 $\mathcal{P}(A\setminus \{ a\}) \cup X_a$은 $2^k + 2^k = 2^k\cdot 2 = 2^{k+1}$개의 원소를 갖고

임의의 $C \in \mathcal{P}(A)$는 $C\subseteq A$이므로

$a\notin C$이면 $C \subseteq (A\setminus \{ a\})$가 되어 $C \in \mathcal{P}(A\setminus \{ a\})$이고

$a\in C$이면 $(C\setminus \{ a\}) \subseteq (A\setminus \{ a\})$이므로 위 정리로 $ C=(C\setminus \{ a\}) \cup \{ a\} \in X_a$가 되어

$C \in \mathcal{P}(A\setminus \{ a\}) \cup X_a$이므로 $\mathcal{P}(A)\subseteq \mathcal{P}(A\setminus \{ a\}) \cup X_a$이고

$ \mathcal{P}(A\setminus \{ a\}) \cup X_a \subseteq \mathcal{P}(A)$임은 자명하므로 집합정리로 $ \mathcal{P}(A\setminus \{ a\}) \cup X_a = \mathcal{P}(A)$는 $2^{k+1}$개의 원소를 갖는다.

모든 $n \in \mathbb{N}$에 대해 정리가 성립하므로 $\mathcal{P}(A)$는 $2^n$개의 원소를 갖는 유한집합이다.

 

 

 

정리15

임의의 집합 $X$가 무한집합이기 위한 필요충분조건은 $f(X)$ $\subset$ $X$인 단사함수 $f:X\to X$가 존재하는 것이다.

증명

$f(X) \subset X$인 단사함수 $f$가 존재할때 $X$가 유한이라 가정하면

유한집합의 정의로 어떤 $n \in \mathbb{N}$에 대해 전단사함수 $g : \mathbb{Z}_n \to X$가 존재하고

함수정리로 모든 $x \in X$에 대해 $h(x) = f(x)$인 함수 $h : X \to f(X)$는 전단사가 되어

합성함수 정리로 $h \circ g : \mathbb{Z}_n \to f(X)$는 전단사이므로 유한집합의 정의로 $f(X)$는 $n$개의 원소를 갖는 유한집합이다.

하지만 $f(X) \subseteq X$이고 $f(X) \ne X$인데 위 정리로 $f(X) = X$가 되어 모순이므로 $X$는 무한집합이다.

역으로 $X$가 무한집합일때 $X$가 가산이면

가산집합 정리로 $X$는 가부번이므로 전단사함수 $g : \mathbb{N} \to X$가 존재하여

축소함수 정리로 $g|_{\mathbb{Z}^+} : \mathbb{Z}^+ \to X$는 단사이다.

또 양의 정수집합 $\mathbb{Z}^+$는 가부번이므로 가부번정리로 전단사함수 $h : X \to \mathbb{Z}^+$가 존재하여 

합성함수 정리로 $g|_{\mathbb{Z}^+} \circ h : X \to X$는 단사이다.

$f = g|_{\mathbb{Z}^+}\circ h$로 정의할때 $g$는 단사이고 모든 $k \in \mathbb{Z}^+$는 $0\ne k$이므로 $g(0) \ne g(k) = g|_{\mathbb{Z}^+}(k)$이고

모든 $x \in X$에 대해 $h(x) \in \mathbb{Z}^+$이므로 $g(0) \ne g|_{\mathbb{Z}^+}(h(x)) = (g|_{\mathbb{Z}^+}\circ h)(x) = f(x)$이다.

따라서 $g(0) \notin f(X)$이고 $g(0) \in X$이므로 $f(X) \subset X$인 단사함수 $f:X\to X$가 존재한다.

$X$가 비가산이면

비가산집합 정리로 $A\subset X$이고 가부번집합 $A$가 존재하여 전단사함수 $g : \mathbb{N} \to A$가 존재한다.

모든 $x \in X$에 대해 $x \in g(\mathbb{N})$일때 $x = g(n)$인 $n \in \mathbb{N}$이 존재하므로 $f(x) = g(n+1)$로 정의하고

$x \notin g(\mathbb{N})$일때 $f(x) = x$로 $f : X\to X$를 정의하면 $x\ne y$인 모든 $x,y \in X$에 대해

$x \in g(\mathbb{N})$이고 $y \notin g(\mathbb{N})$이면 $f(y) = y \notin g(\mathbb{N})$이므로 $x = g(n)$인 $n\in \mathbb{N}$에 대해 $f(x) = g(n+1) \ne y= f(y) $이고

$x, y \in g(\mathbb{N})$이면 $ g(n)=x\ne y = g(k)$인 $n,k \in \mathbb{N}$는 $n\ne k$이므로 $f(x)=g(n+1) \ne g(k+1) = f(y)$이고

$x, y \notin g(\mathbb{N})$이면 $f(x) = x \ne y = f(y)$가 되어 $f$는 단사이다.

또 모든 $x \in X$에 대해 $x\notin g(\mathbb{N})$이면 $g(0) \ne x = f(x)$이고

$x \in g(\mathbb{N})$이면 $x = g(n)$인 $n \in \mathbb{N}$에 대해 $0\ne n+1$이므로 $g(0) \ne g(n+1) = f(x)$이다.

따라서 $g(0) \notin f(X)$이고 $g(0) \in X$이므로 $f(X) \subset X$인 단사함수 $f:X\to X$가 존재한다.

 

 

 

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

정의의 링크 : 

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

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

 

정리의 링크 : 

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

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

 

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

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

 

출처(저자 - 제목 - ISBN13)

Robert G. Bartle - Introduction to real analysis - 9788993543766

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