24/06/16 11:35:50.97 u+1dTVIO.net
H. L. Royden著『Real Analysis Third Edition』
p.23 Problem 26
選択公理と再帰的定義の一般化された原理を使って、各無限集合 X は可算無限部分集合を含むことを示せ。
この問題ですが、松坂和夫著『集合・位相入門』では、選択公理を使って示しています。
ですが、再帰的定義については当たり前のこととして何も注意していません。
一般化された再帰的定義の原理とは、
X を集合とする。
各自然数 n に対して f_n を X^n から X への関数とする。
a ∈ X とする。
そうすると、 X の列 <x_i> で x_1 = a および x_{i+1} = f_i(x_1, …, x_i) であるようなものが一意的に存在する。
この原理を使うと解答は以下のようになります。
X のすべての部分集合からなる集合を P(X) と書く。
M を P(X) から空集合を除いた集合とする。
選択公理によって、 M から X への写像 g で g(A) ∈ A であるようなものが存在する。
ｎ を任意の自然数とする。
X^n から X への関数 f_n を以下で定義する。
f_n(x_1, …, x_n) = g(X - {x_1, …, x_n})
a を X の任意の元とする。
一般化された再帰的定義の原理により、 X の列 <x_i> で
x_1 = a, x_{i+1} = f_i(x_1, …, x_i) を満たすようなものが一意的に存在する。
明らかに、 i ≠ j ならば x_i ≠ x_j である。
{x_1, ｘ_2, …} は X の可算無限部分集合である。