伯恩斯坦引理的证明
伯恩斯坦引理：若 \({\rm card} X\le {\rm card} Y\) 且 \({\rm card} Y\le {\rm card} X\)，则 \({\rm card} X={\rm card} Y.\)
证明：由条件得存在单射 \(f\colon X\longrightarrow Y\) 和 \(g\colon Y\longrightarrow X\)，取 \(g\) 的一个左逆 \(h\colon X\longrightarrow Y.\)
令 \(X_1=X-g(Y)\)，定义记号 \(A'=X_1\cup(g\circ f)(A)\)，集族 \(\mathcal F=\{A\in\mathcal P(X)\mid A'\subset A\}.\)
(1) 因为 \(X\in \mathcal F\)，所以 \(\mathcal F\) 非空.
(2) 若 \(A\in \mathcal F\)，则 \(A'\subset A.\) 因此
即 \(A'\in \mathcal F.\)
(3) 令 \(A^{*}=\bigcap\limits_{A\in \mathcal F}A\).
对于任意 \(A\in \mathcal F\)，有 \(X_1\cup(g\circ f)(A)\subset A\)，从而
因此 \(A^{*}\in \mathcal F.\)
(4) 因为 \(A^{*}\in\mathcal F\)，所以 \((A^{*})'\in\mathcal F\)，所以 \(A^{*}=\bigcap\limits_{A\in \mathcal F}A\subset (A^{*})'.\) 而 \((A^{*})'\subset A^{*}\)， 因此 \(A^{*}=(A^{*})'.\)
(5) 构造映射 \(\phi\colon X\longrightarrow Y,\)
(6) 任给 \(x_1,x_2\in X\) 且 \(x_1\ne x_2\)，
若 \(x_1\in A^{*},x_2\in X-A^{*}\)，则 \(g(f(x_1))\in (g\circ f)(A^{*})\subset A^{*}\)；因为 \(x_2\not\in A^{*}\supset X_1\)，所以 \(x_2\in g(Y)\)，所以存在 \(y\in Y\) 使得 \(x_2=g(y)\)，从而 \(h(x_2)=(h\circ g)(y)=y\)，因此 \(g(h(x_2))=g(y)=x_2\in X-A^{*}\)，所以 \(g(f(x_1))\ne g(h(x_2))\)，于是 \(f(x_1)\ne g(x_2)\)，即 \(\phi(x_1)\ne \phi(x_2).\)
若 \(x_1\in X-A^{*},x_2\in A^{*}\)，同理有 \(\phi(x_1)\ne \phi(x_2).\)
若 \(x_1,x_2\in A^{*}\)，因为 \(f\) 是单射，所以 \(f(x_1)\ne f(x_2)\)，即 \(\phi(x_1)\ne \phi(x_2)\).
若 \(x_1,x_2\in X-A^{*}\)，由上可知 \(g(h(x_1))=x_1\ne x_2=g(h(x_2))\)，从而 \(h(x_1)\ne h(x_2)\)，即 \(\phi(x_1)=\phi(x_2).\)
综上 \(\phi(x_1)\ne \phi(x_2)\)，从而 \(\phi\) 为单射.
(7) 任给 \(y\in Y\)，
若 \(g(y)\in A^{*}\)，则 \(g(y)\in X_1\cup (g\circ f)(A^{*})\)，因为 \(g(y)\in g(Y)\)，所以 \(g(y)\not\in X_1\)，从而 \(g(y)\in (g\circ f)(A^{*})\)，即存在 \(x\in A^{*}\)，使得 \(g(y)=(g\circ f)(x)=g(f(x))\). 因为 \(g\) 是单射，所以 \(y=f(x)=\phi(x).\)
若 \(g(y)\in X-A^{*}\)，则 \(y=h(g(y))=\phi(g(y)).\)
综上，总存在 \(x\in X\)，使得 \(y=\phi(x)\)，从而 \(\phi\) 是满射.
(8) 由 (6)，(7) 得 \(\phi\) 是双射，即得 \({\rm card} X={\rm card} Y.\)