칸토어-베른슈타인 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

칸토어-베른슈타인 정리는 두 집합 X와 Y 사이에 단사 함수 f: X → Y와 g: Y → X가 존재하면, 전단사 함수 h: X → Y가 존재한다는 정리이다. 이 정리는 선택 공리 없이 증명할 수 있으며, 기수의 관점에서 |X| ≤ |Y|이고 |Y| ≤ |X|이면 |X| = |Y|임을 의미한다. 칸토어-베른슈타인 정리는 여러 수학자에 의해 증명되었으며, 율리우스 쾨니히, 펠릭스 베른슈타인, 리하르트 데데킨트 등의 이름을 따서 불린다. 이 정리는 집합론에서 중요한 역할을 하며, [0, 1]에서 [0, 1)으로, 또는 [0, 2)에서 [0, 1)²으로의 전단사 함수를 구성하는 데 사용될 수 있다.

칸토어-베른슈타인 정리

개요

유형	집합론의 정리
관련 분야	수학, 논리학
다른 이름	칸토어-베른슈타인-슈뢰더 정리 슈뢰더-베른슈타인-칸토어 정리 쾨니히-베른슈타인 정리 (에른스트 체르멜로)

내용

가정	함수 f : A → B 가 존재 함수 g : B → A 가 존재
결론	A 와 B 사이에 전단사 함수 h : A → B 가 존재
의미	\|A\| ≤ \|B\| 이고 \|B\| ≤ \|A\| 이면 \|A\| = \|B\| 이다. 두 집합 A와 B 각각이 다른 집합의 부분집합과 대등하면, 두 집합은 대등하다.

증명

증명 방법	다양한 증명 방법 존재
일반적인 증명	구성적 증명 (집합 A를 분할하여 전단사 함수 h 구성)

역사

초기 증명 시도	칸토어 (1883): 오류 포함 슈뢰더 (1896): 오류 포함, 미발표
최초의 정확한 증명	베른슈타인 (1897): 칸토어에게 전달, 1898년 보렐에 의해 발표 체르멜로 (1901): 베른슈타인과는 독립적으로 증명
슈뢰더의 증명 발표	슈뢰더 (1898): 수정된 증명 발표 (여전히 오류 존재)

활용

집합의 크기 비교	두 집합의 크기 비교에 유용하게 사용

참고 자료

관련 항목	집합론, 기수 (수학)

📚 더 읽어볼만한 페이지

기수 - 초한수
초한수는 게오르크 칸토어가 도입한 무한 개념을 확장한 수로, 집합의 크기를 나타내는 기수와 정렬된 집합 내의 위치를 나타내는 서수로 나뉘며, 무한에도 여러 종류가 있음을 밝혀 현대 수학의 기초를 다졌다.
기수 - 칸토어의 정리
칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2<sup>κ</sup> > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.
수학기초론 정리 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
수학기초론 정리 - 칸토어의 정리
칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2<sup>κ</sup> > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.

1. 개요
2. 정의
3. 증명
4. 역사
- 4.1. 초기 역사
- 4.2. 명칭 문제
5. 전제 조건
6. 예시
- 6.1. [0, 1] → [0, 1) 전단사 함수
- 6.2. [0, 2) → [0, 1)² 전단사 함수

2. 정의

칸토어-베른슈타인 정리는 두 집합의 크기를 비교하는 기본적인 정리로, 내용은 다음과 같다.

* 두 집합 $X$ 와 $Y$ 사이에 단사 함수 $f\colon X\to Y$ 와 $g\colon Y\to X$ 가 존재한다면, 전단사 함수 $h\colon X\to Y$ 가 존재한다.

이 정리는 선택 공리 없이 증명할 수 있다는 특징이 있다.

기수는 집합의 크기를 나타내는 개념으로, 같은 수의 원소를 가진 집합들을 하나의 동치류로 묶어 생각할 수 있다. 구체적으로, 두 집합 $X$ 와 $Y$ 사이에 전단사 함수가 존재하면 두 집합의 크기가 같다고 정의하고 $|X|=|Y|$ 로 표기한다. 여기서 $|X|$ 는 집합 $X$ 의 크기를 나타내는 기수이다. 만약 단사 함수 $X\to Y$ 가 존재한다면, $X$ 의 크기가 $Y$ 의 크기보다 작거나 같다고 정의하고 $|X|\le|Y|$ 로 표기한다. 이 기수의 순서 관계 $\le$ 는 어떤 집합을 선택하든 상관없이 잘 정의된다. 이 순서는 자기 자신에 대해 항상 성립하는 반사 관계이며(항등 함수는 단사 함수이므로 $|X|\le|X|$ ), $|X|\le|Y|$ 이고 $|Y|\le|Z|$ 이면 $|X|\le|Z|$ 가 성립하는 추이적 관계이다(단사 함수의 합성은 단사 함수).

칸토어-베른슈타인 정리는 기수의 관점에서 다음과 같이 표현할 수 있다.

* 만약 $|X|\le|Y|$ 이며 $|Y|\le|X|$ 라면, $|X|=|Y|$ 이다.

이는 기수의 순서 관계 $\le$ 가 $|X|\le|Y|$ 이고 $|Y|\le|X|$ 이면 $|X|=|Y|$ 가 성립하는 반대칭 관계임을 보여준다. 따라서 기수의 순서 관계는 부분 순서이다.

정렬 집합들 사이에서는 항상 크기를 비교할 수 있다. 만약 선택 공리를 가정한다면, 모든 집합은 어떤 정렬 집합과 크기가 같아지므로, 임의의 두 집합의 크기는 항상 비교 가능하게 된다. 즉, 선택 공리를 가정하면 기수의 순서는 전순서가 된다.

3. 증명

칸토어-베른슈타인 정리를 증명하는 방법은 여러 가지가 있다. 대부분의 증명은 집합 $A$ 와 $B$ 사이에 주어진 두 단사 함수 $f: A \to B$ 와 $g: B \to A$ 를 이용하여, $A$ 에서 $B$ 로 가는 전단사 함수 $h: A \to B$ 를 직접 구성하는 방식으로 이루어진다.

대표적인 방법 중 하나는 율리우스 쾨니히가 제시한 증명으로, 각 원소에서 시작하여 $f$ 와 $g$ 및 그 부분 함수인 역함수 $g^{-1}$ , $f^{-1}$ 를 번갈아 적용하여 만들어지는 원소들의 열(sequence)을 분석하는 방식이다.
: $\cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots$
이러한 열들은 각 원소가 속한 열의 시작점이나 형태(예: $A$ 에서 멈춤, $B$ 에서 멈춤, 양방향 무한, 순환)에 따라 분류될 수 있다. 각 분류에 따라 함수 $h$ 를 $f$ 또는 $g^{-1}$ 를 이용하여 정의함으로써 전체적으로 전단사 함수를 구성한다.

다른 접근 방식으로는 집합 $A$ 의 부분집합들을 귀납적으로 구성하여 전단사 함수 $h$ 를 정의하는 방법이 있다. 예를 들어, $A$ 를 특정 기준(예: $g$ 의 치역에 속하지 않는 원소에서 시작하여 $f$ 와 $g$ 를 반복 적용하여 도달할 수 있는 원소들의 집합 $C$ )에 따라 두 부분집합 $C$ 와 $A \setminus C$ 로 나누고, 다음과 같이 $h$ 를 정의하는 방식이다.
: $h(x) = \begin{cases}f(x)& \text{if }x \in C \\g^{-1}(x)& \text{if } x \notin C\end{cases}$
이 함수 $h$ 가 전단사 함수임을 보인다.

이 외에도 타르스키 고정점 정리를 이용하는 등 다양한 증명 방법이 존재한다. 각 증명의 구체적인 과정은 하위 섹션에서 자세히 다룬다.

3.1. 표준적인 증명

칸토어-베른슈타인 정리의 표준적인 증명은 두 집합 사이에 각각 단사 함수가 존재하면 전단사 함수도 존재함을 보이는 방식으로, 주로 두 가지 접근법이 사용된다. 두 방법 모두 귀납적인 집합 구성을 통해 원하는 전단사 함수를 직접 만들어낸다.

=== 집합열을 이용한 증명 ===
두 집합 $X$ 와 $Y$ 사이에 두 단사 함수 $f: X \to Y$ 와 $g: Y \to X$ 가 주어졌다고 하자. 다음과 같이 $X$ 의 부분 집합들의 열을 정의한다.
: $X_0=X$
: $Y_0=g(Y)$
: $X_{n+1}=g(f(X_n))$
: $Y_{n+1}=g(f(Y_n))$
여기서 $f(X_n)$ 은 $X_n$ 의 $f$ 에 대한 상이고, $g(Y)$ , $g(f(X_n))$ , $g(f(Y_n))$ 도 마찬가지로 $g$ 에 대한 상이다. 함수 $f$ 와 $g$ 가 단사이므로, 이들의 합성은 $g \circ f: X \to X$ 역시 단사 함수이다.

이렇게 정의된 집합들은 다음 포함 관계를 만족한다.
: $X_0\supseteq Y_0\supseteq X_1\supseteq Y_1\supseteq X_2\supseteq Y_2\supseteq\cdots$
이는 수학적 귀납법으로 증명할 수 있다.
* 기저 단계 (n=0): $X_0 = X \supseteq g(Y) = Y_0$ 는 정의상 성립한다. $f(X) \subseteq Y$ 이므로 $X_1 = g(f(X)) \subseteq g(Y) = Y_0$ 이다. 따라서 $X_0 \supseteq Y_0 \supseteq X_1$ 이다.
* 귀납 단계: 어떤 $k \ge 0$ 에 대해 $X_k \supseteq Y_k \supseteq X_{k+1}$ 이 성립한다고 가정하자. 함수 $g \circ f$ 는 단사이므로 집합의 포함 관계를 보존한다. 따라서 $g(f(X_k)) \supseteq g(f(Y_k)) \supseteq g(f(X_{k+1}))$$ 이 성립한다. 정의에 의해 이는 $X_{k+1} \supseteq Y_{k+1} \supseteq X_{k+2}$ 와 같다.

따라서 모든 자연수 $n \ge 0$ 에 대해 $X_n \supseteq Y_n \supseteq X_{n+1}$ 이 성립한다.

이제 함수 $h\colon X\to Y$ 를 다음과 같이 정의하자.
: $h(x)=\begin{cases}f(x)& \text{만약 어떤 } n \ge 0 \text{에 대해 } x \in X_n \setminus Y_n \text{ 이면} \\g^{-1}(x)& \text{만약 모든 } n \ge 0 \text{에 대해 } x \notin X_n \setminus Y_n \text{ 이면}\end{cases}$
여기서 $g$ 는 단사 함수이므로, 치역 $g(Y) = Y_0$ 로 공역을 제한하면 역함수 $g^{-1}\colon Y_0 \to Y$ 를 정의할 수 있다. $x \notin \bigcup_{n=0}^\infty (X_n \setminus Y_n)$ 인 경우는 $x$ 가 모든 $n$ 에 대해 $x \in Y_n$ 이거나 ( $x \in \bigcap_{n=0}^\infty Y_n$ ), 어떤 $k$ 에 대해 $x \in Y_k \setminus X_{k+1}$ 인 경우이다. 두 경우 모두 $x \in Y_0 = g(Y)$ 이므로 $g^{-1}(x)$ 는 잘 정의된다.

이제 $h$ 가 전단사 함수임을 보이자.

* $h$ 는 단사 함수이다: $f$ 와 $g^{-1}$ 는 모두 단사 함수이므로, $h$ 는 각 정의 구간( $\bigcup_{n=0}^\infty (X_n \setminus Y_n)$ 와 그 여집합)에서 단사적이다. 서로 다른 구간에 속하는 $x_1 \in \bigcup_{n=0}^\infty (X_n \setminus Y_n)$ 와 $x_2 \notin \bigcup_{n=0}^\infty (X_n \setminus Y_n)$ 를 생각해보자. $x_1 \in X_k \setminus Y_k$ 인 $k \ge 0$ 가 존재한다. $h(x_1) = f(x_1)$ 이고 $h(x_2) = g^{-1}(x_2)$ 이다. 만약 $h(x_1) = h(x_2)$ 라면 $f(x_1) = g^{-1}(x_2)$ 이고, 양변에 $g$ 를 적용하면 $g(f(x_1)) = x_2$ 가 된다. $x_1 \in X_k \setminus Y_k$ 이므로 $x_2 = g(f(x_1)) \in g(f(X_k \setminus Y_k))$$ 이다. $g(f(X_k)) = X_{k+1}$ 이고 $g(f(Y_k)) = Y_{k+1}$ 이므로, $x_2 \in X_{k+1} \setminus Y_{k+1}$ 이다. 이는 $x_2 \notin \bigcup_{n=0}^\infty (X_n \setminus Y_n)$ 라는 가정에 모순이다. 따라서 $h(x_1) \neq h(x_2)$ 이고, $h$ 는 전체 정의역에서 단사 함수이다.

* $h$ 는 전사 함수이다: 임의의 $y \in Y$ 를 생각하자. $g(y) \in X$ 이다.
* 만약 어떤 $n \ge 0$ 에 대해 $g(y) \in X_n \setminus Y_n$ 이라면, $g(y) \in g(Y) = Y_0$ 이므로 반드시 $n > 0$ 이다. $g(y) \in X_n \setminus Y_n = g(f(X_{n-1})) \setminus g(f(Y_{n-1}))$$ 이다. $g$ 는 단사이므로, $y \in f(X_{n-1}) \setminus f(Y_{n-1})$ 이다. 즉, $y = f(x)$ 를 만족하는 $x \in X_{n-1} \setminus Y_{n-1}$ 가 존재한다. 이 $x$ 는 $\bigcup_{n=0}^\infty (X_n \setminus Y_n)$ 에 속하므로, $h(x) = f(x) = y$ 이다.
* 만약 모든 $n \ge 0$ 에 대해 $g(y) \notin X_n \setminus Y_n$ 이라면, $h$ 의 정의에 따라 $x = g(y)$ 에 대해 $h(x) = h(g(y)) = g^{-1}(g(y)) = y$ 가 성립한다.
따라서 모든 $y \in Y$ 에 대해 $h(x) = y$ 인 $x \in X$ 가 존재하므로, $h$ 는 전사 함수이다.

결론적으로 $h$ 는 단사 함수이고 전사 함수이므로 전단사 함수이다.

=== 귀납적 집합 구성을 이용한 증명 ===
집합 $A$ 와 $B$ 사이에 단사 함수 $f \colon A \to B$ 와 $g \colon B \to A$ 가 주어졌다고 가정하자.
다음과 같이 집합족 $\{ C_n \}_{n \in \mathbb{N}}$ ( $\mathbb{N} = \{0, 1, 2, \dots\}$ ) 를 귀납적으로 정의한다.
: $C_0 := A \setminus g(B)$ (즉, $g$ 의 치역에 속하지 않는 $A$ 의 원소들의 집합)
: $C_{n+1} := g(f(C_n))$ (즉, $C_n$ 의 원소를 $f$ 로 보내고 다시 $g$ 로 보낸 집합)
이제 이 집합들의 합집합을 $C$ 라고 하자.
: $C = \bigcup_{n=0}^\infty C_n = C_0 \cup C_1 \cup C_2 \cup \cdots$
이제 함수 $h \colon A \to B$ 를 다음과 같이 정의한다.
: $h(x) = \begin{cases}f(x)& \text{if }x \in C \\g^{-1}(x)& \text{if } x \notin C \text{ (즉, } x \in A \setminus C \text{)}\end{cases}$
여기서 $x \notin C$ 이면 $x \notin C_0$ 이므로 $x \in g(B)$ 이다. $g$ 는 단사이므로 $g^{-1}(x)$ 는 $B$ 의 원소로서 유일하게 정의된다. 이제 이 함수 $h$ 가 전단사 함수임을 보이자.

* $h$ 는 단사 함수이다:
* 만약 $x_1, x_2 \in C$ 이고 $h(x_1) = h(x_2)$ 이면, $f(x_1) = f(x_2)$ 이다. $f$ 는 단사이므로 $x_1 = x_2$ 이다.
* 만약 $x_1, x_2 \in A \setminus C$ 이고 $h(x_1) = h(x_2)$ 이면, $g^{-1}(x_1) = g^{-1}(x_2)$ 이다. 양변에 $g$ 를 적용하면 $x_1 = x_2$ 이다 ( $g^{-1}$ 도 단사).
* 만약 $x_1 \in C$ 이고 $x_2 \in A \setminus C$ 인데 $h(x_1) = h(x_2)$ 라고 가정하자. 그러면 $f(x_1) = g^{-1}(x_2)$ 이다. 양변에 $g$ 를 적용하면 $g(f(x_1)) = x_2$ 이다. $x_1 \in C = \bigcup_{n=0}^\infty C_n$ 이므로, 어떤 $n \ge 0$ 에 대해 $x_1 \in C_n$ 이다. 그러면 $x_2 = g(f(x_1)) \in g(f(C_n)) = C_{n+1}$ 이다. 그런데 $C_{n+1} \subseteq C$ 이므로 $x_2 \in C$ 가 된다. 이는 $x_2 \in A \setminus C$ 라는 가정에 모순이다. 따라서 $x_1 \in C$ 와 $x_2 \in A \setminus C$ 에 대해 $h(x_1) \neq h(x_2)$ 이다.
위 세 경우를 종합하면, $h$ 는 단사 함수이다.

* $h$ 는 전사 함수이다: 임의의 $y \in B$ 를 생각하자. 우리는 $h(x) = y$ 인 $x \in A$ 를 찾아야 한다.
$g(y) \in A$ 를 고려하자.
* 만약 $g(y) \in C$ 라면, $h$ 의 정의에 따라 $h(g(y))$ 는 정의되지 않는다 (정의역은 $A$ ). 대신 $g(y) \in C = \bigcup C_n$ 이므로 어떤 $n$ 에 대해 $g(y) \in C_n$ 이다.
* 만약 $n=0$ 이면 $g(y) \in C_0 = A \setminus g(B)$ 인데, 이는 $g(y)$ 가 $g$ 의 치역에 속한다는 사실에 모순이다. 따라서 $n > 0$ 이어야 한다.
* $n > 0$ 이면 $g(y) \in C_n = g(f(C_{n-1}))$$ 이다. $g$ 는 단사이므로, $y \in f(C_{n-1})$$ 이다. 즉, $y = f(x)$ 를 만족하는 $x \in C_{n-1}$ 이 존재한다. $C_{n-1} \subseteq C$ 이므로 $x \in C$ 이다. 따라서 $h(x) = f(x) = y$ 이다.
* 만약 $g(y) \notin C$ (즉, $g(y) \in A \setminus C$ ) 라면, $h$ 의 정의에 따라 $x = g(y)$ 로 두면 $x \in A \setminus C$ 이므로 $h(x) = h(g(y)) = g^{-1}(g(y)) = y$ 이다.
따라서 모든 $y \in B$ 에 대해 $h(x) = y$ 인 $x \in A$ 가 존재하므로, $h$ 는 전사 함수이다.

결론적으로 $h$ 는 단사 함수이고 전사 함수이므로 전단사 함수이다. 이 증명은 다음과 같이 요약될 수 있다: $A$ 는 $C$ 와 $A \setminus C$ 로 분할되고, $B$ 는 $f(C)$ 와 $B \setminus f(C)$ 로 분할된다. 함수 $h$ 는 $C$ 에서 $f(C)$ 로 가는 전단사 함수 $f$ 와, $A \setminus C$ 에서 $B \setminus f(C)$ 로 가는 전단사 함수 $g^{-1}$ 를 조합한 것이다. 실제로 $g^{-1}(A \setminus C) = g^{-1}(A) \setminus g^{-1}(C)$ 이고, $g^{-1}(A) = B$ 이며,
: $g^{-1}(C) = g^{-1}\left(\bigcup_{n=0}^\infty C_n\right) = g^{-1}(C_0) \cup g^{-1}\left(\bigcup_{n=1}^\infty C_n\right)$
$C_0 = A \setminus g(B)$ 이므로 $g^{-1}(C_0)$ 는 공집합이다. $C_n = g(f(C_{n-1}))$$ 이므로,
: $g^{-1}\left(\bigcup_{n=1}^\infty C_n\right) = \bigcup_{n=1}^\infty g^{-1}(C_n) = \bigcup_{n=1}^\infty g^{-1}(g(f(C_{n-1}))) = \bigcup_{n=1}^\infty f(C_{n-1}) = \bigcup_{k=0}^\infty f(C_k) = f\left(\bigcup_{k=0}^\infty C_k\right) = f(C)$
따라서 $g^{-1}(A \setminus C) = B \setminus f(C)$ 이다. 즉, $h$ 는 $A \setminus C$ 를 $B \setminus f(C)$ 로 보내는 전단사 함수 $g^{-1}$ 와 같다.

3.2. 쾨니히의 증명

다음 증명은 율리우스 쾨니히에 의한 것이다.

일반성을 잃지 않으면서, 두 집합 A와 B가 상호소 집합이라고 가정한다. (만약 상호소가 아니라면, 크기가 같은 두 서로소 집합

\tilde A=\{(0,a)\colon a\in A\}

와

\tilde B=\{(1,b)\colon b\in B\}

로 대체할 수 있다.) 단사 함수

f\colon A\to B

와

g\colon B\to A

가 주어졌다고 하자. 이 함수들의 부분적인 역함수

f^{-1}\colon f(A)\to A

와

g^{-1}\colon g(B)\to B

를 정의한다. 이때

f^{-1}

와

g^{-1}

는 부분 함수이다. 즉, 정의역에 포함되지 않는 원소에 대해서는 함수값이 정의되지 않을 수 있다.

임의의 원소

a \in A

또는

b \in B

에 대해, 함수

f

와

g

, 그리고 그 역함수

f^{-1}

와

g^{-1}

를 반복적으로 적용하여 원소들의 열(sequence)을 만들 수 있다. 예를 들어,

a \in A

에서 시작하는 열은 다음과 같다.
:

\cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots

이 열은

A

의 원소와

B

의 원소가 번갈아 나타난다. 오른쪽으로는 함수

f

와

g

를 계속 적용하여 무한히 이어질 수 있다. 왼쪽으로는 역함수

f^{-1}

나

g^{-1}

를 적용하는데, 만약 어떤 원소에서 역함수가 정의되지 않으면(즉, 그 원소가 각각

g(B)

나

f(A)

에 속하지 않으면) 열은 그 지점에서 멈춘다.

함수

f

와

g

는 단사 함수이므로,

A \cup B

의 각 원소는 정확히 하나의 열에 속한다. 만약 두 열이 하나의 원소라도 공유한다면, 그 열은 완전히 동일해야 한다. 따라서 이러한 열들은

A \cup B

전체를 서로 겹치지 않는 부분집합들로 나누는 집합의 분할을 형성한다. 이제 각 열 안에서

A

의 원소들과

B

의 원소들 사이에 전단사 함수

h \colon A \to B

를 정의하면 된다.

각 열은 다음 네 가지 유형 중 하나로 분류될 수 있다.
* A-스토퍼(A-stopper): 열이 왼쪽으로 진행하다가

A

의 원소에서 멈추는 경우. 이는

g^{-1}

가 정의되지 않는

A

의 원소에서 시작하는 열이다. 이 열에 속하는 모든

a \in A

에 대해

h(a) = f(a)

로 정의한다. 그러면

f

자체가 이 열의

A

원소들과

B

원소들 사이의 전단사 함수가 된다.
* B-스토퍼(B-stopper): 열이 왼쪽으로 진행하다가

B

의 원소에서 멈추는 경우. 이는

f^{-1}

가 정의되지 않는

B

의 원소에서 시작하는 열이다. 이 열에 속하는 모든

a \in A

에 대해

h(a) = g^{-1}(a)

로 정의한다. 즉,

g(h(a)) = a

가 성립한다. 그러면

g^{-1}

가 이 열의

A

원소들과

B

원소들 사이의 전단사 함수가 된다.
* 양방향 무한대(Doubly infinite): 열이 양쪽 방향으로 무한히 계속되는 경우. 이 열에 속하는

a \in A

에 대해

h(a) = f(a)

로 정의하거나,

h(a) = g^{-1}(a)

로 정의할 수 있다. 어느 쪽이든 이 열의

A

원소들과

B

원소들 사이의 전단사 함수가 된다. (위 그림 예시에서는

h(a) = g^{-1}(a)

를 사용했다.)
* 사이클(Cycle): 열의 원소들이 유한하게 반복되는 경우. 이 경우도 양방향 무한대와 마찬가지로

h(a) = f(a)

또는

h(a) = g^{-1}(a)

중 하나로 정의하면 전단사 함수가 된다. (위 그림 예시에서는

h(a) = g^{-1}(a)

를 사용했다.)

이렇게 각 열마다 정의된 함수 조각들을 모두 합치면, 전체 집합

A

에서

B

로 가는 전단사 함수

h

가 구성된다. 따라서

A

와

B

의 크기(기수)는 같다.

3.3. 타르스키 고정점 정리를 통한 증명

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

4. 역사

칸토어-베른슈타인 정리의 명칭은 그 발견과 증명의 복잡한 역사를 반영한다. 전통적으로 "슈뢰더-베른슈타인 정리" 또는 "칸토어-베른슈타인 정리" 등으로 불리는데, 이는 1898년 슈뢰더와 베른슈타인이 각자 독립적으로 증명을 발표한 사실과 관련이 있다.

그러나 정리 자체는 1887년 칸토어가 처음 언급했으며, 같은 해 데데킨트가 처음으로 증명했지만 발표하지는 않았다. 또한 슈뢰더가 발표한 증명에는 오류가 있었다는 점 등 여러 역사적 사실이 얽혀 있어, 정리의 이름에 누구를 포함해야 하는지에 대해서는 다양한 견해가 존재한다. 베른슈타인에 따르면 칸토어는 이 정리에 "동치 정리"(Äquivalenzsatz^독일어)라는 이름을 제안하기도 했다. 이처럼 수학 정리의 이름이 항상 최초 발견자나 증명자의 이름을 따르거나 역사적 경위를 정확히 반영하는 것은 아니며, 칸토어-베른슈타인 정리는 그러한 복잡한 과정을 보여주는 대표적인 사례 중 하나이다.

4.1. 초기 역사

전통적인 명칭인 "슈뢰더-베른슈타인" 또는 "칸토어-베른슈타인"은 이 정리의 발견 및 증명 과정에 기여한 여러 수학자들의 이름을 반영하지만, 그 과정이 복잡하여 명칭에 대한 논란이 있다. 슈뢰더의 이름은 그의 증명에 오류가 있었기 때문에 제외되기도 하며, 정리를 처음 증명한 데데킨트의 이름은 보통 포함되지 않는다. 칸토어는 이 정리를 처음 언급했기 때문에 이름에 포함되기도 한다. 베른슈타인에 따르면, 칸토어는 이 정리에 "동치 정리"(Äquivalenzsatz)라는 이름을 제안했다.

정리의 발견과 증명 과정은 다음과 같이 요약할 수 있다.

👆

좌우로 밀어서 보기

연도	인물	내용
1887	칸토어	정리를 발표했지만, 증명은 포함하지 않았다.
1887	데데킨트	7월 11일, 선택 공리에 의존하지 않고 정리를 증명했다. 그러나 자신의 증명을 출판하거나 칸토어에게 알리지 않았다. 에른스트 체르멜로는 데데킨트의 증명을 발견했고, 1908년에 데데킨트의 논문 "Was sind und was sollen die Zahlen?"의 '사슬 이론'에 기반한 자신의 증명을 발표했다.
1895	칸토어	집합론과 초한수에 관한 첫 번째 논문에서 이 정리를 기수의 선형 순서의 쉬운 결과로 언급했다. 그러나 그는 후자의 정리를 증명할 수 없었고, 이는 1915년에 하르토그스에 의해 선택 공리와 동치임이 밝혀졌다.
1896	슈뢰더	(제본스의 정리의 따름 정리로) 증명을 발표했다.
1897	베른슈타인	칸토어의 세미나에 참여하던 19세 학생으로, 자신의 증명을 제시했다.
1897	슈뢰더	거의 동시에, 그러나 독립적으로 증명을 찾았다.
1897	데데킨트	베른슈타인의 방문 후, 독립적으로 두 번째 증명을 발견했다.
1898	베른슈타인	보렐의 함수에 관한 책(1897년 취리히 국제 수학자 회의에서 칸토어에 의해 전달됨)과 자신의 학위 논문을 통해 증명을 발표했다(선택 공리에 의존하지 않음).
1898	슈뢰더	자신의 증명을 출판했다.
1902	코르셀트	슈뢰더의 증명에 결함이 있음을 발견했다(슈뢰더 사망 직전 확인). 코르셀트의 논문은 1911년에 출판되었다.

데데킨트의 두 증명은 모두 그의 유명한 1888년 논문 "Was sind und was sollen die Zahlen?"에 기반하며, 칸토어의 논문의 C 명제와 동치인 명제, 즉 "A ⊆ B ⊆ C 이고 |A| = |C| 이면 |A| = |B| = |C| 이다"라는 명제의 따름 정리로 이끌어냈다. 칸토어는 1882년 또는 1883년에 집합론과 초한수 연구 중에 이 속성을 관찰했으며, 따라서 (암묵적으로) 선택 공리에 의존하고 있었다.

4.2. 명칭 문제

이 정리의 명칭은 역사적으로 여러 이름으로 불려왔다. 전통적으로는 "슈뢰더-베른슈타인 정리"라는 이름이 사용되었는데, 이는 1898년에 슈뢰더와 베른슈타인이 각각 독립적으로 증명을 발표한 것에 기인한다.

그러나 이 정리의 명칭에는 몇 가지 논쟁점이 있다. 칸토어는 1887년에 이 정리를 처음 언급했지만 증명을 제시하지는 않았다. 그럼에도 그의 선구적인 역할을 인정하여 "칸토어-베른슈타인 정리"라고 부르기도 한다. 베른슈타인에 따르면, 칸토어는 이 정리에 대해 "동치 정리"(Äquivalenzsatz^독일어)라는 이름을 제안했다고 한다.

한편, 슈뢰더의 이름이 포함되는 것에 대해서는 비판적인 시각이 존재한다. 그가 1898년에 발표한 증명은 1902년 코르셀트에 의해 오류가 있음이 밝혀졌기 때문이다. 슈뢰더 본인도 오류를 인정했다.

더욱 복잡한 점은, 이 정리를 역사상 처음으로 증명한 사람은 데데킨트라는 사실이다. 그는 1887년에 선택 공리에 의존하지 않는 증명에 성공했지만, 이를 발표하거나 칸토어에게 알리지 않았다. 그의 증명은 나중에 체르멜로에 의해 발견되어 1908년에 알려졌다. 이처럼 최초 증명자임에도 불구하고 데데킨트의 이름은 이 정리의 명칭에 거의 포함되지 않는다.

수학 정리의 명칭이 항상 역사적 경위를 정확히 반영하는 것은 아니며, 칸토어-베른슈타인 정리 역시 그러한 사례 중 하나이다. 정리의 발견과 증명에 관련된 주요 인물과 시기는 다음과 같이 정리할 수 있다.

👆

좌우로 밀어서 보기

정리 증명 및 발표 관련 주요 연표
연도	인물	내용
1887	칸토어	정리를 발표했으나 증명은 포함하지 않음.
1887	데데킨트	선택 공리에 의존하지 않고 정리를 증명했으나 발표하지 않음.
1895	칸토어	첫 번째 집합론 논문에서 기수의 선형 순서(비교 가능성)의 결과로 정리를 언급. (선형 순서 자체는 증명 못함)
1896	슈뢰더	증명을 발표함.
1897	베른슈타인	칸토어 세미나에서 19세의 나이로 증명을 제시함.
1897	슈뢰더	베른슈타인과 거의 동시, 독립적으로 증명을 찾음.
1897	데데킨트	베른슈타인 방문 후 독립적으로 두 번째 증명을 발견함.
1898	베른슈타인	에밀 보렐의 저서 및 본인의 학위 논문을 통해 증명 발표.
1898	슈뢰더	자신의 증명을 출판함.
1902	코르셀트	슈뢰더의 1898년 증명에 결함이 있음을 발견 (1911년 발표).
1908	체르멜로	데데킨트의 미발표 증명을 발견하고, 이를 기반으로 자신의 증명을 발표.

데데킨트의 두 증명은 모두 그의 1888년 저서 "Was sind und was sollen die Zahlen?^독일어"에 나오는 '사슬 이론'에 기반하며, 다음과 같은 명제의 따름정리로 유도된다.
: A ⊆ B ⊆ C 이고 |A| = |C| 이면 |A| = |B| = |C| 이다.
칸토어는 이와 동등한 속성을 1882년 또는 1883년경 집합론 연구 중에 발견했지만, 이는 암묵적으로 선택 공리에 의존하는 것이었다.

결론적으로, "칸토어-베른슈타인 정리", "슈뢰더-베른슈타인 정리", 혹은 단순히 "베른슈타인 정리" 등 다양한 명칭이 사용되는 것은 이러한 복잡한 역사적 배경 때문이다.

5. 전제 조건

칸토어의 1895년 증명은 사실상 선택 공리에 의존했는데, 이는 이 결과를 정렬 정리의 따름정리로 추론했기 때문이다. 하지만 율리우스 쾨니히가 제시한 증명을 포함한 다른 증명들은 선택 공리를 사용하지 않고도 이 정리를 증명할 수 있음을 보여준다.

만약 선택 공리를 가정한다면, 두 집합 사이에 각각 전사 함수가 존재할 경우, 그 역함수들로부터 단사 함수를 구성하고 칸토어-베른슈타인 정리를 적용하여 두 집합 사이에 전단사 함수가 존재함을 보일 수 있다.

한편, 쾨니히의 증명은 배중률을 사용한다. 배중률을 받아들이지 않는 구성주의 수학, 특히 직관주의 집합론( ${\mathsf{IZF}}$ )에서는 칸토어-베른슈타인 정리가 성립하지 않을 수 있다. 실제로 이러한 체계에서 칸토어-베른슈타인 정리를 가정하면 배중률이 따라 나온다는 것이 증명되었다. 따라서 직관주의자들은 칸토어-베른슈타인 정리의 명제를 일반적으로 받아들이지 않는다.

이 정리의 다른 증명 방법으로는 타르스키의 고정점 정리를 이용하는 것이 있다.

6. 예시

칸토어-베른슈타인 정리는 두 집합 사이에 각각 단사 함수가 존재하면, 두 집합 사이에 전단사 함수도 존재함을 보장하며 그 함수를 구성하는 방법을 제시한다. 이 정리를 이용하여 다양한 무한 집합들 사이의 크기가 같음을 보이고 구체적인 전단사 함수를 만들 수 있다.

아래는 칸토어-베른슈타인 정리를 이용한 전단사 함수 구성의 구체적인 예시들이다.

* 닫힌 구간 [0, 1]과 반열린 구간 [0, 1) 사이의 전단사 함수
* 반열린 구간 [0, 2)와 단위 정사각형 [0, 1)² 사이의 전단사 함수
* 반열린 구간 [0, ∞)과 열린 구간 (0, ∞) 사이의 전단사 함수

6.1. [0, 1] → [0, 1) 전단사 함수

참고: $[0, 1)$ 은 0을 포함하고 1을 제외하는 0에서 1까지의 반열린 구간이다.

닫힌 구간 $[0, 1]$ 에서 반열린 구간 $[0, 1)$ 으로 가는 단사 함수 $f: [0, 1]\to[0, 1)$ 를 $f(x)=x/2$ 로 정의하고, 반대로 $[0, 1)$ 에서 $[0, 1]$ 로 가는 단사 함수 $g: [0, 1 )\to [0, 1]$ 를 $g(x)=x$ 로 정의할 수 있다.

칸토어-베른슈타인 정리의 구성적 증명 절차에 따라, 다음과 같이 집합 $C$ 를 정의한다.
$C_0=\{1\}$
$C_k=\{2^{-k}\}$ (여기서 $k=0, 1, 2, ...$ )
$C = \bigcup_{k=0}^\infty C_k = \{1, \tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, ... \}$

이제 $[0, 1]$ 에서 $[0, 1)$ 로 가는 전단사 함수 $h(x)$ 를 다음과 같이 정의할 수 있다.
$h(x) = \begin{cases} f(x) = \frac{x}{2} , & x \in C \text{ 일 때} \\ x , & x \in [0, 1] \setminus C \text{ 일 때}\end{cases}$

이 함수 $h(x)$ 는 $x$ 가 집합 $C$ (즉, $1, 1/2, 1/4, ...$ )의 원소이면 그 값을 $f(x)$ 에 따라 절반으로 만들고 ( $1 \to 1/2, 1/2 \to 1/4, ...$ ), $C$ 의 원소가 아니면 그대로 둔다 ( $g^{-1}(x)$ 에 해당하지만 여기서는 $g$ 가 항등함수이므로 $x$ 가 된다). 결과적으로 $1$ 은 $1/2$ 로, $1/2$ 은 $1/4$ 등으로 이동하며 $1$ 이 빠진 구간 $[0, 1)$ 의 모든 원소와 일대일 대응을 이룬다.

6.2. [0, 2) → [0, 1)² 전단사 함수

반열린 구간 $[0, 2)$ 에서 열린 단위 정사각형 $[0, 1 )^2$ 으로 가는 단사 함수 $f$ 를 다음과 같이 정의할 수 있다.
$f(x)=(x/2, 0)$

반대로, $[0, 1 )^2$ 에서 $[0, 2)$ 로 가는 단사 함수 $g$ 도 정의할 수 있다. $(x, y) \in [0, 1 )^2$ 에 대해, $x$ 와 $y$ 를 각각 십진법 소수로 다음과 같이 전개한다. (단, 소수 표현의 유일성을 위해 무한소수 표현을 사용한다고 가정한다. 예: 0.5 대신 0.499...)
$x = \sum_{k=1}^\infty a_k \cdot 10^{-k} = 0.a_1 a_2 a_3 \dots$
$y = \sum_{k=1}^\infty b_k \cdot 10^{-k} = 0.b_1 b_2 b_3 \dots$
여기서 $a_k, b_k$ 는 0부터 9까지의 정수이다 ( $a_k, b_k \in \{0, 1, ..., 9\}$ ).

이제 함수 $g$ 를 다음과 같이 정의한다. 이는 $x$ 와 $y$ 의 소수점 아래 자릿수를 번갈아 배열하여 새로운 소수를 만드는 방식이다.
$g(x, y) = \sum_{k=1}^\infty (10 \cdot a_k + b_k) \cdot 10^{-2k} = 0.(10a_1+b_1)(10a_2+b_2)\dots$ (여기서 각 $(10a_k+b_k)$ 는 두 자리 숫자로 간주)
이 함수 $g$ 는 $[0, 1 )^2$ 에서 $[0, 1)$ 로 가는 단사 함수이다. (원본 소스에서는 $[0, 2)$ 로 간다고 되어 있으나, 함수의 정의상 치역은 $[0, 1)$ 이다. $[0, 2)$ 로 가는 단사 함수를 만들기 위해서는 예를 들어 $g'(x,y) = g(x,y)$ 또는 $g'(x,y) = g(x,y)+1$ 처럼 구간을 나누어 정의하거나, 아래의 $g_2$ 와 같이 정의해야 한다. 여기서는 원본 소스의 설명을 따라 $g$ 를 사용한 구성 과정을 설명한다.)
예를 들어, $g(\tfrac{1}{3}, \tfrac{2}{3}) = g(0.333..., 0.666...) = 0.(10 \cdot 3 + 6)(10 \cdot 3 + 6)... = 0.363636... = \tfrac{36}{99} = \tfrac{4}{11}$ 이다.

칸토어-베른슈타인 정리에 따르면, 두 집합 사이에 각각 단사 함수 $f: [0, 2) \to [0, 1)^2$ 와 $g: [0, 1)^2 \to [0, 2)$ 가 존재하므로 (여기서 $g$ 는 위에서 정의한 $[0, 1)^2 \to [0, 1)$ 함수를 이용하여 $[0, 2)$ 로 가는 단사 함수로 확장 가능하다고 가정), 두 집합 사이에 전단사 함수 $h: [0, 2) \to [0, 1)^2$ 가 존재한다. 이 $h$ 는 $f$ 와 $g$ (의 역함수 $g^{-1}$ )를 이용하여 구성할 수 있다.

구성 과정에서 사용되는 집합 $C$ 는 다음과 같이 정의된다. (원본 소스의 $C_0 = [1, 2)$ 정의는 $g$ 의 치역이 $[0, 1)$ 라고 가정할 때 $[0, 2) \setminus g([0, 1)^2)$ 의 일부 또는 전부를 나타내는 것으로 해석될 수 있다.)
$C_0 = [1, 2)$ (원본 소스 표기)
$C_1 = g(f(C_0)) = g(\{ (x/2, 0) \mid x \in [1, 2) \}) = g(\{ (x', 0) \mid x' \in [\tfrac{1}{2}, 1) \})$
$C_k = g(f(C_{k-1}))$ for $k \ge 1$
$C = \bigcup_{k=0}^\infty C_k$

전단사 함수 $h$ 는 다음과 같이 정의된다.
$h(x) = \begin{cases} f(x), & \text{if } x \in C \\ g^{-1}(x), & \text{if } x \notin C \text{ (즉, } x \in [0, 2) \setminus C \text{)} \end{cases}$
이 구성 방법에서 $C_0 = [1, 2)$ 는 비교적 간단하지만, $C_1 = g(\{ (x', 0) \mid x' \in [\tfrac{1}{2}, 1) \})$ 만 해도 그 형태가 상당히 복잡해진다.

참고로, $[0, 1)^2$ 에서 $[0, 2)$ 로 가는 전단사 함수를 직접 정의하여 더 간단하게 전단사 함수 $h$ 를 찾는 방법도 있다. 예를 들어 함수 $g_2$ 를 다음과 같이 정의한다.
$g_2(x, y) = 2 \cdot \sum_{k=1}^\infty (10 \cdot a_k + b_k) \cdot 10^{-2k}$
이 함수 $g_2$ 는 (십진법 표현의 유일성 문제를 해결한다는 가정 하에) 그 자체로 $[0, 1)^2$ 에서 $[0, 2)$ 로 가는 전단사 함수이다. 이 $g_2$ 를 사용하면, 칸토어-베른슈타인 정리의 구성 과정에서 집합 $C$ 는 공집합( $\emptyset$ )이 되고, 결과적으로 모든 $x \in [0, 2)$ 에 대해 전단사 함수는 $h(x) = g_2^{-1}(x)$ 로 간단히 주어진다.