Kategori teorisini görsellerle anlamak: sıra

• Bir öğe kümesi üzerindeki ikili ilişki, yansıma, geçişlilik ve antisimetriklik gibi yasaları sağladığında bir sıra yapısı oluşur
• Doğrusal sıra, her iki öğenin karşılaştırılabildiği bir yapıdır; tamlık kaldırıldığında kısmi sıra elde edilir
• Kısmi sıralarda yapı, zincir, en büyük öğe / en küçük öğe, join / meet ve Hasse diyagramı ile anlaşılabilir
• Renk karışımı, bölünebilirlik ve kümelerin içerme ilişkisi kısmi sıraya örnektir; hem join hem meet varsa lattice oluşur
• Preorder, yalnızca yansıma ve geçişlilik içeren yapıdır; her preorder, iki nesne arasında en fazla bir morfizma bulunan bir kategori olarak yorumlanabilir

---

Sıra

• Sıra, bir öğe kümesi ile onun üzerindeki bir ikili ilişkiden oluşur; belirli yasaları sağladığında matematiksel bir yapı ortaya çıkar
  • Esas nokta, sıralama ölçütünün kendisinden çok öğeler arasındaki ilişkinin hangi özelliklere sahip olduğudur
  • İkili ilişki, kümenin iki öğesi arasındaki ilişkidir ve oklarla da gösterilebilir
• Sıra, küme kuramında bir kümenin kendisiyle Kartezyen çarpımının bir altkümesi olarak, programlamada ise iki nesneyi karşılaştıran bir fonksiyon olarak ifade edilebilir
  • Ancak her karşılaştırma fonksiyonu ya da her öğe çifti kümesi bir sıra tanımlamaz; başlangıç yerleşiminden bağımsız tutarlı sonuçlar için belirli kurallar gerekir

Doğrusal sıra

• Doğrusal sıra**, her öğenin diğerlerine göre bir konuma sahip olduğu ve bir öğenin diğerinden önce gelip gelmediğinin** belirsiz olmadığı yapıdır

  • Örnek olarak ışığın dalga boyu ya da gökkuşağındaki dizilişe göre renk sırası verilir
  • Doğrusal sıra, yansıma, geçişlilik, antisimetriklik ve tamlık sağlayan bir ikili ilişki olarak tanımlanır
  • Bu dört yasa, sıra ilişkisini oluşturan koşullardır

• Yansıma

  • Her öğe kendisinden büyük ya da kendisine eşit olmalıdır; yani her $a$ için $a \le a$ geçerlidir
  • Bu, taban durumu ele alan kuraldır; tersine, bir öğenin kendisiyle ilişki kurmadığı tanım yapılırsa strict order benzeri başka bir tür elde edilir

• Geçişlilik

  • $a \le b$ ve $b \le c$ ise $a \le c$ olması gereken kuraldır
  • Sıranın özünü büyük ölçüde belirleyen yasadır

• Antisimetriklik

  • Çelişkili karşılaştırma sonuçlarını yasaklayan kuraldır; $x \le y$ ve $y \le x$ durumu yalnızca $x = y$ olduğunda kabul edilir
  • Beraberliğe izin verilmediği biçiminde de özetlenir

• Tamlık

  • Her iki öğe mutlaka karşılaştırılabilir olmalıdır; yani herhangi iki öğe için $a \le b \lor b \le a$ geçerlidir
  • Herhangi iki öğeden biri diğerinden büyük ya da ona eşit olmalıdır
  • Tamlık, $a$ ile $b$'nin aynı olduğu durumu da içerdiği için yansımayı özel bir durum olarak kapsar
  • Tamlık kaldırıldığında kısmi sıra elde edilir ve doğrusal sıra bazen total order olarak da yazılır

• Doğal sayıların sırası

  • Doğal sayılar, büyük ya da eşit olma ilişkisi altında doğrusal bir sıra oluşturur
  • Her sonlu doğrusal sıra, birinci öğeyi 1'e, ikinci öğeyi 2'ye eşleyen biçimde doğal sayıların bir altkümesiyle izomorfiktir
  • Bu nedenle aynı büyüklükteki tüm sonlu doğrusal sıralar birbirleriyle izomorfiktir
  • Kategori teorisi açısından bakıldığında, tüm sonlu doğrusal sıraların ve çoğu sonsuz doğrusal sıranın diyagramları da aynı görünür

Kısmi sıra

• Kısmi sıra, doğrusal sıradan tamlığın çıkarıldığı yapıdır; yalnızca yansıma, geçişlilik ve antisimetriklik kalır
  • partially-ordered set, yani poset adı da kullanılır
• Her doğrusal sıra bir kısmi sıradır, ancak her kısmi sıra doğrusal sıra değildir
• Kısmi sıra, eşdeğerlik ilişkisiyle de bağlantılıdır; eşdeğerlik ilişkisindeki simetrikliğin yerini burada antisimetriklik alır
• Futbol becerisi karşılaştırması örneğinde, yalnızca doğrudan ya da dolaylı biçimde karşılaştırılabilen bazı kişiler varsa doğrusal sıra mümkün olabilir; ancak hiç maç yapmamış kişiler de varsa yapı doğrusal olmayan hale gelir ve kısmi sıra oluşur
  • Kısmi sıra, kimin daha iyi olduğu sorusuna her zaman kesin cevap vermeyebilir

• Zincir

  • Kısmi sıra, birden fazla doğrusal altkümeden oluşabilir; bu tür doğrusal altkümelere chain denir
  • Örnek olarak $m \to g \to f$ ve $d \to o$ olmak üzere iki zincir verilir
  • Zincirlerin tamamen ayrık olması gerekmez; tüm bağlantılar bire bir birbirine eklenip tek bir zincire dönüşmediği sürece kısmi sıra korunur
  • Örnekte $d \le g$ ve $f \le g$ bilinebilir, ancak $d$ ile $f$ arasındaki ilişki belirsizdir

• En büyük ve en küçük öğe

  • Bir $a$ öğesi, diğer tüm $x$ öğeleri için $x \le a$ koşulunu sağlıyorsa bu öğe greatest element olur
  • Bazı kısmi sıralarda böyle bir öğe vardır; örnek diyagramda $m$ greatest element'tir
  • Birden fazla öğe diğerlerinin hepsinden büyük olsa bile bunlar birbirine eşit değilse greatest element yoktur
  • Aynı şekilde least element de tanımlanır

• Join

  • Bağlantılı iki öğenin least upper bound'una join denir
  • Tanımın iki koşulu vardır
    • $A \le G$ ve $B \le G$ olmalıdır
    • $A$ ve $B$'den büyük olan başka herhangi bir $P$ öğesi için $G \le P$ olmalıdır
  • Bir öğe diğerinden büyükse join, doğrudan daha büyük olan öğenin kendisidir
  • Doğrusal sırada herhangi iki öğenin join'i zaten daha büyük olan öğedir
  • Aynı büyüklükte birden fazla üst sınır varsa join yoktur; join tekil olmalıdır

• Meet

  • Her ikisinden de küçük ya da eşit olan öğeler arasındaki en büyük öğeye meet denir
  • Join ile aynı kurallar ters yönde uygulanır

• Hasse diyagramı

  • Bu bölümde kullanılan çizimler Hasse diagrams'dır
  • Daha büyük öğenin daima daha yukarı yerleştirilmesi gibi ek bir kural vardır
  • Ok varsa, okun yöneldiği nokta daima daha yukarıdadır
  • Bu yerleşim sayesinde yalnızca iki noktanın yukarı-aşağı ilişkisine bakarak karşılaştırma yapılabilir; join de ortak bağlanan öğeler arasındaki en alttakini bulma yoluyla saptanabilir

• Renk karışımı için kısmi sıra

  • Her rengin kendisini içeren renge yöneldiği bir color-mixing partial order verilir
  • Herhangi iki rengin join'i, bu iki renk karıştırıldığında ortaya çıkan renktir

• Bölünebilirliğe göre sayıların kısmi sırası

  • Sayılar büyüklüğe göre değil, bölünebilirlik bakımından sıralanırsa bir kısmi sıra oluşur
  • $a$, $b$'yi bölüyorsa $a$'nın $b$'den önce geldiği kabul edilir
  • Örneğin $2 \times 5 = 10$ olduğundan 2 ve 5, 10'dan önce gelir; ama 3, 10'dan önce gelmez
  • Bu sırada join en küçük ortak kat, meet ise en büyük ortak bölen olur

• İçerme kısmi sırası

  • Ortak bazı öğeler içeren çeşitli kümeler varsa inclusion order tanımlanabilir
  • Bir $a$ kümesi $b$'yi içeriyorsa, başka bir deyişle $b$, $a$'nın altkümesiyse, $a$'nın $b$'den önce geldiği söylenir
  • Bu durumda join birleşim kümesi, meet ise kesişim kümesi olur
  • Her kümede bulunan renkler karıştırıldığında, daha önce görülen renk karışımı kısmi sırasıyla aynı yapı elde edilir
  • Sayıların bölünebilirlik sırası, tekrarın izinli olduğu bir asal kümesi ya da prime powers için içerme sırasıyla izomorfiktir
  • Bu, her sayının asal çarpanların çarpımı olarak tam bir tek biçimde yazılabildiğini söyleyen aritmetiğin temel teoremiyle doğrulanır

Birkhoff'un gösterim teoremi

• Hem renk karışımı hem de sayıların bölünebilirlik kısmi sırası, bazı temel öğelerin olası küme birleşimlerine ait içerme sırası olarak gösterilebilir
  • İlkinde temel öğeler ana renklerdir, ikincisinde ise asallar ya da asal kuvvetleri
• Sonlu bir kısmi sıranın bu şekilde gösterilip gösterilemeyeceğini Birkhoff’s representation theorem belirler
  • İki koşul vardır
    • Her öğe çifti için join ve meet bulunmalıdır
    • Join ile meet birbirine göre dağılmalıdır. $∨$ ve $∧$ gösterimiyle: $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
• Her öğesinin join ve meet'i olan kısmi sıraya lattice denir
• Bu işlemler birbirine göre dağılabiliyorsa yapı distributive lattice olur
• İçerme sırasını kuran “asal benzeri” öğeler, başka öğelerin join'i olarak ifade edilemeyen öğelerdir; bunlara join-irreducible elements denir
• Teorem, her distributive lattice'in kendi join-irreducible elements'lerinin inclusion order'ı ile izomorfik olduğu biçiminde de ifade edilir
• Distributive lattice olmayan kısmi sıralar da inclusion order ile izomorfik olabilir; ancak bu durumda, mümkün olan tüm birleşimleri içermeyen bir inclusion order ile eşleşirler

Kafes

• lattice, her iki öğe için de join ve meet bulunan bir kısmi sıradır
  • Her lattice bir kısmi sıradır, fakat her kısmi sıra lattice değildir
• Belirli kurallarla üretilen birçok kısmi sıra distributive lattice'tir; önceki bölümdeki örnekler de eksiksiz çizildiğinde distributive lattice olur
• Renk karışımı örneğinde yukarıya siyah top, aşağıya beyaz top eklenir
  • Aksi halde üstteki üç öğenin join'i olmaz, alttaki üç öğenin de meet'i olmaz

• Sınırlı kafes

  • Hem greatest element hem de least element içeren lattice'e bounded lattice denir
  • Renk karışımı lattice'inde siyah top greatest element, beyaz top ise least element'tir
  • Tüm sonlu lattice'lerin bounded olduğu da ayrıca belirtilir

Sıra izomorfizmi

• Sıra izomorfizmi, iki sıranın taban kümeleri arasında tersinir bir fonksiyon olup sıra oklarını koruyan fonksiyondur
• Sayıların bölünebilirlik sırası ile asal içerme sırası örneğinde bu, iki fonksiyondan oluşur
  • Asal içerme sırasından sayıların sırasına giden fonksiyon, küme öğelerinin çarpımıdır
  • Sayıların sırasından asal içerme sırasına giden fonksiyon ise sayıyı çarpanlarına ayıran prime factorization'dır
• Sıra izomorfizminin temel koşulu, iki öğe $a$, $b$ için $a \le b$ ise ve ancak o zaman $F(a) \le F(b)$ olmasıdır
• Böyle fonksiyonlara order-preserving fonksiyon denir

Ön sıra

• preorder, doğrusal sıradan antisimetrikliğin çıkarıldığı yapıdır; yalnızca yansıma ve geçişlilik kalır
• Karşılaştırılabilirlik ölçütüne göre
  • Doğrusal sırada $a \le b$ veya $b \le a$
  • Kısmi sırada bunlardan biri geçerli olabilir ya da ikisi de olmayabilir
  • Ön sırada bunlardan biri, hiçbiri ya da ikisinin de doğru olması mümkündür
• Ön sıra, gündelik anlamdaki sıradan farklıdır; herhangi bir noktadan başka bir noktaya ok gidebilir
  • Futbolda “kimin kimi yendiği”nin, doğrudan ya da dolaylı galibiyetler de dahil edilerek modellenmesi örnek verilir
• Geçişlilik nedeniyle dolaylı galibiyetler de doğrudan ilişki gibi eklenir; bunun sonucunda döngüsel bir ilişki varsa birkaç nesnenin birbirine tamamen bağlı olduğu bir yapı oluşur

• Ön sıra ve eşdeğerlik ilişkisi

  • Ön sıra, kısmi sıra ile eşdeğerlik ilişkisi arasında duran bir yapıdır
  • Çünkü bu ikisini ayıran tek nokta olan (anti)simetriklik burada eksiktir
  • Ön sırada birbirine çift yönlü bağlı olan öğeler simetriklik sağladığından bir eşdeğerlik ilişkisi oluşturur
  • Bu öğeler gruplanınca ön sıranın equivalence classes'ı oluşur
  • Ardından yalnızca bu eşdeğerlik sınıfları arasındaki bağlantılar ele alınırsa, bu bağlantılar antisimetriklik sağlayan bir kısmi sıra oluşturur
  • Dolayısıyla her ön sıra için onun eşdeğerlik sınıfları üzerindeki bir kısmi sıra tanımlanabilir

Ön sıra ve kategori

• Ön sıradaki geçişlilik, $a \le b$ ve $b \le c$ varsa $a \le c$ elde edilmesi kuralıdır; bu, ilişkinin bileşimi olarak yorumlanabilir
• Bir kategorinin tanımı şu iki koşulu içerir
  • Her nesne için bir özdeşlik morfizması vardır
  • Uygun iki morfizma bileştirilebilir ve bu bileşim birleşmelidir
• Ön sırada geçişlilik bileşimi üstlenir, yansıma ise özdeşlik morfizmasının rolünü oynar
• Bu yüzden her preorder bir kategoridir
• Genel kategorilerde iki nesne arasında birden çok morfizma olabilir; ama ön sırada herhangi iki nesne arasında en fazla bir morfizma bulunur
  • Ya $a \le b$ vardır ya da yoktur
• Nasıl monoid tek nesneli bir kategori ise, sıralar da iki nesne arasında en fazla bir morfizma bulunan kategoriler olarak özetlenebilir
• Bu özellik nedeniyle ön sıralarda tüm diyagramlar komütatiftir

• Kısmi sıra ve ön sıranın kategorik özellikleri

  • Kısmi sıra ile ön sıra, ön sıranın özel durumları olduğundan aynı zamanda kategoridir
  • Ön sıralar kategori teorisinde skeletal categories olarak da anılır; yani izomorfik nesnelerin birbirinden ayrı tutulmadığı kategoriler

• Çarpım ve eşçarpım

  • Bir kategoride coproduct tanımı, iki morfizma $A \to A + B$, $B \to A + B$ ve bir evrensel özellikten oluşur
  • Bu, sıralardaki join tanımıyla tam olarak aynı biçimdedir
  • Sıralarda tüm morfizmalar tekil olduğu için “daha büyük olma”, “tekil bir morfizmanın var olması” ile eşleşir
  • Dolayısıyla ön sıra kategorisinde categorical coproduct, join'dir
  • Dualite gereği product, meet ile örtüşür

• Biçimsel tanım

  • Kategori teorisinde, sıra gibi iki nesne arasında en fazla bir morfizma bulunan kategorilere thin categories denir
  • Her preorder böyle bir thin category olarak görülebilir; tersine, böyle kategoriler de preorder olarak yorumlanabilir
  • Thin category, genel kategorilere kıyasla daha kolay anlaşılabilen bir bağlamda kategori kavramını incelemek için kullanılır
  • Meet ve join'i anlamak, product ve coproduct gibi daha genel kategorik kavramları anlamaya da yardımcı olur
  • Ayrıca nesneler arasındaki çoklu morfizma farklarının önemli olmadığı, yalnızca basit yapının gerektiği durumlarda yararlı bir çerçevedir

[GN⁺]

Hacker News görüşleri

• category theory’yi daha klasik bir yoldan öğrenmek istiyorsanız, birçok kişi ücretsiz olan Tom Leinster’ın Basic Category Theory kitabını öneriyor. Ben de yakında adım adım okumayı planlıyorum; göz gezdirdiğim kadarıyla TFA gibi kaynaklardan daha matematiksel ama oldukça iyi görünüyordu. Özellikle category theory’nin neden başlı başına bir araştırma alanı olduğunu açıklama konusunda daha ikna ediciydi
  • Yine de gerek bu kitap gerekse genel olarak category theory kitaplarının çoğu, lisans düzeyi matematiğe zaten aşina olanları hedef alarak yazılmış gibi geliyor. algebraic structures, linear algebra ve topology’ye aşina değilseniz, aralarda başka kaynaklara da bakmanız gerekebilir. Ayrıca category theory, birleştirmeye çalıştığı semantik bağlamı az çok bildiğinizde daha etkileyici geliyor. Örneğin kitapta initial property ilk başta çok doğal bir şeymiş gibi sunuluyor ama asıl kritik nokta, bunun keyfi yapılarda kendiliğinden geçerli olmadığını fark etmek
• Matematiği satır satır doğrulamayı düşünmeden, metni iyi niyetle okusam bile, yazıdaki şu JavaScript örneği bile güvenimi sarstı: [1, 3, 2].sort((a, b) => { if (a > b) { return true } else { return false } }) gibi bir kod geçerli bir comparator değil. API negatif, 0 ya da pozitif bir değer bekliyor ama bu kod boolean döndürüyor; bende Chrome’da sonuç [1, 3, 2] olarak kaldı. Bana göre yazının matematiksel doğruluğu da buna benzer düzeydeydi; ayrıntılı itirazlarımı bu yorumda toparladım
  • Neden bunun kesinlikle JavaScript olduğunu varsaydıklarını merak ettim. Gördüğüm kadarıyla orijinal metinde dil belirtilmiyordu
• Bana kalırsa soyut matematiğin genelinde, özellikle de category theory’de asıl engel insanların "linear order" kavramını anlayamaması değil. Daha büyük sorun, bunun günlük hayattan fazla kopuk olduğu için işe yaramazmış gibi hissettirmesi. Sanki tamamen pürüzsüz bir camın üstüne su dökmek gibi
  • category theory tarafında da ilk duyduğunuzda aklı uçuran bir gerçek gibi bir şey olup olmadığını merak ettim. Eskiden group theory ile beşinci derecenin üstündeki polinomlar için genel bir kapalı form çözüm olmadığının kanıtlanabildiğini ilk duyduğumda çok etkilenmiştim; category theory’de bunun benzeri bir şey var mı diye sormak isterdim
  • Bu eleştirinin düşündüğümden de doğru olduğunu hissediyorum. Matematiğin amacı kesin düşünmekse, o yazı fazla belirsizdi. Kimsenin bunu umursamaması ya da fark etmemesi beni daha da şaşırttı; diğer yorumumda çok eksik de olsa bir hata listesi bıraktım. Sonuç olarak, böyle bir yazının genel okur için pek faydalı olmadığı kanaatine vardım. Yanlış matematik de doğru matematikle benzer şekilde tüketiliyorsa, pratik değeri daha da şüpheli hale geliyor
  • Bence bu bir öğretim yöntemi meselesi. order theory programlamada çok faydalı. Esas nokta, dünyanın totally ordered comparator’lar etrafında döndüğü alışkanlığından çıkmak; özellikle preorder çok güçlü geliyor. Örneğin state machine transition’ları bazı durumlarda preorder olarak görülebilir ve bunu kurabildiğinizde karmaşık testleri <= ilişkisinin sağlanıp sağlanmadığını kontrol etme problemine indirebilirsiniz. Elbette buna alışmak zaman alıyor ama tersine, bunu gündelik işlere ne kadar çok taşırsanız o kadar tanıdık hale geliyor. Bir noktadan sonra testlere bakıp "bu koşul ifadesi şu preorder ile modellenebilir" diye düşünmeye başlıyorsunuz
  • Ben bunu ancak doktoranın ikinci yılı civarında bilinçli olarak fark ettim. Ve o anda, doktorayı bitirince alandan ayrılmak istediğimi hemen anladım
• Yazarın üslubu ve parantezleri aşırı kullanması çok yorucuydu. Gerçekten parenthetic material nadirdir; iyi teknik yazının da parantezi çok daha ölçülü kullandığını düşünüyorum
  • Genel olarak internette, özellikle HN yorumlarında, parantezli ifadelerin gereğinden fazla kullanıldığını hissediyorum. Ben de bazen yapıyorum ama iç içe parantezleri belli bir seviyeden sonra katlayan ya da üstünü çizen bir tarayıcı eklentisi olsa oldukça faydalı olurdu
  • Şaka yollu da olsa, birinin ADHD eğilimini parantez kullanım miktarından biraz okuyabildiğimi düşünüyorum. Tabii Lisp programcıları istisna olabilir
• category theory’yi derinlemesine okumuş değilim ama bana, programcıların zaten yaptığı şeylerin biraz daha matematiksel ifade edilmiş hali gibi geldi. Soyutlama seviyeleri arasında çıkıp inmek, graf yapılarıyla uğraşmak, bir tür object’i başka bir türe dönüştüren fonksiyonlarla düşünmek gibi alışkanlıklara epey benziyor
• category theory’yi esasen yalnızca okların teorisi olarak açıklamanın da mümkün olduğunu düşünüyorum. Tanım gereği her object’in bir identity arrow’u var; dolayısıyla o identity arrow’u object’in kendisiyle eşleyebilirsiniz. Bu açıdan bakınca object’ler bir tür syntactic sugar gibi görünüyor
  • Yazıyı açıp her yerin renkli M&M görselleriyle dolu olduğunu görünce bu nokta bana neredeyse anında apaçık geldi ve sayfayı hemen kapattım
• Geçmişte defter ve kalemle bu tür diyagramlar çizen birini görmüştüm. O zaman bana graph theory gibi gelmişti ve konuşmak için fırsatı kaçırdığıma üzülmüştüm. Adam sanki bunu hobi olarak yapıyor gibiydi; o yüzden daha da merak etmiştim. Bu teori ya da matematik alanlarında kolayca üretilebilecek bulmacalar olup olmadığını, bu işi yapanlara ya da araştıranlara sormak isterdim
  • Ben algebraic graph theory içinde s-arc transitive graphs üzerine çalıştım ama şaşırtıcı biçimde gerçek grafikleri doğrudan çizmek neredeyse hiç gerekmiyordu. Çoğu zaman mesele, group actions, automorphisms, arc-stabilisers gibi şeyler üzerinden akıl yürütmekti. Nasıl bir şey olduğunu merak edenler için kısa bir notu buraya koymuştum. Kendi araştırdığım s-arc-transitivity’yi doğrudan anlatmıyor ama alanın havasını verebilir. graph theory’nin önemli bir kısmı, somut grafikler hiç çizilmeden de ilerleyebiliyor
• 2015’te yüksek lisans yaparken category theory çalışıyordum ve sıralama ilişkilerinin data structures’dan algorithms’e kadar gerçekten çok fazla şeye etki ettiğini görmüştüm. Bana oldukça temel ama merkezi bir konu gibi gelmişti
• Bunu görünce Haskell’deki type classes aklıma geldi. Kendi kurallar kümesiyle order kavramını zarif biçimde tanımlamaları ve ilişkileri temiz şekilde yakalamaları bakımından benzer duruyor
• Bana göre bu kaynak, order relations konusunu gerçekten çok net anlatıyor. Yapıyı görselleştirdiği için soyut kavramları sindirmek çok daha kolay hale gelmiş