Relasi ekuivalensi

Relasi ekuivalensi adalah relasi biner pada himpunan yang bersifat refleksif, simetris, dan transitif.

Motivasi

Relasi ekuivalensi bisa dipandang sebagai versi yang lebih longgar dari relasi sama dengan. Kita selalu bisa menentukan apakah dua elemen suatu himpunan sama, yaitu apakah a = b. Namun, kadang kita ingin mengetahui apakah dua elemen hanya mirip, tidak harus sama. Dengan kata lain, apakah keduanya memiliki suatu sifat penting yang sama. Misalnya, dua buku bisa kita anggap mirip jika genrenya sama — atau dengan bahasa ekuivalensi: dua buku ekuivalen jika genrenya sama.

Apa yang kita harapkan dari ekuivalensi seperti itu? Mari kita ambil contoh lain. Dua kata disebut mirip/ekuivalen jika panjangnya sama.

Kita tentu berharap bahwa jika kita mengukur kemiripan dua kata yang sama, hasilnya adalah keduanya mirip. Jadi, setiap kata harus mirip/ekuivalen dengan dirinya sendiri. Dalam bahasa relasi: relasi ekuivalensi harus refleksif.

Selanjutnya, jika kata “pohon” mirip/ekuivalen dengan kata “Rizky”, tentu kita berharap kata “Rizky” juga ekuivalen dengan kata “pohon”. Dengan kata lain, urutan tidak penting. Dalam bahasa relasi: relasi ekuivalensi harus simetris.

Terakhir, jika kata “mati” mirip/ekuivalen dengan kata “buku” dan kata “buku” ekuivalen dengan kata “kaki”, kita berharap pasangan kata “mati” dan “kaki” juga ekuivalen. Jadi, relasi ekuivalensi juga harus transitif.

Tidak ada hal lain yang kita harapkan dari ekuivalensi.

Contoh

Contoh-contoh ekuivalensi lainnya:

• Tinggal di kota yang sama. Budi tentu tinggal di kota yang sama dengan Budi (refleksif). Jika Budi tinggal di kota yang sama dengan Andi, Andi juga tinggal di kota yang sama dengan Budi (simetris). Jika Andi tinggal di kota yang sama dengan Rizky, Budi juga tinggal di kota yang sama dengan Rizky (transitif).
• Lagu-lagu dengan pencipta yang sama. Lagu “Monolog Marah Anak Tutup Got” tentu memiliki pencipta yang sama dengan lagu “Monolog Marah Anak Tutup Got” (refleksif). Jika lagu “Monolog Marah Anak Tutup Got” dan “Perang di Kandang Bebek” memiliki pencipta yang sama, maka “Perang di Kandang Bebek” dan “Monolog Marah Anak Tutup Got” juga memiliki pencipta yang sama (simetris). Jika “Perang di Kandang Bebek” dan “Ekspedisi Mencari Kebenaran Lumpur” memiliki pencipta yang sama, maka “Monolog Marah Anak Tutup Got” dan “Ekspedisi Mencari Kebenaran Lumpur” juga memiliki pencipta yang sama (transitif).
• (a, b) ∈ R jika dan hanya jika a − b bilangan genap; a, b bilangan bulat. Sifat refleksif: a − a = 0, dan nol adalah bilangan genap. Sifat simetris: misalkan c = a − b. Maka b − a = −(a − b) = −c. Jika c genap, −c juga harus genap. Sifat transitif: misalkan p = a − b dan q = b − c. Kita tahu bahwa p dan q bilangan genap. Sekarang kita harus membuktikan bahwa a − c bilangan genap. Ke dalam bentuk ini, untuk c kita substitusikan c = b − q: a − (b − q), yang sama dengan a − b + q. Dari asumsi, kita tahu bahwa a − b bilangan genap. Jika bilangan genap ditambah bilangan genap lain q, hasilnya juga bilangan genap.
• Relasi sama dengan. Relasi sama dengan adalah ekuivalensi, sekaligus ekuivalensi terkecil pada sembarang himpunan M.

Ekuivalensi trivial

Misalkan diberikan himpunan tak kosong M. Apa ekuivalensi terkecil yang mungkin R pada himpunan M? Himpunan bagian terkecil yang mungkin dari hasil kali Kartesius M × M adalah himpunan kosong ∅. Apakah himpunan kosong memenuhi syarat ekuivalensi?

Himpunan kosong pasti simetris: karena relasi R tidak memiliki elemen, syarat simetris otomatis terpenuhi secara trivial. Begitu pula sifat transitif. Masalahnya ada pada sifat refleksif. Definisinya menyatakan bahwa untuk semua elemen x himpunan M berlaku (x, x) ∈ R. Apakah syarat ini terpenuhi? Himpunan M tidak kosong, jadi memuat suatu elemen, misalnya q. Apakah pasangan (q, q) berada dalam relasi R? Tidak. Jadi, relasi R tidak refleksif.

Apa relasi terkecil yang refleksif? Relasi sama dengan. Relasi R harus memuat paling sedikit pasangan (x, x) untuk semua elemen M. Itulah relasi identitas. Apakah relasi ini simetris? Dengan mudah terlihat bahwa ya. Dengan mudah terlihat juga bahwa relasi ini transitif. Jadi, relasi ekuivalensi terkecil pada himpunan M adalah relasi identitas, yang dilambangkan id_M dan memuat pasangan (x, x) untuk semua x ∈ M.

Apa ekuivalensi terbesar yang mungkin pada himpunan M? Himpunan bagian terbesar adalah seluruh himpunan M × M. Apakah himpunan ini memenuhi syarat ekuivalensi? Cukup jelas bahwa ya.

Kelas ekuivalensi

Setiap ekuivalensi membagi himpunan M menjadi keluarga himpunan yang saling lepas, yang disebut kelas ekuivalensi.

Misalkan M adalah himpunan semua kata dan R adalah ekuivalensi “kata yang sama panjang”. Jadi, (a, b) ∈ R jika dan hanya jika kata a dan b memiliki panjang yang sama. Ekuivalensi ini membagi himpunan kata menjadi beberapa himpunan yang lebih kecil, yang masing-masing memuat kata-kata dengan panjang yang sama. Kelas-kelas ekuivalensi dapat dibedakan dengan indeks bawah, yang sekaligus menunjukkan panjang kata dalam himpunan tersebut:

• M₁ = {a, i, o, e, …}
• M₂ = {di, ke, ya, om, tu, …}
• M₃ = {ada, itu, dan, tak, …}
• M₄ = {mati, buku, kaki, mata, …}
• …

Perhatikan dua hal: 1) himpunan-himpunan tersebut saling lepas, tidak memiliki elemen bersama. 2) semua elemen dalam setiap himpunan saling ekuivalen. Semua kata dalam himpunan M₃ saling ekuivalen, karena semuanya memiliki panjang tiga, yaitu panjang yang sama, dan itulah syarat ekuivalensinya.

Selain itu, setiap elemen menentukan kelas ekuivalensinya secara tunggal. Hal ini biasanya ditulis dengan notasi M[x], dengan x ∈ M. Jika kita menulis M[ada], kita menentukan secara tunggal kelas ekuivalensi yang sudah kita beri lambang M₃.

Bagaimana cara mencari kelas ekuivalensi jika kita mengetahui suatu x ∈ M? Kita periksa semua elemen M dan kita tentukan elemen mana yang ekuivalen dengan elemen x. Elemen-elemen itulah yang membentuk kelas ekuivalensi M[x].

Untuk M[ada], kita akan memeriksa semua kata dalam M dan menyimpan dalam M₃ kata-kata yang panjangnya tiga.

Definisi dan sifat-sifat kelas ekuivalensi

Kelas ekuivalensi dapat didefinisikan sebagai berikut. Misalkan diberikan himpunan M dan ekuivalensi R yang didefinisikan pada himpunan tersebut. Kelas ekuivalensi yang memuat elemen x ∈ M adalah:

$$M[x]=\{y\in M;(x,y)\in R\}$$

Definisi ini menyatakan bahwa kelas tersebut terdiri atas semua y yang ekuivalen dengan elemen x yang diberikan. Karena relasi ekuivalensi refleksif, elemen x sendiri juga termasuk di dalamnya — karena x ekuivalen dengan dirinya sendiri.

Partisi yang bersesuaian dengan relasi ekuivalensi adalah himpunan semua kelas ekuivalensi. Jadi, partisi himpunan semua kata adalah himpunan {M₁, M₂, M₃, …}.

Sifat-sifat dasar kelas ekuivalensi:

• (a, b) ∈ R jika dan hanya jika M[a] = M[b]. Jika dua elemen a, b ekuivalen, kelas ekuivalensinya harus sama.
• Sebaliknya, jika tidak berlaku (a, b) ∈ R, maka juga M[a] ≠ M[b], tepatnya M[a] ∩ M[b] = ∅. Jika dua elemen tidak ekuivalen, kelas ekuivalensinya saling lepas.
• Gabungan semua kelas ekuivalensi harus sama dengan himpunan semula M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Penulisan ini hanya untuk banyak kelas ekuivalensi yang berhingga, tetapi secara umum banyaknya bisa tak hingga.)

Contoh partisi menurut relasi ekuivalensi

Contoh pertama, bilangan ganjil dan bilangan genap:

Misalkan diberikan ekuivalensi sederhana R yang didefinisikan pada bilangan asli N. (a, b) ∈ R jika dan hanya jika a dan b sama-sama ganjil atau a dan b sama-sama genap. Contoh elemennya: (1, 7), (13, 9), (4, 6), (8, 136). Sekarang kita tentukan partisi ekuivalensi ini menjadi kelas-kelas ekuivalensi.

Kita mulai langkah demi langkah. Apa isi kelas N[1]? Kita harus mencari semua bilangan yang ekuivalen dengan bilangan satu. Menurut syarat ekuivalensi, bilangan-bilangan itu adalah semua bilangan ganjil, sehingga N[1] = {1, 3, 5, 7, 9, …}.

Apa isi kelas N[2]? Kita cari semua bilangan yang ekuivalen dengan dua. Bilangan-bilangan itu adalah semua bilangan genap: N[2] = {2, 4, 6, 8, 10, …}.

Sekarang N[3]. Bilangan apa saja yang ekuivalen dengan tiga? Semua bilangan ganjil. Namun, dengan begitu kita memperoleh himpunan N[1] yang sudah kita hitung dua paragraf sebelumnya. Begitu pula untuk N[4], kita kembali memperoleh himpunan bilangan genap.

Terlihat bahwa selanjutnya himpunan yang sama akan terus berulang. Hal ini juga terlihat dari fakta bahwa bilangan asli n mana pun yang kita ambil, akan berlaku n ∈ N[1] atau n ∈ N[2]. Tidak ada bilangan asli selain bilangan ganjil dan genap, sehingga kedua himpunan ini membentuk partisi yang bersesuaian dengan ekuivalensi tersebut.

Hal ini mirip dengan ekuivalensi pada himpunan manusia: a dan b sama-sama laki-laki atau a dan b sama-sama perempuan. Partisinya terdiri atas himpunan perempuan dan himpunan laki-laki.

Contoh kedua, nilai mutlak:

Misalkan diberikan ekuivalensi R pada himpunan bilangan bulat Z yang didefinisikan sebagai berikut: (a, b) ∈ R jika dan hanya jika |a| = |b|. (Garis-garis tegak itu adalah nilai mutlak.) Kita kembali bekerja langkah demi langkah:

• Z[0] = {0}. Nol hanya berelasi dengan nol.
• Z[1] = {−1, 1}. Satu berelasi dengan satu dan dengan minus satu, karena |1| = |−1|.
• Z[2] = {−2, 2}. Dua berelasi dengan dua dan dengan minus dua.
• Z[3] = {−3, 3}.
• …

Tentu sudah jelas bagaimana kelanjutannya. Jadi, seluruh partisinya adalah himpunan kelas-kelas berikut:

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

(Yaitu semua pasangan a, −a, dengan a bilangan bulat nonnegatif.) Terlihat bahwa banyaknya kelas tak hingga.