２のべき乗

質問

ある集合Sはその要素、もしくはその和で、全ての正の整数を一意的に表現することが出来る。Sの要素が全て正の整数であるとしたら、S＝{2^k　0<=k}(kは整数)であり、Sはそれ以外の集合にはなりえないことを証明せよ。

この問題のところで、S＝{2^k　0<=k}を満たさないようなSが存在しないというところを証明するところが難解です。なにか証明する方法はあるのですか？

回答No.6

B-juggler

Ｎｏ．３です。なるほど、Ｎｏ．４氏　了解。

２＾ｋ　（ｋ≧０｜ｋ∈Ｚ）　全てが必要の証明と、

２進数でないといけない理由。これがいるんですね。了解了解。

アウトラインはできてあるようだし、別解みたいにしかならないのかな？

３＾ｋ　だと、現せない数が一つでも存在することを示せばいい。

　＃自動的に　ａ＾２　ａ≠２　では不可能と示せるはず。

反例は簡単に出ますね。５は？＾＾；　３＾ｘ＝２　となる　ｘが存在しない。

　整数としてね。

全て必要のほうは、二進数の一意性（十進数についての）で、
さして書く必要はないかと思ったけれど、
書くとしても自明でよさそうにも思うけれど。

ここが困ってあるのかな？

十進数ならば二進数に置き換えることが出来る。

これはいいよね？　このときつまり、｛２＾０、２＾１、・・・・・、２＾ｋ｝＝Ｓ

とやっておくと、Ｓの要素で必ず全ての１０進数（正の整数が）表せると、出来るね。

３＾ｘ　のときがダメなのは、上に書いているとおり。

じゃなぜか？　つまり　１　これ！　２＾０ね。

２のべき乗なのだから、必ず偶数。ここに１が入って和を取ることで、奇数が生まれる。

これが分かれば一目。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

回答No.5

tmpname

Sの元nで、『{x|xはSの要素、かつx≦n}』が S_nと一致しないものがあるとして、そのようなnの中で『最小のもの』を取ったとき、それをNとすると、今言ったことから

と書いた所は、

1以上の整数nで、『{x|xはSの要素、かつx≦n}』が S_nと一致しないものがあるとして、そのようなnの中で『最小のもの』を取ったとき、それをNとすると、今言ったことから

の方がいいです。S_nの定義は、すでに書いた通り
S_n = {x| ある非負整数kがあって、x=2^kとかける、かつx ≦ n}です。

回答No.4

tmpname

#No.3さん

それだと{2^k| 0<=k, kは整数}が「全部いる」ことを示せてないし、「2進数以外の方法では出来無い」ことも示せてないですね。

回答No.3

B-juggler

もうちょっと簡単に行こう。おそらく難しく取りすぎていると思う。

最後は読解力だからね、数学は。　元代数の非常勤ね。

要は

＞ある集合Sはその要素、もしくはその和で、全ての正の整数を一意的に表現することが出来る。

これを示せばいい。

２＾ｋ　の和　を考えれば、全ての正の整数が表せる。と考えればいいわけね。

１＝２＾０
２＝２＾１
３＝１＋２＝２＾０＋２＾１
４＝２＾２
５＝４＋１＝２＾２＋２＾０
・・・・

こういう具合になっていることは簡単に理解できるでしょう？

後はね、極端に行けば「２進数は１０進数に対して一意性を持つ」ことを示せばいいよね。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

お礼

二進数と10進数が一対一で対応していることは存じてますが、その手法だとどうしてもSが複数存在するという仮定の反証をすることが難しいと思うんです。

回答ありがとうございます。

回答No.2

tmpname

取り敢えず1も2もSには必ずSに入っているのはいいとして、手順としては

A 3以上の整数nは、自然数全体の部分集合
S_n = {x| ある非負整数kがあって、x=2^kとかける、かつx ≦ n}
の中の有限個の元の和で書ける
B n=2^m (mは1以上の整数）とかける整数nについては、
S_{n-1} = {x| ある非負整数kがあって、x=2^kとかける、かつx ≦ n-1}
の中の有限個の元の和で書け「ない」

ことを証明してしまえば、あとは
＊Sの元nで、『{x|xはSの要素、かつx≦n}』が S_nと一致しないものがあるとして、そのようなnの中で『最小のもの』を取ったとき、それをNとすると、今言ったことから

- Nは3以上
- {x|xはSの要素、かつx<N}はS_{N-1}と一致する（Nは『最小のもの』を取ってきたから）

ことから、

C: N = 2^m （mは1以上の整数）とかける数の時、仮定からS_NにNは含まれ『ない』。この時BからNはS_N = S_{N-1}の中の有限個の元の和では書けないので矛盾する。

D: N=2^m（mは1以上の整数）とかけない数の時、仮定からS_NにNは含ま『れる』。この時Aから、S_N = S_{N-1}∪ {N}の中の有限個の元の和で Nを表現する方法は少なくとも2通りあるので矛盾する。

となります。そうでないものの『最小のもの』を取ってくるとうまくいきます（実は、これは結局数学的帰納法と変わらなかったりする）。詳しいことは一度考えてみてください。

お礼

回答ありがとうございます。非常に考え抜かれた証明のためのアウトラインを作ってくださって大変感謝してます。
自分はこの問題にはシンプルな証明があるだろうと思って色々と試行錯誤しているうちに、これは自分が当初考えていたような単純な問題ではないことに気づきました。
私が証明を完成させて確認した後にベストアンサーに選ばせていただきますね。

回答No.1

Tacosan

構成的に示せそう.