〔定義〕Nを自然数全体の集合とします。今、ある関数f:N→{0,1}が、条件
「m,n∈Nをうまく選べば、i≧mを満たすすべてのiについてf(i+n)=f(i)である」
(※要するに、あるところから同じ有限部分列を無限に繰り返す)
を満たす時、無限数列{f(1),f(2),f(3),…,f(i),…}を仮に「有理列」と呼ぶ事にします。
同様に、条件を満たさない時は「無理列」と呼ぶ事にします。
質問は以下の2点(+α)です:
(1)有理列全体の集合は、可算ですか?
(2)もし可算だったなら、この集合の全ての有理列から対角線論法の要領で新たな無限数列{f_1(1),f_2(2),f_3(3),…,f_i(i),…}を構成した時、たとえどのように項を選んだとしても、必ず無理列になりますか?
(3)もしそうなら、項をうまく選べば、任意の無理列を構成できますか?
(4)もしよろしければ、以上の質問に関連したショートストーリを考えて下さい。
追記:
(2’)問(2)でできる無理列全体の集合は、非可算ですか?
(3’)問(3)において有理列の並べ方と無理数の間の対応関係はユニークですか?
私自身は、(1)可算、(2)必ず無理列になる、(3)任意は無理:任意の無理列が構成できると仮定すると恐らく(2)に矛盾、無理数に代数的数と超越数があるように、この方法で構成できない無理列があるのではないか、と考えてます。
追記:(3)は肯定的に解決されたようですhttp://q.hatena.ne.jp/1474976765#a1259369]
(3)無理列(有理列でもいいが)fにたいして、
f_k(n)=f(n) (n≦k) , 0 (n>k)
とすれば、f_kは有理列で、対角線のf_k(k)=f(k)なので無理列になります。
(1) 可算です。m, n, f(1), f(2), …, f(m), f(m+1), f(m+n-1)が決まればfは決まるので、例えばm+n, m, f(1), f(2), …, f(m), f(m+1), f(m+n-1)の辞書順に並べられます。
(2) なります。というより、なるように作るのが対角線論法です。
(3) 並べ方を固定した上で対角線論法で作るなら、対角線のどこかが一致するものは対角線論法によるものにはなりません。
それ以外であっても、具体的に定義できるものは可算しかありません。なぜなら定義は有限この文字列によって行うのですから。上につけたり下につけたりするのは例えばTeXの入力に直せば文字列です。「構成」というのをそういう意味にとるなら、不可算のものをすべては構成できません。
0, 1値だけですから、並べ方を固定すれば対角線論法によるものは1つしかありません。
しかし並べ方も動かせば違います。
といっても、あくまで具体的に定義できるものは可算です。
例えば、実数全体は可算ですが、具体的に定義できる実数は可算しかありません。
自然数は具体的に書けます。
有理数は分数の形で書けます。
無理数は例えば√2なり5√6-8√2なり書けるものもあります。
2.718281828…はその後がどうなるか不明なので不可です。1/0!+1/1!+1/2!+…はその後どうなるかは普通は暗黙の了解事項として使いますが、厳密には不可です。
∞
Σ1/n!
n=0
ならOKです。しかし、そのように具体的に書けるものだけではありません。書けない物がたくさんあるということです。
なおN上の自己変換S:N→N全体は不可算です。その後の「例えば」以下は1つに定まってしまいますが、書き忘れただけだと思います。Nの部分集合Aを固定して、Aを不動点としてそれ以外を小さい順に順に2つずつ入れ替えるのかと思います。Aを固定すれば変換は1つに定まりますが、Aを動かすと不可算(詳しくは連続、もっとも可算と不可算の区別は重要ですがどの大きさの不可算かを気にする必要はあまり生じませんが)になります。しかし、Aを具体的に定義できないものがたくさんあると言うことです。
お答から察するに、私の書き方が良くなかったのでしょう、どうやら質問の題意を勘違いされてます。
(3)の質問は(2')が当然成り立っているだろうと思ってのものですが、そもそも構成できる無理列に重複がある可能性も否定できないわけですね。ただ、私自身は(2')も成り立つものと考えています。
(1),(2)に関してはみやどさんと同意見です。
(2)'に関しては可算かと思っていたけど、質問者さんの適切な反例で非可算と納得できました。
べき集合は上の濃度になりますね。
(3)に関して、任意の無理数列を持ってきたとき、これを作るような対角線の選び方があるか、という話ですね。
つまりすべての有理数列について、重複ないようにそれぞれ桁を選んで与えられた数列とそこで異なるようにできるか、という。異なっている桁は無限にあるはずで(有限しかなく途中から同じであればそこから先が周期的になり矛盾)、k桁目まで決めた後で今まで使ってない桁を無限の中から選んでいけば、
ナイーブには可能のように思えますが、そこで選択公理とか絡んでくるんでしょうか。
(4)ルーディ・ラッカーに頼みましょう^^
もし任意の無理列がとれるとすると、超限帰納法の出番かもしれないと思い始めてます。
(間違いなので削除します。)
間違いでした。この方法だと有理数列「全体」を並べていません。もちろん他の方法ではできる可能性はまだ残されています。
あとからご覧になる方のためにも、消されない方が。
(3)無理列(有理列でもいいが)fにたいして、
f_k(n)=f(n) (n≦k) , 0 (n>k)
とすれば、f_kは有理列で、対角線のf_k(k)=f(k)なので無理列になります。
「i≧kを満たす任意のiでf(i)≠f_r(i)となるrが存在する」のは、「f(k)≠f_p(k)となるkは無限に存在する」で示されているので、大丈夫だと思います。
あと、自分もちょっと気になっている「どのような有限個のkを取り除いたf_kに対しても、f_k(r)=0となるrもf_k(r)=1となるrも無限に存在します。」ですが、十分大きなNをとれば、m(有限確定部)+n(循環部)<Nとなり、1≦n≦N-1でNはいくらでも大きくできるので、有限確定部の並び替えでいくらでも取ることができます。
除外される部分が問題になるかもしれませんが、実質、除外されるのは有限確定部ではなく循環部です。つまり、f_pの有限確定部はすべて現れるので、したがって、有限確定部をいくらでも大きくすることができるため、ある桁が0や1になるf_pを無限に取ることができます。
(3')唯一ではないです。例えば、
f_1={0,0,0,0,...(ずっと0が続く)}
f_2={0,0,1,1,...(ずっと1が続く)}
f_3以降は適当な有理列を並べる
とすると、{f_1,f_2,f_3,...}で得られる無理列も{f_2,f_1,f_3,...}で得られる無理列も一致するからです。
私も書いてから気づきました(笑)
要は2か所が一致する有理列の組を入れ替えても対角線上には影響ないので、無数に存在しますね。
「i≧kを満たす任意のiでf(i)≠f_r(i)となるrが存在する」のは、「f(k)≠f_p(k)となるkは無限に存在する」で示されているので、大丈夫だと思います。
2016/10/01 22:26:51あと、自分もちょっと気になっている「どのような有限個のkを取り除いたf_kに対しても、f_k(r)=0となるrもf_k(r)=1となるrも無限に存在します。」ですが、十分大きなNをとれば、m(有限確定部)+n(循環部)<Nとなり、1≦n≦N-1でNはいくらでも大きくできるので、有限確定部の並び替えでいくらでも取ることができます。
2016/10/01 22:41:43除外される部分が問題になるかもしれませんが、実質、除外されるのは有限確定部ではなく循環部です。つまり、f_pの有限確定部はすべて現れるので、したがって、有限確定部をいくらでも大きくすることができるため、ある桁が0や1になるf_pを無限に取ることができます。