Relasi Khusus, Ekivalensi, Poset

A. Relasi Khusus

Ada beberapa relasi antar anggota himpunan yang bersifat khusus:

1. Relasi Refleksif

Suatu relasi R dikatakan bersifat refleksif bila dan hanya bila untuk setiap anggota himpunan berelasi R dengan dirinya sendiri, ditulis sebagai "aRa" atau "(a, a) ∈ R".

2. Relasi Simetrik dan Antisimetrik

Suatu relasi R dikatakan bersifat simetrik bila dan hanya bila misalkan a berelasi R dengan b maka b berelasi R dengan a. Ditulis sebagai:

"jika (a, b) ∈ R maka (b, a) ∈ R" atau "aRb → bRa"

Sedangkan suatu relasi R dikatakan bersifat antisimetrik bila dan hanya bila misalkan a berelasi R dengan b dan b berelasi R dengan a maka a sama dengan b. Ditulis sebagai:

"jika (a, b) ∈ R dan (b, a) ∈ R, maka a = b" atau "aRb ∧ bRa → a = b"

3. Relasi Transitif

Suatu relasi R dikatakan bersifat transitif bila dan hanya bila misalkan a berelasi R dengan b dan b berelasi R dengan c maka a berelasi R dengan c. Ditulis sebagai:

"jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R" atau "aRb ∧ bRc → aRc"

4. Relasi Ekivalensi, Kompatibilitas, Urutan Parsial

Suatu relasi R yang bersifat refleksif, simetrik, dan transitif disebut relasi ekivalensi. Suatu relasi R yang bersifat refleksif, dan simetrik disebut relasi kompatibilitas. Suatu relasi R yang bersifat refleksif, antisimetrik, dan transitif disebut relasi urutan parsial. Suatu himpunan A yang dilengkapi dengan suatu relasi urutan parsial R disebut himpunan terurut parsial (partially ordered set, disingkat poset).

B. Kelas Ekivalensi dan Partisi

1. Kelas Ekivalensi

Suatu himpunan dengan relasi ekivalensi, terbentuklah kelas ekivalensi. Kelas ekivalensi dari elemen a adalah semua anggota himpunan yang berelasi dengan a.

Misalkan ada sebuah himpunan dengan relasi ekivalensi, yang beranggotakan {a, b, c, d, e, f, g, h}, elemen a ekivalen dengan elemen c dan f, berarti kelas ekivalensi dari elemen a adalah {a, c, f}.

2. Partisi

Suatu himpunan dengan relasi ekivalensi akan membangkitkan partisi, karena setiap anggota himpunan akan terkelompokkan dengan anggota-anggota yang berelasi dengannya.

Misalkan ada sebuah himpunan dengan relasi ekivalensi, yang beranggotakan {a, b, c, d, e, f, g, h}, elemen a ekivalen dengan elemen c dan f, terbangkitkan partisi {a, c, f}, elemen b ekivalen dengan elemen d dan h, terbangkitkan partisi {b, d, h}, elemen e ekivalen dengan g, terbangitkan partisi {e, g}. Famili himpunan partisi yang terbangkitkan adalah {{a, c, f}, {b, d, h}, {e, g}}.

C. Himpunan Terurut Parsial (Poset)

Sebagaimana telah disebutkan sebelumnya bahwa himpunan terurut parsial (partially ordered set, disingkat poset) adalah himpunan dengan relasi urutan parsial. Ada 2 macam urutan parsial, yaitu:

1. Urutan parsial tak tegas (disimbolkan ≤)

Urutan parsial tak tegas memiliki sifat-sifat sebagai berikut:

a. Refleksif (a ≤ a), artinya setiap elemen berelasi dengan dirinya sendiri

b. Antisimetrik (a ≤ b ∧ a ≤ b → a = b), artinya tidak ada dua elemen berbeda yang saling mendahului

c. Transitif (a ≤ b ∧ b ≤ c → a ≤ c)

2. Urutan parsial tegas (disimbolkan <)

Urutan parsial tegas memiliki sifat-sifat sebagai berikut:

a. Irrefleksif ~(a < a), artinya setiap elemen tidak berelasi dengan dirinya sendiri

b. Asimetrik (a < b → ~(b < a)), artinya tidak ada dua elemen yang saling berelasi

c. Transitif (a < b ∧ b < c → a < c)

Korespondensi antara relasi tak tegas dengan relasi tegas adalah:

a < b berkorespondensi dengan a ≤ b ∧ a ≠ b

a ≤ b berkorespondensi dengan a < b ∨ a = b

Contoh soal dan pembahasan

1. Diketahui X adalah himpunan semua garis lurus pada bidang datar dan R adalah relasi sejajar antara garis lurus. Apakah relasi R itu bersifat refleksif, simetrik, antisimetrik, transitif?

Relasi itu tidak refleksif karena setiap garis tidak sejajar dengan dirinya sendiri, melainkan berhimpit

Relasi itu simetrik karena jika garis 1 sejajar dengan garis 2 maka garis 2 sejajar dengan garis 1

Relasi itu tidak antisimetrik karena kedua garis yang sejajar pasti beda

Relasi itu transitif karena jika garis 1 sejajar dengan garis 2 dan garis 2 sejajar dengan garis 3 maka garis 1 sejajar dengan garis 3

2. Pada himpunan X = {1, 2, 3, 4, 5, 6} diketahui relasi R = {(1, 1), (1, 5), (2, 2), (2, 3), (2, 6), (3, 2), (3, 3), (3, 6), (4, 4), (5, 1), (5, 5), (6, 2), (6, 3), (6, 6)}

(a) Buktikan bahwa relasi R tersebut adalah suatu relasi ekivalensi.

Refleksif: {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}, dari sini R refleksif

Simetrik: {(1, 5), (5, 1), (2, 3), (3, 2), (2, 6), (6, 2), (3, 6), (6, 3)}, dari sini r simetrik

Transitif: {(2, 3), (3, 6), (2, 6)}, dari sini r transitif

Karena R refleksif, simetrik, dan transitif, maka R ekivalen

(c) Tentukan partisi yang dibangkitkan oleh relasi ekivalensi R itu.

X = {{1, 5}, {2, 3, 6}, {4}}

3. Diketahui himpunan semua bilangan cacah C, pada C × C didefinisikan relas R sebagai berikut:

(a, b)R(c, d) ↔ a + d = b + c. Selidiki apakah R relasi ekivalen. Jika R ekivalen tentukan kelas ekivalen yang memuat (0, 0) dan juga kelas ekivalen yang memuat (1, 0).

Untuk menyelidiki ekivalen, perlu diselidiki ketiga syarat ekivalen:

(i) Refleksif

(a, b)R(a, b) ↔ a + b = b + a

Jelas bahwa a + b = b + a, sehingga R refleksif

(ii) Simetrik

(a, b)R(c, d) ↔ a + d = b + c ↔ d + a = c + b ↔ c + b = d + a ↔ (c, d)R(a, b)

Dari sini R simetrik

(iii) Transitif

(a, b)R(c, d) ↔ a + d = b + c

(c, d)R(e, f) ↔ c + f = d + e

a + d + c + f = b + c + d + e ↔ a + f = b + e ↔ (a, b)R(e, f)

Dari sini R transitif

Karena R refleksif, simetrik, dan transitif maka R ekivalen.

4. Didefinisikan Relasi R pada himpunan S dengan (∀a,b,c ∈ S).aRb ∧ bRc → cRa

Buktikan bahwa jika R refleksif maka R merupakan relasi ekivalen!

Diketahui aRb ∧ bRc → cRa

R refleksif berarti bRb, sehingga diperoleh:

aRb ∧ bRb → bRa

aRb → bRa berarti R simetrik

R simetrik berarti cRa → aRc, sehingga diperoleh:

aRb ∧ bRc → aRc yang berarti R transitif

Karena R refleksif, simetrik, dan transitif maka R ekivalen

Terbukti

Tonton video relasi antar anggota himpunan: