RELASI EKUIVALENSI (Minggu ke-12 dan 13)

RELASI EKUIVALENSI (Minggu ke-12 dan 13)

1.

Relasi Ekuivalensi.

Definisi 1. Diketahui A himpunan tidak kosong. Relasi R pada A (dari A ke A) disebut refleksif jika untuk setiap anggota dari semestanya berlaku aRa R refleksif



( a A).aRa.

Contoh: 1. Relasi mencintai antara orang-orang adalah relasi yang refleksif 2. Relasi kesejajaran antara garis-garis lurus adalah refleksif, sebab a sejajar dengan a sendiri, untuk setiap garis a. 3. Relasi R pada ℝ, dengan a, b   R , jika a 2  2b  b 2  2a , bersifat refleksif 4. Relasi F pada ℤ dengan definisi a, b   F , jika 7 b  a , merupakan relasi refleksif

Definisi 2. Diketahui R relasi : S  S. 1. Relasi R disebut non-refleksif : a  S a, a   R 2. Relasi R disebut non-refleksif : a  S a, a   R Contoh 1. Relasi “lebih tinggi” antara orang-orang merupakan irrefleksif (non refleksif) 2. Diketahui A = { 1, 2, 3, 4 } dan R relasi pada S, dengan a, a 1  R , untuk a  4 ,

4,1  R , dan 2,2  R . 3. Relasi F

Relasi R nonrefleksif (tidak irrefleksif)

pada ℤ dengan

definisi

a, b  F ,

7n  b  a , merupakan relasi irrefleksif

Teorema 1. Jika R irrefleksif, maka R non refleksif

jika terdapat n  ℕ, sehingga

Definisi 3. Relasi R pada A disebut simetris jika untuk setiap a,b dari semestanya berlaku: aRb  bRa. Notasi matematisnya, R simetris



(a,b  A).aRb  bRa.

Contoh 1. Relasi kesejajaran antara garis-garis lurus. 2. Relasi R pada ℝ, dengan a, b   R , jika a 2  2b  b 2  2a 3. Diketahui n bilangan bulat positif. Relasi F pada ℤ dengan definisi a, b   F , jika

pb  a,

Definisi 4. Diketahui R relasi pada S. 1. R non simetris : a, b  S a, b  R  b, a   R  2. R asimetris

: a, b  S a, b  R  b, a   R 

3. R antisimetris : a, b  S a, b  R  b, a   R   a  b

Contoh 1. Relasi “⊂“ pada himpunan kuasa P X  dengan X  , merupakan relasi asimetris. 2. Relasi mencintai pada manusia non simetris, tapi tidak asimetris 3. Relasi “  ” pada ℤ, ℝ, dan ℕ merupakan antisimetris

Teorema 3. R asimetris ⇒ R non simetris

Definisi 5. Relasi R pada A dikatakan transitif jika untuk setiap tripel a,b,c di A berlaku apabila aRb dan bRc maka aRc. Notasi matematisnya, R transitif



(a, b, cS).aRb  bRc  aRc.

Contoh 1. Relasi “  ” pada ℤ, ℝ, dan ℕ 2. Relasi “⊂“ pada himpunan kuasa P X  dengan X  ,

Definisi 6. Diketahui R relasi pada himpunan S. 1. R dikatakan non-transitif : (∃a, b, cS).(a, b)R  (b, c)R  (a, c)R 2. R dikatakan intransitif

: (a, b, cS).(a, b)R  (b, c)R  (a, c)R

Contoh: 1. Pada himpunan semua garis di ℝ3 relasi tegak lurus antar garis, bersifat non transitif tapi tidak intransitif 2. Pada himpunan semua garis di ℝ2 relasi tegak lurus antar garis, bersifat intransitif

Teorema 4. Semua relasi intransitif pasti non transitif. Sebaliknya jika R non transitif, maka belum tentu R intransitif. Contoh: Pada himpunan semua garis di ℝ3 relasi tegak lurus antar garis, bersifat non transitif tapi tidak intransitif

Definisi 7. Suatu relasi R yang sekaligus memiliki sifat refleksif, simetris, dan transitif disebut relasi ekuivalensi.

Contoh : 1. Relasi kesejajaran antara garis – garis lurus pada bidang datar. 2. Relasi R pada ℝ, dengan a, b   R , jika a 2  2b  b 2  2a 3. Relasi kesebangunan antara segitiga-segitga dalam bidang datar. 4. Relasi ““ pada himpunan kuasa P X  dengan X  ,

5. Diambil sebarang bilangan bulat positif m > 1 dan relasi (kongruensi modulo) antara bilangan-bilangan bulat ℤ berikut ini: Didefinisikan relasi modulo m disingkat “mod m” didefinisikan sebagai berikut: a  b(mod m)



(∃kℤ).a – b = km

Keterangan: 1. Sifat refleksif

: a - a = 0.m, sehingga a  a(mod m).

2. Sifat simetris

: Jika a – b = k.m, maka b – a = (-k)m, a  b(mod m) ⇒ b  a(mod m).

3. Sifat transitif

: Jika a  b(mod m) dan b  c(mod m), maka a – b = km dan b – c = lm, ∃ k, l ℤ, Sehingga a – c = (k + l)m, Jadi a  c(mod m).

Relasi modulo m disebut relasi kongruensi, karena memenuhi: 1. a  b(mod m) dan c  d(mod m) ⇒ a + c  b + d(mod m) 2. a  b(mod m) dan c  d(mod m) ⇒ ac  bd(mod m)

Definisi 8. Diketahui A himpunan tak kosong dan K = { Hi | i  I } koleksi subhimpunan A. Koleksi K disebut partisi A jika

i  I H   , i

 H i  A , dan i  j H i  H j   iI

Contoh 1. Misalkan A  1,   . Koleksi K = { (n, n + 1⦌ | nℕ} merupakan partisi A 2. Pada himpunan B = {a, c, d, g, m}, koleksi ℋ = a, g, c, d , m partisi B

Teorema 6. Sebarang relasi ekuivalensi R antara anggota-anggota himpunan A, mengakibatkan adanya partisi (penggolongan) di dalam A.

Akibat 7. Himpunan A terbagi atas himpunan-himpunan bagian (kelas-kelas)

a  x  A xRa, a  A tidak kosong dan saling asing, sehingga x  A!a .x  a A

Contoh Diambil relasi kongruensi modulo m, antara bilangan-bilangan bulat. Untuk a ℤ

a  x x  amod m yaitu : 0  x x  0mod m  ,  2m,  m, 0, m, 2m, 

1  x x  1mod m  ,  2m  1,  m  1, 1, m  1, 2m  1,  ⋮

m  1  x x  m  1mod m  ,  2m  m  1,  m  m  1, m  1, m  m  1, 

 ,  m  1,  1, m  1, 2m  1,  Kelas-kelas tersebut : K   0, 1, 2, , m  1