F-algebra - F-algebra

Komutativní diagram, který definuje vlastnost požadovanou morfismem originálu kategorie, aby to mohly být morfizmy nově definované kategorie F-algebry.

v matematika, konkrétně v teorie kategorií, F-algebry zobecnit pojem algebraická struktura. Přepis algebraických zákonů na morfismy eliminuje všechny odkazy na kvantifikované prvky z axiomů a tyto algebraické zákony pak mohou být slepeny dohromady, pokud jde o jeden funktor F, podpis.

F-algebry lze také použít k reprezentaci datové struktury použito v programování, jako seznamy a stromy.

Hlavní související pojmy jsou počáteční F-algebry, které mohou sloužit k zapouzdření indukčního principu, a dvojí konstrukce F-coalgebry.

Definice

Li C je kategorie, a F: C → C je endofunctor z C, pak F-algebra je n-tice (A, α), kde A je objekt z C a α je a C-morfismus F(A) → A. Objekt A se nazývá dopravce algebry. Pokud je to z kontextu přípustné, na algebry se často odkazuje jejich dopravcem pouze místo n-tice.

A homomorfismus z F-algebra (A, α) na an F-algebra (B, β) je a C-morfismus F: A→B takhle F ∘ α = β ∘ F(F), podle následujícího komutativní diagram:

Vybaven těmito morfismy, F-algebry tvoří kategorii.

Duální konstrukce jsou F-coalgebras, což jsou objekty A^* společně s morfismem α^* : A^* → F(A^*).

Příklady

Skupiny

Klasicky, a skupina je soubor G s binární operací m : G × G → G, splňující tři axiomy:

asociativita: ∀ x∈G, ∀ y∈G, ∀ z∈G, m(m(X, y), z) = m(X, m(y, z)),
prvek identity: ∃ 1∈G, ∀ x∈G, m(1, X) = m(X, 1) = X,
inverzní prvek: ∃ 1∈G, ∀ x∈G, ∃ X⁻¹∈G, m(X⁻¹, X) = m(X, X⁻¹) = 1.

Všimněte si, že uzavření axiom je obsažen v symbolické definici m.

Abychom to zacházeli v kategorickém rámci, nejprve definujeme identitu a inverzi jako morfismy E a i resp. Nechat C být libovolná kategorie s konečnými produkty a a koncový objekt *. Skupina G je objekt v C. Morfismus E odešle každý prvek v * na 1, prvek identity skupiny G. Morfismus i odešle každý prvek X v G k jeho inverzi X⁻¹, uspokojující m(X⁻¹, X) = m(X, X⁻¹) = 1. Potom skupina G lze definovat jako 4 n-tici (G, m, E, i), který popisuje a kategorie monoidů pouze s jedním objektem G. Každý morfismus F v této kategorii monoidů má inverzní F⁻¹ to uspokojuje F⁻¹ ∘ F = F ∘ F⁻¹ = Id.^[1]

Potom je možné přepsat axiomy z hlediska morfismů:

∀ x∈G, ∀ y∈G, ∀ z∈G, m(m(X, y), z) = m(X, m(y, z)),
∀ x∈G, m(E(*), X) = m(X, E(*)) = X,
∀ x∈G, m(i(X), X) = m(X, i(x)) = E(*).

Poté odeberte odkazy na prvky G (což také odstraní univerzální kvantifikátory):

m∘(m, Id) = m∘(Id, m),
m∘(E, Id) = m∘(Id, E) = Id,
m∘(i, Id) = m∘(Id, i) = E.

Což je stejné jako u komutativity pro následující diagramy:^[2]

Nyní použijte koprodukt (dále jen disjunktní unie množin) k lepení tří morfismů do jednoho: α = E + i + m podle

{ displaystyle { begin {matrix} alpha: {1} + G + G krát G & to & G, 1 & mapsto & 1, x & mapsto & x ^ {- 1}, (x, y) & mapsto & x cdot y. end {matrix}}}

To definuje skupinu jako a F-algebra kde F je funktor F(G) = 1 + G + G × G.

Poznámka 1: Výše uvedená konstrukce se používá k definování skupinové objekty nad libovolnou kategorií s konečnými produkty a koncovým objektem *. Když kategorie připouští konečné koprodukty, objekty skupiny jsou F-algebry. Například konečné skupiny jsou F-algebry v kategorii konečné množiny a Lež skupiny jsou F-algebry v kategorii hladké potrubí s hladké mapy.

Algebraické struktury

Jít o krok napřed univerzální algebra, většina algebraických struktur je F-algebry. Například, abelianské skupiny jsou F-algebry pro stejný funktor F(G) = 1 + G + G×G pokud jde o skupiny, s dalším axiomem pro komutativitu: m∘t = m, kde t(X,y) = (y,X) je provedení GXG.

Monoidy jsou F-algebry podpisu F(M) = 1 + M×M. Ve stejném duchu, poloskupiny jsou F-algebry podpisu F(S) = S×S

Prsteny, domén a pole jsou také F-algebry s podpisem zahrnujícím dva zákony +, •: R×R → R, aditivní identita 0: 1 → R, multiplikativní identita 1: 1 → R, a aditivní inverzní pro každý prvek -: R → R. Protože všechny tyto funkce sdílejí stejné codomain R lze je slepit do jedné funkce podpisu 1 + 1 + R + R×R + R×R → R, s axiomy k vyjádření asociativity, distribučnost, a tak dále. To dělá prsteny F-algebry na kategorie sad s podpisem 1 + 1 + R + R×R + R×R.

Alternativně se můžeme podívat na funktor F(R) = 1 + R×R v kategorie abelianských skupin. V tomto kontextu je množení homomorfismus, což znamená m(X + y, z) = m(X,z) + m(y,z) a m(X,y + z) = m(X,y) + m(X,z), což jsou přesně podmínky distribuce. Proto je prsten F-algebra podpisu 1 + R×R nad kategorií abelianských skupin, která splňuje dva axiomy (asociativitu a identitu pro množení).

Když přijdeme k vektorové prostory a moduly, funktor podpisu zahrnuje a skalární násobení k×E → Ea podpis F(E) = 1 + E + k×E je parametrizován pomocí k přes kategorii polí nebo prstenů.

Algebry nad polem lze zobrazit jako F-algebry podpisu 1 + 1 + A + A×A + A×A + k×A nad kategorií sad podpis 1 + A×A přes kategorie modulů (modul s interním násobením) a podpis k×A přes kategorie prstenů (kruh se skalárním násobením), když jsou asociativní a unitární.

Mříž

Ne všechny matematické struktury jsou F-algebry. Například a poset P lze definovat kategoricky morfismem s:P × P → Ω, na a klasifikátor podobjektu (Ω = {0,1} v kategorii sad a s(X,y) = 1 přesně když X≤y). Axiomy omezující morfismus s definovat poset lze přepsat pomocí morfismů. Jako codomain of s je Ω a ne P, to není F-algebra.

Nicméně, mříže ve kterém každé dva prvky mají supremum a infimum, a to zejména celkový počet objednávek, jsou F-algebry. Důvodem je, že je lze ekvivalentně definovat z hlediska algebraických operací: X∨y = inf (X,y) a X∧y = sup (X,y), s výhradou určitých axiomů (komutativita, asociativita, absorpce a idempotence). Takové jsou F-algebry podpisu P X P + P X P. Často se říká, že teorie mřížky čerpá jak z teorie řádu, tak z univerzální algebry.

Opakování

Zvažte funktor ${ displaystyle F: mathrm { bf {Set}} to mathrm { bf {Set}}}$ který pošle sadu ${ displaystyle X}$ na ${ displaystyle 1 + X}$ . Tady, ${ displaystyle mathrm { bf {Set}}}$ označuje kategorii sad, ${ displaystyle +}$ označuje obvyklé koprodukt dané disjunktní unie, a ${ displaystyle 1}$ je koncový objekt (tj. jakýkoli jedináček soubor). Pak sada ${ displaystyle mathbb {N}}$ z přirozená čísla společně s funkcí ${ displaystyle [ mathrm {nula}, mathrm {succ}]: 1+ mathbb {N} to mathbb {N}}$ —Který je koproduktem funkcí ${ displaystyle mathrm {nula}: 1 mapsto 0}$ a ${ displaystyle mathrm {succ}: n mapsto n + 1}$ -je F-algebra.

Počáteční F-algebra

Pokud je kategorie F-algebry pro daný endofunktor F má počáteční objekt, nazývá se to počáteční algebra. Algebra ${ displaystyle ( mathbb {N}, [ mathrm {nula}, mathrm {succ}])}$ ve výše uvedeném příkladu je počáteční algebra. Rozličný konečný datové struktury použito v programování, jako seznamy a stromy, lze získat jako počáteční algebry konkrétních endofunktorů.

Typy definované pomocí nejméně pevný bod konstrukce s funktorem F lze považovat za iniciálu F-algebra, za předpokladu, že parametricita drží pro typ.^[3]

Viz také Univerzální algebra.

Terminál F-coalgebra

V dvojí způsobem existuje podobný vztah mezi pojmy největší pevný bod a terminál F-coalgebra. Ty lze použít k povolení potenciálně nekonečný předměty při údržbě silná normalizační vlastnost.^[3] V silně normalizaci Charita programovací jazyk (tj. každý program v něm končí), koinduktivní datové typy lze použít k dosažení překvapivých výsledků, což umožňuje definici vzhlédnout konstrukty k implementaci takových "silný" funkce jako Ackermannova funkce.^[4]

Viz také

Poznámky

^ Oddíl I.2, III.6 v Mac Lane, Saunders (1988). Kategorie pro pracujícího matematika (4. kor. Tisk. Vyd.). New York: Springer-Verlag. ISBN 0-387-90035-7.
^ Svislé šipky bez popisků ve třetím diagramu musí být jedinečné, protože * je koncový.
^ ^A ^b Philip Wadler: Rekurzivní typy zdarma! University of Glasgow, červen 1990. Koncept.
^ Robin Cockett: Charitable Thoughts (ps^{[trvalý mrtvý odkaz ]} a ps.gz^{[trvalý mrtvý odkaz ]})

Reference

Pierce, Benjamin C. (1991). "F-Algebry “. Teorie základní kategorie pro počítačové vědce. ISBN 0-262-66071-7.
Barr, Michael; Wells, Charles (1990). Teorie kategorií pro výpočetní vědu. New York: Prentice Hall. str. 355. ISBN 0131204866. OCLC 19126000.

externí odkazy

Kategorické programování s indukčními a koindukčními typy od Varmo Vene
Philip Wadler: Rekurzivní typy zdarma! University of Glasgow, červen 1990. Koncept.
Algebra a uhlígebra od CLiki
Jacobs, J. Rutten: Výukový program pro (Co) Algebry a (Co) Indukci. Bulletin Evropské asociace pro teoretickou informatiku, sv. 62, 1997
Porozumění F-algebrám autor Bartosz Milewski

[1] Oddíl I.2, III.6 v Mac Lane, Saunders (1988). Kategorie pro pracujícího matematika (4. kor. Tisk. Vyd.). New York: Springer-Verlag. ISBN 0-387-90035-7.

[2] Svislé šipky bez popisků ve třetím diagramu musí být jedinečné, protože * je koncový.

[free-rectypes-3] A ^b Philip Wadler: Rekurzivní typy zdarma! University of Glasgow, červen 1990. Koncept.

[4] Robin Cockett: Charitable Thoughts (ps^{[trvalý mrtvý odkaz ]} a ps.gz^{[trvalý mrtvý odkaz ]})

[1]

[2]

[3]

[4]