数学の質問＆宿題○投げ場コミュの集合論の問題です

補題　２つの加算無限集合A、Bの直積A×Bは加算無限である

以下　Nは自然数全体を表すNとしてください（自然数全体のNは環境依存文字なので）
補題の証明
A～NかつB～Nとすれば、A×B～N×Nは明らかである。そこで、N×N～Nをいえばよい。いま、N×NからNへの関数ｆを以下のように定める（カントルの対関数）
ｆ(m,n)={(m+n)(m+n+1)/2}+m
図１．７より、fが全単射であることは容易にわかる

ここからが質問の問題です

補題の証明において、カントルの対関数f(m,n)がN×NからNへの全単射になることを示せ

証明をどこから手をつけてどのようなプロセスで進めれば良いのか全く分かりません。どなたかわかりやすく教えていただけたら嬉しいです。よろしくお願いいたします。

コメント(1)

最初
全て
最新の40件

[1] mixiユーザー 07月22日 09:35

N×NからNへの全射であること：0から順に1ずつ増える数を無限に数えるので、
fによるN×Nの像はNとなる。よって全射。

N×NからNへの単射であること：図１．７の数え方をみると異なる点は、異なる番号を付けている。よって単射。

単射について、もう少し詳しく。
図１．７の数え方は、
(0,2),(1,1),(2,0)のようにm+n=2なら３～５の番号、
(0,3),(1,2),(2,1),(3,0)のようにm+n=3なら６～９の番号、
というように、
m+nの値ごとに重ならない異なるグループの番号を付けているので、
m+nの値が異なれば番号も違う。
同じm+nの値ならmの値によって異なる番号を付けている。

ログインすると、みんなのコメントがもっと見れるよ