Zornの補題⇒濃度比較可能定理の証明

集合論p222、Zorn補題⇒濃度比較可能の証明。帰結は対称な形をしているので、証明も対称に書くことを試みた。

(証明)\(X\times Y\)上の二項関係で、その任意の元\(\langle x_1,y_1\rangle,\langle x_2,y_2\rangle\)に対し\(x_1=x_2\leftrightarrow y_1=y_2\)を満たすものの全体を\(\mathcal M\)とする。\(\mathcal M\)の元\(M\)について、\[D_X(M)=\{x\in X|\exists y\in Y[\langle x,y\rangle\in M]\},\]\[D_Y(M)=\{y\in Y|\exists x\in X[\langle x,y\rangle\in M]\}\]とすると、\(M\)は\(D_X(M)\)から\(D_Y(M)\)への全単射となっている。

\(\mathcal M\)の元を集合の包含関係で並べた半順序を考える。半順序集合\(\mathcal M\)の部分集合で全順序をなすもの\(\mathcal C\)を任意にとる。\(\mathcal C\)のすべての元の和集合\(\bigcup\mathcal{C}\)の任意の元\(\langle x_1, y_1\rangle,\langle x_2,y_2\rangle\)に対し、各々を要素に持つ\(A_1,A_2\in\mathcal{C}\)がそのつど存在し、その少なくとも一方が他方を包含する。すなわち、両順序対を同時に要素として持つ\(\mathcal M\)の要素が存在するから、\(x_1=x_2\leftrightarrow y_1=y_2\)が成り立つ。したがって\(\bigcup\mathcal{C}\in\mathcal{M}\)であり、\(\bigcup\mathcal{C}\)は\(\mathcal M\)における\(\mathcal C\)の上界となる。

以上により\(\mathcal M\)は帰納的集合であることが分かったから、Zorn補題によって\(\mathcal M\)は極大元\(M_0\)を持つ。いま\(X\backslash D_X(M_0)\)と\(Y\backslash D_Y(M_0)\)がともに非空であると仮定すると、各々からひとつずつとった要素からなる順序対を\(M_0\)に付け加えたものを考えることにより、\(M_0\)の極大性に反することが分かる。したがって両者の少なくとも一方は空であり、これは\(X\)と\(Y\)の少なくとも一方から他方への単射が存在することを意味する。■