F余代数
関手 F : S e t ⟶ S e t {\displaystyle F\colon \mathbf {Set} \longrightarrow \mathbf {Set} } として、 X {\displaystyle X} を ( X × A ) ∪ { 1 } {\displaystyle (X\times A)\cup \{1\}} に送るものを考える。すると F-余代数 α : X ⟶ ( X × A ) ∪ { 1 } = F X {\displaystyle \alpha \colon X\longrightarrow (X\times A)\cup \{1\}=FX} はアルファベット A {\displaystyle A} 上の有限または無限のストリームをあらわすことになる。このとき X {\displaystyle X} は状態集合、 α {\displaystyle \alpha } は状態遷移関数である。状態遷移関数を状態に適用した場合、2通りの結果が考えられる。ひとつは A {\displaystyle A} の元とストリームの次の状態が返される場合、もうひとつは単元集合 { 1 } {\displaystyle \{1\}} の元が返される場合である。後者は特別な「終状態」、つまりストリームが打ち止めであることを表す値である。
多くの実用的な例では、このような余代数の状態遷移関数は X → f 1 × f 2 × ... × f n {\displaystyle X\rightarrow f_{1}\times f_{2}\times \ldots \times f_{n}} という形になっていて、「セレクタ」「オブザーバ」「メソッド」のように機能別に X → f 1 , X → f 2 .
.. X → f n {\displaystyle X\rightarrow f_{1},\,X\rightarrow f_{2}\,\ldots \,X\rightarrow f_{n}} と分割して考えることができるようになっている。多くの場合、オブザーバーは何らかの属性値を出力するようになっていて、状態を書き換えるメソッドは X → X A 1 × ... × A n {\displaystyle X\rightarrow X^{A_{1}\times \ldots \times A_{n}}} のように追加のパラメーターを受け取って次の状態を返す形になっている。このような分解は、F-始代数をいくつかの「コンストラクタ」の直和に分解できる現象の双対になっている。
P ( X ) {\displaystyle {\mathcal {P}}(X)} を X {\displaystyle X} の冪集合とし、これを集合の圏の共変関手とみなす。このとき、 P {\displaystyle {\mathcal {P}}} -余代数は二項関係の入った集合と一対一に対応する。さらにここで集合 A {\displaystyle A} を固定する。すると自己関手 P ( A × ( − ) ) {\displaystyle {\mathcal {P}}(A\times (-))} の余代数はラベルつき遷移系と一対一に対応し、余代数の間の準同型は関数双模倣に対応する。