Subbab 6.1 Notasi dan Terminologi Dasar

Suatu himpunan terurut parsial atau poset \(\bfP\) adalah pasangan \((X,P)\text{,}\) dengan \(X\) sebagai suatu himpunan dan \(P\) sebagai relasi biner yang refleksif, antisimetris, dan transitif pada \(X\text{.}\) (Jika perlu, lihat Subbab B.10 untuk menyegarkan kembali pengertian sifat-sifat ini.) Kita menyebut \(X\) sebagai himpunan dasar, sedangkan \(P\) merupakan urutan parsial pada \(X\text{.}\) Elemen-elemen himpunan dasar \(X\) juga disebut titik, dan poset \(\bfP\) disebut hingga jika himpunan dasarnya \(X\) merupakan himpunan hingga.

Jika \(\PXP\) merupakan poset, lazim ditulis \(x\le y\) dalam \(P\) atau \(y\ge x\) dalam \(P\) sebagai pengganti \((x,y)\in P\text{.}\) Tentu saja, notasi \(x\lt y\) dalam \(P\) dan \(y>x\) dalam \(P\) berarti \(x\le y\) dalam \(P\) dan \(x\ne y\text{.}\) Jika poset \(\bfP\) tetap sepanjang suatu pembahasan, kita terkadang menyingkat \(x\le y\) dalam \(P\) dengan hanya menulis \(x\le y\text{,}\) etc. Jika \(x\) dan \(y\) merupakan titik-titik berbeda dari \(X\text{,}\) kita mengatakan bahwa \(x\) ditutupi oleh \(y\) dalam \(P\)

¹

Mencerminkan ragam ungkapan dalam bahasa Inggris, matematikawan menggunakan frasa-frasa berikut secara bergantian: (1) \(x\) ditutupi oleh \(y\) dalam \(P\text{;}\) (2) \(y\) menutupi \(x\) dalam \(P\text{;}\) dan (3) \((x,y)\) merupakan penutup dalam \(P\text{.}\)

jika \(x\lt y\) dalam \(P\) dan tidak ada titik \(z\in X\) yang memenuhi \(x\lt z\) dan \(z\lt y\) dalam \(P\text{.}\) Sebagai contoh, dalam poset \(\bfP_3=(X,R_3)\) dari Contoh 6.3, \(d\) ditutupi oleh \(e\) dan \(c\) menutupi \(b\text{.}\) Namun, \(a\) tidak ditutupi oleh \(f\) karena \(a\lt e\lt f\) dalam \(R_3\text{.}\) Selanjutnya, kita dapat mengaitkan poset \(\bfP\) dengan sebuah graf penutup \(\mathbf{G}\) yang himpunan simpulnya adalah himpunan dasar \(X\) dari \(\bfP\text{,}\) dengan \(xy\) sebagai sisi dalam \(\mathbf{G}\) jika dan hanya jika salah satu dari \(x\) dan \(y\) menutupi yang lainnya dalam \(\bfP\text{.}\) Sekali lagi, untuk poset \(\bfP_3\) dari Contoh 6.3, graf penutup ditampilkan di sisi kiri Gambar 6.4. Sebenarnya, sisi kanan gambar tersebut hanyalah penggambaran lain dari graf yang sama.

Poset dapat digambarkan dengan mudah melalui diagram graf penutup yang ditata secara tepat pada bidang Euklides. Kita memilih sistem koordinat horizontal/vertikal baku pada bidang dan mensyaratkan agar koordinat vertikal titik yang bersesuaian dengan \(y\) lebih besar daripada koordinat vertikal titik yang bersesuaian dengan \(x\) setiap kali \(y\) menutupi \(x\) dalam \(P\text{.}\) Setiap sisi dalam graf penutup direpresentasikan oleh ruas garis lurus yang tidak memuat titik yang bersesuaian dengan elemen poset mana pun selain kedua titik ujungnya. Diagram semacam ini disebut diagram Hasse (diagram poset, diagram urutan, atau cukup diagram). Sekarang jelas bahwa gambar di sisi kanan Gambar 6.4 merupakan diagram poset \(\bfP_3\) dari Contoh 6.3, sedangkan gambar di sisi kiri bukan.

Untuk poset berukuran sedang, diagram sering digunakan untuk mendefinisikan poset—alih-alih notasi relasi biner eksplisit seperti pada Contoh 6.3. Pada Gambar 6.5, kita menggambarkan poset \(\PXP\) dengan himpunan dasar \(X=[18]=\{1,2,\dots,18\}\text{.}\) Diperlukan beberapa baris teks untuk menuliskan relasi biner \(P\) secara lengkap, sedangkan diagram memberi kita gambaran yang lebih nyata mengenai sifat-sifat poset tersebut.

Urutan parsial \(P\) disebut urutan total (juga disebut urutan linear) jika untuk setiap \(x,y\in X\text{,}\) berlaku \(x\le y\) dalam \(P\) atau \(y\le x\) dalam \(P\text{.}\) Untuk himpunan hingga berukuran kecil, kita dapat menentukan suatu urutan linear dengan mendaftarkan elemen-elemennya dari yang terkecil hingga yang terbesar. Sebagai contoh, \(L=[b,c,d,a,f,g,e]\) merupakan urutan linear pada himpunan dasar \(\{a,b,c,d,e,f,g\}\) dengan \(b\lt c\lt d\lt a\lt f\lt g\lt e\) dalam \(L\text{.}\)

Himpunan bilangan real dilengkapi dengan urutan total alami. Sebagai contoh, \(1\lt 7/5\lt \sqrt{2}\lt \pi\) dalam urutan ini. Namun, dalam bab ini kita terutama tertarik pada urutan parsial yang bukan urutan linear. Kita juga perlu berhati-hati ketika membahas urutan parsial pada himpunan dasar yang elemen-elemennya merupakan bilangan real. Pada poset yang ditampilkan dalam Gambar 6.5, perhatikan bahwa \(14\) lebih kecil daripada \(8\text{,}\) sedangkan \(3\) dan \(6\) tidak dapat dibandingkan. Sebaiknya jangan memberi tahu orang tua Anda bahwa Anda telah mempelajari bahwa, dalam keadaan tertentu, \(14\) dapat lebih kecil daripada \(8\) dan bahwa Anda mungkin tidak dapat mengatakan mana di antara \(3\) dan \(6\) yang lebih besar. Nuansa ini mungkin akan hilang dalam perdebatan sengit yang hampir pasti menyusul.

Titik-titik berbeda \(x\) dan \(y\) dalam poset \(\PXP\) disebut dapat dibandingkan jika berlaku \(x\lt y\) dalam \(P\) atau \(x>y\) dalam \(P\text{;}\) jika tidak, \(x\) dan \(y\) disebut tidak dapat dibandingkan. Jika \(x\) dan \(y\) tidak dapat dibandingkan dalam \(\bfP\text{,}\) terkadang kita menulis \(x\| y\) dalam \(\bfP\text{.}\) Dengan poset \(\PXP\text{,}\) kita mengaitkan sebuah graf keterbandingan \({\bfG}_1=(X,E_1)\) dan sebuah graf ketakterbandingan \({\bfG}_2=(X,E_2)\text{.}\) Sisi-sisi dalam graf keterbandingan \({\bfG}_1\) terdiri atas pasangan-pasangan yang dapat dibandingkan, sedangkan sisi-sisi dalam graf ketakterbandingan merupakan pasangan-pasangan yang tidak dapat dibandingkan. Kita menggambarkan definisi ini pada Gambar 6.9, yang menampilkan graf keterbandingan dan graf ketakterbandingan dari poset \(\bfP_3\text{.}\)

Jika \(\PXP\) merupakan poset dan \(Y\subseteq X\text{,}\) relasi biner \(Q=P\cap(Y\times Y)\) merupakan urutan parsial pada \(Y\text{,}\) dan kita menyebut poset \((Y,Q)\) sebagai subposet dari \(\bfP\text{.}\) Pada Gambar 6.10, kita menampilkan sebuah subposet dari poset yang pertama kali disajikan dalam Gambar 6.5.

Jika \(\PXP\) merupakan poset dan \(C\) adalah subhimpunan dari \(X\text{,}\) kita menyebut \(C\) sebagai rantai jika setiap pasangan titik berbeda dari \(C\) dapat dibandingkan dalam \(P\text{.}\) Jika \(P\) merupakan urutan linear, seluruh himpunan dasar \(X\) adalah rantai. Secara dual, jika \(A\) merupakan subhimpunan dari \(X\text{,}\) kita menyebut \(A\) sebagai antirantai jika setiap pasangan titik berbeda dari \(A\) tidak dapat dibandingkan dalam \(P\text{.}\) Perhatikan bahwa subhimpunan berelemen tunggal merupakan rantai sekaligus antirantai. Kita juga menganggap himpunan kosong sebagai rantai sekaligus antirantai.

Tinggi suatu poset \(\PXP\text{,}\) yang dinotasikan dengan \(\height(\bfP)\), adalah bilangan terbesar \(h\) yang untuknya terdapat rantai dengan \(h\) titik dalam \(\bfP\text{.}\) Secara dual, lebar suatu poset \(\PXP\text{,}\) yang dinotasikan dengan \(\width(\bfP)\), adalah bilangan terbesar \(w\) yang untuknya terdapat antirantai dengan \(w\) titik dalam \(\bfP\text{.}\)