Sammanfattning av denna webbsida: Denna uppsats försöker förklara varför och hur kategoriteori är användbar inom datavetenskap, genom att ge riktlinjer för tillämpning av sju grundläggande kategoriska begrepp: kategori, functor, naturlig omvandling, gräns, angränsande, colimit och komma kategori. Några exempel, intuition, och referenser ges för varje koncept, men fullständighet är inte försök. Några ytterligare kategoriska begrepp och förslag till ytterligare forskning nämns också. Dokumentet avslutas med en del filosofiska diskussioner. Denna uppsats försöker förklara varför kategoriteori är användbar inom datavetenskap. Det grundläggande svaret är att datavetenskap är en ung eld som växer snabbt, är dåligt organiserad, och behöver all hjälp den kan få, och att kategoriteori kan ge hjälp med åtminstone följande: Formulera de nitions och teorier. Inom datavetenskapen är det ofta mer kult att formulera begrepp och resultat än att ge ett bevis. De sju riktlinjerna i detta dokument kan vara till hjälp vid utformningen; riktlinjerna kan också användas för att mäta elegansen och samstämmigheten i befintliga formuleringar. Utföra bevis. När grundbegreppen väl har formulerats korrekt på ett kategoriskt språk, verkar det ofta som om bevis bara händer ": vid varje steg finns det en naturlig" sak att prova, och det fungerar. Diagram jagar se Avsnitt 1.2 ger många exempel på detta. Man kan nästan säga att syftet med kategoriteorin är att reducera alla bevis till sådana enkla beräkningar. Upptäcka och utnyttja relationer med andra alder. Successivt abstrakta formuleringar kan avslöja överraskande kopplingar. Till exempel, en analogi mellan Petri nät och -calculus kan föreslå letar efter en sluten kategori struktur på kategorin Petri nät 52. Att hantera abstraktion och representationsoberoende. Inom datavetenskapen är mer abstrakta synsätt ofta mer användbara, på grund av behovet av att uppnå självständighet från de ofta överväldigande komplexa detaljerna om hur saker representeras eller genomförs. En följd av den första riktlinjen som ges i avsnitt 1 är att två objekt är abstrakt samma" i de är isomorfa; se avsnitt 1.1. Dessutom, universella konstruktioner d.v.s., gränsar till sina resultat unikt upp till isomorfism, d.v.s. abstrakt" i just denna mening. Den forskning som redovisas i denna uppsats har delvis fått stöd genom bidrag från Science and Engineering Research Council, National Science Foundation, och System Development Foundation, samt kontrakt med O ce of Naval Research och Fujitsu Corporation. Kategoriteorin kan också missbrukas, och i flera olika ämnen. En form av missbruk är särdeles allmängiltighet, där någon teori eller ett exempel generaliseras på ett sätt som faktiskt inte innehåller några nya exempel på verkligt intresse. En relaterad typ av missbruk är kategoriskt overkill, där språket i kategoriteori används för att beskriva fenomen som faktiskt inte kräver en sådan utstuderad behandling eller terminologi. Ett exempel är att beskriva en Galois-anslutning på språket för angränsande functors. Kategoriteorin har kallats abstrakt nonsens" av både dess vänner och dess förtalare. Kanske vad denna fras antyder för båda är att kategoriteori har relativt mer form än innehåll, jämfört med andra områden av matematik. Dess vänner hävdar detta som en dygd, i motsats till den överdrivna konkretitet och representation beroende av uppsättningar teoretiska grunder, och den relativt dåliga vägledning för att upptäcka eleganta och sammanhängande teorier som de ger. Avsnitt 9 behandlar detta ytterligare. Kategoriteori kan också användas på ganska konkreta sätt, eftersom kategorier efter alla bara en annan algebraisk struktur, generalisera både monoider och partiella order se även Exempel 1.4 nedan. I detta dokument presenteras sju riktlinjer för användning av kategoriteori, var och en med en allmän diskussion och särskilda exempel. Det finns inget anspråk på originalitet, eftersom jag tror att de underliggande intuitionerna delas av i huvudsak alla arbetare i kategoriteori, även om de kanske har varit förståeligt motvilliga att placera sådana dogmatiska påståenden i läroböcker eller andra skrivna dokument 1. Riktlinjerna är nödvändigtvis otydliga, och kommer att verka överdrivna om de tas alltför bokstavligt, eftersom de inte är objektiva fakta, utan snarare heuristiker för att tillämpa vissa matematiska begrepp. I synnerhet kan de förefalla vara kult att tillämpa, eller till och med omöjliga, i vissa situationer, och de kan behöva re nement i andra. Som en påminnelse om att de inte bör tas alltför dogmatiskt, kommer jag att kalla dem dogmer. Inga försök görs att vara uttömmande. I synnerhet utelämnas de tekniska förklaringarna, eftersom vårt syfte är att ge intuition, och de kan hittas i vilken lärobok som helst. Således, om du är en nykomling till kategori teori, y ou kommer att behöva använda någon text i samband med detta papper. Tyvärr är ingen befintlig text idealisk för dataforskare, men kanske det av Goldblatt 36 kommer närmast. Den klassiska texten av Mac Lane 47 rekommenderas varmt för dem med tillräcklig matematikbakgrund, och Herrlich och Streckers bok 39 är beundransvärt grundlig; se även 2 och 45. Tidningen 22 ger ett relativt konkret och fristående konto o f några grundläggande kategori teori för dataforskare, med hjälp av teorier, ekvationer, och uni katjon som motivation, och många exempel från detta papper används här. Så vitt jag vet, är det första sådana försök min o wn i 34, vilket ger fyra av riktlinjerna här. Det enda andra försöket som jag vet beror på Lambek och Scott 45, som ger en numberof slagord "i en liknande stil. Den första dogmen är följande: För att each arter av matematisk struktur, det c ellerresponderar en kategori vars objekt har denna struktur, och vars morfismer bevara den. Det är en del av denna riktlinje att det för att förstå en struktur är nödvändigt att förstå de morfismer som bevarar den. I själva verket har kategoriteoretiker hävdat att morfismer är viktigare än objekt, eftersom de avslöjar vad strukturen egentligen är. Dessutom kan kategoribegreppet benämnas endast med hjälp av morfismer. Kanske är det så att de moderna västerländska språkens och kulturernas fördomar mot objekt snarare än relationer står för detta, jfr. 50, 64 för en del närbesläktade diskussioner. Som notation använder vi ;" för sammansättning, och 1 A för identitet morfismen vid ett objekt A. Nu några exempel: 1.1 Ställer. Om vi tar set för att beobjects, då deras morphisms kommer helt klart att fungera. En viss morfism är dock inte bara en uppsättning beställda par, eftersom den också måste ange särskilda källor och måluppsättningar. Detta är förenligt med praxis i beräkningsteori som tilldelar typer till funktioner. Den uppsättning teoretiska representationen av funktioner är en artefakt av den uppsättning teoretiska grunderna i matematik, och som alla sådana representationer, har oavsiktliga egenskaper utöver de i begreppet är det avsett att fånga. En av dessa egenskaper är att två uppsättningar beställda par kan kombineras för att ge en tredjedel. Kategorin Set av sätter förkroppsligar en motsatt synvinkel, att varje funktion har en domän där dess argument är meningsfull, en codomain där dess resultat är meningsfulla, och sammansättning av funktioner är endast tillåtet när meningsfull i denna mening. Se 36 för relaterade diskussioner. 1.2 Förbindelser. Precis som med funktioner, verkar det önskvärt att anta att sammansättningen av relationer är bara meningsfullt när domänerna matchar. Således m a y de ne a relation från en uppsättning A 0 till en uppsättning A 1 att vara en trippel A 0 ; R ; A 1 med R A 0 A 1, och sedan tillåta dess sammansättning med B 0 ; S ; B 1 de ner i A 1 = B 0. Detta ger upphov till en kategori som vi betecknar Rel, av vilken Set kan betraktas som en underkategori. 1.3 Diagram. En graf G består av en uppsättning E av kanter, en uppsättning N av noder, och två funktioner @ 0 ; @ 1 : E! N som ger källan och målet för varje kant, respektive. Eftersom de viktigaste komponenterna i grafer är uppsättningar, de viktigaste komponenterna i deras morfismer bör vara motsvarande funktioner som bevarar den ytterligare strukturen. Således en morfism från G = E;N;@ 0; @ 1 till G 0 = E 0; N 0; @ 0; @ 0 1 består av två funktioner, f: E! E 0 och g : N! N 0, sådan att följande diagram pendlar i Set för i = 0 ; 1: För att visa att vi h a ve en kategori Diagram av grafer, vi m ust visar att en sammansättning av två sådana morfismer är en annan, och att ett par identitetsfunktioner satis es diagrammen och också fungerar som en identitet för komposition. Eftersom de viktigaste komponenterna i automata är uppsättningar, de viktigaste komponenterna i deras morfismer bör vara motsvarande funktioner som bevarar strukturen. där fg betecknar en godtycklig en punkt som anges med punkt. Det måste visas att en sammansättning av två sådana morfismer är en annan, och att en trippel av identiteter satis diagrammen och fungerar som en identitet för komposition. Dessa kontroller visar att vi har en kategori Aut av automata, och deras enkelhet ökar vår samstämmighet i riktigheten av deioner 18. 1.6 Typer. Typer används för att klassificera saker", och enligt den första dogmen, de bör bilda en kategori som har typer som objekt; naturligtvis, beroende på vad som klassificeras, kommer olika kategorier att uppstå. Ett enkelt exempel är nita produkttyper, som på ett bekvämt sätt representeras av naturliga tal, med morfismer som beskriver vad som kan kallas registeröverföring" bland tupler av register. Alltså, n 2! anger en n-tuple ht 1 ; ::; t n i av dataobjekt i n register ", och en morfism f : m! n är en funktion f1, ::; ng! f 1; :::; mg anger att innehållet i registret fi bör överföras till register i, för i = 1 ; :::; n. I själva verket, om vi identifierar siffran med uppsättningen f1; ::; ng och 0 med ;, då denna kategori är motsatsen till en underkategori av Set; låt oss beteckna det N. En variant av N har som objekt nite undergrupper av en xed countable uppsättning X, och som morfismer igen motsatsen till funktioner bland dessa, så att vi får en annan motsatsen till en underkategori av Set, betecknar säga X. Här är registren" betecknade med variabla symboler" från X, snarare än med naturliga tal. Går lite längre, kan vi tilldela typer från en uppsättning S till symbolerna i X, och kräver att morfismerna bevarar dessa typer. Låt oss beteckna denna kategori X S. 4 1.7 Ersättningar. Två nyckelattribut för en substitution är den uppsättning variabler i vilka den ersätter, och den uppsättning variabler som förekommer i vad den ersätter. Därför har substitutioner naturliga källor och målobjekt, var och en en uppsättning variabler, som i exempel 1.6 ovan. Det är uppenbart att det finns identitetssubstitutioner för varje uppsättning variabler som ersätter varje variabel för sig, och sammansättningen av substitutioner är associativ när de fastställs. Således får vi en kategori med substitutioner som morfismer.
De första CT-tillämpningarna inom datavetenskap och det allmänna påståendet om CT:s extrema användbarhet för datortillämpningar bör naturligtvis tillskrivas Joseph Goguen REF.
A categorical manifesto
{'venue': 'Mathematical Structures in Computer Science', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}