Bab 4: Relasi, Kelas Ekuivalensi, dan Urutan Parsial

Pasangan terurut memungkinkan kita menyatakan hubungan antara dua objek sebagai himpunan. Bab ini membangun bahasa relasi dari konstruksi tersebut, lalu menelaah dua bentuk hubungan: kesetaraan dan urutan. Kelas ekuivalensi memberi cara mengumpulkan objek yang setara tanpa memilih wakil secara sembarang. Urutan parsial menjelaskan ketergantungan tanpa memaksa semua objek dapat dibandingkan. Contoh kongruensi, keterbagian, dan penjadwalan memperlihatkan bagaimana definisi formal mengendalikan perhitungan dan gambar.

4.1 Definisi Formal Relasi Biner

Dalam matematika kita terus-menerus membicarakan hubungan antarobjek: $x$ lebih kecil daripada $y$, garis $\ell$ sejajar dengan garis $m$, bilangan $a$ membagi bilangan $b$. Setiap pernyataan seperti itu menyebut dua objek dalam peran yang berbeda. "$2<5$" benar, sedangkan "$5<2$" salah. Jadi urutan penyebutan membawa informasi.

Daftar anggota suatu himpunan tidak membawa urutan penyebutan. Menurut ekstensionalitas, $\{2,5\}=\{5,2\}$ karena kedua himpunan memiliki anggota yang sama. Karena itu kita tidak bisa sekadar menyimpan "pasangan $2$ dan $5$" sebagai himpunan $\{2,5\}$. Bila begitu, informasi tentang objek yang disebut lebih dulu akan hilang.

Unit ini menyelesaikan masalah tersebut dalam tiga langkah:

1. membangun pasangan terurut dari himpunan biasa dan membuktikan sifat yang membuatnya berguna;
2. membentuk produk Kartesius $A\times B$ sebagai himpunan yang keberadaannya dijamin aksioma;
3. mendefinisikan relasi sebagai himpunan bagian dari produk Kartesius, lalu mempelajari empat sifat dasar relasi pada satu himpunan.

Kita memakai hasil Bab 1–2 tentang kesamaan, implikasi, negasi, kuantifikator, dan kuantifikasi atas himpunan kosong. Dari Bab 3 kita memakai ekstensionalitas, aksioma pasangan, gabungan, himpunan kuasa, separasi, dan pembuktian kesamaan melalui dua inklusi. Bilangan bulat beserta urutan dan aritmetika elementernya hanya dipinjam sebagai sumber contoh. Konstruksinya baru dilakukan kemudian.

Pasangan terurut

Yang kita perlukan dari "pasangan terurut" hanyalah satu sifat: dua pasangan sama jika dan hanya jika komponen pertamanya sama dan komponen keduanya sama. Kita akan memilih satu kode konkret dalam bahasa himpunan, lalu membuktikan bahwa kode itu memiliki sifat tersebut.

Definisi 4.1.1 (pasangan terurut). Untuk objek $a$ dan $b$, didefinisikan

$$(a,b):=\{\{a\},\{a,b\}\}.$$

Objek $a$ disebut koordinat pertama dan $b$ koordinat kedua.

Keberadaannya dijamin aksioma pasangan yang dipakai tiga kali. Penerapan pertama membentuk $\{a,b\}$. Penerapan kedua membentuk $\{a\}=\{a,a\}$. Penerapan ketiga membentuk himpunan yang anggotanya tepat $\{a\}$ dan $\{a,b\}$. Menurut ekstensionalitas, himpunan itu tunggal.

Perlu dicatat kasus $a=b$. Dalam kasus ini $\{a,b\}=\{a\}$, sehingga

$$(a,a)=\{\{a\},\{a\}\}=\{\{a\}\}$$

hanya memiliki satu anggota. Kasus inilah yang membuat bukti keunikan koordinat memerlukan perhatian lebih.

Untuk himpunan tak kosong $\mathcal F$, tulis $\bigcap\mathcal F$ untuk himpunan semua $x$ yang menjadi anggota setiap anggota $\mathcal F$. Keberadaannya dijamin separasi: ambil sembarang $F_0\in\mathcal F$ dan bentuk $\{x\in F_0:\forall Y\in\mathcal F\;(x\in Y)\}$. Menurut ekstensionalitas, hasilnya tidak bergantung pada pilihan $F_0$. Tulis pula $\bigcup\mathcal F$ untuk gabungan yang dijamin aksioma gabungan.

Lema 4.1.2. Untuk setiap objek $a,b$ berlaku

$$\bigcap\,(a,b)=\{a\}\qquad\text{dan}\qquad\bigcup\,(a,b)=\{a,b\}.$$

Bukti. Himpunan $(a,b)$ tak kosong karena memuat $\{a\}$, sehingga $\bigcap(a,b)$ terdefinisi. Anggota $(a,b)$ tepat $\{a\}$ dan $\{a,b\}$. Untuk sembarang $x$:

$$x\in\bigcap(a,b)\iff\bigl(x\in\{a\}\ \land\ x\in\{a,b\}\bigr)\iff\bigl(x=a\ \land\ (x=a\lor x=b)\bigr)\iff x=a.$$

Langkah terakhir berlaku karena $x=a$ sudah menjamin disjungsi $x=a\lor x=b$. Jadi $\bigcap(a,b)=\{a\}$ menurut ekstensionalitas.

Untuk gabungan,

$$x\in\bigcup(a,b)\iff\bigl(x\in\{a\}\ \lor\ x\in\{a,b\}\bigr)\iff\bigl(x=a\ \lor\ x=a\ \lor\ x=b\bigr)\iff x\in\{a,b\}.$$

Jadi $\bigcup(a,b)=\{a,b\}$. Perhitungan ini tidak memisahkan kasus $a=b$ dan $a\ne b$, sehingga berlaku untuk keduanya. $\blacksquare$

Teorema 4.1.3 (sifat karakteristik pasangan terurut). Untuk setiap objek $a,b,c,d$,

$$(a,b)=(c,d)\iff\bigl(a=c\ \land\ b=d\bigr).$$

Bukti. ($\Leftarrow$) Jika $a=c$ dan $b=d$, substitusi pada ruas kanan Definisi 4.1.1 memberikan $\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$, yaitu $(a,b)=(c,d)$.

($\Rightarrow$) Misalkan $(a,b)=(c,d)$. Himpunan yang sama mempunyai irisan yang sama dan gabungan yang sama. Dengan Lema 4.1.2 diperoleh

$$\{a\}=\{c\}\qquad\text{dan}\qquad\{a,b\}=\{c,d\}.$$

Koordinat pertama. Karena $a\in\{a\}=\{c\}$, kita peroleh $a=c$. Akibatnya kesamaan kedua dapat ditulis ulang menjadi $\{a,b\}=\{a,d\}$.

Koordinat kedua. Kita pisahkan dua kasus yang mencakup semua kemungkinan.

• Kasus $b=a$. Maka $\{a,d\}=\{a,b\}=\{a\}$. Karena $d\in\{a,d\}$, diperoleh $d\in\{a\}$, jadi $d=a$. Dengan demikian $b=a=d$.
• Kasus $b\ne a$. Karena $b\in\{a,b\}=\{a,d\}$, berlaku $b=a$ atau $b=d$. Disjungsi pertama dikecualikan oleh hipotesis kasus, sehingga $b=d$.

Pada kedua kasus $b=d$. Bersama $a=c$, bukti selesai. $\blacksquare$

Catatan 4.1.4 (mengapa kasus $a=b$ tidak boleh dilewati). Ada argumen yang tampak wajar tetapi keliru: "$(a,b)$ dan $(c,d)$ masing-masing berisi satu himpunan bertitik tunggal dan satu himpunan bertitik dua; cocokkan yang bertitik tunggal dengan yang bertitik tunggal." Argumen ini runtuh tepat ketika $a=b$. Dalam kasus itu $(a,a)=\{\{a\}\}$ tidak memuat himpunan bertitik dua sama sekali. Bukti di atas menghindari masalah ini karena memakai irisan dan gabungan, yang dihitung seragam dalam Lema 4.1.2, lalu memisahkan kasus hanya pada langkah terakhir.

Catatan 4.1.5 (pasangan terurut bukan pasangan tak terurut). Dari Teorema 4.1.3, $(1,2)=(2,1)$ akan memaksa $1=2$. Jadi $(1,2)\ne(2,1)$, sedangkan $\{1,2\}=\{2,1\}$. Kode $\{\{a\},\{a,b\}\}$ hanyalah satu pilihan yang sah di dalam ZF. Setelah Teorema 4.1.3 terbukti, kita tidak akan lagi memakai rincian kode itu. Pernyataan seperti "$\{a\}\in(a,b)$" memang benar untuk kode ini, tetapi hanyalah artefak pilihan kode dan tidak akan dipakai dalam argumen.

Produk Kartesius

Kita ingin membentuk "himpunan semua pasangan $(a,b)$ dengan $a\in A$ dan $b\in B$". Komprehensi tanpa pembatas tidak diizinkan, jadi kita perlu sebuah himpunan yang sudah ada dan cukup besar untuk memuat semua pasangan tersebut. Himpunan itu disediakan oleh lema berikut.

Lema 4.1.6. Jika $a\in A$ dan $b\in B$, maka $(a,b)\in\mathcal P(\mathcal P(A\cup B))$.

Bukti. Karena $a\in A\subseteq A\cup B$, berlaku $\{a\}\subseteq A\cup B$. Karena $a,b\in A\cup B$, berlaku pula $\{a,b\}\subseteq A\cup B$. Jadi $\{a\}\in\mathcal P(A\cup B)$ dan $\{a,b\}\in\mathcal P(A\cup B)$. Kedua anggota $(a,b)$ berada di $\mathcal P(A\cup B)$, artinya $(a,b)\subseteq\mathcal P(A\cup B)$, sehingga $(a,b)\in\mathcal P(\mathcal P(A\cup B))$. $\blacksquare$

Definisi 4.1.7 (produk Kartesius). Untuk himpunan $A$ dan $B$, didefinisikan dengan separasi

$$A\times B:=\bigl\{p\in\mathcal P(\mathcal P(A\cup B)):\ \exists a\in A\ \exists b\in B\ \ (p=(a,b))\bigr\}.$$

Separasi diterapkan pada himpunan $\mathcal P(\mathcal P(A\cup B))$, yang keberadaannya dijamin aksioma gabungan dan himpunan kuasa. Jadi $A\times B$ memang himpunan dan tunggal menurut ekstensionalitas.

Proposisi 4.1.8 (keanggotaan produk).

1. $p\in A\times B$ jika dan hanya jika ada $a\in A$ dan $b\in B$ dengan $p=(a,b)$.
2. Untuk setiap objek $x,y$: $(x,y)\in A\times B$ jika dan hanya jika $x\in A$ dan $y\in B$.
3. Setiap $p\in A\times B$ mempunyai tepat satu koordinat pertama dan tepat satu koordinat kedua: jika $p=(a,b)=(a',b')$, maka $a=a'$ dan $b=b'$.

Bukti. (1) Arah ($\Rightarrow$) langsung dari syarat separasi. Untuk arah ($\Leftarrow$), jika $p=(a,b)$ dengan $a\in A$ dan $b\in B$, maka $p\in\mathcal P(\mathcal P(A\cup B))$ menurut Lema 4.1.6, dan $p$ memenuhi syarat separasi. Jadi $p\in A\times B$.

(2) Arah ($\Leftarrow$) adalah kasus khusus dari (1). Untuk arah ($\Rightarrow$), misalkan $(x,y)\in A\times B$. Menurut (1) ada $a\in A$ dan $b\in B$ dengan $(x,y)=(a,b)$. Teorema 4.1.3 memberikan $x=a$ dan $y=b$, sehingga $x\in A$ dan $y\in B$.

(3) Langsung dari Teorema 4.1.3. $\blacksquare$

Butir (2) tampak remeh, tetapi buktinya memerlukan Teorema 4.1.3. Tanpa keunikan koordinat, $(x,y)$ bisa saja sama dengan suatu $(a,b)$ yang koordinatnya berada di $A$ dan $B$, sementara $x$ sendiri tidak berada di $A$. Butir (3) membenarkan ungkapan "koordinat pertama dari $p$". Ungkapan ini akan dipakai di Bab 5 untuk mendefinisikan proyeksi, tetapi di sini cukup dicatat bahwa koordinat itu ada dan tunggal.

Proposisi 4.1.9. Untuk setiap himpunan $A$ dan $B$ berlaku $A\times\varnothing=\varnothing$ dan $\varnothing\times B=\varnothing$.

Bukti. Andaikan $p\in A\times\varnothing$. Menurut Proposisi 4.1.8(1), ada $b\in\varnothing$ dengan $p=(a,b)$ untuk suatu $a\in A$. Ini mustahil karena $\varnothing$ tidak beranggota. Jadi $A\times\varnothing$ tidak beranggota, dan menurut ekstensionalitas $A\times\varnothing=\varnothing$. Argumen untuk $\varnothing\times B$ sama, dengan peran koordinat pertama dan kedua dipertukarkan. $\blacksquare$

Contoh 4.1.10.

$$\{1,2\}\times\{3\}=\{(1,3),(2,3)\},\qquad\{3\}\times\{1,2\}=\{(3,1),(3,2)\}.$$

Kesamaan pertama dibuktikan dengan dua inklusi. Jika $p\in\{1,2\}\times\{3\}$, Proposisi 4.1.8(1) memberikan $p=(a,b)$ dengan $a\in\{1,2\}$ dan $b=3$, sehingga $p=(1,3)$ atau $p=(2,3)$. Sebaliknya, $(1,3)$ dan $(2,3)$ anggota produk menurut Proposisi 4.1.8(2). Kesamaan kedua dibuktikan dengan cara yang sama.

Kedua himpunan ini berbeda. Andaikan $(1,3)\in\{3\}\times\{1,2\}$. Proposisi 4.1.8(2) akan memberikan $1\in\{3\}$, yaitu $1=3$, dan ini salah. Jadi kesamaan $A\times B=B\times A$ tidak berlaku untuk semua $A,B$. Kesamaan itu tetap berlaku, misalnya, bila $A=B$ atau salah satunya kosong (Proposisi 4.1.9).

Relasi biner

Definisi 4.1.11 (relasi). Misalkan $A$ dan $B$ himpunan. Relasi dari $A$ ke $B$ adalah himpunan $R$ dengan $R\subseteq A\times B$. Untuk sembarang objek $x,y$ kita menulis

$$x\,R\,y\quad:\Longleftrightarrow\quad(x,y)\in R,$$

dan menulis $x\not\!R\,y$ bila $(x,y)\notin R$. Karena $R\subseteq A\times B$, Proposisi 4.1.8(2) menjamin bahwa $x\,R\,y$ hanya mungkin bila $x\in A$ dan $y\in B$. Relasi dari $A$ ke $A$ disebut relasi pada $A$.

Konvensi 4.1.12 (himpunan asal, kodomain, domain, jangkauan). Himpunan $R$ sendiri tidak menyimpan informasi tentang $A$ dan $B$. Contohnya, $\varnothing$ adalah relasi dari setiap $A$ ke setiap $B$. Karena itu, dalam buku ini frasa "$R$ relasi dari $A$ ke $B$" selalu menyertakan $A$ dan $B$ sebagai bagian dari pernyataan. $A$ disebut himpunan asal dan $B$ disebut kodomain. Dari ketiga data tersebut kita membentuk, dengan separasi,

$$\operatorname{dom}R:=\{x\in A:\exists y\in B\ (x\,R\,y)\},\qquad \operatorname{ran}R:=\{y\in B:\exists x\in A\ (x\,R\,y)\},$$

yang masing-masing disebut domain dan jangkauan relasi. Domain dapat merupakan himpunan bagian sejati dari himpunan asal, dan jangkauan dapat merupakan himpunan bagian sejati dari kodomain. Bab 5 akan menambahkan syarat khusus untuk fungsi. Di sini konvensi ini hanya mencegah kita mencampuradukkan "himpunan yang dideklarasikan" dengan "himpunan koordinat yang benar-benar muncul".

Contoh 4.1.13. Misalkan $A=\{1,2\}$, $B=\{5,6\}$, dan $H=\{(1,5)\}$ sebagai relasi dari $A$ ke $B$. Jika $x\,H\,y$, maka $(x,y)=(1,5)$, sehingga $x=1$ dan $y=5$ menurut Teorema 4.1.3. Jadi $\operatorname{dom}H=\{1\}$ dan $\operatorname{ran}H=\{5\}$. Karena $2\ne1$, berlaku $\{1\}\subsetneq A$; karena $6\ne5$, berlaku $\{5\}\subsetneq B$. Kodomainnya tetap $B$.

Ketergantungan pada himpunan yang dideklarasikan juga berlaku untuk sifat relasi. Ambil $J=\{(1,1),(2,2)\}$. Sebagai relasi pada $\{1,2\}$, relasi ini refleksif menurut Definisi 4.1.17 di bawah. Sebagai relasi pada $\{1,2,3\}$, relasi yang sama tidak refleksif karena $(3,3)\notin J$. Jadi pertanyaan "apakah $J$ refleksif?" tidak bermakna sebelum himpunan $A$ ditetapkan.

Contoh 4.1.14 (tiga relasi baku pada $A$).

• Relasi kosong $\varnothing\subseteq A\times A$. Untuk setiap $x,y$, pernyataan $x\,\varnothing\,y$ salah.
• Relasi penuh $A\times A$. Untuk setiap $x,y\in A$, pernyataan $x\,(A\times A)\,y$ benar.
• Diagonal $\Delta_A:=\{p\in A\times A:\exists a\in A\ (p=(a,a))\}$, dibentuk dengan separasi pada $A\times A$.

Proposisi 4.1.15. Untuk $x,y\in A$ berlaku $x\,\Delta_A\,y\iff x=y$.

Bukti. ($\Leftarrow$) Jika $x=y$, maka $(x,y)=(x,x)$ dengan $x\in A$. Pasangan ini anggota $A\times A$ dan memenuhi syarat separasi dengan saksi $a=x$. ($\Rightarrow$) Jika $(x,y)\in\Delta_A$, maka ada $a\in A$ dengan $(x,y)=(a,a)$. Teorema 4.1.3 memberikan $x=a$ dan $y=a$, sehingga $x=y$. $\blacksquare$

Jadi $\Delta_A$ adalah relasi kesamaan yang dibatasi pada $A$. Kita juga meminjam dari aritmetika urutan biasa $<$ dan $\le$ pada $\mathbb Z$ sebagai relasi pada $\mathbb Z$. Sifat-sifat yang dipakai ialah: $x\le x$; $x\not<x$; jika $x\le y$ dan $y\le x$ maka $x=y$; transitivitas $<$ dan $\le$; serta bahwa untuk $x,y\in\mathbb Z$ tidak mungkin $x<y$ dan $y<x$ sekaligus.

Catatan 4.1.16 (tabel dan digraf). Jika $A$ berhingga dan kecil, relasi pada $A$ dapat disajikan sebagai tabel atau sebagai digraf.

• Dalam tabel, baris $x$ dan kolom $y$ diberi tanda bila $x\,R\,y$.
• Dalam digraf, setiap anggota $A$ menjadi titik, dan dibuat panah dari $x$ ke $y$ bila $x\,R\,y$. Panah dari $x$ ke $x$ disebut loop.

Untuk relasi $R$ yang dibahas di bawah, tabelnya adalah

Penyajian ini berguna untuk melihat pola dan menemukan calon saksi, tetapi tidak menggantikan bukti, karena tiga alasan:

1. Tabel atau gambar berhingga yang menampilkan setiap anggota dan setiap pasangan hanya dapat memuat seluruh relasi pada himpunan berhingga. Relasi pada himpunan tak hingga dapat digambarkan secara skematis, tetapi gambar berhingga itu tidak memeriksa seluruh kasus. Klaim tentang relasi pada $\mathbb Z$, atau tentang semua relasi dengan sifat tertentu, memerlukan argumen umum.
2. Membaca gambar sebagai bukti berarti melakukan pemeriksaan kasus. Pemeriksaan itu sah hanya bila semua kasus yang dituntut kuantifikator benar-benar diperiksa. Transitivitas, misalnya, menuntut pemeriksaan semua rangkaian $x\,R\,y$, $y\,R\,z$, bukan hanya rangkaian yang "terlihat".
3. Gambar harus mencatat seluruh himpunan asal $A$ sebagai himpunan titik, termasuk titik tanpa panah. Jika titik semacam itu terlewat, gambar tidak lagi menyajikan seluruh data relasi pada $A$.

Karena itu, setiap klaim dalam unit ini tetap disertai argumen.

Empat sifat relasi pada satu himpunan

Definisi 4.1.17. Misalkan $R$ relasi pada $A$, yaitu $R\subseteq A\times A$. Relasi $R$ disebut

$$\begin{aligned} \textbf{refleksif}\ &\text{jika}\ \forall x\in A\ (x\,R\,x),\\ \textbf{simetris}\ &\text{jika}\ \forall x,y\in A\ (x\,R\,y\Rightarrow y\,R\,x),\\ \textbf{antisimetris}\ &\text{jika}\ \forall x,y\in A\ \bigl((x\,R\,y\land y\,R\,x)\Rightarrow x=y\bigr),\\ \textbf{transitif}\ &\text{jika}\ \forall x,y,z\in A\ \bigl((x\,R\,y\land y\,R\,z)\Rightarrow x\,R\,z\bigr). \end{aligned}$$

Untuk perbandingan, $R$ disebut irrefleksif jika $\forall x\in A\ (x\not\!R\,x)$, dan asimetris jika $\forall x,y\in A\ (x\,R\,y\Rightarrow y\not\!R\,x)$.

Membantah suatu sifat berarti membuktikan negasinya. Dengan aturan negasi kuantifikator dari Bab 2, negasi-negasi tersebut adalah sebagai berikut.

Bentuk saksi untuk transitivitas perlu diperhatikan. Kita harus menunjukkan tiga objek yang membuat kedua premis benar dan kesimpulan salah. Menunjukkan bahwa sebuah pasangan "tidak ada di $R$" belum cukup.

Setiap sifat dalam Definisi 4.1.17 berbentuk kuantifikasi universal atas anggota $A$. Tiga di antaranya, yaitu simetris, antisimetris, dan transitif, juga berbentuk implikasi dengan premis yang memuat $x\,R\,y$. Dua fakta dari Bab 2 akan sering dipakai:

• implikasi dengan premis salah bernilai benar;
• kuantifikasi universal atas himpunan kosong bernilai benar.

Proposisi 4.1.18 (kesamaan). Untuk setiap himpunan $A$, diagonal $\Delta_A$ refleksif, simetris, antisimetris, dan transitif.

Bukti. Gunakan Proposisi 4.1.15: untuk $x,y\in A$, $x\,\Delta_A\,y$ berarti $x=y$.

• Refleksif: $x=x$ untuk setiap $x\in A$.
• Simetris: dari $x=y$ diperoleh $y=x$.
• Antisimetris: premis $x=y\land y=x$ sudah memuat kesimpulan $x=y$.
• Transitif: dari $x=y$ dan $y=z$ diperoleh $x=z$ dengan substitusi. $\blacksquare$

Proposisi ini menunjukkan bahwa sebuah relasi bisa simetris dan antisimetris sekaligus. Kedua sifat itu bukan lawan satu sama lain. Hal ini dibahas lebih lanjut di bagian akhir.

Proposisi 4.1.19 (relasi kosong). Misalkan $A$ himpunan.

1. Relasi kosong pada $A$ bersifat simetris, antisimetris, transitif, irrefleksif, dan asimetris.
2. Relasi kosong pada $A$ refleksif jika dan hanya jika $A=\varnothing$.
3. Jika $A=\varnothing$, satu-satunya relasi pada $A$ adalah $\varnothing$, dan relasi itu memiliki keempat sifat dalam Definisi 4.1.17.

Bukti. (1) Untuk setiap $x,y\in A$, pernyataan $x\,\varnothing\,y$ salah. Pada sifat simetris, antisimetris, transitif, dan asimetris, premis setiap implikasi memuat suatu konjung berbentuk $x\,\varnothing\,y$. Premis itu salah, sehingga implikasinya benar untuk setiap pilihan $x,y,z$. Sifat-sifat ini berlaku secara vakum. Irrefleksivitas berlaku karena $x\,\varnothing\,x$ salah untuk setiap $x$.

(2) Jika $A\ne\varnothing$, ambil $a\in A$. Maka $(a,a)\notin\varnothing$, sehingga $a$ menjadi saksi kegagalan refleksivitas. Jika $A=\varnothing$, pernyataan $\forall x\in\varnothing\ (x\,\varnothing\,x)$ benar secara vakum.

(3) Menurut Proposisi 4.1.9, $\varnothing\times\varnothing=\varnothing$. Jadi relasi $R$ pada $\varnothing$ memenuhi $R\subseteq\varnothing$, yang berarti $R=\varnothing$. Sifat simetris, antisimetris, dan transitif berlaku menurut (1), dan refleksif berlaku menurut (2). $\blacksquare$

Butir (2) dan (3) membantah anggapan bahwa "refleksif berarti relasinya memuat sesuatu". Refleksivitas hanya menuntut $x\,R\,x$ untuk setiap $x$ yang ada di $A$. Pada $A=\varnothing$, tuntutan itu kosong. Relasi pada $\varnothing$ juga sekaligus refleksif dan irrefleksif. Hal ini tidak kontradiktif, karena kedua klaim universal itu benar secara vakum.

Proposisi 4.1.20 (relasi penuh). Relasi $A\times A$ refleksif, simetris, dan transitif. Relasi ini antisimetris jika dan hanya jika $\forall x,y\in A\ (x=y)$, yaitu jika $A$ memiliki paling banyak satu anggota.

Bukti. Setiap pernyataan $x\,(A\times A)\,y$ dengan $x,y\in A$ benar menurut Proposisi 4.1.8(2). Akibatnya kesimpulan pada definisi refleksif, simetris, dan transitif selalu benar.

Untuk antisimetri, misalkan $\forall x,y\in A\ (x=y)$. Maka kesimpulan $x=y$ pada definisi antisimetri selalu benar. Sebaliknya, jika ada $a,b\in A$ dengan $a\ne b$, maka $a\,(A\times A)\,b$ dan $b\,(A\times A)\,a$ benar. Jadi $a,b$ menjadi saksi kegagalan antisimetri. $\blacksquare$

Contoh 4.1.21 (urutan pada $\mathbb Z$). Contoh berikut memakai fakta urutan yang dipinjam.

• Relasi $\le$ refleksif, antisimetris, dan transitif. Relasi ini tidak simetris dengan saksi $0\le1$ tetapi $1\not\le0$.
• Relasi $<$ irrefleksif, transitif, dan asimetris. Asimetri berlaku karena $x<y$ dan $y<x$ tidak dapat terjadi bersamaan. Relasi ini juga antisimetris secara vakum: premis $x<y\land y<x$ tidak pernah benar. Relasi ini tidak refleksif dengan saksi $0\not<0$, dan tidak simetris dengan saksi $0<1$ tetapi $1\not<0$.

Contoh pokok: relasi yang transitif melalui dua blok

Tetapkan $A=\{1,2,3\}$ dan

$$R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}.$$

Ada klaim yang keliru dan mudah muncul tentang relasi ini: "$R$ tidak transitif, karena gabungan pasangan $(1,2)$ dan $(2,1)$, atau rangkaian lebih lanjut darinya, akan menghasilkan sesuatu di luar $R$." Klaim ini salah. Dua bukti berikut menunjukkan bahwa $R$ transitif. Bukti pertama memeriksa semua kasus. Bukti kedua memperlihatkan struktur yang menjelaskan mengapa transitivitas berlaku.

Proposisi 4.1.22. Relasi $R$ pada $A=\{1,2,3\}$ bersifat refleksif, simetris, dan transitif, tetapi tidak antisimetris.

Bukti. Refleksif. Pasangan $(1,1),(2,2),(3,3)$ semuanya anggota $R$.

Simetris. Pasangan dengan koordinat sama adalah kebalikan dirinya sendiri. Dua pasangan lainnya, $(1,2)$ dan $(2,1)$, saling berkebalikan dan keduanya anggota $R$. Jadi untuk setiap $(x,y)\in R$, kebalikannya $(y,x)$ juga anggota $R$.

Tidak antisimetris. Saksinya $x=1$ dan $y=2$: berlaku $1\,R\,2$, $2\,R\,1$, dan $1\ne2$.

Transitif, bukti pertama: pemeriksaan semua rangkaian. Kita harus memeriksa setiap tripel $(x,y,z)$ dengan $(x,y)\in R$ dan $(y,z)\in R$. Untuk tiap $(x,y)\in R$, daftarkan semua pasangan di $R$ yang koordinat pertamanya $y$. Pasangan berkoordinat pertama $1$ adalah $(1,1),(1,2)$. Berkoordinat pertama $2$ adalah $(2,2),(2,1)$. Berkoordinat pertama $3$ hanya $(3,3)$.

Tabel ini memuat kesembilan rangkaian yang mungkin, dan setiap kesimpulannya berada di $R$. Rangkaian yang tampak "berbahaya", yaitu $1\,R\,2$ lalu $2\,R\,1$, hanya menghasilkan $(1,1)$. Pasangan ini sudah ada di $R$. Tidak ada rangkaian yang menghubungkan $\{1,2\}$ dengan $3$, karena tidak ada pasangan di $R$ yang memuat $3$ bersama $1$ atau $2$.

Transitif, bukti kedua: dua blok. Tulis $C=\{1,2\}$ dan $D=\{3\}$. Kita perlu dua fakta.

Fakta pertama: $R=(C\times C)\cup(D\times D)$. Dengan Proposisi 4.1.8, $C\times C=\{(1,1),(1,2),(2,1),(2,2)\}$ dan $D\times D=\{(3,3)\}$. Setiap anggota $R$ muncul di salah satu daftar ini, dan setiap anggota kedua daftar ini muncul di $R$. Jadi kedua inklusi berlaku.

Fakta kedua: $C\cap D=\varnothing$, karena $3\ne1$ dan $3\ne2$.

Sekarang misalkan $x\,R\,y$ dan $y\,R\,z$. Ada blok $K\in\{C,D\}$ dengan $(x,y)\in K\times K$, dan ada blok $L\in\{C,D\}$ dengan $(y,z)\in L\times L$. Maka $y\in K$ dan $y\in L$, sehingga $y\in K\cap L$. Andaikan $K\ne L$. Maka $\{K,L\}=\{C,D\}$, sehingga $K\cap L=C\cap D=\varnothing$, dan ini bertentangan dengan $y\in K\cap L$. Jadi $K=L$. Akibatnya $x\in K$ dan $z\in L=K$, sehingga $(x,z)\in K\times K\subseteq R$. $\blacksquare$

Bukti kedua tidak memakai daftar rangkaian sama sekali. Yang dipakai hanyalah fakta bahwa $R$ merupakan gabungan "persegi" $K\times K$ atas blok-blok yang saling lepas. Satu-satunya cara rangkaian $x\,R\,y\,R\,z$ dapat berpindah blok adalah melalui anggota bersama $y$. Karena blok-bloknya saling lepas, perpindahan seperti itu mustahil. Argumen ini berlaku untuk banyak relasi lain, dan polanya akan menjadi pusat pembahasan 4.2.

Contoh 4.1.23 (relasi refleksif dan simetris yang sungguh tidak transitif). Pada $A=\{1,2,3\}$ yang sama, definisikan

$$T=R\cup\{(2,3),(3,2)\}=\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}.$$

• Refleksif: $T\supseteq R$, dan $R$ memuat ketiga pasangan diagonal.
• Simetris: pasangan diagonal adalah kebalikan dirinya sendiri. Pasangan selain diagonal muncul berpasangan dengan kebalikannya: $(1,2)$ dengan $(2,1)$, dan $(2,3)$ dengan $(3,2)$.
• Tidak transitif: saksinya $x=1$, $y=2$, $z=3$. Kedua premis $1\,T\,2$ dan $2\,T\,3$ benar, tetapi $(1,3)\notin T$.
• Tidak antisimetris: saksi yang sama dengan saksi untuk $R$.

Mengapa argumen dua blok gagal untuk $T$? Andaikan $T$ ditulis sebagai gabungan persegi $K\times K$ atas blok-blok yang saling lepas. Karena $(1,2)\in T$, ada blok yang memuat $1$ dan $2$. Karena $(2,3)\in T$, ada blok yang memuat $2$ dan $3$. Kedua blok itu sama-sama memuat $2$, sehingga keduanya blok yang sama. Akibatnya $(1,3)$ berada di persegi blok itu, sehingga $(1,3)\in T$, padahal kenyataannya tidak. Jadi $T$ tidak berbentuk seperti itu.

Yang berlaku justru

$$T=(\{1,2\}\times\{1,2\})\cup(\{2,3\}\times\{2,3\}).$$

Kedua inklusi diperiksa dengan mendaftar: persegi pertama memuat $(1,1),(1,2),(2,1),(2,2)$, persegi kedua memuat $(2,2),(2,3),(3,2),(3,3)$, dan gabungan kedua daftar tepat ketujuh anggota $T$. Kedua blok $\{1,2\}$ dan $\{2,3\}$ menutupi $A$ tetapi tumpang tindih di $2$, dan di titik itulah transitivitas gagal (bandingkan Latihan 4.1.L7(b)).

Ringkasan sifat pada $A=\{1,2,3\}$. Kolom terakhir memuat relasi $L=\{(1,2),(1,3),(2,3)\}$, yaitu $<$ yang dibatasi pada $A$. Pembenarannya dikerjakan di Latihan 4.1.L4.

Pembenaran setiap entri:

• Kolom $\Delta_A$, $\varnothing$, dan $A\times A$ mengikuti Proposisi 4.1.18–4.1.20. Asimetri gagal pada $\Delta_A$: premis asimetri benar untuk $x=y=1$ karena $1\,\Delta_A\,1$, tetapi kesimpulan $1\not\!\Delta_A\,1$ salah. Asimetri gagal pada $A\times A$ dengan saksi yang sama, karena $1\,(A\times A)\,1$.
• Kolom $R$ dan $T$ mengikuti Proposisi 4.1.22 dan Contoh 4.1.23. Asimetri gagal pada keduanya dengan saksi $x=y=1$, karena $1\,R\,1$ dan $1\,T\,1$.

Antisimetris, tidak simetris, dan asimetris

Tiga istilah ini sering tertukar karena namanya mirip. Isi logisnya berbeda.

• Tidak simetris hanyalah negasi dari simetris: ada satu pasangan $x\,R\,y$ yang kebalikannya tidak berlaku.
• Antisimetris adalah syarat universal: hubungan dua arah hanya boleh terjadi antara objek yang sama.
• Asimetris adalah syarat universal yang lebih kuat: hubungan dua arah tidak boleh terjadi sama sekali, termasuk dari suatu objek ke dirinya sendiri.

Hubungan antara ketiganya dirumuskan dalam proposisi berikut.

Proposisi 4.1.24. Misalkan $R$ relasi pada $A$.

1. $R$ asimetris jika dan hanya jika $R$ antisimetris dan irrefleksif.
2. $R$ simetris dan antisimetris jika dan hanya jika $R\subseteq\Delta_A$.

Bukti. (1) Untuk arah ($\Rightarrow$), misalkan $R$ asimetris.

• Irrefleksif: ambil $x\in A$ dan andaikan $x\,R\,x$. Asimetri dengan $y=x$ memberikan $x\not\!R\,x$, sebuah kontradiksi. Jadi $x\not\!R\,x$.
• Antisimetris: premis $x\,R\,y\land y\,R\,x$ tidak pernah benar, sebab $x\,R\,y$ memaksa $y\not\!R\,x$. Implikasinya benar secara vakum.

Untuk arah ($\Leftarrow$), misalkan $R$ antisimetris dan irrefleksif, dan misalkan $x\,R\,y$. Andaikan $y\,R\,x$. Antisimetri memberikan $x=y$, sehingga $x\,R\,x$, dan ini bertentangan dengan irrefleksivitas. Jadi $y\not\!R\,x$.

(2) Untuk arah ($\Rightarrow$), misalkan $R$ simetris dan antisimetris. Ambil $p\in R\subseteq A\times A$. Menurut Proposisi 4.1.8(1), $p=(x,y)$ untuk suatu $x,y\in A$. Simetri memberikan $y\,R\,x$, lalu antisimetri memberikan $x=y$. Jadi $p=(x,x)\in\Delta_A$ menurut Proposisi 4.1.15.

Untuk arah ($\Leftarrow$), misalkan $R\subseteq\Delta_A$. Jika $x\,R\,y$, maka $x=y$ menurut Proposisi 4.1.15. Akibatnya:

• Antisimetri: kesimpulan $x=y$ sudah diperoleh dari premis $x\,R\,y$ saja.
• Simetri: $(y,x)=(x,y)\in R$ dengan substitusi, sehingga $y\,R\,x$. $\blacksquare$

Contoh 4.1.25 (keempat kombinasi simetri dan antisimetri). Tulis $S=\{(1,2)\}$ sebagai relasi pada $\{1,2\}$ dan $U=\{(1,2),(2,1),(1,3)\}$ sebagai relasi pada $\{1,2,3\}$.

Pembenaran setiap sel:

• Sel kiri atas mengikuti Proposisi 4.1.24(2), karena kedua relasi termuat dalam diagonal.
• Sel kanan atas mengikuti Proposisi 4.1.20.
• Untuk $S$: relasi ini tidak simetris karena $1\,S\,2$ tetapi $2\not\!S\,1$. Relasi ini antisimetris karena premisnya tidak pernah benar. Jika $x\,S\,y$ dan $y\,S\,x$, maka $(x,y)=(1,2)$ dan $(y,x)=(1,2)$. Teorema 4.1.3 memberi $y=2$ dari kesamaan pertama dan $y=1$ dari kesamaan kedua, sehingga $1=2$, mustahil.
• Untuk $U$: tidak simetris karena $1\,U\,3$ tetapi $3\not\!U\,1$. Tidak antisimetris karena $1\,U\,2$, $2\,U\,1$, dan $1\ne2$.

Sel kanan bawah memakai tiga titik karena alasan berikut. Pada himpunan dua titik $\{1,2\}$, kegagalan antisimetri memaksa $(1,2)$ dan $(2,1)$ keduanya ada di relasi. Akibatnya semua pasangan yang mungkin, yaitu dua pasangan itu dan pasangan diagonal, sudah memiliki kebalikan di relasi, sehingga relasi itu simetris. Latihan 4.1.L6 meminta pembuktian rinci fakta ini.

Jadi "antisimetris" tidak berarti "tidak simetris", dan "tidak simetris" tidak berarti "antisimetris". Implikasi "antisimetris $\Rightarrow$ tidak simetris" dibantah oleh sel kiri atas ($\Delta_{\{1,2\}}$ antisimetris sekaligus simetris), dan implikasi "tidak simetris $\Rightarrow$ antisimetris" dibantah oleh sel kanan bawah ($U$).

Di antara sifat-sifat ini, asimetris mengimplikasikan antisimetris dan irrefleksif (Proposisi 4.1.24(1)), tetapi kebalikan implikasi pertama gagal pada $\Delta_A$ untuk setiap $A\ne\varnothing$. Asimetris juga mengimplikasikan "tidak simetris" hanya bila $R\ne\varnothing$. Memang, jika $R$ asimetris dan ada $x\,R\,y$, simetri akan memberi $y\,R\,x$ sedangkan asimetri memberi $y\not\!R\,x$; jadi $x,y$ menjadi saksi bahwa $R$ tidak simetris. Sebaliknya, relasi kosong bersifat asimetris dan simetris sekaligus secara vakum (Proposisi 4.1.19). Jadi asimetri pun bukan negasi simetri.

Latihan

Latihan 4.1.L1. (a) Buktikan bahwa $(a,b)=(b,a)$ jika dan hanya jika $a=b$. (b) Tentukan $\bigcap(2,2)$ dan $\bigcup(2,2)$, lalu periksa kecocokannya dengan Lema 4.1.2.

Latihan 4.1.L2. Buktikan bahwa $A\times B=\varnothing$ jika dan hanya jika $A=\varnothing$ atau $B=\varnothing$.

Latihan 4.1.L3 (relasi kosong dan kesamaan). (a) Daftarkan semua relasi pada $A=\{1\}$, lalu tentukan untuk masing-masing apakah relasi itu refleksif, simetris, antisimetris, transitif, dan asimetris. (b) Untuk $A=\varnothing$, apakah relasi kosong sama dengan $\Delta_A$? Jelaskan. (c) Buktikan bahwa jika $A\ne\varnothing$, maka $\Delta_A$ tidak asimetris.

Latihan 4.1.L4. Pada $A=\{1,2,3\}$, selidiki sifat refleksif, irrefleksif, simetris, antisimetris, asimetris, dan transitif untuk

$$L=\{(1,2),(1,3),(2,3)\}\qquad\text{dan}\qquad M=\{(1,1),(1,2),(2,3)\}.$$

Untuk transitivitas, periksa semua rangkaian.

Latihan 4.1.L5. Pada $\mathbb Z$ definisikan $x\,Q\,y$ jika $x\le y+1$. Tentukan apakah $Q$ refleksif, simetris, antisimetris, dan transitif. Berikan bukti atau saksi.

Latihan 4.1.L6. Buktikan bahwa setiap relasi pada $\{1,2\}$ yang tidak antisimetris pasti simetris.

Latihan 4.1.L7 (dua blok secara umum). Misalkan $C,D\subseteq A$ dengan $C\cap D=\varnothing$ dan $C\cup D=A$. Didefinisikan $E=(C\times C)\cup(D\times D)$. (a) Buktikan bahwa $E$ refleksif, simetris, dan transitif pada $A$. (b) Tunjukkan bahwa tanpa syarat $C\cap D=\varnothing$, transitivitas dapat gagal. (c) Tunjukkan bahwa tanpa syarat $C\cup D=A$, refleksivitas dapat gagal.

Pembahasan

4.1.L1. (a) Menurut Teorema 4.1.3, $(a,b)=(b,a)$ jika dan hanya jika $a=b$ dan $b=a$. Konjungsi ini setara dengan $a=b$.

(b) $(2,2)=\{\{2\},\{2\}\}=\{\{2\}\}$, sehingga himpunan ini hanya beranggota $\{2\}$. Maka $\bigcap(2,2)=\{2\}$ dan $\bigcup(2,2)=\{2\}$. Lema 4.1.2 memberikan $\{a\}=\{2\}$ dan $\{a,b\}=\{2,2\}=\{2\}$, jadi hasilnya cocok. Contoh ini memperlihatkan bahwa lema tetap berlaku ketika pasangan "runtuh" menjadi himpunan beranggota satu.

4.1.L2. ($\Leftarrow$) Ini adalah Proposisi 4.1.9. ($\Rightarrow$) Kita buktikan kontraposisinya. Misalkan $A\ne\varnothing$ dan $B\ne\varnothing$. Ambil $a\in A$ dan $b\in B$. Menurut Proposisi 4.1.8(2), $(a,b)\in A\times B$, sehingga $A\times B\ne\varnothing$.

Perhatikan bahwa pengambilan $a$ dan $b$ di sini hanyalah eliminasi dua kuantor eksistensial, masing-masing satu kali. Tidak ada pemilihan tak hingga yang diperlukan.

4.1.L3. (a) Karena $\{1\}\times\{1\}=\{(1,1)\}$, relasi pada $\{1\}$ adalah himpunan bagian dari $\{(1,1)\}$. Jadi hanya ada dua relasi: $\varnothing$ dan $E_1=\{(1,1)\}$.

• Relasi $\varnothing$. Menurut Proposisi 4.1.19, relasi ini tidak refleksif (saksinya $1$) serta simetris, antisimetris, transitif, dan asimetris.
• Relasi $E_1=\Delta_{\{1\}}$. Menurut Proposisi 4.1.18, relasi ini refleksif, simetris, antisimetris, dan transitif. Relasi ini tidak asimetris, karena $1\,E_1\,1$ membuat premis asimetri benar untuk $x=y=1$, tetapi kesimpulan $1\not\!E_1\,1$ salah.

(b) Ya. $\Delta_\varnothing\subseteq\varnothing\times\varnothing=\varnothing$, sehingga $\Delta_\varnothing=\varnothing$. Pada himpunan kosong, relasi kesamaan dan relasi kosong adalah objek yang sama. Hal ini konsisten dengan Proposisi 4.1.19(3).

(c) Ambil $a\in A$. Maka $a\,\Delta_A\,a$. Asimetri dengan $x=y=a$ akan menuntut $a\not\!\Delta_A\,a$, padahal itu salah. Jadi $a$ menjadi saksi bahwa $\Delta_A$ tidak asimetris.

4.1.L4. Relasi $L$.

• Tidak refleksif: $(1,1)\notin L$.
• Irrefleksif: tidak ada pasangan diagonal di $L$.
• Tidak simetris: $1\,L\,2$ tetapi $(2,1)\notin L$.
• Asimetris: kebalikan setiap anggota $L$, yaitu $(2,1)$, $(3,1)$, dan $(3,2)$, tidak ada di $L$.
• Antisimetris: mengikuti dari asimetri menurut Proposisi 4.1.24(1).
• Transitif: rangkaian yang mungkin hanya yang pasangan keduanya berkoordinat pertama sama dengan koordinat kedua pasangan pertama. Untuk $(1,2)$, pasangan di $L$ yang berawal $2$ hanya $(2,3)$, sehingga kesimpulannya $(1,3)\in L$. Untuk $(1,3)$ dan $(2,3)$, tidak ada pasangan di $L$ yang berawal $3$. Jadi hanya ada satu rangkaian, dan kesimpulannya berada di $L$.

Relasi $M$.

• Tidak refleksif: $(2,2)\notin M$.
• Tidak irrefleksif: $1\,M\,1$.
• Tidak simetris: $1\,M\,2$ tetapi $(2,1)\notin M$.
• Antisimetris: satu-satunya pasangan $(x,y)\in M$ yang kebalikannya juga di $M$ adalah $(1,1)$, dan untuk pasangan itu $x=y$. Kebalikan $(1,2)$ dan $(2,3)$ tidak ada di $M$.
• Tidak asimetris: $1\,M\,1$ membuat premis asimetri benar untuk $x=y=1$, sedangkan kesimpulannya salah.
• Tidak transitif: saksinya $x=1$, $y=2$, $z=3$. Premis $1\,M\,2$ dan $2\,M\,3$ benar, tetapi $(1,3)\notin M$. Satu saksi sudah cukup untuk membantah transitivitas, tetapi pemeriksaan lengkap memberi gambaran utuh. Rangkaian lainnya, yaitu $(1,1)$ lalu $(1,1)$ dan $(1,1)$ lalu $(1,2)$, menghasilkan $(1,1)$ dan $(1,2)$, keduanya di $M$. Tidak ada pasangan di $M$ yang berawal $3$, sehingga $(2,3)$ tidak memulai rangkaian. Jadi dari tiga rangkaian, hanya $(1,2),(2,3)$ yang gagal.

4.1.L5.

• Refleksif: $x\le x+1$ untuk setiap $x\in\mathbb Z$.
• Tidak simetris: $0\,Q\,5$ karena $0\le6$, tetapi $5\,Q\,0$ salah karena $5\le1$ salah.
• Tidak antisimetris: $0\,Q\,1$ karena $0\le2$, dan $1\,Q\,0$ karena $1\le1$, tetapi $0\ne1$.
• Tidak transitif: $2\,Q\,1$ karena $2\le2$, dan $1\,Q\,0$ karena $1\le1$, tetapi $2\,Q\,0$ salah karena $2\le1$ salah.

Relasi ini menunjukkan bahwa sedikit "kelonggaran" pada $\le$ merusak antisimetri dan transitivitas, walaupun refleksivitasnya tetap terjaga.

4.1.L6. Misalkan $V$ relasi pada $\{1,2\}$ yang tidak antisimetris. Maka ada $x,y\in\{1,2\}$ dengan $x\,V\,y$, $y\,V\,x$, dan $x\ne y$. Karena hanya ada dua anggota, $\{x,y\}=\{1,2\}$, sehingga $(1,2)\in V$ dan $(2,1)\in V$.

Sekarang buktikan simetri. Ambil $(u,v)\in V$. Karena $u,v\in\{1,2\}$, pasangan $(u,v)$ adalah salah satu dari $(1,1),(2,2),(1,2),(2,1)$:

• Jika $u=v$ (pasangan $(1,1)$ atau $(2,2)$), maka $(v,u)=(u,v)\in V$.
• Jika $(u,v)=(1,2)$, maka $(v,u)=(2,1)\in V$.
• Jika $(u,v)=(2,1)$, maka $(v,u)=(1,2)\in V$.

Keempat kemungkinan sudah tercakup, jadi $V$ simetris.

4.1.L7. (a) Bagian ini dikerjakan per sifat.

• Refleksif: ambil $x\in A=C\cup D$. Jika $x\in C$, maka $(x,x)\in C\times C$. Jika $x\in D$, maka $(x,x)\in D\times D$. Pada kedua kasus $(x,x)\in E$.
• Simetris: jika $(x,y)\in K\times K$ dengan $K\in\{C,D\}$, maka $x,y\in K$, sehingga $(y,x)\in K\times K\subseteq E$.
• Transitif: argumennya sama persis dengan bukti kedua Proposisi 4.1.22. Blok $K$ yang memuat $x,y$ dan blok $L$ yang memuat $y,z$ beririsan di $y$. Karena $C\cap D=\varnothing$, haruslah $K=L$, sehingga $(x,z)\in K\times K\subseteq E$.

Perhatikan kasus batas. Jika $C=\varnothing$, maka $C\times C=\varnothing$ dan $E=D\times D=A\times A$, sehingga argumen tetap berlaku. Jika $A=\varnothing$, maka $C=D=\varnothing$ dan $E=\varnothing$, yang memiliki ketiga sifat menurut Proposisi 4.1.19.

(b) Ambil $A=\{1,2,3\}$, $C=\{1,2\}$, dan $D=\{2,3\}$. Maka $C\cup D=A$ tetapi $C\cap D=\{2\}$. Gabungan $(C\times C)\cup(D\times D)$ tepat sama dengan relasi $T$ pada Contoh 4.1.23, yang tidak transitif dengan saksi $1,2,3$.

(c) Ambil $A=\{1,2,3\}$, $C=\{1,2\}$, dan $D=\varnothing$. Maka $C\cap D=\varnothing$, tetapi $C\cup D=\{1,2\}\ne A$. Di sini $E=\{(1,1),(1,2),(2,1),(2,2)\}$ dan $(3,3)\notin E$, sehingga refleksivitas pada $A$ gagal dengan saksi $3$. Hasil ini sejalan dengan Konvensi 4.1.12: sifat refleksif bergantung pada himpunan $A$ yang dideklarasikan.

Menuju 4.2

Contoh $R$ dan $T$ memperlihatkan perbedaan yang menentukan. Relasi $R$ refleksif, simetris, dan transitif, dan ia tersusun dari dua blok $\{1,2\}$ dan $\{3\}$ yang saling lepas serta menutupi seluruh $A$. Relasi $T$ refleksif dan simetris, tetapi blok-bloknya $\{1,2\}$ dan $\{2,3\}$ tumpang tindih, dan transitivitasnya gagal tepat di titik tumpang tindih itu.

Latihan 4.1.L7 menunjukkan satu arah hubungan ini untuk dua blok. Unit 4.2 menjadikan hubungan ini hasil umum. Relasi yang refleksif, simetris, dan transitif disebut relasi ekuivalensi. Kita akan membuktikan bahwa relasi ekuivalensi pada $A$ berkorespondensi dengan cara membagi $A$ menjadi blok-blok tak kosong yang saling lepas, termasuk dalam kasus $A=\varnothing$. Kita juga akan membuktikan bahwa kedua konstruksi tersebut saling membalik.

Untuk penyajian pembanding definisi relasi dan sifat-sifat dasarnya, lihat [R4-2].

4.2 Relasi Ekuivalensi dan Partisi Himpunan

Di 4.1 kita memeriksa relasi

$$R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$$

pada $A=\{1,2,3\}$. Relasi itu dapat ditulis sebagai $R=(C\times C)\cup(D\times D)$ dengan $C=\{1,2\}$ dan $D=\{3\}$. Jadi $R$ tidak lain adalah relasi "berada dalam kelompok yang sama", dengan kelompok $C$ dan $D$. Unit ini menunjukkan bahwa bentuk itu bukan kebetulan. Setiap relasi yang refleksif, simetris, dan transitif membagi himpunannya menjadi kelompok yang saling lepas. Sebaliknya, setiap pembagian semacam itu menentukan relasi dengan ketiga sifat tersebut. Kedua cara pandang ini memuat informasi yang persis sama.

Motivasinya datang dari kebiasaan mengelompokkan. Kita sering ingin menganggap dua objek "sama untuk keperluan tertentu", misalnya dua kata yang huruf pertamanya sama, atau dua kata yang panjangnya sama. Agar anggapan itu benar-benar menghasilkan kelompok, ada tiga tuntutan minimal:

1. setiap objek sekelompok dengan dirinya sendiri;
2. jika $x$ sekelompok dengan $y$, maka $y$ sekelompok dengan $x$;
3. jika $x$ sekelompok dengan $y$ dan $y$ sekelompok dengan $z$, maka $x$ sekelompok dengan $z$.

Tuntutan ketiga paling sering dilanggar dalam praktik. Relasi "mirip" atau "cukup dekat" biasanya memenuhi dua tuntutan pertama, tetapi rantai kemiripan dapat menyambungkan objek yang sama sekali tidak mirip. Akibat kegagalan itu kita lihat pada Contoh 4.2.8.

Relasi ekuivalensi

Definisi 4.2.1 (relasi ekuivalensi). Misalkan $A$ himpunan dan $\sim\;\subseteq A\times A$. Relasi $\sim$ disebut relasi ekuivalensi pada $A$ jika ia refleksif, simetris, dan transitif pada $A$ dalam arti 4.1:

$$\begin{aligned} &\forall x\in A\;(x\sim x),\\ &\forall x,y\in A\;(x\sim y\Rightarrow y\sim x),\\ &\forall x,y,z\in A\;((x\sim y\land y\sim z)\Rightarrow x\sim z). \end{aligned}$$

Frasa "pada $A$" bukan hiasan. Refleksivitas bergantung pada himpunan yang dinyatakan. Himpunan pasangan $\{(1,1),(2,2)\}$ adalah relasi ekuivalensi pada $\{1,2\}$. Sebagai relasi pada $\{1,2,3\}$, himpunan yang sama tidak refleksif karena $(3,3)$ tidak termuat di dalamnya. Simetri dan transitivitas hanya membicarakan pasangan yang sudah ada dalam relasi, sehingga tidak terpengaruh oleh penggantian $A$ dengan himpunan yang lebih besar.

Contoh 4.2.2.

(a) Kesamaan. Untuk sebarang himpunan $A$, bentuk dengan separasi pada $A\times A$

$$\Delta_A=\{p\in A\times A:\exists x\,(x\in A\land p=(x,x))\}.$$

Karakterisasi kesamaan pasangan dari 4.1 memberi $(x,y)\in\Delta_A$ jika dan hanya jika $x,y\in A$ dan $x=y$. Ketiga sifat ekuivalensi menjadi sifat logika kesamaan dari Bab 1: $x=x$; dari $x=y$ diperoleh $y=x$; dari $x=y$ dan $y=z$ diperoleh $x=z$.

(b) Relasi penuh. $A\times A$ adalah ekuivalensi pada $A$. Setiap pasangan anggota $A$ termuat di dalamnya, sehingga ketiga kesimpulan yang dituntut selalu benar.

(c) Relasi $R$ dari 4.1. Di 4.1 sudah dibuktikan bahwa $R$ refleksif, simetris, dan transitif pada $\{1,2,3\}$. Jadi $R$ relasi ekuivalensi. Kegagalan antisimetri ($1R2$, $2R1$, $1\ne2$) tidak relevan bagi ekuivalensi.

(d) Himpunan kosong. Karena $\varnothing\times\varnothing=\varnothing$ (4.1), satu-satunya relasi pada $\varnothing$ adalah $\varnothing$. Relasi ini ekuivalensi secara vakum, sebab setiap kuantor universal di Definisi 4.2.1 berjalan atas pembatas kosong.

(e) Bukan ekuivalensi. Relasi $T=R\cup\{(2,3),(3,2)\}$ dari 4.1 refleksif dan simetris, tetapi $1T2$, $2T3$, dan bukan $1T3$. Jadi $T$ bukan ekuivalensi.

Kelas ekuivalensi

Definisi 4.2.3 (kelas). Misalkan $\sim$ relasi ekuivalensi pada $A$ dan $a\in A$. Kelas ekuivalensi dari $a$ ialah

$$[a]=\{x\in A: x\sim a\}.$$

Himpunan ini ada menurut aksioma separasi dengan pembatas $A$. Bila perlu menegaskan relasinya, ditulis $[a]_\sim$. Anggota $a$ disebut wakil dari kelas tersebut. Akibat 4.2.6(b) akan menunjukkan bahwa setiap anggota suatu kelas dapat berperan sebagai wakilnya.

Kelas bergantung pada dua data, yaitu himpunan $A$ dan relasi $\sim$. Lambang $[a]$ saja tidak bermakna sebelum keduanya ditetapkan.

Lemma 4.2.4. Misalkan $\sim$ ekuivalensi pada $A$ dan $a\in A$. Maka: (a) untuk setiap $x$: $x\in[a]$ jika dan hanya jika $x\in A$ dan $x\sim a$; (b) $[a]\subseteq A$; (c) $a\in[a]$, sehingga $[a]\ne\varnothing$.

Bukti. Pernyataan (a) adalah bunyi aksioma separasi untuk himpunan pada Definisi 4.2.3. Pernyataan (b) langsung mengikuti (a). Untuk (c), $a\in A$ dan $a\sim a$ menurut refleksivitas, sehingga $a\in[a]$ menurut (a). $\blacksquare$

Teorema berikut adalah inti unit ini. Ketiga sifat ekuivalensi dipakai di dalamnya, masing-masing pada langkah yang dapat ditunjuk.

Teorema 4.2.5. Misalkan $\sim$ relasi ekuivalensi pada $A$ dan $a,b\in A$. Ketiga pernyataan berikut setara:

$$\text{(i) } a\sim b,\qquad \text{(ii) } [a]=[b],\qquad \text{(iii) } [a]\cap[b]\ne\varnothing.$$

Bukti. Kita buktikan (i)$\Rightarrow$(ii)$\Rightarrow$(iii)$\Rightarrow$(i).

(i)$\Rightarrow$(ii). Misalkan $a\sim b$. Kesamaan $[a]=[b]$ dibuktikan melalui dua inklusi, lalu ekstensionalitas.

• $[a]\subseteq[b]$: ambil $x\in[a]$. Menurut Lemma 4.2.4(a), $x\in A$ dan $x\sim a$. Dari $x\sim a$ dan $a\sim b$, transitivitas memberi $x\sim b$. Jadi $x\in[b]$.
• $[b]\subseteq[a]$: ambil $x\in[b]$, jadi $x\in A$ dan $x\sim b$. Simetri dari $a\sim b$ memberi $b\sim a$. Transitivitas pada $x\sim b$ dan $b\sim a$ memberi $x\sim a$. Jadi $x\in[a]$.

(ii)$\Rightarrow$(iii). Misalkan $[a]=[b]$. Menurut Lemma 4.2.4(c), $a\in[a]$, sehingga $a\in[b]$ juga. Jadi $a\in[a]\cap[b]$, dan irisan itu tidak kosong.

(iii)$\Rightarrow$(i). Misalkan ada $c\in[a]\cap[b]$. Maka $c\in A$, $c\sim a$, dan $c\sim b$. Simetri memberi $a\sim c$. Transitivitas pada $a\sim c$ dan $c\sim b$ memberi $a\sim b$. $\blacksquare$

Perhatikan pula jalan pintas (ii)$\Rightarrow$(i): dari $a\in[a]=[b]$ diperoleh langsung $a\sim b$. Arah sebaliknya, (i)$\Rightarrow$(iii), juga singkat: jika $a\sim b$, maka $a$ sendiri adalah saksi di $[a]\cap[b]$, karena $a\in[a]$ dan $a\sim b$ berarti $a\in[b]$.

Akibat 4.2.6. Misalkan $\sim$ ekuivalensi pada $A$. (a) Untuk setiap $a,b\in A$, tepat satu dari dua hal berikut berlaku: $[a]=[b]$, atau $[a]\cap[b]=\varnothing$. (b) Jika $a\in A$ dan $x\in[a]$, maka $[x]=[a]$. Jadi setiap anggota suatu kelas dapat menjadi wakilnya.

Bukti. (a) Teorema 4.2.5 memberi: jika $[a]\cap[b]\ne\varnothing$, maka $[a]=[b]$. Jadi sekurang-kurangnya satu dari kedua hal berlaku. Keduanya tidak mungkin berlaku bersama: jika $[a]=[b]$ dan $[a]\cap[b]=\varnothing$, maka dengan substitusi $[b]$ oleh $[a]$ diperoleh $[a]=[a]\cap[a]=[a]\cap[b]=\varnothing$, bertentangan dengan $a\in[a]$. (b) Dari $x\in[a]$ diperoleh $x\in A$ dan $x\sim a$, sehingga $[x]=[a]$ menurut Teorema 4.2.5. $\blacksquare$

Akibat 4.2.6 menunjukkan bahwa nama dan objek harus dibedakan. Lambang $[a]$ dan $[b]$ dengan $a\ne b$ dapat menamai himpunan yang sama. Dua kelas yang berbeda saling lepas, tetapi dua wakil yang berbeda tidak menjamin kelasnya berbeda. Menghitung kelas dengan menghitung wakil adalah kekeliruan.

Contoh 4.2.7 (kelas relasi $R$). Pada $A=\{1,2,3\}$ dengan $R$ seperti di atas, periksa setiap $x\in A$:

• $[1]=\{x\in A:xR1\}$. Untuk $x=1$: $(1,1)\in R$. Untuk $x=2$: $(2,1)\in R$. Untuk $x=3$: $(3,1)\notin R$. Jadi $[1]=\{1,2\}$.
• $[2]=\{x\in A:xR2\}$. Karena $(1,2),(2,2)\in R$ dan $(3,2)\notin R$, diperoleh $[2]=\{1,2\}$.
• $[3]=\{x\in A:xR3\}$. Satu-satunya pasangan di $R$ berkomponen kedua 3 adalah $(3,3)$, sehingga $[3]=\{3\}$.

Ada tiga wakil, tetapi hanya dua kelas: $[1]=[2]=\{1,2\}$ dan $[3]=\{3\}$. Sesuai Teorema 4.2.5, $1R2$ dan $[1]=[2]$. Karena $(1,3)\notin R$, diperoleh $[1]\ne[3]$, dan memang $[1]\cap[3]=\varnothing$.

Contoh 4.2.8 (kesalahan: kemiripan yang tidak transitif). Pada $A=\{1,2,3\}$, bentuk dengan separasi pada $A\times A$ relasi "kemiripan" $x\approx y$ jika $|x-y|\le1$ (nilai mutlak bilangan bulat dipinjam sebagai aritmetika elementer). Pemeriksaan semua sembilan pasangan menunjukkan bahwa $\approx$ tepat sama dengan relasi $T$ dari 4.1:

$$\approx\;=\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}=T.$$

Relasi ini refleksif ($|x-x|=0$) dan simetris ($|x-y|=|y-x|$). Ia tidak transitif: $1\approx2$, $2\approx3$, tetapi $|1-3|=2$.

Separasi tetap mengizinkan pembentukan $N(a)=\{x\in A:x\approx a\}$ untuk setiap $a\in A$. Keberadaan himpunan bukan masalahnya. Masalahnya terletak pada sifat himpunan-himpunan itu:

$$N(1)=\{1,2\},\qquad N(2)=\{1,2,3\},\qquad N(3)=\{2,3\}.$$

Ketiganya berbeda. Meski begitu, $N(1)\cap N(3)=\{2\}\ne\varnothing$, dan $N(1)\cap N(2)\ne\varnothing$ walaupun $N(1)\ne N(2)$. Implikasi (iii)$\Rightarrow$(i) di Teorema 4.2.5 runtuh tepat pada langkah transitivitas. Implikasi (i)$\Rightarrow$(ii) juga runtuh: $1\approx2$ tetapi $N(1)\ne N(2)$. Kelompok yang tumpang tindih seperti ini tidak dapat ditafsirkan sebagai pengelompokan. Pertanyaan "objek 2 masuk kelompok mana?" tidak mempunyai jawaban tunggal.

Pola ini dapat muncul pada kriteria "selisih paling banyak $\varepsilon$" dengan $\varepsilon>0$: dua objek berdekatan, objek kedua dekat dengan objek ketiga, tetapi objek pertama dan ketiga belum tentu dekat. Contoh ini hanya menyatakan fakta tentang relasinya. Ia tidak menilai metode pengelompokan data tertentu.

Partisi

Definisi 4.2.9 (partisi). Misalkan $A$ himpunan. Himpunan $\Pi$ disebut partisi dari $A$ jika $\Pi\subseteq\mathcal P(A)$ dan

$$\begin{aligned} &\text{(P1)}\quad \forall B\in\Pi\;(B\ne\varnothing),\\ &\text{(P2)}\quad \textstyle\bigcup\Pi=A,\\ &\text{(P3)}\quad \forall B,C\in\Pi\;(B\ne C\Rightarrow B\cap C=\varnothing). \end{aligned}$$

Anggota $\Pi$ disebut blok. Setiap blok adalah himpunan bagian dari $A$, dan sekaligus anggota dari $\Pi$. Kedua hubungan ini, yaitu inklusi $B\subseteq A$ dan keanggotaan $B\in\Pi$, jangan dipertukarkan.

Menurut aksioma gabungan dari Bab 3, ada himpunan $\bigcup\Pi$ dengan sifat: untuk setiap $x$, $x\in\bigcup\Pi$ jika dan hanya jika $\exists B\in\Pi\,(x\in B)$. Karena $\Pi\subseteq\mathcal P(A)$, inklusi $\bigcup\Pi\subseteq A$ selalu berlaku. Jadi isi sebenarnya dari (P2) adalah inklusi $A\subseteq\bigcup\Pi$: setiap anggota $A$ termuat dalam suatu blok.

Lemma 4.2.10. Jika $\Pi$ partisi dari $A$, maka untuk setiap $x\in A$ ada tepat satu $B\in\Pi$ dengan $x\in B$.

Bukti. Keberadaan: dari (P2), $x\in\bigcup\Pi$, jadi ada $B\in\Pi$ dengan $x\in B$. Ketunggalan: jika $x\in B$ dan $x\in C$ dengan $B,C\in\Pi$, maka $x\in B\cap C$, sehingga $B\cap C\ne\varnothing$. Kontraposisi (P3) memberi $B=C$. $\blacksquare$

Contoh 4.2.11. Pada $A=\{1,2,3\}$, himpunan berikut adalah partisi:

$$\{\{1,2,3\}\},\quad \{\{1\},\{2,3\}\},\quad \{\{2\},\{1,3\}\},\quad \{\{3\},\{1,2\}\},\quad \{\{1\},\{2\},\{3\}\}.$$

(Latihan 4.2.34 memeriksa bahwa kelimanya memang partisi dan bahwa tidak ada partisi lain.) Berikut contoh yang bukan partisi dan syarat yang dilanggarnya:

• $\{\{1,2\},\{2,3\}\}$: kedua blok berbeda tetapi beririsan di $2$, sehingga melanggar (P3);
• $\{\{1\},\{3\}\}$: gabungannya $\{1,3\}\ne A$, sehingga melanggar (P2);
• $\{\{1,2\},\{3\},\varnothing\}$: memuat blok kosong, sehingga melanggar (P1);
• $\{\{1,2,3\},\{4\}\}$: $\{4\}\notin\mathcal P(A)$, sehingga keluarga ini bukan himpunan bagian dari $\mathcal P(A)$.

Contoh 4.2.12 (kasus batas $A=\varnothing$). Karena $\mathcal P(\varnothing)=\{\varnothing\}$, calon partisi hanya $\varnothing$ dan $\{\varnothing\}$.

• $\Pi=\{\varnothing\}$ bukan partisi, karena satu-satunya bloknya kosong dan (P1) gagal.
• $\Pi=\varnothing$ adalah partisi. (P1) dan (P3) berlaku secara vakum, sebab tidak ada blok. (P2) berlaku karena $\bigcup\varnothing=\varnothing=A$.

Jadi satu-satunya partisi dari $\varnothing$ adalah $\varnothing$. Syarat (P1) menuntut setiap blok tak kosong. Ia tidak menuntut keluarga $\Pi$ sendiri tak kosong. Sebaliknya, jika $A\ne\varnothing$, keluarga $\varnothing$ bukan partisi dari $A$, sebab $\bigcup\varnothing=\varnothing\ne A$.

Dengan alasan yang sama, $\{A\}$ adalah partisi dari $A$ jika dan hanya jika $A\ne\varnothing$. Untuk $A\ne\varnothing$, ketiga syarat jelas berlaku. Untuk $A=\varnothing$, $\{A\}=\{\varnothing\}$ gagal di (P1).

Dari ekuivalensi ke partisi

Kita ingin mengumpulkan semua kelas ke dalam satu himpunan. Ungkapan $\{[a]:a\in A\}$ belum dibenarkan oleh aksioma yang tersedia sejauh ini (Bab 3). Keluarga itu harus dipisahkan dari himpunan yang sudah ada, dan pembatas yang tepat adalah $\mathcal P(A)$, sebab setiap kelas adalah himpunan bagian dari $A$.

Definisi 4.2.13 (keluarga kelas). Misalkan $\sim$ ekuivalensi pada $A$. Definisikan dengan separasi pada $\mathcal P(A)$:

$$\mathcal K_\sim=\{B\in\mathcal P(A):\exists a\in A\;\forall x\;(x\in B\leftrightarrow(x\in A\land x\sim a))\}.$$

Lemma 4.2.14. Untuk setiap himpunan $B$: $B\in\mathcal K_\sim$ jika dan hanya jika ada $a\in A$ dengan $B=[a]$.

Bukti. ($\Rightarrow$) Jika $B\in\mathcal K_\sim$, ada $a\in A$ sehingga untuk setiap $x$, $x\in B$ setara dengan $x\in A\land x\sim a$. Menurut Lemma 4.2.4(a), syarat yang sama setara dengan $x\in[a]$. Jadi $B$ dan $[a]$ beranggota sama, dan $B=[a]$ menurut ekstensionalitas. ($\Leftarrow$) Jika $B=[a]$ dengan $a\in A$, maka $B\subseteq A$ (Lemma 4.2.4(b)), sehingga $B\in\mathcal P(A)$. Rumus pemisahnya dipenuhi dengan saksi $a$ menurut Lemma 4.2.4(a). $\blacksquare$

Teorema 4.2.15. Jika $\sim$ ekuivalensi pada $A$, maka $\mathcal K_\sim$ adalah partisi dari $A$.

Bukti. Inklusi $\mathcal K_\sim\subseteq\mathcal P(A)$ berlaku menurut konstruksi.

(P1) Ambil $B\in\mathcal K_\sim$. Menurut Lemma 4.2.14, $B=[a]$ untuk suatu $a\in A$, dan $a\in[a]$, sehingga $B\ne\varnothing$.

(P2) Kita buktikan dua inklusi. Jika $x\in\bigcup\mathcal K_\sim$, ada $B\in\mathcal K_\sim$ dengan $x\in B$. Karena $B\subseteq A$, diperoleh $x\in A$. Sebaliknya, jika $x\in A$, maka $x\in[x]$ dan $[x]\in\mathcal K_\sim$ menurut Lemma 4.2.14, sehingga $x\in\bigcup\mathcal K_\sim$.

(P3) Ambil $B,C\in\mathcal K_\sim$ dengan $B\ne C$. Tulis $B=[a]$ dan $C=[b]$ dengan $a,b\in A$. Jika $B\cap C\ne\varnothing$, Teorema 4.2.5 memberi $[a]=[b]$, yaitu $B=C$, suatu kontradiksi. Jadi $B\cap C=\varnothing$. $\blacksquare$

Dari partisi ke ekuivalensi

Arah sebaliknya meniru bentuk $R=(C\times C)\cup(D\times D)$: dua anggota berelasi jika ada blok yang memuat keduanya.

Definisi 4.2.16. Misalkan $\Pi$ partisi dari $A$. Definisikan dengan separasi pada $A\times A$:

$$\sim_\Pi\;=\{p\in A\times A:\exists x\,\exists y\,\exists B\,(p=(x,y)\land B\in\Pi\land x\in B\land y\in B)\}.$$

Lemma 4.2.17. Untuk $x,y\in A$: $(x,y)\in\;\sim_\Pi$ jika dan hanya jika ada $B\in\Pi$ dengan $x\in B$ dan $y\in B$.

Bukti. ($\Leftarrow$) Jika $x,y\in B\in\Pi$, maka $(x,y)\in A\times A$, dan rumus pemisah dipenuhi dengan saksi $x,y,B$. ($\Rightarrow$) Jika $(x,y)\in\;\sim_\Pi$, ada $x',y',B$ dengan $(x,y)=(x',y')$, $B\in\Pi$, $x'\in B$, dan $y'\in B$. Karakterisasi kesamaan pasangan berurutan dari 4.1 memberi $x=x'$ dan $y=y'$. Jadi $x,y\in B$. $\blacksquare$

Langkah ($\Rightarrow$) memakai karakterisasi kesamaan pasangan berurutan dari 4.1 untuk membaca kembali komponen $x$ dan $y$ dari pasangan $p$. Karena syarat "$x\in B$ dan $y\in B$" simetris dalam $x$ dan $y$, keterurutan pasangan tidak berperan khusus di sini. Keterurutan menjadi penting untuk relasi yang tidak simetris, misalnya relasi urutan pada 4.4.

Teorema 4.2.18. Jika $\Pi$ partisi dari $A$, maka $\sim_\Pi$ adalah relasi ekuivalensi pada $A$.

Bukti. Semua langkah memakai Lemma 4.2.17.

Refleksif. Ambil $x\in A$. Menurut (P2) ada $B\in\Pi$ dengan $x\in B$. Blok $B$ memuat $x$ dan $x$, sehingga $x\sim_\Pi x$.

Simetris. Jika $x\sim_\Pi y$, ada $B\in\Pi$ dengan $x,y\in B$. Blok yang sama menyaksikan $y\sim_\Pi x$.

Transitif. Misalkan $x\sim_\Pi y$ dan $y\sim_\Pi z$. Ada $B\in\Pi$ dengan $x,y\in B$ dan ada $C\in\Pi$ dengan $y,z\in C$. Maka $y\in B\cap C$, sehingga $B\cap C\ne\varnothing$. Kontraposisi (P3) memberi $B=C$. Jadi $x,z\in B$ dan $x\sim_\Pi z$. $\blacksquare$

Bukti transitivitas memakai (P3) secara hakiki. Dua blok yang sama-sama memuat $y$ harus merupakan blok yang sama. Untuk keluarga yang bloknya tumpang tindih, relasi "ada blok yang memuat keduanya" dapat gagal transitif (Latihan 4.2.29). Refleksivitas memakai (P2). Syarat (P1) tidak dipakai di sini, tetapi diperlukan pada teorema berikut agar konstruksi bolak-balik kembali ke titik awal.

Kedua konstruksi saling membalik

Lemma 4.2.19. Misalkan $\Pi$ partisi dari $A$, $B\in\Pi$, dan $a\in B$. Maka kelas $a$ terhadap $\sim_\Pi$ adalah $B$:

$$[a]_{\sim_\Pi}=B.$$

Bukti. Perhatikan bahwa $a\in A$ karena $B\subseteq A$. ($\subseteq$) Jika $x\in[a]_{\sim_\Pi}$, maka $x\in A$ dan $x\sim_\Pi a$. Jadi ada $C\in\Pi$ dengan $x,a\in C$. Karena $a\in B\cap C$, (P3) memberi $C=B$, sehingga $x\in B$. ($\supseteq$) Jika $x\in B$, maka $x\in A$, dan blok $B$ memuat $x$ dan $a$. Jadi $x\sim_\Pi a$, yaitu $x\in[a]_{\sim_\Pi}$. $\blacksquare$

Teorema 4.2.20 (korespondensi ekuivalensi–partisi). Misalkan $A$ himpunan. (a) Untuk setiap partisi $\Pi$ dari $A$: $\mathcal K_{\sim_\Pi}=\Pi$. (b) Untuk setiap ekuivalensi $\sim$ pada $A$: $\sim_{\mathcal K_\sim}\;=\;\sim$.

Bukti. (a) Ruas kiri terdefinisi karena $\sim_\Pi$ ekuivalensi (Teorema 4.2.18). Kita buktikan dua inklusi. ($\subseteq$) Ambil $D\in\mathcal K_{\sim_\Pi}$. Menurut Lemma 4.2.14, $D=[a]_{\sim_\Pi}$ untuk suatu $a\in A$. Menurut (P2), ada $B\in\Pi$ dengan $a\in B$. Lemma 4.2.19 memberi $D=B\in\Pi$. ($\supseteq$) Ambil $B\in\Pi$. Menurut (P1), $B\ne\varnothing$, jadi ada $a\in B$. Lemma 4.2.19 memberi $B=[a]_{\sim_\Pi}$, dengan $a\in A$. Menurut Lemma 4.2.14, $B\in\mathcal K_{\sim_\Pi}$.

(b) Ruas kiri terdefinisi karena $\mathcal K_\sim$ partisi (Teorema 4.2.15). Kedua relasi adalah himpunan bagian dari $A\times A$, sehingga setiap anggotanya berbentuk $(x,y)$ dengan $x,y\in A$. Cukup dibuktikan bahwa untuk $x,y\in A$:

$$x\sim_{\mathcal K_\sim}y\iff x\sim y.$$

($\Leftarrow$) Jika $x\sim y$, maka $x\in[y]$. Juga $y\in[y]$ dan $[y]\in\mathcal K_\sim$. Jadi blok $[y]$ memuat keduanya. ($\Rightarrow$) Jika ada $B\in\mathcal K_\sim$ dengan $x,y\in B$, tulis $B=[a]$ dengan $a\in A$. Maka $x\sim a$ dan $y\sim a$. Simetri memberi $a\sim y$, dan transitivitas memberi $x\sim y$. Kedua relasi beranggota sama, sehingga sama menurut ekstensionalitas. $\blacksquare$

Teorema 4.2.20 menyatakan bahwa kedua konstruksi tidak kehilangan informasi. Partisi yang berbeda menghasilkan relasi yang berbeda, karena partisi dapat dibaca kembali dari relasinya menurut (a). Setiap ekuivalensi berasal dari suatu partisi, yaitu dari keluarga kelasnya sendiri menurut (b). Bahasa fungsi untuk menyebut korespondensi seperti ini secara ringkas baru dibangun pada Bab 5.

Catatan 4.2.21 (tidak ada aksioma pilihan). Pada bukti ($\supseteq$) di Teorema 4.2.20(a), kita "mengambil $a\in B$". Ini adalah instansiasi eksistensial biasa di dalam bukti pernyataan berbentuk $\forall B\in\Pi(\cdots)$. Untuk satu blok $B$ yang sedang ditinjau, ketakkosongan $B$ memberi suatu anggota, dan kesimpulan $B\in\mathcal K_{\sim_\Pi}$ tidak bergantung pada anggota mana yang diambil. Kita tidak pernah membentuk satu objek yang serentak memilih wakil dari setiap blok. Jaminan adanya pilihan wakil serentak untuk setiap keluarga sebarang dari himpunan tak kosong memerlukan aksioma pilihan (AC). Untuk keluarga tertentu, pilihan wakil dapat tersedia tanpa AC, misalnya bila wakil dapat ditentukan dengan suatu aturan eksplisit. Keluarga kelas $\mathcal K_\sim$ juga dibentuk tanpa pilihan, cukup dengan separasi pada $\mathcal P(A)$. Seluruh unit ini berlangsung tanpa AC.

Contoh 4.2.22 (bolak-balik untuk $R$). Menurut Lemma 4.2.14, $B\in\mathcal K_R$ jika dan hanya jika $B=[a]$ untuk suatu $a\in\{1,2,3\}$. Contoh 4.2.7 memberi $[1]=[2]=\{1,2\}$ dan $[3]=\{3\}$, sehingga menurut ekstensionalitas $\mathcal K_R=\{\{1,2\},\{3\}\}$, dengan $[1]=[2]\ne[3]$. Ini partisi dari $\{1,2,3\}$. Sekarang bentuk kembali $\sim_\Pi$ untuk $\Pi=\{\{1,2\},\{3\}\}$. Pasangan dengan kedua komponen di $\{1,2\}$ ada empat, yaitu $(1,1),(1,2),(2,1),(2,2)$. Pasangan dengan kedua komponen di $\{3\}$ hanya $(3,3)$. Tidak ada pasangan lain yang komponennya termuat bersama dalam satu blok. Jadi

$$\sim_\Pi\;=\{(1,1),(1,2),(2,1),(2,2),(3,3)\}=R,$$

sesuai Teorema 4.2.20(b) dan sesuai bentuk $R=(C\times C)\cup(D\times D)$ di 4.1.

Contoh 4.2.23 (kasus ekstrem).

(a) $A=\varnothing$. Satu-satunya ekuivalensi adalah relasi kosong $\varnothing$ (Contoh 4.2.2(d)). Keluarga kelasnya

$$\mathcal K_\varnothing=\{B\in\mathcal P(\varnothing):\exists a\in\varnothing\,(\cdots)\}=\varnothing,$$

karena tidak ada $a\in\varnothing$ yang dapat menjadi saksi. Hasil ini cocok dengan Contoh 4.2.12: satu-satunya partisi adalah $\varnothing$, bukan $\{\varnothing\}$. Dari arah sebaliknya, $\sim_\varnothing\subseteq\varnothing\times\varnothing=\varnothing$. Di sini $\mathcal K_\varnothing$ dibentuk dari relasi kosong, sedangkan $\sim_\varnothing$ dibentuk dari partisi kosong. Kedua konstruksi saling membalik pada satu-satunya ekuivalensi ($\varnothing$) dan satu-satunya partisi ($\varnothing$) dari $\varnothing$.

(b) Kesamaan $\Delta_A$. Di sini $[a]=\{x\in A:x=a\}=\{a\}$, jadi setiap blok berupa singleton. Misalnya untuk $A=\{1,2,3\}$, $\mathcal K_{\Delta_A}=\{\{1\},\{2\},\{3\}\}$.

(c) Relasi penuh $A\times A$ dengan $A\ne\varnothing$. Untuk setiap $a\in A$, $[a]=A$, sehingga $\mathcal K_{A\times A}=\{A\}$. Untuk $A=\varnothing$, relasi penuhnya adalah $\varnothing$ dan keluarga kelasnya $\varnothing$, bukan $\{A\}=\{\varnothing\}$. Kasus batas ini konsisten dengan Contoh 4.2.12.

Penerapan: mengelompokkan data menurut kriteria yang eksplisit

Bagian ini adalah model kecil yang dapat dihitung tangan. Ia tidak melaporkan sistem atau perangkat lunak tertentu. Misalkan data berupa himpunan enam kata

$$A=\{\text{apel},\ \text{anggur},\ \text{alpukat},\ \text{belimbing},\ \text{bayam},\ \text{cabai}\}.$$

Kriteria 1: huruf pertama sama. Bentuk dengan separasi pada $A\times A$ relasi $x\equiv_1 y$ jika huruf pertama $x$ sama dengan huruf pertama $y$. Setiap kata di $A$ tak kosong, sehingga huruf pertamanya tertentu secara tunggal. Relasi ini ekuivalensi karena ketiga sifatnya diwarisi dari kesamaan huruf, seperti pada Contoh 4.2.2(a). Kelas-kelasnya:

$$[\text{apel}]=\{\text{apel},\text{anggur},\text{alpukat}\},\quad [\text{bayam}]=\{\text{belimbing},\text{bayam}\},\quad [\text{cabai}]=\{\text{cabai}\}.$$

Ada enam wakil tetapi tiga kelas. Ketiga himpunan itu tak kosong, saling lepas, dan bergabung menjadi $A$. Menurut Teorema 4.2.20(b), relasinya terdiri tepat dari pasangan yang kedua komponennya termuat dalam satu blok. Dengan mendaftar pasangan per blok diperoleh sembilan pasangan dari blok huruf a, empat dari blok huruf b, dan satu, yaitu $(\text{cabai},\text{cabai})$, dari blok huruf c; seluruhnya $14$ pasangan.

Kriteria berbentuk "nilai atribut tertentu sama" selalu menghasilkan ekuivalensi, asalkan setiap objek mempunyai tepat satu nilai atribut itu. Bab 5 akan merumuskan pola ini dengan bahasa fungsi.

Kriteria 2: panjang kata sama. Panjang kata-kata tersebut berturut-turut $4,6,7,9,5,5$. Relasi "panjangnya sama", juga dibentuk dengan separasi pada $A\times A$, adalah ekuivalensi dengan partisi

$$\{\{\text{apel}\},\{\text{anggur}\},\{\text{alpukat}\},\{\text{belimbing}\},\{\text{bayam},\text{cabai}\}\}.$$

Kriteria 3 (gagal): panjang berselisih paling banyak 1. Relasi ini refleksif dan simetris. Ia tidak transitif: apel (4) dan bayam (5) berselisih 1, bayam (5) dan anggur (6) berselisih 1, tetapi apel (4) dan anggur (6) berselisih 2. Seperti pada Contoh 4.2.8, "kelompok kemiripan" yang dibentuk kriteria ini tumpang tindih dan tidak membentuk partisi. Jika suatu pengelompokan tetap diinginkan, kriteria harus diganti dengan ekuivalensi yang dinyatakan eksplisit. Alternatifnya, pengguna harus menerima bahwa rantai kemiripan menyatukan objek yang tidak saling mirip (Latihan 4.2.31).

Catatan: ekuivalensi yang antisimetri

Proposisi 4.2.24. Jika $\sim$ ekuivalensi pada $A$ yang juga antisimetri, maka $\sim\;=\Delta_A$.

Bukti. Jika $x\sim y$, simetri memberi $y\sim x$, lalu antisimetri memberi $x=y$. Jadi $\sim\;\subseteq\Delta_A$. Sebaliknya, refleksivitas memberi $x\sim x$ untuk setiap $x\in A$, sehingga $\Delta_A\subseteq\;\sim$. $\blacksquare$

Jadi pada $A$, $\Delta_A$ adalah satu-satunya relasi yang sekaligus refleksif, simetris, antisimetri, dan transitif. Relasi $R$ dari 4.1 gagal antisimetri justru karena ia menggabungkan $1$ dan $2$ ke dalam satu kelas. Unit 4.4 akan menempuh arah yang berlawanan: refleksivitas dan transitivitas dipertahankan, tetapi simetri diganti antisimetri. Relasi semacam itu akan disebut urutan parsial.

Kesalahan umum

1. Menghitung wakil sebagai kelas. $[1]$ dan $[2]$ pada Contoh 4.2.7 adalah satu objek, yaitu $\{1,2\}$.
2. Menganggap $\{\varnothing\}$ sebagai partisi dari $\varnothing$. Blok tidak boleh kosong. Partisi dari $\varnothing$ adalah $\varnothing$.
3. Hanya memeriksa (P1) dan (P2). Keluarga yang menutupi $A$ dengan blok tak kosong tetapi tumpang tindih bukan partisi, dan relasi turunannya bisa gagal transitif.
4. Menyebut "kemiripan" sebagai ekuivalensi tanpa memeriksa transitivitas. Untuk membantahnya, tampilkan tiga objek dengan kedua premis benar dan kesimpulan salah.
5. Menulis $\{[a]:a\in A\}$ tanpa membatasi pada himpunan yang sudah ada. Keluarga kelas dibentuk dengan separasi pada $\mathcal P(A)$ (Definisi 4.2.13).
6. Mencampur anggota dan himpunan bagian. Blok $B$ memenuhi $B\in\Pi$ dan $B\subseteq A$. Pernyataan $B\in A$ atau $B\subseteq\Pi$ tidak mengikuti definisi partisi.

Latihan

Latihan 4.2.25. Pada $A=\{1,2,3,4\}$ diberikan

$$S=\{(1,1),(2,2),(3,3),(4,4),(1,3),(3,1)\}.$$

Buktikan bahwa $S$ ekuivalensi. Hitung $[a]$ untuk setiap $a\in A$, tentukan $\mathcal K_S$, lalu bentuk kembali $\sim_{\mathcal K_S}$ dan bandingkan dengan $S$.

Latihan 4.2.26. Pada $A=\{1,2,3,4,5\}$ diberikan $\Pi=\{\{1,4\},\{2,3,5\}\}$. Periksa bahwa $\Pi$ partisi. Tuliskan semua pasangan di $\sim_\Pi$ dan hitung banyaknya. Hitung $[5]_{\sim_\Pi}$ dan $[1]_{\sim_\Pi}$ langsung dari definisi kelas, lalu cocokkan dengan Lemma 4.2.19.

Latihan 4.2.27. Misalkan $\sim$ ekuivalensi pada $A$. Pada bukti Teorema 4.2.5, tunjukkan sifat mana (refleksif, simetris, transitif) yang dipakai di setiap implikasi. Untuk relasi $T$ dari 4.1, tentukan implikasi mana yang gagal, lengkap dengan saksinya.

Latihan 4.2.28. Tentukan mana yang merupakan partisi dari $A=\{1,2,3,4\}$, dengan alasan: (a) $\{\{1,2\},\{2,3\},\{4\}\}$; (b) $\{\{1\},\{2,3\}\}$; (c) $\{\{1,2,3,4\}\}$; (d) $\{\{1\},\{2\},\{3\},\{4\},\varnothing\}$; (e) $\{\{1,2\},\{3,4\}\}$.

Latihan 4.2.29. Untuk keluarga $\mathcal F=\{\{1,2\},\{2,3\},\{4\}\}$ pada $A=\{1,2,3,4\}$, definisikan $x\,\rho\,y$ jika ada $B\in\mathcal F$ dengan $x,y\in B$. Tunjukkan bahwa $\rho$ refleksif dan simetris tetapi tidak transitif, lalu tunjukkan langkah bukti Teorema 4.2.18 yang gagal.

Latihan 4.2.30. Misalkan $\sim\;\subseteq A\times A$ refleksif dan memenuhi

$$\forall x,y,z\in A\;((x\sim y\land x\sim z)\Rightarrow y\sim z).$$

Buktikan bahwa $\sim$ ekuivalensi. Sebaliknya, buktikan bahwa setiap ekuivalensi memenuhi sifat ini.

Latihan 4.2.31. Pada $A=\{2,3,4,10\}$, definisikan $x\approx y$ jika $|x-y|\le1$. (a) Tunjukkan bahwa $\approx$ refleksif dan simetris tetapi tidak transitif. (b) Hitung $N(a)=\{x\in A:x\approx a\}$ untuk setiap $a\in A$, lalu jelaskan mengapa keluarga

$$\mathcal N=\{B\in\mathcal P(A):\exists a\in A\;\forall x\,(x\in B\leftrightarrow(x\in A\land x\approx a))\}$$

bukan partisi dari $A$. (c) Tentukan partisi $\Pi$ dari $A$ dengan blok sebanyak mungkin yang memenuhi syarat: setiap pasangan $x\approx y$ termuat dalam satu blok $\Pi$.

Latihan 4.2.32 (A kosong). Tentukan semua relasi pada $\varnothing$ dan semua himpunan bagian dari $\mathcal P(\varnothing)$. Tentukan mana yang ekuivalensi dan mana yang partisi, lalu periksa kedua bagian Teorema 4.2.20 secara langsung.

Latihan 4.2.33 (anggota versus himpunan bagian). Misalkan $A=\{\varnothing\}$. Daftarkan semua himpunan bagian dari $\mathcal P(A)$ dan tentukan mana yang partisi dari $A$. Daftarkan pula semua relasi pada $A$ dan tentukan mana yang ekuivalensi.

Latihan 4.2.34. Buktikan bahwa partisi dari $\{1,2,3\}$ tepat lima buah, yaitu yang terdaftar di Contoh 4.2.11. Simpulkan banyak relasi ekuivalensi pada $\{1,2,3\}$, dan tentukan partisi yang berpadanan dengan $R$ dari 4.1.

Latihan 4.2.35. Misalkan $\sim$ ekuivalensi pada $A$ dan $a,b\in A$ dengan $[a]\ne[b]$. Buktikan bahwa untuk setiap $x\in[a]$ dan $y\in[b]$ berlaku bukan $x\sim y$.

Pembahasan

4.2.25. Pasangan diagonal $(1,1),\ldots,(4,4)$ termuat, sehingga $S$ refleksif. Pasangan nondiagonal hanya $(1,3)$ dan $(3,1)$, dan keduanya saling mencerminkan, sehingga $S$ simetris.

Untuk transitivitas, misalkan $xSy$ dan $ySz$. Jika premis pertama diagonal, yaitu $x=y$, maka kesimpulan $xSz$ sama dengan premis kedua. Hal serupa berlaku jika $y=z$. Jika keduanya nondiagonal, maka $(x,y)$ dan $(y,z)$ berasal dari $\{(1,3),(3,1)\}$ dengan komponen tengah yang sama. Kemungkinannya hanya $(1,3),(3,1)$, yang memberi $(1,1)\in S$, atau $(3,1),(1,3)$, yang memberi $(3,3)\in S$.

Kelas-kelasnya: $[1]=\{x\in A:xS1\}=\{1,3\}$, $[3]=\{x\in A:xS3\}=\{1,3\}$, $[2]=\{2\}$, $[4]=\{4\}$. Ada empat wakil tetapi tiga kelas, dan menurut Lemma 4.2.14, $\mathcal K_S=\{\{1,3\},\{2\},\{4\}\}$. Pasangan yang kedua komponennya termuat dalam satu blok adalah $(1,1),(1,3),(3,1),(3,3)$ dari blok pertama, serta $(2,2)$ dan $(4,4)$. Hasilnya tepat $S$, sesuai Teorema 4.2.20(b).

4.2.26. $\Pi\subseteq\mathcal P(A)$, kedua blok tak kosong, gabungannya $\{1,2,3,4,5\}=A$, dan $\{1,4\}\cap\{2,3,5\}=\varnothing$. Jadi $\Pi$ partisi. Menurut Lemma 4.2.17, pasangan di $\sim_\Pi$ tepat pasangan yang kedua komponennya termuat dalam satu blok:

$$\sim_\Pi=\{(1,1),(1,4),(4,1),(4,4),\,(2,2),(2,3),(2,5),(3,2),(3,3),(3,5),(5,2),(5,3),(5,5)\},$$

yaitu $4+9=13$ pasangan.

Untuk $[5]$: pasangan di $\sim_\Pi$ dengan komponen kedua $5$ adalah $(2,5),(3,5),(5,5)$, sehingga $[5]=\{2,3,5\}$. Untuk $[1]$: pasangan dengan komponen kedua $1$ adalah $(1,1),(4,1)$, sehingga $[1]=\{1,4\}$. Keduanya adalah blok yang memuat wakilnya, sesuai Lemma 4.2.19.

4.2.27. (i)$\Rightarrow$(ii): inklusi $[a]\subseteq[b]$ memakai transitivitas, sedangkan $[b]\subseteq[a]$ memakai simetri dan transitivitas. (ii)$\Rightarrow$(iii): refleksivitas, melalui $a\in[a]$. (iii)$\Rightarrow$(i): simetri dan transitivitas.

Untuk $T$, refleksivitas dan simetri tersedia, sehingga (ii)$\Rightarrow$(iii) tetap berlaku. Dengan $N(a)=\{x\in A:xTa\}$ seperti di Contoh 4.2.8:

• (i)$\Rightarrow$(ii) gagal: $1T2$, tetapi $N(1)=\{1,2\}\ne\{1,2,3\}=N(2)$. Saksinya $3\in N(2)\setminus N(1)$. Pada langkah transitivitas, $3T2$ dan $2T1$ tidak memberi $3T1$.
• (iii)$\Rightarrow$(i) gagal: $2\in N(1)\cap N(3)$, tetapi bukan $1T3$.

4.2.28. (a) Bukan partisi: $\{1,2\}\ne\{2,3\}$ tetapi irisannya $\{2\}$, sehingga (P3) gagal. (b) Bukan partisi: $4\notin\bigcup\{\{1\},\{2,3\}\}=\{1,2,3\}$, sehingga (P2) gagal. (c) Partisi: satu blok tak kosong yang sama dengan $A$, dan (P3) vakum karena tidak ada dua blok berbeda. (d) Bukan partisi: $\varnothing$ adalah blok, sehingga (P1) gagal, walaupun (P2) dan (P3) berlaku. (e) Partisi: kedua blok tak kosong, saling lepas, dan gabungannya $A$.

4.2.29. Setiap $x\in A$ termuat dalam suatu anggota $\mathcal F$, sehingga $x\rho x$. Simetri berlaku karena kondisi "$x,y\in B$" simetris dalam $x$ dan $y$. Transitivitas gagal: $1\rho2$ melalui $\{1,2\}$ dan $2\rho3$ melalui $\{2,3\}$, tetapi tidak ada anggota $\mathcal F$ yang memuat $1$ dan $3$.

Pada bukti Teorema 4.2.18, dari $y=2\in B\cap C$ dengan $B=\{1,2\}$ dan $C=\{2,3\}$ kita menyimpulkan $B=C$ menggunakan (P3). Langkah itu gagal karena $\mathcal F$ tidak memenuhi (P3).

4.2.30. Simetri. Misalkan $x\sim y$. Refleksivitas memberi $x\sim x$. Terapkan hipotesis pada $x\sim y$ dan $x\sim x$, dengan $z:=x$, sehingga diperoleh $y\sim x$. Transitivitas. Misalkan $x\sim y$ dan $y\sim z$. Simetri yang baru dibuktikan memberi $y\sim x$. Terapkan hipotesis pada $y\sim x$ dan $y\sim z$, dengan peran $(x,y,z)$ diisi $(y,x,z)$, sehingga diperoleh $x\sim z$. Sebaliknya. Jika $\sim$ ekuivalensi, serta $x\sim y$ dan $x\sim z$, maka simetri memberi $y\sim x$, dan transitivitas pada $y\sim x$, $x\sim z$ memberi $y\sim z$.

4.2.31. (a) $|x-x|=0\le1$ dan $|x-y|=|y-x|$. Transitivitas gagal dengan saksi $2\approx3$, $3\approx4$, tetapi $|2-4|=2>1$.

(b) $N(2)=\{2,3\}$, $N(3)=\{2,3,4\}$, $N(4)=\{3,4\}$, $N(10)=\{10\}$. Seperti pada Lemma 4.2.14, $B\in\mathcal N$ jika dan hanya jika $B=N(a)$ untuk suatu $a\in A$. Jadi $\mathcal N=\{\{2,3\},\{2,3,4\},\{3,4\},\{10\}\}$. Keluarga ini ada menurut separasi pada $\mathcal P(A)$; yang gagal adalah syarat partisinya. Himpunan $N(2)\ne N(3)$ tetapi $N(2)\cap N(3)=\{2,3\}\ne\varnothing$, sehingga (P3) gagal.

(c) Misalkan $\Pi$ memenuhi syarat. Pasangan $2\approx3$ memaksa $2$ dan $3$ berada dalam satu blok $B$. Pasangan $3\approx4$ memaksa $3$ dan $4$ berada dalam satu blok $C$. Karena $3\in B\cap C$, (P3) memberi $B=C$, sehingga $\{2,3,4\}\subseteq B$. Partisi $\{\{2,3,4\},\{10\}\}$ memenuhi syarat, sebab setiap pasangan $\approx$ termuat dalam salah satu bloknya. Partisi ini juga mempunyai blok sebanyak mungkin: setiap partisi yang memenuhi syarat menaruh $2,3,4$ dalam satu blok, sehingga paling banyak ada dua blok. Pengelompokan yang konsisten dengan kemiripan ini memaksa $2$ dan $4$ sekelompok, walaupun keduanya tidak mirip.

4.2.32. $\varnothing\times\varnothing=\varnothing$, sehingga satu-satunya relasi pada $\varnothing$ adalah $\varnothing$, dan relasi ini ekuivalensi secara vakum. $\mathcal P(\varnothing)=\{\varnothing\}$ mempunyai dua himpunan bagian, yaitu $\varnothing$ dan $\{\varnothing\}$. Menurut Contoh 4.2.12, hanya $\varnothing$ yang partisi.

Pemeriksaan langsung Teorema 4.2.20(a): untuk partisi $\Pi=\varnothing$, relasi $\sim_\Pi\subseteq\varnothing\times\varnothing=\varnothing$, jadi $\sim_\Pi$ adalah relasi kosong. Keluarga kelasnya kosong karena syarat pemisah menuntut saksi $a\in\varnothing$. Jadi $\mathcal K_{\sim_\Pi}=\varnothing=\Pi$.

Pemeriksaan langsung Teorema 4.2.20(b): untuk relasi $\sim\;=\varnothing$, keluarga kelas $\mathcal K_\sim=\varnothing$ dengan alasan yang sama. Relasi yang dibentuk dari partisi kosong ini termuat dalam $\varnothing\times\varnothing=\varnothing$, sehingga sama dengan relasi awal $\varnothing$.

4.2.33. $\mathcal P(A)=\{\varnothing,\{\varnothing\}\}$, sehingga himpunan bagiannya ada empat: $\varnothing$, $\{\varnothing\}$, $\{\{\varnothing\}\}$, $\{\varnothing,\{\varnothing\}\}$.

• $\varnothing$: $\bigcup\varnothing=\varnothing\ne A$, sebab $\varnothing\in A$. Bukan partisi.
• $\{\varnothing\}$: bloknya kosong. Bukan partisi.
• $\{\{\varnothing\}\}$: satu blok $\{\varnothing\}=A$, tak kosong, dengan gabungan $A$. Ini partisi.
• $\{\varnothing,\{\varnothing\}\}$: memuat blok kosong. Bukan partisi.

Jadi satu-satunya partisi adalah $\{A\}=\{\{\varnothing\}\}$. Objek $\varnothing$ di sini adalah anggota $A$, dan sebagai blok ia ditolak oleh (P1). Selanjutnya, $A\times A=\{(\varnothing,\varnothing)\}$, sehingga relasi pada $A$ ada dua: $\varnothing$, yang tidak refleksif karena $A\ne\varnothing$, dan $\{(\varnothing,\varnothing)\}$, yang ekuivalensi. Satu ekuivalensi berpadanan dengan satu partisi, sesuai Teorema 4.2.20.

4.2.34. Misalkan $\Pi$ partisi dari $A=\{1,2,3\}$. Menurut Lemma 4.2.10, ada tepat satu blok $B_1\in\Pi$ yang memuat $1$. Karena $1\in B_1\subseteq A$, $B_1$ salah satu dari $\{1\},\{1,2\},\{1,3\},\{1,2,3\}$. Setiap blok $C\in\Pi$ tak kosong menurut (P1). Jadi $C$ memuat suatu $x\in A$, dan menurut Lemma 4.2.10, $C$ adalah blok tunggal yang memuat $x$. Akibatnya $\Pi$ ditentukan penuh oleh blok-blok yang memuat $1$, $2$, dan $3$.

• $B_1=A$: blok yang memuat $2$ dan blok yang memuat $3$ juga $B_1$, sehingga $\Pi=\{A\}$.
• $B_1=\{1,2\}$: blok $C$ yang memuat $3$ berbeda dari $B_1$ karena $3\notin B_1$, sehingga $C\cap B_1=\varnothing$ menurut (P3). Jadi $C\subseteq\{3\}$, dan karena $3\in C$, $C=\{3\}$. Maka $\Pi=\{\{1,2\},\{3\}\}$.
• $B_1=\{1,3\}$: secara serupa, $\Pi=\{\{1,3\},\{2\}\}$.
• $B_1=\{1\}$: blok $C$ yang memuat $2$ berbeda dari $B_1$, sehingga saling lepas dengannya, dan $C\in\{\{2\},\{2,3\}\}$. Jika $C=\{2,3\}$, maka $\Pi=\{\{1\},\{2,3\}\}$. Jika $C=\{2\}$, blok yang memuat $3$ saling lepas dengan $\{1\}$ dan $\{2\}$, sehingga sama dengan $\{3\}$. Maka $\Pi=\{\{1\},\{2\},\{3\}\}$.

Sebaliknya, kelima keluarga ini memenuhi (P1)–(P3). Setiap bloknya tak kosong dan termuat dalam $A$; gabungan blok-blok tiap keluarga adalah $\{1,2,3\}$, seperti terlihat langsung dari daftarnya; dan blok-blok yang berbeda dalam satu keluarga tidak berbagi anggota. Kelima keluarga juga saling berbeda, karena blok yang memuat $1$ atau blok yang memuat $2$ berbeda di antara mereka. Jadi partisi dari $\{1,2,3\}$ tepat lima.

Menurut Teorema 4.2.20, partisi yang berbeda menghasilkan ekuivalensi yang berbeda, dan setiap ekuivalensi berasal dari suatu partisi. Jadi ada tepat lima relasi ekuivalensi pada $\{1,2,3\}$. Relasi $R$ berpadanan dengan $\{\{1,2\},\{3\}\}$ (Contoh 4.2.22).

4.2.35. Andaikan $x\sim y$ untuk suatu $x\in[a]$ dan $y\in[b]$. Akibat 4.2.6(b) memberi $[x]=[a]$ dan $[y]=[b]$. Teorema 4.2.5 memberi $[x]=[y]$. Jadi $[a]=[b]$, bertentangan dengan hipotesis.

Menuju 4.3

Teorema 4.2.15 memberi himpunan sah $\mathcal K_\sim\subseteq\mathcal P(A)$ yang anggotanya adalah kelas-kelas, bukan wakil-wakilnya. Di 4.3 himpunan ini diberi nama himpunan kuosien dan dilambangkan $A/{\sim}$. Konstruksinya tidak perlu diulang, karena keberadaannya sudah dijamin oleh separasi pada $\mathcal P(A)$. Aturan $a\mapsto[a]$ dapat dipandang sebagai pratinjau fungsi: setiap $a$ menentukan tepat satu kelas, dan setiap kelas mempunyai sekurang-kurangnya satu wakil. Dari sini belum dapat disimpulkan adanya satu pilihan wakil serentak untuk semua kelas.

Akibat 4.2.6 sekaligus memunculkan persoalan utama unit berikutnya. Karena satu kelas dapat mempunyai beberapa wakil, setiap aturan yang didefinisikan melalui wakil harus diperiksa agar hasilnya tidak bergantung pada wakil yang dipilih. Di 4.3 pemeriksaan ini disebut sifat terdefinisi dengan baik (well-defined). Contoh utamanya adalah kongruensi modulo bilangan bulat positif $m$.

4.3 Kelas Ekuivalensi dan Himpunan Kuosien

Di 4.2 kita membuktikan bahwa relasi ekuivalensi $\sim$ pada himpunan $A$ memecah $A$ menjadi kelas-kelas yang saling lepas. Unit ini memakai pecahan itu untuk membentuk objek baru. Gagasannya adalah memperlakukan unsur-unsur yang setara sebagai satu objek. Dalam aritmetika jam, misalnya, kita tidak membedakan $3$, $8$, $13$, dan $-2$ jika yang penting hanya sisa pembagiannya oleh $5$. Secara informal, kita juga tidak membedakan dua pecahan yang menyatakan rasio yang sama. Bilangan rasional belum dibangun dalam buku ini, jadi contoh ini hanya motivasi.

Ada dua cara keliru untuk "mengidentifikasi". Cara pertama adalah berpura-pura bahwa $3=8$. Ini salah, karena keduanya tetap bilangan bulat yang berbeda. Cara kedua adalah memilih satu nama untuk setiap golongan dan membuang sisanya. Cara ini memerlukan pemilihan wakil dari setiap golongan, dan pemilihan semacam itu tidak selalu dapat dibenarkan tanpa argumen tambahan. Cara yang sah lebih sederhana: objek barunya adalah kelas itu sendiri, yaitu himpunan semua unsur yang setara. Dua bilangan yang setara tidak menjadi sama. Yang sama adalah kelasnya, dan kesamaan kelas sudah dicirikan di 4.2:

$$[a]=[b]\iff a\sim b .$$

Himpunan kuosien

Definisi 4.3.1 (himpunan kuosien). Misalkan $\sim$ relasi ekuivalensi pada himpunan $A$. Himpunan kuosien $A$ oleh $\sim$ adalah

$$A/{\sim}\;:=\;\{B\in\mathcal P(A):\exists a\in A\;\forall x\;(x\in B\leftrightarrow(x\in A\land x\sim a))\}.$$

Himpunan ini ada karena dibentuk dengan separasi pada himpunan kuasa $\mathcal P(A)$, yang keberadaannya sudah dijamin di Bab 3. Ini adalah keluarga kelas $\mathcal K_\sim$ yang dibentuk di 4.2, sehingga $A/{\sim}=\mathcal K_\sim$. Kita memakai singkatan

$$A/{\sim}=\{[a]:a\in A\},$$

dengan pengertian bahwa $B\in A/{\sim}$ jika dan hanya jika $B=[a]$ untuk suatu $a\in A$. Singkatan ini bukan komprehensi baru tanpa pembatas. Ia hanya cara lain menuliskan himpunan yang sudah dibatasi oleh $\mathcal P(A)$.

Ada dua hal yang perlu ditekankan.

1. Anggota $A/{\sim}$ adalah kelas-kelas yang merupakan himpunan bagian $A$. Keanggotaan suatu kelas dalam $A$ tidak mengikuti definisi kuosien. Kalimat "$[a]\in A/{\sim}$" benar untuk $a\in A$. Kalimat "$a\in A/{\sim}$" memerlukan pemeriksaan tersendiri dan bukan arti notasi kelas tersebut.
2. Lambang $[a]$ adalah nama kelas, dan satu kelas dapat mempunyai banyak nama. Jika $a\sim b$ dan $a\ne b$, maka $[a]$ dan $[b]$ adalah dua nama untuk satu objek. Jadi banyaknya anggota kuosien tidak dapat dihitung dengan menghitung nama-nama wakil.

Proposisi 4.3.2 (setiap anggota kelas mewakilinya). Misalkan $C\in A/{\sim}$ dan $c\in C$. Maka $C=[c]$. Akibatnya, jika $c,c'\in C$, maka $c\sim c'$.

Bukti. Karena $C\in A/{\sim}$, ada $a\in A$ dengan $C=[a]$. Dari $c\in[a]$ diperoleh $c\sim a$. Menurut 4.2, $c\sim a$ berakibat $[c]=[a]=C$. Untuk bagian kedua, $[c]=C=[c']$, sehingga $c\sim c'$, juga menurut 4.2. $\square$

Proposisi ini memberi isi pada ungkapan "ambil sembarang wakil". Setiap kelas tidak kosong karena $a\in[a]$, jadi kita dapat mengambil satu unsur $c\in C$. Unsur mana pun yang diambil, kelas yang ditentukannya tetap $C$.

Contoh 4.3.3. (a) Pada $A=\{1,2,3\}$, ambil relasi dari 4.1:

$$R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}=(C\times C)\cup(D\times D),\qquad C=\{1,2\},\;D=\{3\}.$$

Di 4.2 sudah diperiksa bahwa $[1]=[2]=\{1,2\}$ dan $[3]=\{3\}$. Jadi

$$A/R=\{\{1,2\},\{3\}\}.$$

Himpunan ini mempunyai dua anggota, walaupun ada tiga nama wakil $[1],[2],[3]$.

(b) Pada $A=\varnothing$, relasi kosong adalah ekuivalensi. Syarat "$\exists a\in\varnothing\,(\dots)$" selalu salah, sehingga $\varnothing/{\sim}=\varnothing$. Hasilnya bukan $\{\varnothing\}$, karena $\varnothing$ bukan kelas dari unsur mana pun.

Catatan 4.3.4 (proyeksi; pratinjau Bab 5). Aturan $a\mapsto[a]$ disebut proyeksi dari $A$ ke $A/{\sim}$. Ada dua fakta tentangnya. Pertama, setiap $a\in A$ menentukan tepat satu kelas, yaitu $[a]$. Kedua, setiap kelas $C$ sama dengan $[c]$ untuk suatu $c\in A$, karena kelas tidak kosong dan Proposisi 4.3.2 berlaku. Grafik aturan ini, $\{(a,[a]):a\in A\}$, dapat dibentuk dengan separasi pada $A\times(A/{\sim})$. Pembahasan fungsi secara resmi, termasuk istilah surjeksi, menunggu Bab 5.

Yang tidak kita klaim adalah arah sebaliknya, yaitu adanya aturan yang memilih satu wakil tertentu dari setiap kelas sekaligus. Fakta "setiap kelas tak kosong" hanya mengizinkan kita mengambil wakil dari kelas yang sedang ditinjau. Fakta itu tidak memberi pilihan serentak untuk semua kelas. Unit ini tidak memerlukan pilihan serentak. Pada contoh modulo $m$ di bawah, pembagian Euclid justru memberi wakil kanonik yang didefinisikan secara eksplisit, sehingga tidak ada pemilihan yang perlu dibenarkan.

Kongruensi modulo $m$

Bilangan bulat dan aritmetika elementernya (penjumlahan, perkalian, urutan $<$, nilai mutlak, dan hukum-hukum yang biasa) dipinjam di sini sebagai bahan contoh. Konstruksinya dari teori himpunan dilakukan kemudian. Sepanjang bagian ini, $m$ adalah bilangan bulat dengan $m>0$. Rumusan ini dipilih dengan sengaja. Kita tidak menulis $m\in\mathbb N$, karena dengan konvensi buku $\mathbb N=\{0,1,2,\ldots\}$ rumusan itu akan memasukkan $m=0$.

Definisi 4.3.5. Untuk $m,t\in\mathbb Z$, tulis $m\mid t$ (dibaca "$m$ membagi $t$") jika ada $k\in\mathbb Z$ dengan $t=mk$. Bilangan $k$ disebut saksi. Untuk $x,y\in\mathbb Z$ dan $m>0$ didefinisikan

$$x\equiv y\pmod m\quad:\Longleftrightarrow\quad m\mid(x-y).$$

Sebagai himpunan, relasinya adalah $\{(x,y)\in\mathbb Z\times\mathbb Z: m\mid(x-y)\}$, yang dibentuk dengan separasi pada $\mathbb Z\times\mathbb Z$. Kelas $x$ terhadap relasi ini ditulis $[x]$, atau $[x]_m$ bila modulusnya perlu disebut. Kuosiennya ditulis $\mathbb Z/m\mathbb Z$. Lambang ini dibaca sebagai satu nama untuk $\mathbb Z/{\equiv_m}$. Alasan penamaannya terlihat dari Proposisi 4.3.7, dengan $m\mathbb Z:=0+m\mathbb Z=[0]$.

Proposisi 4.3.6. Untuk setiap bilangan bulat $m>0$, relasi $\equiv\pmod m$ adalah relasi ekuivalensi pada $\mathbb Z$.

Bukti. Ambil sembarang $x,y,z\in\mathbb Z$.

Refleksif. $x-x=0=m\cdot 0$. Saksi $k=0$ menunjukkan $m\mid(x-x)$, jadi $x\equiv x$.

Simetris. Misalkan $x\equiv y$, yaitu $x-y=mk$ untuk suatu $k\in\mathbb Z$. Maka $y-x=-(x-y)=m(-k)$, dan $-k\in\mathbb Z$. Jadi $y\equiv x$.

Transitif. Misalkan $x\equiv y$ dan $y\equiv z$, yaitu $x-y=mk$ dan $y-z=m\ell$ untuk suatu $k,\ell\in\mathbb Z$. Maka

$$x-z=(x-y)+(y-z)=mk+m\ell=m(k+\ell),$$

dan $k+\ell\in\mathbb Z$. Jadi $x\equiv z$. $\square$

Bukti ini tidak memakai pembagian Euclid. Bukti ini juga tidak memakai syarat $m>0$. Syarat itu baru diperlukan saat kita menghitung kelas (lihat Catatan 4.3.13).

Proposisi 4.3.7 (deskripsi kelas). Untuk $r\in\mathbb Z$ didefinisikan, dengan separasi pada $\mathbb Z$,

$$r+m\mathbb Z:=\{x\in\mathbb Z:\exists k\in\mathbb Z\;(x=r+mk)\},$$

yang biasa ditulis $\{r+mk:k\in\mathbb Z\}$. Maka

$$[r]=\{x\in\mathbb Z:m\mid(x-r)\}=r+m\mathbb Z .$$

Bukti. Kesamaan pertama adalah definisi kelas: $x\in[r]$ jika dan hanya jika $x\in\mathbb Z$ dan $x\equiv r$, yaitu $m\mid(x-r)$. Kesamaan kedua dibuktikan dengan dua inklusi.

($\subseteq$) Jika $x\in[r]$, ada $k\in\mathbb Z$ dengan $x-r=mk$. Maka $x=r+mk$, sehingga $x\in r+m\mathbb Z$.

($\supseteq$) Jika $x\in r+m\mathbb Z$, ada $k\in\mathbb Z$ dengan $x=r+mk$. Maka $x-r=mk$, sehingga $m\mid(x-r)$ dan $x\in[r]$. $\square$

Bentuk $r+m\mathbb Z$ adalah deskripsi lain dari himpunan yang keberadaannya sudah dijamin. Ia bukan cara kedua untuk membentuk objek tersebut.

Pembagian Euclid sebagai prasyarat yang dinyatakan

Untuk membuktikan bahwa ada tepat $m$ kelas, kita perlu dua fakta. Pertama, setiap bilangan bulat setara dengan salah satu dari $0,1,\ldots,m-1$. Kedua, bilangan-bilangan itu tidak saling setara. Fakta pertama memerlukan suatu sifat bilangan bulat yang belum kita buktikan, jadi kita menyatakannya secara terbuka.

Lemma 4.3.8. Misalkan $m>0$, $t\in\mathbb Z$, $m\mid t$, dan $|t|<m$. Maka $t=0$.

Bukti. Tulis $t=mk$ dengan $k\in\mathbb Z$. Andaikan $k\ne0$. Bilangan bulat tak nol memenuhi $|k|\ge1$; ini sifat aritmetika $\mathbb Z$ yang dipinjam. Maka $|t|=m|k|\ge m$, yang bertentangan dengan $|t|<m$. Jadi $k=0$ dan $t=0$. $\square$

Teorema 4.3.9 (pembagian Euclid; dipinjam). Untuk setiap $x\in\mathbb Z$ dan setiap bilangan bulat $m>0$, ada tepat satu pasangan $q,r\in\mathbb Z$ dengan

$$x=mq+r\qquad\text{dan}\qquad 0\le r<m .$$

Status teorema ini. Hasil ini dipinjam dari aritmetika bilangan bulat. Bukti di bawah memakai prinsip urutan baik untuk $\mathbb N$: setiap himpunan bagian tak kosong dari $\mathbb N$ mempunyai unsur terkecil. Prinsip ini baru dikembangkan di Bab 7. Jadi bukti ini sah dengan syarat prinsip tersebut diterima. Selain urutan baik, bukti memakai sifat-sifat $\mathbb Z$ yang dipinjam: $\mathbb N\subseteq\mathbb Z$, bilangan bulat positif paling sedikit $1$, dan hasil kali dua bilangan bulat tak nol tidak nol. Bukti ini tidak memakai fungsi lantai, karena keberadaannya belum dijamin di buku ini.

Bukti (dengan prasyarat urutan baik).

Keberadaan. Bentuk dengan separasi pada $\mathbb N$:

$$S:=\{n\in\mathbb N:\exists q\in\mathbb Z\;(n=x-mq)\}.$$

Himpunan $S$ tidak kosong. Ambil $q=-|x|$, sehingga $x-mq=x+m|x|$. Karena $m\ge1$ dan $|x|\ge0$, berlaku $x+m|x|\ge x+|x|\ge0$. Jadi bilangan ini anggota $\mathbb N$ dan anggota $S$. Menurut urutan baik, $S$ mempunyai unsur terkecil $r$. Tulis $r=x-mq_0$ untuk suatu $q_0\in\mathbb Z$. Karena $r\in\mathbb N$, berlaku $r\ge0$. Andaikan $r\ge m$. Maka $r-m\in\mathbb N$ dan

$$r-m=x-m(q_0+1),$$

sehingga $r-m\in S$ dan $r-m<r$. Ini bertentangan dengan pemilihan $r$ sebagai unsur terkecil. Jadi $0\le r<m$, dan $x=mq_0+r$.

Ketunggalan. Misalkan $x=mq+r=mq'+r'$ dengan $0\le r,r'<m$. Maka $r'-r=m(q-q')$, sehingga $m\mid(r'-r)$. Dari $0\le r,r'<m$ diperoleh $-m<r'-r<m$, yaitu $|r'-r|<m$. Menurut Lemma 4.3.8, $r'-r=0$, jadi $r=r'$. Akibatnya $m(q-q')=0$. Karena $m\ne0$ dan hasil kali dua bilangan bulat tak nol tidak nol, berlaku $q-q'=0$, yaitu $q=q'$. $\square$

Tepat $m$ kelas

Teorema 4.3.10. Untuk setiap bilangan bulat $m>0$:

(a) $\mathbb Z/m\mathbb Z=\{[0],[1],\ldots,[m-1]\}$;

(b) untuk $0\le r,s<m$, jika $[r]=[s]$ maka $r=s$. Dengan kata lain, kelas-kelas pada daftar (a) berbeda satu sama lain, dan menurut 4.2 dua kelas yang berbeda saling lepas.

Di sini $\{[0],\ldots,[m-1]\}$ menyingkat $\{C\in\mathbb Z/m\mathbb Z:\exists r\in\mathbb Z\,(0\le r<m\land C=[r])\}$, yang dibentuk dengan separasi. Jadi kuosien terdiri dari tepat $m$ kelas, yaitu $[0],\ldots,[m-1]$. Selain itu, setiap kelas memuat tepat satu bilangan $r$ dengan $0\le r<m$. Bilangan itu disebut wakil kanonik kelas tersebut.

Bukti. (a) Kedua inklusi dibuktikan terpisah.

($\supseteq$) Ambil $r\in\mathbb Z$ dengan $0\le r<m$. Maka $[r]\in\mathbb Z/m\mathbb Z$.

($\subseteq$) Ambil $C\in\mathbb Z/m\mathbb Z$, jadi $C=[x]$ untuk suatu $x\in\mathbb Z$. Menurut Teorema 4.3.9, ada $q,r$ dengan $x=mq+r$ dan $0\le r<m$. Maka $x-r=mq$, sehingga $x\equiv r$ dan $[x]=[r]$ menurut 4.2. Jadi $C$ ada pada daftar.

(b) Jika $[r]=[s]$, maka $r\equiv s$, yaitu $m\mid(r-s)$. Karena $0\le r,s<m$, berlaku $|r-s|<m$. Menurut Lemma 4.3.8, $r-s=0$.

Wakil kanonik. Setiap $C$ memuat suatu $r$ dengan $0\le r<m$: menurut (a), $C=[r]$ untuk suatu $r$ seperti itu, dan $r\in[r]=C$. Jika $r,s\in C$ dengan $0\le r,s<m$, Proposisi 4.3.2 memberi $r\equiv s$, jadi $[r]=[s]$, dan menurut (b) $r=s$. $\square$

Ada tiga catatan tentang bukti ini.

• Bagian (a) hanya memakai keberadaan dalam Teorema 4.3.9. Bagian (b) tidak memakai teorema itu, hanya Lemma 4.3.8. Isi bagian (b) sebenarnya adalah ketunggalan sisa.
• Wakil kanonik suatu kelas $C$ dapat didefinisikan secara eksplisit sebagai satu-satunya $r\in C$ dengan $0\le r<m$. Karena itu, modulo $m$ kita mempunyai pemilihan wakil yang serentak tanpa aksioma pilihan, karena pemilihan itu ditentukan oleh rumus. Pemilihan itu tetap bergantung pada Teorema 4.3.9 yang dipinjam. Kelebihan ini khusus untuk contoh ini dan tidak berlaku untuk sembarang ekuivalensi.
• Ungkapan "tepat $m$" di sini berarti dua hal: daftar pada (a) menghabiskan kuosien, dan suku-suku daftar itu saling berbeda. Perumusan resmi tentang banyaknya unsur, melalui korespondensi satu-satu dengan $\{0,\ldots,m-1\}$, memerlukan bahasa fungsi di Bab 5 dan induksi di Bab 7.

Peringatan. Kuosien $\mathbb Z/5\mathbb Z$ tidak boleh disamakan dengan $\{0,1,2,3,4\}$. Anggota $\{0,1,2,3,4\}$ adalah bilangan bulat, yaitu wakil kanonik. Anggota $\mathbb Z/5\mathbb Z$ adalah kelas, yaitu himpunan bagian $\mathbb Z$ seperti $[0]=\{x\in\mathbb Z:5\mid(x-0)\}$, yang memuat $0,5,-5,10,\ldots$. Hubungan yang benar antara keduanya adalah korespondensi $r\mapsto[r]$, bukan kesamaan. Perlakukan setiap pernyataan tentang kelas sebagai pernyataan tentang himpunan, bukan tentang satu bilangan.

Contoh 4.3.11 ($m=5$). Kelima kelasnya adalah

$$\begin{aligned} [0]&=\{\ldots,-10,-5,0,5,10,\ldots\}, & [1]&=\{\ldots,-9,-4,1,6,11,\ldots\},\\ [2]&=\{\ldots,-8,-3,2,7,12,\ldots\}, & [3]&=\{\ldots,-7,-2,3,8,13,\ldots\},\\ [4]&=\{\ldots,-6,-1,4,9,14,\ldots\}. \end{aligned}$$

Penulisan dengan elipsis di atas hanya ilustrasi. Definisi resminya adalah $[r]=\{x\in\mathbb Z:5\mid(x-r)\}$. Misalnya $[3]=\{x\in\mathbb Z:5\mid(x-3)\}$. Beberapa perhitungan:

• $-7=5\cdot(-2)+3$ dengan $0\le3<5$, sehingga $[-7]=[3]$. Pemeriksaan langsung: $-7-3=-10=5\cdot(-2)$.
• Persamaan $-7=5\cdot(-1)+(-2)$ juga benar, tetapi $-2$ bukan sisa Euclid karena $-2<0$. Persamaan itu tetap menunjukkan $-7\equiv-2$. Ini konsisten dengan $[-2]=[3]$, sebab $-2=5\cdot(-1)+3$.
• $13=5\cdot2+3$, sehingga $[13]=[3]=[-7]$. Jadi $3$, $13$, dan $-7$ adalah tiga nama untuk satu kelas.
• $-1=5\cdot(-1)+4$, sehingga $[-1]=[4]$. Juga $-10=5\cdot(-2)+0$, sehingga $[-10]=[0]$.

Contoh 4.3.12 ($m=1$). Untuk setiap $x,y\in\mathbb Z$ berlaku $x-y=1\cdot(x-y)$, jadi $1\mid(x-y)$. Maka $[x]=\mathbb Z$ untuk setiap $x$, dan

$$\mathbb Z/1\mathbb Z=\{\mathbb Z\}=\{[0]\}.$$

Kuosien ini mempunyai satu anggota, sesuai dengan Teorema 4.3.10 untuk $m=1$: satu-satunya sisa dengan $0\le r<1$ adalah $r=0$.

Catatan 4.3.13 (mengapa $m=0$ dikeluarkan, dan $m$ negatif tidak diperlukan).

Kasus $m=0$. Definisi $0\mid t$ tetap bermakna, dan berarti $t=0\cdot k=0$. Jika rumus Definisi 4.3.5 diterapkan pada $m=0$, maka $x\equiv y\pmod 0$ jika dan hanya jika $x=y$, yaitu relasi kesamaan. Bukti Proposisi 4.3.6 tetap berlaku, sehingga relasi ini masih ekuivalensi, dengan kelas $[x]=\{x\}$. Klaim "tepat $m$ kelas" gagal untuk $m=0$. Pertama, $\mathbb Z\ne\varnothing$, sehingga kuosiennya memuat paling sedikit satu kelas, yaitu $\{0\}$, padahal klaim itu menyatakan tidak ada kelas sama sekali. Alasan ini sudah cukup untuk membantah klaim tersebut. Kedua, kelas-kelas $\{0\},\{1\},\{2\},\ldots$ saling berbeda. Secara intuitif, tidak ada daftar berhingga yang dapat menghabiskannya, tetapi perumusan resmi "berhingga" dan "tak hingga" menunggu Bab 7. Pembagian Euclid juga gagal pada $m=0$, karena syarat $0\le r<0$ mustahil dipenuhi.

Kasus $m<0$. Karena $t=mk$ jika dan hanya jika $t=(-m)(-k)$, berlaku $m\mid t\iff(-m)\mid t$. Jadi modulus $m$ dan $-m$ menghasilkan relasi yang sama. Membuang modulus negatif tidak menghilangkan satu pun relasi kongruensi: setiap relasi modulo $m<0$ sudah muncul sebagai relasi modulo $-m>0$. Yang benar-benar dikeluarkan hanyalah $m=0$, yaitu relasi kesamaan, dengan alasan di atas. Syarat $m>0$ juga membuat syarat sisa $0\le r<m$ bermakna.

Aturan pada kelas dan syarat well-defined

Kita ingin menjumlahkan kelas dengan aturan $[a]+[b]=[a+b]$. Masalahnya, ruas kanan dihitung dari wakil $a$ dan $b$, sedangkan ruas kiri seharusnya hanya bergantung pada kelas. Sebuah kelas mempunyai banyak wakil. Jika wakil yang berbeda menghasilkan kelas hasil yang berbeda, aturan itu tidak menentukan apa pun. Pemeriksaan bahwa hasilnya tidak bergantung pada wakil disebut pemeriksaan well-defined. Pemeriksaan ini wajib dilakukan sebelum aturan dipakai.

Proposisi 4.3.14 (kriteria umum). Misalkan $\sim$ ekuivalensi pada $A$, dan misalkan suatu aturan memberi setiap $a\in A$ tepat satu objek $f(a)$ di himpunan $Y$. Maka dua pernyataan berikut setara:

1. untuk setiap $C\in A/{\sim}$ ada tepat satu $y\in Y$ sehingga $y=f(c)$ untuk setiap $c\in C$;
2. untuk setiap $a,a'\in A$: $a\sim a'\Rightarrow f(a)=f(a')$, dengan kesamaan di $Y$.

Bukti. (2 ⇒ 1) Ambil $C\in A/{\sim}$. Kelas itu tidak kosong, jadi ambil satu $c_0\in C$ dan tetapkan $y=f(c_0)$. Untuk sembarang $c\in C$, Proposisi 4.3.2 memberi $c\sim c_0$, sehingga $f(c)=f(c_0)=y$ menurut (2). Nilai $y$ tunggal karena setiap $y'$ yang memenuhi syarat harus sama dengan $f(c_0)$.

(1 ⇒ 2) Misalkan $a\sim a'$. Maka $a,a'\in[a]$. Menurut (1), ada $y$ dengan $f(a)=y=f(a')$. $\square$

Hal terpenting di sini adalah bahwa jenis kesamaan yang diperiksa ditentukan oleh himpunan sasaran $Y$. Jika $Y=\mathbb Z$, yang diperiksa adalah kesamaan bilangan. Jika $Y=\mathbb Z/m\mathbb Z$, yang diperiksa adalah kesamaan kelas, yaitu kongruensi wakil-wakilnya. Proposisi ini hanya pratinjau. Bahasa fungsi yang resmi ada di Bab 5.

Lemma 4.3.15 (kompatibilitas). Misalkan $m>0$ dan $a,a',b,b'\in\mathbb Z$ memenuhi $a\equiv a'$ dan $b\equiv b'\pmod m$. Maka

$$a+b\equiv a'+b'\qquad\text{dan}\qquad ab\equiv a'b'\pmod m .$$

Bukti. Tulis $a-a'=mk$ dan $b-b'=m\ell$ dengan $k,\ell\in\mathbb Z$.

Penjumlahan:

$$(a+b)-(a'+b')=(a-a')+(b-b')=mk+m\ell=m(k+\ell).$$

Perkalian: dengan menambah dan mengurangkan $a'b$,

$$ab-a'b'=(ab-a'b)+(a'b-a'b')=(a-a')b+a'(b-b')=mkb+a'm\ell=m(kb+a'\ell).$$

Karena $k+\ell$ dan $kb+a'\ell$ bilangan bulat, kedua selisih habis dibagi $m$. $\square$

Definisi 4.3.16 (penjumlahan dan perkalian kelas). Untuk $C,D\in\mathbb Z/m\mathbb Z$, definisikan $C\oplus D$ sebagai satu-satunya $E\in\mathbb Z/m\mathbb Z$ sehingga $E=[a+b]$ untuk suatu $a\in C$ dan $b\in D$. Definisikan $C\odot D$ dengan cara yang sama memakai $[ab]$.

Definisi ini sah karena dua alasan.

Keberadaan. $C$ dan $D$ tidak kosong. Ambil satu $a\in C$ dan satu $b\in D$; ini dua pengambilan dari dua himpunan tertentu, bukan pemilihan serentak. Maka $E=[a+b]$ memenuhi syarat.

Ketunggalan. Misalkan $E=[a+b]$ dan $E'=[a'+b']$ dengan $a,a'\in C$ dan $b,b'\in D$. Menurut Proposisi 4.3.2, $a\equiv a'$ dan $b\equiv b'$. Menurut Lemma 4.3.15, $a+b\equiv a'+b'$, sehingga $E=E'$ menurut 4.2. Argumen yang sama, dengan bagian perkalian Lemma 4.3.15, berlaku untuk $\odot$.

Akibatnya aturan $[a]\oplus[b]=[a+b]$ dan $[a]\odot[b]=[ab]$ berlaku untuk setiap pilihan wakil. Kita tidak akan mengembangkan sifat-sifat aljabar operasi ini (asosiatif, distributif, dan seterusnya) di bab ini.

Contoh 4.3.17 (modulo 5). $[8]\oplus[-7]=[8+(-7)]=[1]$. Karena $8=5\cdot1+3$ dan $-7=5\cdot(-2)+3$, wakil kanonik kedua kelas adalah $3$ dan $3$. Dengan wakil itu, $[3]\oplus[3]=[6]$, dan $6=5\cdot1+1$, sehingga $[6]=[1]$. Hasilnya sama.

$[8]\odot[-7]=[-56]$, dan $-56=5\cdot(-12)+4$, sehingga hasilnya $[4]$. Dengan wakil $3,3$ diperoleh $[9]$, dan $9=5\cdot1+4$, sehingga $[9]=[4]$. Hasilnya sama.

Contoh 4.3.18 (aturan yang gagal: "ambil wakilnya"). Misalkan kita mencoba mendefinisikan aturan $F$ dari $\mathbb Z/m\mathbb Z$ ke $\mathbb Z$ dengan $F([a])=a$. Sasarannya $\mathbb Z$, jadi yang harus diperiksa adalah kesamaan bilangan. Untuk $m>0$ berlaku $m-0=m\cdot1$, sehingga $[0]=[m]$. Aturan itu memberi $F([0])=0$ dan $F([m])=m$ untuk kelas yang sama, padahal $0\ne m$. Syarat (2) Proposisi 4.3.14 gagal, sehingga "$F$" tidak menetapkan nilai. Kegagalan ini tidak bertentangan dengan adanya wakil kanonik. Aturan "kirim $C$ ke satu-satunya $r\in C$ dengan $0\le r<m$" sah, karena aturan itu tidak bergantung pada nama $[a]$ yang dipakai.

Contoh 4.3.19 (relasi yang gagal: urutan pada kelas modulo 2). Misalkan kita mencoba mendefinisikan "$[a]\prec[b]$ jika $a<b$" pada $\mathbb Z/2\mathbb Z$. Dengan wakil $0$ dan $1$ berlaku $0<1$, jadi $[0]\prec[1]$. Tetapi $[0]=[2]$, karena $2-0=2\cdot1$, dan dengan wakil $2$ dan $1$ berlaku $2\not<1$. Jadi kebenaran "$[0]\prec[1]$" bergantung pada wakil yang dipilih. Aturan ini tidak mendefinisikan relasi pada kelas.

Ada dua cara yang tampak wajar untuk memperbaiki aturan itu, tetapi keduanya tidak memuaskan.

• Versi "untuk suatu wakil", yaitu $C\prec D$ jika ada $a\in C$ dan $b\in D$ dengan $a<b$, memang mendefinisikan suatu himpunan, tetapi hasilnya trivial. Untuk $C=[a]$ dan $D=[b]$, bilangan $b'=b+2(|a-b|+1)$ anggota $D$, karena $b'-b=2(|a-b|+1)$, dan memenuhi $b'\ge b+(a-b)+2>a$. Jadi $C\prec D$ untuk semua $C,D$, termasuk $[0]\prec[0]$.
• Versi "untuk semua wakil", yaitu $C\prec D$ jika $a<b$ untuk setiap $a\in C$ dan $b\in D$, tidak pernah berlaku. Untuk sembarang $C=[a]$ dan $D=[b]$, wakil $a'=a+2(|a-b|+1)\in C$ memenuhi $a'\ge a+(b-a)+2>b$, sehingga syarat "$a'<b$" gagal.

Urutan $<$ pada $\mathbb Z$ tidak dapat diturunkan ke kuosien begitu saja.

---

Latihan

Latihan 4.3.20. Tentukan $A/R$ untuk $A=\{1,2,3\}$ dan $R$ seperti di Contoh 4.3.3. Tentukan juga kuosien relasi kosong pada $\varnothing$. Untuk masing-masing, bandingkan banyaknya nama wakil $[a]$ dengan banyaknya kelas, dan jelaskan kapan keduanya berbeda.

Latihan 4.3.21. Buktikan $\mathbb Z/1\mathbb Z=\{\mathbb Z\}$ tanpa memakai Teorema 4.3.10.

Latihan 4.3.22. Modulo 5, tentukan $q$ dan sisa Euclid $r$ untuk $x=-1,-13,-25,23$. Tuliskan kelas masing-masing sebagai salah satu dari $[0],\ldots,[4]$, dan periksa jawabanmu dengan definisi $5\mid(x-r)$.

Latihan 4.3.23. Buktikan secara langsung bahwa $\mathbb Z/4\mathbb Z=\{[0],[1],[2],[3]\}$ dan bahwa keempat kelas itu saling berbeda. Apakah $[2]=[-1]$?

Latihan 4.3.24. Modulo 3, buktikan dengan dua inklusi bahwa $[-2]=1+3\mathbb Z$.

Latihan 4.3.25. Buktikan bahwa aturan $-[a]:=[-a]$ well-defined pada $\mathbb Z/m\mathbb Z$. Simpulkan bahwa $[a]\ominus[b]:=[a-b]$ juga well-defined.

Latihan 4.3.26. (a) Tunjukkan bahwa aturan $h([a]_5)=[a]_3$ dari $\mathbb Z/5\mathbb Z$ ke $\mathbb Z/3\mathbb Z$ tidak well-defined. (b) Tunjukkan bahwa $g([a]_6)=[a]_3$ dari $\mathbb Z/6\mathbb Z$ ke $\mathbb Z/3\mathbb Z$ well-defined.

Latihan 4.3.27. Untuk wakil $a\in\mathbb Z$ dan wakil eksponen $b\in\mathbb N$ dengan $b\ge1$, usulkan aturan "$[a]^{[b]}=[a^b]$" modulo 5. Tunjukkan dengan contoh terhitung bahwa aturan ini tidak well-defined terhadap wakil eksponen.

Latihan 4.3.28. Tentukan kelas-kelas relasi yang diperoleh dengan menerapkan rumus Definisi 4.3.5 pada $m=0$. Jelaskan mengapa Teorema 4.3.10 tidak dapat diperluas ke $m=0$. Tunjukkan juga bahwa rumus yang sama untuk $m=-5$ menghasilkan relasi yang sama dengan modulo $5$.

Latihan 4.3.29. Misalkan seseorang menyatakan: "$\mathbb Z/5\mathbb Z$ mempunyai lebih dari lima anggota, sebab $[0],[5],[10],[3],[-7],[1],[2],[4]$ semuanya anggotanya." Temukan kesalahannya, dan hitung banyaknya kelas yang sebenarnya muncul dalam daftar itu.

---

Pembahasan

4.3.20. Pada $A=\{1,2,3\}$ berlaku $1R2$, sehingga $[1]=[2]=\{1,2\}$. Unsur $3$ hanya berelasi dengan dirinya sendiri, sehingga $[3]=\{3\}$. Jadi $A/R=\{\{1,2\},\{3\}\}$. Ada tiga nama $[1],[2],[3]$, tetapi hanya dua objek, karena $[1]$ dan $[2]$ menamai himpunan yang sama.

Pada $\varnothing$, anggota kuosien adalah himpunan $B\in\mathcal P(\varnothing)=\{\varnothing\}$ yang memenuhi "$\exists a\in\varnothing(\dots)$". Syarat ini salah untuk setiap $B$, sehingga kuosiennya $\varnothing$. Khususnya, $\varnothing$ sendiri bukan anggota kuosien: setiap kelas memuat wakilnya, sehingga tidak ada kelas yang kosong. Pada kasus ini banyaknya nama dan banyaknya kelas sama-sama nol. Perbedaan baru muncul jika ada dua wakil berbeda yang setara, seperti $1$ dan $2$ di atas.

4.3.21. Untuk sembarang $x\in\mathbb Z$, kita tunjukkan $[x]=\mathbb Z$. Inklusi $[x]\subseteq\mathbb Z$ berlaku menurut definisi. Untuk inklusi sebaliknya, ambil $y\in\mathbb Z$. Maka $y-x=1\cdot(y-x)$, sehingga $1\mid(y-x)$ dan $y\in[x]$.

Sekarang buktikan $\mathbb Z/1\mathbb Z=\{\mathbb Z\}$ dengan dua inklusi. ($\subseteq$) Setiap anggota kuosien berbentuk $[x]$, dan $[x]=\mathbb Z$. ($\supseteq$) $\mathbb Z=[0]$ adalah anggota kuosien.

4.3.22.

• $-1=5\cdot(-1)+4$, jadi $q=-1$, $r=4$, dan $[-1]=[4]$. Pemeriksaan: $-1-4=-5=5\cdot(-1)$.
• $-13=5\cdot(-3)+2$, jadi $q=-3$, $r=2$, dan $[-13]=[2]$. Pemeriksaan: $-13-2=-15=5\cdot(-3)$.
• $-25=5\cdot(-5)+0$, jadi $q=-5$, $r=0$, dan $[-25]=[0]$. Pemeriksaan: $-25-0=5\cdot(-5)$.
• $23=5\cdot4+3$, jadi $q=4$, $r=3$, dan $[23]=[3]$. Pemeriksaan: $23-3=20=5\cdot4$.

Pada setiap kasus, $0\le r<5$. Persamaan seperti $-13=5\cdot(-2)+(-3)$ juga benar, tetapi tidak memberi sisa Euclid karena $-3<0$.

4.3.23. Untuk inklusi $\supseteq$: $0,1,2,3\in\mathbb Z$, jadi keempat kelas itu anggota kuosien. Untuk inklusi $\subseteq$: setiap anggota kuosien berbentuk $[x]$. Teorema 4.3.9 dengan $m=4$ memberi $x=4q+r$ dengan $0\le r<4$, sehingga $x-r=4q$ dan $[x]=[r]$ dengan $r\in\{0,1,2,3\}$.

Untuk keberbedaan: jika $[r]=[s]$ dengan $0\le r,s<4$, maka $4\mid(r-s)$ dan $|r-s|\le3<4$. Lemma 4.3.8 memberi $r=s$. Jadi keenam pasangan unsur berbeda dari $\{0,1,2,3\}$ menghasilkan kelas yang berbeda.

Selanjutnya, $-1=4\cdot(-1)+3$, sehingga $[-1]=[3]$. Karena $2\ne3$ dan keduanya sisa yang sah, $[3]\ne[2]$. Jadi $[2]\ne[-1]$. Ini juga dapat diperiksa langsung: $2-(-1)=3$, dan $4\mid3$ akan memberi $3=0$ menurut Lemma 4.3.8, yang mustahil.

4.3.24. ($\subseteq$) Jika $x\in[-2]$, ada $k\in\mathbb Z$ dengan $x+2=3k$. Maka $x=1+3(k-1)$ dan $k-1\in\mathbb Z$, sehingga $x\in1+3\mathbb Z$.

($\supseteq$) Jika $x=1+3j$ untuk suatu $j\in\mathbb Z$, maka $x-(-2)=3+3j=3(j+1)$, sehingga $x\in[-2]$.

Ini sesuai dengan $-2=3\cdot(-1)+1$ dan Proposisi 4.3.7: $[-2]=[1]=1+3\mathbb Z$.

4.3.25. Sasaran aturan $-[a]:=[-a]$ adalah $\mathbb Z/m\mathbb Z$, jadi yang perlu diperiksa adalah kesamaan kelas. Misalkan $a\equiv a'$, yaitu $a-a'=mk$. Maka $(-a)-(-a')=-(a-a')=m(-k)$, sehingga $[-a]=[-a']$. Menurut Proposisi 4.3.14, aturan ini menetapkan tepat satu kelas untuk setiap kelas.

Untuk pengurangan, tulis $a-b=a+(-b)$. Jika $a\equiv a'$ dan $b\equiv b'$, maka $-b\equiv-b'$ menurut bagian sebelumnya. Lemma 4.3.15 (penjumlahan) kemudian memberi $a+(-b)\equiv a'+(-b')$. Jadi $[a-b]=[a'-b']$. Aturan ini melibatkan dua kelas, sehingga Proposisi 4.3.14 tidak langsung berlaku. Keberadaan dan ketunggalan hasil terbukti dengan argumen yang sama seperti pada Definisi 4.3.16, memakai kongruensi yang baru diperoleh sebagai pengganti Lemma 4.3.15.

4.3.26. (a) Sasarannya $\mathbb Z/3\mathbb Z$. Kita mempunyai $[0]_5=[5]_5$, karena $5-0=5\cdot1$. Aturan $h$ memberi $[0]_3$ dan $[5]_3$ untuk kelas yang sama. Sekarang $5=3\cdot1+2$, sehingga $[5]_3=[2]_3$. Selain itu $[2]_3\ne[0]_3$: jika $3\mid2$, Lemma 4.3.8 memberi $2=0$ karena $|2|<3$, yang mustahil. Jadi satu kelas modulo 5 diberi dua nilai berbeda, dan $h$ tidak well-defined.

(b) Misalkan $[a]_6=[a']_6$, yaitu $a-a'=6k$. Maka $a-a'=3(2k)$ dan $2k\in\mathbb Z$, sehingga $[a]_3=[a']_3$. Menurut Proposisi 4.3.14, $g$ well-defined. Inti perbedaannya dengan (a) adalah bahwa $3\mid6$, sedangkan $3\nmid5$.

4.3.27. Modulo 5, $[1]=[6]$ karena $6-1=5$. Dengan wakil eksponen $1$: $[2]^{[1]}=[2^1]=[2]$. Dengan wakil eksponen $6$: $[2^6]=[64]$, dan $64=5\cdot12+4$, sehingga hasilnya $[4]$. Karena $0\le2,4<5$ dan $2\ne4$, Teorema 4.3.10(b) memberi $[2]\ne[4]$. Jadi nilai aturan ini bergantung pada wakil eksponen, dan aturan ini tidak well-defined.

Untuk eksponen tertentu yang ditulis eksplisit, misalnya $b=2$ atau $b=3$, penggantian wakil basis tidak menimbulkan masalah. Lemma 4.3.15 tinggal dipakai berulang sebanyak yang tertulis, misalnya $a^3=(a\cdot a)\cdot a\equiv(a'\cdot a')\cdot a'$. Pernyataan untuk semua $b\in\mathbb N$ dengan $b\ge1$ sekaligus memerlukan induksi (Bab 7). Yang gagal di soal ini adalah penggantian wakil eksponen.

4.3.28. $0\mid(x-y)$ berarti $x-y=0\cdot k=0$, yaitu $x=y$. Jadi $[x]=\{y\in\mathbb Z:y=x\}=\{x\}$, dan kuosiennya $\{\{x\}:x\in\mathbb Z\}$. Teorema 4.3.10 tidak dapat diperluas ke kasus ini karena dua alasan.

1. Teorema itu akan menyatakan adanya tepat $0$ kelas, padahal $\{0\}$ adalah kelas. Bahkan $\{0\}\ne\{1\}$ menurut ekstensionalitas, karena $0\in\{0\}$ tetapi $0\notin\{1\}$. Jadi ada paling sedikit dua kelas.
2. Buktinya bergantung pada Teorema 4.3.9, yang menuntut $0\le r<m$. Untuk $m=0$, syarat itu tidak dapat dipenuhi oleh bilangan apa pun.

Untuk $m=-5$: jika $x-y=(-5)k$, maka $x-y=5(-k)$; sebaliknya, jika $x-y=5k$, maka $x-y=(-5)(-k)$. Jadi kedua relasi sama sebagai himpunan pasangan.

4.3.29. Kesalahannya adalah menghitung nama sebagai objek. Dengan sisa Euclid:

• $[0]=[5]=[10]$, karena $5=5\cdot1+0$ dan $10=5\cdot2+0$;
• $[-7]=[3]$, karena $-7=5\cdot(-2)+3$.

Jadi daftar itu hanya memuat kelas $[0],[1],[2],[3],[4]$, yaitu lima kelas, yang menurut Teorema 4.3.10(b) saling berbeda. Delapan nama dalam daftar menamai lima objek, sesuai dengan Teorema 4.3.10.

---

Menuju 4.4

Relasi ekuivalensi bersifat simetris. Ketiga sifat ekuivalensi menjamin bahwa kelas-kelasnya membentuk partisi. Himpunan kuosien memakai kelas-kelas tersebut sebagai anggotanya. Contoh 4.3.19 memperlihatkan sisi lain: urutan $<$ tidak dapat diturunkan ke kuosien, karena urutan memisahkan unsur-unsur yang oleh kongruensi dianggap setara. Jadi urutan memerlukan sifat lain, yaitu antisimetri: jika $x\preceq y$ dan $y\preceq x$, maka $x=y$. Antisimetri bukan negasi simetri (4.1). Kesamaan bersifat simetris sekaligus antisimetri. Namun pada relasi yang antisimetri, dua unsur berbeda tidak pernah saling berelasi dua arah, sehingga tidak ada yang dapat "dilebur". Relasi keterbagian $\mid$ yang dipakai di unit ini akan muncul lagi di 4.4 sebagai urutan pada bilangan bulat positif. Di sana akan diperiksa mengapa positivitas diperlukan untuk antisimetrinya, dan bagaimana strukturnya digambarkan dengan diagram Hasse.

4.4 Relasi Urutan Parsial dan Diagram Hasse

Unit 4.2 dan 4.3 membahas relasi yang menyamakan. Relasi ekuivalensi mengumpulkan objek ke dalam kelas. Simetri menjamin bahwa jika $x$ setara dengan $y$, maka $y$ setara dengan $x$. Unit ini membahas relasi yang mengurutkan: dua unsur berbeda tidak boleh saling berelasi dua arah. Jika $x$ berada "di bawah" $y$ dan $y$ berada "di bawah" $x$, kita ingin menyimpulkan bahwa keduanya objek yang sama. Itulah peran antisimetri.

Banyak urutan yang wajar tidak membandingkan setiap pasangan objek. Bilangan $2$ dan $3$ tidak saling membagi. Himpunan $\{1\}$ dan $\{2\}$ tidak saling memuat. Dua tugas dalam suatu proyek bisa saja tidak saling bergantung. Karena itu kita mulai dari urutan parsial, dan urutan total diperlakukan sebagai kasus khusus.

Sepanjang unit ini, $S$ adalah himpunan. Sesuai Unit 4.1, relasi pada $S$ berarti himpunan bagian dari $S\times S$. Untuk relasi yang dilambangkan $\preceq$, kita menulis $x\preceq y$ untuk $(x,y)\in{\preceq}$. Bilangan bulat dan aritmetika elementernya dipinjam sebagai contoh, seperti pada unit-unit sebelumnya.

Urutan parsial

Definisi 4.4.1 (urutan parsial, poset). Relasi $\preceq$ pada $S$ disebut urutan parsial jika ia memenuhi tiga sifat berikut.

$$\begin{aligned} \text{refleksif: }&\forall x\in S\;(x\preceq x),\\ \text{antisimetri: }&\forall x,y\in S\;((x\preceq y\land y\preceq x)\Rightarrow x=y),\\ \text{transitif: }&\forall x,y,z\in S\;((x\preceq y\land y\preceq z)\Rightarrow x\preceq z). \end{aligned}$$

Pasangan $(S,\preceq)$ disebut himpunan terurut parsial atau poset.

Definisi ini tidak mensyaratkan $S\neq\varnothing$. Untuk $S=\varnothing$, satu-satunya relasi pada $S$ adalah $\varnothing$, karena $\varnothing\times\varnothing=\varnothing$. Menurut Unit 4.1, ketiga sifat di atas berlaku secara vakum. Jadi $(\varnothing,\varnothing)$ adalah poset, dan kita menyebutnya poset kosong.

Contoh 4.4.2.

(a) $(\mathbb Z,\le)$ adalah poset. Dari aritmetika yang dipinjam, berlaku $x\le x$. Jika $x\le y$ dan $y\le x$, maka $x=y$. Jika $x\le y$ dan $y\le z$, maka $x\le z$.

(b) Untuk himpunan $X$, $(\mathcal P(X),\subseteq)$ adalah poset. Setiap $A\subseteq X$ memenuhi $A\subseteq A$. Jika $A\subseteq B$ dan $B\subseteq C$, setiap anggota $A$ adalah anggota $B$, sehingga juga anggota $C$. Antisimetri tidak lain adalah prinsip dua inklusi dari Bab 3: $A\subseteq B$ dan $B\subseteq A$ memberi $A=B$ melalui ekstensionalitas.

(c) Keterbagian pada bilangan bulat positif adalah poset. Hal ini dibuktikan di bawah.

Untuk $a,b\in\mathbb Z$, tulis $a\mid b$ jika ada $k\in\mathbb Z$ dengan $b=ak$. Ini perluasan rumusan Unit 4.3 ke pembagi $a$ sembarang.

Proposisi 4.4.3. Misalkan $P\subseteq\{n\in\mathbb Z:n>0\}$. Definisikan relasi pada $P$ dengan $a\preceq b$ jika dan hanya jika $a\mid b$. Maka $(P,\preceq)$ adalah poset. Selain itu, untuk $a,b\in P$, $a\mid b$ mengakibatkan $a\le b$.

Bukti.

Refleksif. Untuk $a\in P$, berlaku $a=a\cdot 1$. Jadi $a\mid a$.

Transitif. Misalkan $b=ak$ dan $c=b\ell$ dengan $k,\ell\in\mathbb Z$. Maka $c=a(k\ell)$, dan $k\ell\in\mathbb Z$. Jadi $a\mid c$.

Sebuah lema kecil. Misalkan $a,b\in P$ dan $b=ak$. Maka $k>0$. Seandainya $k\le 0$, maka $ak\le 0$ karena $a>0$. Ini bertentangan dengan $ak=b>0$. Akibatnya $k\ge 1$, sehingga $b=ak\ge a$. Ini membuktikan klaim terakhir proposisi.

Antisimetri. Misalkan $b=ak$ dan $a=b\ell$. Menurut lema, $k\ge1$ dan $\ell\ge1$. Dari kedua persamaan diperoleh $a=a(k\ell)$, sehingga $a(k\ell-1)=0$. Karena $a>0$, berlaku $a\neq0$, sehingga $k\ell=1$. Seandainya $k\ge2$, maka $k\ell\ge 2\ell\ge2$, suatu kontradiksi. Jadi $k=1$ dan $b=a$. $\blacksquare$

Positivitas dipakai pada dua tempat. Pertama, pada lema, untuk menyimpulkan $k>0$. Kedua, untuk menjamin $a\neq0$ pada langkah antisimetri. Positivitas tidak dapat dibuang. Pada seluruh $\mathbb Z$, keterbagian tetap refleksif dan transitif, karena bukti kedua sifat itu tidak memakai tanda. Namun antisimetri gagal. Dari $-2=2\cdot(-1)$ dan $2=(-2)\cdot(-1)$ diperoleh $2\mid -2$ dan $-2\mid 2$, padahal $2\neq-2$. Jadi keterbagian pada $\mathbb Z$ bukan urutan parsial.

Urutan ketat yang bersesuaian

Dalam percakapan sehari-hari, "lebih kecil" sering berarti "lebih kecil dan tidak sama". Kita memformalkan pengertian ini.

Definisi 4.4.4 (bagian ketat, diagonal). Misalkan $(S,\preceq)$ poset. Diagonal $S$ adalah

$$\Delta_S=\{p\in S\times S:\exists x\in S\;(p=(x,x))\}.$$

Bagian ketat dari $\preceq$ adalah

$${\prec}=\{p\in S\times S:\exists x,y\in S\;(p=(x,y)\land x\preceq y\land x\neq y)\}.$$

Jadi $x\prec y$ berarti $x\preceq y$ dan $x\neq y$.

Kedua himpunan ini diperoleh dengan separasi pada $S\times S$, sehingga keberadaannya terjamin. Menurut sifat pasangan berurutan dari Unit 4.1, $(x,y)=(x',x')$ jika dan hanya jika $x=x'$ dan $y=x'$. Akibatnya, untuk $x,y\in S$, berlaku $(x,y)\in\Delta_S$ jika dan hanya jika $x=y$. Fakta ini akan dipakai berulang kali.

Proposisi 4.4.5. Bagian ketat $\prec$ dari suatu urutan parsial memiliki tiga sifat berikut.

• Irrefleksif: tidak ada $x\in S$ dengan $x\prec x$.
• Transitif: jika $x\prec y$ dan $y\prec z$, maka $x\prec z$.
• Asimetris: tidak ada $x,y\in S$ dengan $x\prec y$ dan $y\prec x$.

Bukti.

Irrefleksif. Pernyataan $x\prec x$ mensyaratkan $x\neq x$, dan itu mustahil.

Transitif. Misalkan $x\prec y$ dan $y\prec z$. Dari $x\preceq y$ dan $y\preceq z$, transitivitas $\preceq$ memberi $x\preceq z$. Tinggal ditunjukkan $x\neq z$. Seandainya $x=z$, maka $y\preceq z$ berarti $y\preceq x$. Bersama $x\preceq y$, antisimetri memberi $x=y$. Ini bertentangan dengan $x\prec y$.

Asimetris. Jika $x\prec y$ dan $y\prec x$, transitivitas memberi $x\prec x$, bertentangan dengan irrefleksivitas. $\blacksquare$

Transitivitas bagian ketat bukan sekadar warisan dari transitivitas $\preceq$. Untuk menjamin kesimpulannya tetap ketat, antisimetri ikut diperlukan.

Definisi 4.4.6 (urutan ketat). Relasi $\sqsubset$ pada $S$ disebut urutan ketat jika ia irrefleksif dan transitif.

Lambang $\sqsubset$ dipakai untuk urutan ketat sembarang, agar tidak tertukar dengan $<$ pada bilangan. Proposisi berikut menunjukkan bahwa urutan parsial dan urutan ketat adalah dua cara menyimpan informasi yang sama. Untuk berpindah dari yang ketat ke yang parsial, kita cukup menambahkan diagonal.

Proposisi 4.4.7.

(a) Jika $\preceq$ urutan parsial pada $S$ dengan bagian ketat $\prec$, maka $\prec$ adalah urutan ketat dan ${\preceq}={\prec}\cup\Delta_S$.

(b) Jika $\sqsubset$ urutan ketat pada $S$, maka ${\sqsubseteq}:={\sqsubset}\cup\Delta_S$ adalah urutan parsial pada $S$, dan bagian ketatnya tepat $\sqsubset$.

Bukti.

(a) Proposisi 4.4.5 menunjukkan bahwa $\prec$ urutan ketat. Kesamaan himpunan dibuktikan dengan dua inklusi.

• Misalkan $x\preceq y$. Jika $x=y$, maka $(x,y)\in\Delta_S$. Jika $x\neq y$, maka $x\prec y$.
• Sebaliknya, ${\prec}\subseteq{\preceq}$ menurut definisi, dan $\Delta_S\subseteq{\preceq}$ karena $\preceq$ refleksif.

(b) Kita periksa tiga sifat, lalu bagian ketatnya.

Refleksif. Untuk setiap $x\in S$, berlaku $(x,x)\in\Delta_S\subseteq{\sqsubseteq}$.

Antisimetri. Misalkan $x\sqsubseteq y$ dan $y\sqsubseteq x$, dan andaikan $x\neq y$. Maka $(x,y)\notin\Delta_S$ dan $(y,x)\notin\Delta_S$. Akibatnya $x\sqsubset y$ dan $y\sqsubset x$. Transitivitas memberi $x\sqsubset x$, bertentangan dengan irrefleksivitas. Jadi $x=y$.

Transitif. Misalkan $x\sqsubseteq y$ dan $y\sqsubseteq z$.

• Jika $x=y$, maka $x\sqsubseteq z$ tidak lain adalah $y\sqsubseteq z$.
• Jika $y=z$, maka $x\sqsubseteq z$ tidak lain adalah $x\sqsubseteq y$.
• Jika $x\ne y$ dan $y\ne z$, maka $x\sqsubset y$ dan $y\sqsubset z$. Akibatnya $x\sqsubset z$, sehingga $x\sqsubseteq z$.

Bagian ketat. Misalkan $x\sqsubseteq y$ dan $x\neq y$. Maka $(x,y)\notin\Delta_S$, sehingga $x\sqsubset y$. Sebaliknya, misalkan $x\sqsubset y$. Maka $x\sqsubseteq y$. Selain itu $x\neq y$, sebab $x\sqsubset x$ mustahil. $\blacksquare$

Komparabilitas dan urutan total

Definisi 4.4.8. Misalkan $(S,\preceq)$ poset. Dua unsur $x,y\in S$ sebanding jika $x\preceq y$ atau $y\preceq x$. Jika tidak, keduanya tak sebanding, ditulis $x\parallel y$. Poset disebut terurut total (atau linear) jika setiap dua unsurnya sebanding.

Beberapa contoh:

• $(\mathbb Z,\le)$ terurut total.
• Pada keterbagian bilangan positif, $2\parallel3$. Seandainya $3=2k$, Proposisi 4.4.3 memaksa $k$ bulat positif. Namun $k=1$ memberi $2$, sedangkan $k\ge2$ memberi paling sedikit $4$. Jadi $2\nmid3$. Selain itu $3\nmid 2$, karena $3>2$ dan Proposisi 4.4.3.
• Pada $(\mathcal P(\{1,2\}),\subseteq)$, berlaku $\{1\}\parallel\{2\}$.

Kata "parsial" berarti "tidak harus total", bukan "pasti tidak total". Setiap urutan total adalah urutan parsial.

Minimal dan maksimal; terkecil dan terbesar

Definisi 4.4.9. Misalkan $(S,\preceq)$ poset dan $\prec$ bagian ketatnya.

• $m\in S$ minimal jika tidak ada $y\in S$ dengan $y\prec m$.
• $m\in S$ maksimal jika tidak ada $y\in S$ dengan $m\prec y$.
• $\ell\in S$ terkecil jika $\ell\preceq y$ untuk setiap $y\in S$.
• $g\in S$ terbesar jika $y\preceq g$ untuk setiap $y\in S$.

Kedua pasang pengertian ini berbeda secara mendasar. Unsur minimal hanya menjamin bahwa tidak ada unsur yang secara ketat berada di bawahnya. Ia tidak mengatakan apa pun tentang unsur yang tak sebanding dengannya. Unsur terkecil menuntut lebih banyak, yaitu ia berada di bawah semua unsur. Perbedaannya juga tampak pada kuantifikator. Minimalitas adalah pernyataan negatif "tidak ada $y$", sedangkan keterkecilan adalah pernyataan universal "untuk setiap $y$".

Proposisi 4.4.10 (keunikan). Suatu poset memiliki paling banyak satu unsur terkecil dan paling banyak satu unsur terbesar.

Bukti. Misalkan $\ell$ dan $\ell'$ keduanya terkecil. Karena $\ell$ terkecil dan $\ell'\in S$, berlaku $\ell\preceq\ell'$. Karena $\ell'$ terkecil, berlaku $\ell'\preceq\ell$. Antisimetri memberi $\ell=\ell'$. Argumen untuk terbesar sama, dengan arah dibalik. $\blacksquare$

Karena keunikan ini, bila unsur terkecil ada, kita boleh menyebutnya unsur terkecil dengan kata sandang tentu. Untuk unsur minimal, keunikan semacam itu tidak berlaku, seperti diperlihatkan Contoh 4.4.13.

Proposisi 4.4.11. Jika $\ell$ unsur terkecil, maka $\ell$ minimal, dan $\ell$ adalah satu-satunya unsur minimal. Pernyataan serupa berlaku untuk unsur terbesar dan unsur maksimal.

Bukti.

$\ell$ minimal. Misalkan ada $y\in S$ dengan $y\prec\ell$. Maka $y\preceq\ell$. Karena $\ell$ terkecil, juga $\ell\preceq y$. Antisimetri memberi $y=\ell$, bertentangan dengan $y\neq\ell$.

Satu-satunya. Misalkan $m$ minimal. Karena $\ell$ terkecil, $\ell\preceq m$. Seandainya $\ell\neq m$, maka $\ell\prec m$, bertentangan dengan minimalitas $m$. Jadi $m=\ell$.

Kasus terbesar diperoleh dengan membalik arah. $\blacksquare$

Akibat 4.4.12. Jika suatu poset memiliki dua unsur minimal yang berbeda, maka ia tidak memiliki unsur terkecil. Hal yang sama berlaku untuk dua unsur maksimal yang berbeda dan unsur terbesar.

Unsur minimal juga tidak selalu ada. $(\mathbb Z,\le)$ tidak memiliki unsur minimal, sebab untuk setiap $m$ berlaku $m-1<m$.

Pada poset kosong, keadaannya lebih ekstrem. Keempat definisi di atas menuntut adanya unsur $m\in S$, sehingga tidak ada unsur minimal, maksimal, terkecil, maupun terbesar. Hal ini tetap benar meskipun aksioma urutan parsial berlaku secara vakum. Wajar untuk bertanya apakah setiap poset berhingga tak kosong memiliki unsur minimal. Namun buktinya memerlukan induksi, sehingga klaim tersebut tidak dipakai pada unit ini.

Unit ini juga tidak membahas batas atas terkecil (supremum) suatu himpunan bagian. Supremum tidak selalu ada, dan bila ada belum tentu menjadi anggota himpunan bagian tersebut. Teori kelengkapan bukan materi bab ini.

Contoh utama: keterbagian pada $\{2,3,6,12,18\}$

Contoh 4.4.13. Misalkan $S=\{2,3,6,12,18\}$ dengan $a\preceq b$ jika dan hanya jika $a\mid b$. Menurut Proposisi 4.4.3, $(S,\preceq)$ adalah poset.

Kita menghitung seluruh relasinya. Tabel berikut memuat tanda ✓ pada baris $a$ dan kolom $b$ tepat ketika $a\mid b$.

Setiap isi tabel dapat diperiksa sebagai berikut.

Tanda ✓. Setiap tanda ✓ disertai saksi eksplisit:

• $6=2\cdot3$, $12=2\cdot6$, $18=2\cdot9$;
• $6=3\cdot2$, $12=3\cdot4$, $18=3\cdot6$;
• $12=6\cdot2$, $18=6\cdot3$;
• diagonal: $a=a\cdot1$.

Tanda – di bawah diagonal. Pada posisi ini $b<a$. Menurut Proposisi 4.4.3, $a\mid b$ dengan $a,b>0$ memaksa $a\le b$. Jadi $a\mid b$ tidak mungkin terjadi.

Tanda – di atas diagonal. Hanya ada dua posisi seperti ini. Pada keduanya, faktor $k$ harus bulat positif menurut Proposisi 4.4.3.

• $2\nmid 3$: faktor $k=1$ memberi $2$, sedangkan $k\ge2$ memberi paling sedikit $4$.
• $12\nmid18$: faktor $k=1$ memberi $12$, sedangkan $k\ge2$ memberi paling sedikit $24$.

Dari tabel diperoleh hal-hal berikut.

• Relasi penuh memuat $4+4+3+1+1=13$ pasangan. Lima di antaranya adalah pasangan diagonal $(2,2),(3,3),(6,6),(12,12),(18,18)$.
• Bagian ketat memuat delapan pasangan:

$$(2,6),(2,12),(2,18),(3,6),(3,12),(3,18),(6,12),(6,18).$$

• Pasangan tak sebanding. Dari $\binom52=10$ pasangan unsur berbeda, delapan sebanding. Dua sisanya tak sebanding, yaitu $2\parallel3$ dan $12\parallel18$.
• Minimal. Unsur $m$ minimal tepat ketika kolom $m$ hanya memuat ✓ pada diagonal. Hal ini terjadi untuk kolom $2$ dan $3$. Jadi unsur minimalnya adalah $2$ dan $3$. Unsur $6$, $12$, dan $18$ tidak minimal karena $2\prec 6$, $2\prec 12$, dan $2\prec 18$.
• Maksimal. Dengan cara yang sama, unsur $m$ maksimal tepat ketika baris $m$ hanya memuat ✓ pada diagonal. Jadi unsur maksimalnya adalah $12$ dan $18$. Unsur $2$, $3$, dan $6$ tidak maksimal karena $2\prec 6$, $3\prec 6$, dan $6\prec 12$.
• Tidak ada unsur terkecil maupun terbesar. Ada dua unsur minimal yang berbeda dan dua unsur maksimal yang berbeda, sehingga Akibat 4.4.12 berlaku. Hal ini juga terlihat langsung. Unsur terkecil harus membagi $2$ dan $3$, padahal kolom $2$ dan kolom $3$ tidak memiliki tanda ✓ pada baris yang sama. Unsur terbesar harus habis dibagi $12$ dan $18$, padahal baris $12$ dan baris $18$ tidak memiliki tanda ✓ pada kolom yang sama.

Relasi penutup

Tabel lengkap memuat banyak informasi yang berulang. Misalnya, $2\prec12$ sudah dapat disimpulkan dari $2\prec6$ dan $6\prec12$. Kita mencari pasangan "langkah terpendek" yang cukup untuk memulihkan seluruh relasi.

Definisi 4.4.14 (penutup). Misalkan $(S,\preceq)$ poset. Unsur $y$ menutupi $x$, ditulis $x\lessdot y$, jika $x\prec y$ dan tidak ada $z\in S$ dengan $x\prec z$ dan $z\prec y$.

Kedua ketaksamaan dalam syarat "tidak ada $z$" harus ketat. Andaikan syarat itu ditulis "tidak ada $z\in S$ dengan $x\preceq z\preceq y$". Untuk setiap $x\preceq y$, pilihan $z=x$ sudah memenuhi $x\preceq x\preceq y$. Akibatnya tidak ada pasangan $x,y$ dengan $y$ menutupi $x$, dan relasi penutup yang dihasilkan selalu kosong.

Perhatikan pula bahwa $z$ berkisar pada $S$, sehingga relasi penutup bergantung pada himpunan yang dipakai. Dalam poset $\{2,12\}$ dengan keterbagian, berlaku $2\lessdot12$, karena tidak ada unsur lain yang dapat menyela. Dalam $S$ di atas, $2\not\lessdot12$ karena $6$ menyela.

Contoh 4.4.15 (penutup pada $S$). Kita memeriksa kedelapan pasangan ketat dari Contoh 4.4.13. Untuk setiap pasangan $(x,y)$, kita mencari $z\in S$ dengan $x\prec z\prec y$. Calon $z$ harus berada pada baris $x$ (di luar diagonal) sekaligus pada kolom $y$ (di luar diagonal).

Jadi relasi penutup pada $S$ terdiri tepat dari empat pasangan:

$$2\lessdot6,\qquad 3\lessdot6,\qquad 6\lessdot12,\qquad 6\lessdot18.$$

Diagram Hasse untuk poset berhingga

Definisi 4.4.16 (konvensi diagram Hasse). Misalkan $(S,\preceq)$ poset berhingga, artinya unsur-unsurnya dapat didaftar habis. Definisi formal keberhinggaan menyusul pada bab-bab berikutnya. Diagram Hasse untuk $(S,\preceq)$ dibuat sebagai berikut.

1. Setiap unsur $S$ digambar sebagai satu titik.
2. Untuk setiap $x\lessdot y$, titik $y$ diletakkan lebih tinggi daripada titik $x$, lalu keduanya dihubungkan dengan satu ruas garis.
3. Tidak ada ruas garis lain.

Karena arah selalu dibaca ke atas, ruas garis tidak perlu diberi panah. Ada dua jenis informasi yang sengaja dihilangkan.

• Gelung $(x,x)$ dihilangkan, karena refleksivitas sudah diketahui.
• Ruas yang dapat ditempuh lewat jalur naik, seperti $2$ ke $12$, juga dihilangkan, karena ia dipulihkan oleh transitivitas.

Pembatasan pada poset berhingga bukan sekadar soal kepraktisan menggambar. Pada $(\mathbb Q,\le)$, tidak ada unsur yang menutupi unsur lain (Latihan 4.4.30). "Diagram" yang dibuat dengan aturan yang sama hanya berupa titik-titik tanpa ruas, sehingga tidak menyimpan informasi apa pun tentang urutan.

Proposisi 4.4.17 (rekonstruksi untuk poset berhingga; dengan prasyarat pinjaman). Misalkan $(S,\preceq)$ poset berhingga dan $x,y\in S$. Maka $x\preceq y$ jika dan hanya jika salah satu dari dua hal berikut berlaku.

• $x=y$ (bagian diagonal); atau
• ada $n\ge1$ dan unsur $z_0,z_1,\ldots,z_n\in S$ dengan $z_0=x$, $z_n=y$, dan $z_{i-1}\lessdot z_i$ untuk setiap $i=1,\ldots,n$. Dengan kata lain, ada jalur naik dari $x$ ke $y$ dalam diagram.

Prasyarat yang dipinjam. Bukti ini memakai induksi pada bilangan asli, termasuk bentuk induksi kuat, dan fakta dasar ukuran himpunan berhingga: jika $B$ himpunan bagian sejati dari himpunan berhingga $C$, maka $|B|<|C|$. Keduanya diterima di sini sebagai prasyarat; fondasi umumnya belum dibangun dalam bab ini. Daftar berhingga dan penyambungannya juga dipakai dengan pengertian yang sama seperti pada uraian diagram.

Bukti. Jika $x=y$, refleksivitas memberi $x\preceq y$. Jika terdapat jalur penutup dari $x$ ke $y$ dengan panjang $n\ge1$, kita buktikan $x\prec y$ dengan induksi pada $n$. Untuk $n=1$, $x\lessdot y$ langsung memberi $x\prec y$. Untuk langkah induksi, misalkan $z_0\lessdot z_1\lessdot\cdots\lessdot z_{n+1}$. Hipotesis induksi pada $n$ ruas pertama memberi $z_0\prec z_n$, sedangkan ruas terakhir memberi $z_n\prec z_{n+1}$. Transitivitas bagian ketat (Proposisi 4.4.5) memberi $z_0\prec z_{n+1}$. Jadi setiap jalur penutup berpanjang positif memberikan $x\prec y$, dan karena itu $x\preceq y$.

Sebaliknya, misalkan $x\preceq y$. Kasus $x=y$ sudah memenuhi alternatif pertama, jadi cukup menangani $x\prec y$. Bentuk interval urutan dengan separasi pada $S$:

$$I(x,y):=\{u\in S:x\preceq u\ \land\ u\preceq y\}.$$

Interval ini berhingga karena merupakan himpunan bagian dari $S$, dan memuat dua unsur berbeda $x,y$. Kita memakai induksi kuat pada $k=|I(x,y)|\ge2$ untuk membuktikan bahwa setiap pasangan ketat dengan interval berukuran $k$ dapat dihubungkan oleh jalur penutup dalam poset $(S,\preceq)$.

Dasar $k=2$. Karena $x,y\in I(x,y)$ dan keduanya berbeda, $I(x,y)=\{x,y\}$. Tidak ada $z\in S$ dengan $x\prec z\prec y$: unsur semacam itu akan menjadi anggota ketiga interval. Jadi $x\lessdot y$, dan satu ruas sudah menjadi jalur yang diminta.

Langkah induksi. Misalkan $k>2$, dan hasil berlaku untuk setiap pasangan ketat yang intervalnya berukuran kurang dari $k$. Ambil $x\prec y$ dengan $|I(x,y)|=k$. Jika $x\lessdot y$, selesai. Jika bukan, definisi penutup memberikan $z\in S$ dengan $x\prec z\prec y$.

Kita periksa ukuran kedua interval yang lebih pendek. Jika $u\in I(x,z)$, maka $x\preceq u\preceq z\preceq y$; transitivitas memberi $u\in I(x,y)$. Jadi $I(x,z)\subseteq I(x,y)$. Akan tetapi, $y\notin I(x,z)$: jika $y\preceq z$, bersama $z\preceq y$ antisimetri memberi $y=z$, bertentangan dengan $z\prec y$. Karena $y\in I(x,y)$, inklusi tersebut sejati. Demikian pula, jika $u\in I(z,y)$, maka $x\preceq z\preceq u\preceq y$, sehingga $u\in I(x,y)$. Unsur $x$ tidak berada dalam $I(z,y)$, sebab $z\preceq x$ bersama $x\preceq z$ akan memberi $z=x$, bertentangan dengan $x\prec z$. Maka $I(z,y)\subsetneq I(x,y)$ juga.

Fakta ukuran berhingga yang dipinjam memberi

$$|I(x,z)|<k\qquad\text{dan}\qquad |I(z,y)|<k.$$

Hipotesis induksi menghasilkan jalur penutup dalam poset yang sama, dari $x$ ke $z$ dan dari $z$ ke $y$. Sambungkan kedua daftar pada $z$, dengan menuliskan $z$ sekali. Setiap ruas tetap merupakan pasangan penutup dalam $S$, sehingga diperoleh jalur penutup dari $x$ ke $y$. Induksi selesai, dan kedua arah terbukti. $\blacksquare$

Contoh $(\mathbb Q,\le)$ menunjukkan bahwa hipotesis keberhinggaan tidak dapat dibuang. Pada contoh-contoh di unit ini, kedua arah kami periksa langsung dengan daftar lengkap, tanpa memakai Proposisi 4.4.17.

Contoh 4.4.18 (diagram Hasse untuk $S=\{2,3,6,12,18\}$).

Uraian lengkap diagram berikut tidak bergantung pada gambar.

• Titik. Ada lima titik dalam tiga tingkat. Tingkat bawah memuat $2$ dan $3$. Tingkat tengah memuat $6$. Tingkat atas memuat $12$ dan $18$.
• Ruas. Ada tepat empat ruas: $2$–$6$, $3$–$6$, $6$–$12$, dan $6$–$18$. Pada setiap ruas, ujung yang lebih tinggi adalah unsur yang menutupi.
• Tidak ada ruas lain. Khususnya, tidak ada ruas langsung $2$–$12$, $2$–$18$, $3$–$12$, atau $3$–$18$.

Rekonstruksi. Jalur naik dalam diagram dapat didaftar habis menurut titik awalnya:

• dari $2$: $2$–$6$; $2$–$6$–$12$; $2$–$6$–$18$;
• dari $3$: $3$–$6$; $3$–$6$–$12$; $3$–$6$–$18$;
• dari $6$: $6$–$12$; $6$–$18$;
• dari $12$ dan $18$: tidak ada ruas naik.

Pasangan (awal, akhir) dari delapan jalur ini tepat sama dengan delapan pasangan ketat dalam Contoh 4.4.13. Setiap jalur dengan dua ruas ditangani oleh satu kali transitivitas, misalnya $2\mid6$ dan $6\mid12$ memberi $2\mid12$. Menambahkan lima pasangan diagonal mengembalikan ketiga belas pasangan relasi penuh. Jadi diagram, bersama konvensi "diagonal ditambahkan", menyimpan relasi secara utuh.

Tinggi saja tidak menentukan perbandingan. Titik $12$ dan $18$ sama tinggi, tetapi itu tidak berarti keduanya "setara": keduanya tak sebanding. Sebaliknya, "lebih tinggi" juga tidak berarti "lebih besar". Yang menentukan perbandingan hanyalah jalur naik. Latihan 4.4.25 memuat titik $4$ yang digambar lebih tinggi daripada $3$, padahal $3\parallel4$.

Membaca sifat khusus dari diagram. Pada contoh ini, unsur minimal tepat titik-titik yang tidak memiliki ruas ke bawah, yaitu $2$ dan $3$. Unsur maksimal tepat titik-titik yang tidak memiliki ruas ke atas, yaitu $12$ dan $18$. Kedua hasil ini kita cocokkan langsung dengan tabel pada Contoh 4.4.13. Untuk poset berhingga umum, kriteria tersebut bergantung pada Proposisi 4.4.17.

Penerapan: dependensi tugas dan graf berarah asiklik

Bagian ini menyajikan model matematis, bukan laporan tentang proyek atau perangkat lunak tertentu.

Misalkan sejumlah tugas harus dikerjakan, dan beberapa tugas mensyaratkan tugas lain selesai lebih dahulu. Data yang biasanya tersedia hanyalah prasyarat langsung, dan relasi prasyarat langsung umumnya tidak transitif. Akan kita lihat bahwa urutan parsial muncul dari keterjangkauan, bukan dari sisi langsung.

Definisi 4.4.19 (graf berarah, lintasan, siklus, DAG).

• Graf berarah adalah pasangan $(V,K)$ dengan $V$ himpunan dan $K\subseteq V\times V$. Jadi $K$ adalah relasi pada $V$, dan anggotanya disebut sisi. Kita menulis $u\to v$ untuk $(u,v)\in K$. Dalam model dependensi, $u\to v$ berarti $u$ prasyarat langsung bagi $v$.
• Lintasan berarah dengan panjang $n\ge1$ dari $u$ ke $v$ adalah daftar berhingga $(v_0,v_1,\ldots,v_n)$ unsur $V$ dengan $v_0=u$, $v_n=v$, dan $v_{i-1}\to v_i$ untuk setiap $i=1,\ldots,n$.
• Siklus berarah adalah lintasan berarah dengan panjang $n\ge1$ yang memenuhi $v_n=v_0$. Gelung tunggal $v\to v$ adalah siklus dengan panjang $1$.
• DAG (graf berarah asiklik) adalah graf berarah yang tidak memuat siklus berarah apa pun.

Kami memakai "daftar berhingga" secara informal, sebagai urutan objek yang ditulis berjajar. Perlakuan formalnya sebagai fungsi pada himpunan indeks menunggu Bab 5. Satu-satunya operasi yang dipakai di bawah ini adalah penyambungan. Jika $(v_0,\ldots,v_n)$ dan $(w_0,\ldots,w_k)$ adalah lintasan dengan $v_n=w_0$, maka

$$(v_0,\ldots,v_n,w_1,\ldots,w_k)$$

adalah lintasan dengan panjang $n+k\ge2$. Setiap dua suku berurutan di dalamnya membentuk sisi, karena masing-masing berasal dari salah satu lintasan asal atau berupa sambungan $v_n=w_0\to w_1$.

Tanpa gelung tidak sama dengan asiklik. Pada $V=\{t_1,t_2,t_3\}$ dengan sisi $t_1\to t_2$, $t_2\to t_3$, dan $t_3\to t_1$, tidak ada gelung tunggal. Namun $(t_1,t_2,t_3,t_1)$ adalah siklus dengan panjang tiga, sehingga graf ini bukan DAG.

Sisi langsung umumnya tidak transitif. Dalam Contoh 4.4.22 di bawah, $A\to B$ dan $B\to D$, tetapi $A\to D$ bukan sisi.

Definisi 4.4.20 (keterjangkauan). Untuk graf berarah $(V,K)$, tulis $u\prec_K v$ jika ada lintasan berarah dengan panjang positif dari $u$ ke $v$.

Relasi $\prec_K$ adalah himpunan bagian dari $V\times V$ yang dipilih dengan separasi. Rumus pemilihnya berbicara tentang lintasan, yaitu daftar berhingga, yang dalam unit ini masih diperlakukan secara informal. Rumusan formalnya, sebagai fungsi pada himpunan indeks, menunggu Bab 5. Pada contoh utama DAG, pasangan keterjangkauan dan lintasan saksinya diperiksa secara eksplisit.

Proposisi 4.4.21. Misalkan $(V,K)$ graf berarah.

(a) $\prec_K$ transitif.

(b) $\prec_K$ irrefleksif jika dan hanya jika $(V,K)$ adalah DAG.

(c) Jika $(V,K)$ DAG, maka ${\preceq_K}:={\prec_K}\cup\Delta_V$ adalah urutan parsial pada $V$, dan bagian ketatnya tepat $\prec_K$.

(d) Jika $(V,K)$ memuat siklus yang melewati dua simpul berbeda, maka ${\prec_K}\cup\Delta_V$ tidak antisimetri.

Bukti.

(a) Jika ada lintasan dari $u$ ke $v$ dan lintasan dari $v$ ke $w$, penyambungan keduanya adalah lintasan berpanjang positif dari $u$ ke $w$.

(b) Pernyataan $v\prec_K v$ berarti ada lintasan berpanjang positif dari $v$ ke $v$. Lintasan seperti itu tepat merupakan siklus yang dimulai di $v$.

• Jika graf tidak memuat siklus, maka tidak ada $v$ dengan $v\prec_K v$.
• Sebaliknya, jika $(v_0,\ldots,v_n)$ adalah siklus, maka $v_0\prec_K v_0$.

(c) Menurut (a) dan (b), $\prec_K$ adalah urutan ketat. Kesimpulan mengikuti dari Proposisi 4.4.7(b).

Antisimetri juga dapat dilihat langsung. Misalkan $u\neq v$ dengan $u\prec_K v$ dan $v\prec_K u$. Menyambung kedua lintasan menghasilkan siklus dari $u$ kembali ke $u$, padahal graf adalah DAG.

(d) Misalkan $(v_0,\ldots,v_n)$ siklus dengan $v_n=v_0$, dan ada indeks $j$ dengan $v_j\neq v_0$. Maka $j\neq0$ dan $j\neq n$, sehingga $0<j<n$. Kedua penggalan berikut adalah lintasan berpanjang positif:

• $(v_0,\ldots,v_j)$ dengan panjang $j$, dari $v_0$ ke $v_j$;
• $(v_j,\ldots,v_n)$ dengan panjang $n-j$, dari $v_j$ ke $v_0$.

Jadi $v_0\prec_K v_j$ dan $v_j\prec_K v_0$, padahal $v_0\neq v_j$. Ini melanggar antisimetri. $\blacksquare$

Ringkasnya, keterjangkauan pada DAG adalah urutan ketat, dan dengan menambahkan diagonal kita memperoleh poset. Siklus merusak struktur ini. Siklus apa pun merusak irrefleksivitas, dan siklus yang melewati simpul berbeda merusak antisimetri.

Contoh 4.4.22 (lima tugas). Misalkan $V=\{A,B,C,D,E\}$, dengan himpunan sisi $K$ yang memuat tepat

$$A\to B,\quad A\to C,\quad B\to D,\quad C\to D,\quad D\to E.$$

Uraian lengkap gambar: $A$ adalah prasyarat langsung bagi $B$ dan $C$. Keduanya, $B$ dan $C$, adalah prasyarat langsung bagi $D$. Lalu $D$ adalah prasyarat langsung bagi $E$. Tidak ada sisi lain.

Seluruh lintasan. Simpul $E$ tidak memiliki sisi keluar, dan setiap simpul lain hanya memiliki sisi keluar yang tercantum di atas. Karena itu semua lintasan dapat didaftar habis dengan memperpanjang setiap lintasan sejauh sisi keluar memungkinkan:

• dari $E$: tidak ada;
• dari $D$: $(D,E)$;
• dari $B$: $(B,D)$, $(B,D,E)$;
• dari $C$: $(C,D)$, $(C,D,E)$;
• dari $A$: $(A,B)$, $(A,B,D)$, $(A,B,D,E)$, $(A,C)$, $(A,C,D)$, $(A,C,D,E)$.

Tidak satu pun lintasan berakhir di simpul awalnya, jadi graf ini DAG.

Keterjangkauan. Dengan mengambil pasangan (awal, akhir) dari setiap lintasan, diperoleh tepat sembilan pasangan ketat:

$$A\prec_K B,\ A\prec_K C,\ A\prec_K D,\ A\prec_K E,\ B\prec_K D,\ B\prec_K E,\ C\prec_K D,\ C\prec_K E,\ D\prec_K E.$$

Lima pasangan adalah sisi asli. Empat pasangan lainnya, yaitu $(A,D)$, $(A,E)$, $(B,E)$, dan $(C,E)$, muncul dari transitivitas. Dengan menambahkan lima pasangan diagonal, Proposisi 4.4.21(c) memberi poset $(V,\preceq_K)$ dengan $14$ pasangan.

Penutup. Kita memeriksa setiap pasangan ketat.

• $(A,D)$ disela $B$. Pasangan $(A,E)$, $(B,E)$, dan $(C,E)$ masing-masing disela $D$. Jadi keempatnya bukan penutup.
• $(A,B)$ adalah penutup. Penyela $z$ harus memenuhi $z\prec_K B$, padahal satu-satunya simpul yang menjangkau $B$ adalah $A$, dan $A\prec_K A$ mustahil. Hal yang sama berlaku untuk $(A,C)$.
• $(B,D)$ adalah penutup. Penyela $z$ harus memenuhi $B\prec_K z$, sehingga $z\in\{D,E\}$, dan juga $z\prec_K D$. Namun $D\prec_K D$ mustahil dan $E$ tidak menjangkau $D$. Hal yang sama berlaku untuk $(C,D)$.
• $(D,E)$ adalah penutup. Satu-satunya simpul yang dijangkau $D$ adalah $E$ sendiri, dan $E\prec_K E$ mustahil.

Jadi penutupnya tepat kelima sisi asli. Diagram Hasse-nya menempatkan $A$ di bawah, $B$ dan $C$ sejajar di atasnya, lalu $D$, dan $E$ paling atas. Ruasnya adalah $A$–$B$, $A$–$C$, $B$–$D$, $C$–$D$, dan $D$–$E$.

Unsur khusus.

• $A$ adalah unsur terkecil, karena $A\prec_K v$ untuk setiap $v\neq A$. Menurut Proposisi 4.4.11, $A$ juga satu-satunya unsur minimal.
• $E$ adalah unsur terbesar dan satu-satunya unsur maksimal.
• Satu-satunya pasangan tak sebanding adalah $B\parallel C$.

Bandingkan dengan Contoh 4.4.13, yang tidak memiliki unsur terkecil maupun terbesar. Keberadaan unsur terkecil adalah sifat poset tertentu, bukan sifat semua poset.

Contoh 4.4.23 (jadwal linear dan tingkat). Urutan pengerjaan linear adalah daftar semua tugas di $V$, masing-masing tepat sekali, sedemikian sehingga $u\prec_K v$ selalu mengakibatkan $u$ muncul sebelum $v$.

Dua kandidat. Daftar $A,B,C,D,E$ memenuhi syarat. Dengan posisi $1$ sampai $5$, setiap pasangan $(u,v)$ dari sembilan pasangan ketat memenuhi "posisi $u$ < posisi $v$":

• $A$ (posisi 1) mendahului semuanya;
• $B$ (posisi 2) dan $C$ (posisi 3) mendahului $D$ (posisi 4) dan $E$ (posisi 5);
• $D$ mendahului $E$.

Daftar $A,C,B,D,E$ juga memenuhi syarat dengan pemeriksaan yang sama. Pertukaran $B$ dan $C$ tidak melanggar apa pun karena $B\parallel C$.

Tidak ada urutan lain. Kedua daftar ini adalah satu-satunya urutan yang memenuhi syarat.

• $A$ harus mendahului keempat tugas lain, jadi $A$ berada di posisi $1$.
• $E$ harus didahului keempat tugas lain, jadi $E$ berada di posisi $5$.
• Posisi $2$ sampai $4$ diisi $B$, $C$, dan $D$. Karena $B\prec_K D$ dan $C\prec_K D$, tugas $D$ harus berada di posisi $4$.
• $B$ dan $C$ mengisi posisi $2$ dan $3$ dalam salah satu dari dua urutan.

Tingkat. Kelompokkan tugas menjadi $\{A\}$, $\{B,C\}$, $\{D\}$, $\{E\}$. Dalam setiap kelompok, tidak ada tugas yang menjangkau tugas lain dalam kelompok yang sama. Karena itu $B$ dan $C$ boleh dikerjakan sejajar, bila sumber daya memungkinkan. Relasi urutan hanya memberi izin kesejajaran. Relasi itu tidak menjamin bahwa sumber daya tersedia.

Perhitungan dengan hipotesis tambahan. Misalkan berlaku anggapan model berikut, yang bukan bagian dari relasi:

• setiap tugas memerlukan tepat satu satuan waktu;
• sebuah tugas baru boleh dimulai setelah semua prasyaratnya selesai;
• setiap pelaksana mengerjakan paling banyak satu tugas pada satu waktu, dan tugas tidak dipecah.

Di bawah anggapan ini, kita peroleh tiga hasil berikut.

• Jadwal per tingkat dengan dua pelaksana. $A$ dikerjakan pada satuan waktu ke-1, $B$ dan $C$ bersamaan pada ke-2, $D$ pada ke-3, dan $E$ pada ke-4. Semua tugas selesai pada akhir satuan ke-4.
• Batas bawah. Rantai $A\prec_K B\prec_K D\prec_K E$ memaksa empat tugas dikerjakan berurutan. $A$ selesai paling cepat di akhir satuan ke-1, $B$ di akhir ke-2, $D$ di akhir ke-3, dan $E$ di akhir ke-4. Jadi tidak ada jadwal yang selesai sebelum akhir satuan ke-4, berapa pun banyak pelaksananya. Jadwal per tingkat mencapai batas tersebut.
• Dengan satu pelaksana. Pelaksana itu mengerjakan paling banyak satu tugas per satuan waktu, sehingga lima tugas tidak dapat selesai sebelum akhir satuan ke-5. Kedua urutan linear di atas mencapai angka itu.

Kesimpulan ini sepenuhnya bergantung pada anggapan durasi dan pelaksana di atas. Dengan durasi berbeda, biaya, atau batasan sumber daya lain, relasi $\preceq_K$ saja tidak menentukan jadwal terbaik. Unit ini tidak membuat klaim apa pun tentang optimisasi umum.

Contoh 4.4.24 (mengubah sisi). Tetap gunakan $V$ dan $K$ dari Contoh 4.4.22.

(a) Menambah sisi berlebih. Misalkan $K_1=K\cup\{(A,D)\}$. Tidak ada sisi di $K_1$ yang masuk ke $A$. Akibatnya, setiap lintasan yang memakai sisi $A\to D$ harus dimulai di $A$, sehingga lintasan baru hanyalah $(A,D)$ dan $(A,D,E)$. Keduanya hanya menghasilkan pasangan $(A,D)$ dan $(A,E)$, yang sudah ada. Siklus juga tidak mungkin melewati $A$, karena siklus yang melewati $A$ harus kembali ke $A$, padahal tidak ada sisi masuk ke $A$. Jadi setiap siklus di $K_1$ tidak memakai sisi $A\to D$ dan merupakan siklus di $K$, padahal $K$ tidak memuat siklus. Akibatnya $(V,K_1)$ tetap DAG dan ${\prec_{K_1}}={\prec_K}$. Poset keterjangkauannya sama persis. Sisi $A\to D$ bukan sisi Hasse, karena $B$ tetap menyela $A\prec_{K_1}B\prec_{K_1}D$. Diagram Hasse, sebagai gambar relasi penutup, tidak menyimpan sisi berlebih semacam ini.

(b) Menambah sisi balik. Misalkan $K_2=K\cup\{(E,A)\}$. Maka $(A,B,D,E,A)$ adalah siklus. Menurut Proposisi 4.4.21(b), keterjangkauan tidak lagi irrefleksif, misalnya $A\prec_{K_2}A$. Lintasan $(A,B,D,E)$ dan $(E,A)$ memberi $A\prec_{K_2}E$ dan $E\prec_{K_2}A$ dengan $A\neq E$, sehingga antisimetri gagal, sesuai Proposisi 4.4.21(d). Graf $(V,K_2)$ bukan DAG, dan ${\prec_{K_2}}\cup\Delta_V$ bukan urutan parsial pada himpunan simpul $\{A,B,C,D,E\}$.

Batas klaim. Kami tidak menyatakan bahwa setiap DAG memiliki simpul tanpa sisi masuk (sumber) atau tanpa sisi keluar (sink). Pada DAG kosong, misalnya, tidak ada simpul sama sekali. Untuk DAG berhingga dan tak kosong, pernyataan itu benar, tetapi buktinya memerlukan argumen keberhinggaan yang baru tersedia setelah induksi pada Bab 7. Hal yang sama berlaku untuk teorema umum bahwa setiap DAG berhingga memiliki urutan pengerjaan linear. Dalam contoh di atas, urutan seperti itu kami temukan dan periksa secara langsung.

Latihan dan pembahasan

Latihan 4.4.25. Misalkan $T=\{1,2,3,4,6,12\}$ dengan keterbagian. (a) Hitung banyak pasangan ketat. (b) Daftarkan semua pasangan penutup. (c) Tentukan unsur minimal, maksimal, terkecil, dan terbesar. (d) Daftarkan semua pasangan tak sebanding.

Pembahasan.

(a) Proposisi 4.4.3 berlaku karena semua unsur positif. Pasangan ketat dihitung menurut unsur bawahnya:

• $1$ membagi kelima unsur lain;
• $2\mid4,6,12$;
• $3\mid6,12$;
• $4\mid12$;
• $6\mid12$.

Jadi ada $5+3+2+1+1=12$ pasangan ketat. Pasangan berurutan $(a,b)$ lainnya dengan $a\ne b$ tidak termasuk relasi, karena alasan berikut:

• jika $a>b$, maka $a\mid b$ mustahil menurut Proposisi 4.4.3;
• $2\nmid3$, karena faktor bulat positif $1$ memberi $2$ dan faktor $\ge2$ memberi paling sedikit $4$;
• $3\nmid4$, karena $3\cdot1<4<3\cdot2$;
• $4\nmid6$, karena $4\cdot1<6<4\cdot2$.

(b) Pasangan penutupnya adalah

$$1\lessdot2,\quad 1\lessdot3,\quad 2\lessdot4,\quad 2\lessdot6,\quad 3\lessdot6,\quad 4\lessdot12,\quad 6\lessdot12.$$

Sebagai contoh pemeriksaan, untuk $2\lessdot6$ calon penyelanya adalah unsur yang habis dibagi $2$ dan membagi $6$, selain $2$ dan $6$. Pembagi $6$ lainnya di $T$ hanyalah $1$ dan $3$, dan keduanya tidak habis dibagi $2$. Lima pasangan ketat sisanya bukan penutup:

• $1\prec4$ disela $2$;
• $1\prec6$ disela $2$;
• $1\prec12$ disela $2$;
• $2\prec12$ disela $4$;
• $3\prec12$ disela $6$.

Jadi ada tujuh penutup dari dua belas pasangan ketat.

(c) $1$ adalah unsur terkecil karena $1\mid b$ untuk setiap $b$. Menurut Proposisi 4.4.11, $1$ juga satu-satunya unsur minimal. Dengan cara yang sama, $12$ adalah unsur terbesar dan satu-satunya unsur maksimal.

(d) Ada $\binom62-12=3$ pasangan tak sebanding, yaitu $2\parallel3$, $3\parallel4$, dan $4\parallel6$. Dalam diagram Hasse yang wajar, $3$ berada di tingkat kedua dan $4$ di tingkat ketiga. Titik $4$ lebih tinggi daripada $3$, tetapi tidak ada jalur naik dari $3$ ke $4$. Inilah contoh bahwa tinggi saja tidak menentukan perbandingan.

Latihan 4.4.26. Misalkan $S'=\{1,2,3,6,12,18\}$ dengan keterbagian. Bandingkan dengan Contoh 4.4.13: apa yang berubah pada penutup, unsur minimal, dan unsur terkecil?

Pembahasan. Penutup bertambah dua, yaitu $1\lessdot2$ dan $1\lessdot3$. Pasangan $1\prec6$, $1\prec12$, dan $1\prec18$ bukan penutup karena masing-masing disela $2$. Penutup lama $2\lessdot6$, $3\lessdot6$, $6\lessdot12$, dan $6\lessdot18$ tetap penutup. Penyela harus berada secara ketat di atas unsur bawah pasangan, sedangkan $1$ tidak berada di atas $2$, $3$, atau $6$. Jadi kini ada enam penutup.

Unsur $2$ dan $3$ tidak lagi minimal karena $1\prec2$ dan $1\prec3$. Unsur $1$ adalah unsur terkecil, sekaligus satu-satunya unsur minimal. Di bagian atas tidak ada perubahan: $12$ dan $18$ tetap dua unsur maksimal yang berbeda, sehingga menurut Akibat 4.4.12 tidak ada unsur terbesar. Latihan ini menunjukkan bahwa menambah satu unsur dapat menciptakan unsur terkecil tanpa memengaruhi keberadaan unsur terbesar.

Latihan 4.4.27. Seorang penulis mendefinisikan "$y$ menutupi $x$" sebagai: $x\preceq y$ dan tidak ada $z\in S$ dengan $x\preceq z\preceq y$. Tunjukkan bahwa menurut definisi ini, dalam poset apa pun, tidak ada pasangan $x,y$ dengan $y$ menutupi $x$.

Pembahasan. Misalkan $x\preceq y$. Ambil $z=x$. Refleksivitas memberi $x\preceq x$, dan hipotesis memberi $x\preceq y$. Jadi ada $z$ dengan $x\preceq z\preceq y$, sehingga syarat "tidak ada $z$" gagal. Jika $x\not\preceq y$, syarat pertama sudah gagal. Dalam kedua kasus, $y$ tidak menutupi $x$, sehingga relasi penutup menurut definisi ini selalu kosong. Definisi yang benar (Definisi 4.4.14) memakai $x\prec z\prec y$, sehingga kedua ujung dikecualikan.

Latihan 4.4.28. Misalkan $X=\{1,2\}$ dan perhatikan poset $(\mathcal P(X),\subseteq)$. Daftarkan unsur-unsurnya, pasangan penutupnya, pasangan tak sebanding, serta unsur minimal, maksimal, terkecil, dan terbesar. Uraikan diagram Hasse-nya dengan kata-kata.

Pembahasan. Unsurnya ada empat: $\varnothing$, $\{1\}$, $\{2\}$, dan $X$.

Tulis $A\subsetneq B$ untuk bagian ketat dari $\subseteq$, yaitu $A\subseteq B$ dan $A\neq B$. Pasangan ketat ada lima:

• $\varnothing\subsetneq\{1\}$, $\varnothing\subsetneq\{2\}$, $\varnothing\subsetneq X$;
• $\{1\}\subsetneq X$, $\{2\}\subsetneq X$.

Pasangan $\varnothing\subsetneq X$ disela $\{1\}$, sehingga bukan penutup. Empat pasangan lainnya adalah penutup. Sebagai contoh, penyela untuk $\varnothing\subsetneq\{1\}$ harus berupa himpunan bagian sejati tak kosong dari $\{1\}$, dan tidak ada himpunan seperti itu.

Satu-satunya pasangan tak sebanding adalah $\{1\}\parallel\{2\}$, karena $1\in\{1\}$ tetapi $1\notin\{2\}$, dan sebaliknya untuk $2$.

$\varnothing$ adalah unsur terkecil, karena $\varnothing\subseteq A$ untuk setiap $A$. $X$ adalah unsur terbesar. Menurut Proposisi 4.4.11, keduanya juga satu-satunya unsur minimal dan satu-satunya unsur maksimal.

Diagram Hasse-nya berbentuk belah ketupat. $\varnothing$ berada di bawah, $\{1\}$ dan $\{2\}$ sejajar di tengah, dan $X$ di atas. Ada empat ruas: $\varnothing$–$\{1\}$, $\varnothing$–$\{2\}$, $\{1\}$–$X$, dan $\{2\}$–$X$.

Latihan 4.4.29. Buktikan bahwa dalam poset terurut total, setiap unsur minimal adalah unsur terkecil. Simpulkan bahwa poset total memiliki paling banyak satu unsur minimal.

Pembahasan. Misalkan $m$ minimal dan $y\in S$. Karena urutannya total, $m\preceq y$ atau $y\preceq m$.

• Jika $m\preceq y$, selesai.
• Jika $y\preceq m$ dan $y\neq m$, maka $y\prec m$, bertentangan dengan minimalitas $m$.
• Jika $y=m$, maka $m\preceq y$ menurut refleksivitas.

Dalam setiap kasus $m\preceq y$, jadi $m$ terkecil. Jika $m$ dan $m'$ keduanya minimal, keduanya terkecil, sehingga $m=m'$ menurut Proposisi 4.4.10.

Contoh 4.4.13 menunjukkan bahwa hipotesis "total" diperlukan: $2$ dan $3$ keduanya minimal, tetapi tak satu pun terkecil.

Latihan 4.4.30. Tunjukkan bahwa dalam $(\mathbb Q,\le)$, untuk $x<y$ tidak pernah berlaku $x\lessdot y$. Mengapa hal ini menjelaskan pembatasan diagram Hasse pada poset berhingga?

Pembahasan. Misalkan $x<y$ di $\mathbb Q$, dan ambil $z=\frac{x+y}{2}\in\mathbb Q$ dengan aritmetika rasional yang dipinjam. Dari $x<y$ diperoleh $2x<x+y<2y$, sehingga $x<z<y$. Jadi $z$ menyela, dan $y$ tidak menutupi $x$.

Akibatnya relasi penutup pada $\mathbb Q$ kosong. "Diagram" yang dibuat dengan aturan Definisi 4.4.16 hanya berupa titik tanpa ruas, sehingga tidak ada jalur naik sama sekali, padahal $0<1$. Kesimpulan Proposisi 4.4.17 gagal untuk $\mathbb Q$. Jadi hipotesis keberhinggaan dalam fakta tersebut sungguh diperlukan.

Latihan 4.4.31. Misalkan $V=\{p,q,r,s\}$ dengan sisi $p\to q$, $q\to r$, $p\to r$, dan $r\to s$. (a) Tunjukkan bahwa graf ini DAG. (b) Hitung keterjangkauan. (c) Tentukan sisi yang bukan sisi Hasse. (d) Daftarkan semua urutan pengerjaan linear.

Pembahasan.

(a) Lintasan didaftar habis menurut simpul awal:

• dari $s$: tidak ada;
• dari $r$: $(r,s)$;
• dari $q$: $(q,r)$, $(q,r,s)$;
• dari $p$: $(p,q)$, $(p,q,r)$, $(p,q,r,s)$, $(p,r)$, $(p,r,s)$.

Tidak ada lintasan yang kembali ke simpul awalnya, jadi graf ini DAG.

(b) Pasangan ketatnya ada enam:

$$p\prec q,\ p\prec r,\ p\prec s,\ q\prec r,\ q\prec s,\ r\prec s.$$

Keenam pasangan ini mencakup semua $\binom42$ pasangan simpul berbeda. Jadi poset keterjangkauannya terurut total.

(c) Sisi langsung $p\to r$ bukan penutup, karena $q$ menyela $p\prec q\prec r$. Sisi Hasse-nya adalah $p$–$q$, $q$–$r$, dan $r$–$s$. Membuang sisi $p\to r$ tidak mengubah keterjangkauan, karena pasangan $p\prec r$ dan $p\prec s$ tetap diperoleh melalui $q$.

(d) Karena urutannya total, posisi setiap tugas terpaksa:

• $p$ mendahului ketiga tugas lain, jadi berada di posisi $1$;
• $q$ mendahului $r$ dan $s$, jadi berada di posisi $2$;
• $r$ mendahului $s$.

Satu-satunya urutan adalah $p,q,r,s$, dan tidak ada tugas yang boleh dikerjakan sejajar.

Latihan 4.4.32. Misalkan $V=\{t_1,t_2,t_3\}$ dengan himpunan sisi $K$ yang memuat tepat $t_1\to t_2$, $t_2\to t_3$, dan $t_3\to t_1$. (a) Apakah graf memuat gelung tunggal? (b) Apakah graf ini DAG? (c) Periksa irrefleksivitas $\prec_K$ dan antisimetri ${\prec_K}\cup\Delta_V$.

Pembahasan.

(a) Tidak ada sisi berbentuk $(v,v)$, jadi tidak ada gelung tunggal.

(b) $(t_1,t_2,t_3,t_1)$ adalah siklus dengan panjang tiga, jadi graf ini bukan DAG.

(c) Siklus tersebut memberi $t_1\prec_K t_1$, sehingga $\prec_K$ tidak irrefleksif. Penggalan $(t_1,t_2)$ dan $(t_2,t_3,t_1)$ memberi $t_1\prec_K t_2$ dan $t_2\prec_K t_1$ dengan $t_1\neq t_2$. Jadi ${\prec_K}\cup\Delta_V$ tidak antisimetri, sesuai Proposisi 4.4.21(d). Graf tanpa gelung tunggal belum tentu asiklik.

Latihan 4.4.33. Periksa poset kosong $(\varnothing,\varnothing)$. (a) Mengapa ia poset? (b) Apakah ia terurut total? (c) Apakah ia memiliki unsur minimal atau unsur terkecil? (d) Apa diagram Hasse-nya?

Pembahasan.

(a) Ketiga aksioma berbentuk "untuk setiap $x\in\varnothing,\ldots$", sehingga berlaku secara vakum.

(b) Ya, secara vakum, karena tidak ada pasangan unsur yang perlu dibandingkan.

(c) Tidak. Setiap pengertian dalam Definisi 4.4.9 menuntut adanya unsur $m\in\varnothing$, dan tidak ada unsur seperti itu. Kontras ini penting. Pernyataan universal tentang $\varnothing$ benar secara vakum, sedangkan pernyataan keberadaan tentang $\varnothing$ salah.

(d) Diagram tanpa titik dan tanpa ruas.

Latihan 4.4.34. Misalkan $\sqsubset$ urutan ketat pada $S$. Buktikan bahwa $\sqsubset$ asimetris. Lalu tunjukkan bahwa relasi $R_0=\{(1,2),(2,1)\}$ pada $\{1,2\}$ simetris tetapi bukan urutan ketat.

Pembahasan. Jika $x\sqsubset y$ dan $y\sqsubset x$, transitivitas memberi $x\sqsubset x$, bertentangan dengan irrefleksivitas. Jadi $\sqsubset$ asimetris.

Relasi $R_0$ simetris karena memuat $(1,2)$ beserta kebalikannya $(2,1)$. Dari $1R_02$ dan $2R_01$, transitivitas akan menuntut $1R_01$, padahal $(1,1)\notin R_0$. Jadi $R_0$ tidak transitif, sehingga bukan urutan ketat. Jika kita memaksakan transitivitas dengan menambahkan $(1,1)$, irrefleksivitas gagal. Secara umum, relasi simetris yang memuat pasangan $(x,y)$ dengan $x\neq y$ tidak pernah menjadi urutan ketat, sebab ia akan melanggar asimetri.

Penutup Bab 4

Bab ini dimulai dari satu konstruksi, yaitu pasangan berurutan $(a,b)=\{\{a\},\{a,b\}\}$. Konstruksi ini membuat hasil kali $A\times B$ dan relasi $R\subseteq A\times B$ menjadi himpunan yang sah. Dari sana muncul dua keluarga relasi dengan peran berbeda.

• Relasi ekuivalensi (Unit 4.2–4.3) bersifat simetris. Relasi ini memecah himpunan menjadi kelas-kelas yang saling lepas, dan kelas-kelas itu membentuk himpunan kuosien. Aturan yang memakai wakil kelas hanya sah bila hasilnya tidak bergantung pada wakil yang dipilih.
• Urutan parsial (unit ini) bersifat antisimetri. Relasi ini menyusun unsur dalam tingkatan tanpa memaksa setiap pasangan sebanding. Untuk poset berhingga, diagram Hasse menyimpan seluruh relasi melalui penutup. Pada graf dependensi, urutan parsial muncul dari keterjangkauan, asalkan graf tidak memuat siklus.

Dalam bab ini beberapa kali muncul aturan yang dimaksudkan memasangkan setiap objek dengan tepat satu objek:

• proyeksi $a\mapsto[a]$ ke himpunan kuosien, yang memang memasangkan setiap $a$ dengan tepat satu kelas;
• aturan pada kelas yang didefinisikan melalui wakil, seperti penjumlahan yang memasangkan setiap pasangan kelas dengan satu kelas hasil, dan sah setelah diperiksa tidak bergantung pada wakil;
• penempatan setiap tugas pada satu posisi dalam urutan pengerjaan linear.

Ketiganya adalah relasi dengan sifat khusus: setiap unsur domain berelasi dengan tepat satu unsur kodomain. Sebaliknya, "aturan" $F([a])=a$ gagal memenuhi sifat ini, sebab untuk modulus $m>0$, kelas $[0]=[m]$ akan berelasi dengan dua bilangan berbeda, $0$ dan $m$.

Bab 5 menjadikan sifat tersebut definisi fungsi. Di sana dibahas grafik fungsi sebagai himpunan pasangan, domain dan kodomain, injeksi dan surjeksi, serta peta maju dan peta balik. Dengan bahasa itu, pemeriksaan kesahan aturan pada kuosien dapat dibaca ulang sebagai pemeriksaan apakah suatu relasi memang fungsi. Daftar berhingga, yang dalam unit ini dipakai secara informal untuk lintasan dan urutan pengerjaan, memperoleh rumusan formalnya sebagai fungsi pada himpunan indeks.

Rujukan Bab 4

[R4-1] Richard Hammack. Book of Proof, edisi ketiga. Bagian 11.4 dan awal 11.5, halaman cetak 215–218. https://richardhammack.github.io/BookOfProof/Main.pdf

[R4-2] Alexander Brandt. Discrete Structures for Computing, bagian 2.2, "Relations". https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter2/relations.html

[R4-3] Alexander Brandt. Discrete Structures for Computing, bagian 7.2, "Directed Graphs". https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter7/directedgraphs.html