칸토어-베른슈타인 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:CantorEquivalenceTheorem1887b.gif|thumb|칸토어-베른슈타인 정리의 최초의 서술]]
[[집합론]]에서, '''칸토어-베른슈타인 정리'''({{llang|en|Cantor–Bernstein theorem}}) 또는 '''슈뢰더-베른슈타인 정리'''({{llang|en|Schröder–Bernstein theorem}})는 두 [[집합]] 사이에 두 방향으로 모두 [[단사 함수]]가 존재한다면, 두 집합 사이에 [[일대일 대응]]이 존재한다는 정리이다. [[체르멜로-프렝켈 집합론]]에서 [[선택 공리]]를 사용하지 않고 증명할 수 있다. 칸토어-베른슈타인 정리에 따라, [[기수 (수학)|기수]]의 표준적인 순서는 [[부분 순서]]이다. [[선택 공리]]를 추가로 가정하면, 기수의 순서가 [[전순서]]임을 보일 수 있다.

== 정의 ==
'''칸토어-베른슈타인 정리'''는 다음과 같다.<ref name="Jech">{{서적 인용|성1=Jech|이름1=Thomas|제목=Set theory|url=https://archive.org/details/settheory0000jech_f7i4|언어=en|판=3|총서=Springer Monographs in Mathematics|출판사=Springer|위치=Berlin|날짜=2003|isbn=978-3-540-44085-7|issn=1439-7382|doi=10.1007/3-540-44761-X|mr=1940513|zbl=1007.03002|id={{iaid|settheory0000jech_f7i4}}}}</ref>{{rp|28, Theorem 3.2}}
* 두 집합 <math>X</math>와 <math>Y</math> 사이에 [[단사 함수]] <math>f\colon X\to Y</math>와 <math>g\colon Y\to X</math>가 존재한다면, [[전단사 함수]] <math>h\colon X\to Y</math>가 존재한다.
이는 [[선택 공리]] 없이 증명할 수 있다.

[[기수 (수학)|기수]]는 같은 수의 원소를 포함하는 집합들을 묶은 [[동치류]]로 여길 수 있다. 구체적으로, 만약 [[전단사 함수]] <math>X\to Y</math>가 존재한다면, <math>|X|=|Y|</math>라고 정의한다 (<math>|X|</math>는 <math>X</math>의 [[집합의 크기|크기]]를 나타내는 [[기수 (수학)|기수]]). 만약 [[단사 함수]] <math>X\to Y</math>가 존재한다면, <math>|X|\le|Y|</math>라고 정의한다. 물론, 기수의 순서 <math>\le</math>의 정의는 기수를 크기로 하는 집합의 선택과 무관하다. 이 순서는 [[반사 관계]]이며 ([[항등 함수]]는 단사 함수), [[추이적 관계]]이다 (단사 함수의 [[함수의 합성|합성]]은 단사 함수). 칸토어-베른슈타인 정리는 다음과 같이 적을 수 있다.
* 만약 <math>|X|\le|Y|</math>이며 <math>|Y|\le|X|</math>라면, <math>|X|=|Y|</math>이다.
즉, 기수의 순서는 [[반대칭 관계]]이며, 따라서 [[부분 순서]]이다.

[[정렬 집합]]들 사이에서는 항상 크기를 비교할 수 있다. [[선택 공리]]를 가정하면, 모든 [[집합]]은 [[정렬 집합]]과 크기가 같으므로, 모든 집합들의 크기는 비교 가능하다. 즉, 기수의 순서는 [[전순서]]이다.

== 증명 ==
같은 맥락의 여러 증명들이 존재한다.

=== 표준적인 증명 ===
다음과 같이 정의하자.<ref name="Jech"/>{{rp|28, Theorem 3.2}}
:<math>X_0=X</math>
:<math>Y_0=g(Y)</math>
:<math>X_{n+1}=g(f(X_n))</math>
:<math>Y_{n+1}=g(f(Y_n))</math>
그러면 일련의 <math>X</math>의 [[부분 집합]]들
:<math>X_0\supseteq Y_0\supseteq X_1\supseteq Y_1\supseteq X_2\supseteq Y_2\supseteq\cdots</math>
을 얻는다. (자명하게 <math>X_0\supseteq Y_0</math>이다. <math>Y\supseteq f(X)</math>이므로 <math>Y_0\supseteq X_1</math>이다. <math>X_n\supseteq Y_n\supseteq X_{n+1}</math>에 <math>g\circ f</math>에 대한 [[상 (수학)|상]]을 씌우면 <math>X_{n+1}\supseteq Y_{n+1}\supseteq X_{n+2}</math>를 얻는다.) 이제, 함수 <math>h\colon X\to Y</math>를 다음과 같이 정의하자.
:<math>h(x)=\begin{cases}
f(x)&\exists n=0,1,\dots\colon x\in X_n\setminus Y_n\\
g^{-1}(x)&\not\exists n=0,1,\dots\colon x\in X_n\setminus Y_n
\end{cases}
</math>
(<math>g</math>는 [[전단사 함수]]일 필요가 없으므로 [[역함수]]를 가질 필요가 없지만, [[공역]]을 제한하여 부분적인 역함수 <math>g^{-1}\colon g(Y)\to Y</math>를 정의할 수 있다.) 이제 <math>h</math>가 [[단사 함수]]이자 [[전사 함수]]임을 보이면 충분하다.
* <math>h</math>는 단사 함수
** <math>h</math>는 <math>(X_0\setminus Y_0)\cup(X_1\setminus Y_1)\cup\cdots</math>로 제한되었을 때 <math>f</math>이며, 그 [[여집합]] <math>(Y_0\setminus X_1)\cup(Y_1\setminus X_2)\cup\cdots</math>로 제한하면 <math>g^{-1}</math>이다. <math>f</math>와 <math>g^{-1}</math>은 단사 함수이다. 따라서, <math>(X_0\setminus Y_0)\cup(X_1\setminus Y_1)\cup\cdots</math>의 서로 다른 원소 또는 <math>(Y_0\setminus X_1)\cup(Y_1\setminus X_2)\cup\cdots</math>의 서로 다른 원소의, <math>h</math>에 대한 상은 서로 다르다. <math>g\circ h</math>는 <math>X_n\setminus Y_n</math>의 원소를 <math>X_{n+1}\setminus Y_{n+1}</math>의 원소로 보내고, <math>Y_n\setminus X_{n+1}</math>의 원소를 (스스로로 보내므로) <math>Y_n\setminus X_{n+1}</math>로 보낸다. <math>X_{n+1}\setminus Y_{n+1}</math>와 <math>Y_n\setminus X_{n+1}</math>는 서로 만나지 않는다. 따라서, <math>(X_0\setminus Y_0)\cup(X_1\setminus Y_1)\cup\cdots</math>의 원소와 <math>(Y_0\setminus X_1)\cup(Y_1\setminus X_2)\cup\cdots</math>원소의, <math>h</math>에 대한 상은 서로 다르다.
* <math>h</math>는 전사 함수
** <math>y\in Y</math>라고 하자. <math>g(y)\in X_n\setminus Y_n</math>이라면, <math>n>0</math>이다 (<math>\because g(y)\in g(Y)=Y_0</math>). 즉, <math>X_n=g(f(X_{n-1}))</math>, <math>Y_n=g(f(Y_{n-1}))</math>이다. <math>g</math>가 [[단사 함수]]이므로, <math>y=f(x)=h(x)</math>인 <math>x\in X_{n-1}\setminus Y_{n-1}</math>이 존재한다. <math>g(y)\in Y_n\setminus X_{n+1}</math>이라면, <math>h(g(y))=g^{-1}(g(y))=y</math>이다.

=== 쾨니그의 증명 ===
편의상 <math>X\cap Y=\varnothing</math>이라고 가정하자 (가정이 참이 아니라면, 두 집합을 크기가 같은 두 서로소 집합 <math>\tilde X=\{(0,x)\colon x\in X\}</math>와 <math>\tilde Y=\{(1,y)\colon y\in Y\}</math>로 대체한다). 단사 함수 <math>f\colon X\to Y</math>와 <math>g\colon Y\to X</math>의 부분적 [[역함수]]
:<math>f^{-1}\colon f(X)\to X</math>
:<math>g^{-1}\colon g(Y)\to Y</math>
를 정의하자. 임의의 <math>x\in X</math>에 대하여, <math>X\sqcup Y</math> 위의 열
:<math>\dots,f^{-1}(g^{-1}(x)),g^{-1}(x),x,f(x),g(f(x)),\dots</math>
을 구성할 수 있다. 마찬가지로, 임의의 <math>y\in Y</math>에 대하여, <math>X\cup Y</math> 위의 열
:<math>\dots,g^{-1}(f^{-1}(y)),f^{-1}(y),y,g(y),f(g(y)),\dots</math>
을 구성할 수 있다. 이러한 열은 <math>X</math>와 <math>Y</math>의 원소가 번갈아 가며 나타나며, 오른쪽으로는 끝없이 이어지고, 왼쪽은 끝이 없거나 (<math>f^{-1}</math>나 <math>g^{-1}</math>가 정의되지 않는) 어떤 <math>X</math> 또는 <math>Y</math>의 원소에서 끝이 난다. 임의의 항은 열을 완전하게 결정하므로, 두 열이 어떤 항을 공유한다면, 두 열은 서로 같다. 즉, 위와 같은 꼴의 열들은 <math>X\sqcup Y</math>을 [[집합의 분할|분할]]한다. 따라서, 각 열에 등장하는 <math>X</math>의 원소와 <math>Y</math>의 원소 사이의 [[전단사 함수]]를 찾으면 충분하다. 임의의 항은 열을 결정하므로, 특히 바로 다음 항을 결정한다. 즉, 임의의 항을 오른쪽의 이웃하는 항으로 대응시키는 함수는 항상 잘 정의된다. 이는 열 속 <math>X</math>의 원소에서 열 속 <math>Y</math>의 원소로 가는 [[전단사 함수]]이거나, 반대 방향의 [[전단사 함수]]이다.

=== 타르스키 고정점 정리를 통한 증명 ===
<math>X</math>의 [[멱집합]] 격자 <math>(\mathcal P(X),\subseteq)</math>는 [[완비 격자]]를 이룬다. 함수
:<math>\mathcal P(X)\to\mathcal P(X)</math>
:<math>S\mapsto X\setminus g(Y\setminus f(S))</math>
는 [[순서 보존 함수]]이므로, [[타르스키 고정점 정리]]에 따라 [[고정점]] <math>S\subseteq X</math>를 갖는다. 즉,
:<math>X\setminus S=g(Y\setminus f(S))</math>
이다. 따라서, [[전단사 함수]]
:<math>X\to Y</math>
:<math>x\mapsto\begin{cases}
f(x)&x\in S\\
g^{-1}(x)&x\in X\setminus S
\end{cases}
</math>
가 존재한다.

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{eom|제목=Schroeder–Bernstein theorem}}
* {{매스월드|id=Schroeder-BernsteinTheorem|제목=Schröder-Bernstein theorem}}
* {{nlab|id=Cantor-Schroeder-Bernstein theorem}}

[[분류:수학기초론 정리]]
[[분류:기수]]