Last Updated on Februari 24, 2022 by prooffic
Postingan kali ini akan membahas mengenai kongruen modulo dan relasi ekuivalen. Adapun isi dari postingan ini adalah membuktikan bahwa kongruen modulo merupakan relasi ekuivalen. Selain itu, kita juga akan menentukan (dan membuktikan) kelas-kelas ekuivalen dari relasi kongruen modulo.
Relasi Ekuivalen
Misalkan $”\sim”$ adalah menyatakan suatu relasi biner pada suatu himpunan $X$, yaitu $a\sim b$ untuk $a$ di domain dan $b$ di kodomain. Relasi tersebut dikatakan sebagai relasi ekuivalen jika memenuhi sifat refleksif, simetri, dan transitif sebagai berikut.
Sifat Refleksif
$”\sim”$ memenuhi sifat refleksif jika untuk setiap $a \in X$, berlaku $a\sim a$.
Sifat Simetri
$”\sim”$ memenuhi sifat simetri jika untuk setiap $a,b \in X$ berlaku $a\sim b$ jika dan hanya jika $b\sim a$.
Sifat Transitif
$”\sim”$ memenuhi sifat transitif jika untuk setiap $a,b \in X$ dengan $a\sim b$ dan $b\sim c$, berlaku $a\sim c$.
Kelas-kelas ekuivalen relasi $\sim$ pada $X$ didefinisikan sebagai berikut. Misalkan $a \in X.$ Kelas ekuivalen dari $a$ dinotasikan dengan $[a]$ dan didefinisikan dengan $$[a] = \{b \in a : b\sim a\} $$Karena relasi tersebut adalah relasi ekuivalen, maka relasi tersebut adalah relasi refleksif dan $a \sim a$ yang berakibat bahwa $a \in [a].$ Oleh karena itu, $[a] \neq \emptyset.$ Oleh karena itu, dapat dikatakan bahwa setiap kelas ekuivalen bukan himpunan kosong.
Kelas-kelas ekuivalen pada $X$ atas relasi ekuivalen $”\sim”$ adalah saling lepas atau sama sebagaimana dinyatakan pada sifat berikut.
Sifat 1: Kelas-kelas ekuivalen pada $X$ atas relasi ekuivalen $”\sim”$ adalah saling lepas atau sama
Bukti. Misalkan $a$ dan $b$ adalah anggota dari $X.$ Jika $[a]$ dan $[b]$ adalah saling lepas, maka bukti selesai. Sebaliknya, asumsikan bahwa kedua kelas ekuivalen tersebut tidak saling lepas.
Karena $[a]$ dan $[b]$ tidak saling lepas, maka ada $z \in [a] \cap [b].$ Karena $z \in [a],$ maka $z \sim a$. Kemudian, $z \in [b]$ mengimplikasikan bahwa $z \sim b.$ Berdasarkan asumsi bahwa relasi $”\sim”$ adalah relasi ekuivalen, diperoleh bahwa $a \sim z$ dan $z \sim b$ yang berakibat bahwa $a \sim b$ dan $b \sim a.$
Akan ditunjukkan bahwa $[a]$ dan $[b]$ adalah sama, yaitu dengan menunjukkan bahwa $[a] \subseteq [b]$ dan $[b] \subseteq [a].$
Baca Juga: Kesamaan dua himpunan
Terlebih dahulu ditunjukkan bahwa $[a] \subseteq [b]$. Diberikan sebarang $x \in [a].$ Dari sini, $x \sim a$.
Karena $x \sim a$ dan $a \sim b$, maka $x \sim b$ dan $x \in [b$]. Ini menunjukkan bahwa jika $x \in [a],$ maka $x \in [b].$ Dengan kata lain, kita peroleh bahwa $[a] \subseteq [b].$
Sebaliknya, akan ditunjukkan bahwa $[b] \subseteq [a]$. Caranya mirip seperti sebelumnya.
Diberikan sebarang $x \in [b].$ Dari sini, $x \sim b$.
Karena $x \sim b$ dan $b \sim a$, maka $x \sim a$ dan $x \in [a]$. Ini menunjukkan bahwa jika $x \in [b],$ maka $x \in [a].$ Dengan kata lain, kita peroleh bahwa $[b] \subseteq [a].$
Dari sini, kita telah menunjukka bahwa $[a] \subseteq [b]$ dan $[b] \subseteq [a].$ Oleh karena itu, kita menyimpulkan bahwa $[a] = [b].$ Secara keseluruhan, terbukti bahwa dua kelas ekuivalen $[a]$ dan $[b]$ adalah sama atau saling lepas ♥
Ini memberikan kita informasi bahwa setiap himpunan yang dilengkapi dengan sebuah relasi ekuivalen dapat dibentuk menjadi gabungan dari subhimpunan-subhimpunan yang saling lepas. Perhatikan bahwa meskipun dua kelas ekuivalen $[a]$ dan $[b]$ adalah sama, tetapi $a$ dan $b$ belum tentu sama. Contohnya dapat kita temui pada bagian berikutnya.
Sifat penting lainnya dari relasi ekuivalen adalah sebagai berikut.
Sifat 2: Jika $a$ berelasi dengan $b$, maka kelas ekuivalen dari $a$ dan $b$ adalah sama
Bukti. Misalkan $”\sim”$ adalah relasi ekuivalen pada $X.$ Akan ditunjukkan bahwa jika $a, b \in X$ dengan $a \sim b,$ maka $[a] = [b].$
Diberikan $a, b \in X$ dengan $a \sim b$. Dari sini, $b \sim a.$
Misalkan $x \in [a].$ Maka, $x \sim a$. Karena $x \sim a$ dan $a \sim b,$ maka $x \sim b$ dan $x \in [b].$ Ini menunjukkan bahwa $$[a] \subseteq [b]$$
Sebaliknya, misalkan $x \in [b].$ Maka, $x \sim b$. Karena $x \sim b$ dan $b \sim a,$ maka $x \sim a$ dan $x \in [a].$ Ini menunjukkan bahwa $$[b] \subseteq [a]$$
Oleh karena itu, kita menyimpulkan bahwa kedua kelas ekuivalen tersebut adalah sama, yaitu $[a] = [b]$ ♥
Kongruen Modulo
Salah satu contoh dari relasi biner dalam matematika adalah relasi kongruen modulo pada himpunan bilangan bulat $\mathbb{Z}$. Diberikan bilangan asli $N.$ Misalkan $”\sim”$ menyatakan relasi kongruen modulo $N,$ yaitu $a\sim b$ jika $a \equiv \bmod{N}$ atau dengan kata lain, $a\sim b$ jika $N$ membagi habis $a-b.$
Kongruen Modulo adalah Relasi Ekuivalen
Pada bagian ini, kita akan menunjukkan bahwa relasi kongruen modulo yang didefinisikan sebelumnya adalah relasi ekuivalen. Setelah itu, kita akan menentukan kelas-kelas ekuivalennya.
Bukti bahwa kongruen modulo adalah relasi ekuivalen
Akan ditunjukkan bahwa relasi kongruen modulo adalah kelas ekuivalen. Diberikan bilangan asli $N.$ Misalkan $”\sim”$ menyatakan relasi kongruen modulo, yaitu dua buah bilangan bulat $a$ dan $b$ saling berelasi, ditulis $a\sim b$ jika $a \equiv \bmod{N}$.
Sifat Refleksif: Misalkan $a \in \mathbb{Z}.$ Karena $a – a = 0$ dapat dibagi oleh $N,$ maka $a \equiv b \bmod{N}$ dan $a \sim a.$ Oleh karena itu, relasi kongruen modulo memenuhi sifat refleksif.
Sifat Simetri: Misalkan $a, b \in \mathbb{Z}.$ Asumsikan bahwa $a \sim b,$ yaitu $a \equiv b \bmod{N}.$ Maka, $N$ membagi habis $a -b$ . Dari sini, $N$ juga haruslah membagi $b-a$ yang berakibat bahwa $b \equiv a \bmod{N}$. Oleh karena itu, $b \sim a.$ Akibatnya, relasi kongruen modulo memenuhi sifat simetri.
Sifat Transitif: Misalkan $a, b, c \in \mathbb{Z}.$ Asumsikan bahwa $a \sim b$ dan $b \sim c.$ Dari sini $$a \equiv b \bmod{N} $$dan $$b \equiv c \bmod{N} $$Oleh karena itu, $N$ membagi habis $a-b$ dan $b-c$. Akibatnya, $N$ juga membagi habis $(a-b)+(b-c) = a-c$ atau $a \equiv c \bmod{N}$. Karena $a \equiv c \bmod{N}$, maka $a \sim c.$ Jadi, relasi kongruen modulo memenuhi sifat transitif.
Karena relasi kongruen modulo memenuhi sifat refleksi, sifat simetri, dan sifat transitif, maka kita dapat menyimpulkan bahwa relasi kongruen modulo adalah relasi ekuivalen.
Selanjutnya adalah menentukan kelas-kelas ekuivalen dari relasi kongruen modulo.
Kelas-kelas ekuivalen relasi kongruen modulo
Misakan $N$ adalah sebarang bilangan asli. Akan ditunjukkan bahwa kelas-kelas ekuivalen dari relasi kongruen modulo untuk $N$ adalah $$[0], [1], …, [N-1] $$dengan menunjukkan bahwa untuk setiap kelas ekuivalen $[a]$ dengan $a \in \mathbb{Z},$ diperoleh bahwa $[a]$ pada dasarnya sama dengan suatu kelas-kelas ekuivalen tersebut, yaitu $$[a] = [r] $$untuk suatu $0 \leq r < N.$
Untuk itu, misalkan $a$ adalah sebarang bilangan bulat. Tinjau kelas ekuivalen $[a]$.
Berdasarkan Algoritma Euclid, maka $$a = kN + r $$untuk suatu $k \in \mathbb{Z}$ dan $r$ bilangan bulat dengan $0 \leq r < N.$ Dari sini, $$a – r = kN $$dan $N$ membagi habis $a-r$ yang berakibat bahwa $a \equiv r \bmod{N}$ dan $a \sim r.$
Karena $a \sim r,$ maka $a \in [r].$ Berdasarkan sifat 2 yang telah dibuktikan sebelumnya, maka $[a] = [r].$
Oleh karena itu, untuk setiap $a \in \mathbb{Z},$ diperoleh bahwa $$[a] = [r] $$untuk suatu bilangan bulat $r$ dengan $0 \leq r < N.$ Ini menunjukkan bahwa kelas-kelas ekuivalen dari relasi kongruen modulo $N$ adalah $$[0], [1], …, [N-1]$$
Kesimpulan
Relasi kongruen modulo dari bilangan asli $N$ adalah relasi ekuivalen dengan kelas-kelas ekuivalennya adalah $$[0], [1], …, [N-1]$$
Demikian pembahasan kali ini terkait dengan kongruen modulo dan relasi ekuivalen. Jika Anda tertarik dengan postingan berupa materi terkait dengan materi himpunan maupun struktur aljabar lainnya, silahk ke sini untuk materi himpunan dan ke sini untuk materi struktur aljabar. Semoga membantu. Sekian dan terima kasih.
