Bernsteinの定理のTarskiの不動点定理による簡潔な証明

Bernstein（ベルンシュタイン、ベアンシュタイン）の定理という集合論の基本定理があります。

定理（Bernstein）任意の集合 ${A, B}$ について、単射 ${f : A \to B,\ g : B \to A}$ があるならば、全単射 ${h : A \to B}$ が存在する。

一見単純そうですが、馬鹿でかい無限集合も考えないといけないので少々証明は厄介なようです。僕が数学書で見かけた中では 1.集合の無限列を作っていってそれらの和集合を取るもの*1、2.ジグザグジグザグ選択公理を行使して更にジグザグジグザグ*2 の2つの証明がありますが、1.はなんだかゴチャゴチャしていて、2.は直感的にわかりやすいけどきちんと証明を書こうとすると難しそう、という印象です。*3

そんな定理も忘れかけていた最近『型システム入門 (TaPL)』をきっかけにTarski（タルスキ）の不動点定理に出会って、ちょっと調べていたらTarsikiの不動点定理からBernsteinの定理を簡単に（選択公理も使わずに）証明できるということを知って、ちょっと感動しました。あまり有名でないようなので、ここで詳しく紹介しようと思います。なお、以下の内容は Tarski's Fixed Point Theorem, Wolfram MathWorld と型システム入門 p.222 の証明を簡単にまとめたものです。

まず、 ${A}$ の部分集合 ${X}$ を ${A}$ の部分集合に対応付ける関数 ${K(X) = A \setminus g \lbrack B \setminus f \lbrack X \rbrack \rbrack}$ を考えます。*4

そして2つの補題を作ります。

補題1（単調性）任意の ${X, Y \subset A}$ について、 ${X \subset Y}$ ならば ${K(X) \subset K(Y)}$ である。

補題2（不動点の存在） ${X_0 = K(X_0)}$ なる ${X_0 \subset A}$ が存在する。

では証明していきましょう。

（補題1の証明） ${X \subset Y}$ 。ゆえに ${f \lbrack X \rbrack \subset f \lbrack Y \rbrack}$ 。ゆえに ${B \setminus f \lbrack X \rbrack \supset B \setminus f \lbrack Y \rbrack}$ 。ゆえに ${g \lbrack B \setminus f \lbrack X \rbrack \rbrack \supset g \lbrack B \setminus f \lbrack Y \rbrack \rbrack}$ 。ゆえに ${K(X) = A \setminus g \lbrack B \setminus f \lbrack X \rbrack \rbrack \subset A \setminus g \lbrack B \setminus f \lbrack Y \rbrack \rbrack = K(Y)}$ 。（証明終わり）

（補題2の証明） 「補題1ならば補題2である」というのはTarskiの不動点定理の系なのですが、ここでは集合の場合に限って証明しておきます。*5 ${S = \lbrace X \subset A \mid X \subset K(X) \rbrace}$ とし、 ${X_0 = \bigcup S \subset A}$ とします。補題1より、 ${X_0 \subset K(X_0)}$ です。さらに補題1より ${K(X_0) \subset K(K(X_0))}$ であるので、 ${K(X_0) \in S}$ であり、 ${K(X_0) \subset X_0}$ となります。 ${X_0 \subset K(X_0)}$ かつ ${K(X_0) \subset X_0}$ より ${X_0 = K(X_0)}$ であるので、これが探していた不動点です。 *6 （証明終わり）

（定理の証明） 補題2より ${X_0 = A \setminus g \lbrack B \setminus f \lbrack X_0 \rbrack \rbrack}$ なので、 ${A \setminus X_0 = g \lbrack B \setminus f \lbrack X_0 \rbrack \rbrack}$ です。よって ${f, g}$ の制限 ${f' : X_0 \to f \lbrack X_0 \rbrack,\ g' : B \setminus f \lbrack X_0 \rbrack \to A \setminus X_0}$ はどちらも全単射になるので、全単射 ${h : A \to B}$ を ${h(x) = f'(x)\ \ \ (x \in X_0),\ \ \ g'^{-1}(x)\ \ \ (x \in A \setminus X_0)}$ として作ることができます。 *7 （証明終わり）

*1:教科書で普通採用されているのはこちらです

*2:Proofs from THE BOOK で知りました。König (1906) によるものであるとのことです。

*3:なお、Bernsteinの定理は選択公理を使わなくても証明できますが、ZFの直観主義論理版では証明できないということが知られています。

*4: ${f \lbrack X \rbrack}$ は ${X}$ の ${f}$ による像、 ${\setminus}$ は差集合を表します。

*5:以下の証明を束論における議論に修正するのは容易です。

*6:ただちに ${X_0}$ が ${K}$ の最大不動点であると分かります。同様にして最小不動点も作れます。

*7:Bernsteinの定理の証明にはいろいろありますが、この記事で紹介している証明はいずれも結局は ${A \setminus X_0 = g \lbrack B \setminus f \lbrack X_0 \rbrack \rbrack}$ なる ${X_0}$ （すなわち ${K}$ の不動点）を構築している、ということに注意してください。