슈뢰더-베른슈타인 정리

By | April 24, 2016

유한집합의 경우 두 집합의 크기를 비교할 때에는 원소의 개수를 세어 비교하면 된다. 그러나 무한집합의 경우 원소의 개수를 끝까지 셀 수 없으므로 다른 방법으로 두 집합의 크기를 비교한다.

두 집합 \(X,\) \(Y\)에 대하여 일대일 대응 \(f : X \to Y \)가 존재할 때 \(X\)와 \(Y\)는 대등하다(equipotent) 또는 동등하다고 말하고, 이것을 기호로는 \(X \approx Y\)로 나타낸다. 책에 따라서는 두 집합 \(X,\) \(Y\)가 대등한 것을 \(X \sim Y\)로 나타내기도 한다.

두 집합 \(X,\) \(Y\)에 대하여 일대일 함수 \(f : X \to Y\)가 존재하면 \(Y\)의 원소의 개수는 \(X\)의 원소의 개수보다 많거나 또는 그 둘은 서로 같다. 이것을 기호로는 \(X \preccurlyeq Y\) 또는 \(Y \succcurlyeq X\)로 나타낸다.

\(x\)와 \(y\)가 실수일 때, \(x \leq y\)이면서 동시에 \(x \geq y\)이면 \(x=y\)가 성립한다. 집합에 대해서도 비슷한 생각을 할 수 있다. \(X\)와 \(Y\)가 집합일 때, \(X \preccurlyeq Y\)이면서 동시에 \(X \succcurlyeq Y\)이면 \(X \approx Y\)가 성립할 것을 예상할 수 있다. 직관적으로는 자명하지만, 이 정리의 증명은 간단하지 않다.

슈뢰더-베른슈타인 정리.

집합 \(X,\) \(Y\)에 대하여 \(X \preccurlyeq Y\)이고 동시에 \(X \succcurlyeq Y\)이면 \(X \approx Y\)가 성립한다.

증명.\(X \preccurlyeq Y\)이고 \(X \succcurlyeq Y\)이므로 두 일대일 함수 \(f : X \to Y\)와 \(g : Y \to X\)가 존재한다. 이제 두 집합 \(X,\) \(Y\) 사이의 일대일 대응이 존재함을 보여야 한다. 일반성을 잃지 않고 \(X,\) \(Y\)가 서로소라고 하자. [일반성을 잃지 않는 이유는, 만약 서로소가 아니라면 \[X ' := X \times \left\{ 0 \right\} , ~~ Y' := Y \times \left\{ 1 \right\}\]라고 한 뒤 \(X',\) \(Y'\)에 대하여 논하면 되기 때문이다.]

\(y \in Y \)와 \(x \in X\)에 대하여 \( g(y) = x\)가 성립할 때 \(y\)를 \(x\)의 선행자(parent)라고 부르자. 마찬가지로 \(x \in X \)와 \( y \in Y \)에 대하여 \(f(x) = y\)가 성립할 때 \(x\)를 \(y\)의 선행자(parent)라고 부르자. 선행자의 정의에 의하여 \(X,\) \(Y\)의 각 원소는 많아야 하나의 선행자를 가진다.

\(z \in X \cup Y\)로부터 시작하여 선행자를 이어서 나열하여 만든 순서쌍 \[ \left( z_0 , ~ z_1 , ~ \cdots , ~ z_n \right) \]을 \(z\)의 선행자 사슬(parent chain)이라고 부르자. 즉 \(z_0 = z \)이며, 각 \(i = 0 , ~ \cdots , ~ n-1 \)에 대하여 \(z_{i+1}\)은 \(z_i\)의 선행자이다. 이 사슬의 길이(length)를 \(n\)으로 정의하자. (즉 사슬의 길이는 성분의 개수가 아니라 대응의 횟수이다.) 여기서 재미있는 사실은 선행자 사슬의 성분은 두 집합 \(X,\) \(Y\)의 원소가 번갈아가면서 나타난다는 점이다.

이제 각 원소 \(z\)에 대하여 두 가지 경우를 생각할 수 있다. 임의의 자연수에 대하여 \(z\)의 선행자 사슬의 길이가 그 자연수보다 더 긴 것이 존재하는 경우, \(z\)의 깊이(depth)를 무한대로 정의하자. 그렇지 않은 경우 \(z\)의 선행자 사슬 중 그 길이가 가장 긴 것이 유일하게 존재하는데, 바로 그 선행자 사슬의 길이를 \(z\)의 깊이(depth)로 정의하자. 물론, \(z\)의 선행자가 존재하지 않는 경우에는 \(z\)의 깊이를 \(0\)으로 정의한다.

\(X\)의 원소 중에서 깊이가 짝수인 것들의 모임을 \(X_e \)로 나타내고, \(X\)의 원소 중에서 깊이가 홀수인 것들의 모임을 \(X_o\)로 나타내자. 또한 \(X\)의 원소 중에서 깊이가 무한대인 것들의 모임을 \(X_ \infty \)로 나타내자. \(Y_e , \) \( Y_o , \) \(Y_ \infty \)에 대해서도 마찬가지로 정의하자.

\(x \in X\)의 깊이가 유한이라면 \(f(x)\)의 깊이는 \(x\)의 깊이에 \(1\)을 더한 것과 같다. \(x\in X\)의 깊이가 무한이라면 \(f(x)\)의 깊이도 무한이다. 그러므로 함수 \(f\)는 \[ f : X_e \to Y_o , ~~ f : X_o \to Y_e , ~~ f : X_ \infty \to Y_\infty \]로 대응시킨다. \(Y\)의 원소에 대하여 \(g\)도 마찬가지로 작용한다. 더욱이 \(Y_o \)와 \(Y_\infty \)의 각 원소들은 선행자를 가지므로 \(f\)에 의한 대응 \[ f : X_e \to Y_o , ~~ f : X_\infty \to Y_\infty \]는 일대일 대응이다. [그러나 \(Y_e \)의 원소는 선행자를 갖지 않을 수도 있으므로 대응 \( f : X_o \to Y_e \)는 일대일 대응이 아닐 수도 있다.]

이제 함수 \(h : X \to Y\)를 다음과 같이 정의하자. \[ h(x) := \begin{cases} f(x)~~ &\mbox{if} ~~ x \in X_e \cup X_\infty \\ \\ g^{-1} (x) ~~ &\mbox{if} ~~ x \in X_o \end{cases} \]그러면 \(h\)는 일대일 대응이 된다.

위 정리는 관계 \(\preccurlyeq\)가 순서의 성질을 가지고 있음을 나타낸다.

따름정리 1.

\(X\)가 집합족이고 \(X \ne \emptyset \)이라고 하자. 또한 상집합 \(X / \approx \)의 임의의 두 원소 \([A], \) \([B]\)에 대하여 \[ [A] \preccurlyeq [B] ~~ \Longleftrightarrow ~~ A \preccurlyeq B \]인 것으로 정의하자. 그러면 \( \preccurlyeq \)는 \(X / \approx \)에서 순서관계이다.

증명.명백히 \( \preccurlyeq \)는 순서관계의 세 가지 조건을 모두 만족시킨다. 먼저 \(X / \approx \)의 임의의 원소 \([A] \)에 대하여

\([A] \preccurlyeq [A] \)

이므로 \(\preccurlyeq\)는 반사적이다. 다음으로 \(X / \approx \)의 임의의 원소 \([A] , \) \([B] \)에 대하여

\( ( [A] \preccurlyeq [B] ~\wedge ~ [B] \preccurlyeq [A] ) ~~ \) \( \Rightarrow ~~ (A \preccurlyeq B ~ \wedge ~ B \preccurlyeq A ) ~~ \) \( \Rightarrow ~~ A ~\approx~ B ~~ \) \( \Rightarrow ~~ [A] = [B] \)

이므로 \(\preccurlyeq\)는 반대칭적이다. 끝으로 \(X / \approx \)의 임의의 원소 \([A] , \) \([B] , \) \([C] \)에 대하여

\( ( [A] \preccurlyeq [B] ~ \wedge ~ [B] \preccurlyeq [C] ) ~~ \) \( \Rightarrow ~~ ( A \preccurlyeq B ~\wedge~ B \preccurlyeq C ) ~~ \) \( \Rightarrow ~~ A \preccurlyeq C ~~ \) \(\Rightarrow ~~ [A] \preccurlyeq [C] \)

이므로 \( \preccurlyeq \)는 추이적이다.

따름정리 2.

\(CD\)가 모든 기수들의 모임이고 \(X\)가 \(CD\)의 부분집합이라고 하자. 그러면 \( \preccurlyeq \)는 \(X\)에서 순서관계이다.

증명.임의의 기수 \(x,\) \(y\)에 대하여 \[x \approx y ~~ \Longleftrightarrow ~~ x=y \] 이므로 \(X / \approx \)의 임의의 원소 \([x],\) \([y]\)에 대하여 \[ [x] = [y] ~~ \Longleftrightarrow ~~ x = y \] 이다. 따라서 대응 \( [x] ~\mapsto~ x \)는 \(X / \approx\)로부터 \(X\)로의 순서동형사상이다.

따름정리 1에 의하여 \( \preccurlyeq \)가 \(X / \approx\)에서 순서관계이므로 \( \preccurlyeq \)는 \(X\)에서 순서관계이다.

따름정리 2에서 \( \preccurlyeq \)를 \(CD\)에서의 순서관계라고 하지 않고 \(CD\)의 부분집합인 \(X\)에서의 순서관계라고 한 이유는 \(CD\)가 고유 클래스(proper class)이기 때문이다(Cantor's paradox).

Schreibe einen Kommentar