ものの並べ方

質問

『やさしいコンピュータ科学』（Alan W. Biermann著、アスキー出版社）のなかで、
どうしてもわからない部分があります。

＊＊＊
"computers"、"#!-7"、"Let us go."のような出力可能な有限数の文字列の場合でも、長さゼロの文字列を箱1に入れ、長さ1の文字列を箱2、箱3、箱4、箱5、…箱nに、という具合に次々と並べることが出来る。この場合、有限数の異なる文字だけを考えているからである。次に、長さ2の文字列は、箱n+1、n+2などに記憶できる。
＊＊＊

この「長さ1」とはどういうことですか。
"computers"であれば、"c"や"m"などのアルファベット1文字が「長さ1」なのか、
"computers"が「長さ1」なのかがわかりません。

そして、「長さ2」や「長さ3」とは具体的にはどういうものですか。
"computers"が「長さ1」だとしたら、「長さ2」というのはイメージできません。
（"c"や"m"などのアルファベット1文字が「長さ1」だとしたら、
　"ac"や"bb"が「長さ2」なのかなと思っています。）

また、この本の続きに、以下の文がいてあります。

＊＊＊
こうなると、いくつかの非常に大きな集合が一列に並べられると思う人がいるかもしれない。ところが、正の整数を入力すると正の整数の答が出るような関数は並べられない。それらをいくら箱のなかに詰め込もうとしても、箱に入りきれないほど膨大な数になってしまう。
＊＊＊

これを具体的にわかりやすく説明しなおしていただけませんか。
「正の整数を入力すると正の整数の答が出るような関数は並べられない」とはどういうことでしょうか。また、これを証明するとしたら、どうなるのでしょうか。

以上、よろしくお願い致します。

回答No.1

kabaokaba

その本は知らないし，
あなたの数学的な素養も不明なのですが・・・

>正の整数を入力すると正の整数の答が出るような関数は並べられない

正の整数の集合は無限集合である．そして
正の整数から正の整数への関数全体は
正の整数のべき集合そのものである．
そのような関数全体のなす集合は，
正の整数全体のなす集合よりも大きい，
正確に言えば，集合としての濃度が大きいので
今までのように整数で（自明な）番号付けをして
並べることはできない

こーいうような意味だと思う．

補足

> あなたの数学的な素養も不明なのですが・・・
素養はありません。

> 正の整数から正の整数への関数全体は
> 正の整数のべき集合そのものである．
> そのような関数全体のなす集合は，
> 正の整数全体のなす集合よりも大きい
ということを、より定性的に説明していただければ幸いです。