Relasi Ekivalen (Teogrup)

1. Definisi dan Contoh

A. Definisi Relasi

Misalkan S suatu himpunan tak kosong dan misalkan pula R suatu subset tak kosong dari hasil kali kartesius S×S. Secara umum kita katakan bahwa R adalah suatu relasi pada S.

B. Relasi Ekivalen

Relasi R adalah relasi ekivalen pada S jika memenuhi ketiga sifat berikut:

1. Refleksif

(a, a) ∈ R, untuk semua a ∈ S

2. Simetris

Jika (a, b) ∈ R, maka (b, a) ∈ R, untuk semua a, b ∈ S

3. Transitif

Jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk semua a, b, c ∈ S.

Jika (a,b) unsur suatu relasi ekuivalen, kita katakan bahwa a ekuivalen dengan b.

C. Contoh

Berikut ini beberapa contoh:

1. Relasi "=" merupakan relasi ekivalen.

2. Relasi "≤" dan "≥" bukan relasi ekivalen karena tidak simetris.

3. Relasi "<" dan ">" bukan relasi ekivalen karena tidak refleksif.

4. Kekongruenan modulo m pada aritmetika modular merupakan relasi ekivalen.

2. Poset (Relasi Terurut)

A. Poset Tidak Tegas

Relasi R adalah relasi poset tidak tegas pada S jika memenuhi ketiga sifat berikut:

1. Refleksif

(a, a) ∈ R, untuk semua a ∈ S

2. Antisimetris

Jika (a, b) ∈ R dan (b, a) ∈ R, maka a = b, untuk semua a, b ∈ S

3. Transitif

Jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk semua a, b, c ∈ S.

Contoh paling umum untuk poset tidak tegas adalah relasi "≤" dan "≥".

B. Poset Tegas

Relasi R adalah relasi poset tegas pada S jika memenuhi ketiga sifat berikut:

1. Irrefleksif

(a, a) ∉ R, untuk semua a ∈ S

2. Asimetris

Jika (a, b) ∈ R maka (b, a) ∉ R, untuk semua a, b ∈ S

3. Transitif

Jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk semua a, b, c ∈ S.

Contoh paling umum untuk poset tegas adalah relasi "<" dan ">".

3. Definisi Partisi

Suatu koleksi 𝒫 = {Sᵢ ⊆ S | 1 ≤ i ≤ n} dengan (∀i). Sᵢ ≠ ∅ adalah suatu partisi dari S jika berlaku:

a. S₁ ∪ S₂ ∪ ... ∪ Sₙ = S

b. (∀i, j). i ≠ j ⇒ Sᵢ ∩ Sⱼ = ∅

Boleh juga dikatakan 𝒫 adalah suatu partisi dari S jika berlaku (∀a ∈ S)(∃!i) ∋ a ∈ Sᵢ.

4. Keterkaitan Relasi Ekivalen dengan Partisi

Misal R relasi ekivalen pada S. Untuk setiap a ∈ S didefinisikan himpunan:

[a] = {b ∈ S : (b, a) ∈ R}

Diperoleh koleksi {[a] : a ∈ S} membentuk partisi dari S.

Dengan kata lain, relasi ekivalen membangkitkan partisi.

Selanjutnya himpunan yang termuat dalam suatu partisi yang terbangkitkan oleh suatu relasi ekivalen disebut sebagai kelas ekivalensi.

5. Algoritma Pembagian

(∀a ∈ ℤ)(∀b ∈ ℕ)(∃!q ∈ ℤ) ∋ a = bq + r; dengan r ∈ ℤ ∧ 0 ≤ r < b.

Misalkan [a] kelas ekuivalen yang memuat a ∈ ℤ untuk relasi Rₙ. Dengan algoritma pembagian kita dapatkan a = qn + r, untuk suatu q, r ∈ ℤ dengan 0 ≤ r < n. Perhatikan bahwa a – r = qn, suatu kelipatan dari n, sehingga r ∈ [a], yang berarti [a] = [r].

Perhatikan kelas-kelas ekuivalen [0], [1], ..., [n – 1]. Ke-n kelas ekuivalen ini berbeda karena tidak ada pasangan bilangan berbeda di antara 0, 1, ..., n – 1 yang termuat dalam Rₙ. Selain itu, setiap bilangan bulat mesti termuat di dalam salah satu dari n kelas ekuivalen tersebut. Ini berarti bahwa [0], [1], ..., [n – 1] adalah kelas-kelas ekuivalen lengkap untuk Rₙ. Dengan demikian, Rₙ memunculkan n kelas ekuivalen.

6. Relasi Keinversan

Misalkan U subgrup dari G. Misal diambil relasi R = {(u, v) ∈ G × G: uv⁻¹ ∈ U}.

Klaim: R merupakan relasi ekivalen.

Bukti:

• Refleksif

Ambil sebarang a ∈ G.

Elemen (a, a), a ∈ G, mestilah terdapat di R. Ini benar karena aa⁻¹ = e ∈ U.

• Simetris

Misalkan (a, b) ∈ R. Maka ab⁻¹ ∈ U. Akibatnya ba⁻¹ = (ab⁻¹)⁻¹ ∈ U, sehingga (b, a) ∈ R. Jadi, jika (a, b) ∈ R, maka (b, a) ∈ R.

• Transitif

Misalkan (a, b), (b, c) ∈ R. Maka ab⁻¹, bc⁻¹ ∈ U. Dengan demikian ac⁻¹ = a(b⁻¹b)c⁻¹ = (ab⁻¹)(bc⁻¹) ∈ U, sehingga (a, c) ∈ R. Jadi, jika (a, b), (b, c) ∈ R, maka (a, c) ∈ R.

Jadi R adalah benar suatu relasi ekuivalen.