この記事も実はマルカキス論文（「指標の組織化と表現方法と呼び名は色々だ」参照）に触発された指標／コンピュータッドに関わるネタなのですが、独立な話として読めるので、タイトルに「指標の話：」とは入れてません。
順序数に沿って再帰的構成や帰納的証明をするとき、順序数全体をモノイド圏だとみなしたほうが便利なので、そのことを話題にします。$`\newcommand{\mrm}[1]{ \mathrm{#1} }
%\newcommand{\cat}[1]{ \mathcal{#1} }
\newcommand{\In}{\text{ in }}
%\newcommand{\id}{ \mathrm{id} }
%\newcommand{\op}{ \mathrm{op} }
\newcommand{\Imp}{\Rightarrow}
%\newcommand{\hyp}{\text{－} }
\newcommand{\Iff}{\Leftrightarrow }
\newcommand{\ordmega}{\boldsymbol{\omega}}
%\newcommand{\NFProd}[3]{ \mathop{_{#1} \!\underset{#2}{ \times }\,\!_{#3} } }
%\newcommand{\incto}{\hookrightarrow}
`$
内容：
ハブ記事：
再帰と帰納
「再帰〈recursion〉」と「帰納〈induction〉」を使い分ける人がいます。例えば、再帰は関数やデータを定義する構成法であり、帰納は証明の技法だと言う人がいます。しかし、証明を書くことと関数を定義することって事実上同じですよね。関数／データの定義と証明の作成の境界線がハッキリしてるわけでもないです。
といった理由で僕は「再帰」と「帰納」を区別する気はないです。しかし、習慣的に「再帰」と呼ばれているものは「再帰」と呼び（例えば「再帰的関数」）、習慣的に「帰納」と呼ばれているものは「帰納」と呼びます（例えば「数学的帰納法」）。また、定義なら「再帰」で証明なら「帰納」という方針にも、ゆるーくは準拠します。
マルカキス論文（「指標の組織化と表現方法と呼び名は色々だ」参照）に、累積再帰的かつ相互再帰的な構造帰納法による超限帰納的構成が出てきます（「再帰」と「帰納」が混ぜ混ぜで気持ち悪いなら、どっちか一方に統一するのはお好きにどうぞ）。そこで、再帰・帰納の基盤となる順序数について明確にしておきます。
順序数達の圏
フォン・ノイマン流の集合論的な順序数〈ordinal number〉の全体は全順序集合となります。一般的に、順序集合からはやせた圏〈thin category〉が誘導されるので、順序数の全体を圏と考えて $`{\bf Odnl}`$ と書きます。$`{\bf Odnl}`$ の全順序の構造を忘れた（射を捨てた）“順序数達の集合”は $`|{\bf Odnl}|`$ です。しかし、ひとつの順序数 $`\alpha \in |{\bf Odnl}|`$ を取り出すと、それは全順序集合です。そして、圏 $`{\bf Odnl}`$ の部分圏なので
$`\quad \alpha \subseteq {\bf Odnl} \In {\bf CAT}`$
です（ややこしいけどね）。
大きい集合〈クラス〉 $`|{\bf Odnl}|`$ は、集合論の絶対的大宇宙のなかではなくて、ワーキング宇宙であるグロタンディーク宇宙 $`{\bf U}`$ のなかで考えます。つまり：
$`\quad |{\bf Odnl}| \subseteq {\bf U}`$
$`|{\bf Odnl}|`$ はグロタンディーク宇宙 $`{\bf U}`$ のなかに閉じ込められていますが、$`|{\bf Odnl}|\in {\bf U}`$ ではないので小さい集合ではありません。順序数全体の集合は、$`{\bf U}`$-小集合ではなくて$`{\bf U}`$-クラス（真のクラス）です。
フォン・ノイマン流の定義だと、順序数 $`\alpha, \beta`$ のあいだの全順序関係 $`a\le \beta`$ は、集合の包含関係 $`\alpha \subseteq \beta`$ で与えられます。例えば、$`2 \le 3`$ とは $`2 \subseteq 3`$ のことです。それと同時に $`2\in 3`$ です。
すべての順序数は全順序集合であるなら、すべての順序数はやせた圏です。圏そのものと圏の対象集合（全順序集合の台集合）は区別するべきでしょう。となると、$`3`$ は圏であり、$`|3|`$ が集合ということになります。ちゃんと区別して書くなら：
$`\quad 3 = \{0 \lt 1 \lt 2\}\\
\quad |3| = \{0 , 1 , 2\}
`$
$`2 \subseteq 3`$ と書いたときの包含関係は、順序集合の圏における（構造としての）包含関係であり、$`|2| \subseteq |3|`$ は集合圏における無構造な包含関係です。
必ずしも全順序とは限らない、サイズが大きくてもよい順序集合の圏を $`{\bf ORD}`$ とします。$`{\bf ORD}`$ の対象は圏でもあり、$`{\bf ORD}`$ の射は関手でもある、という立場をとります。
$`\quad |{\bf ORD}| \subseteq |{\bf CAT}|\In \mathbb{SET}`$
ここで、$`\mathbb{SET}`$ は、とても大きい集合達の集合圏です。「とても大きい集合」については次の記事で書いています。
とても大きい集合達の集合圏 $`\mathbb{SET}`$ の手前に、大きい集合達の集合圏 $`{\bf SET}`$ があります。グロタンディーク宇宙と集合圏の関係を書いておくと、次のようです。
$`\quad |{\bf Set}| = {\bf U}\\
\quad {\bf U} \in {\bf U'}\\
\quad |{\bf SET}| = {\bf U'}\\
\quad {\bf U'} \in {\bf U''}\\
\quad |\mathbb{SET}| = {\bf U''}
`$
通常の集合圏の対象達（つまり小さい集合達）と包含写像だけからなる圏を $`{\bf Set}^\mrm{Inc}`$ とします。すると次が成立します。
$`\quad {\bf Set}^\mrm{Inc} \in |{\bf ORD}| \subseteq |{\bf CAT}|\In \mathbb{SET}`$
$`{\bf Odnl}`$ の順序関係（やせた圏の射）を集合の包含写像と同一視すると：
$`\quad {\bf Odnl} \subseteq {\bf Set}^\mrm{Inc} \subseteq {\bf Set} \In {\bf CAT}`$
対象集合〈set of objects〉だけ見ると、最初の仮定 $`|{\bf Odnl}|\subseteq {\bf U}`$ が再現します。
$`\quad |{\bf Odnl}| \subseteq |{\bf Set}^\mrm{Inc}| = |{\bf Set}| = {\bf U} \In {\bf SET}`$
自然数と自然数の全体
ここでは、自然数全体の集合（無構造な集まり）は $`{\bf N}`$ と書き、自然数全体を順序数とみなした場合は $`\ordmega`$ だとします。
$`\quad \ordmega \in |{\bf Odnl}| \In {\bf SET}\\
\quad \ordmega \subseteq {\bf Odnl} \In {\bf CAT}\\
\quad |\ordmega| \subseteq |{\bf Odnl}| \In {\bf SET}
`$
集合 $`|{\bf Odnl}|`$ は、次の性質を持つ集合です。
$`\quad x\in A \Imp x\subseteq A`$
別な書き方をすると：
$`\quad x\in A \land y\in x \Imp y \in A`$
この性質は推移性〈transitivity〉といいます。グロタンディーク宇宙は推移的です。$`|{\bf Odnl}|`$ も推移的です。自然数の集合 $`{\bf N} = |\ordmega|`$ は、推移的集合の要素になっており、それ自身もまた推移的集合になっています。「要素は部分である」という性質は、（直感的には）奇妙な印象を抱かせるかも知れません。
空集合とゼロを同一視して、有限な順序数と自然数を同一視すれば：
$`\quad \emptyset = 0 \in |\ordmega| \In {\bf Set}\\
\quad n\in {\bf N} \Iff n \in |\ordmega| \In {\bf Set}\\
\quad n\in {\bf N} \Imp (n \subseteq \ordmega \In {\bf Odnl})
`$
順序数の足し算によるモノイド構造
$`\alpha, \beta \in |{\bf Odnl}|`$ に対して、順序数の足し算が定義できます。足し算はプラス記号 '$`+`$' で書きますが、可換ではありません。例えば：
$`\quad \ordmega + 1 \ne 1 + \ordmega`$
可換ではありませんが、結合法則とゼロ法則は満たします。
$`\quad (\alpha + \beta) + \gamma = \alpha + (\beta + \gamma) \\
\quad 0 +\alpha = \alpha = \alpha + 0
`$
また、次も成立します。
$`\quad \alpha \le \beta,\; \alpha' \le \beta' \Imp \alpha + \alpha' \le \beta + \beta'`$
これを圏の言葉に翻訳すれば、次のように解釈できます。
$`\quad f:\alpha \to \beta,\; f' : \alpha' \to \beta' \Imp f + f' : \alpha + \alpha' \to \beta + \beta' \In {\bf Odnl}`$
足し算をモノイド積、$`0 = \emptyset`$ を単位対象として、 $`({\bf Odnl}, +, 0)`$ は厳密モノイド圏になります。対称モノイド圏にはならなくて、非対称な厳密モノイド圏です。
モノイド圏に対しては、左から／右からのスタンピング関手〈テンソリング関手）を考えることができます。
$`\text{For }\xi \in |{\bf Odnl}|\\
\quad L_\xi : {\bf Odnl} \to {\bf Odnl}\\
\qquad L_\xi(\alpha) := \xi + \alpha\\
\quad R_\xi : {\bf Odnl} \to {\bf Odnl}\\
\qquad R_\xi(\alpha) := \alpha + \xi
`$
足し算の非可換性〈非対称性〉から、$`L_1`$ と $`R_1`$ は違う関手です。
そしてそれから
再帰・帰納の基盤となるのは順序数です。実際には、順序数の全体より複雑な順序構造（全順序とは限らない）に沿って再帰・帰納を遂行することもありますが、その場合でも、順序数の全体が背骨のような役割りを果たします。複雑・大規模な再帰・帰納では、順序数達の構造の理解が必須です。
