수학/집합론

[집합의 크기] ch1. 유한집합

김한결 2022. 11. 22. 17:26

이전 읽을거리)

[집합론 기초] ch2. 합집합, 교집합, 명제

함수의 엄밀한 정의

데카르트 곱의 일반화된 정의

수학적 귀납법과 정렬원리

다음 읽을거리: ch2. 가산집합과 비가산집합

유한집합의 정의

자연수 $n$ 에 대해 $n$ 보다 작은 자연수의 집합을 $S_n$ 또는 $\{1,\ldots,n-1\}$ 이라고 표기하고, 이를 자연수의 절편(section)이라고 한다. 물론 $S_1=\varnothing$ 이다. 자연수의 절편은 유한집합이라고 불리는 것들의 원형이다.

Definition. 집합 $A$ 와 자연수의 어떤 절편 $S_n$ 에 대해 일대일 대응 $A\to S_n$ 이 존재하면 $A$ 가 유한하다(finite)고 한다. 다시말해 $A$ 가 유한하다는 것은 공집합이거나, 어떤 자연수 $n$ 에 대해 전단사함수 $f:A\to\{1,\ldots,n\}$ 이 존재하는 것이다. 전자의 경우 $A$ 의 크기(cardinality)가 0이라고 하고, 후자의 경우 $A$ 의 크기가 $n$ 이라고 한다.

예를들면 집합 $\{1,\ldots,n\}$ 은 항등함수에 의해 스스로에 대한 일대일대응을 가지므로 크기가 $n$ 이다.

아직 우리는 유한집합의 크기가 그 집합에 의해 유일하게 결정됨을 보이지 않았음에 유의하자. 공집합의 경우 크기가 0임은 분명하다. 하지만 현재까지의 정보로는, 공집합이 아닌 집합 $A$ 에서 서로 다른 두 집합 $\{1,\ldots,m\}$ , $\{1,\ldots,n\}$ 으로의 두 일대일대응이 존재할 수 없다고 확신할 수 없다. 이는 마치 두 사람이 한 상자 안의 조약돌 갯수를 세고 서로 다른 수를 말했는데 둘 다 정답인 것과 비슷하므로, 우스꽝스러운 가능성에 대해 논의하는 것 처럼 느껴진다. 일상에서 갯수를 세어본 경험을 이것이 불가능함을 암시하며, 실제로 작은 수 1,2,3 등에 대해서는 이를 쉽게 증명할 수 있다. 그러나 5백만 등의 경우 이를 직접 증명하는 것은 엄청나게 부담스러울 것이다.

인생을 살며 우리는 작은 집합을 세는 경험이 임의의 큰 집합에 대해서도 동일학 적용될 것이라고 믿는다. 그러나 수학에서는 이러한 표현을 믿음에 의지하지 않는다. 물리적 셈 보다는 일대일대응의 유무가 수학적 증명으로 적합하다.

유한집합의 성질

유한집합에 대한 수많은 직관적 사실들은 수학적으로 증명 가능하다. 아래는 그 시작으로 적절한 예시이다.

Lemma 1.1. 자연수 $n$ 과 집합 $A$ , $A$ 의 원소 $a_0$ 을 생각하자. 일대일대응 $A\to\{1,\ldots,n+1\}$ 이 존재할 필요충분조건은 일대일대응 $A\setminus\{a_0\}\to\{1,\ldots,n\}$ 이 존재하는 것이다.

Proof.

($\Leftarrow$) 일대일대응 $g:A\setminus\{a_0\}\to\{1,\ldots,n\}$ 이 존재한다고 가정하자. 이때 함수 $f:A\to\{1,\ldots,n+1\}$ 을 다음과 같이 정의하자.

$$f(x)=\begin{cases}g(x)&\text{for }x\in A\setminus\{a_0\}\\n+1&\text{for }x\neq a_0\end{cases}$$

$f$ 는 자명하게 전단사이므로 원하는 결과를 얻는다.

($\Rightarrow$) 일대일대응 $f:A\to\{1,\ldots,n+1\}$ 이 존재한다고 가정하자. 만약 $f(a_0)=n+1$ 이라면 $f|_{A\setminus\{a_0\}}$ 은 우리가 찾는 일대일대응 $A\setminus\{a_0\}\to\{1,\ldots,n\}$ 이다. 그 밖의 경우에 대해, $f(a_0)=m$ 이라고 하고 $f(a_1)=n+1$ 이도록 하는 $a_1\in A$ 를 생각하자. 이때 $a_0\neq a_1$ 이다. 이제 새로운 함수 $h:A\to\{1,\ldots,n+1\}$ 을 다음과 같이 정의하자.

$$h(x)=\begin{cases}f(x)&\text{for }x\in A\setminus\{a_0,a_1\}\\m&\text{for }x=a_1\\n+1&\text{for }x=a_0\end{cases}$$

$h$ 는 자명하게 전단사이다. 이때 $h|_{A\setminus\{a_0\}}$ 은 우리가 찾는 일대일대응 $A\setminus\{a_0\}\to\{1,\ldots,n\}$ 이므로 원하는 결과를 얻는다. $\square$

이 보조정리로부터 수많은 유용한 결과가 얻어진다.

Theorem 1.2. 집합 $A$ 에 대해, 어떤 자연수 $n$ 에 대하여 일대일대응 $A\to\{1,\ldots,n\}$ 이 존재한다고 가정하자. $A$ 진부분집합 $B$ 에 대해 일대일대응 $B\to\{1,\ldots,n\}$ 은 존재하지 않지만, $B\neq\varnothing$ 인 경우 어떤 $m<n$ 에 대해 일대일대응 $B\to\{1,\ldots,m\}$ 이 존재한다.

Proof. $B=\varnothing$ 의 경우 공집합 $B$ 에서 공집합이 아닌 집합으로의 전단사함수가 존재할 수 없으므로 본 정리가 자명하게 성립한다.

이 정리를 귀납법으로 증명하자. 먼저 이 정리가 $n=1$ 에 대해 참임을 보이자 이 경우 $A$ 는 홀원소집합이며 이의 유일한 진부분집합 $B$ 는 공집합이므로 위의 논의에 따라 본 정리가 성립한다.

이제 이 정리가 $n$ 에 대해 참이라고 가정하고 $n+1$ 에 대해서도 참임을 보이자. 일대일대응 $f:A\to\{1,\ldots,n+1\}$ 과 $A$ 의 공집합이 아닌 진부분집합 $B$ 를 생각하자. $B$ 의 원소 $a_0$ 과 $A\setminus B$ 의 원소 $a_1$ 을 선택하자. 보조정리 1.1.에 따르면 일대일대응 $g:A\setminus\{a_0\}\to\{1,\ldots,n\}$ 이 존재한다. 이때 $a_1$ 은 $A\setminus\{a_0\}$ 에 속하지만 $B\setminus\{a_0\}$ 에는 속하지 않으므로 $B\setminus\{a_0\}$ 는 $A\setminus\{a_0\}$ 의 진부분집합이다. 귀납법 가정에 따라 다음이 성립한다.

(1) 일대일대응 $B\setminus\{a_0\}\to\{1,\ldots,n\}$ 이 존재하지 않는다.

(2) $B\setminus\{a_0\}=\varnothing$ 이거나 어떤 $p<n$ 에 대해 일대일대응 $B\setminus\{a_0\}\to\{1,\ldots,p\}$ 가 존재한다.

(1) 과 도움정리 1.1.에 따르면 일대일대응 $B\to\{1,\ldots,n+1\}$ 은 존재하지 않는다. 이는 본 정리의 첫 번째 결론이다. 본 정리의 두 번째 결론을 증명하자. 만약 $B\setminus\{a_0\}=\varnothing$ 이면 $B=\{a_0\}$ 이므로 일대일대응 $B\to\{1\}$ 이 존재한다. 반면 $B\setminus\{a_0\}\neq\varnothing$ 이라면 (2)와 도움정리 1.1.에 따라 일대일대응 $B\to\{1,\ldots,p+1\}$ 이 존재하며, 특히 $p+1<n+1$ 이다. 정리하면 두 경우 모두 어떤 $m<n+1$ 에 대해 일대일대응 $B\to\{1,\ldots,m\}$ 이 존재하므로 원하는 결과를 얻는다. $\square$

따름정리들

Corollary 1.3. 유한집합 $A$ 에 대해, $A$ 에서 $A$ 의 진부분집합으로의 일대일대응은 존재하지 않는다.

Proof. 모순을 보이기 위해 $A$ 의 진부분집합 $B$ 에 대해 일대일대응 $f:A\to B$ 가 존재한다고 가정하자. 유한집합의 정의에 따라 어떤 자연수 $n$ 에 대해 일대일대응 $g:A\to\{1,\ldots,n\}$ 이 존재한다. 이때 합성함수 $g\circ f^{-1}$ 는 일대일대응 $B\to\{1,\ldots,n\}$ 이며, 이는 정리 1.2.와 모순된다. 따라서 원하는 결과를 얻는다. $\square$

Corollary 1.4. $\mathbb{N}$ 은 유한하지 않다.

Proof. 함수 $f:\mathbb{N}\to\mathbb{N}\setminus\{1\}$ , $f(n)=n+1$ 은 $\mathbb{N}$ 에서 $\mathbb{N}$ 의 진부분집합으로의 일대일대응이다. 따름정리 1.3.에 따라 $\mathbb{N}$ 는 유한하지 않다. $\square$

Corollary 1.5. 유한집합 $A$ 의 크기는 $A$ 에 의해 유일하게 결정된다.

Proof. $m<n$ 에 대해 일대일대응 $f:A\to\{1,\ldots,n\}$ , $g:A\to\{1,\ldots,m\}$ 을 생각하자. 합성함수 $g\circ f^{-1}$ 는 일대일대응 $\{1,\ldots,n\}\to\{1,\ldots,m\}$ 이다. $\{1,\ldots,m\}$ 은 $\{1,\ldots,n\}$ 의 진부분집함이므로 이는 따름정리 1.3.에 모순되므로 원하는 결과를 얻는다. $\square$

Corollary 1.6. $B$ 가 유한집합 $A$ 의 부분집합이면 $B$ 는 유한하다. 만약 $B$ 가 $A$ 의 진부분집합이면 $B$ 의 크기는 $A$ 의 크기보다 작다.

Proof. $B=A$ 이면 자명하게 $B$ 는 유한하다. $B$ 가 $A$ 의 진부분집합이라고 가정하자. (이 가정은 $A\neq\varnothing$ 를 전제한다) 만약 $B=\varnothing$ 이면 $B$ 는 유한하며 $B$ 의 크기는 0이므로 본 정리가 성립한다. $B\neq\varnothing$ 이면 정리 1.2.에 따라 $A$ 의 크기를 $n$ 이라고 할 때 어떤 $m<n$ 에 대해 일대일대응 $B\to\{1,\ldots,m\}$ 이 존재한다. 따라서 $B$ 는 유한하며, $B$ 의 크기 $m$ 은 $n$ 보다 작으므로 원하는 결과를 얻는다. $\square$

다음의 정리에 따르면 어떤 집합이 유한할 조건은 (자연수의 절편과의) 전단사함수가 존재하는 대신, 적절한 방향의 전사함수 또는 단사함수가 존재하는 것 만으로 충분함을 말한다.

Corollary 1.7. 공집합이 아닌 집합 $B$ 에 대해 다음의 세 명제는 동치이다.
(1) $B$ 는 유한하다.
(2) 어떤 자연수 $n$ 에 대해 전사함수 $\{1,\ldots,n\}\to B$ 가 존재한다.
(3) 어떤 자연수 $n$ 에 대해 단사함수 $B\to\{1,\ldots,n\}$ 가 존재한다.

Proof.

($1\Rightarrow 2$) $B$ 는 공집합이 아니므로, 유한성의 정의에 따라 $B$ 에서 자연수의 어떤 절편으로의 전단사함수가 존재한다.

($2\Rightarrow 3$) 전사함수 $f:\{1,\ldots,n\}\to B$ 에 대해, 함수 $g:B\to\{1,\ldots,n\}$ 을 각 $b\in B$ 에 대해 $g(b)=\text{min }f^{-1}(\{b\})$ 라고 정의하자. $f$ 는 전사이므로 $f^{-1}(\{b\})$ 는 공집합이 아니며 정렬원리에 따라 최소원소가 존재하므로 $g$ 가 잘 정의된다. 이때 $b\neq b'$ 에 대해 $f^{-1}(\{b\})$ 와 $f^{-1}(\{b'\})$ 는 서로소이므로 (만약 서로소가 아니면 공통의 원소 $i$ 에 대해 $f(i)=b$ , $f(i)=b'$ , $b\neq b'$ 이며 이는 대응규칙의 정의에 어긋난다) 각 집합의 최소원소도 서로 다르다. 따라서 $g$ 는 단사이다.

($3\Rightarrow 1$) 단사함수 $g:B\to\{1,\ldots,n\}$ 에 대해, $g$ 의 치역을 $S$ 라고 하자. 이때 함수 $h:B\to S$ , $h(b)=g(b)$ 는 전단사이다. $S$ 는 유한집합 $\{1,\ldots,n\}$ 의 부분집합이므로 유한하며, $S$ 의 크기를 $m$ 이라고 할 때 일대일대응 $\pi:S\to\{1,\ldots,m\}$ 에 대해 합성함수 $\pi\circ h$ 는 일대일대응 $B\to\{1,\ldots,m\}$ 이므로 $B$ 는 유한하다. $\square$

Corollary 1.8. 유한집합의 유한 합집합과 유한 데카르트 곱은 유한하다.

Proof. 먼저 유한집합 $A,B$ 에 대해 $A\cup B$ 가 유한함을 보이자. $A$ 또는 $B$ 가 공집합인 경우에는 자명하게 성립한다. 그 밖의 경우 어떤 자연수 $m,n$ 에 대해 전단사함수 $f:\{1,\ldots,m\}\to A$ , $g:\{1,\ldots,n\}\to B$ 가 존재한다. $\{1,\ldots,m+n\}$ 에서 $A\cup B$ 로의 함수 $h$ 를 각 $i=1,\ldots,m$ 에서 $f(i)=f(i)$, 각 $i=m+1,\ldots,m+n$ 에서 $h(i)=g(i-m)$ 이라고 정의하자. $h$ 는 전사함수이므로 따름정리 1.7.에 따라 $A\cup B$ 는 유한하다.

이제 귀납법을 이용해 집합 $A_1,\ldots,A_n$ 이 유한하면 $A_1\cup\cdots\cup A_n$ 이 유한함을 보이자. $n=1$ 인 경우에 정리가 자명하게 성립한다. $n-1$ 에서 정리가 성립한다고 가정하자. 이때 집합 $A_1\cup\cdots\cup A_n$ 은 유한집합 $A_1\cup\cdots\cup A_{n-1}$ 과 유한집합 $A_n$ 의 합집합이므로 위의 논의에 따라 $n$ 에서도 정리가 성립한다. 따라서 원하는 결과를 얻는다.

유한집합 $A,B$ 에 대해 $A\times B$ 가 유한함을 보이자. 만약 $A$ 또는 $B$ 가 공집합이라면 $A\times B=\varnothing$ 이므로 $A\times B$ 는 유한하다. 그 밖의 경우, 각 $a_0\in A$ 에 대해 $\{a_0\}\times B$ 는 자명한 일대일대응 $b\leftrightarrow(a_0,b)$ 에 의해 유한하다. $A\times B$ 는 이러한 집합의 합집합이다. $A$ 가 유한하므로 이는 유한집합이 유한 합집합이며 따라서 $A\times B$ 는 유한하다.

이제 귀납법을 이용해 집합 $A_1,\ldots,A_n$ 이 유한하면 $A_1\times\cdots\times A_n$ 이 유한함을 보이자. $A_1$ 의 원소의 1-순서쌍의 집합은 자명한 일대일대응 $a_1\leftrightarrow(a_1)$ 에 의해 유한하므로 $n=1$ 의 경우 정리가 성립한다. $n-1$ 에서 정리가 성립한다고 가정하자. 이전의 논의에 따라 $A_1\times\cdots\times A_{n-1}$ 과 $A_n$ 의 데카르트 곱 $(A_1\times\cdots\times A_{n-1})\times A_n$ 은 유한하며, 자명한 일대일대응

$$\big((a_1,\ldots,a_{n-1}),a_n\big)\leftrightarrow(a_1,\ldots,a_n)$$

에 의해 $A_1\times\cdots\times A_n$ 도 유한하다. 따라서 원하는 결과를 얻는다. $\square$

읽어주셔서 감사합니다.

References)

[1] James R. Munkres. (2000). Topology. Pearson College Div.