有限列と無限列
文字集合を \Sigma としたとき、有限の文字列の集合 \Sigma^{*} は、
\Sigma^{*} = 1 + \Sigma + \Sigma^2 + \Sigma^3 + \cdots
という直和で表すことができます。
集合の直和は論理式の排他的論理和で、
w \in \Sigma^{*} \iff w \in 1 \oplus w \in \Sigma \oplus w \in \Sigma^3 \oplus \cdots
と書き換えられます。これはつまり、ある自然数 n \in \mathbb{N} が一意に定まり、
が成り立つ、ということです。この n \in \mathbb{N} は長さ（length）と言います。
さて、無限の文字列の集合 \Sigma^{∞} は、
\Sigma^{∞} = \Sigma \times \Sigma \times \Sigma \cdots
で表されます。w \in \Sigma^{∞} には長さはありません。文字列 w を文字 a_i の連接で展開すると、
w = a_1 \cdot a_2 \cdot a_3 \cdots
です。このとき、a_n は n 番目の文字を表しています。この文字列が無限であるということは、任意の自然数 n \in \mathbb{N} について、a_n \in \Sigma が一意に存在するということです。
不動点としての有限列と無限列
有限もしくは無限の文字列の集合は次のような等式が成り立ちます。
\begin{align*}
\Sigma^{*} &= 1 + \Sigma \times \Sigma^{*} \\
\Sigma^{∞} &= \Sigma \times \Sigma^{∞}
\end{align*}
あえて F(X) = 1 + \Sigma \times X あるいは G(X) = \Sigma \times X とすれば、上記の等式は、
\begin{align*}
F(\Sigma^{*}) &= \Sigma^{*} \\
G(\Sigma^{∞}) &= \Sigma^{∞}
\end{align*}
と表すことができます。つまり、\Sigma^{*} と \Sigma^{∞} は、F または G によって動かないということです。しばしば、不動点といいます。
始代数としての有限列
有限の文字列の集合 \Sigma^{*} は
1 + \Sigma \times X \xrightarrow{\lbrack c, h \rbrack} X
という代数からなる圏の始対象
1 + \Sigma \times \Sigma^{*} \xrightarrow{\lbrack \varepsilon, \sigma \rbrack} \Sigma^{*}
でした。これを始代数と言います。詳しくは、記事「文字列と始代数」を読んでいただければと思います。
始代数は必ず不動点になります。というのは、始代数が任意の代数について準同型を一意に定める普遍性により、\lbrack \varepsilon, \sigma \rbrack の逆射の存在が定まるからです。バナナ括弧を使えば、(\!|1 + \Sigma \times \lbrack \varepsilon, \sigma \rbrack|\!) : \Sigma^{*} \times 1 + \Sigma \times \Sigma^{*} が逆射になります。
同様にこの双対である終余代数（terminal coalgebra）も考えることができます。終余代数もまた不動点であり、そして、無限列 \Sigma^{∞} はその例です。
終余代数としての無限列
X \xrightarrow{\lang |\_|, h \rang} \Sigma \times X
を対象とします。直積を展開すれば、
\Sigma \xleftarrow{|\_|} X \xrightarrow{h} X
となります。あえて |\_| : X \rightarrow \Sigma つまり x \mapsto |x| といく記法を選んだのは、x \in X を |x| \in \Sigma に写す射影の側面があるからです。h : X \rightarrow X は単項演算子です。
この終対象つまり終余代数は、
\Sigma^{∞} \xrightarrow{\lang |\_|,\,\tilde{\_} \rang} \Sigma \times \Sigma^{∞}
になります。\lang |\_|,\,\tilde{\_} \rang は 頭（head）と尾（tail）に分けています。つまり、
\begin{align*}
|w| &= a_1 \\
\tilde{w} &= a_2 \cdot a_3 \cdots
\end{align*}
です。この記法は |\_| が代表を選んでいて、\tilde{\_} がそれを差し引いた 余因子 を選んでいる、というイメージです。つまり、
\begin{align*}
w &= |w| \cdot \tilde{w} \\
&= (a_1) \cdot (a_2 \cdot a_3\cdots) \\
&= a_1 \cdot a_2 \cdot a_3 \cdots
\end{align*}
です。直積を展開すれば、
\Sigma \xleftarrow{|\_|} \Sigma^{∞} \xrightarrow{\tilde{\_}} \Sigma^{∞}
になります。
さて、この終余代数への余準同型 \varphi : X \rightarrow \Sigma^{∞} は、任意の x \in X について、
\begin{align*}
|\varphi(x)| &= |x| \\
\tilde{\varphi(x)} &= \varphi(hx)
\end{align*}
が成り立ちます。
合わせて書けば、
\begin{align*}
\varphi(x) = |x| \cdot \varphi(hx)
\end{align*}
この式は次のように無限に展開ができます。
\begin{align*}
\varphi(x) &= |x| \cdot \varphi(hx) \\
&= |x| \cdot |hx| \cdot \varphi(h^2x) \\
&= |x| \cdot |hx| \cdot |h^2x| \cdot \varphi(h^2x) \\
&= |x| \cdot |hx| \cdot |h^2x| \cdot |h^3x| \cdots
\end{align*}
同じことですが、文字列の記法ではなく順序対の記法では次のようになります。
\begin{align*}
\varphi(x) &= (|x|, \varphi(h(x))) \\
&= (|x|, |hx|, \varphi(h^2x)) \\
&= (|x|, |hx|, |h^2x|, \varphi(h^2x))\\
&= (|x|, |hx|, |h^2x|, |h^3x| \cdots)
\end{align*}
帰納法と余帰納法
自然数についての漸化式は、
\begin{align*}
a_0 &= c \\
a_{\sigma n} &= h (a_n)
\end{align*}
と表しました。任意の自然数 n \in \mathbb{N} は n = \sigma^{n}(0) です。このこと合わせて考えると、
\begin{align*}
a_n &= a_{\sigma^{n}(0)} \\
&= h (a_{\sigma^{n-1}(0)}) \\
& \cdots \\
&= h^n (a_0) \\
&= h^n (c)
\end{align*}
と展開は終わります。このような展開は帰納法と呼ばれます。一方で、余帰納法は展開が終わりません。というのは、帰納法はカウントダウンですが余帰納法はカウントアップだからです。
Discussion