자연수의 다른 정의
이제 우리는 §서수와 정렬집합의 방법 대신, 우리가 이미 정의한 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)
명제 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$와 $b$가 존재하여 $ax+by$이도록 할 수 있다.
무한집합의 정의와 성질들
정의 11 집합이 무한하다infinite는 것은 유한하지 않다는 것이다.
이제 infinite cardinal의 성질에 대해 살펴보자. 앞서 finite cardinal은 $\mathfrak{a}\neq\mathfrak{a}+1$을 만족했다. 다음 정리는 이와 유사한 infinite cardinal만의 성질이다.
명제 12 모든 infinite cardinal $\mathfrak{a}$에 대하여 $\mathfrak{a}^2=\mathfrak{a}$가 성립한다.
이를 보이기 위해서는 다음의 보조정리들을 먼저 증명해야 한다.
보조정리 13 임의의 무한집합 $A$는 $\mathbb{N}$과 equipotent한 부분집합을 포함한다.
증명
$A$의 well-ordering이 존재한다. 자신을 제외한 $\mathbb{N}$의 임의의 segment는 항상 유한하므로, $A$는 $\mathbb{N}$의 segment와 isomorphic할 수 없다. 따라서 $\mathbb{N}$이 $A$의 segment와 isomorphic하다. (§서수들 사이의 순서관계, ⁋명제 1)
보조정리 14 집합 $\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}$여야 한다.
이를 활용하면 다음은 쉽게 보일 수 있다.
따름정리 15 $\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.
댓글남기기