F代数

数学、特に圏論において、F代数は代数構造の概念を一般化します。 代数法則を射の観点から書き直すと、公理から量化要素への参照がすべて削除され、これらの代数法則は単一の関数 F、シグネチャの観点からまとめることができます。

F代数は、リストやツリーなど、プログラミングで使用されるデータ構造を表すためにも使用できます。

主な関連概念は、帰納原理をカプセル化するのに役立つ可能性のある初期 F代数と、双対構成F余代数です。

がカテゴリで、 がの自己関数子である場合、-代数はタプル であり、 はの対象であり、は-射です。この対象は代数のキャリアと呼ばれます。文脈から許される場合、代数はタプルではなくキャリアのみで参照されることがよくあります。 ${\displaystyle C}$${\displaystyle F:C\rightarrow C}$${\displaystyle C}$${\displaystyle F}$${\displaystyle (A,\alpha )}$${\displaystyle A}$${\displaystyle C}$${\displaystyle \alpha}$${\displaystyle C}$ ${\displaystyle F(A)\rightarrow A}$${\displaystyle A}$

-代数から-代数への準同型とは、次の可換図式に従って、となる-射である。 ${\displaystyle F}$${\displaystyle (A,\alpha )}$${\displaystyle F}$${\displaystyle (B,\beta )}$${\displaystyle C}$${\displaystyle f:A\rightarrow B}$${\displaystyle f\circ \alpha =\beta \circ F(f)}$

これらの射を備えた- 代数はカテゴリを構成します。 ${\displaystyle F}$

双対構成は-余代数であり、これは射を伴うオブジェクトです。 ${\displaystyle F}$${\displaystyle A^{*}}$${\displaystyle \alpha^{*}:A^{*}\rightarrow F(A^{*})}$

古典的には、群は群法則を持つ集合であり、 は単位元の存在、群の各元に対する逆元の存在、結合性という 3 つの公理を満たします。 ${\displaystyle G}$ ${\displaystyle m:G\times G\rightarrow G}$${\displaystyle m(x,y)=x\cdot y}$

これをカテゴリカルな枠組みに当てはめるには、まず を、をとする関数（集合 の射）として恒等関数と逆関数を定義します。ここで は1 つの要素 を持つ集合を表し、これにより を射 で要素と同一視できるようになります。 ${\displaystyle G}$${\displaystyle e:1\rightarrow G}$${\displaystyle e(*)=1}$${\displaystyle i:G\rightarrow G}$${\displaystyle i(x)=x^{-1}}$${\displaystyle 1}$${\displaystyle 1=\left\{*\right\}}$${\displaystyle x\in G}$${\displaystyle 1\rightarrow G}$

すると、群の公理を関数で記述することが可能になります (存在量指定子がないことに注意してください)。

• ${\displaystyle \forall x\in G,\forall y\in G,\forall z\in G,m(m(x,y),z)=m(x,m(y,z))}$、
• ${\displaystyle \forall x\in G,m(e(*),x)=m(x,e(*))=x}$、
• ${\displaystyle \forall x\in G,m(i(x),x)=m(x,i(x))=e(*)}$。

これを可換図式で表現すると次のようになる: ^{[1] [2]}

ここで、余積（集合の非結合和）を使って3つの射を1つにまとめます。 ${\displaystyle \alpha =e+i+m}$

${\displaystyle {\begin{matrix}\alpha :{1}+G+G\times G&\to &G,\\*&\mapsto &1,\\x&\mapsto &x^{-1},\\(x,y)&\mapsto &x\cdot y.\end{matrix}}}$

したがって、群は、が関数である -代数です。ただし、その逆は必ずしも真ではありません。 が関数である -代数の中には、群ではないものもあります。 ${\displaystyle F}$${\displaystyle F}$${\displaystyle F(G)=1+G+G\times G}$${\displaystyle F}$${\displaystyle F}$${\displaystyle F(G)=1+G+G\times G}$

上記の構成は、有限積と終端オブジェクトを持つ任意のカテゴリ上のグループオブジェクトを定義するために使用されます。カテゴリが有限余積を許容する場合、グループオブジェクトは-代数です。たとえば、 有限グループは有限集合のカテゴリの -代数であり、リー群は滑らかな写像を持つ滑らかな多様体のカテゴリの -代数です。 ${\displaystyle 1}$${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$

普遍代数より一歩進んで、ほとんどの代数構造はF代数です。たとえば、アーベル群は、群の場合と同じ関数F ( G ) = 1 + G + G × Gに対するF代数ですが、可換性の公理m ∘ t = mが追加されています。ここで、t ( x , y ) = ( y , x ) はG x G上の転置です。

モノイドはシグネチャF ( M ) = 1 + M × MのF代数です。同様に、半群はシグネチャF ( S ) = S × SのF代数です。

環、領域、体も、2 つの法則 +、•: R × R → R、加法恒等式 0: 1 → R、乗法恒等式 1: 1 → R、各要素の加法逆 -: R → Rを含むシグネチャを持つ F 代数です。これらすべての関数は同じ余領域 R を共有するため、結合法則、分配法則などを表現する公理を持つ単一のシグネチャ関数 1 + 1 + R + R × R + R × R → Rに接着できます。これにより、環は、シグネチャ 1 + 1 + R + R × R + R × Rを持つ集合のカテゴリ上のF代数になります。

あるいは、アーベル群のカテゴリで関数F ( R ) = 1 + R × Rを見ることができます。そのコンテキストでは、乗算は準同型であり、m ( x  +  y , z ) = m ( x , z ) +  m ( y , z ) およびm ( x , y  +  z ) = m ( x , y ) +  m ( x , z ) を意味し、これらはまさに分配法則条件です。したがって、環は、アーベル群のカテゴリ上のシグネチャ 1 + R × RのF代数であり、2 つの公理（乗算の結合性と恒等性）を満たします。

ベクトル空間と加群に関しては、シグネチャ関数にはスカラー乗算 k × E → Eが含まれ、シグネチャF ( E ) = 1 + E + k × Eは体または環のカテゴリ上の kによってパラメータ化されます。

体上の代数は、結合的かつユニタリである場合、集合のカテゴリ上のシグネチャ1 + 1 + A + A × A + A × A + k × A 、加群のカテゴリ（内部乗算を持つ加群）上のシグネチャ 1 + A × A 、および環のカテゴリ（スカラー乗算を持つ環）上のシグネチャk × Aの F 代数として見ることができます。

すべての数学的構造がF代数であるわけではありません。たとえば、poset P は、サブオブジェクト分類子(集合のカテゴリでは Ω = {0,1} であり、x ≤ yのときにs ( x , y )=1 となる) 上の射s : P × P → Ω を用いてカテゴリカルな用語で定義できます。poset を定義するために射s を制限する公理は、射の用語で書き直すことができます。ただし、 sの共域はΩ でありP ではないため、これはF代数 ではありません。

しかし、格子、つまり 2 つの元ごとに上限と下限を持つ半順序、特に全順序はF代数です。これは、特定の公理 (可換性、結合性、吸収性、および冪等性) に従って、x ∨ y = inf( x , y ) およびx ∧ y = sup( x , y ) という代数演算で同等に定義できるためです。したがって、これらはシグネチャP x P + P x PのF代数です。格子理論は順序理論と普遍代数の両方に基づいているとよく言われます。

集合を に送信する関数を考えます。ここで、 は集合のカテゴリを表し、 は非結合和によって与えられる通常の余積を表し、 は終端オブジェクト（つまり、任意の単集合）です。すると、自然数の集合 と関数（これは関数 と の余積です）を合わせると、F代数になります。 ${\displaystyle F:\mathrm {\bf {セット}} \to \mathrm {\bf {セット}} }$${\displaystyle X}$${\displaystyle 1+X}$${\displaystyle \mathrm {\bf {セット}} }$${\displaystyle +}$${\displaystyle 1}$${\displaystyle \mathbb {N} }$${\displaystyle [\mathrm {zero} ,\mathrm {succ} ]:1+\mathbb {N} \to \mathbb {N} }$${\displaystyle \mathrm {ゼロ} :1\mapsto 0}$${\displaystyle \mathrm {成功} :n\mapsto n+1}$

与えられた自己関数FのF代数のカテゴリに初期オブジェクトがある場合、それは初期代数と呼ばれます。上記の例の代数は初期代数です。リストやツリーなど、プログラミングで使用されるさまざまな有限データ構造は、特定の自己関数の初期代数として取得できます。 ${\displaystyle (\mathbb {N} ,[\mathrm {zero} ,\mathrm {succ} ])}$

関数Fを持つ最小不動点構造を使用して定義された型は、その型にパラメトリシティが成立する限り、初期F代数とみなすことができます。 ^[3]

普遍代数も参照してください。

二重の意味で、最大不動点と終端F余代数の概念の間にも同様の関係が存在します。これらは、強い正規化特性を維持しながら潜在的に無限のオブジェクトを許可するために使用できます。^[3]強く正規化するCharityプログラミング言語（つまり、各プログラムはその言語で終了します）では、共帰納的データ型を使用して驚くべき結果を達成することができ、ルックアップ構造の定義でアッカーマン関数などの「強い」関数を実装することができます。^[4]

• モナドの代数
• 代数データ型
• 異形作用
• ダイアル代数

• 帰納的型と共帰納的型によるカテゴリカルプログラミング (2020-11-30 にWayback Machineでアーカイブ) Varmo Vene 著
• Philip Wadler: 再帰型を無料で! ( Wayback Machineに 2020-11-30 アーカイブ) グラスゴー大学、1990 年 6 月。ドラフト。
• 代数と余代数 (2019-04-27 にWayback Machineでアーカイブ) CLiki より
• B. Jacobs、J. Rutten: (Co) 代数と (Co) 帰納法に関するチュートリアル。欧州理論計算機科学協会紀要、第 62 巻、1997 年、2021 年 2 月 12 日にWayback Machineにアーカイブ
• F-代数の理解 ( Wayback Machineで 2020-08-04 にアーカイブ) by Bartosz Milewski