유한집합과 무한집합

by I Seul Bee

이 글은 『미적분학 첫걸음』 0장 3절의 내용입니다.  (미적분학 첫걸음 차례 보기)

음이 아닌 정수 \(0,1,2,\ldots\)를 집합으로 나타내는 한 가지 표준적인 방법은 다음과 같다. \[ \begin{align} 0 &= \varnothing,\\[6pt] 1 &= 0 \cup \left\{ 0 \right\} = \left\{ 0 \right\},\\[6pt] 2 &= 1 \cup \left\{ 1 \right\} = \left\{ 0,\,1 \right\},\\[6pt] 3 &= 2 \cup \left\{ 2 \right\} = \left\{ 0,\,1,\,2 \right\},\\[6pt] 4 &= 3 \cup \left\{ 3 \right\} = \left\{ 0,\,1,\,2,\,3 \right\},\\[6pt] &\qquad\vdots \end{align} \] 그러므로 \(n\)이 음이 아닌 정수라면, 이와 같이 나타낸 집합 \(n\)은 \(n\)개의 원소로 이루어져 있다. 이 글에서는 음이 아닌 정수 전체의 집합을 \[ \mathbb{N}=\left\{0,\,1,\,2,\,3,\,\ldots\right\} \] 로 나타낸다.

\(A\)와 \(B\)가 집합이라고 하자. 만약 \(A\)와 \(B\) 사이에 일대일 대응이 존재하면 “\(A\)와 \(B\)의 기수가 같다(have the same cardinality)”라고 말하고, 이것을 기호로 \[ \lvert A\rvert=\lvert B\rvert \quad\text{또는}\quad A\approx B \] 와 같이 나타낸다.

유한집합과 무한집합

\(E\)가 집합이라고 하자. 만약 음이 아닌 정수 \(k\)가 존재하여 \[ E\approx k \] 이면 \(E\)를 유한집합(finite set)이라고 부른다. 서로 다른 음이 아닌 정수는 같은 기수를 갖지 않으므로 이러한 \(k\)는 유일하다. 이때 \(E\)의 원소의 개수는 \(k\)라고 하고, 이것을 기호로 \[ n(E)=k \quad\text{또는}\quad \lvert E\rvert=k \] 와 같이 나타낸다.

어떠한 음이 아닌 정수 \(k\)에 대해서도 \(E\approx k\)가 성립하지 않으면 \(E\)를 무한집합(infinite set)이라고 부른다.

\(A\)와 \(B\)가 집합이라고 하자. 만약 \(A\)에서 \(B\)로의 일대일 함수가 존재하면 이것을 기호로 \[ \lvert A\rvert\le\lvert B\rvert \] 와 같이 나타낸다. 만약 \(\lvert A\rvert\le\lvert B\rvert\)이면서 \(\lvert A\rvert\ne\lvert B\rvert\)이면 \[ \lvert A\rvert<\lvert B\rvert \] 와 같이 나타낸다. 이로써 집합의 원소가 무한히 많을 때에도 집합의 크기를 비교할 수 있다.

다음 정리는 집합의 크기를 비교할 때 자주 사용된다.

정리 0.3.1. (Schröder-Bernstein 정리)

\(A\)와 \(B\)가 집합이라고 하자. 만약 \[ \lvert A\rvert\le\lvert B\rvert \quad\text{이고}\quad \lvert B\rvert\le\lvert A\rvert \] 이면 \[ \lvert A\rvert=\lvert B\rvert \] 이다.

증명.

\(f:A\rightarrow B\)와 \(g:B\rightarrow A\)가 일대일 함수라고 하자. 다음과 같이 \(A\)의 부분집합들을 정의한다. \[ A_0=A\setminus g(B), \qquad A_{n+1}=g(f(A_n)) \quad(n=0,1,2,\ldots). \] 그리고 \[ C=\bigcup_{n=0}^{\infty}A_n \] 이라고 하자.

\(a\in A\)에 대하여 함수 \(h:A\rightarrow B\)를 다음과 같이 정의한다. \[ h(a)= \begin{cases} f(a), & a\in C,\\ g^{-1}(a), & a\notin C. \end{cases} \] 여기서 \(a\notin C\)이면 특히 \(a\notin A_0=A\setminus g(B)\)이므로 \(a\in g(B)\)이다. 또한 \(g\)가 일대일 함수이므로 \(g^{-1}(a)\)는 하나로 정해진다.

먼저 \(h\)가 일대일 함수임을 보이자. \(C\) 안에서는 \(f\)가 일대일 함수이고, \(A\setminus C\)에서는 \(g^{-1}\)가 일대일 함수이다. 한편 \(a\in C\), \(a'\notin C\)이고 \(h(a)=h(a')\)라고 가정하면 \[ f(a)=g^{-1}(a') \] 이므로 \[ a'=g(f(a)). \] 그러나 \(a\in A_n\)인 어떤 \(n\)이 존재하므로 \[ a'\in g(f(A_n))=A_{n+1}\subseteq C \] 가 되어 모순이다. 따라서 \(h\)는 일대일 함수이다.

이제 \(h\)가 위로의 함수임을 보이자. \(b\in B\)라고 하자. 만약 \(g(b)\notin C\)이면 \[ h(g(b))=g^{-1}(g(b))=b. \] 만약 \(g(b)\in C\)이면 \(g(b)\notin A_0\)이므로 어떤 \(n\)에 대하여 \[ g(b)\in A_{n+1}=g(f(A_n)) \] 이다. 따라서 어떤 \(a\in A_n\)에 대하여 \[ g(b)=g(f(a)) \] 이고, \(g\)가 일대일 함수이므로 \(b=f(a)\)이다. 이때 \(a\in C\)이므로 \[ h(a)=f(a)=b. \] 따라서 \(h\)는 위로의 함수이다.

그러므로 \(h:A\rightarrow B\)는 일대일 대응이고 \[ \lvert A\rvert=\lvert B\rvert \] 이다.

집합 \(E\)의 모든 부분집합으로 이루어진 집합을 \(E\)의 멱집합(power set)이라고 부르고 \(P(E)\)로 나타낸다. 즉 \[ P(E)=\left\{A\,\vert\,A\subseteq E\right\} \] 이다.

정리 0.3.2. (Cantor 정리)

임의의 집합 \(E\)에 대하여 \[ \lvert E\rvert<\lvert P(E)\rvert \] 이다.

증명.

함수 \[ \iota:E\rightarrow P(E), \qquad \iota(x)=\{x\} \] 는 일대일 함수이므로 \[ \lvert E\rvert\le\lvert P(E)\rvert \] 이다.

한편 \(E\)에서 \(P(E)\)로의 위로의 함수가 존재한다고 가정하고 이를 \(f:E\rightarrow P(E)\)라고 하자. 다음과 같은 \(E\)의 부분집합을 생각하자. \[ D=\left\{x\in E\,\vert\,x\notin f(x)\right\}. \] \(D\in P(E)\)이고 \(f\)가 위로의 함수이므로 \(f(d)=D\)를 만족시키는 \(d\in E\)가 존재한다. 그런데 \(D\)의 정의에 의하여 \[ d\in D \quad\Longleftrightarrow\quad d\notin f(d) \quad\Longleftrightarrow\quad d\notin D \] 가 되어 모순이다. 따라서 \(E\)에서 \(P(E)\)로의 위로의 함수는 존재하지 않으며, 특히 두 집합 사이에는 일대일 대응이 존재하지 않는다. 그러므로 \[ \lvert E\rvert<\lvert P(E)\rvert \] 이다.

보기 0.3.3. 다음은 자주 사용되는 집합의 기수에 관한 표준적인 결과이다. 이 결과들의 증명은 이 글의 범위를 벗어나므로 생략한다.

  1. \(\lvert\mathbb{N}\rvert=\lvert\mathbb{Z}\rvert=\lvert\mathbb{Q}\rvert.\)
  2. \(\lvert\mathbb{N}\rvert=\lvert\mathbb{N}\times\mathbb{N}\rvert.\)
  3. \(\lvert\mathbb{N}\rvert<\lvert\mathbb{R}\rvert.\)
  4. \(\lvert\mathbb{R}\rvert=\lvert\mathbb{C}\rvert.\)
  5. \(\lvert\mathbb{R}\rvert=\lvert\mathbb{R}^d\rvert\)   (\(d\)는 양의 정수).

\(E\)가 집합이라고 하자. 만약 \[ \lvert E\rvert=\lvert\mathbb{N}\rvert \] 이면 \(E\)를 무한가산집합(countably infinite set)이라고 부른다. \(E\)가 유한집합이거나 무한가산집합이면 \(E\)를 가산집합(countable set)이라고 부르고, 가산집합이 아닌 집합을 비가산집합(uncountable set)이라고 부른다.

예를 들어 다음은 모두 가산집합이다. \[ \varnothing,\qquad \left\{1,\,2,\,3\right\},\qquad \mathbb{N},\qquad \mathbb{Z},\qquad \mathbb{Q},\qquad \mathbb{N}^2. \] 반면 \(\mathbb{R}\)와 \(\mathbb{C}\)는 비가산집합이다.

유한집합과 무한집합의 성질

이 절에서는 선택공리를 가정하는 통상적인 집합론의 틀에서 다음 사실을 증명 없이 사용한다.

기본 사실.

모든 무한집합은 무한가산인 부분집합을 가진다.

선택공리와 관련된 자세한 논의는 이 글의 범위를 벗어나므로 생략한다.

정리 0.3.4.

\(A,\) \(B,\) \(C\)가 집합이라고 하자. 이때 다음이 성립한다.

  1. \(A\)가 유한집합이고 \(B\)가 무한집합이면 \(\lvert A\rvert<\lvert B\rvert\)이다.
  2. \(\lvert A\rvert\le\lvert B\rvert\)이고 \(\lvert B\rvert\le\lvert C\rvert\)이면 \(\lvert A\rvert\le\lvert C\rvert\)이다.
  3. \(A\subseteq B\)이고 \(B\)가 유한집합이면 \(A\)도 유한집합이다.
  4. \(A\subseteq B\)이고 \(A\)가 무한집합이면 \(B\)도 무한집합이다.
  5. \(A\subseteq B\)이고 \(B\)가 가산집합이면 \(A\)도 가산집합이다.
  6. \(A\subseteq B\)이고 \(A\)가 비가산집합이면 \(B\)도 비가산집합이다.
  7. \(A\)가 무한집합일 필요충분조건은 \(A\)와 기수가 같은 \(A\)의 진부분집합이 존재하는 것이다.

증명.

(1) \(\lvert A\rvert=n\)이라고 하자. 기본 사실에 의하여 \(B\)는 무한가산인 부분집합을 가지므로 \(A\)에서 \(B\)로의 일대일 함수를 만들 수 있다. 따라서 \[ \lvert A\rvert\le\lvert B\rvert. \] 만약 \(\lvert A\rvert=\lvert B\rvert\)이면 \(B\)도 \(n\)개의 원소로 이루어진 유한집합이 되어 모순이다. 그러므로 \[ \lvert A\rvert<\lvert B\rvert. \]

(2) 일대일 함수 \(f:A\rightarrow B\)와 \(g:B\rightarrow C\)가 존재한다고 하자. 그러면 \(g\circ f:A\rightarrow C\)도 일대일 함수이므로 \[ \lvert A\rvert\le\lvert C\rvert. \]

(3) \(\lvert B\rvert=n\)이라고 하자. \(B\)의 부분집합은 \(n\)개 이하의 원소를 가지므로 \(A\)도 유한집합이다.

(4) 만약 \(B\)가 유한집합이면 (3)에 의하여 \(A\)도 유한집합이다. 이는 \(A\)가 무한집합이라는 가정에 모순이다. 따라서 \(B\)는 무한집합이다.

(5) 먼저 \(B\)가 유한집합이면 (3)에 의하여 \(A\)도 유한집합이므로 가산집합이다. 이제 \(B\)가 무한가산집합이라고 하자. \(B\)와 \(\mathbb{N}\) 사이의 일대일 대응을 하나 고정하면 \(A\)는 \(\mathbb{N}\)의 어떤 부분집합과 일대일 대응한다. \(\mathbb{N}\)의 부분집합은 유한집합이거나, 원소들을 작은 것부터 차례로 나열하여 \(\mathbb{N}\)과 일대일 대응시킬 수 있다. 따라서 \(A\)는 가산집합이다.

(6) 만약 \(B\)가 가산집합이면 (5)에 의하여 \(A\)도 가산집합이 되어 모순이다. 따라서 \(B\)는 비가산집합이다.

(7) 먼저 \(A\)가 무한집합이라고 하자. 기본 사실에 의하여 서로 다른 원소 \[ a_0,a_1,a_2,\ldots \] 를 \(A\)에서 택할 수 있다. 다음과 같이 \(h:A\rightarrow A\setminus\{a_0\}\)를 정의한다. \[ h(a_n)=a_{n+1}\quad(n=0,1,2,\ldots), \] 그리고 \(x\notin\{a_0,a_1,a_2,\ldots\}\)이면 \(h(x)=x\)로 놓는다. 그러면 \(h\)는 일대일 대응이다. 따라서 \(A\)는 자신의 진부분집합 \(A\setminus\{a_0\}\)과 같은 기수를 가진다.

거꾸로 \(A\)의 진부분집합 \(D\)가 존재하여 \[ \lvert A\rvert=\lvert D\rvert \] 라고 하자. 만약 \(A\)가 유한집합이면 진부분집합 \(D\)는 \(A\)보다 적은 수의 원소를 가지므로 두 집합의 기수가 같을 수 없다. 따라서 \(A\)는 무한집합이다.

따라서 유한집합과 달리 무한집합은 자신의 진부분집합과 일대일 대응할 수 있다. 선택공리를 가정하는 통상적인 집합론에서는 이 성질을 무한집합의 특징 가운데 하나로 볼 수 있다.