- 308 名前：１３２人目の素数さん [02/02/01 00:37]
- >>294
もし可能だとすると、
アルファベットm種類では可能だが、m-1種類では不可能であるようなmが
存在する。
ここで、m種のアルファベットのうち特定のある１つを使用しない単語が
無限にあると仮定するなら、その単語だけ選んで単語列を作ると条件を
みたしてしまい、m-1種のアルファベットでは不可能であるということに
反するので矛盾。
したがって、m種のうちある一つを使用しない単語は有限個数しかないので、
これらをすべて単語列から除いても条件は成立する。
この操作をm回繰り返すことにより、全ての単語がm種のアルファベット全てを
使用している単語列が作れる。
以上より、この命題に
「全ての単語は、使用可能なアルファベットの全種類を含むものとする」
という条件を追加しても、その真偽はかわらない。
次に、n番目の単語がw(n)文字であったとすると、w(n)文字以下の単語は
有限個数しかないことから、単語列の無限性を損なわずに
n+1番目以降からw(n)文字以下の単語を取り除くことができる。
n＝1から順にこの操作を行うことにより、文字数が単調増加である
単語列を作ることができる。
したがって、この命題に
「n番目の単語の文字数をw(n)とすると、j＜k⇒w(j)＜w(k)」
という条件を追加しても、真偽は変わらない。
これで、少しは考えやすくなったかなあ．．．
|
 |
