数学の濃度の問題

質問

どなたか、よろしくお願いいたします。

(1),|N*N|=|N|

NからN＊Nへ全単射の関数を規定したいです。
N*N=（ｍ,ｎ）｛m,n∈N｝

(2), N^k=｛(n1,n2,,nk)|ni∈N,1≦i≦k｝
|N^k|=|N|（帰納法を用いて）

a), K=1 のとき、|N|=|N|であり、明らか。
b), K=m で成り立っているとき、K=m+1でも題意が成り立つことを示す。
T=｛N^m｝S=｛N｝
|N^m|=|N| つまりこれは、f:S→T　全単射である。Si=Ti
N^(m+1)はN・Ti
これは、f:N→N^(m+1) g=N*f　関数gで表わせれる。
もし、Si=Ti であれば　gf(si)=N*Si=gf(ti)=N*Tiであり。これは全単射である。

雑すぎて自分でもよくわかっていません。。

(3)S=｛1,2,3,4.....,10^6｝ Tを全てのSの部分集合とする。f:T→Sを満たす、
1対1のfが存在しないことを示せ。

回答No.1

old_sho · ベストアンサー

（２）の部分ですが、記法が曖昧で何とも言い難いですね。要は、（１）の結果を利用するということではありませんか。

（１）の全単射をｇとして、 K=m で仮定の全単射は
f:N→N^m
この自然な拡張である
ｆ1:N*N→N^m*N
は、全単射である事は簡単に示せて、
ｆ1◦ｇ：N→N*N→N^(m+1)
が、全単射であることを示せば、終了ではないでしょうか。まあ、いろいろなもって行き方が可能ではあるしょうが。

（１）は、方眼紙に、左下を１にして、番号を同心円上に振って行き、横にどういう数列になるかを考えるのが楽しいのではないでしょうか。例えば、
９８７
４３６
１２５
これは、（１．１）＝１、（１，２）＝２、（１，３）＝５という対応です。
これもいくつも考え方があるでしょう。

（３）有限集合の部分集合の数は高校で勉強したでしょう。

お礼

よくわかりました。ありがとうございます。どれも単純な問題だったのですね。
この範囲はいまいちコンセプトが新しいのでわかりずらかったのですが、周辺知識が増えるにつれてだんだん理解できてきました。