カントールの往復論法

以下のとおりだとみなす。

• (A, ≦_A) と (B, ≦_B) は、全順序集合である。
• A、B は、最大元および最小元を有しない。
• A、B は、稠密に順序付けられている、つまり、任意の 2 元の間には他の元が少なくとも 1 つ存在する。
• A、B は、可算無限濃度である。

A、B の元を重なりなく以下のとおり列挙し、これを固定する。

A = {a₁, a₂, a₃, …}

B = {b₁, b₂, b₃, …}

ここで、A と B の間に、狭義単調増加な一対一対応を構成しよう。 初期状態では、A のどの要素も B の元と対応付けられていない。

(1)　i を、B の如何なる要素とも対応付けられていない a_i のうちの最小の添字とする。 j を、A の如何なる要素とも対応付けられていない b_j であって、かつ a_i が b_j と対応付けても、対応付けが狭義単調であるという要件を満たすことができるものとする。 このとき、a_i と b_j を対応付ける。

(2)　j を、A の如何なる要素とも対応付けられていない b_j のうちの最小の添字とする。 i を、B の如何なる要素とも対応付けられていない a_i であって、かつ b_j が a_i と対応付けても、対応付けが狭義単調であるという要件を満たすことができるものとする。 このとき、b_j と a_i を対応付ける。

(3)　手続き (1) に戻る。

手続き (1) と (2) で要求される選択を、実際に要件に合致しつつ行うことができるかの検証が、依然として残っている。 手続き (1) を例に取ると、以下のとおりである。

既に、A の中の a_p と a_q および夫々に対応する B の中の b_p と b_q が存在し、かつ a_p ＜ a_i ＜ a_q および b_p ＜ b_q であれば、 b_j は、稠密性を使って、 b_p と b_q の間に選ぶ。 そうでない場合には、B が 最大元も最小元も有しないという性質を使って、適当に大きいまたは小さい B の要素を選ぶ。 手続き (2) の選択も、双対的に可能である。 最後に、A と B は可算無限集合だから、この構成は、可算無限回の後に終了する。 全ての前提条件を使用しなければならないことに注意されたい。

往復せずに手続き (1) を繰り返すだけでは、結果として得られる対応が全単射にならない。

• 数学基礎論