いきなりですが問題です．
任意の長さのビット列全体からなる集合は，無限集合であることを証明しなさい．
ここでは0と1で構成される，長さ0以上有限長の並びを「ビット列」とし，すべてのビット列からなる集合を考えます．この集合をBと書くことにします．
証明方法の一つ目は，背理法を使うものです．Bが有限集合ならば，その要素数が決まります．それをkと書きます．しかし，"1", "11", "111", ... 「"1"がk+1個並んだもの」はいずれもBに属します．これらのビット列だけで，Bの要素数がkを越えています．ということで矛盾が生じ，Bは有限集合ではないとなります．
証明方法の二番目は，Bと，自然数全体の集合Nとの全単射a bijectionを示すというものです．そのような全単射があれば，BはNと同じ濃度となり，もちろんNは(可算)無限集合ですから，Bも(可算)無限集合となります．
BからNへの全単射というのは，Bの要素を漏れなく列挙すればいいのです．具体的には，空ビット列から始まって, "0", "1", "00", "01", "10", "11", "000", "001", ...というのが列挙の例となります．列挙のn番目のビット列が，自然数のnに対応付けられるわけです*1．
また別の方法でも，証明ができます．集合Aが無限集合であることの十分条件*2の一つに，「AからAへの単射でありかつ全単射でない写像が存在すること」というのがあり，これを使います．
上記の列挙で，順に現れるそれぞれのビット列の末尾に，"0" をつけます．すると，"0", "00", "10", "000", "010", "100", "110", "0000", "0010", ...となります．
集合として書くと，B0={x0|x∈B}です．ここで「B0」は一つの集合を表すのに対して，「x0」は(xよりも1文字長い)ビット列であるという違いには，注意をしてください．
ビット列の末尾に "0" をつける，というのは，BからB0への全単射を意味します．単射であることは一見自明でないので，確認しておきますと，x∈B，y∈B，かつx≠yを満たすどのようなx, yについても，x0∈B0，y0∈B0ですし，x0≠y0ですね．
次に，BとB0の包含関係を押さえておきます．「ビット列の末尾に "0" をつけ」てできたものもビット列ですから，x∈B0ならばx∈Bです．しかし逆は真ならずです．"1"はBに属しますが，B0には属しません．したがって，B0はBに真に含まれます．
「ビット列の末尾に "0" をつける，というのは，BからB0への全単射を意味します．」と書きましたが，この操作は，BからBへの写像ととらえることもできます．このとき，BからBへの単射ですが，全射ではありません．実際，(「Bから」の集合Bの中から)どんなビット列を持ってきても，末尾に "0" をつけることで，"1" というビット列(「Bへの」の集合Bの要素の一つ)を作ることはできません．
したがって，BからBへの全単射でもありません．証明終．
問題と，その直後に書いた集合Bの定義を見直してほしいのですが，Bの要素となるビット列はいずれも長さが有限です．無限長のビット列は，Bに属していません．
しかしBは無限集合です．
ちなみにこれは自然数全体の集合Nについても同じで，その要素は，どれを取り出しても有限の値であり，∞は属していません．しかしいくらでも大きな有限の値を取り出せるので，無限集合となります．
これを一般化すると，「有限個の基礎となる情報に対して，有限個のルールの集合からルールを取り出して有限回適用したものの集合は無限集合になり得る」ということです．もちろん有限集合の場合もあるので，「なり得る」と表現しておきます．
アルゴリズムも，有限長で記述し，実行時間は有限でないといけないのですが，アルゴリズムを適用して，仕様にあった解を得られるような個別問題の集合は，一般に，無限集合です．
冒頭の問題を考えることになったきっかけについて，ここで書いておきます．まず，ビット列の列挙というのは，情報セキュリティで，一方向ハッシュ関数の弱衝突耐性や強衝突耐性が原理的には破れるという根拠となります．
そして，今年度から後期に新しく担当する科目「システムソフトウェア」で，文法の前の段階までを担当することになり，文字や文字列，言語，文法を説明するには，無限集合の性質を理解しておくことが避けて通れないのでした．
「無限集合なら何でも同じ」というわけではありません．これについては，日を改めて，検討することにします．
