Urutan yang Dilihat Melalui Gambar Kategori

• Struktur urutan terbentuk ketika relasi biner pada himpunan elemen memenuhi hukum seperti refleksivitas, transitivitas, dan antisimetri
• Urutan linear adalah struktur di mana setiap dua elemen dapat dibandingkan, dan jika totalitas dihapus maka menjadi urutan parsial
• Dalam urutan parsial, struktur dapat dipahami melalui chain, elemen terbesar·elemen terkecil, join·meet, dan diagram Hasse
• Pencampuran warna, keterbagian bilangan, dan relasi inklusi himpunan adalah contoh urutan parsial, dan jika semuanya memiliki join dan meet maka terbentuk lattice
• Preorder adalah struktur yang hanya memiliki refleksivitas dan transitivitas, dan setiap preorder dapat ditafsirkan sebagai kategori yang memiliki paling banyak satu morfisme di antara dua objek

---

Urutan

• Urutan terdiri dari himpunan elemen dan relasi biner di atasnya, dan menjadi struktur matematis ketika memenuhi hukum tertentu
  • Yang penting bukan kriteria pengurutannya sendiri, melainkan sifat relasi antarelemen
  • Relasi biner adalah relasi antara dua elemen dalam suatu himpunan, dan bisa juga dinyatakan dengan panah
• Dalam teori himpunan, urutan dapat dinyatakan sebagai himpunan bagian dari hasil kali Cartesius himpunan dengan dirinya sendiri; dalam pemrograman, dapat dinyatakan sebagai fungsi yang membandingkan dua objek
  • Namun tidak semua fungsi pembanding atau himpunan pasangan elemen mendefinisikan urutan; agar hasilnya konsisten terlepas dari susunan awal, diperlukan aturan tertentu

Urutan linear

• Urutan linear** adalah urutan di mana semua elemen memiliki posisi relatif satu sama lain, yaitu struktur yang** tidak ambigu mengenai apakah suatu elemen mendahului elemen lain

  • Contohnya adalah urutan warna berdasarkan panjang gelombang cahaya atau susunan warna dalam pelangi
  • Urutan linear didefinisikan sebagai relasi biner yang memenuhi refleksivitas, transitivitas, antisimetri, dan totalitas
  • Keempat hukum ini adalah syarat pembentuk relasi urutan

• Refleksivitas

  • Setiap elemen harus lebih besar atau sama dengan dirinya sendiri, sehingga untuk setiap $a$, berlaku $a \le a$
  • Ini adalah aturan untuk menangani kasus dasar; sebaliknya, jika didefinisikan agar tidak berelasi dengan dirinya sendiri, terbentuk jenis lain yang mirip strict order

• Transitivitas

  • Jika $a \le b$ dan $b \le c$, maka harus berlaku $a \le c$
  • Ini adalah hukum yang sangat menentukan inti dari urutan

• Antisimetri

  • Ini adalah aturan yang melarang hasil perbandingan yang saling bertentangan; jika $x \le y$ dan $y \le x$, itu hanya diizinkan ketika $x = y$
  • Dapat diringkas juga sebagai tidak adanya hasil seri di antara elemen berbeda

• Totalitas

  • Setiap dua elemen harus dapat dibandingkan, sehingga untuk sembarang dua elemen berlaku $a \le b \lor b \le a$
  • Artinya, untuk elemen mana pun, salah satunya harus lebih besar atau sama dengan yang lain
  • Karena totalitas mencakup kasus saat $a$ dan $b$ sama, refleksivitas termasuk sebagai kasus khusus
  • Jika totalitas dihapus, hasilnya adalah urutan parsial, dan urutan linear juga disebut total order

• Urutan bilangan asli

  • Bilangan asli membentuk urutan linear di bawah relasi lebih besar atau sama dengan
  • Setiap urutan linear hingga isomorfik dengan subhimpunan bilangan asli, dengan mencocokkan elemen pertama ke 1, elemen kedua ke 2, dan seterusnya
  • Karena itu, semua urutan linear hingga dengan ukuran yang sama saling isomorfik
  • Dari sudut pandang teori kategori, juga disebutkan bahwa diagram semua urutan linear hingga dan sebagian besar urutan linear tak hingga tampak sama

Urutan parsial

• Urutan parsial adalah struktur yang diperoleh dari urutan linear dengan menghapus totalitas, sehingga hanya menyisakan refleksivitas, transitivitas, dan antisimetri
  • Istilah lain yang juga digunakan adalah partially-ordered set, atau poset
• Semua urutan linear adalah urutan parsial, tetapi tidak semua urutan parsial adalah urutan linear
• Urutan parsial juga berkaitan dengan relasi ekuivalensi; strukturnya dapat dipandang sebagai relasi ekuivalensi dengan simetri diganti menjadi antisimetri
• Dalam contoh perbandingan kemampuan sepak bola, jika hanya ada beberapa orang yang bisa dibandingkan secara langsung atau tidak langsung maka urutan linear mungkin terbentuk, tetapi jika ada orang-orang yang belum pernah saling bertanding maka strukturnya menjadi non-linear dan membentuk urutan parsial
  • Urutan parsial tidak selalu dapat memberi jawaban yang tegas untuk pertanyaan siapa yang lebih baik

• Chain

  • Urutan parsial dapat terdiri dari beberapa subhimpunan linear, dan subhimpunan linear semacam ini disebut chain
  • Sebagai contoh diberikan dua chain: $m \to g \to f$ dan $d \to o$
  • Chain tidak harus sepenuhnya terpisah; selama semua koneksi tidak menyatu menjadi satu chain tunggal yang tersambung satu per satu, struktur urutan parsial tetap terjaga
  • Dalam contoh tersebut kita dapat mengetahui $d \le g$ dan $f \le g$, tetapi relasi antara $d$ dan $f$ belum ditentukan

• Elemen terbesar dan elemen terkecil

  • Jika suatu elemen $a$ memenuhi $x \le a$ untuk setiap elemen lain $x$, maka elemen itu disebut greatest element
  • Beberapa urutan parsial memiliki elemen seperti ini; pada diagram contoh, $m$ adalah greatest element
  • Walaupun ada beberapa elemen yang semuanya lebih besar daripada elemen lain, jika mereka tidak saling identik maka greatest element tetap tidak ada
  • Dengan cara yang sama, least element juga didefinisikan

• Join

  • Least upper bound dari dua elemen yang terhubung disebut join
  • Syarat definisinya ada dua
    • Harus berlaku $A \le G$ dan $B \le G$
    • Untuk elemen lain sembarang $P$ yang lebih besar daripada $A$ dan $B$, harus berlaku $G \le P$
  • Jika satu elemen lebih besar daripada elemen lainnya, join adalah elemen yang lebih besar itu sendiri
  • Dalam urutan linear, join dari sembarang dua elemen adalah elemen yang lebih besar
  • Jika ada beberapa batas atas dengan tingkat yang sama, join tidak ada; join harus unik

• Meet

  • Di antara elemen-elemen yang lebih kecil atau sama dengan kedua elemen, elemen terbesar disebut meet
  • Aturan yang sama seperti join diterapkan ke arah yang berlawanan

• Diagram Hasse

  • Diagram yang digunakan dalam bagian ini adalah diagram Hasse
  • Ada aturan tambahan bahwa elemen yang lebih besar selalu ditempatkan lebih tinggi
  • Jika ada panah, titik yang dituju panah selalu berada lebih tinggi
  • Dengan tata letak ini, kita dapat membandingkan hanya dengan melihat posisi atas-bawah dua titik, dan join juga dapat diidentifikasi dengan mencari elemen terendah yang terhubung secara bersama

• Urutan parsial pencampuran warna

  • Diperkenalkan color-mixing partial order yang didefinisikan dengan membuat setiap warna mengarah ke warna yang memuat warna tersebut
  • Join dari dua warna sembarang adalah warna yang dihasilkan ketika keduanya dicampur

• Urutan parsial bilangan berdasarkan pembagian

  • Jika bilangan diurutkan bukan berdasarkan besarannya melainkan berdasarkan keterbagian, terbentuk urutan parsial
  • Didefinisikan bahwa jika $a$ membagi $b$, maka $a$ mendahului $b$
  • Sebagai contoh, karena $2 \times 5 = 10$, maka 2 dan 5 mendahului 10, tetapi 3 tidak mendahului 10
  • Dalam urutan ini, join adalah kelipatan persekutuan terkecil, sedangkan meet adalah faktor persekutuan terbesar

• Urutan parsial inklusi

  • Ketika ada beberapa himpunan yang memuat sebagian elemen yang sama, dapat didefinisikan inclusion order
  • Jika himpunan $a$ memuat $b$, atau dengan kata lain $b$ adalah subhimpunan dari $a$, maka $a$ mendahului $b$
  • Dalam kasus ini, join adalah gabungan, dan meet adalah irisan
  • Jika warna-warna yang terkandung di tiap himpunan dicampur, terbentuk struktur yang sama dengan urutan parsial pencampuran warna yang dibahas sebelumnya
  • Urutan pembagian pada bilangan isomorfik dengan urutan inklusi dari himpunan bilangan prima atau prime powers yang mengizinkan pengulangan
  • Hal ini dapat dipastikan oleh teorema dasar aritmetika, yang menyatakan bahwa setiap bilangan dapat dinyatakan sebagai hasil kali bilangan prima dengan tepat satu cara

Teorema representasi Birkhoff

• Urutan parsial pencampuran warna dan urutan parsial pembagian bilangan sama-sama dapat direpresentasikan sebagai urutan inklusi atas kombinasi himpunan yang mungkin dari elemen-elemen dasar tertentu
  • Pada kasus pertama, elemen dasarnya adalah warna primer; pada kasus kedua, bilangan prima atau pangkat bilangan prima
• Apakah suatu urutan parsial hingga dapat direpresentasikan dengan cara ini diatur oleh Birkhoff’s representation theorem
  • Ada dua syarat
    • Untuk setiap pasangan elemen, harus ada join dan meet
    • Join dan meet harus distributif satu terhadap yang lain. Dengan notasi $∨$, $∧$, berlaku $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
• Urutan parsial yang setiap elemennya memiliki join dan meet disebut lattice
• Jika operasi-operasi itu saling distributif, disebut distributive lattice
• Elemen “prima” yang membentuk inclusion order adalah elemen yang tidak dapat dinyatakan sebagai join dari elemen lain, dan disebut join-irreducible elements
• Teorema ini juga dapat dinyatakan sebagai: setiap distributive lattice isomorfik dengan inclusion order dari join-irreducible elements miliknya sendiri
• Urutan parsial yang bukan distributive lattice pun bisa saja isomorfik dengan inclusion order, tetapi dalam hal itu korespondensinya adalah dengan inclusion order yang tidak memuat semua kombinasi yang mungkin

Kisi

• Lattice adalah urutan parsial di mana setiap dua elemen memiliki join dan meet
  • Setiap lattice adalah urutan parsial, tetapi tidak semua urutan parsial adalah lattice
• Banyak urutan parsial yang dibentuk oleh aturan tertentu merupakan distributive lattice, dan contoh-contoh pada bagian sebelumnya juga menjadi distributive lattice jika digambar secara lengkap
• Dalam contoh pencampuran warna, ditambahkan bola hitam di bagian atas dan bola putih di bagian bawah
  • Tanpa itu, tiga elemen di atas tidak memiliki join dan tiga elemen di bawah tidak memiliki meet

• Kisi berbatas

  • Lattice yang memiliki greatest element dan least element sekaligus disebut bounded lattice
  • Dalam lattice pencampuran warna, bola hitam adalah greatest element dan bola putih adalah least element
  • Disebutkan juga bahwa semua lattice hingga bersifat bounded

Isomorfisme urutan

• Isomorfisme urutan adalah fungsi yang dapat dibalik antara himpunan dasar dari dua urutan, sekaligus fungsi yang mempertahankan panah urutan
• Dengan mengambil contoh urutan pembagian bilangan dan urutan inklusi bilangan prima, ia tersusun dari dua fungsi
  • Fungsi dari urutan inklusi bilangan prima ke urutan bilangan adalah perkalian elemen-elemen himpunan
  • Fungsi dari urutan bilangan ke urutan inklusi bilangan prima adalah prime factorization yang menguraikan bilangan menjadi hasil kali faktor prima
• Syarat inti isomorfisme urutan adalah bahwa untuk dua elemen $a$, $b$, berlaku $a \le b$ jika dan hanya jika $F(a) \le F(b)$
• Fungsi semacam ini disebut fungsi order-preserving

Praurutan

• Preorder adalah struktur yang diperoleh dari urutan linear dengan menghapus antisimetri, sehingga hanya menyisakan refleksivitas dan transitivitas
• Jika dilihat dari kriteria keterbandingan
  • Dalam urutan linear, berlaku $a \le b$ atau $b \le a$
  • Dalam urutan parsial, salah satunya bisa benar, atau keduanya bisa tidak benar
  • Dalam preorder, salah satunya bisa benar, keduanya bisa tidak benar, atau keduanya benar
• Preorder berbeda dari makna urutan dalam kehidupan sehari-hari, karena panah bisa berjalan dari sembarang titik ke titik lain
  • Diberikan contoh pemodelan sepak bola dengan “siapa mengalahkan siapa”, termasuk kemenangan tidak langsung
• Karena transitivitas, kemenangan tidak langsung juga ditambahkan seperti relasi langsung, dan akibatnya jika ada relasi siklik maka beberapa objek membentuk struktur yang semuanya saling terhubung

• Preorder dan relasi ekuivalensi

  • Preorder adalah struktur perantara antara urutan parsial dan relasi ekuivalensi
  • Sebab yang hilang hanya titik pembeda berupa (anti)simetri
  • Dalam preorder, elemen-elemen yang saling terhubung dua arah memenuhi simetri, sehingga membentuk relasi ekuivalensi
  • Jika elemen-elemen itu dikelompokkan, terbentuk equivalence classes dari preorder tersebut
  • Jika hanya koneksi antarkelas ekuivalensi yang dipindahkan, koneksi itu akan memenuhi antisimetri dan membentuk urutan parsial
  • Karena itu, untuk setiap preorder dapat didefinisikan urutan parsial di atas kelas-kelas ekuivalensinya

Preorder dan kategori

• Transitivitas pada preorder adalah aturan bahwa jika ada $a \le b$ dan $b \le c$, maka muncul $a \le c$, dan ini dapat ditafsirkan sebagai komposisi relasi
• Definisi kategori mencakup dua syarat berikut
  • Setiap objek memiliki morfisme identitas
  • Dua morfisme yang sesuai dapat dikomposisikan, dan komposisi itu harus asosiatif
• Dalam preorder, transitivitas menangani komposisi, sedangkan refleksivitas berperan sebagai morfisme identitas
• Karena itu, setiap preorder adalah kategori
• Dalam kategori umum, bisa ada banyak morfisme di antara dua objek, tetapi dalam preorder hanya ada paling banyak satu morfisme di antara dua objek sembarang
  • Ada atau tidak adanya $a \le b$, hanya itu kemungkinannya
• Seperti halnya monoid adalah kategori dengan satu objek, urutan dapat diringkas sebagai kategori yang memiliki paling banyak satu morfisme di antara dua objek
• Karena sifat ini, dalam preorder semua diagram bersifat komutatif

• Sifat kategoris dari urutan parsial dan preorder

  • Urutan parsial dan preorder keduanya merupakan kasus khusus dari preorder, sehingga keduanya juga merupakan kategori
  • Dalam teori kategori, preorder disebut sebagai skeletal categories, yaitu kategori yang tidak mempertahankan objek-objek isomorfik sebagai entitas terpisah

• Produk dan koproduk

  • Definisi coproduct dalam kategori terdiri dari dua morfisme $A \to A + B$, $B \to A + B$ beserta sifat universalnya
  • Bentuk ini persis sama dengan definisi join dalam urutan
  • Dalam urutan, semua morfisme bersifat unik, sehingga “lebih besar” berkorespondensi dengan “ada morfisme unik”
  • Karena itu, dalam kategori preorder, categorical coproduct adalah join
  • Melalui dualitas, product berkorespondensi dengan meet

• Definisi formal

  • Dalam teori kategori, kategori yang seperti urutan—yakni memiliki paling banyak satu morfisme di antara dua objek—disebut thin categories
  • Setiap preorder dapat dipandang sebagai thin category, dan sebaliknya kategori seperti itu dapat ditafsirkan sebagai preorder
  • Thin category digunakan untuk mengeksplorasi konsep kategori dalam konteks yang lebih mudah dipahami daripada kategori umum
  • Memahami meet dan join juga membantu dalam memahami konsep kategori yang lebih umum seperti product dan coproduct
  • Kerangka ini juga berguna ketika kita tidak tertarik pada perbedaan banyak morfisme di antara objek dan hanya memerlukan struktur yang sederhana

[GN⁺]

Opini Hacker News

• Jika ingin belajar category theory dengan pendekatan yang lebih ortodoks, banyak orang merekomendasikan Basic Category Theory karya Tom Leinster yang gratis. Aku juga berencana membacanya pelan-pelan segera, dan dari kesan sekilas, buku itu terasa lebih matematis daripada materi seperti TFA, tetapi cukup bagus. Terutama, penjelasannya terasa lebih meyakinkan dalam menjelaskan mengapa category theory layak berdiri sebagai satu bidang penelitian tersendiri
  • Meski begitu, buku ini juga, seperti buku-buku category theory pada umumnya, menurutku ditulis dengan asumsi pembacanya sudah terbiasa dengan matematika tingkat sarjana. Jika belum akrab dengan algebraic structures, linear algebra, atau topology, kemungkinan besar perlu sesekali mencari referensi lain sambil jalan. Dan category theory juga terasa lebih mengena kalau kita sudah agak paham konteks semantik yang ingin disatukannya. Misalnya, buku itu mula-mula memperkenalkan initial property seolah tampak jelas dengan sendirinya, tetapi poin pentingnya justru baru terlihat kalau kita sadar bahwa pada struktur sembarang hal itu tidak otomatis berlaku
• Bahkan jika membaca tulisannya dengan itikad baik tanpa berniat memeriksa semua matematikanya satu per satu, kepercayaanku sudah goyah hanya dari contoh JavaScript ini saja: [1, 3, 2].sort((a, b) => { if (a > b) { return true } else { return false } }) bukan comparator yang valid. API-nya mengharapkan bilangan negatif, 0, atau positif, tetapi kode itu mengembalikan boolean, dan di Chrome milikku hasilnya tetap [1, 3, 2]. Menurutku, ketelitian matematis tulisan itu kira-kira berada di tingkat yang sama, dan kritik rinci sudah kurangkum di komentar ini
  • Aku penasaran kenapa harus diasumsikan bahwa kode itu pasti JavaScript. Setahuku, di sumber aslinya tidak ada penanda bahasa sama sekali
• Menurutku, hambatan utama dalam matematika abstrak secara umum, terutama category theory, bukan karena orang tidak paham "linear order". Masalah yang lebih besar adalah kesan bahwa ini tidak berguna karena terlalu jauh dari kehidupan sehari-hari. Rasanya seperti menuangkan air ke atas kaca yang benar-benar licin
  • Aku penasaran apakah di category theory juga ada semacam fakta yang bikin kepala pening saat pertama kali mendengarnya. Dulu aku benar-benar takjub saat pertama kali mendengar bahwa group theory bisa dipakai untuk membuktikan tidak adanya solusi analitik umum untuk polinomial derajat lebih dari 5; aku ingin tahu apakah category theory punya padanan seperti itu
  • Rasanya kritik ini bahkan lebih tepat daripada yang kukira. Jika tujuan matematika adalah berpikir secara presisi, maka tulisan itu terlalu tidak presisi. Aku justru heran karena tampaknya tidak ada yang peduli atau menyadarinya, dan di komentar lainku aku menulis daftar kesalahan yang sangat tidak lengkap. Kesimpulanku adalah tulisan seperti ini tidak terlalu membantu pembaca umum. Jika matematika yang salah bisa dikonsumsi dengan cara yang mirip dengan matematika yang benar, maka kegunaan praktisnya jadi makin patut diragukan
  • Menurutku ini masalah cara mengajar. order theory itu sangat berguna dalam pemrograman. Kuncinya adalah keluar dari kebiasaan memandang dunia berpusat pada comparator yang totally ordered, dan menurutku preorder sangat kuat. Misalnya, transisi state machine dalam beberapa kasus bisa dipandang sebagai preorder, dan kalau bisa dimodelkan seperti itu, pengujian yang rumit dapat direduksi menjadi persoalan memeriksa apakah <= berlaku. Memang butuh banyak latihan sampai terasa alami, tetapi sebaliknya, kalau terus dibawa ke pekerjaan sehari-hari, lama-lama akan terasa akrab. Lalu saat melihat sebuah test, bisa muncul intuisi seperti, "kondisi ini bisa dimodelkan sebagai preorder tertentu"
  • Aku baru benar-benar menyadari ini secara sadar kira-kira setelah dua tahun menjalani program doktoral. Dan pada saat itu juga, aku langsung tahu bahwa setelah lulus aku ingin meninggalkan bidang ini
• Gaya bahasa penulis dan penggunaan tanda kurung yang berlebihan sangat menyiksa. Materi yang benar-benar parenthetical itu sebenarnya jarang, dan menurutku tulisan teknis yang baik jauh lebih hemat memakai tanda kurung
  • Rasanya di internet secara umum, terutama di komentar HN, ekspresi dengan tanda kurung muncul terlalu sering. Aku sendiri kadang begitu juga, tetapi akan cukup berguna kalau ada ekstensi browser yang melipat atau mencoret tanda kurung bertingkat setelah level tertentu
  • Aku kadang bercanda merasa bisa membaca sedikit banyak kecenderungan ADHD seseorang dari seberapa banyak mereka memakai tanda kurung. Tentu saja, programmer Lisp mungkin pengecualian
• Aku belum pernah mendalami category theory, tetapi rasanya seperti versi yang lebih matematis dari hal-hal yang sejak lama dilakukan programmer. Naik-turun tingkat abstraksi, menangani graf, dan memikirkan fungsi yang mengubah object dari satu jenis ke jenis lain terasa sangat mirip
• Menurutku category theory juga bisa dijelaskan secara efektif sebagai teori tentang panah semata. Semua object, menurut definisinya, punya identity arrow, jadi identity arrow itu bisa dipetakan ke object itu sendiri. Dari sudut pandang itu, object tampak seperti semacam syntactic sugar
  • Begitu membuka artikelnya dan melihat penuh dengan gambar M&M berwarna, poin ini langsung terasa hampir seketika, dan aku pun segera menutupnya
• Dulu aku pernah melihat seseorang menggambar diagram seperti ini dengan buku catatan dan pensil. Saat itu tampak seperti graph theory, dan aku menyesal karena melewatkan kesempatan untuk menyapanya. Orang itu terlihat seperti mengerjakannya sebagai hobi, jadi aku makin penasaran. Aku ingin bertanya kepada orang-orang yang bekerja atau meneliti bidang ini apakah ada teka-teki yang mudah dibuat dari teori atau matematika semacam ini
  • Aku pernah mengerjakan topik s-arc transitive graphs dalam algebraic graph theory, dan ternyata hampir tidak pernah perlu menggambar graf sungguhan secara langsung. Kebanyakan pekerjaannya berupa penalaran tentang group actions, automorphisms, arc-stabilisers, dan semacamnya. Untuk yang penasaran bentuk nyatanya seperti apa, aku menaruh catatan singkat di sini. Memang tidak membahas s-arc-transitivity yang kuteliti secara langsung, tetapi cukup memberi gambaran nuansa bidangnya. Sebagian besar graph theory bisa berjalan tanpa menggambar graf konkret sama sekali
• Saat mengambil master pada 2015, aku belajar category theory dan melihat bahwa relasi urutan memengaruhi begitu banyak hal, dari data structures sampai algorithms. Rasanya ini topik yang cukup mendasar sekaligus inti
• Ini mengingatkanku pada type classes di Haskell. Kemiripannya terasa pada cara ia mendefinisikan konsep order dengan anggun lewat seperangkat aturan sendiri, sambil menangkap relasi-relasi itu dengan rapi
• Menurutku materi ini menjelaskan order relations dengan sangat jelas. Visualisasi strukturnya membuat konsep yang abstrak jauh lebih mudah dicerna