プロが教える店舗&オフィスのセキュリティ対策術

2つの可算無限集合においてその直積は可算無限集合であるということ{f(i,j)=1/2(i+j-1)(i+j-2)+j}を数列、または格子を使って証明するにはどうしたらよいか教えてください。

A 回答 (2件)

格子を使って説明する方法はたとえば「無限と連続」遠山啓著の分数が,可算無限個である証明で出てきます.


m/n(n,mは自然数)という分数の場合,
横軸にmを縦軸にnを配置します.
任意の分数j/kは横軸j縦軸kの交点という格子点で
表せます.あとは,この格子点をたとえば
1/1 1/2 2/1 1/3 2/3 3/3 ・・・1/n 2/n ・・・ n-1/n ・・・
のようにたどると,自然数と全単射が作れるので(但し,1/2=2/4=3/6・・・のように同じ数のときは飛ばすようにする必要がある.)この分数と自然数の濃度は同じといえます.

直積の場合も同じ(分数の時のように飛ばして数えることがないので分かりやすいと思います.)考えで,全単射を作れます.
∀(n,m)∈N×N(記号がなかったのでかけるで代用)
に対して, k∈Nを
k(n,m)=n+Σ(j=1 to m-1)j
とすれば,全単射となります.
    • good
    • 0
この回答へのお礼

ありがとうございます。参考になりました。このやり方で考えてみます。

お礼日時:2005/05/12 01:38

可算無限集合であることを証明するためには、(i,j)と1,2,3,....の間に一対一の対応があることを証明すればいいのです。


そして、この問題では、ご親切に、具体的にf(i,j)=1/2(i+j-1)(i+j-2)+jという対応を与えてくれています。つまり、この関数自身が、(i,j)と1,2,3,....の間の一対一対応になっているのです。

それを証明しましょう。
まず、(i+j-1)か(i+j-2)のどちらかが偶数になるので、f(i,j)は自然数です。ここで、f(i,j)=f(k,l)かつ、i≠k,j≠lと仮定して、矛盾を導くのが一番簡単なやり方です。

つまり、f(i,j)が自然数で、値が重ならないことを示してやればいいのです。
背理法使わなくても出来ます。
f(i,j)<f(i+1,j)<f(i,j+1)<f(i+1,j+1)
という関係が成り立つ(i,j)→Zへの写像fを作れば帰納的に証明できます。実際にこの関数fはそうなっています。
f(i,j+1)<f(i+1,j+1)
f(i,j)<f(i+1,j)
は、ほとんど自明ですね。
f(i+1,j)-1=f(i,j+1)は、すぐにわかります。よって、
f(i+1,j)<f(i,j+1)
です。
以上より、
f(i,j)<f(i+1,j)<f(i,j+1)<f(i+1,j+1)
が成立。また、
f(1,1)=1<f(2,1)=2<f(1,2)=3<f(2,2)=5
より、帰納法を用いて証明できた。
となります。
    • good
    • 0
この回答へのお礼

ありがとうございます☆すっきりしてて分かりやすいないようでした。自分なりにもう一度考えてみます。

お礼日時:2005/05/12 01:40

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!