Kelas kesetaraan (kelas ekuivalensi) adalah istilah yang diberikan pada himpunan bagian (subset) dari sejumlah relasi kesetaraan (equivalence relation) $R$ yang memuat semua elemen yang saling setara satu sama lain. Relasi kesetaraan didefinisikan sebagai relasi yang transitif, simetris (simetris), dan transitif (transitif) sekaligus.
Misalkan $R$ adalah relasi kesetaraan pada himpunan $A.$ Himpunan dari semua elemen yang berelasi dengan elemen $x \in A$ disebut sebagai kelas kesetaraan (equivalence class) dari $x$ di $R.$ Notasi yang dipakai untuk kelas kesetaraan adalah nama elemen yang ditutup dengan menggunakan kurung siku. Secara matematis, kita tulis sebagai berikut.
$$[x] = \{y \mid (x, y) \in R\}$$Setiap elemen pada kelas ekuivalensi disebut sebagai perwakilan (representative).
Sebagai contoh, kita punya $A = \{1, 2, 3, 4, 5\}$ dan relasi $R = \{(a, b) \mid (a + b)~\text{genap}\}.$ Diketahui bahwa $R$ didefinisikan pada himpunan $A.$
Untuk menentukan kelas kesetaraan, kita harus mengecek terlebih dahulu apakah $R$ merupakan relasi kesetaraan atau bukan.
Relasi refleksif: Akan ditunjukkan bahwa $(x, x) \in R$ untuk setiap $x \in A.$ Ambil sembarang $a \in A.$ Kita tahu bahwa $a + a = 2a$ adalah bilangan genap. Jadi, $(a, a) \in R$ sehingga $R$ refleksif.
Relasi simetris: Akan ditunjukkan bahwa jika $(a + b)$ genap, maka $(b + a)$ juga genap. Ini jelas benar karena penggunaan sifat komutatif pada bilangan bulat tidak mengubah paritas (ganjil-genap).
Relasi transitif: Akan ditunjukkan bahwa $(a + b)$ genap dan $(b + c)$ genap, maka $(a+c)$ genap. Ada dua kasus yang perlu ditinjau: (1) Jika $a$ dan $b$ keduanya genap, $c$ haruslah genap sehingga $(a+c)$ genap; (2) Jika $a$ dan $b$ keduanya ganjil, $c$ juga harus ganjil sehingga $(a+c)$ genap.
Jadi, $R$ terbukti merupakan relasi kesetaraan.
Selanjutnya, kita dapat membuat kelas kesetaraan dari salah satu elemen $A$, yaitu $1.$
$$[1] = \{1, 3, 5\}$$karena $(1, 1),$ $(1, 3)$, dan $(1,5)$ merupakan anggota $R.$ Penulisan $(1, 3)$ dan $(3, 1)$ dianggap sama karena $R$ simetris.
Adapun kelas kesetaraan dari elemen $A$ yang lain adalah sebagai berikut.
$$\begin{aligned} \left[2\right] & = \{2, 4\} \\ [3] & = \{1, 3, 5\} \\ [4] & = \{2, 4\} \\ [5] & = \{1, 3, 5\} \end{aligned}$$Dapat dilihat bahwa kelas kesetaraan dari elemen $1, 3,$ dan $5$ sama, begitu juga dengan kelas kesetaraan dari elemen $2$ dan $4.$ Kelas kesetaraan dari elemen $A$ di $R$ hanya ada dua.
Baca: Soal dan Pembahasan – Relasi dan Fungsi
Sembarang elemen dari $1, 3,$ dan $5$ dapat dipilih untuk mewakili kelas kesetaraan $\{1, 3, 5\}$, begitu juga dengan kelas kesetaraan $\{2, 4\}$ yang dapat diwakili oleh $2$ atau $4.$
Misalkan kita memilih $1$ sebagai perwakilan kelas kesetaraan $\{1, 3, 5\}$ dan $2$ sebagai perwakilan kelas kesetaraan $\{2, 4\}.$
$$\begin{aligned} \left[1\right] & = \{1, 3, 5\} \\ [2] & = \{2, 4\} \end{aligned}$$
Contoh lain: Perhatikan lima garis lurus berikut.
Lima garis tersebut dikelompokkan dalam satu himpunan $L = \{\ell, m, n, p, q\}.$ Definisikan $R = \{(a, b) \mid a~\text{sejajar dengan}~b\}.$ Diketahui bahwa $R$ didefinisikan pada himpunan $L.$
Untuk menentukan kelas kesetaraan, kita harus mengecek terlebih dahulu apakah $R$ merupakan relasi kesetaraan atau bukan.
Relasi refleksif: Akan ditunjukkan bahwa untuk setiap $a \in L,$ berlaku $(a, a) \in R.$ Ambil sembarang $a \in L.$ Kita tahu bahwa setiap garis pasti sejajar dengan dirinya sendiri. Jadi, $R$ refleksif.
Relasi simetris: Akan ditunjukkan bahwa jika $a$ sejajar dengan $b$, maka $b$ sejajar dengan $a$. Ini jelas benar menurut definisi.
Relasi transitif: Akan ditunjukkan bahwa jika $a$ sejajar dengan $b$ dan $b$ sejajar dengan $c,$ maka $a$ sejajar dengan $c.$ Ini juga jelas benar menurut definisi.
Jadi, $R$ terbukti merupakan relasi kesetaraan.
Selanjutnya, kita dapat membuat kelas kesetaraan dari elemen $L.$
$$\begin{aligned} \left[\ell\right] & = \{\ell, m, n\} \\ [p] & = \{p, q\} \end{aligned}$$Perhatikan bahwa hanya ada dua relasi kesetaraan berbeda yang dapat dibuat dari elemen $L$ di $R.$ Kita menggunakan $\ell$ dan $p$ sebagai perwakilannya.
Teorema: Ekuivalensi Pernyataan dalam Kelas Kesetaraan
Misalkan $R$ merupakan relasi kesetaraan pada himpunan $A.$ Misalkan juga $a, b \in A.$ Pernyataan berikut ekuivalen.
- $a~R~b.$
- $[a] = [b].$
- $[a] \cap [b] \neq \emptyset.$
Untuk menunjukkan bahwa ketiga pernyataan tersebut ekuivalen, kita akan menunjukkan bahwa Pernyataan 1 mengimplikasikan Pernyataan 2, Pernyataan 2 mengimplikasikan Pernyataan 3, dan Pernyataan 3 mengimplikasikan Pernyataan 1.
Misalkan $R$ merupakan relasi kesetaraan pada himpunan $A$ serta $a, b \in A.$
Bagian 1: 1 $\Rightarrow$ 2
Misalkan $a~R~b.$ Untuk menunjukkan bahwa $[a] = [b],$ kita akan menunjukkan bahwa $[a] \subseteq [b]$ dan $[b] \subseteq [a].$
Pertama, ambil sembarang $x \in [a].$ Artinya, $a~R~x.$ Perhatikan bahwa $a~R~b$ menandakan $b~R~a$ karena $R$ simetris. Lebih lanjut, $b~R~a$ dan $a~R~x$ mengimplikasikan $b~R~x$ karena $R$ transitif. Artinya, $x \in [b]$ sehingga $[a] \subseteq [b].$
Berikutnya, ambil sembarang $y \in [b].$ Artinya, $b~R~y.$ Lebih lanjut, $a~R~b$ dan $b~R~y$ mengimplikasikan $a~R~y$ karena $R$ transitif. Artinya, $y \in [a]$ sehingga $[b] \subseteq [a].$
Jadi, terbukti bahwa $[a] = [b].$
Bagian 2: 2 $\Rightarrow$ 3
Misalkan $[a] = [b].$ Akan ditunjukkan bahwa $[a] \cap [b] \neq \emptyset.$ Perhatikan bahwa $[a]$ takkosong karena $R$ refleksif sehingga terdapat $a \in [a].$ Karena $[a] = [b],$ jelas $[b]$ juga takkosong. Akibatnya, $[a] \cap [b] \neq \emptyset.$
Bagian 3: 3 $\Rightarrow$ 1
Misalkan $[a] \cap [b] \neq \emptyset.$ Akan ditunjukkan bahwa $a~R~b.$ Karena $[a] \cap [b] \neq \emptyset,$ terdapat $x \in A$ sehingga $x \in [a]$ dan $x \in [b].$ Dengan demikian, $x~R~a$ dan $x~R~b.$ Karena $R$ simetris, $x~R~a$ sama saja artinya dengan $a~R~x.$ Karena $R$ transitif, $a~R~x$ dan $x~R~b$ mengimplikasikan $a~R~b.$
Dari tiga bagian pembuktian di atas, terbukti bahwa ketiga pernyataan yang dicetuskan dalam teorema di atas ekuivalen. $\blacksquare$
Teorema di atas menunjukkan bahwa kelas kesetaraan dari dua elemen di himpunan $A$ memiliki tepat dua kemungkinan, yaitu identik atau disjoin (saling lepas). Secara matematis, jika $a, b \in A,$ maka $[a]_R \cap [b]_R = \emptyset$ ketika $[a]_R \ne [b]_R.$ Selain itu, gabungan dari semua kelas kesetaraan dari $R$ adalah himpunan $A$ itu sendiri, atau secara matematis, ditulis $\bigcup\limits_{a \in R} [a] = A.$ Hal ini berlaku lantaran setiap elemen $A$ muncul di kelas kesetaraannya masing-masing karena sifat refleksif yang dimiliki oleh relasi, yaitu untuk setiap $a \in A,$ berlaku $(a, a) \in R.$
Dari sini, kelas kesetaraan dari himpunan $A$ akan membentuk “partisi” dari $A.$ Apa itu partisi? Kita akan mendefinisikannya sebagai berikut.
Definisi: Partisi
- $A_i \neq \emptyset$ untuk setiap $i \in I.$
- $A_i \cap A_j = \emptyset$ untuk $i \neq j$ dengan $i, j \in I.$
- $\bigcup\limits_{i \in I} A_i = A.$
Sebagai contoh, misalkan $A = \{1, 2, 3, 4, 5, 6\}.$ Definisikan $$R = \{(a, b) \mid a+b~\text{genap}\}.$$Dengan demikian, $R$ merupakan relasi kesetaraan. Perhatikan bahwa $A_1 = [1] = \{1, 3, 5\}$ dan $A_2 = [2] = \{2, 4, 6\}.$ Jelas bahwa $A_1$ dan $A_2$ keduanya takkosong. Lebih lanjut, $A_1 \cap A_2 = \emptyset$ dan $A_1 \cup A_2 = A.$ Berdasarkan definisi, kelas kesetaraan $[1]$ dan $[2]$ membentuk partisi dari himpunan $A.$
Today Quote
Bagian Pilihan Ganda
Soal Nomor 1
Misalkan $R$ adalah relasi kesetaraan pada himpunan pasangan berurut dari bilangan bulat positif sedemikian sehingga $((a, b), (c, d)) \in R$ jika dan hanya jika $ad = bc.$ Salah satu elemen dari kelas kesetaraan $\left[(1, 2)\right]$ di $R$ adalah $\cdots \cdot$
A. $(2, 1)$
B. $(100, 50)$
C. $(200, 100)$
D. $(100, 150)$
E. $(100, 200)$
Perhatikan bahwa $(1, 2)$ dikatakan berelasi dengan $(c, d)$ oleh $R$ jika dan hanya jika $d = 2c.$ Dengan demikian, $(c, d) = (c, 2c)$ untuk setiap bilangan bulat positif $c.$ Oleh karena itu, kelas kesetaraan dari $(1, 2)$ dinyatakan oleh
$$\left[(1, 2)\right] = \{(1, 2), (2, 4), (4, 8), \cdots, (100, 200), \cdots\}.$$Jadi, Salah satu elemen dari kelas kesetaraan $\left[(1, 2)\right]$ di $R$ adalah $\boxed{(100, 200)}$
(Jawaban E)
Baca Juga: Soal dan Pembahasan – Relasi dalam Matematika Diskret
Soal Nomor 2
Pandang himpunan bilangan bulat dan relasi “kongruensi modulo $5$”. Dua bilangan bulat $a$ dan $b$ dikatakan kongruen modulo $5,$ dinotasikan oleh $a \equiv b~(\text{mod}~5),$ jika dan hanya jika $a-b$ habis dibagi oleh $5.$
Misalkan $R$ merupakan himpunan bilangan bulat yang berkaitan dengan kongruensi modulo $5.$ Masing-masing kelas kesetaraan di $R$ dibedakan berdasarkan sisa hasil bagi bilangan bulat oleh $5.$ Bilangan bulat berikut yang berada dalam kelas kesetaraan yang sama dengan $23$ adalah $\cdots \cdot$
A. $15$ D. $32$
B. $18$ E. $37$
C. $29$
Untuk menentukan bilangan bulat yang berada dalam kelas kesetaraan yang sama dengan $23,$ kita perlu mencari bilangan bulat yang memiliki sisa hasil bagi yang sama dengan $23$ ketika dibagi oleh $5.$ Perhatikan bahwa sisa hasil bagi $23$ oleh $5$ adalah $3$ sebagaimana $23 = 4 \cdot 5 + 3.$ Selanjutnya, tinjau setiap bilangan bulat yang tercantum dalam opsi jawaban.
Cek opsi A:
Sisa hasil bagi $15$ oleh $5$ adalah $0$ karena $15 = 3 \cdot 5 + 0.$
Cek opsi B:
Sisa hasil bagi $18$ oleh $5$ adalah $3$ karena $18 = 3 \cdot 5 + 3.$
Cek opsi C:
Sisa hasil bagi $29$ oleh $5$ adalah $4$ karena $29 = 5 \cdot 5 + 4.$
Cek opsi D:
Sisa hasil bagi $32$ oleh $5$ adalah $2$ karena $32 = 6 \cdot 5 + 2.$
Cek opsi E:
Sisa hasil bagi $37$ oleh $5$ adalah $2$ karena $37 = 7 \cdot 5 + 2.$
Jadi, $18$ memiliki sisa hasil bagi yang sama dengan $23$ ketika dibagi oleh $5.$ Dengan kata lain, $18$ berada dalam kelas kesetaraan yang sama dengan $23.$
(Jawaban B)
Soal Nomor 3
Pandang himpunan bilangan bulat positif dan relasi “keterbagian”. Dua bilangan bulat positif $a$ dan $b$ dikatakan berelasi dalam keterbagian, ditulis oleh $a \mid b,$ jika dan hanya jika $b$ habis dibagi oleh $a,$ artinya terdapat bilangan bulat $k$ sehingga $b = a \cdot k.$ Misalkan $D$ merupakan himpunan bilangan bulat positif yang berelasi dalam keterbagian. Setiap kelas kesetaraan di $D$ direpresentasikan oleh semua kelipatan dari suatu bilangan bulat positif tertentu.
Bilangan bulat positif yang berada dalam kelas kesetaraan yang sama dengan $24$ adalah $\cdots \cdot$
A. $15$ D. $48$
B. $18$ E. $50$
C. $36$
Untuk menentukan bilangan bulat positif yang berada dalam kelas kesetaraan yang sama dengan $24,$ kita perlu mencari bilangan bulat positif yang merupakan kelipatan dari $24.$ Hal ini lantaran jika $24$ habis dibagi oleh bilangan bulat positif tertentu, maka kelipatannya juga pasti habis dibagi oleh bilangan bulat positif tersebut. Tinjau setiap bilangan bulat yang tercantum dalam opsi jawaban.
Cek opsi A:
$15$ bukan kelipatan dari $24.$
Cek opsi B:
$18$ bukan kelipatan dari $24.$
Cek opsi C:
$36$ bukan kelipatan dari $24.$
Cek opsi D:
$48$ merupakan kelipatan dari $24$ karena $48 = 2 \cdot 24.$
Cek opsi E:
$50$ bukan kelipatan dari $24.$
Karena $48$ merupakan kelipatan dari $24,$ dapat dikatakan bahwa $48$ berada dalam kelas kesetaraan yang sama dengan $24.$
(Jawaban D)
Soal Nomor 4
Misalkan $a$ dan $b$ merupakan bilangan bulat. Misalkan juga $R$ merupakan relasi yang didefinisikan oleh $a \sim b$ jika dan hanya jika $a^2 \equiv b^2~(\text{mod}~7)$ dengan $\equiv$ menyatakan kongruensi modulo $7.$ Pasangan bilangan bulat berikut yang berada dalam kelas kesetaraan yang sama di $R$ adalah $\cdots \cdot$
A. $(3, 10)$ D. $(-2, 9)$
B. $(5, -6)$ E. $(-6, -7)$
C. $(8, -2)$
Untuk menentukan pasangan bilangan bulat yang berada dalam kelas kesetaraan yang sama di $R$ dengan $a \sim b$ jika dan hanya jika $a^2 \equiv b^2~(\text{mod}~7),$ kita perlu memeriksa kuadrat dari masing-masing bilangan bulat pada pasangan mana yang kongruen modulo $7.$
Cek opsi A:
Diberikan pasangan bilangan bulat $(3, 10).$ Perhatikan bahwa $3^2 \equiv 2~(\text{mod}~7)$ dan $10^2 \equiv 2~(\text{mod}~7).$ Karena itu, $3^2 \equiv 10^2~(\text{mod}~7).$ Jadi, $3$ dan $10$ kongruen modulo $7$ sehingga $(3, 10)$ berada dalam kelas kesetaraan yang sama di $R.$
Cek opsi B:
Diberikan pasangan bilangan bulat $(5, -6).$ Perhatikan bahwa $5^2 \equiv 4~(\text{mod}~7)$ dan $(-6)^2 \equiv 1~(\text{mod}~7).$ Karena itu, $5^2 \not\equiv (-6)^2~(\text{mod}~7).$ Jadi, $5$ dan $-6$ tidak kongruen modulo $7$ sehingga $(5, -6)$ tidak berada dalam kelas kesetaraan yang sama di $R.$
Cek opsi C:
Diberikan pasangan bilangan bulat $(8, -2).$ Perhatikan bahwa $8^2 \equiv 1~(\text{mod}~7)$ dan $(-2)^2 \equiv 4~(\text{mod}~7).$ Karena itu, $8^2 \not\equiv (-2)^2~(\text{mod}~7).$ Jadi, $8$ dan $-2$ tidak kongruen modulo $7$ sehingga $(8, -2)$ tidak berada dalam kelas kesetaraan yang sama di $R.$
Cek opsi D:
Diberikan pasangan bilangan bulat $(-2, 11).$ Perhatikan bahwa $(-2)^2 \equiv 4~(\text{mod}~7)$ dan $11^2 \equiv 2~(\text{mod}~7).$ Karena itu, $(-2)^2 \not\equiv 11^2~(\text{mod}~7).$ Jadi, $-2$ dan $11$ tidak kongruen modulo $7$ sehingga $(-2, 11)$ tidak berada dalam kelas kesetaraan yang sama di $R.$
Cek opsi E:
Diberikan pasangan bilangan bulat $(-6, -7).$ Perhatikan bahwa $(-6)^2 \equiv 1~(\text{mod}~7)$ dan $(-7)^2 \equiv 0~(\text{mod}~7).$ Karena itu, $(-6)^2 \equiv (-7)^2~(\text{mod}~7).$ Jadi, $-6$ dan $-7$ tidak kongruen modulo $7$ sehingga $(-6, -7)$ tidak berada dalam kelas kesetaraan yang sama di $R.$
(Jawaban A)
Soal Nomor 5
Misalkan $R$ merupakan relasi yang didefinisikan oleh $a \equiv b~(\text{mod}~6)$ dengan $a$ dan $b$ merupakan bilangan bulat positif yang tidak melebihi $100.$ Kardinalitas kelas kesetaraan dari bilangan bulat $9$ di relasi tersebut adalah $\cdots \cdot$
A. $10$ D. $17$
B. $12$ E. $19$
C. $16$
Kelas kesetaraan dari bilangan bulat $9$ di relasi $R$ adalah himpunan yang anggotanya kongruen dengan $9$ modulo $6.$ Dengan kata lain, kita perlu mencari bilangan bulat positif $a \le 100$ sehingga $a \equiv 9 \equiv 3~(\text{mod}~6).$ Bilangan bulat positif $\le 100$ yang bersisa $3$ ketika dibagi oleh $6$ adalah $3, 9,$ $15, 21, \cdots,$ $99.$ Artinya,
$$[9] = \{3, 9, 15, 21, \cdots, 99\}.$$Banyaknya anggota dalam kelas kesetaraan tersebut sama dengan $\dfrac{99-3}{6}+1 = 17.$ Jadi, kardinalitas kelas kesetaraan dari bilangan bulat $9$ di relasi R adalah $\boxed{17}.$
(Jawaban D)
Soal Nomor 6
Koleksi himpunan bagian berikut yang merupakan partisi dari $\{-3, -2, -1, 0, 1, 2, 3\}$ adalah $\cdots \cdot$
A. $\{-3, -1, 1, 3\},$ $\{-2, 0, 2\}$
B. $\{-3, -2, -1, 0\},$ $\{0, 1, 2, 3\}$
C. $\{-3, 3\}, \{-2, 2\},$ $\{-1, 1\}$
D. $\{-3, -2, 2, 3\},$ $\{-1, 1\}$
E. $\{-3, -1\}, \{-2, 0\},$ $\{1, 2, 3\}, \{3\}$
Misalkan $S = \{-3, -2, -1, 0, 1, 2, 3\}.$
Koleksi himpunan bagian dikatakan sebagai partisi dari suatu himpunan jika setiap himpunan bagian tersebut takkosong, tidak saling beririsan, dan gabungannya merupakan himpunan mula-mula.
Cek opsi A:
Misalkan $S_1 = \{-3, -1, 1, 3\}$ dan $S_2 = \{-2, 0, 2\}.$ Jelas bahwa $S_1$ dan $S_2$ takkosong. Lebih lanjut, $S_1 \cap S_2 = \emptyset$ dan $S_1 \cup S_2 = S.$ Berdasarkan definisi, koleksi himpunan bagian pada opsi A membentuk partisi dari himpunan yang dimaksud.
Cek opsi B:
Misalkan $S_1 = \{-3, -2, -1, 0\}$ dan $S_2 = \{0, 1, 2, 3\}.$ Jelas bahwa $S_1$ dan $S_2$ takkosong. ebih lanjut, $S_1 \cup S_2 = S,$ tetapi $S_1 \cap S_2 = \{0\} \neq \emptyset.$ Dengan demikian, koleksi himpunan bagian pada opsi B tidak membentuk partisi dari himpunan yang dimaksud.
Cek opsi C:
Misalkan $S_1 = \{-3, 3\},$ $S_2 = \{-2, 2\},$ dan $S_3 = \{-1, 1\}.$ Jelas bahwa $S_1, S_2,$ dan $S_3$ takkosong. Lebih lanjut, $S_1 \cap S_2 \cap S_3 = \emptyset,$ tetapi $$S_1 \cup S_2 \cup S_3 = \{-3, -2, -1, 1, 2, 3\} \neq S.$$Dengan demikian, koleksi himpunan bagian pada opsi C tidak membentuk partisi dari himpunan yang dimaksud.
Cek opsi D:
Misalkan $S_1 = \{-3, -2, 2, 3\}$ dan $S_2 = \{-1, 1\}.$ Jelas bahwa $S_1$ dan $S_2$ takkosong. Lebih lanjut, $S_1 \cap S_2 = \emptyset,$ tetapi $$S_1 \cup S_2 = \{-3, -2, -1, 1, 2, 3\} \neq S.$$Dengan demikian, koleksi himpunan bagian pada opsi D tidak membentuk partisi dari himpunan yang dimaksud.
Cek opsi E:
Misalkan $S_1 = \{-3, -1\},$ $S_2 = \{-2, 0\},$ $S_3 = \{1, 2, 3\},$ dan $S_4 = \{3\}.$ Jelas bahwa $S_1, S_2, S_3,$ dan $S_4$ takkosong. Lebih lanjut, $$S_1 \cup S_2 \cup S_3 \cup S_4 = \{-3, -2, -1, 0, 1, 2, 3\} = S,$$tetapi $$S_1 \cap S_2 \cap S_3 \cap S_4 = \{3\} \neq \emptyset.$$Dengan demikian, koleksi himpunan bagian pada opsi E tidak membentuk partisi dari himpunan yang dimaksud.
(Jawaban A)
Bagian Uraian
Soal Nomor 1
Didefinisikan $R = \{(x, y) \in \mathbb{Z}^2 \mid 3 \mid (x-y)\}.$
- Buktikan bahwa $R$ merupakan relasi kesetaraan.
- Carilah banyaknya kelas kesetaraan berbeda di $R.$
Diketahui $R = \{(x, y) \in \mathbb{Z}^2 \mid 3 \mid (x-y)\}.$
Jawaban a)
Untuk membuktikan bahwa $R$ merupakan relasi kesetaraan, kita harus membuktikan bahwa $R$ refleksif, simetris, dan transitif.
Relasi refleksif: Akan ditunjukkan bahwa untuk setiap $(x, x) \in \mathbb{Z}^2,$ berlaku $(x, x) \in R.$ Ambil sembarang $(x, x) \in \mathbb{Z}^2.$ Akibatnya, $x-x = 0 = 0(3)$ sehingga menurut definisi keterbagian, $3 \mid (x-y.$ Jadi, $(x, x) \in R$ sehingga $R$ refleksif.
Relasi simetris: Akan ditunjukkan bahwa jika $(x, y) \in R,$ maka $(y, x) \in R.$ Misalkan $(x, y) \in R.$ Karena itu, $3 \mid (x-y)$ yang berarti $x-y = 3k$ untuk suatu bilangan bulat $k.$ Akibatnya, $y-x = -(x-y)= 3(-k).$ Menurut definisi keterbagian, $3 \mid (y-x)$ sehingga $(y, x) \in R.$ Jadi, $R$ simetris.
Relasi transitif: Akan ditunjukkan bahwa jika $(x, y) \in R$ dan $(y, z) \in R,$ maka $(x, z) \in R.$ Misalkan $(x, y) \in R$ dan $(y, z) \in R.$ Karena itu, $3 \mid (x-y)$ dan $3 \mid (y-z)$ sehingga $x-y = 3k$ dan $y-z = 3m$ untuk suatu bilangan bulat $k$ dan $m.$ Dari sini, diperoleh $x-z = 3(k+m).$ Karena $k$ dan $m$ bulat, $k+m$ juga demikian. Menurut definisi keterbagian, $3 \mid (x-z)$ sehingga $(x, z) \in R.$ Jadi, $R$ transitif.
Karena $R$ merupakan relasi refleksif, simetris, dan transitif, kita simpulkan bahwa $R$ merupakan relasi kesetaraan. $\blacksquare$
Jawaban b)
Adapun kelas kesetaraan berbeda di $R$ adalah sebagai berikut.
$$\begin{aligned} \left[0\right] & = \{\cdots, -6, -3, 0, 3, 6, \cdots\} \\ & = \{\ell \mid\ell = 3k, k \in \mathbb{Z}\} \\ \left[1\right] & = \{\cdots, -5, -2, 1, 4, 7, \cdots\} \\ & = \{\ell \mid \ell = 3k+1, k \in \mathbb{Z}\} \\ \left[2\right] & = \{\cdots, -4, -1, 2, 5, 8, \cdots\} \\ & = \{\ell \mid \ell = 3k+2, k \in \mathbb{Z}\} \end{aligned}$$Jadi, ada $\boxed{3}$ kelas kesetaraan berbeda dari $R.$
Soal Nomor 2
Diberikan relasi $R$ pada himpunan semua bilangan bulat $\mathbb{Z}$ yang didefinisikan sebagai $$(x, y) \in R \Leftrightarrow x^2 + 2y = y^2 + 2x$$untuk setiap $x, y \in \mathbb{Z}.$
- Buktikan bahwa $R$ merupakan relasi kesetaraan.
- Tentukan kelas kesetaraan dari $i \in \{1, 2, 3, 4, 5\}$ di $R.$
Jawaban a)
Untuk membuktikan bahwa $R$ merupakan relasi kesetaraan, kita harus membuktikan bahwa $R$ refleksif, simetris, dan transitif.
Relasi refleksif: Akan ditunjukkan bahwa untuk setiap $(x, x) \in \mathbb{Z},$ berlaku $(x, x) \in R.$ Ambil sembarang $(x, x) \in \mathbb{Z}.$ Akibatnya, diperoleh $^2 + 2x = x^2 + 2x$ (benar untuk setiap $x \in \mathbb{Z}$). Jadi, $(x, x) \in R$ sehingga $R$ refleksif.
Relasi simetris: Akan ditunjukkan bahwa jika $(x, y) \in R,$ maka $(y, x) \in R.$ Misalkan $(x, y) \in R.$ Karena itu, $x^2 + 2y = y^2 + 2x.$ Persamaan tersebut ekuivalen dengan $y^2 + 2x = x^2 + 2y$ karena tanda = (sama dengan) bersifat simetris. Jadi, $(y, x) \in R$ sehingga $R$ simetris.
Relasi transitif: Akan ditunjukkan bahwa jika $(x, y) \in R$ dan $(y, z) \in R,$ maka $(x, z) \in R.$ Misalkan $(x, y) \in R$ dan $(y, z) \in R.$ Karena itu,
$$\begin{aligned} x^2+2y = y^2+2x & \Leftrightarrow x^2-2x = y^2-2y~~~(\cdots 1) \\ y^2 + 2z = z^2+2y & \Leftrightarrow y^2-2y = z^2-2z~~~(\cdots 2). \end{aligned}$$Dari $(1)$ dan $(2),$ didapat $x^2-2x = z^2-2z$ yang ekuivalen dengan $x^2 + 2z = z^2+2x.$ Ini berarti $(x, z) \in R$ sehingga $R$ transitif.
Karena $R$ merupakan relasi refleksif, simetris, dan transitif, kita simpulkan bahwa $R$ merupakan relasi kesetaraan. $\blacksquare$
Jawaban b)
Misalkan $(x, y) \in R$ sehingga berlaku
$$x^2 + 2y = y^2 + 2x \Leftrightarrow y^2-2y+(2x-x^2) = 0.$$Dengan memandang persamaan terakhir sebagai persamaan kuadrat bervariabel $y,$ diperoleh
$$\begin{aligned} y_{1, 2} & = \dfrac{-(-2) \pm \sqrt{(-2)^2-4(1)(2x-x^2)}}{2(1)} \\ & = \dfrac{2 \pm \sqrt{4-4(2x-x^2)}}{2} \\ & = 1 \pm \sqrt{1-(2x-x^2)} \\ & = 1 \pm \sqrt{(x-1)^2} \\ & = 1 \pm |x-1|. \end{aligned}$$Dengan demikian,
$$\begin{cases} y_1 & = 1 + (x-1) = x \\ y_2 & = 1-(x-1) = -x+2. \end{cases}$$Kelas kesetaraan dari $i \in \{1, 2, 3, 4, 5\}$ dinyatakan sebagai berikut.
$$\begin{aligned} \left[1\right] & = \{1\} \\ \left[2\right] & = \{0, 2\} \\ \left[3\right] & = \{-1, 3\} \\ \left[4\right] & = \{-2, 4\} \\ \left[5\right] & = \{-3, 5\} \end{aligned}$$
Soal Nomor 3
Misalkan $a$ dan $b$ merupakan bilangan bulat serta $n$ merupakan bilangan bulat positif yang lebih besar daripada $1.$ Definisikan relasi $\equiv_n$ pada bilangan bulat yang menyatakan bahwa $a \equiv_n b$ jika dan hanya jika $a$ dan $b$ keduanya memiliki sisa hasil bagi yang sama ketika dibagi oleh $n.$
- Buktikan bahwa $\equiv_n$ merupakan relasi kesetaraan.
- Misalkan $a$ merupakan sembarang bilangan bulat. Tentukan kelas kesetaraan $[a]_n$ terhadap $\equiv_n.$
- Berapa banyak kelas kesetaraan berbeda yang dapat terbentuk oleh $\equiv_n?$
Jawaban a)
Untuk membuktikan bahwa $\equiv_n$ merupakan relasi kesetaraan, kita harus membuktikan bahwa $\equiv_n$ refleksif, simetris, dan transitif.
Relasi refleksif: Ambil sembarang bilangan bulat $a.$ Jelas bahwa $a \equiv_n a$ karena sisa hasil bagi $a$ oleh $n$ sama dengan sisa hasil bagi dirinya sendiri oleh $n.$
Relasi simetris: Ambil sembarang bilangan bulat $a$ dan $b.$ Jika $a \equiv_n b,$ maka $b \equiv_n a.$ Hal ini jelas benar secara trivial karena jika $a$ memiliki sisa hasil bagi yang sama dengan $b$ ketika dibagi oleh $n,$ maka $b$ juga pasti memiliki sisa hasil bagi yang sama dengan $a$ ketika dibagi oleh $n.$
Relasi transitif: Ambil sembarang bilangan bulat $a, b,$ dan $c.$ Misalkan $a \equiv_n b$ dan $b \equiv_n c.$ Karena $a$ memiliki sisa hasil bagi yang sama dengan $b$ ketika dibagi oleh $n$ dan $b$ memiliki sisa hasil bagi yang sama dengan $c$ ketika dibagi oleh $n,$ haruslah $a$ memiliki sisa hasil bagi yang sama dengan $c$ ketika dibagi oleh $n.$ Jadi, $a \equiv_n c.$
Karena $\equiv_n$ merupakan relasi refleksif, simetris, dan transitif, kita simpulkan bahwa $\equiv_n$ merupakan relasi kesetaraan. $\blacksquare$
Jawaban b)
Misalkan $a$ merupakan sembarang bilangan bulat. Kelas kesetaraan $[a]_n$ merupakan himpunan semua bilangan bulat yang kongruen dengan $a$ modulo $n.$ Secara matematis, dapat ditulis
$$[a]_n = \{b \in \mathbb{Z} \mid b \equiv_n a\}.$$Dengan kata lain, $[a]_n$ berisi semua bilangan bulat $b$ sehingga $a$ dan $b$ memiliki sisa hasil bagi yang sama ketika dibagi oleh $n.$
Jawaban c)
Kelas kesetaraan yang terbentuk oleh $\equiv_n$ dibedakan berdasarkan sisa hasil bagi bilangan bulat oleh $n.$ Dalam hal ini, sisa hasil bagi yang mungkin ada sebanyak $n,$ yaitu $0, 1, 2, \cdots, n-1.$ Dengan demikian, akan ada $n$ kelas kesetaraan berbeda yang dapat terbentuk oleh $\equiv_n,$ yakni $[0]_n,$ $[1]_n,$ $[2]_n, \cdots,$ dan $[n-1]_n.$
Soal Nomor 4
Pandang himpunan bilangan rasional $\mathbb{Q}.$ Definisikan relasi $\sim$ pada $\mathbb{Q}$ yang menyatakan bahwa $\dfrac{a}{b} \sim \dfrac{c}{d}$ jika dan hanya jika $ad-bc = 0$ dengan $a, b, c, d \in \mathbb{Z}$ dan $b, d \ne 0.$
- Buktikan bahwa $\sim$ merupakan relasi kesetaraan pada $\mathbb{Q}.$
- Tentukan kelas kesetaraan $[r]_\sim$ dari suatu bilangan rasional $r = \dfrac{a}{b}$ terhadap $\sim.$
- Berapa banyak relasi kesetaraan berbeda yang dapat terbentuk oleh $\sim$ pada $\mathbb{Q}?$
Jawaban a)
Untuk membuktikan bahwa $\sim$ pada $\mathbb{Q}$ merupakan relasi kesetaraan, kita harus membuktikan bahwa $\sim$ refleksif, simetris, dan transitif.
Relasi refleksif: Ambil sembarang bilangan rasional $r = \dfrac{a}{b}.$ Jelas bahwa $ab-ba = 0$ sehingga $r \sim r.$
Relasi simetris: Ambil sembarang bilangan rasional $r_1 = \dfrac{a_1}{b_1}$ dan $r_2 = \dfrac{a_2}{b_2}.$ Misalkan $r_1 \sim r_2.$ Artinya, $a_1b_2-b_1a_2 = 0.$ Kalikan kedua ruas dengan $-1$ akan menghasilkan $a_2b_1-b_2a_1 = 0$ yang berarti $r_2 = \dfrac{a_2}{b_2} \sim \dfrac{a_1}{b_1} = r_1.$
Relasi transitif: Ambil sembarang bilangan rasional $r_1 = \dfrac{a_1}{b_1},$ $r_2 = \dfrac{a_2}{b_2},$ dan $r_3 = \dfrac{a_3}{b_3}.$ Misalkan $r_1 \sim r_2$ dan $r_2 \sim r_3.$ Artinya, $a_1b_2-b_1a_2 = 0$ dan $a_2b_3-b_2a_3 = 0,$ atau ekuivalen dengan $a_1b_2 = b_1a_2$ dan $a_2b_3 = b_2a_3.$ Kalikan kedua persamaan terakhir sesuai ruasnya untuk memperoleh
$$a_1a_2b_2b_3 = a_2a_3b_1b_2.$$Diketahui $b_2 \ne 0.$
- Jika $a_2 \neq 0,$ kedua ruas dapat dibagi dengan $a_2b_2$ sehingga diperoleh $a_1a_3 = b_1a_3,$ atau $a_1a_3-b_1a_3 = 0.$ Artinya, $r_1 \sim r_3.$
- Jika $a_2 = 0,$ maka $a_1b_2 = 0$ dan $b_2a_3 = 0.$ Karena $b_2 \neq 0,$ haruslah $a_1 = a_3 = 0.$ Akibatnya, $a_1a_3 = b_1a_3$ karena kedua ruas pasti bernilai $0.$ Hal ini juga mengimplikasikan $r_1 \sim r_3.$
Karena $\sim$ merupakan relasi refleksif, simetris, dan transitif, kita simpulkan bahwa $\sim$ merupakan relasi kesetaraan pada $\mathbb{Q}.$ $\blacksquare$
Jawaban b)
Misalkan $r$ merupakan sembarang bilangan rasional. Kelas kesetaraan $[r]_\sim$ menyatakan himpunan semua bilangan rasional yang ekuivalen dengan $r$ di relasi $\sim.$ Secara matematis, dapat ditulis
$$[r]_\sim = \left\{\dfrac{c}{d} \in \mathbb{Q}~\Bigg |~\dfrac{ad-bc}{bd} = 0\right\}.$$Jawaban c)
Misalkan $\dfrac{a}{b}$ merupakan bilangan rasional. Kelas kesetaraan $\left[\dfrac{a}{b}\right]_\sim$ memuat semua bilangan rasional berbentuk $\dfrac{ka}{kb}$ untuk setiap bilangan bulat $k \neq 0.$ Karena itu, $\left[\dfrac{a}{b}\right]_\sim$ memiliki anggota yang takberhingga banyaknya. Dengan kata lain, ada takberhingga banyaknya relasi kesetaraan berbeda yang dapat terbentuk oleh $\sim$ pada $\mathbb{Q}.$
Soal Nomor 5
Misalkan $A = \{0, 1, 2, 3\}$ dan $R = \{(0, 0),$ $(1, 1),$ $(2, 2),$ $(3, 3),$ $(1, 2),$ $(2, 1),$ $(2, 2),$ $(3, 2),$ $(2, 3),$ $(3, 1),$ $(1, 3)\}.$
- Tunjukkan bahwa $R$ merupakan relasi kesetaraan pada $A.$
- Misalkan $a \in A$ dan definisikan $c(a) = \{b \in A \mid a~R~b\}$ sebagai kelas kesetaraan dari $a$ di $R.$ Carilah $c(a)$ untuk setiap elemen $a \in A.$
- Tunjukkan bahwa $\{c(a) \mid a \in A\}$ membentuk suatu partisi dari $A.$
Jawaban a)
$R$ refleksif karena $(a, a) \in R$ untuk setiap elemen $a \in A.$
$R$ simetris karena jika $(a, b) \in R,$ berlaku $(b, a) \in R$ untuk setiap elemen $a, b \in A.$
$R$ transitif karena jika $(a, b) \in R$ dan $(b, c) \in R,$ berlaku $(a, c) \in R$ untuk setiap elemen $a, b, c \in R.$
Karena $R$ refleksif, simetris, dan transitif, disimpulkan bahwa $R$ merupakan relasi kesetaraan.
Jawaban b)
Diketahui $A = \{0, 1, 2, 3\}.$ Kelas kesetaraan dari $a \in A$ di $R$ dinyatakan oleh
$$\begin{aligned} c(0) & = \{0\} \\ c(1) = c(2) = c(3) & = \{1, 2, 3\}. \end{aligned}$$Jawaban c)
Perhatikan bahwa $M = c(0) = \{0\}$ dan $N =c(1)=c(2)$ $=c(3)=\{1, 2, 3\}$ sehingga diperoleh himpunan $\{\{0\}, \{1, 2, 3\}\}.$ Karena $M$ dan $N$ bukan himpunan kosong, $M \cup N = A,$ dan $M \cap N = \emptyset,$ terbukti bahwa $\{c(a) \mid a \in A\}$ membentuk suatu partisi dari $A.$
Soal Nomor 6
Buktikan bahwa relasi $R$ pada himpunan semua untaian bit (bit string) yang didefinisikan oleh $s~R~t$ jika dan hanya jika $s$ dan $t$ merupakan untaian bit yang memuat bit $1$ dalam jumlah yang sama merupakan relasi kesetaraan. Kemudian, tentukan kelas kesetaraan dari untaian bit $011$ untuk relasi kesetaraan $R.$
Misalkan $A$ merupakan himpunan semua untaian bit dan $$R = \{(s, t) \mid s~\text{dan}~t~\text{mempunyai banyak bit}~1~\text{yang sama}\}.$$Untuk membuktikan bahwa $R$ merupakan relasi kesetaraan, kita perlu membuktikan bahwa $R$ refleksif, simetris, dan transitif.
Relasi refleksif: Ambil sembarang $s \in A.$ Jelas bahwa $(s, s) \in R$ karena satu untaian bit yang sama tentu memiliki banyak bit $1$ yang sama pula.
Refleksi simetris: Ambil sembarang $s, t \in A.$ Misalkan $(s, t) \in R,$ berarti $s$ dan $t$ memiliki banyak bit $1$ yang sama. Hal ini sama saja dengan mengatakan bahwa $t$ dan $s$ memiliki banyak bit $1$ yang sama. Artinya, $(t, s) \in R.$
Refleksi transitif: Ambil sembarang $s, t, u \in A.$ Misalkan $(s, t), (t, u) \in R.$ Perhatikan bahwa $s$ dan $t$ memiliki banyak bit $1$ yang sama. Sementara itu, $t$ dan $u$ memiliki banyak bit $1$ yang sama pula. Hal ini jelas mengimplikasikan bahwa $s$ dan $u$ memiliki banyak bit $1$ yang sama pula.
Karena $R$ refleksif, simetris, dan transitif, berdasarkan definisi, terbukti bahwa $R$ merupakan relasi kesetaraan.
Berikutnya, akan ditentukan kelas kesetaraan dari untaian bit $011$ untuk relasi kesetaraan $R.$ Dalam hal ini, $[011]$ menyatakan himpunan untaian bit yang memuat bit $1$ sebanyak dua kali, seperti $11, 0011, 1010, 00011,$ dan sebagainya. Dari sini, dapat diketahui bahwa kelas kesetaraan $[011]$ memiliki takberhingga banyaknya anggota.