自然数と文字列の対応関係

自然数と文字列の対応関係

自然数の集合と文字列の集合は、両者とも自由モノイドなので対応関係があります。たとえば、0と空列はモノイド単位元です。このようにいくつか対応項が作れるので、ここでまとめてみましょう。文字が1種類しかない場合を考えたときの文字列の集合が自然数に相当しているので、これにより対応関係を調べることができます。

自然数	文字列
0	ε
σ	(:)
1	η
(+)	(・)

0とε

0と空列εは、お互いモノイドの単位元であること、また再帰的定義における構成子（初期値）としても対応しています。

σと(:)

σは自然数上の後者関数（successor）、(:)は文字列に文字を追加するconsです。両者ともに、再帰的定義における構成子です。

1とη

ηは挿入関数（inclusion）と呼ばれる文字集合から文字列集合への関数で、各文字aを長さ1の文字列aへ返す関数です。構成子から次のように定義されます。
\[ η(a) = a:ε\]
　同様に1もσ0として定義されます。

(+)と(・)

(+)は自然数上の足し算、(・)は文字列上の連接で、両者ともにモノイド乗法として共通しています。両者ともにσまたは(:)を底とする指数関数を考えることで定義することができます。詳しくは、指数関数の一般化に関する記事を参照してください。

それぞれの関係

自然数と文字列の間に4つの対応項があることを確認しました。これら4つは基本的な構成要素といえるでしょう。4つの間には指数関数によってある関係があります。それをここでまとめましょう。

自然数

\[ 1 = σ0 \\
 m + n = σ^m\ n \\
σm = 1 + m \]

文字列

\[ η(a) = a:ε \\
 x \cdot y = (:)^x\ y \\
a:x = η(a) \cdot x \]

掛け算について

自然数上の掛け算(×)は次のように定義することができます。
\[ (×) : \mathbb{N} × \mathbb{N} → \mathbb{N} \\
m × n = m^n\]
　右辺が通常の意味での指数関数にならないことに注意です。自然数は、任意のモノイドの元を底とする指数関数を考えることができました。ここでは、任意のモノイドとして単位元を0、乗法を+とする自然数を選んだということです。通常の指数関数の場合は、モノイドの二項演算を乗法として考えるので指数関数という表現を使いましたが、加法として考える場合は、直観的には掛け算になります。

文字列の掛け算について

自然数上の掛け算の類似から、あえて文字列Σ*上の掛け算を考えると次のようになります。
\[ (×) : Σ^* × \mathbb{N} → Σ^* \\
x × m = x^m
\]
　これは、文字列xをm回連接する計算です。連接を加法としてとらえる場合は左辺の表記が、乗法としてとらえる場合は右辺の表記がいいでしょう。

掛け算の性質

自然数上の掛け算の性質が文字列へ一般化できるものをまとめましょう。自然数上の次の性質が一般化できます。
\[ m × 0 = 0 \\ m × 1 = m \\ m × (n_1 + n_2) = m × n_1 + m × n_2\]
　ただし、自然数上の掛け算が可換であるからといって、これを入れ替えてはいけません。文字列上では可換性は失われます。
　以上の性質に対応する文字列上の性質は次のようになります。
\[ x × 0 = ε \\ x × 1 = x \\ x × (n_1 + n_2) = (x × n_1) \cdot (x × n_2) \]