有限の情報の集合が無限集合になる - わさっきの続きです．
情報の学科に入って，大学1〜2年のうちに，無限集合の厄介さ，もしくは奥深さについて，いくつか知っておくといいことを並べてみます．
- 前のエントリでも書きましたが，無限集合Aについては，AからAへの単射でありかつ全単射でない写像が存在します．逆に，そのような写像が存在することが，Aが無限集合であることの十分条件ともなります．
- 自然数全体の集合をNと書くとき，N×N，すなわちXY平面の格子点全体(第1象限のみ)からなる集合も，可算無限です．言い換えると，Nから，N×Nへの全単射が存在します．有理数全体の集合Qも，可算無限です．
- 0以上1未満の全ての実数からなる集合は，可算無限よりも大きな集合です．この証明は，カントールの対角線論法として知られています．
- 集合を基数だけでなく序数ととらえると，また世界が広がります．まずは無限と有限について -この世の中に存在する無限と有限という言葉はどう- その他(教育・科学・学問) | 教えて!gooのANo.6の回答をご覧ください．入門書としては，『無限集合 (数学ワンポイント双書 4)』があります．
ここまでは，別に情報分野というよりは，純粋な数学の話です．情報科学の知見に基づく，無限の面白さの例を一つ，紹介します．
次の3つの集合A, B, Cを考えます．なお簡単のため，いずれの集合にも空文字列は含まないものとします．
- Aは，0と1で構成される，長さが偶数の文字列全体からなる集合です．"0101" や "11000110" などが属します．
- Bは，0と1で構成される，長さが偶数の，回文となる文字列全体からなる集合です．回文はよく，「先頭から読んでも，末尾から(逆順に)読んでも，同じになる文字列」として定義されます．"0110" や "11000011" などです．
- Cは，1のみで構成される，長さが偶数の文字列全体からなる集合です．"11"，"1111"，"111111"，"11111111"，…と列挙できます．
これらはいずれも無限集合です．冒頭のリンクに書いている証明を使って，同様に証明できます．
包含関係は，明らかに，C⊂B⊂Aです．例を比較すれば分かるように，Cに属さないがBに属するもの，Bに属さないがAに属するものがあります．
なのですが，AとCについては，それぞれに対応する正規表現を書くことができます．Aは "(00|01|10|11)+"，Cは "(11)+" です．
しかし，Bについては，対応する正規表現が存在しません*1．集合AとCは正規言語に位置し，集合Bは，文脈自由言語と呼ばれる，正規言語よりも広い言語のクラスに位置します．
以上の考察から，次の主張ができそうです．すなわち，集合Bについて，Bよりも広い(制約の緩い)集合Aと，Bよりも狭い(制約の厳しいrestricted)集合Cがあるとき，AとCが何らかの性質を満たすときに，Bもその性質を満たすとは限らない，ということです．
そしてそのような集合Bが，情報の分野で興味深い検討対象になることもしばしばです．
正規表現の確認プログラム
#!/usr/bin/env ruby # rematch.rb class REMatch def initialize(pattern_string) @pattern_string = pattern_string @pattern = Regexp.new(pattern_string) @maxlen = 8 end def match(n) 0.upto(2 ** n - 1) do |i| str = sprintf("%0*b", n, i) if @pattern =~ str puts " #{str}" end end end def start puts "\"#{@pattern_string}\" matches:" 1.upto(@maxlen) do |i| match(i) end end end if __FILE__ == $0 REMatch.new(ARGV.shift || "^(11)+$").start end
引数なしで実行すると，上述の集合Cに属する，長さ8までの文字列を出力します．引数に「'^(00|01|10|11)+$'」を指定して実行すると，集合Aです．
なお，「^」と「$」は必須で，これらがないと，例えば "(11)+" は "110" にもマッチします．これは，"110" の中の最初の2文字にマッチするためです．
