Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas teorema relasi ekivalen dalam matematika diskrit. Teorema tersebut menyatakan bahwa jika relasi R ekivalen atas himpunan A, maka A berrelasi dengan B, kelas A sama dengan kelas B, dan kelas A diiris kelas B tidak kosong. Dari teorema tersebut, dapat didefinisikan partisi dari suatu himpunan S sebagai himpunan bagian tak kosong yang saling lepas dan gabungannya membentuk S. Sifatnya bolak-balik, di mana relasi ekivalen atas A akan membentuk partisi, dan sebaliknya. Contohnya, partisi himpunan bilangan bulat Z dengan relasi kongruen modulo 3 membentuk 3 kelas yang saling lepas. Demikian pula, pada himpunan untayan biner, terdapat 15 kelas ekivalen yang saling lepas, membentuk partisi sesuai dengan relasi R3.

Kalau kita punya AB anggota A kemudian kita mempunyai relasi R atas himpunan tersebut dan relasinya ekivalen itu ternyata kita punya sifat yang menarik.

Jadi kalau relasi antara A dan B itu ada atau A itu berrelasi dengan B, maka kelas A itu akan sama dengan kelas B dan juga kelas A dengan kelas B itu enggak mungkin irisannya kosong, enggak mungkin saling lepas.

Jadi ada teoremanya yang merangkum hal tersebut yang mengatakan misalkan R relasi ekivalen atas himpunan A,

maka pernyataan-pernyataan terkait AB anggota A berikut adalah ekivalen yaitu A berrelasi dengan B, kelas A itu sama dengan kelas B dan kelas A diiris kelas B itu tidak kosong.

Sekarang kita lihat buktinya, bukti yang pertama itu kita akan buktikan itu pernyataan ekivalen tidak berarti ekivalennya sama dengan kelas ekivalen,

ekivalen itu artinya dia bisa saling dibuktikan yang pertama itu akan mengakibatkan B jadi jika dan hanya jika sifatnya begitu juga B dengan C juga jika dan hanya jika.

Sekarang kita akan mau buktikan ketiga pernyataan tersebut ekivalen dalam arti pernyataan satu itu akan mengakibatkan pernyataan kedua,

kemudian pernyataan kedua itu akan mengakibatkan pernyataan ketiga dan pernyataan ketiga akan mengakibatkan pernyataan yang pertama.

Yang pernyataan pertama ke kedua itu artinya kalau kita tahu A berrelasi dengan B maka kelas ekivalennya diantara mereka itu sama,

jadi kelas ekivalen A itu sama dengan kelas ekivalen B.

Untuk membuktikannya kita pakai pembuktian dengan menunjukkan kelas ekivalen A itu subset dengan kelas ekivalen B dan juga sebaliknya.

Jadi untuk yang pertama kita ambil C itu anggota kelas A, itu artinya A nya itu akan berrelasi dengan C.

Kalau kita punya A nya berrelasi dengan B maka dengan sifat simetris kita tahu B nya itu juga berrelasi dengan A.

Kalau B berrelasi dengan A, A nya berrelasi dengan C maka dengan sifat transitif B nya itu akan berrelasi dengan C.

Sehingga C nya itu akan masuk ke dalam kelas B, sehingga kita bisa tunjukkan bahwa kelas A itu adalah subset atau subhimpunan dari kelas B.

Sekarang kalau kita mulainya dari B, jadi serupa kita ambil C nya itu anggota kelas B berarti B nya berrelasi dengan C,

kemudian kita lihat A dengan B, kalau A dan B itu berrelasi kemudian B nya berrelasi dengan C maka dengan sifat transitif kita akan dapat A nya berrelasi dengan C.

Artinya C nya masuk di dalam kelas A, sehingga kelas B itu adalah subset kelas A.

Di sini kita sudah membuktikan bahwa kelas ekivalen A itu akan sama dengan kelas ekivalen B.

Untuk yang kedua kita mau buktikan bahwa kalau kelas A nya itu sama dengan kelas B maka irisan dari mereka itu tidak kosong.

Jadi kalau kelas A sama dengan kelas B maka irisannya itu pasti akan sama dengan kelas A atau sama dengan kelas B

dan kelas A itu bersifat refleksif sehingga relasinya bersifat refleksif maka A itu akan masuk di dalam kelas A.

Sehingga enggak mungkin kelas A itu kosong, jadi irisannya juga tidak kosong.

Dan yang terakhir kita akan buktikan kalau irisannya itu tidak kosong maka itu menunjukkan bahwa A dan B itu saling berrelasi atau A berrelasi dengan B.

Kita ambil satu elemen C di irisan kedua kelas, artinya C nya itu ada di kelas A, dia juga ada di kelas B.

Kalau C ada di kelas A berarti C nya berrelasi dengan A, kalau C di kelas B berarti C nya berrelasi dengan B.

Kemudian pakai sifat simetris kita akan dapat A berrelasi dengan C dan C berrelasi dengan B

sehingga dengan sifat transitif kita akan dapat A berrelasi dengan B.

Karena A nya di sini sudah dibuktikan berrelasi B, nanti kita akan juga tunjukkan bahwa kalau A berrelasi B

kelas A itu sama dengan kelas B, kemudian kita juga sudah menunjukkan bahwa kelas A diiris kelas B itu tidak kosong.

Dan juga kita bisa menunjukkan bahwa nanti A nya berrelasi dengan B, jadi di sini kita punya bukti yang melingkar

sehingga ketiga pernyataan tersebut ekivalen.

Dari pernyataan tadi atau teorema tadi kita bisa mendefinisikan suatu istilah yang disebut sebagai partisi dari suatu himpunan S.

Itu adalah himpunan bagian yang tak kosong dari S yang mereka saling lepas dan gabungannya membentuk S.

Jadi artinya misalnya kita punya AI itu adalah sub-himpunan dari S, I nya masuk di indeks I,

dia akan membentuk partisi karena AI nya tidak kosong untuk setiap I, irisannya kosong kalau I nya tidak sama dengan J

Jadi kalau misalnya kita pakai diagram Venn itu bentuknya misalnya ini S nya maka kita akan membentuk partisi

di sini ada A1, A2, A3 dan selanjutnya yang mereka saling lepas, misalnya di sini ada 6 himpunan.

Jadi irisannya tidak boleh sama tapi gabungannya itu di S sendiri.

Kalau kita lihat contohnya S nya itu himpunan 1, 2, 3, 4, 5, 6, A1 nya 1,2, A2 nya 3,4,5 dan A3 nya 6

itu akan membentuk partisi karena mereka masing-masing himpunan yang tidak kosong,

irisannya kosong dan gabungannya membentuk si S tersebut.

Jadi kita bisa juga mendapatkan sifat yang dirangkum dalam teorema 2,

kalau R nya itu relasi ekivalen atas himpunan A, maka kelas-kelas ekivalen R itu akan membentuk partisi.

Sebaliknya jika himpunan AI itu merupakan partisi,

maka kita bisa membuat suatu relasi ekivalen yang memiliki AI nya sebagai kelas-kelas ekivalensinya.

Kita lihat contohnya, kalau kita daftarkan semua pasangan terurut dalam relasi ekivalen R

yang dihasilkan dari himpunan S itu 1, 2, 3, 4, 5, 6 tadi sebagai A1 nya 1,2, A2 nya 3,4,5 dan A3 nya 6,

maka kalau kita diminta untuk mencari berapa sih atau bagaimana relasi yang terbentuk di situ elemennya apa saja gitu,

di sini kita bisa membuat 1,1, 1,2, 2,1, 2,2 karena di sini A1 merupakan kelas ekivalensi.

Kita bisa membentuk 3,3, 3,4, 3,5, 4,3, 4,4, 4,5, 5,3 dan 5,4 serta 5,5,

dia juga anggota R karena A2 merupakan relasi ekivalensi dan 6,6 anggota R karena A3 nya merupakan kelas ekivalensi.

Jadi kita bisa mendaftarkan semua elemen dari relasinya.

Kalau misalnya tadi saya sudah menggambarkan dengan diagram Venn untuk himpunan S gitu ya,

sekarang kalau kita punya himpunan bilangan bulat Z itu ternyata kita bisa partisi itu dengan relasi kongruen modulo 3.

Jadi kita punya 3 kelas kan ya tadi yang berbeda, jadi kelas 0, kemudian kelas 1,

kemudian kelas 2, kelas 3 nanti akan sama dengan kelas 0, kelas 4 akan sama dengan kelas 1 dan seterusnya.

Jadi kelas 0 tadi dengan modulo 3 itu adalah 0, 3, 6 untuk yang positif dan seterusnya,

min 3, min 6 dan seterusnya untuk yang negatif,

untuk yang kelas 1 itu mulai dari negatif min 5, min 2, 1, 4, 7 dan seterusnya,

kemudian kalau 2 itu isinya antara lain min 4, min 1, 2, 5, 8.

Mereka tidak saling beririsan, jadi ketiga kelas tadi itu tidak saling beririsan dalam arti saling lepas

dan semua bilangan bulat itu masuk di dalam salah satu kelas tersebut, jadi dia akan membentuk partisi.

Kita lihat misalnya soalnya sekarang ganti bukan dalam bentuk S nya impunan bilang bulat,

tapi di sini impunan untayan binar yang relasinya tadi, dia sama atau yang tiga pertamanya.

Kelas ekivalennya untuk panjang untayan yang kurang dari 3 itu isinya adalah lambda,

lambda itu untayan kosong di sini, kemudian ada 00 itu isinya 00, 01 kelas 01 isinya 01,

kelas 10 isinya 10, kelas 11 itu isinya 11 dan seterusnya.

Untuk yang panjang untayannya 3 atau lebih kita bisa melihat kalau yang dimulai dengan 000,

nanti kita akan dapatkan atau daftarkan isinya 000, 000, 0001 dan seterusnya.

Begitu juga untuk yang mulai dengan 001, mulai dengan 010, mulai dari 011, mulai dari 100, 101, 110 dan 111.

Semuanya ada 15 kelas dan saling lepas dan di sini kita akan bisa membentuk kelas partisi

karena kita bisa cek untuk setiap kelas itu dia saling lepas dan nanti dia gabungannya akan membentuk

si impunan dari untayan binar dengan relasi R3.