Jika \(\PXP\) merupakan poset dan \(\width(P)=w\text{,}\) terdapat partisi \(X=C_1\cup
C_2\cup\dots \cup C_w\text{,}\) dengan \(C_i\) berupa rantai untuk \(i=1,2,\dots,w\text{.}\) Selain itu, tidak ada partisi rantai yang menggunakan lebih sedikit rantai.
Sebelum melanjutkan dengan pembuktian Teorema Dilworth pada bagian ini nanti, kita berhenti sejenak untuk membahas versi dual bagi partisi menjadi antirantai, karena versi ini bahkan lebih mudah dibuktikan.
Jika \(\PXP\) merupakan poset dan \(\height(P)=h\text{,}\) terdapat partisi \(X=A_1\cup
A_2\cup\dots\cup A_h\text{,}\) dengan \(A_i\) berupa antirantai untuk \(i=1,2,\dots,h\text{.}\) Selain itu, tidak ada partisi yang menggunakan lebih sedikit antirantai.
dengan \(x=x_t\text{.}\) Jelas bahwa \(\height(x)\le h\) untuk semua \(x\in X\text{.}\) Selanjutnya, untuk setiap \(i=1,2,\dots,h\text{,}\) misalkan \(A_i=\{x\in X:\height(x)=i\}\text{.}\) Mudah dilihat bahwa setiap \(A_i\) merupakan antirantai. Sebab, jika \(x,y\in A_i\) dan \(x\lt y\text{,}\) terdapat rantai \(x_1\lt
x_2\lt \cdots\lt x_i=x \lt x_{i+1}=y\text{,}\) sehingga \(\height(y)\ge i+1\text{.}\) Karena \(\height(P)=h\text{,}\) terdapat rantai terbesar \(C=\{x_1,x_2,\dots,x_h\}\text{.}\) Seandainya \(\bfP\) dapat dipartisi menjadi \(t\lt h\) antirantai, maka menurut Prinsip Sarang Merpati, salah satu antirantai akan memuat dua titik dari \(C\text{,}\) padahal hal ini tidak mungkin.
Jika \(\PXP\) merupakan poset, titik \(x\in X\) dengan \(\height(x)=1\) disebut titik minimal dari \(\bfP\text{.}\) Kita menotasikan himpunan semua titik minimal dari poset \(\PXP\) dengan \(\min(X,P)\text{.}\) 1
Karena kita menggunakan notasi \(\bfP= (X,P)\) untuk poset, himpunan elemen minimal dapat dinotasikan dengan \(\min(\bfP)\) atau \(\min(X,P)\text{.}\) Konvensi ini akan digunakan untuk semua fungsi bernilai himpunan dan fungsi bernilai bilangan bulat pada poset.
Argumen dalam pembuktian Teorema 6.18 menghasilkan algoritma yang efisien dan didefinisikan secara rekursif. Tetapkan \(\bfP_0= \bfP\text{.}\) Jika \(\bfP_i\) telah didefinisikan dan \(\bfP_i\neq \emptyset\text{,}\) tetapkan \(A_i=\min(\bfP_i)\text{,}\) lalu gunakan \(\bfP_{i+1}\) untuk menotasikan subposet yang tersisa setelah \(A_i\) dihapus dari \(\bfP_i\text{.}\)
Dalam Gambar 6.19, kita menggambarkan partisi antirantai yang dihasilkan algoritma ini untuk poset \(18\) titik dari Gambar 6.5. Titik-titik gelap membentuk rantai berukuran \(5\text{.}\)
Diagram Hasse poset 18 titik. Setiap titik diberi label tinggi 1 sampai 5, sehingga titik-titik dengan label yang sama membentuk antirantai. Lima titik gelap, masing-masing berlabel 1, 2, 3, 4, dan 5, membentuk satu rantai dari kanan bawah menuju kiri atas.
Secara dual, kita dapat membicarakan himpunan \(\max(\bfP)\) yang terdiri atas titik maksimal dari \(\bfP\text{.}\) Kita juga dapat mempartisi \(\bfP\) menjadi \(\height(\bfP)\) antirantai dengan menghapus himpunan titik maksimal secara rekursif.
Perhatikan bahwa jika \(\PXP\) merupakan poset, himpunan semua rantai dalam \(\bfP\) terurut parsial oleh relasi inklusi. Karena itu, wajar untuk mengatakan bahwa rantai \(C\) bersifat maksimal apabila tidak ada rantai \(C'\) yang memuat \(C\) sebagai subhimpunan sejati. Selain itu, rantai \(C\) disebut terbesar apabila tidak ada rantai \(C'\) dengan \(|C|\lt |C'|\text{.}\) Tentu saja, rantai terbesar bersifat maksimal, tetapi rantai maksimal belum tentu merupakan rantai terbesar.
Dengan terminologi ini, inti Teorema 6.18 adalah bahwa kita dapat dengan mudah menemukan tinggi \(h\) suatu poset serta rantai terbesar \(C\) yang terdiri atas \(h\) titik dari \(\bfP\text{.}\) Tentu saja, kita juga memperoleh partisi praktis dari poset tersebut menjadi \(h\) antirantai.
Argumen untuk Teorema Dilworth menjadi lebih sederhana dengan notasi berikut. Jika \(\PXP\) merupakan poset dan \(x\in X\text{,}\) tetapkan \(D(x)=\{y\in X:y\lt x \text{ dalam } P\}\text{;}\)\(D[x]=\{y\in
X:y\le x\text{ dalam } P\}\text{;}\)\(U(x)=\{y\in X:y>x \text{ dalam } P\}\text{;}\)\(U[x]=\{y\in X:y\ge
x\}\text{;}\) dan \(I(x)=\{y\in X-\{x\}:x\Vert y \text{ dalam } P\}\text{.}\) Jika \(S\subseteq X\text{,}\) tetapkan \(D(S)= \{y\in X:y\lt x\) dalam \(P\text{,}\) untuk suatu \(x\in S\}\) dan \(D[S]=S\cup D(S)\text{.}\) Subhimpunan \(U(S)\) dan \(U[S]\) didefinisikan secara dual. Kita menyebut \(D(x)\text{,}\)\(D[x]\text{,}\)\(D(S)\text{,}\) dan \(D[S]\) sebagai himpunan bawah, sedangkan \(U(x)\text{,}\)\(U[x]\text{,}\)\(U(S)\text{,}\) dan \(U[S]\) disebut himpunan atas. Perhatikan bahwa jika \(A\) merupakan antirantai maksimal dalam \(\bfP\text{,}\) himpunan dasar \(X\) dapat dipartisi menjadi himpunan-himpunan yang saling lepas sebagai \(X=A\cup D(A)\cup U(A)\text{.}\)
Sekarang kita siap membuktikan teorema tersebut. Misalkan \(\PXP\) suatu poset dan misalkan \(w\) menyatakan lebar \(\bfP\text{.}\) Seperti dalam Teorema 6.18, Prinsip Sarang Merpati menyiratkan bahwa kita memerlukan sedikitnya \(w\) rantai dalam setiap partisi rantai dari \(\bfP\text{.}\) Untuk membuktikan bahwa \(w\) rantai mencukupi, kita menggunakan induksi pada \(|X|\text{;}\) hasilnya trivial jika \(|X|=1\text{.}\) Andaikan hasil tersebut berlaku bagi semua poset dengan \(|X|\le k\text{,}\) dan misalkan \(\PXP\) merupakan poset dengan \(|X|=k+1\text{.}\) Tanpa mengurangi keumuman, \(w>1\text{;}\) jika tidak, partisi trivial \(X=C_1\) memenuhi kesimpulan teorema. Selanjutnya, kita mengamati bahwa jika \(C\) merupakan rantai tak kosong dalam \((X,P)\text{,}\) kita boleh mengasumsikan bahwa subposet \((X-C,P(X-C))\) juga memiliki lebar \(w\text{.}\) Untuk melihatnya, perhatikan bahwa teorema berlaku bagi subposet tersebut. Jadi, jika \(\width(X-C,P(X-C))=w'\lt w\text{,}\) kita dapat mempartisi \(X-C\) sebagai \(X-C=C_1\cup
C_2\cup\dots\cup C_{w'}\text{,}\) sehingga \(X=C\cup C_1\cup\dots\cup C_{w'}\) merupakan partisi menjadi \(w'+1\) rantai. Karena \(w'\lt w\text{,}\) kita memiliki \(w'+1\le w\text{,}\) sehingga diperoleh partisi \(X\) menjadi paling banyak \(w\) rantai. Karena setiap partisi \(X\) menjadi rantai harus menggunakan sedikitnya \(w\) rantai, inilah partisi yang kita cari.
Pilih titik maksimal \(x\) dan titik minimal \(y\) dengan \(y\le x\) dalam \(P\text{.}\) Selanjutnya, misalkan \(C\) merupakan rantai yang hanya memuat titik \(x\) dan \(y\text{.}\) Perhatikan bahwa \(C\) memuat satu atau dua elemen, bergantung pada apakah \(x\) dan \(y\) berbeda.
Misalkan \(Y=X-C\) dan \(Q=P(Y)\text{,}\) serta misalkan \(A\) merupakan antirantai berukuran \(w\) dalam subposet \((Y,Q)\text{.}\) Dalam partisi \(X=A\cup D(A)\cup U(A)\text{,}\) fakta bahwa \(y\) merupakan titik minimal sedangkan \(A\) merupakan antirantai maksimal menyiratkan \(y\in D(A)\text{.}\) Demikian pula, \(x\in U(A)\text{.}\) Secara khusus, hal ini menunjukkan bahwa \(x\) dan \(y\) berbeda.
Labeli elemen-elemen \(A\) sebagai \(\{a_1,a_2,\dots,a_w\}\text{.}\) Perhatikan bahwa \(U[A]\ne X\) karena \(y\notin U[A]\text{,}\) dan \(D[A]\ne X\) karena \(x\notin D[A]\text{.}\) Oleh karena itu, kita dapat menerapkan hipotesis induksi masing-masing pada subposet \(\bfP\) yang ditentukan oleh \(D[A]\) dan \(U[A]\text{,}\) lalu mempartisi masing-masing dari kedua subposet tersebut menjadi \(w\) rantai:
Tanpa mengurangi keumuman, kita dapat mengasumsikan bahwa rantai-rantai tersebut telah dilabeli sedemikian sehingga \(a_i\in
C_i\cap D_i\) untuk setiap \(i=1,2,\dots,w\text{.}\) Hal ini menyiratkan bahwa
Dalam Gambar 6.21, kita menggambarkan Teorema Penutupan Rantai Dilworth bagi poset yang pertama kali diperkenalkan dalam Gambar 6.5. Titik-titik gelap membentuk antirantai berisi \(7\) elemen, sedangkan label-labelnya memberikan partisi menjadi \(7\) rantai.
Diagram Hasse poset 18 titik. Tujuh titik gelap membentuk antirantai, dan setiap titik diberi salah satu label 1 sampai 7. Titik-titik dengan label yang sama membentuk satu rantai, sehingga ketujuh label memberikan partisi poset menjadi tujuh rantai.
Alice yang selalu waspada memperhatikan bahwa pembuktian Teorema Dilworth di atas tampaknya tidak memberikan algoritma yang efisien untuk menemukan lebar \(w\) suatu poset, apalagi partisi poset tersebut menjadi \(w\) rantai. Bob masih belum memahami mengapa mendaftarkan semua subhimpunan \(X\) merupakan gagasan buruk. Carlos duduk tenang mendengarkan perdebatan mereka, tetapi akhirnya ia mengatakan bahwa pemrogram yang terampil dapat menyusun algoritma dari pembuktian tersebut. Anda dianjurkan untuk membahas dilema ini—namun tenanglah karena kita akan kembali membahas persoalan ini pada bagian selanjutnya dalam buku.
