定期的に何か文章を書きたいのだが、特にネタもないので5分で証明できる定理をちょくちょく紹介することにしたい。
任意の形式言語は高々可算である。
ただしここで形式言語とは、アルファベットと呼ばれる可算集合(有限集合に限定する流儀もあるが、こちらの方が強い主張なので問題ない)の要素を有限個並べて作った列(語)からなる集合のことをいう。
以下、自然数とは1以上の整数のことをいい、
またアルファベットの集合
さて、ここで正の整数
ところで素数は可算無限個存在するから、素数を小さい順に
ただし、空語
この方法により任意の
一般に
文章を打ち込む時間を考えると、これ全然5分では済まないな。
#0は自然数
なので本記事でもそのように書いていたが、