【無限数列・集合の濃度・選択公理・対角線論法】ある条件を満たす無限数列全体の集合の濃度について考えています…


〔定義〕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人5回まで
  • 登録:
  • 終了:2016/10/26 20:22:03
※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。
id:kuro-yo

私自身は、(1)可算、(2)必ず無理列になる、(3)任意は無理:任意の無理列が構成できると仮定すると恐らく(2)に矛盾、無理数に代数的数と超越数があるように、この方法で構成できない無理列があるのではないか、と考えてます。

追記:(3)は肯定的に解決されたようですhttp://q.hatena.ne.jp/1474976765#a1259369]

ベストアンサー

id:tatsumi-da No.4

回答回数25ベストアンサー獲得回数5

ポイント300pt

(3)無理列(有理列でもいいが)fにたいして、
f_k(n)=f(n) (n≦k) , 0 (n>k)
とすれば、f_kは有理列で、対角線のf_k(k)=f(k)なので無理列になります。

他17件のコメントを見る
id:tatsumi-da

「i≧kを満たす任意のiでf(i)≠f_r(i)となるrが存在する」のは、「f(k)≠f_p(k)となるkは無限に存在する」で示されているので、大丈夫だと思います。

2016/10/01 22:26:51
id:tatsumi-da

あと、自分もちょっと気になっている「どのような有限個の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を無限に取ることができます。

2016/10/01 22:41:43

その他の回答4件)

id:MIYADO No.1

回答回数1054ベストアンサー獲得回数192

ポイント100pt

(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の入力に直せば文字列です。「構成」というのをそういう意味にとるなら、不可算のものをすべては構成できません。

他2件のコメントを見る
id:MIYADO

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を具体的に定義できないものがたくさんあると言うことです。

2016/09/28 19:36:38
id:kuro-yo

お答から察するに、私の書き方が良くなかったのでしょう、どうやら質問の題意を勘違いされてます。

2016/09/28 19:44:17
id:kuro-yo

質問文を編集しました。詳細はこちら

id:kuro-yo

(3)の質問は(2')が当然成り立っているだろうと思ってのものですが、そもそも構成できる無理列に重複がある可能性も否定できないわけですね。ただ、私自身は(2')も成り立つものと考えています。

id:ita No.2

回答回数204ベストアンサー獲得回数48

ポイント100pt

(1),(2)に関してはみやどさんと同意見です。
(2)'に関しては可算かと思っていたけど、質問者さんの適切な反例で非可算と納得できました。
べき集合は上の濃度になりますね。
(3)に関して、任意の無理数列を持ってきたとき、これを作るような対角線の選び方があるか、という話ですね。
つまりすべての有理数列について、重複ないようにそれぞれ桁を選んで与えられた数列とそこで異なるようにできるか、という。異なっている桁は無限にあるはずで(有限しかなく途中から同じであればそこから先が周期的になり矛盾)、k桁目まで決めた後で今まで使ってない桁を無限の中から選んでいけば、
ナイーブには可能のように思えますが、そこで選択公理とか絡んでくるんでしょうか。
(4)ルーディ・ラッカーに頼みましょう^^

id:kuro-yo

もし任意の無理列がとれるとすると、超限帰納法の出番かもしれないと思い始めてます。

2016/09/29 19:07:16
id:MIYADO No.3

回答回数1054ベストアンサー獲得回数192

ポイント100pt

(間違いなので削除します。)

他1件のコメントを見る
id:MIYADO

間違いでした。この方法だと有理数列「全体」を並べていません。もちろん他の方法ではできる可能性はまだ残されています。

2016/09/29 19:18:59
id:kuro-yo

あとからご覧になる方のためにも、消されない方が。

2016/09/29 22:10:53
id:tatsumi-da No.4

回答回数25ベストアンサー獲得回数5ここでベストアンサー

ポイント300pt

(3)無理列(有理列でもいいが)fにたいして、
f_k(n)=f(n) (n≦k) , 0 (n>k)
とすれば、f_kは有理列で、対角線のf_k(k)=f(k)なので無理列になります。

他17件のコメントを見る
id:tatsumi-da

「i≧kを満たす任意のiでf(i)≠f_r(i)となるrが存在する」のは、「f(k)≠f_p(k)となるkは無限に存在する」で示されているので、大丈夫だと思います。

2016/10/01 22:26:51
id:tatsumi-da

あと、自分もちょっと気になっている「どのような有限個の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を無限に取ることができます。

2016/10/01 22:41:43
id:kuro-yo

質問文を編集しました。詳細はこちら

id:tatsumi-da No.5

回答回数25ベストアンサー獲得回数5

ポイント100pt

(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,...}で得られる無理列も一致するからです。

id:kuro-yo

私も書いてから気づきました(笑)
要は2か所が一致する有理列の組を入れ替えても対角線上には影響ないので、無数に存在しますね。

2016/10/02 10:26:04
  • id:kuro-yo
    スマホ版では質問者からの補足は回答のところに表示されるのかぁ
  • id:kuro-yo
    一般的な数学用語を使用したつもりでしたが、長々と数式や図を書くのが面倒くさいので(ぉぃ)、とりあえず題意に関する補足はしないでおきます。そのうちまとまった暇ができたら補足します。
  • id:kuro-yo
    思ってたより難しい問題だったようです…
  • id:ita
    「010101・・・を置換して任意の数列を作れるか」でも十分に非自明そうですね。
  • id:MIYADO
    0, 1だけからなる数列でいずれも無限に現れるものなら、初出から順に動かせばいいので作れます。
  • id:kuro-yo
    任意の数列は無理です:反例としては、途中から無限に0または1が無限に続く(つまり、循環部分の長さが1)場合です。
  • id:kuro-yo
    書くまでもないと思いましたが(めんどくさかったので(笑))、「対角線論法の要領で」無限列を構成するにあたって、項が一致していてはいけないという事はありません:一致と不一致が混在していなければいいですので、すなわち、全部一致か全部不一致のどちらかでもいいので、無理に不一致の方で論じなくても、題意は損なわれません。なぜなら、有理列性(もちろん無理列性も)は、各項の0と1を入れ替えても変わらないからです。
    (なので「対角線論法で」ではなく「対角線論法の要領で」と表現しました。)
  • id:MIYADO
    (ブックマークコメントへ)通常の意味の小数とは言えません。そういうのを定義すればありますが、する意義があるかどうか。
  • id:kuro-yo
    考えがまとまらない…
  • id:kuro-yo
    とりあえず、(1)と(3)が肯定的に解決するという事は、有理列全体の集合は有理列の並び順を変えて対角線部分を取り出したものをすべて付け加える事で完備化できる、という事を示した事になりますね。(3)肯定的解決するなら(2')は自動的に肯定されますね。
  • id:kuro-yo
    あ、適当な順番に有理列を並べて、適当な間隔で無限に元を取り出したら、その極限が対角線上の無理列になって、それって要するに完備化なのでは…(妄想
  • id:tatsumi-da
    ああ、それは自分も考えました。有理列は有界な有理数列の部分集合と見なせるから、有界な閉集合は収束する部分列を持つので、任意の無理列は構成できるのではないかなと。

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

回答リクエストを送信したユーザーはいません