Pada bagian ini, kita mengembangkan algoritme untuk menemukan representasi interval dari suatu urutan interval. Bahkan, algoritme ini dapat diterapkan pada poset apa pun. Algoritme tersebut akan menemukan representasi interval atau menemukan subposet yang isomorfik dengan \(\bftwo+\bftwo\text{.}\) Sebagai konsekuensinya, kita membuktikan arah sebaliknya dari Teorema Fishburn.
Jika \(\PXP\) merupakan urutan interval dan \(n\) bilangan bulat positif, mungkin ada banyak cara untuk merepresentasikan \(\bfP\) menggunakan interval yang titik ujungnya berupa bilangan bulat dalam \([n]\text{.}\) Namun, tentu ada \(n\) terkecil yang memungkinkan ditemukannya sebuah representasi, dan di sini kita akan melihat bahwa representasi tersebut unik. Pembahasan ini kembali menggunakan notasi himpunan bawah dan himpunan atas yang diperkenalkan sebelum bukti Teorema Dilworth. Sebagai pengingat, notasi tersebut kita ulangi di sini. Untuk poset \(\PXP\) dan subhimpunan \(S\subset X\text{,}\) misalkan \(D(S)
= \{y\in X:\) terdapat suatu \(x\in S\) sedemikian sehingga \(y\lt x\) dalam \(P\}\text{.}\) Misalkan pula \(D[S]=D(S)\cup
S\text{.}\) Jika \(|S|=1\text{,}\) katakanlah \(S=\{x\}\text{,}\) kita menulis \(D(x)\) dan \(D[x]\text{,}\) bukan \(D(\{x\})\) dan \(D[\{x\}]\text{.}\) Secara dual, untuk subhimpunan \(S\subseteq X\text{,}\) kita mendefinisikan \(U(S) =
\{y\in X:\) terdapat suatu \(x\in S\) sedemikian sehingga \(y>x\) dalam \(P\}\text{.}\) Seperti sebelumnya, misalkan \(U[S]=U(S)\cup
S\text{.}\) Jika \(S=\{x\}\text{,}\) kita cukup menulis \(U(x)\) untuk \(\{y\in X:x\lt y\) dalam \(P\}\text{.}\)
Misalkan \(\PXP\) sebuah poset. Kita memulai prosedur dengan mencari keluarga subhimpunan berikut dari himpunan dasar: \(\mathcal{D} = \{D(x):x\in X\}\text{.}\) Selanjutnya, kita membedakan dua kasus. Dalam kasus pertama, terdapat dua elemen berbeda \(x\) dan \(y\) sedemikian sehingga \(D(x)\nsubseteq D(y)\) dan \(D(y)\nsubseteq
D(x)\text{.}\) Dalam kasus ini, kita memilih sebuah elemen \(z\in D(x)-D(y)\) dan sebuah elemen \(w\in
D(y)-D(x)\text{.}\) Dengan demikian, keempat elemen dalam \(\{x,y,z,w\}\) membentuk subposet dari \(\bfP\) yang isomorfik dengan \(\bftwo+\bftwo\text{.}\)
Kasus kedua ialah \(D(x)\subseteq D(y)\) atau \(D(y)\subseteq D(x)\) untuk setiap \(x,y\in
X\text{.}\) Dalam kasus ini, akan kita tunjukkan bahwa \(\bfP\) merupakan urutan interval. Sekarang tentukan keluarga \(\mathcal{U}
= \{U(x):x\in X\}\text{.}\) Mudah dilihat bahwa dalam kasus ini kita selalu memiliki \(U(x)\subseteq
U(y)\) atau \(U(y)\subseteq U(x)\) untuk setiap \(x,y\in X\text{.}\)
Misalkan \(d=|\mathcal{D}|\text{.}\) Dalam latihan, kami akan menyajikan (sebenarnya, dengan mengerjakan pekerjaan rumah, Andalah yang akan menyajikan) rincian yang mendukung pernyataan berikut: \(|\mathcal{U}|=|\mathcal{D}|\text{.}\) Untuk sementara, kita menganggap pernyataan ini benar. Beri label pada himpunan-himpunan dalam \(\mathcal{D}\) dan \(\mathcal{U}\text{,}\) secara berurutan, sebagai \(D_1\text{,}\)\(D_2,\dots,D_d\) dan \(U_1\text{,}\)\(U_2,\dots,U_d\) sedemikian sehingga
Kita membentuk representasi interval \(I\) dari \(\bfP\) dengan aturan berikut: untuk setiap \(x\in
X\text{,}\) tetapkan \(I(x)=[i,j]\text{,}\) dengan \(D(x)=D_i\) dan \(U(x)=U_j\text{.}\) Belum langsung jelas bahwa aturan ini sah; i.e., penerapan aturan tersebut mungkin saja menghasilkan nilai \(i\) dan \(j\) yang memenuhi \(j\lt i\text{.}\) Namun, melalui latihan kita akan melihat bahwa hal ini tidak pernah terjadi. Rangkaian latihan tersebut dirangkum dalam teorema berikut.
Untuk setiap \(x,y\in X\text{,}\) jika \(I(x)=[i,j]\) dan \(I(y)=[k,l]\text{,}\) maka \(x\lt y\) dalam \(P\) jika dan hanya jika \(j\lt k\) dalam \(\reals\text{.}\)
Bilangan bulat \(d\) merupakan bilangan bulat positif terkecil yang memungkinkan \(\bfP\) memiliki representasi interval dengan titik ujung bilangan bulat dari \([d]\text{.}\) Representasi ini unik.
Diagram Hasse sebuah urutan interval pada 10 titik. Titik a, h, dan j masing-masing menutupi c, f, dan g; titik b dan i menutupi h; titik d menutupi c; dan titik e menutupi a, h, dan j.
Untuk poset ini, \(d= 5\text{,}\) dengan \(D_1=\emptyset\text{,}\)\(D_2=\{c\}\text{,}\)\(D_3=\{c,f,g\}\text{,}\)\(D_4=\{c,f,g,h\}\text{,}\) dan \(D_5=\{a,c,f,g,h,j\}\text{.}\) Selain itu, \(U_1=\{a,b,d,e,h,i,j\}\text{,}\)\(U_2=\{a,b,e,h,i,j\}\text{,}\)\(U_3=\{b,e,i\}\text{,}\)\(U_4=\{e\}\text{,}\) dan \(U_5=\emptyset\text{.}\) Jadi,
Untuk mengilustrasikan bagaimana proses ini dapat digunakan untuk menentukan bahwa sebuah poset bukan urutan interval, perhatikan kembali poset dalam Gambar 6.31. Hapus garis yang menghubungkan titik \(c\) dan \(j\text{.}\) Pada poset yang dihasilkan, Anda akan memperoleh \(D(j)=\{f,g\}\) dan \(D(d)=\{c\}\text{.}\) Oleh karena itu, keempat titik \(c\text{,}\)\(d\text{,}\)\(f\text{,}\) dan \(j\) membentuk salinan \(\bftwo+\bftwo\) dalam poset yang telah diubah ini.
