0

型推栄の5分で定理 #1

48
0

これは何

定期的に何か文章を書きたいのだが、特にネタもないので5分で証明できる定理をちょくちょく紹介することにしたい。

Kts.1

Kts.1

任意の形式言語は高々可算である。

ただしここで形式言語とは、アルファベットと呼ばれる可算集合(有限集合に限定する流儀もあるが、こちらの方が強い主張なので問題ない)の要素を有限個並べて作った列(語)からなる集合のことをいう。

以下、自然数とは1以上の整数のことをいい、Nで自然数全体を指すものとする。
またアルファベットの集合Σに対し、2Σは(冪集合でなく)Σ上の語全体がなす集合を表す。

L をアルファベット Σ 上の勝手な形式言語とすると、 L2Σ である。ここで Σ は可算であるから、要素である各文字は自然数によって s1,s2,Σ と付番できる。

さて、ここで正の整数 k に対して [k]k 以下の自然数からなる集合を表す。Σ 上の長さ n>0 の語 w が写像 f:[n]Nにより wsf(1)sf(n) と表せるとする。なお、そのような f は長さ1以上のどんな語 w に対しても必ず存在する。

ところで素数は可算無限個存在するから、素数を小さい順に p1,p2,p3, と付番する(例えば p1=2,p2=3,p3=5 である)。そこで写像 g:2ΣN を次の通り定義する。

g(sf(1)sf(n)):=p1f(1)pnf(n)

ただし、空語λに対してはg(λ)=1と約束する。

この方法により任意の w2Σ に自然数 g(w) を対応づけることができ、また素因数分解の一意性から g は明らかに単射である。よって |2Σ||N| であるから、 L もやはり高々可算である。

余談

一般に g(w)w のゲーデル数 (Gödel number) と呼ばれる。

ゲーデル数 - Wikipedia

感想

文章を打ち込む時間を考えると、これ全然5分では済まないな。

修正(2024/03/17)

#0は自然数 なので本記事でもそのように書いていたが、gの定義においてg(s0)=1(s=λ,s,ss,sss,)となって不都合であったから1-indexedに修正した。

投稿日:2024314
更新日:2024317
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. これは何
  2. Kts.1
  3. 余談
  4. 感想
  5. 修正(2024/03/17)