집합론
자연수와 무한집합
자연수의 정의와 무한집합의 성질들
자연수의 다른 정의
이제 우리는 §서수와 정렬집합의 방법 대신, 우리가 이미 정의한 cardinal을 사용해서 자연수를 만들고 cardinal number들 위에서 정의했던 연산과 대소관계를 이용해 자연수의 구조를 탐구한다.
정의 1 Cardinal \(\mathfrak{a}\)가 유한하다finite는 것은 \(\mathfrak{a}\neq\mathfrak{a}+\mathbf{1}\)인 것이다. 유한한 cardinal을 자연수natural number라고 부른다. 집합 \(E\)에 대하여, cardinal \(\card E\)가 유한하다면 이 집합을 유한하다고 부르며, 이 때 \(\card E\)를 집합 \(E\)의 원소의 갯수라고 부른다.
자연수는 cardinal들의 집합의 부분집합이므로 well-ordered이다. (§기수, ⁋정리 5) 따라서 자연수에서 귀납법을 사용할 수 있다. (§정렬집합의 성질들, ⁋보조정리 7 (Transfinite induction))
명제 2 Cardinal \(\mathfrak{a}\)가 유한한 것과 \(\mathfrak{a}+\mathbf{1}\)이 유한한 것이 동치이다.
증명
§기수들 사이의 연산, ⁋명제 6에 의하여, \(\mathfrak{a}=\mathfrak{b}\)인 것은 \(\mathfrak{a}+\mathbf{1}=\mathfrak{b}+\mathbf{1}\)인 것과 동치이다. 이제 \(\mathfrak{b}=\mathfrak{a}+\mathbf{1}\)로 잡으면, 가정에 의해 \(\mathfrak{a}\neq\mathfrak{b}\)이고, 따라서
\[\mathfrak{b}=\mathfrak{a}+\mathbf{1}\neq\mathfrak{b}+\mathbf{1}\]이므로 \(\mathfrak{a}\)가 유한한 것은 \(\mathfrak{b}=\mathfrak{a}+\mathbf{1}\)이 유한인 것과 동치이다.
이제부터 자연수들은 블랙레터 \(\mathfrak{a}\), \(\mathfrak{b}\) 대신 \(m\), \(n\) 등과 같은 일반적인 알파벳으로, 그리고 cardinal number인 \(\mathbf{0}\)과 \(\mathbf{1}\)도 간단히 \(0\)과 \(1\)로 쓰기로 한다.
자연수 사이의 대소관계
보조정리 3 \(\mathfrak{a}\)와 \(\mathfrak{b}\)가 cardinal이라 하자. 그럼 \(\mathfrak{a}\geq\mathfrak{b}\)인 것은 어떠한 cardinal \(\mathfrak{c}\)가 존재하여 \(\mathfrak{a}=\mathfrak{b}+\mathfrak{c}\)인 것과 동치이다.
증명
\(\mathfrak{a}\geq\mathfrak{b}\)인 것은, cardinal \(\mathfrak{a}\)와 \(\mathfrak{b}\)를 갖는 집합 \(A\), \(B\)가 각각 존재하여 \(A\supset B\)인 것과 동치이다. 이제 \(A=B\cup(A\setminus B)\).
명제 4 \(n\)이 자연수라 하자. 그럼 \(\mathfrak{a}\leq n\)을 만족하는 모든 cardinal \(\mathfrak{a}\)도 자연수이다. 만일 \(n\neq 0\)이라면, 유일한 자연수 \(m\)이 존재하여 \(n=m+1\)이다. 이 때, \(a\)에 관한 unary relation \(a<n\)은 \(a\leq m\)과 동치이다.
증명
우선 첫 번째를 보이기 위해 \(\mathfrak{a}\)가 \(\mathfrak{a}\leq n\)을 만족하는 cardinal이라 하자. 그럼 어떤 cardinal \(\mathfrak{b}\)가 존재하여 \(n=\mathfrak{a}+\mathfrak{b}\)이다. 이제
\[(\mathfrak{a}+1)+\mathfrak{b}=(\mathfrak{a}+\mathfrak{b})+1=n+1\neq n\]이므로 \((\mathfrak{a}+1)+\mathfrak{b}\neq\mathfrak{a}+\mathfrak{b}\)이다. 따라서 \(\mathfrak{a}+1\neq\mathfrak{a}\)이므로 \(\mathfrak{a}\)는 자연수다.
만일 \(n\neq 0\)이라면 \(n\geq 1\)이므로, 앞선 보조정리에 의해 \(n=m+1\)인 cardinal \(m\)이 존재하며, 앞선 논리에 의해 \(m\)도 자연수이다. 따라서 \(a<n\)이 \(a\leq m\)과 동치임만 보이면 된다.
우선 \(a<n\)이라면, 유일한 자연수 \(b\)가 존재하여 \(n=a+b\)이다. \(b\neq 0\)이므로, 어떠한 \(c\)에 대해 \(b=c+1\)이다. 그럼
\[m+1=n=a+b=a+(c+1)=(a+c)+1\]에서 \(m=a+c\)이다. 따라서 \(a\leq m\)이다. 반대로 만일 \(a\leq m\)일 경우,
\[a\leq m+1=n\]이고, \(a=n=m+1>m\)은 모순이므로 \(a\neq n\)이다. 따라서 \(a<n\)이다.
명제 5 \(a\)와 \(b\)가 자연수라 하자. \(a<b\)는 어떤 자연수 \(c>0\)가 존재하여 \(b=a+c\)인 것과 동치이다.
증명
보조정리 3의 직접적인 결과다. \(a\leq b\)이므로 그러한 \(c\geq 0\)가 존재하는데, \(c=0\)이라면 \(a=b\)이기에 \(c\neq 0\)이기 때문이다.
지금까지 한 것들을 정리하면 다음을 얻는다.
명제 6 \(a\)와 \(b\)가 자연수라 하자. 그럼 함수 \(x\mapsto a+x\)는 구간 \([0,b]\)에서 \([a,a+b]\)로의 strictly increasing order isomorphism이다.
따라서 임의의 구간 \([a,b]\)를 원소의 갯수 \(b-a+1\)개짜리 집합과 동일하게 취급할 수 있다. 유한한 정의역을 가지는 함수를 유한수열이라 부르는데, 모든 유한집합은 위의 정리에 의해 \([1,n]\)과 동일시될 수 있으므로 우리는 항상 유한수열이 \(1\)부터 \(n\)까지의 자연수 위에서 정의된 것으로 취급할 수 있다.
명제 7 \((a_i)_{i\in I}\)가 자연수를 값으로 갖는 유한수열이라 하자. 그럼 \(\sum a_i\)와 \(\prod a_i\)는 모두 자연수이다.
증명
\(I\)가 유한이므로, 임의의 자연수 \(a\)와 \(b\)에 대해 \(a+b\)와 \(ab\)가 자연수임만 보이면 충분하다. 이는 \(b\)에 대한 귀납법으로 보이면 된다. 우선 \(a+0=a\)가 자연수이고, \(a+k\)가 자연수라면 \(a+(k+1)=(a+k)+1\) 또한 마찬가지이므로 쉽게 보일 수 있다. 곱셈도 마찬가지.
자연수 집합의 성질들
정의 8 \(A\)가 공집합이 아니고 \(X\)가 \(A\)의 부분집합이라 하자. \(X\)의 특성함수characteristic function는 함수 \(\chi_X:E\rightarrow \{0,1\}\)이며, 그 값은 다음의 식
\[\chi_X(x)=\begin{cases}1&\text{if $x\in X$}\\ 0&\text{if $x\in A\setminus X$}\end{cases}\]으로 주어진다.
다음 정리는 자명하다.
명제 9 집합 \(A\)의 두 부분집합 \(X\)와 \(Y\)에 대하여,
\[\begin{aligned} \chi_{A\setminus X}(x)&=1-\chi_X(x)\\ \chi_{X\cap Y}(x)&=\chi_X(x)\chi_Y(x)\\ \chi_{X\cup Y}(x)+\chi_{X\cap Y}(x)&=\chi_X(x)+\chi_Y(x) \end{aligned}\]가 성립한다.
이제 집합론보다는 다른 여러 곳에서 쓸 자연수의 성질을 조금 정리하고 넘어가자. 우선 다음은 유클리드 호제법이라 불리는 나눗셈 알고리즘이다.
정리 10 \(a\)와 \(b\)가 \(b>0\)를 만족하는 자연수들이라 하자. 그럼 유일한 자연수 \(q\)와 \(r\)이 존재하여 \(a=bq+r\)이고 \(r< b\)이다.
증명
만일 그러한 쌍이 존재한다면 \(q\)는 \(a<b(q+1)\)를 만족하는 가장 작은 자연수여야 한다. 그렇지 않으면
\[r=a-bq<0\quad\text{or}\quad r=a-bq\geq b\]이 되기 때문이다. 존재성을 보이기 위해, \(a<a+1<b(a+1)\)라 하자. 그럼 \(a<bp\)를 만족하는 \(p\)의 집합은 공집합이 아니다. 이제 well-orderedness에 의해, least element \(m\)이 존재하므로 \(m=q+1\)라 하면 \(q\)가 주어진 조건을 만족한다.
위의 증명처럼, 우리가 정의한 자연수의 연산을 잘 사용하여 나머지나 배수, 약수 등의 개념을 정의할 수 있다. 다음 따름정리 또한 마찬가지 방식으로 쉽게 증명할 수 있으나, 아직 우리는 정수를 정의하지는 않았으므로 증명은 따로 하지 않는다.
따름정리 11 (Bézout’s lemma) 임의의 두 정수 \(a\), \(b\)가 최대공약수 \(d\)를 갖는다고 하자. 그럼 적당한 두 정수 \(x\)와 \(y\)가 존재하여 \(ax+by=d\)이도록 할 수 있다.
무한집합의 정의와 성질들
정의 12 집합이 무한하다infinite는 것은 유한하지 않다는 것이다.
이제 infinite cardinal의 성질에 대해 살펴보자. 앞서 finite cardinal은 \(\mathfrak{a}\neq\mathfrak{a}+1\)을 만족했다. 다음 정리는 이와 유사한 infinite cardinal만의 성질이다.
명제 13 모든 infinite cardinal \(\mathfrak{a}\)에 대하여 \(\mathfrak{a}^2=\mathfrak{a}\)가 성립한다.
이를 보이기 위해서는 다음의 보조정리들을 먼저 증명해야 한다.
보조정리 14 임의의 무한집합 \(A\)는 \(\mathbb{N}\)과 equipotent한 부분집합을 포함한다.
증명
\(A\)의 well-ordering이 존재한다. 자신을 제외한 \(\mathbb{N}\)의 임의의 segment는 항상 유한하므로, \(A\)는 \(\mathbb{N}\)의 segment와 isomorphic할 수 없다. 따라서 \(\mathbb{N}\)이 \(A\)의 segment와 isomorphic하다. (§서수들 사이의 순서관계, ⁋명제 1)
보조정리 15 집합 \(\mathbb{N}\times\mathbb{N}\)은 \(\mathbb{N}\)과 equipotent하다.
증명
다음의 수열
\[(1,1),\;\; (1,2),(2,1),\;\; (1,3),(2,2),(3,1),\;\; \cdots\]에 의해 자명.
명제 12의 증명
\(A\)가 cardinal \(\mathfrak{a}\)를 갖는 집합이라 하자. 그럼 첫 번째 보조정리로부터 어떤 \(B\subseteq A\)는 \(\mathbb{N}\)과 equipotent하고, 따라서 두 번째 보조정리에 의해 \(B\times B\)와 \(B\) 사이의 전단사함수가 존재한다. 이를 \(f\)라 하자.
\(B\)를 포함하는 \(A\)의 부분집합 \(X\)와, 그 위에서 정의된 \(f\)의 extension \(\psi:X\rightarrow X\times X\)에 대해 \(\mathfrak{M}\)이 이러한 쌍 \((X,\psi)\)들의 모임이라 하자. 그럼 \(\mathfrak{M}\)의 임의의 chain에 대하여 가장 큰 정의역을 갖는 쌍이 maximal element가 되므로, \(\mathfrak{M}\)은 inductive한 집합이고, 따라서 Zorn’s lemma에 의해 \(\mathfrak{M}\)의 maximal element \((F, \tilde{f})\)가 존재한다.
이제 \(\card F=\mathfrak{a}\)임을 보이면 충분하다. 만일 \(\card F=\mathfrak{b}<\mathfrak{a}\)라면, bijection \(\tilde{f}\)에 의해 \(\mathfrak{b}=\mathfrak{b}^2\)이므로
\[\mathfrak{b}\leq 2\mathfrak{b}\leq 3\mathfrak{b}\leq \mathfrak{b}^2=\mathfrak{b}\]에서 \(\mathfrak{b}=2\mathfrak{b}=3\mathfrak{b}\)이다. 그럼 \(\mathfrak{b}<\mathfrak{a}\)에서 \(\card(A\setminus F)>\mathfrak{b}\)이다. 그렇지 않다면
\[\mathfrak{a}=\card A=\card(F\cup(A\setminus F))\leq\card F+\card(A\setminus F)\leq\mathfrak{b}+\mathfrak{b}=2\mathfrak{b}=\mathfrak{b}\]가 되어 모순이기 때문이다. 따라서 어떤 \(Y\subseteq A\setminus F\)가 존재하여 \(\card Y=\mathfrak{b}\)이다. \(Z=F\cup Y\)라 하자. 그럼
\[Z\times Z=(F\times F)\cup(F\times Y)\cup(Y\times F)\cup (Y\times Y)\]이고, 우변의 네 항들은 모두 서로소인 집합들이다. \(F\)와 \(Y\)가 equipotent하므로,
\[\card(F\times Y)=\card(Y\times F)=\card(F\times F)=\mathfrak{b}^2=\mathfrak{b}\]이고 따라서
\[\card((F\times Y)\cup(Y\times F)\cup(Y\times Y))=3\mathfrak{b}=\mathfrak{b}=\card Y\]이다. 그러므로 \(Y\)에서 이 집합들의 합집합으로의 전단사함수가 존재하고, 따라서 \(Z=F\cup Y\)에서 \(Z\times Z\)로의 전단사함수가 존재한다. \(F\)에서는 \(\tilde{f}:F\rightarrow F\times F\)로, \(Y\)에서는 방금 만든 전단사함수를 이용하면 되기 때문이다. 이는 \(F\)의 maximality에 모순이므로 \(\card F=\mathfrak{a}\)여야 한다.
이를 활용하면 다음은 쉽게 보일 수 있다.
따름정리 16 \(\mathfrak{a}\)가 infinite cardinal이라면, 임의의 \(n\geq 1\)에 대해 \(\mathfrak{a}^n=\mathfrak{a}\)이다. 0이 아닌 cardinal들의 유한한 family \((\mathfrak{a}_i)_{i\in I}\)에 대하여, 만일 이들 중 가장 큰 cardinal이 infinite cardinal \(\mathfrak{a}\)라면 이들의 곱과 합은 모두 \(\mathfrak{a}\)이다.
우리는 무한집합들 중 \(\mathbb{N}\)과 equipotent한 것을 특별히 countable이라 부른다.
참고문헌
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.
댓글남기기