証明路開発支援システム(24) - 非専門的シンギュラリティー研究所

対角線論法(1)

前回の証明では、集合の元の個数より順序数の方が多いということを示していないので証明ができていないと思われます。「集合でないと成り立たないこと」を何か使わないといけないのですが、前回の証明ではそれを使っているのか不明です。集合の元の個数に関する議論なので、対角線論法を使えば良いのではないかと思うのですが、使っているのか不明です。

いったん対角線論法について調べてみます。wikipedia:カントールの対角線論法を参考にします。

対角線論法(集合による表現)

$X$ を集合、 $2^X$ を $X$ のべき集合とします。 $\psi$ を $X$ から $2^X$ への写像とします。 $X$ の部分集合 $Y$ を
$Y = \{ x \in X \mid x \notin \psi(x) \}$
と定義します。このとき $\psi(x) = Y$ となる $x \in X$ は存在しません。

[証明]

がを満たすとすると
- $x \in Y \iff x \notin \psi(x) \iff x \notin Y$ となり矛盾。
よって $\psi(x) = Y$ となる $x \in X$ は存在しません。

対角線論法(関数による表現)

$X$ を集合、 $\varphi: X \times X \rightarrow \{0,1\}$ を写像とします。
$\varphi(x, y)$ を $\varphi_{x}(y)$ と書くと、各 $x \in X$ に対し $\varphi_{x}$ は $X$ から $\{0, 1\}$ への写像となります。 $g: X \rightarrow \{0, 1\}$ を
$g(x) = \neg \varphi_{x}(x)$
と定義します。ここで、「 $\neg$ 」は $0$ と $1$ を反転する写像とします( $\neg b = 1 - b$ )。このとき、 $\varphi_{x} = g$ となる $x \in X$ は存在しません。

[証明]

がを満たすとすると
- $g(x) = \varphi_{x}(x) = \neg g(x)$ となり矛盾。
よって $\varphi_{x} = g$ となる $x \in X$ は存在しません。

整列可能定理の証明

前回の証明では、集合 $A$ の部分集合で整列集合であるものと順序数を対応させていました。集合 $2^A$ の部分集合で整列集合であるものに対応する順序数の中には、対角線論法により、集合 $A$ の部分集合で整列集合であるものに対応する順序数ではないものがあるので、それを見つければ証明ができると考えられます。しかしまだやり方は不明です。

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

作者:池上大祐
日本評論社