文字列と始代数～再帰的な定義について～

自然数と始代数

自然数の集合 $\mathbb{N}$ 上には定数 $0 : 1 \rightarrow \mathbb{N}$ と後者関数（successor）$\sigma : \mathbb{N} \rightarrow \mathbb{N}$ が与えられています。これらをまとめて、

$$1 + \mathbb{N} \xrightarrow{\lbrack 0, \sigma \rbrack} \mathbb{N}$$

と表しましょう。この記法については、詳しくは記事「場合分けと排他的論理和」を見ていただければと思います。

後者関数は単項演算です。$X$ 上の定数 $c$ と単項演算 $h$ の組み合わせを、一般に

$$1 + X \xrightarrow{\lbrack c, h \rbrack} X$$

と表しましょう。この定数と単項演算には公理をさしあたり与えませんが、この組み合わせをひとつの代数と考えます。

また、定数と単項演算には特別な名を与えましょう。この定数は初項、単項演算は漸化式と呼びます。

代数ですから準同型（morphism）が考えられます。$f : X \rightarrow X'$ が準同型であるとは、可換図式

$$\begin{CD} 1 + X @>\lbrack c, h \rbrack>> X \\ @VV \mathrm{id}_1 + f V @VV f V \\ 1 + X' @>\lbrack c', h' \rbrack>> X' \\ \end{CD}$$

を満たすことです。この可換図式を展開すると、以下の二つの等式になります。

$$\begin{align*} f(c) &= c' \\ f(h x) &= h' (f(x)) \end{align*}$$

あえて $f(x) = a_x$ と数列の記法で書き換えましょう。

$$\begin{align*} a_c &= c' \\ a_{hx} &= h' (a_x) \end{align*}$$

さて、$1 + X \xrightarrow{\lbrack c, h \rbrack} X$ という組み合わせは圏を与えます。つまり、

• 対象： $1 + X \xrightarrow{\lbrack c, h \rbrack} X$
• 射： 準同型 $f : X \rightarrow X'$

です。さて、$1 + \mathbb{N} \xrightarrow{\lbrack 0, \sigma \rbrack} \mathbb{N}$ はこの圏の始対象（inital object）です。つまり、任意の $1 + X \xrightarrow{\lbrack c, h \rbrack} X$ について、準同型 $f : \mathbb{N} \rightarrow X$ が一意に定まります。準同型であるため、可換図式

$$\begin{CD} 1 + \mathbb{N} @>\lbrack 0, \sigma \rbrack>> \mathbb{N} \\ @VV \mathrm{id}_1 + f V @VV f V \\ 1 + X @>\lbrack c, h \rbrack>> X \\ \end{CD}$$

を満たします。展開すると、

$$\begin{align*} f(0) &= c \\ f(\sigma n) &= h (f(n)) \end{align*}$$

ここでも $f(x) = a_n$ と数列の記法で書き換えましょう。

$$\begin{align*} a_0 &= c \\ a_{\sigma n} &= h (a_n) \end{align*}$$

あえて初項、漸化式と呼んだ理由がわかると思います。$1 + X \xrightarrow{\lbrack c, h \rbrack} X$ という組み合わせを与えるということは、始対象からの一意射を与えることに等しい。つまり、数列 を与えることの等しい。この圏は結果的に自然数を添字とする数列の圏になっているわけです。

この始対象は特別に始代数（inital algebra）と呼ばれます。始代数の文脈では一意射はcatamorphism と呼ばれて、$(\!| c, h |\!) : \mathbb{N} \rightarrow X$ という表記をすることがあります（バナナ括弧）。

関数型プログラミングの文脈ではこれは折り畳み（fold）です。

モノイドの指数関数

モノイド $\langle M, (\_) \cdot (\_), e \rangle$ を考えます。任意のモノイドの元 $x \in M$ について、$x$ を底、自然数を指数とする指数関数を考えることができます。

$$x^n = x \cdot x \cdots x$$

これを初項と漸化式で表すと、

$$\begin{align*} x^0 &= e \\ x^{\sigma n} &= x \cdot x^n \end{align*}$$

となります。可換図式では、

$$\begin{CD} 1 + \mathbb{N} @>\lbrack 0, \sigma \rbrack>> \mathbb{N} \\ @VV \mathrm{id}_1 + x^{(\_)} V @VV x^{(\_)} V \\ 1 + M @>\lbrack e, x \cdot (\_) \rbrack>> M \\ \end{CD}$$

です。

任意のモノイドの元 $x \in M$ について一意に定まる指数関数 $x^{(\_)} : \mathbb{N} \rightarrow M$ はモノイド準同型になります。

モノイド準同型であることを示すためには、$1 + \mathbb{N} \xrightarrow{\lbrack 0, \sigma \rbrack} \mathbb{N}$ に二項演算を定義する必要があります。

自然数の加法

自然数の始代数性から任意のモノイドの元を底とする指数関数を考えられました。自己写像全体もモノイドになるため後者関数 $\sigma$ もモノイドの元になります。そのため、$\sigma$ を底とする指数関数も考えられます。

$$\begin{align*} \sigma^0 &= \mathrm{id}_{\mathbb{N}} \\ \sigma^{\sigma n} &= \sigma \circ \sigma^{n} \end{align*}$$

こうして得られた $\sigma^{(\_)} : \mathbb{N} \rightarrow \mathbb{N}^{\mathbb{N}}$ を非カリー化（uncarrying）したものが加法 $+ : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$になります。つまり、

$$\begin{align*} n + m = \sigma^n (m) \end{align*}$$

です。記事「モノイドについて」で書いた通り、ここから単位元則、結合法則を示すことでモノイドであることがわかります。

文字列と始代数

上記の自然数の議論を文字列に拡張します。文字集合を $\Sigma$ とします。集合 $X$ に初項 $c \in X$ と文字集合 $\Sigma$ を添字集合とする漸化式の列 $(h_a)_{a \in \Sigma}$ を考えます。

これは $h_{(\_)} : \Sigma \rightarrow X^X$ を与えるということです。これを非カリー化した $h : \Sigma \times X \rightarrow X$ を漸化式としましょう。自然数のときと同様に次のような組み合わせを考えます。

$$1 + \Sigma \times X \xrightarrow{\lbrack c, h \rbrack} X$$

自然数のときは漸化式 $h$ がひとつでしたが、添字付きの漸化式 $h_a$ となったため、文字数だけ漸化式が与えられたことになります。

自然数のときと同様に準同型を考えられて、それは圏となり、そして、始対象が与えられます。それが文字列集合 $\Sigma^{*}$です。

$$1 + \Sigma \times \Sigma^{*} \xrightarrow{\lbrack \varepsilon, \sigma \rbrack} \Sigma^{*}$$

自然数の初項である$0 \in \mathbb{N}$ は空列 $\varepsilon \in \Sigma^{*}$ であり、自然数の漸化式である後者関数 $\sigma$ は添字付き後者関数（indexed successor）$\sigma_{(\_)}$ となりました。これはいわゆるconsです。

添字付き指数関数

任意のモノイド $M$ について文字集合 $\Sigma$ を添字集合とする添字付き元の列 $(x_a)_{a \in \Sigma}$ が与えられたとしましょう。このとき、添字付き元の列 $(x_a)$ を底として、文字列 $w \in \Sigma^{*}$ を指数とする指数関数を考えられます。

$$\begin{align*} x^{\varepsilon} &= e \\ x^{\sigma_a w} &= x_a \cdot x^w \end{align*}$$

添字付き後者関数も自己写像全体の作るモノイドの元の列ですから、添字付き後者関数を底とする指数関数 $\sigma^{(\_)} : \Sigma^{*} \rightarrow {\Sigma^{*}}^{\Sigma^{*}}$が与えられます。

$$\begin{align*} \sigma^{\varepsilon} &= \mathrm{id}_{\Sigma^{*}} \\ \sigma^{\sigma_a w} &= \sigma_a \cdot \sigma^w \end{align*}$$

これを非カリー化したものが連接（concatenation）です。つまり、

$$u \cdot v = \sigma^u (v)$$

始代数と自由代数

このように構成された始代数 $\Sigma^{*}$ は生成元集合を $\Sigma$ とする自由モノイドであることを示すことができます。詳しくは「文字列の代数」を読んでいただければと思います。

始代数とは再帰的な定義を普遍性により定義したものと考えられます。たとえば、自然数は

• $0$ は自然数である
• $n$ が自然数であれば、$\sigma n$ は自然数である
• 以上の方法によって定められたもののみが自然数である

と定義されます。三番目の条件は重要です。つまり、この過不足のなさが初項と漸化式のみによって数列 $a_{(\_)} : \mathbb{N} \rightarrow X$ を一意に存在させるからです。

三番目の条件がなければ、過不足を許すことになります。そのため、初項と漸化式だけでは数列は一意にはならない。

文字列も同様です。文字列を再帰的な定義すると、

• $\varepsilon$ は $\Sigma$ 上の文字列である
• $w$ が $\Sigma$ 上の文字列、$a$ が $\Sigma$ 上の文字であれば、$\sigma_a w$ は$\Sigma$ 上の文字列である
• 以上の方法によって定められたもののみが$\Sigma$ 上の文字列である

となります。

データ型

自然数と文字列（リスト）は次のようなデータ型で定義できます。

data Nat := Zero | Succ Nat
data List a := Nil | Cons a (List a)

この記法を数学的な語彙に置き換えると始代数になる、ということです。

再帰性と閉包

直接示すことは難しいですが、自然数と文字列は次のような同型性があります。

$$\begin{align*} \mathbb{N} &\simeq 1 + \mathbb{N}\\ \Sigma^{*} &\simeq 1 + \Sigma \times \Sigma^{*} \end{align*}$$

同型 $\simeq$ を厳密でないことを許せば $=$ に書き換えて、

$$\begin{align*} \mathbb{N} &= 1 + \mathbb{N}\\ \Sigma^{*} &= 1 + \Sigma \times \Sigma^{*} \end{align*}$$

になります。右辺は再帰的に展開ができます。たとえば、上記等式は、

$$\begin{align*} \mathbb{N} &= 1 + 1 + \mathbb{N}\\ \Sigma^{*} &= 1 + \Sigma \times (1 + \Sigma \times \Sigma^{*}) \\ &= 1 + \Sigma + \Sigma \times \Sigma^{*} \end{align*}$$

になります。これを延々と続ければ、

$$\begin{align*} \mathbb{N} &= 1 + 1 + 1 + \cdots \\ \Sigma^{*} &= 1 + \Sigma + \Sigma^2 + \Sigma^3 + \cdots \end{align*}$$

となります。これは直観にも従うのではないでしょうか。このような再帰的な展開の極限として得られるものを閉包（closure）と呼びます。

帰納法による証明

帰納法による証明もいわば初項と漸化式によって与えられたと考えてよいでしょう。

たとえば、初項と漸化式を以下のように定めれば、性質 $p : \mathbb{N} \rightarrow 2$ が一意に定まります。

$$\begin{align*} p(0) &= 1 \\ p(\sigma n) &= 1 \vee p(n) \end{align*}$$

この二つの等式さえ示せれば、任意の $n \in \mathbb{N}$ について　$p(n) = 1$ が成り立つと言えるわけです。