Kita mengatakan bahwa \((X,P)\) dan \((Y,Q)\) isomorfik, dan menuliskan \((X,P) \cong(Y,Q)\text{,}\) jika terdapat suatu bijeksi (pemetaan 1–1 dan surjektif) \(f:X\to Y\) sedemikian sehingga \(x_1\le x_2\) dalam \(P\) jika dan hanya jika \(f(x_1)\le f(x_2)\) dalam \(Q\text{.}\) Dalam definisi ini, pemetaan \(f\) disebut isomorfisme dari \(\bfP\) ke \(\bfQ\text{.}\) Dalam Gambar 6.8, dua poset pertama bersifat isomorfik.
Bob melihat pola yang menghubungkan dua poset pertama dalam Gambar 6.8 dan menyatakan bahwa setiap poset dari salah satu di antara kedua tipe tersebut isomorfik dengan poset dari tipe yang lain. Alice mengakui bahwa Bob benar—tetapi pernyataan yang lebih kuat pun berlaku. Empat konstruksi dalam Contoh 6.7 bersifat universal dalam arti bahwa setiap poset isomorfik dengan suatu poset dari masing-masing keempat tipe itu. Dapatkah Anda melihat alasannya? Jika Anda menemui jalan buntu saat menjawab pertanyaan ini, kita akan membahasnya kembali pada akhir bab dan memberikan sebuah petunjuk.
Isomorfisme dari \(\bfP\) ke \(\bfP\) disebut automorfisme dari \(\bfP\text{.}\) Isomorfisme dari \(\bfP\) ke suatu subposet dari \(\bfQ\) disebut penyematan \(\bfP\) ke dalam \(\bfQ\text{.}\) Dalam kebanyakan pembahasan, kita tidak akan membedakan poset-poset yang isomorfik. Kita akan mengatakan bahwa poset \(\PXP\) termuat dalam \(\QYQ\) (atau bahwa \(\bfQ\) memuat \(\bfP\)) apabila terdapat penyematan \(\bfP\) ke dalam \(\bfQ\text{.}\) Kita juga akan mengatakan bahwa \(\bfP\) menghindari \(\bfQ\) apabila tidak ada subposet \(\bfP\) yang isomorfik dengan \(\bfQ\text{,}\) dan kita akan sering menuliskan \(\bfP=\bfQ\) apabila \(\bfP\) dan \(\bfQ\) isomorfik.
Diagram Hasse tak berlabel dengan sembilan titik pada empat tingkat: satu titik terbesar di atas, empat titik pada tingkat berikutnya, tiga titik di bawahnya, dan satu titik terkecil di dasar. Sisi-sisinya menghubungkan titik-titik pada tingkat berdekatan dan membentuk beberapa rantai yang saling bertemu.
Seberapa sulitkah menentukan apakah dua poset isomorfik? Bob menganggapnya tidak terlalu sulit. Bob mengatakan bahwa jika Anda memberinya suatu bijeksi antara kedua himpunan dasar, ia dapat dengan cepat menentukan apakah bijeksi itu membuktikan bahwa kedua poset tersebut isomorfik. Alice merasa bahwa Bob mencampuradukkan masalah menguji apakah dua poset isomorfik dengan sekadar memverifikasi apakah suatu bijeksi tertentu merupakan isomorfisme. Menurut Alice, masalah pertama jauh lebih sulit. Carlos mengatakan bahwa menurutnya masalah itu memang sangat sulit dan, pada kenyataannya, belum ada yang mengetahui apakah terdapat algoritma yang baik.
Perhatikan bahwa poset dalam Gambar 6.13 hanya memiliki satu titik maksimal. Titik semacam ini kadang-kadang disebut satu, dan sebagaimana dapat diduga dinotasikan dengan \(1\text{.}\) Poset tersebut juga hanya memiliki satu titik minimal, yang disebut nol dan dinotasikan dengan \(0\text{.}\)
Dual suatu urutan parsial \(P\) pada himpunan \(X\) dinotasikan dengan \(P^d\) dan didefinisikan oleh \(P^d=\{(y,x):(x,y)\in
P\}\text{.}\) Dual suatu poset \(\PXP\) dinotasikan dengan \(\bfP^d\) dan didefinisikan oleh \(\bfP^d=(X,P^d)\text{.}\) Poset \(\bfP\) bersifat swa-dual jika \(\bfP=\bfP^d\text{.}\)
Poset \(\PXP\) disebut terhubung jika graf keterbandingannya terhubung, i.e., untuk setiap \(x,y\in X\) dengan \(x\ne y\text{,}\) terdapat barisan hingga \(x=x_0,x_1,\dots,x_n=y\) dari titik-titik dalam \(X\) sedemikian sehingga \(x_i\) dapat dibandingkan dengan \(x_{i+1}\) dalam \(P\) untuk \(i=0,1,2,\dots,n-1\text{.}\) Suatu subposet \((Y,P(Y))\) dari \((X,P)\) disebut komponen dari \(\bfP\) jika \((Y,P(Y))\) terhubung dan tidak ada himpunan \(Z\subseteq X\) yang memuat \(Y\) sebagai subhimpunan sejati sehingga \((Z,P(Z))\) terhubung. Komponen satu titik disebut trivial (juga disebut titik lepas atau titik terisolasi); komponen dengan dua titik atau lebih disebut nontrivial. Perhatikan bahwa titik lepas sekaligus merupakan elemen minimal dan elemen maksimal. Kembali ke poset dalam Gambar 6.5, kita melihat bahwa poset tersebut memiliki dua komponen.
Secara alami, graf \(\bfG\) disebut graf keterbandingan apabila terdapat poset \(\PXP\) yang graf keterbandingannya isomorfik dengan \(\bfG\text{.}\) Sebagai contoh, Gambar 6.15 menampilkan graf dengan \(6\) simpul yang bukan merupakan graf keterbandingan. (Pembuktian klaim ini kita serahkan sebagai latihan.)
Graf enam simpul yang disusun dalam tiga baris berisi satu, dua, dan tiga simpul. Sembilan sisinya membentuk kisi segitiga kecil yang terdiri atas empat segitiga.
Demikian pula, graf \(\bfG\) disebut graf penutup apabila terdapat poset \(\PXP\) yang graf penutupnya isomorfik dengan \(\bfG\text{.}\) Tidak setiap graf merupakan graf penutup. Secara khusus, graf apa pun yang memuat segitiga bukanlah graf penutup. Dalam latihan pada akhir bab, Anda akan diminta mengonstruksi graf tanpa segitiga yang bukan graf penutup—dengan beberapa petunjuk mengenai cara melakukannya.
Tanpa berkecil hati, Bob memperhatikan bahwa graf keterbandingan dalam Gambar 6.9 juga merupakan graf ketakterbandingan (untuk poset lain). Ia kemudian menduga bahwa hal ini selalu benar, i.e., setiap kali \(\bfG\) merupakan graf keterbandingan dari poset \(\bfP\text{,}\) terdapat poset lain \(\bfQ\) sedemikian sehingga \(\bfG\) merupakan graf ketakterbandingan dari \(\bfQ\text{.}\) Alice mengatakan bahwa Bob benar mengenai contoh pertama, tetapi ia tidak begitu yakin mengenai dugaan kedua. Dave bergumam bahwa mereka seharusnya melihat graf keterbandingan dari poset ketiga dalam Gambar 6.8. Graf ini bukan merupakan graf ketakterbandingan. Namun, seperti biasanya ketika sedang kebingungan, Dave tidak memberikan alasan apa pun untuk pernyataan tersebut. Dapatkah Anda membantu Alice dan Bob melihat mengapa Dave benar?
Bob semakin bersemangat dan kemudian menyatakan bahwa menentukan apakah suatu graf merupakan graf keterbandingan relatif mudah (ia membacanya di web), tetapi ia menduga bahwa menentukan apakah suatu graf merupakan graf penutup mungkin sulit. Menurut Anda, apakah ia benar—mengenai salah satu atau kedua hal tersebut?
