帰納構造、帰納代数

帰納的構成はよく使うが、構成（生成）された後にできる構造の話。

Xが生成された集合、Aが初期集合、c_iがコンストラクタだとする。これらを、(X, A, c₁, ..., c_n) という構造だと考える。次の記法を使う。

• X₀ := A
• X₊ := X＼A

定義より、X = X₀ + X₊。X₀の要素をプリミティブ、X₊の要素をコンポジットと呼ぶ。

(X, A, c₁, ..., c_n)が有限全域帰納構造だとは、次を満たすこと。

1. c_i:X→X は全域写像
2. c_iの余域を Im(c_i)に制限すると双射。
3. c₀:A→X を埋め込みとすると、c₀, c₁, ..., c_n は協力して全射〈jointly serjective〉、あるいは被覆〈covering〉。

C = {c₁, ..., c_n} として、記号的な構造として、A×C^*があり、標準的な全射 A×C^*→X がある。

以上の構造を踏まえて、次のように一般化する。

• コンストラクタc_iが有限とは限らない。1, ..., n ではなくて、いくつかの集合 A₁, ..., A_n でパラメトライズされた無限のコンストラクタを許す。
• コンストラクタの写像が全域とは限らない。
• 代数構造 A×C^* がより複雑なオペラッドになる。

以上のような一般化により、帰納構造を持った代数、帰納構造を持った圏／オペラッドを定義する。