Relasi Terurut Sebagian (POSET)

Relasi sering digunakan untuk mengurutkan elemen-elemen di dalam himpunan. Misalnya, elemen-elemen di dalam himpunan bilangan bulat terurut oleh relasi (lebih kecil dari atau sama dengan). Karena elemen-elemen tersebut terurut berdasarkan relasi , maka jika diberikan sebuah elemen bilangan bulat, kita dapat menentukan bilangan bulat berikutnya atau bilangan bulat sebelumnya.

Secara intuitif, di dalam relasi pengurutan parsial, istilah pengurutan berarti dua buah benda saling berhubungan jika salah satunya lebih kecil (lebih besar), daripada, atau lebih rendah (lebih tinggi) daripada lainnya menurut sifat atau kriteria tertentu. Istilah pengurutan itu sendiri memang menyatakan bahwa benda-benda di dalam himpunan tersebut diurutkan berdasarkan sifat atau criteria tersebut. Akan tetapi, ada juga kemungkinan dua buah benda di dalam himpunan tidak berhubungan dalam suatu relasi pengurutan parsial. Dalam hal demikian, kita tidak dapat mmbandingkan keduanya sehingga tidak dapat diidentifikasi mana yang lebih besar atau lebih kecil. Oleh karena itulah digunakan istilah pengurutan parsial atau pengurutan tidak-lengkap. Secara formal didefinisikan sebagai berikut.

Definisi

Jika R relasi pada A dan R memenuhi sifat :

1. Reflektif, yaitu berlaku
   
2. Antisimetri, yaitu ,  dan  berakibat
   
3. Transitif, yaitu ,  dan  berakibat
   

Maka relasi R pada A tersebut mendefinisikan suatu urutan parsial (partial order).

Contoh 1 :

Periksa apakah relasi “x habis membagi y” pada himpunan A = {1, 2, 3, 4, 6} merupakan Relasi Terurut Sebagian.

Sebelumnya kita harus mendaftarkan terlebih dahulu anggota R yang memenuhi relasi diatas. R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (6, 6)}. Setelah itu kita harus selidiki apakah ketiga sifat pada Definisi diatas ada pada relasi R ini.

1. Reflektif
   

   (1, 1), (2, 2), (3, 3), (4, 4), dan (6, 6) R untuk setiap elemen di A.
   

   Berdasarkan definisi Transitif, maka R bersifat transitif
   

2. Antisimetri
   

   Berdasarkan Definisi maka berlaku (a, b) R dan (b, a) R berakibat a = b untuk setiap a, b A. Dan untuk a b berlaku (a, b) R tetapi (b, a) bukan elemen R
   

3. Transitif
   

   Jelas bersifat transitif, silahkan dicek sendiri.
   

Contoh 2 :

Misalkan S dan relasi “” menyatakan urutan kurang dari. Apakah relasi “” pada S merupakan terurut sebagian ?

Relasi bersifat transitif karena untuk setiap a S berlaku a a. Kemudian untuk sifat antisimetri juga berlaku pada relasi ini karena a b dan b a jika a = b dan selain itu a b tetapi b a jika a b. Untuk sifat yang ketiga yaitu sifat transitif juga berlaku karena jika a b dan b c maka a c untuk a, b, c S. Jadi relasi “” termasuk terurut sebgaian.

Sumber :

Bahri, S., 2006, Logika dan Himpunan, Universitas Mataram, Mataram.

Munir, R., 2009, Matematika Diskrit, Informatika, Bandung.