Kartezyen kapalı kategori - Cartesian closed category

Gelen Kategori teorisi , bir kategori Kartezyen kapalı kabaca bile, herhangi bir morfizmanın bir tanımlı ürün iki nesne doğal faktörlerden birinde tanımlanan bir morfizma ile tespit edilebilir. Bu kategoriler içinde özellikle önemlidir matematiksel mantık ve bunların ki, programlama teorisinin iç dil olduğunu basitçe daktilo lambda hesabı . İç dili, lineer tip sistemleri hem kuantum hem de klasik hesaplama için uygun olan kapalı monoidal kategoriler tarafından genelleştirilirler .

etimoloji

Analitik geometri formülasyonu daha sonra kategorik ürün kavramına genelleştirilen Kartezyen ürün kavramını ortaya çıkaran Fransız filozof, matematikçi ve bilim adamı René Descartes'ın (1596-1650) adını almıştır .

Tanım

C kategorisi , ancak ve ancak aşağıdaki üç özelliği karşılıyorsa Kartezyen kapalı olarak adlandırılır :

• Bir terminal nesnesi vardır .
• Herhangi iki nesneleri X ve Y, bir C bir olması ürün X-  X -Y olarak C .
• Herhangi iki nesneleri Y ve Z, bir C bir bilgisi üstel Z ^-Y olarak C .

İlk iki koşul , kategorik ürünün doğal birlikteliği nedeniyle ve bir kategorideki boş ürünün son nesne olması nedeniyle, C'nin herhangi bir sonlu (muhtemelen boş) nesne ailesinin C'de bir ürün kabul etmesi şartıyla birleştirilebilir. o kategorinin.

Üçüncü durum bu şartı eşdeğerdir funktor - x -Y (yani gelen funktor C için C harita nesneleri X için X-  X -Y ve morfizimler φ için φ x id _Y ) bir olan doğru eşlenik , genellikle belirtilen - ^Y için tüm nesneler Y bölgesindeki C . İçin lokal olarak küçük kategorilerde , bu varlığı ile ifade edilebilir bir eşleşme arasındaki hom-setleri

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

ki bu doğal hem de X ve Z .

Kartezyen kapalı bir kategorinin sonlu sınırları olması gerekmediğine dikkat edin; sadece sonlu ürünler garanti edilir.

Bir kategori, tüm dilim kategorilerinin Kartezyen kapalı olma özelliğine sahipse, yerel olarak kartezyen kapalı olarak adlandırılır . Eğer Not o C lokal Kartezyen kapalı, aslında Kartezyen kapalı olması gerekmez; bu, yalnızca C'nin bir terminal nesnesine sahip olması durumunda gerçekleşir .

Temel yapılar

Değerlendirme

Her Y nesnesi için üstel ekin sayısı doğal bir dönüşümdür.

${\displaystyle \mathrm {ev} _{Y,Z}:Z^{Y}\times Y\to Z}$

(dahili) değerlendirme haritası olarak adlandırılır. Daha genel olarak, kısmi uygulama haritasını bileşik olarak oluşturabiliriz.

${\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}.}$

Küme kategorisinin özel durumunda , bunlar sıradan işlemlere indirgenir:

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

Kompozisyon

Üstel değeri bir morfizmde bir argümanda değerlendirmek p  : X → Y morfizmleri verir

${\ Displaystyle p^{Z}:X^{Z}\to Y^{Z},}$

${\displaystyle Z^{p}:Z^{Y}\to Z^{X},}$

p ile bileşimin çalışmasına karşılık gelen . p ^Z işlemi için alternatif gösterimler arasında p _* ve p∘- bulunur . Z ^p işlemi için alternatif gösterimler arasında p ^* ve -∘p bulunur .

Değerlendirme haritaları şu şekilde zincirlenebilir:

${\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}$

üstel ekin altındaki ilgili ok

${\displaystyle c_{X,Y,Z}:Z^{Y}\times Y^{X}\to Z^{X}}$

(iç) kompozisyon haritası olarak adlandırılır .

Set kategorisinin özel durumunda , bu sıradan kompozisyon işlemidir:

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

Bölümler

Bir morfizmanın için p : X → Y , aşağıdaki gerileme kare subobject tanımlayan, mevcut varsayalım X ^{, Y} olan kompozit haritalar karşılık gelen p kimliğidir:

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

burada sağ taraftaki oktur s ^{, Y} ve ilgili kimlik alt tekabül ok Y . Daha sonra Γ _Y ( s ) olarak adlandırılır bölümlerin amacı, bir p . Genellikle Γ _Y ( X ) olarak kısaltılır .

Γ Eğer _Y, ( p ) her morfizmanın için var p değer kümesi ile Y , o zaman bir funktor Γ içine monte edilebilir _{, Y}  : C / E → Cı ürün funktor bir varyantına doğru esleniktir dilim kategori:

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

Y ile üstel bölümler cinsinden ifade edilebilir:

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

Örnekler

Kartezyen kapalı kategori örnekleri şunları içerir:

• Kategori Set Herşeyden setleri ile, fonksiyonlar Morfizm olarak, Kartezyen kapalı olduğunu. Ürün X- X -Y Kartezyen ürünü olan , X ve Y ve Z, ^Y, tüm fonksiyonları dizi Y için Z . Adjointness şu gerçeği ile ifade edilmektedir: fonksiyon f  : X, X -Y → Z , doğal olarak özdeşleşen curried fonksiyonu g  : X → Z ^-Y ile tanımlanan g ( x ) ( y ) = f ( x , y için tüm) x içinde X ve Y de Y .
• İşlevleri morfizm olan sonlu kümeler kategorisi de aynı nedenle Kartezyen kapalıdır.
• Eğer G a, grubu , her sonra kategorisi G -Görüntüler Kartezyen kapalıdır. Eğer Y ve Z'nin ikisi G -Görüntüler, o zaman Z, ^Y, tüm fonksiyonları dizi Y için Z ile G (tarafından tanımlanan işlem g . F ) ( y ) = gr . (F ( g ^-1 için .Y)) tüm g olarak g , F : Y → Z ve Y de Y .
• Sonlu G- kümeleri kategorisi de Kartezyen kapalıdır.
• Tüm küçük kategorilerin Cat kategorisi (fonksiyonlar morfizm olarak) Kartezyen kapalıdır; üstel C ^D , morfizmler olarak doğal dönüşümlerle D' den C'ye kadar tüm işlevlerden oluşan işlev kategorisi tarafından verilir .
• Eğer C bir olan küçük kategori ardından funktoru kategorisi Seti ^C tüm kovaryant functors oluşan C Morfizm gibi doğal dönüşümler ile, setleri kategoride, Kartezyen kapalı olduğunu. Eğer F ve G, iki fanktorlar olan C için Set , daha sonra üstel F ^G değeri nesne üzerinde funktor olan X ve C tüm doğal dönüşümler grubu ile verilmektedir ( X x -,)  G için F .
  • Önceki örnekte G -Görüntüler funktor kategorilerinin özel bir durum olarak görülebilir: Her grup tek nesne kategorisi olarak kabul edilebilir G -Görüntüler bu kategoriden başka bir şey funktorlar olan Set
  • Tüm yönlendirilmiş grafların kategorisi Kartezyen kapalıdır; Bu, işlev kategorisi altında açıklandığı gibi bir işlev kategorisidir.
  • Özellikle, basit kümelerin kategorisi (bunlar X  : Δ ^op → Küme fonktörleridir) Kartezyen kapalıdır.
• Daha da genel olarak, her temel topos Kartezyen kapalıdır.
• Gelen cebirsel topoloji , Kartezyen kategoriler ile çalışmak özellikle kolay olur kapattı. Ne sürekli haritalara sahip topolojik uzaylar kategorisi ne de düzgün haritalara sahip düzgün manifoldlar kategorisi Kartezyen kapalı değildir. Bu nedenle ikame kategoriler düşünülmüştür: kompakt olarak oluşturulmuş Hausdorff uzaylarının kategorisi, Frölicher uzaylarının kategorisi gibi Kartezyen kapalıdır .
• İn order theory , komple, kısmi siparişleri ( CPO ler) doğal bir topoloji sahip Scott topolojisi olan sürekli dönüşümler yapmak Kartezyen kapalı kategori oluşturur (olduğundan, nesneler CPOs, ve morfizimler olan, Scott sürekli kartları). Hem körleme hem de uygula , Scott topolojisinde sürekli fonksiyonlardır ve körleme, uygula ile birlikte, eki sağlar.
• Bir Heyting cebri , Kartezyen kapalı (sınırlı) bir kafestir . Önemli bir örnek topolojik uzaylardan kaynaklanmaktadır. Eğer X, bir topolojik alan, daha sonra açık kümeler içinde X bir kategorinin nesneler oluşturmak O ( X ) benzersiz bir morfizmanın var olduğu için U için V ise , U bir alt kümesidir V ve aksi takdirde hiçbir morfizmanın. Bu poşet "ürünü": bir Kartezyen kapalı bir kategoridir U ve V kesişmesi olan U ve V ve üstel U ^V olan iç bölgesinin , U ∪ ( X \ V ) .
• Bir ile bir kategori sıfır nesne Kartezyen kapalıdır ve yalnızca tek bir nesne ve bir kimlik morfizma bir kategori eşdeğer ise ise. Gerçekten de, eğer 0 ilk amacı, 1 nihai amacı, ve sahip sonra, sadece bir eleman olan. ${\görüntüleme stili 0\kong 1}$${\displaystyle \mathrm {Hom} (X,Y)\cong \mathrm {Hom} (1,Y^{X})\cong \mathrm {Hom} (0,Y^{X})\cong 1}$
  • Özellikle, değişmeli kategori gibi sıfır nesneli önemsiz olmayan herhangi bir kategori Kartezyen kapalı değildir. Yani bir halka üzerindeki modüller kategorisi Kartezyen kapalı değildir. Bununla birlikte, sabit bir modüle sahip functor tensör ürününün sağ bir eki vardır . Tensör ürünü kategorik bir ürün değildir, dolayısıyla bu yukarıdaki ile çelişmez. Bunun yerine modül kategorisinin monoidal kapalı olduğunu elde ederiz .${\görüntüleme stili -\otimes M}$

Yerel Kartezyen kapalı kategori örnekleri şunları içerir:

• Her temel topos yerel olarak Kartezyen kapalıdır. Bu örnek, set , FinSet , G, bir grup için -Görüntüler G , hem de set ^C küçük kategoriler için C .
• Nesneleri topolojik uzaylar ve morfizmleri yerel homeomorfizmalar olan LH kategorisi yerel olarak Kartezyen kapalıdır, çünkü LH/X kasnak kategorisine eşdeğerdir . Ancak, LH'nin bir terminal nesnesi yoktur ve dolayısıyla Kartezyen kapalı değildir.${\görüntüleme stili Sh(X)}$
• C'nin geri çekmeleri varsa ve her ok için p  : X → Y , geri çekmeler alınarak verilen p ^*  : C/Y → C/X functor'un bir sağ eki varsa, o zaman C yerel olarak Kartezyen kapalıdır.
• Eğer C lokal olduğu Kartezyen sonra tüm dilim kategorilerinin, kapalı C / X de yerel Kartezyen kapalıdır.

Yerel Kartezyen kapalı kategorilerine örnek olmayanlar şunları içerir:

• Cat yerel olarak Kartezyen kapalı değildir.

Uygulamalar

Kartezyen kapalı kategorilerde, "iki değişkenli bir fonksiyon" (bir morfizm f  : X × Y → Z ) her zaman "tek değişkenli bir fonksiyon" olarak temsil edilebilir (morfizm λ f  : X → Z ^Y ). Gelen bilgisayar bilimi uygulamaları, bu olarak bilinir -işlemden ; basit tip lambda hesabının herhangi bir Kartezyen kapalı kategoride yorumlanabileceğinin anlaşılmasına yol açmıştır.

Curry-Howard-Lambek yazışma Sezgicilik, sade daktilo lambda hesabı ve Kartezyen kategorilerini kapalı arasındaki derin izomorfizm sağlar.

Belirli Kartezyen kapalı kategoriler, topoi , geleneksel küme teorisi yerine matematik için genel bir ayar olarak önerilmiştir .

Ünlü bilgisayar bilimcisi John Backus , geçmişe bakıldığında Kartezyen kapalı kategorilerin iç diline biraz benzerlik gösteren değişkensiz bir gösterimi veya İşlev düzeyinde programlamayı savundu . CAML , Kartezyen kapalı kategoriler üzerinde daha bilinçli bir şekilde modellenmiştir.

Bağımlı toplam ve ürün

Let C yerel Kartezyen kapalı kategori olmak. O zaman C'nin tüm geri çekmeleri vardır, çünkü kod alanı Z olan iki okun geri çekilmesi , ürün tarafından C/Z'de verilir .

Her ok için p  : X → Y , P karşılık gelen C/Y nesnesini göstersin . p boyunca geri çekmeler almak , hem sol hem de sağ bitişik olan bir p ^*  : C/Y → C/X functor verir .

Soldaki birleşik bağımlı toplam olarak adlandırılır ve bileşim tarafından verilir . ${\displaystyle \Sigma _{p}:C/X\to C/Y}$${\displaystyle p\circ (-)}$

Doğru eke bağımlı ürün denir . ${\displaystyle \Pi _{p}:C/X\to C/Y}$

C/Y cinsinden P ile üstel , bağımlı ürün cinsinden formülle ifade edilebilir . ${\ Displaystyle Q^{P}\cong \Pi _{p}(p^{*}(Q))}$

Bu isimlerin nedeni, çünkü yorumlarken P bir şekilde bağımlı tip , functors ve tipi oluşumlara tekabül ve sırasıyla. ${\displaystyle y:Y\vdash P(y):\mathrm {Tür} }$${\görüntüleme stili \Sigma _{p}}$${\displaystyle \Pi _{p}}$${\görüntüleme stili \Sigma _{x:P(y)}}$${\görüntüleme stili \Pi _{x:P(y)}}$

denklem teorisi

(Üstel gösterimi kullanılarak) her Kartezyen kapalı kategoride, ( X, ^Y ) ^Z, ve ( X ^{, Z} ) ^Y vardır izomorfik tüm nesneler için X , Y ve Z . Bunu "denklem" olarak yazıyoruz

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

Tüm Kartezyen kapalı kategorilerde bu tür başka hangi denklemlerin geçerli olduğu sorulabilir. Hepsinin aşağıdaki aksiyomlardan mantıksal olarak çıktıkları ortaya çıktı:

• x ×( y × z ) = ( x × y )× z
• x × y = y × x
• x ×1 = x (burada 1, C'nin uç nesnesini gösterir )
• 1 ^x = 1
• x ¹ = x
• ( x × y ) ^z = x ^z × y ^z
• ( x ^y ) ^z = x ^{( y × z )}

Bikartezyen kapalı kategoriler

Bicartesian kapalı kategoriler ikili Kartezyen kapalı kategorileri uzanan birlikte- ve ilk nesne ürünleri birlikte-üzerinde dağıtılması ile. Denklem teorileri, aşağıdaki aksiyomlarla genişletilir ve Tarski'nin lise aksiyomlarına benzer bir şey verir, ancak toplamalı terslerle:

• 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

Ancak yukarıdaki listenin tam olmadığını unutmayın; serbest BCCC'deki tip izomorfizmi, sonlu olarak aksiyomlaştırılamaz ve karar verilebilirliği hala açık bir problemdir.

Referanslar

• Seely, RAG (1984). "Yerel kartezyen kapalı kategoriler ve tip teorisi". Cambridge Felsefe Topluluğunun Matematiksel Bildirileri . 95 (1): 33–48. doi : 10.1017/S0305004100061284 . ISSN  1469-8064 .

Dış bağlantılar

• Kartezyen kapalı kategori içinde nLab
• CCC'ler ve lambda hesabı arasındaki ilişki üzerine bir blog yazısı : https://golem.ph.utexas.edu/category/2006/08/cartesian_closed_categories_an_1.html