Kategori Teorisi Resimlerle: Mantık (2021)
(abuseofnotation.github.io)- Mantık, doğru kabul edilen atomik önermelerden başlayıp
and,or,impliesgibi işleçlerle daha büyük önermeler kurar; kategori teorisinde olduğu gibi bileşim merkezî önemdedir - Klasik mantık, önermeleri doğru/yanlış Boolean değerleri olarak, mantıksal işleçleri de Boolean fonksiyonları olarak yorumlar; doğruluk tablolarıyla değilleme, mantıksal ve, mantıksal veya, çıkarım ve eşdeğerliği ele alır
- Sezgiselci mantığın BHK yorumu, önermeleri kanıtı olan nesneler olarak görür;
A ∧ Bbir kanıt çifti,A → BiseAkanıtınıBkanıtına dönüştüren bir fonksiyon olarak yorumlanır - Bazı kategorilerde nesneler önermelere, morfizmler kanıtlara karşılık gelir; sıralarda
A ≤ B,A → Banlamına gelen bir preorder veya partial order olarak görünür - Sezgiselci mantık, sıralama kuramında Heyting cebirine, genel kategori teorisinde ise bicartesian closed category'ye karşılık gelir; mantıksal ve, mantıksal veya, doğru, yanlış ve çıkarım sırasıyla meet/join, terminal/initial, exponential object'e karşılık gelir
Önermelerden başlayan mantık
- Mantık, gözlemden bağımsız olarak kendi içinde tutarlı biçimsel kuralları ele alır; bir şeyi bildiğimizde başka bir şeyin doğru olduğu sonucuna varma ya da bunu kanıtlama sistemidir
- Matematiksel teoriler, mantığa ek tanımların eklendiği yapılar olarak görülebilir
- Küme teorisi, standart mantık aksiyomlarına küme üyelik ilişkisi adlı ilkel kavram eklenerek tanımlanabilir
- Mantığa başlamak için doğru veya yanlış olarak kabul edilen bir başlangıç önerme kümesi gerekir
- Bunlara öncül, atomik önerme veya primary proposition denir
- İki veya daha fazla önerme,
and,or,implies/entailsgibi mantıksal işleçler ile tek bir bileşik önerme hâline gelir∧,andanlamına gelir∨,oranlamına gelir→,followsya da çıkarımı ifade eder
- Bileşik önermeler de atomik önermeler gibi yeniden başka önermelerle birleştirilebilir
Modus ponens ve tautolojiler
- Modus ponens,
Adoğruysa veA → BdoğruysaB'nin de doğru olduğunu söyleyen eski bir mantık kalıbıdır- Biçimi
(A ∧ (A ⇒ B)) → Bşeklindedir - “Sokrates insandır ve insan olan ölümlüyse, Sokrates ölümlüdür” gibi bir örnekle ifade edilir
- Biçimi
- Mantık yalnızca tek tek işleçlerle değil, birden çok mantıksal işlecin birleşimleri ve ilişkileriyle ilgilenir
andileimpliesarasındaki ilişki modus ponens'te görünürandileorarasındaki dağılım yasası da temel ilgi alanlarından biridir
- Tautoloji, bileşen önermelerin doğru/yanlış değerlerinden bağımsız olarak her zaman doğru olan önermedir
- Modus ponens'te
AveBdoğru da olsa yanlış da olsa tüm formül her zaman doğrudur - Her zaman yanlış olan önermeye çelişki denir
- Bir tautolojiye
noteklerseniz çelişki olur; bir çelişkiyenoteklerseniz tautoloji olur
- Modus ponens'te
- Değere göre doğru ya da yanlış olması değişen önermelere contingent statement denir; bunlar mantığın ana ilgi alanının dışındadır
- En basit tautoloji, her önermenin kendisini ima ettiğini söyleyen özdeşlik ilkesidir
Aksiyom şemaları ve mantık sistemleri
- Tautolojiler, aksiyom şemalarının ve çıkarım kurallarının temelini oluşturur
- Aksiyom şeması, yer tutucular içeren bir formüldür; bu yer tutucular önermelerle değiştirilerek somut önermeler elde edilebilir
- Modus ponens'te renkler ya da somut önermeler çıkarıldığında geriye genel yapı kalır
- Bu yapıya atomik ya da bileşik önermeler yerleştirilerek belirli bir modus ponens önermesi kurulabilir
- Çıkarım kuralları neredeyse aksiyom şemalarıyla aynı biçimde yazılabilir; aksiyom şemaları da çıkarım kuralları gibi uygulanabilir
- Her tautoloji bir aksiyom şeması olarak kullanılabilir
- Mantık sistemi ya da biçimsel sistem, aksiyom şemaları ile çıkarım kurallarının bir koleksiyonudur ve bunların uygulanmasıyla mümkün olan tüm önermeleri üretir
- Örnek olarak, beş aksiyom şeması ve modus ponens çıkarım kuralından oluşan bir sistem sunulur
- Böyle bir mantık sisteminin tam olması, Gödel'in tamlık teoremi ile ilişkilidir
Klasik mantığın doğruluk-fonksiyonu yorumu
- Klasik mantık, her önermenin ya doğru ya da yanlış olduğu ikiliğe dayanır
- Klasik yorumda önermeler ve işleçler şöyle tanımlanır
- Önermeler, doğru veya yanlış olan Boolean değerleri gibidir
- Mantıksal işleçler, bir veya daha fazla Boolean değeri alıp Boolean değeri döndüren fonksiyonlardır
- Değilleme
¬p, tekli bir işlemdir; doğruyu yanlışa, yanlışı doğruya çevirir- Aynı şey doğruluk tablosu ile de gösterilebilir
- Çifte değillemenin kaldırılması, değilleme iki kez uygulandığında başlangıçtaki değere dönüldüğü gösterilerek kanıtlanır
and, iki Boolean değeri alır ve yalnızca ikisi de doğruysa doğru döndürürp ∧ q → pp ∧ q → q
or, iki Boolean değerden en az biri doğruysa doğru döndürürp → p ∨ qq → p ∨ q
impliesya da material condition,p → qşeklinde yazılır ve yalnızcapdoğruykenqyanlışsa yanlıştır- Klasik mantıkta
p → q,¬p ∨ qdoğru olduğunda aynı şeydir
- Klasik mantıkta
if and only ifya daiff, iki önerme aynı değeri taşıdığında doğrudurP ↔ Q,P → Q ∧ Q → Pile eşdeğerdir
- Doğruluk tablolarının yanı sıra aksiyomlar ve çıkarım kurallarıyla da
p → qile¬p ∨ qeşdeğerliği kanıtlanabilir- Tam bir eşdeğerlik kanıtı için iki yönlü ispat gerekir
Sezgiselci mantık ve BHK yorumu
- Sezgiselci mantık, kanıtı evrensel bir gerçeğin keşfi değil, bir inşa olarak görür
- Bu bakışta her önermenin zorunlu olarak doğru ya da yanlış olduğu ikiliği kullanılamaz
- Bazı önermeler, yanlış oldukları için değil, verilen mantık sisteminin kapsamı dışında kaldıkları için kanıtlanamayabilir
- İkiz asallar varsayımı buna sık verilen bir örnektir
- Brouwer–Heyting–Kolmogorov (BHK) yorumunda odak önermelerden çok kanıtlardadır
- Önerme, kanıtı bulunan şeydir
- Mantıksal işleçler, başka kanıtlardan kanıt üreten inşalardır
A ∧ B'nin kanıtı,A'nın kanıtı ileB'nin kanıtından oluşan bir çift, yani product'tırA → B,AkanıtınıBkanıtına dönüştüren bir fonksiyonun var olduğu anlamına gelirA → Biçin kanıt kümesi,A'danB'ye giden fonksiyonlar kümesi, yani hom-set olarak ifade edilir- Bu küme boşsa,
AkanıtınıBkanıtına dönüştürmenin bir yolu yoktur
- BHK yorumunda ayrı bir iff işleci yoktur ama ok vardır
A'danB'ye veB'denA'ya fonksiyonlar varsa iki önerme eşdeğer gibi ele alınır- Küme bakış açısından bu, iki önermenin kanıt kümelerinin izomorf olmasıdır
- Değilleme, yalnızca kanıt olmaması anlamına gelmez;
A'nın doğru olduğunu varsaydığınızda çelişkiye ulaştığınızı göstermeniz gerekir⊥, kanıtı olmayan bir formülün kanıtı, yani False veya bottom value rolünü oynar- BHK'de
¬A,A → ⊥diye okunur - Küme teorisinde
⊥, boş küme ile gösterilir
Mantığı bir kategori olarak görmek
- BHK yorumu, mantığı kategori teorisiyle yorumlamak için yüksek seviyeli bir bakış sunar
- Bazı kategoriler bir mantık sistemi gibi görülebilir
- Nesneler önermelerdir
- Morfizmler kanıtlardır
- Her kategori mantık sistemi olmaz; geçerli mantıksal önermelere karşılık gelen nesnelerin bulunması ve geçersiz önermelere karşılık gelen nesnelerin bulunmaması için belirli koşullar gerekir
- Bu koşulları sağlayan kategorilere bicartesian closed category denir
- Basit bir durum olarak önce sıralara bakılırsa, mantık sistemi ile atomik önerme kümesi bir kategori oluşturur
A'danB'ye gitmenin tek bir yolu varsa ya da farkları göz ardı ediliyorsa preorder elde edilir- Birbirini gerektiren önermeler eşdeğer sayılırsa partial order elde edilir
A ≤ B,A → Banlamına gelir
- Hasse diyagramında
A,B'nin altındaysaA → Bgeçerlidir
Mantıksal işleçlerin sıralama kuramındaki karşılıkları
- Mantıktaki
andveor, BHK yorumunda product ve sum olarak görünür; sıralama kuramında ise meet ve join'e karşılık gelir - Bir mantık sistemi olabilmesi için herhangi iki önerme
andya daorile birleştirilebilmelidir; dolayısıyla sıra her eleman çifti için meet ve join içermelidir- Böyle sıralara lattice denir
andileorarasındaki önemli yasalardan biri dağılırlıktır- Tüm
A,B,CiçinA ∧ (B ∨ C) ≅ (A ∧ B) ∨ (A ∧ C)geçerliyse buna distributive lattice denir
- Tüm
- Sezgiselci mantığı ifade etmek için lattice'te
TrueveFalse'a karşılık gelen elemanların da bulunması gerekirFalse,⊥ile yazılır ve False için bir kanıt varsa her önermenin kanıtlanabileceğini söyleyen patlama ilkesi ile ilişkilidirTrue,⊤ile yazılır; her önermeden çıkar ama kendi başına anlamlı bir içerik üretmez
- Sıralarda
TrueveFalsesırasıyla en büyük nesne ve en küçük nesnedir- Kategori teorisi terminolojisinde bunlar terminal object ve initial object'e karşılık gelir
- En küçük ve en büyük elemanları olan lattice'lere bounded lattice denir
Çıkarım nesnesi ve üstel nesne
- Bir mantık sistemini ifade eden lattice'te, her
A,Bçifti içinA'nınB'yi ima ettiğini gösteren bir çıkarım nesnesi bulunmalıdır - Bu nesne, modus ponens yapısıyla tanımlanır
A ∧ (A ⇒ B) → Bgeçerli olmalıdır
- Yalnızca bu koşul yeterli değildir
A ⇒ B ∧ Cya daA ⇒ B ∧ C ∧ Dgibi başka nesneler de aynı yere oturabilir- Gerçek
A ⇒ B,A ∧ X → Bkoşulunu sağlayan tümX'ler içindeki en büyük nesnedir
- Sıralama kuramında
A ⇒ B, exponential element veya relative pseudo-complement olarak adlandırılırA ∧ X ≤ Bkoşulunu sağlayan en büyükXbudur
- Mantıksal olarak
A ∧ X → Bkoşulunu sağlayan en az içerikli önermeX, çıkarım önermesiA ⇒ B'dir - Kategori teorisinde bu, exponential object ya da internal homomorphism object olarak tanımlanır
A × X → Bbiçiminde bir morfizm bulunmalıdır- Aynı özelliğe sahip başka her aday nesneden gerçek üstel nesneye giden benzersiz bir morfizm olmalıdır
- Bu çıkarım nesnesi tanımı sezgiselci mantığa uyar
- Klasik mantıkta üçüncü hâlin imkânsızlığı nedeniyle
A ⇒ B,¬A ∨ B'ye indirgenir
- Klasik mantıkta üçüncü hâlin imkânsızlığı nedeniyle
- Meet, join ve çıkarım nesnesi gibi
A ⇒ Bde yalnızca benzersiz bir izomorfizme kadar tanımlıdır
Heyting cebiri ve bicartesian closed category
- Sezgiselci mantık,
True,False,and,or,impliesile kurulur - Bu yapı sıra olarak ifade edildiğinde Heyting cebiri elde edilir
- Join ve meet içerir
- En büyük ve en küçük nesneyi içerir
- Çıkarım nesnesi içerir
- Sezgiselci mantık sistemi bir Heyting cebiri olarak görülebilir
andveor, meet ve join'dirTrueveFalse, en büyük ve en küçük nesnelerdirimplies, exponential object'tir
- Aynı tanım genel kategorilere uyarlanırsa bicartesian closed category elde edilir
- Product ve coproduct içerir
- Initial ve terminal object içerir
- Exponential object içerir
- Sezgiselci mantık sistemi bicartesian closed category olarak da görülebilir
andveor, product ve coproduct'turTrueveFalse, terminal ve initial object'tirimplies, exponential object'tir
- Klasik mantığa uyan bir lattice, bounded ve distributive olmasının yanı sıra complemented da olmalıdır
- Her önerme
Aiçin,A ∨ ¬A = 1veA ∧ ¬A = 0koşullarını sağlayan özgün bir¬Avardır - Böyle lattice'lere Boolean cebiri denir
- Her önerme
Kategorik mantıkla basit ispatlar
A ∨ ⊤ ≅ ⊤, join tanımından doğrudan çıkar- Join, iki nesneden büyük ya da onlara eşit olan en küçük üst sınırdır
⊤'dan büyük ya da ona eşit tek nesne⊤'nin kendisi olduğundan, herhangi birAile⊤'nin join'i⊤olur- Mantıksal olarak bu, “herhangi bir
Aveya True, True'dur” tautolojisidir
A → BvarsaA ∨ B = Bolur- İki nesneden biri diğerinin üzerindeyse join, yukarıda olan nesnedir
- Bu,
A ∨ ⊤ = ⊤'nin genellemesi olarak görülebilir - Çünkü her nesne
Aiçin her zamanA → ⊤geçerlidir
- Özdeşlik ilkesi, çıkarım nesnesiyle de kanıtlanır
A ⇒ A,A ∧ X → Akoşulunu sağlayan en büyükX'tir- Bu koşul her
Xiçin geçerli olduğundan sonuç en büyük nesne⊤olur - Dolayısıyla
A → Aher zaman doğrudur
- Eğer
A, tüm modellerdeB'yi ima eden bir semantic consequence ise, yaniA ⊨ B, o zamanA ⇒ Bde⊤'ye karşılık gelirAzatenB'yi ima ettiğindenA ∧ X → BherXiçin geçerlidir- Buna deduction theorem de denir
Free Heyting cebiri ile mantık kurmak
- Mantık yapmak için önce problem alanına göre kullanılacak atomik önermeler seçilir
- Seçilen mantık türü sezgiselci mantıksa, tüm
A,BiçinA ∧ B,A ∨ Bgibi bileşik önermelerin grafiği çizilmelidir - Bileşik önermelerin bileşimleri de yeniden dahil edilmesi gerektiğinden tam liste sonsuz olur
- Bir önermenin başka bir önermeyi ima edip etmediği, başlangıç önermesinden çıkan okların yolları izlenerek kontrol edilir
- Mantık yürütmek, eldeki bilgilerden kanıtlanmak istenen sonuca giden bir yol bulma ya da mevcut kanıtları işleyerek yeni bir kanıt kurma sürecidir
- Sezgiselci mantıkta genel olarak bir ifadenin aksiyomlardan ulaşılamaz olduğunu, yani kanıtlanamayacağını kanıtlamak zordur
1 yorum
Hacker News yorumları
Bu sayfa gerçekten harika; ilgili konuları çalışırken birçok kez karşıma çıktı
Yine de öğrenmek için oyumu Milewski'den yana kullanırım. Bunu öğrenmek bir yolculuk ve ct-illustrated'ın yazarı hâlâ o yolculuğun ortasında gibi görünüyor
Milewski ise bu yolu birçok kez gidip gelmiş biri; bu yüzden kitabı ve blogu iyi bir başlangıç noktası
https://github.com/hmemcpy/milewski-ctfp-pdf Kitap
https://bartoszmilewski.com/2014/10/28/category-theory-for-p... Blog
Hafif ve kesin olmayan düzyazıyla yazılınca her şeyin daha anlaşılır olduğunu düşünüyor gibi; bu da onu başvuru kaynağı olarak neredeyse işe yaramaz kılıyor
Hiç de öyle değil¹
¹) https://news.ycombinator.com/item?id=41756286
Ama iş yerinde tüm domain modelim için kategori teorisi kullanıyorum
Daha önce başka URL'lerde zaten tartışılmıştı
https://news.ycombinator.com/item?id=28660131 (2 yorum)
https://news.ycombinator.com/item?id=28660157 (112 yorum)
Kitabın başlarında matematiği bilim veya mühendislikle karşılaştırırken şu güzel cümleye rastladım
“Bu yüzden matematikçiler, yaptıkları işi başka disiplinler için taşıdığı değer açısından sürekli savunmak zorunda kaldıkları tuhaf, hatta benzersiz denebilecek bir konumda bulunurlar. Yeniden vurgulamak gerekirse, başka herhangi bir disiplin için böyle bir şey saçma sayılırdı.”
Doğrudan para kazandıran sonuçlara dönüşmeyen bir alan okumuş herkesin özdeşleşebileceği bir fikir; sayı tarafında yeteneği olanların da Milton Friedman'ın usturası ile mücadele etmek zorunda kaldığını duymak güzel
Bugün “postkolonyalizm” araştırmalarının tamamı Amerikan yumuşak gücünün backend'inden başka bir şey değil; savaş çıktığında muhtemelen sert gücün backend'i de olacak
İçteki daireler her zaman dikey olarak ortalanıyorsa daire içinde daire diyagramları ölçek büyüdüğünde pek dayanıklı kalmıyor
Kategori teorisini kullanarak, kategori teorisi olmadan çözülemeyecek bir CS/SWE problemini faydalı biçimde çözmüş bir başarı hikâyesi var mı? Monad sayılmaz; çünkü durum gerektirirse doğal olarak icat edilecek bir şeydir
Lisansüstünde bir yıl çalıştım ama sonunda bıraktım
Kategori teorisinin en temel teoremlerinden biri olan Yoneda leması, kategori diliyle ifade edilen her problemin doğrudan kümeler ve fonksiyonlar diline çevrilebileceğini söyler. Kümelerle tanımlanan tüm matematiksel nesneler için de aynısı geçerli; yani bir adı her zaman tanımıyla değiştirebilirsiniz
Kategorik dilin bir teorinin örtük çerçevesine katkısı, “kategori” tanımından daha büyük olamaz; o tanım da çok küçüktür. Bu biraz, “bir küme üzerinde birleşme yasası, kapalılık, birim eleman ve ters eleman içeren işlem” daha erişilebilirken neden grup kullanalım diye sormaya benzer
Soyut cebir, yeterince yaygın olacak kadar basit olan küme üzerindeki işlem türlerini adlandıran bir tanımlar kütüphanesine dayanır. Araçlar veya teknikler, tanımın içinde bulabileceğiniz türden şeyler değildir
Halkalar, vektör uzayları ve modüller kendi başlarına hemen kabul görürken kategoriler inananlar ve inanmayanlar diye ayrılıyor. Bunun neden olduğunu merak ediyorum
Leland McInnes ile röportaj yaptığımda, nihai sonucun gerçek kodunda şart olmasa bile kategori teorisinin çeşitli noktaları birleştirmede büyük rol oynadığını ayrıntılı biçimde açıklamıştı
Önceki son teknoloji yöntem olan t-SNE'ye göre göreli iyileşmeye bakınca, yazılımda kategori teorisini konuşma biçimimize dair eleştirimi yeniden düşünmeme neden olan tek örnek bu
https://arxiv.org/abs/1802.03426
Kategori teorisi bir dil ve araçtır; bu yüzden kategori teorisinin diliyle söylenebilen şeyler başka dillerle de söylenebilir
Araba gibi, kullanmayı öğrenirseniz —ki öğrenme eğrisi çok diktir— daha hızlı gidebilirsiniz. İlke olarak, kategori teorisi kavramlarını açıkça anmadan yürüyerek de ulaşılamayacak bir şey yoktur
Benim çok sınırlı anlayışıma göre, nesneleri evrensel özelliklerle karakterize etmek kategori teorisinin önemli bir parçası
Kategori teorisinin bir başka pratik yararı da bilgisayar bilimcilerin, matematikçilerin ve fizikçilerin birlikte konuşabileceği ortak bir dil sağlamasıdır. Herkes aynı örüntüleri farklı adlarla ve biraz uyumsuz tanımlarla anıyorsa iş birliği kolay olmuyor
Şu anki pre-alpha esas olarak sistem dinamiği modellemesi için, ama hedeflenen çalışma kapsamı için kategorik temelin zorunlu olduğunu düşünüyorum. Herkesin görüşünü memnuniyetle duymak isterim
https://topos.site/blog/2024-10-02-introducing-catcolab/
Kategori teorisinin faydalı olduğunu düşünüyorum ama henüz bilişim için değil gibi
Gerçekten ihtiyaç duyduğunuz bir şey yoksa kaçınılmaz olarak zor gelir. Evrensel özellikleri, adjoint functor'ları, Yoneda lemasını gerçekten anlamaya ihtiyaç var mı? Yoksa bunların ne olduğunu öğrenmekte zorlanırsınız
İlginç biçimde fonksiyonel programlama deneyimi kategori teorisini anlamaya yardımcı oluyor, ama tersi pek geçerli değil. Örneğin parametrik polimorfizm doğal dönüşümlere dair sezgi verir; doğal dönüşümler de kategori teorisinin tüm uygulamalarında merkezîdir
Kategori teorisinin ikna edici uygulamaları oldukça matematikseldir. Cebirsel topolojide, temsil teorisinde, cebirsel geometride ve klasik olmayan mantıkta bulunabilir
https://en.m.wikipedia.org/wiki/ZX-calculus
https://zxcalculus.com/
https://www.reddit.com/r/quantum/s/2NzsJaDYwm
Bir hata var
“Modus ponens, burada A ve B ile gösterilen diğer iki önermeden oluşan bir önermedir; A önermesi doğruysa ve A --> B de doğruysa, yani A, B'yi gerektiriyorsa, B'nin de doğru olduğunu söyler. Örneğin ‘Sokrates insandır’ ve ‘İnsanlar ölür’ü biliyorsak, ‘Sokrates ölür’ü de biliriz.”
Bu örnek önerme mantığının bir kuralı olan modus ponens'e örnek değil; yüklem mantığı gerektiren kategorik kıyastır
Burada “mantık mümkün olanın bilimidir” deniyor; mantık kesin olanın bilimi olmalı değil mi?
Bence asıl mesele, neyin geçerli olup olmadığını kesin biçimde söyleyebilmeyi sağlamasında
Diyagram notasyonu ilginç
Yazar diyagramların doğruluk koruyan dönüşümleri için çıkarım kuralları da veriyor mu?