Contoh 19.1.1.
Himpunan bilangan bulat (atau bilangan rasional maupun real) merupakan poset, dengan \(a \leq b\) memiliki makna lazim bagi dua bilangan bulat \(a\) dan \(b\) dalam \({\mathbb Z}\text{.}\)
Bagian 19.1 Latis
Subbagian 19.1.1 Himpunan Terurut Parsial
Kita memulai kajian latis dan aljabar Boolean dengan memperumum gagasan pertidaksamaan. Ingat bahwa relasi pada himpunan \(X\) merupakan himpunan bagian dari \(X \times X\text{.}\) Relasi \(P\) pada \(X\) disebut urutan parsial pada \(X\) jika memenuhi aksioma-aksioma berikut.
-
Relasi tersebut refleksif: \((a, a) \in P\) untuk setiap \(a \in X\text{.}\)
-
Relasi tersebut antisimetris: jika \((a,b) \in P\) dan \((b,a) \in P\text{,}\) maka \(a = b\text{.}\)
-
Relasi tersebut transitif: jika \((a, b) \in P\) dan \((b, c) \in P\text{,}\) maka \((a, c) \in P\text{.}\)
Biasanya kita menulis \(a \preceq b\) untuk menyatakan \((a, b) \in P\text{,}\) kecuali jika suatu lambang secara alami berkaitan dengan urutan parsial tertentu, seperti \(a \leq b\) untuk bilangan bulat \(a\) dan \(b\text{,}\) atau \(A \subset B\) untuk himpunan \(A\) dan \(B\text{.}\) Himpunan \(X\) bersama urutan parsial \(\preceq\) disebut himpunan terurut parsial, atau poset.
Contoh 19.1.2.
Misalkan \(X\) sebarang himpunan. Kita mendefinisikan himpunan kuasa dari \(X\) sebagai himpunan semua himpunan bagian dari \(X\text{.}\) Himpunan kuasa dari \(X\) dinotasikan dengan \({\mathcal P}(X)\text{.}\) Sebagai contoh, misalkan \(X = \{ a, b, c \}\text{.}\) Maka \({\mathcal P}(X)\) merupakan himpunan semua himpunan bagian dari \(\{ a, b, c \}\text{:}\)
\begin{align*}
& \emptyset & & \{ a \} & & \{ b \} & & \{ c \} &\\
& \{ a, b \} & & \{ a, c\} & &\{ b, c\} & & \{ a, b, c \}. &
\end{align*}
Pada himpunan kuasa dari sebarang himpunan \(X\text{,}\) inklusi himpunan, \(\subset\text{,}\) merupakan urutan parsial. Kita dapat merepresentasikan urutan pada \(\{ a, b, c \}\) secara skematis dengan diagram seperti pada Gambar 19.1.3.
Contoh 19.1.4.
Misalkan \(G\) suatu grup. Himpunan subgrup dari \(G\) merupakan poset, dengan inklusi himpunan sebagai urutan parsialnya.
Contoh 19.1.5.
Pada suatu himpunan tertentu dapat terdapat lebih dari satu urutan parsial. Kita dapat membentuk urutan parsial pada \({\mathbb N}\) dengan menetapkan \(a \preceq b\) jika \(a \mid b\text{.}\) Relasi ini jelas refleksif karena \(a \mid a\) untuk setiap \(a \in {\mathbb N}\text{.}\) Jika \(m \mid n\) dan \(n \mid m\text{,}\) maka \(m = n\text{;}\) jadi, relasi tersebut juga antisimetris. Relasi ini transitif, sebab jika \(m \mid n\) dan \(n \mid p\text{,}\) maka \(m \mid p\text{.}\)
Contoh 19.1.6.
Misalkan \(X = \{ 1, 2, 3, 4, 6, 8, 12, 24 \}\) adalah himpunan pembagi \(24\) dengan urutan parsial yang didefinisikan dalam Contoh 19.1.5. Gambar 19.1.7 memperlihatkan urutan parsial pada \(X\text{.}\)
Misalkan \(Y\) himpunan bagian dari poset \(X\text{.}\) Elemen \(u\) dalam \(X\) disebut batas atas dari \(Y\) jika \(a \preceq u\) untuk setiap elemen \(a \in Y\text{.}\) Jika \(u\) merupakan batas atas dari \(Y\) sedemikian sehingga \(u \preceq v\) untuk setiap batas atas lain \(v\) dari \(Y\text{,}\) maka \(u\) disebut batas atas terkecil atau supremum dari \(Y\text{.}\) Elemen \(l\) dalam \(X\) disebut batas bawah dari \(Y\) jika \(l \preceq a\) untuk setiap \(a \in Y\text{.}\) Jika \(l\) merupakan batas bawah dari \(Y\) sedemikian sehingga \(k \preceq l\) untuk setiap batas bawah lain \(k\) dari \(Y\text{,}\) maka \(l\) disebut batas bawah terbesar atau infimum dari \(Y\text{.}\)
Contoh 19.1.8.
Misalkan \(Y = \{ 2, 3, 4, 6 \}\) termuat dalam himpunan \(X\) pada Contoh 19.1.6. Maka \(Y\) memiliki batas atas \(12\) dan \(24\text{,}\) dengan \(12\) sebagai batas atas terkecil. Satu-satunya batas bawah adalah \(1\text{;}\) jadi, elemen ini harus menjadi batas bawah terbesar.
Ternyata, batas atas terkecil dan batas bawah terbesar bersifat tunggal jika ada.
Teorema 19.1.9.
Misalkan \(Y\) himpunan bagian tak kosong dari poset \(X\text{.}\) Jika \(Y\) memiliki batas atas terkecil, maka \(Y\) memiliki batas atas terkecil yang tunggal. Jika \(Y\) memiliki batas bawah terbesar, maka \(Y\) memiliki batas bawah terbesar yang tunggal.
Bukti.
Misalkan \(u_1\) dan \(u_2\) batas atas terkecil dari \(Y\text{.}\) Berdasarkan definisi batas atas terkecil, \(u_1 \preceq u\) untuk setiap batas atas \(u\) dari \(Y\text{.}\) Secara khusus, \(u_1 \preceq u_2\text{.}\) Serupa dengan itu, \(u_2 \preceq u_1\text{.}\) Oleh karena itu, \(u_1 = u_2\) berdasarkan antisimetri. Argumen serupa menunjukkan bahwa batas bawah terbesar bersifat tunggal.
Pada banyak poset, operasi biner dapat didefinisikan menggunakan batas bawah terbesar dan batas atas terkecil dari dua elemen. Latis adalah poset \(L\) sedemikian sehingga setiap pasangan elemen dalam \(L\) memiliki batas atas terkecil dan batas bawah terbesar. Batas atas terkecil dari \(a,
b \in L\) disebut gabung dari \(a\) dan \(b\text{,}\) serta dinotasikan dengan \(a \vee b\text{.}\) Batas bawah terbesar dari \(a,
b \in L\) disebut temu dari \(a\) dan \(b\text{,}\) serta dinotasikan dengan \(a \wedge b\text{.}\)
Contoh 19.1.10.
Misalkan \(X\) suatu himpunan. Maka himpunan kuasa dari \(X\text{,}\) yaitu \({\mathcal P}(X)\text{,}\) merupakan latis. Untuk dua himpunan \(A\) dan \(B\) dalam \({\mathcal P}(X)\text{,}\) batas atas terkecil dari \(A\) dan \(B\) adalah \(A \cup B\text{.}\) Tentu saja, \(A \cup B\) merupakan batas atas dari \(A\) dan \(B\text{,}\) sebab \(A \subset A \cup B\) dan \(B \subset A \cup B\text{.}\) Jika \(C\) adalah himpunan lain yang memuat \(A\) maupun \(B\text{,}\) maka \(C\) harus memuat \(A \cup B\text{;}\) jadi, \(A \cup B\) merupakan batas atas terkecil dari \(A\) dan \(B\text{.}\) Serupa dengan itu, batas bawah terbesar dari \(A\) dan \(B\) adalah \(A \cap B\text{.}\)
Contoh 19.1.11.
Misalkan \(G\) suatu grup dan andaikan \(X\) adalah himpunan subgrup dari \(G\text{.}\) Maka \(X\) merupakan poset yang diurutkan oleh inklusi himpunan, yaitu \(\subset\text{.}\) Himpunan subgrup dari \(G\) juga merupakan latis. Jika \(H\) dan \(K\) subgrup dari \(G\text{,}\) batas bawah terbesar dari \(H\) dan \(K\) adalah \(H \cap K\text{.}\) Himpunan \(H \cup K\) belum tentu merupakan subgrup dari \(G\text{.}\) Sebagai latihan, tunjukkan bahwa batas atas terkecil dari \(H\) dan \(K\) adalah subgrup yang dibangkitkan oleh \(H \cup K\text{.}\)
Dalam teori himpunan terdapat kondisi dualitas tertentu. Sebagai contoh, berdasarkan hukum De Morgan, setiap pernyataan tentang himpunan yang berlaku bagi \((A \cup B)'\) juga harus berlaku bagi \(A' \cap B'\text{.}\) Kita juga memiliki prinsip dualitas untuk latis.
Aksioma 19.1.12. Prinsip Dualitas.
Setiap pernyataan yang berlaku bagi semua latis tetap berlaku jika \(\preceq\) diganti dengan \(\succeq\text{,}\) serta \(\vee\) dan \(\wedge\) dipertukarkan di seluruh pernyataan.
Teorema berikut menyatakan bahwa latis merupakan struktur aljabar dengan dua operasi biner yang memenuhi aksioma tertentu.
Teorema 19.1.13.
Jika \(L\) suatu latis, maka operasi biner \(\vee\) dan \(\wedge\) memenuhi sifat-sifat berikut untuk \(a,
b, c \in L\text{.}\)
-
Hukum komutatif: \(a \vee b = b \vee a\) dan \(a \wedge b = b \wedge a\text{.}\)
-
Hukum asosiatif: \(a \vee ( b \vee c) = (a \vee b) \vee c\) dan \(a \wedge (b \wedge c) = (a \wedge b) \wedge c\text{.}\)
-
Hukum idempoten: \(a \vee a = a\) dan \(a \wedge a = a\text{.}\)
-
Hukum absorpsi: \(a \vee (a \wedge b) = a\) dan \(a \wedge ( a \vee b ) =a\text{.}\)
Bukti.
Berdasarkan Prinsip Dualitas, kita hanya perlu membuktikan pernyataan pertama pada setiap bagian.
(1) Berdasarkan definisi, \(a \vee b\) merupakan batas atas terkecil dari \(\{ a, b\}\text{,}\) dan \(b \vee a\) merupakan batas atas terkecil dari \(\{ b, a \}\text{;}\) padahal, \(\{ a, b\} = \{ b, a \}\text{.}\)
(2) Kita akan menunjukkan bahwa \(a \vee ( b \vee c)\) dan \((a \vee b) \vee c\) keduanya merupakan batas atas terkecil dari \(\{ a, b, c \}\text{.}\) Misalkan \(d = a \vee b\text{.}\) Maka \(c \preceq d \vee c = (a \vee b) \vee c\text{.}\) Kita juga mengetahui bahwa
\begin{equation*}
a \preceq a \vee b =d \preceq d \vee c = (a \vee b) \vee c\text{.}
\end{equation*}
Argumen serupa menunjukkan bahwa \(b \preceq (a \vee b) \vee c\text{.}\) Oleh karena itu, \((a \vee b) \vee c\) merupakan batas atas dari \(\{ a, b, c \}\text{.}\) Sekarang kita perlu menunjukkan bahwa \((a \vee b) \vee c\) merupakan batas atas terkecil dari \(\{ a, b, c\}\text{.}\) Misalkan \(u\) batas atas lain dari \(\{ a, b, c \}\text{.}\) Maka \(a \preceq u\) dan \(b \preceq u\text{;}\) jadi, \(d = a \vee b \preceq u\text{.}\) Karena \(c \preceq u\text{,}\) diperoleh \((a \vee b) \vee c = d \vee c \preceq u\text{.}\) Oleh karena itu, \((a \vee b) \vee c\) harus menjadi batas atas terkecil dari \(\{ a, b, c\}\text{.}\) Argumen yang menunjukkan bahwa \(a \vee ( b \vee c)\) merupakan batas atas terkecil dari \(\{ a, b, c \}\) sama saja. Akibatnya, \(a \vee ( b \vee c) = (a \vee b) \vee c\text{.}\)
(3) Gabung dari \(a\) dan \(a\) merupakan batas atas terkecil dari \(\{ a \}\text{;}\) jadi, \(a \vee a = a\text{.}\)
(4) Misalkan \(d = a \wedge b\text{.}\) Maka \(a \preceq a \vee d\text{.}\) Di sisi lain, \(d = a \wedge b \preceq a\text{,}\) sehingga \(a \vee d \preceq a\text{.}\) Oleh karena itu, \(a \vee ( a \wedge b) = a\text{.}\)
Diberikan sebarang himpunan \(L\) dengan operasi \(\vee\) dan \(\wedge\) yang memenuhi kondisi teorema sebelumnya, wajar untuk bertanya apakah himpunan ini berasal dari suatu latis. Teorema berikut menyatakan bahwa hal tersebut selalu berlaku.
Teorema 19.1.14.
Misalkan \(L\) himpunan tak kosong dengan dua operasi biner \(\vee\) dan \(\wedge\) yang memenuhi hukum komutatif, asosiatif, idempoten, dan absorpsi. Kita dapat mendefinisikan urutan parsial pada \(L\) dengan \(a \preceq b\) jika \(a \vee b = b\text{.}\) Lebih lanjut, \(L\) merupakan latis terhadap \(\preceq\) jika untuk setiap \(a,
b \in L\text{,}\) kita mendefinisikan batas atas terkecil dan batas bawah terbesar dari \(a\) dan \(b\) masing-masing sebagai \(a \vee b\) dan \(a \wedge b\text{.}\)
Bukti.
Pertama-tama kita menunjukkan bahwa \(L\) merupakan poset di bawah \(\preceq\text{.}\) Karena \(a \vee a = a\text{,}\) \(a \preceq a\) dan \(\preceq\) refleksif. Untuk menunjukkan bahwa \(\preceq\) antisimetris, misalkan \(a \preceq b\) dan \(b \preceq a\text{.}\) Maka \(a \vee b = b\) dan \(b \vee a = a\text{.}\) Berdasarkan hukum komutatif, \(b = a \vee b = b \vee a = a\text{.}\) Terakhir, kita harus menunjukkan bahwa \(\preceq\) transitif. Misalkan \(a \preceq b\) dan \(b \preceq c\text{.}\) Maka \(a \vee b = b\) dan \(b \vee c = c\text{.}\) Jadi,
\begin{equation*}
a \vee c = a \vee (b \vee c ) = ( a \vee b) \vee c = b \vee c = c\text{,}
\end{equation*}
atau \(a \preceq c\text{.}\)
Untuk menunjukkan bahwa \(L\) merupakan latis, kita harus membuktikan bahwa \(a \vee b\) dan \(a \wedge b\) masing-masing merupakan batas atas terkecil dan batas bawah terbesar dari \(a\) serta \(b\text{.}\) Karena \(a=(a \vee b) \wedge a = a \wedge (a \vee b)\text{,}\) diperoleh \(a \preceq a \vee b\text{.}\) Serupa dengan itu, \(b \preceq a \vee b\text{.}\) Oleh karena itu, \(a \vee b\) merupakan batas atas dari \(a\) dan \(b\text{.}\) Misalkan \(u\) sebarang batas atas lain dari \(a\) maupun \(b\text{.}\) Maka \(a \preceq u\) dan \(b \preceq u\text{.}\) Namun, \(a \vee b \preceq u\) karena
\begin{equation*}
(a \vee b) \vee u = a \vee (b \vee u) = a \vee u = u\text{.}
\end{equation*}
Pembuktian bahwa \(a \wedge b\) merupakan batas bawah terbesar dari \(a\) dan \(b\) diserahkan sebagai latihan.
