Cartesian lukket kategori - Cartesian closed category

I kategoriteori er en kategori kartesisk lukket, hvis en morfisme defineret på et produkt af to objekter groft sagt kan identificeres naturligt med en morfisme defineret på en af faktorerne. Disse kategorier er især vigtige inden for matematisk logik og programmeringsteorien, idet deres interne sprog er den simpelthen indtastede lambda-beregning . De generaliseres af lukkede monoide kategorier , hvis interne sprog, lineære typesystemer er egnede til både kvante- og klassisk beregning.

Etymologi

Opkaldt efter René Descartes (1596–1650), fransk filosof, matematiker og videnskabsmand, hvis formulering af analytisk geometri gav anledning til begrebet kartesisk produkt , som senere blev generaliseret til begrebet kategorisk produkt .

Definition

Kategori C kaldes kartesisk lukket, hvis og kun hvis den opfylder følgende tre egenskaber:

Det har et terminalobjekt .
Helst to objekter X og Y af C har et produkt X × Y i C .
Helst to objekter Y og Z af C har en eksponentiel Z ^Y i C .

De to første betingelser kan kombineres til det enkelte krav om, at enhver endelig (muligvis tom) familie af genstande af C tillader et produkt i C på grund af det kategoriske produkts naturlige associativitet, og fordi det tomme produkt i en kategori er det terminale objekt af denne kategori.

Den tredje betingelse svarer til kravet om, at funktoren - × Y (dvs. funktoren fra C til C, der kortlægger objekter X til X × Y og morfismer φ til φ × id _Y ) har en ret sammenhæng , normalt betegnet - ^Y , for alle objekter Y i C . For lokalt små kategorier kan dette udtrykkes ved eksistensen af en sammenhæng mellem hjemsættene

{\ displaystyle \ mathrm {Hom} (X \ gange Y, Z) \ cong \ mathrm {Hom} (X, Z ^ {Y})}

som er naturligt i både X og Z .

Vær opmærksom på, at en lukket kategori i Cartesian ikke behøver at have begrænsede grænser; kun begrænsede produkter er garanteret.

Hvis en kategori har den egenskab, at alle dens segmentkategorier er kartesisk lukket, kaldes den lokalt kartesisk lukket . Bemærk, at hvis C er lokalt kartesisk lukket, behøver det ikke rent faktisk være kartesisk lukket; det sker, hvis og kun hvis C har et terminalobjekt.

Grundlæggende konstruktioner

Evaluering

For hvert objekt Y er det eksponentielle tillægs natur en naturlig transformation

{\ displaystyle \ mathrm {ev} _ {Y, Z}: Z ^ {Y} \ gange Y \ til Z}

kaldes det (interne) evalueringskort . Mere generelt kan vi konstruere det delvise applikationskort som kompositten

{\ displaystyle \ mathrm {papply} _ {X, Y, Z}: Z ^ {X \ times Y} \ times X \ cong (Z ^ {Y}) ^ {X} \ times X {\ xrightarrow {\ mathrm {ev} _ {X, Z ^ {Y}}}} Z ^ {Y}.}

I det særlige tilfælde for kategorien Sæt reduceres disse til almindelig drift:

{\ displaystyle \ mathrm {ev} _ {Y, Z} (f, y) = f (y).}

Sammensætning

Evaluering af det eksponentielle i et argument ved en morfisme p : X → Y giver morfismer

{\ displaystyle p ^ {Z}: X ^ {Z} \ til Y ^ {Z},}

{\ displaystyle Z ^ {p}: Z ^ {Y} \ til Z ^ {X},}

svarende til funktionen af sammensætning med p . Alternative notationer for operationen p ^Z inkluderer p _* og p∘- . Alternative notationer for driften Z ^p inkluderer p ^* og -∘p .

Evalueringskort kan lænkes som

{\ displaystyle Z ^ {Y} \ times Y ^ {X} \ times X {\ xrightarrow {\ mathrm {id} \ times \ mathrm {ev} _ {X, Y}}} Z ^ {Y} \ times Y {\ xrightarrow {\ mathrm {ev} _ {Y, Z}}} Z}

den tilsvarende pil under det eksponentielle tillæg

{\ displaystyle c_ {X, Y, Z}: Z ^ {Y} \ gange Y ^ {X} \ til Z ^ {X}}

kaldes (internt) kompositionskort .

I det særlige tilfælde af kategorien Sæt er dette den almindelige kompositionsoperation:

{\ displaystyle c_ {X, Y, Z} (g, f) = g \ circ f.}

Sektioner

For en morfisme p : X → Y , antag at der findes følgende pullback-firkant, der definerer underobjektet af X ^Y svarende til kort, hvis sammensatte med p er identiteten:

{\ displaystyle {\ begin {array} {ccc} \ Gamma _ {Y} (p) & \ to & X ^ {Y} \\\ downarrow && \ downarrow \\ 1 & \ to & Y ^ {Y} \ end {array }}}

hvor pilen til højre er p ^Y og pilen på de nederste svarer til identiteten på Y . Derefter kaldes Γ _Y ( p ) genstand for sektioner af p . Det forkortes ofte som Γ _Y ( X ).

Hvis Γ _Y ( p ) findes for hver morfisme p med kodomæne Y , kan den samles i en funktor Γ _Y : C / Y → C i kategorien skive, som er ret ved siden af en variant af produktfunktionen:

{\ displaystyle \ hom _ {C / Y} (X \ gange Y {\ xrightarrow {\ pi _ {2}}} Y, Z {\ xrightarrow {p}} Y) \ cong \ hom _ {C} (X , \ Gamma _ {Y} (p)).}

Eksponentialet af Y kan udtrykkes i form af sektioner:

{\ displaystyle Z ^ {Y} \ cong \ Gamma _ {Y} (Z \ gange Y {\ xrightarrow {\ pi _ {2}}} Y).}

Eksempler

Eksempler på kartesiske lukkede kategorier inkluderer:

Kategorien Sæt med alle sæt , med funktioner som morfismer, er kartesisk lukket. Produktet X × Y er den kartesiske produkt af X og Y , og Z ^Y er mængden af alle funktioner fra Y til Z . Den adjointness udtrykkes ved følgende faktum: funktionen f : X × Y → Z er naturligt identificeret med den curried funktion g : X → Z ^Y defineret ved g ( x ) ( y ) = f ( x , y ) for alle x i X og y i Y .
Kategorien af begrænsede sæt, med funktioner som morfismer, er kartesisk lukket af samme grund.
Hvis G er en gruppe , er kategorien for alle G- sæt kartesisk lukket. Hvis Y og Z er to G- sæt, er Z ^Y sættet med alle funktioner fra Y til Z med G- handling defineret af ( g . F ) ( y ) = g . (F ( g ^-1 .y)) for alle g i g , F : Y → Z og y i Y .
Kategorien af begrænsede G- sæt er også kartesisk lukket.
Kategorien Cat af alle små kategorier (med funktioner som morfismer) er kartesisk lukket; den eksponentielle C ^D er givet ved functor kategori består af alle functors fra D til C , med naturlige transformationer som morfier.
Hvis C er en lille kategori , er funktorkategorien Sæt ^{C, der} består af alle sammenvarende funktioner fra C i kategorien sæt, med naturlige transformationer som morfismer, kartesisk lukket. Hvis F og G er to functors fra C til sæt , så den eksponentielle F ^G er functor hvis værdi på objektet X af C er givet ved det sæt af alle fysiske transformationer fra ( X , -) × G til F .
- Det tidligere eksempel på G- sæt kan ses som et specielt tilfælde af funktorkategorier: hver gruppe kan betragtes som en kategori med et objekt, og G- sæt er intet andet end funktioner fra denne kategori til Set
- Kategorien af alle rettede grafer er kartesisk lukket; dette er en funktorkategori som forklaret under funktorkategori.
- Især er kategorien af enkle sæt (som er funktioner X : Δ ^op → Set ) kartesisk lukket.
Endnu mere generelt er alle elementære topos lukket i kartesisk.
I algebraisk topologi er kartesiske lukkede kategorier særlig lette at arbejde med. Hverken kategorien af topologiske rum med kontinuerlige kort eller kategorien af glatte manifolder med glatte kort er kartesisk lukket. Der er derfor taget hensyn til erstatningskategorier: kategorien af kompakt genererede Hausdorff-rum er kartesisk lukket, ligesom kategorien Frölicher-rum .
I ordens teori , komplet delvise ordrer ( CPO er) har en naturlig topologi, den Scott topologi , hvis kontinuerlig kort gøre danne en kartesiske lukket kreds (dvs. objekterne er de cpos, og morfier er Scott kontinuerte maps). Både currying og applicering er kontinuerlige funktioner i Scott-topologien, og currying sammen med Apply udgør sammenhængen.
En Heyting-algebra er et kartesisk lukket (afgrænset) gitter . Et vigtigt eksempel opstår fra topologiske rum. Hvis X er et topologisk rum, danner de åbne sæt i X objekterne i en kategori O ( X ), for hvilken der er en unik morfisme fra U til V, hvis U er en delmængde af V og ellers ingen morfisme. Denne poset er en lukket kategori fra Cartesian: "produktet" af U og V er skæringspunktet mellem U og V, og det eksponentielle U ^V er det indre af $U ∪ ( X \ V )$ .
En kategori med et objekt med nul
er kartesisk lukket, hvis og kun hvis det svarer til en kategori med kun et objekt og en identitetsmorfisme. Faktisk, hvis 0 er et indledende objekt og 1 er et endeligt objekt, og vi har , hvilket har kun et element. ${\ displaystyle 0 \ cong 1}$ ${\ displaystyle 0 \ cong 1}$ ${\ displaystyle \ mathrm {Hom} (X, Y) \ cong \ mathrm {Hom} (1, Y ^ {X}) \ cong \ mathrm {Hom} (0, Y ^ {X}) \ cong 1}$ ${\ displaystyle \ mathrm {Hom} (X, Y) \ cong \ mathrm {Hom} (1, Y ^ {X}) \ cong \ mathrm {Hom} (0, Y ^ {X}) \ cong 1}$
- Især enhver ikke-triviel kategori med et objekt uden nul, såsom en abelsk kategori , er ikke kartesisk lukket. Så kategorien af moduler over en ring er ikke kartesisk lukket. Men det functor tensor produktet er med en fast modul har en
ret adjungerede . Tensorproduktet er ikke et kategorisk produkt, så dette modsiger ikke ovenstående. Vi opnår i stedet, at kategorien af moduler er lukket monoformet . ${\ displaystyle - \ otimes M}$

Eksempler på lokalt kartesiske lukkede kategorier inkluderer:

Hver elementær topo er lokalt kartesisk lukket. Dette eksempel omfatter sæt , FinSet , G bruges til at vælge en gruppe G , samt sæt ^C for små kategorier C .
Kategorien LH, hvis objekter er topologiske rum, og hvis morfismer er lokale homeomorfier, er lokalt kartesisk lukket, da LH / X svarer til kategorien skiver . Imidlertid har LH ikke et terminalobjekt og er derfor ikke kartesisk lukket. ${\ displaystyle Sh (X)}$
Hvis C har pullbacks, og for hver pil p : X → Y , har funktoren p ^* : C / Y → C / X givet ved at tage pullbacks en rigtig adjoint, så er C lokalt kartesisk lukket.
Hvis C er lokalt kartesisk lukket, så er alle dets skivekategorier C / X også lokalt kartesiske lukket.

Ikke-eksempler på lokalt kartesiske lukkede kategorier inkluderer:

Katten er ikke lokalt kartesisk lukket.

Ansøgninger

I kartesiske lukkede kategorier kan en "funktion af to variabler" (en morfisme f : X × Y → Z ) altid repræsenteres som en "funktion af en variabel" (morfismen λ f : X → Z ^Y ). I datalogiske applikationer er dette kendt som currying ; det har ført til erkendelsen af, at simpel indtastet lambda-beregning kan fortolkes i en hvilken som helst kartesisk lukket kategori.

Den Curry-Howard-Lambek korrespondance giver en dyb isomorfi mellem intuitionistic logik, blot-indtastet lambdakalkyle og kartesiske lukkede kategorier.

Visse kartesiske lukkede kategorier, topoi , er blevet foreslået som en generel ramme for matematik i stedet for traditionel sætteori .

Den berømte computerforsker John Backus har slået til lyd for en variabel-fri notation eller Funktion-niveau programmering , som i baghånd ligner en vis lighed med det interne sprog i kartesisk lukkede kategorier. CAML er mere bevidst modelleret på lukkede kartesiske kategorier.

Afhængig sum og produkt

Lad C være en lokalt kartesisk lukket kategori. Derefter C har mange pullbacks, fordi tilbagetrækning af to pile med codomain Z er givet ved produktet i C / Z .

For hver pil p : X → Y , lad P betegne det tilsvarende formål med C / Y . At tage pullbacks langs p giver en funktion p ^* : C / Y → C / X, som har både en venstre og en højre tilslutning.

Venstre adjoint kaldes den afhængige sum og er givet ved sammensætning . ${\ displaystyle \ Sigma _ {p}: C / X \ til C / Y}$ ${\ displaystyle p \ circ (-)}$

Den rigtige tilknytning kaldes det afhængige produkt . ${\ displaystyle \ Pi _ {p}: C / X \ til C / Y}$

Eksponentialet med P i C / Y kan udtrykkes i form af det afhængige produkt ved hjælp af formlen . ${\ displaystyle Q ^ {P} \ cong \ Pi _ {p} (p ^ {*} (Q))}$

Årsagen til disse navne er fordi ved fortolkningen P som afhængige type af de functors og svarer til den type formationer og hhv. ${\ displaystyle y: Y \ vdash P (y): \ mathrm {Type}}$ ${\ displaystyle \ Sigma _ {p}}$ ${\ displaystyle \ Pi _ {p}}$ ${\ displaystyle \ Sigma _ {x: P (y)}}$ ${\ displaystyle \ Pi _ {x: P (y)}}$

Ligningsteori

I hvert kartesiske lukket kategori (ved hjælp af eksponentiel notation), ( X ^Y ) ^Z og ( X ^Z ) ^Y er isomorfe for alle objekter X , Y og Z . Vi skriver dette som "ligningen"

( x ^y ) ^z = ( x ^z ) ^y .

Man kan spørge, hvad andre sådanne ligninger er gyldige i alle lukkede kartesiske kategorier. Det viser sig, at alle følger logisk fra følgende aksiomer:

x × ( y × z ) = ( x × y ) × z
x × y = y × x
x × 1 = x (her betegner 1 terminalobjektet for C )
1 ^x = 1
x ¹ = x
( x × y ) ^z = x ^z × y ^z
( x ^y ) ^z = x ^{( y × z )}

Bicartesian lukkede kategorier

Bicartesian lukkede kategorier udvider Cartesian lukkede kategorier med binære coproducts og et indledende objekt med produkter, der distribueres over coproducts. Deres ligningsteori udvides med følgende aksiomer, hvilket giver noget der ligner Tarskis high school-aksiomer, men med additive inverser:

x + y = y + x
( x + y ) + z = x + ( y + z )
x × ( y + z ) = x × y + x × z
x ^{( y + z )} = x ^y × x ^z
0 + x = x
x × 0 = 0
x ⁰ = 1

Bemærk dog, at ovenstående liste ikke er komplet; type isomorfisme i den frie BCCC er ikke endeligt aksiomatiserbar, og dens afgørelighed er stadig et åbent problem.

Referencer

^ John C. Baez og Mike Stay, " Physics, Topology, Logic and Computation: A Rosetta Stone ", (2009) ArXiv 0903.0340 i New Structures for Physics , red. Bob Coecke, Lecture Notes in Physics vol. 813 , Springer, Berlin, 2011, s. 95-174.
^ Saunders., Mac Lane (1978). Kategorier til den arbejdende matematiker (2. udgave). New York, NY: Springer New York. ISBN 1441931236. OCLC 851741862 .
^ "kartesisk lukket kategori i nLab" . ncatlab.org . Hentet 17-09-2017 .
^ Lokalt kartesisk lukket kategori i nLab
^ HP Barendregt, The Lambda Calculus , (1984) Nordholland ISBN 0-444-87508-5 (Se sætning 1.2.16)
^ "Ct.category theory - er kategorien kommutative monoider cartesian lukket?" .
^ S. Soloviev. "Kategori af endelige sæt og kartesiske lukkede kategorier", Journal of Soviet Mathematics, 22, 3 (1983)
^ Fiore, Cosmo og Balat. Bemærkninger om isomorfier i typiske Lambda Calculi med tomme og sumtyper [1]

Seely, RAG (1984). "Lokalt kartesianske lukkede kategorier og typeteori". Matematiske procedurer fra Cambridge Philosophical Society . 95 (1): 33–48. doi : 10.1017 / S0305004100061284 . ISSN 1469-8064 .

eksterne links

Kartesisk lukket kategori i nLab
Et blogindlæg om forholdet mellem CCC'er og lambda-calculus : https://golem.ph.utexas.edu/category/2006/08/cartesian_closed_categories_an_1.html

[1] John C. Baez og Mike Stay, " Physics, Topology, Logic and Computation: A Rosetta Stone ", (2009) ArXiv 0903.0340 i New Structures for Physics , red. Bob Coecke, Lecture Notes in Physics vol. 813 , Springer, Berlin, 2011, s. 95-174.

[2] Saunders., Mac Lane (1978). Kategorier til den arbejdende matematiker (2. udgave). New York, NY: Springer New York. ISBN 1441931236. OCLC 851741862 .

[3] "kartesisk lukket kategori i nLab" . ncatlab.org . Hentet 17-09-2017 .

[4] Lokalt kartesisk lukket kategori i nLab

[5] HP Barendregt, The Lambda Calculus , (1984) Nordholland ISBN 0-444-87508-5 (Se sætning 1.2.16)

[6] "Ct.category theory - er kategorien kommutative monoider cartesian lukket?" .

[7] S. Soloviev. "Kategori af endelige sæt og kartesiske lukkede kategorier", Journal of Soviet Mathematics, 22, 3 (1983)

[8] Fiore, Cosmo og Balat. Bemærkninger om isomorfier i typiske Lambda Calculi med tomme og sumtyper [1]

Languages

In other projects