Relasi urutan

Relasi urutan adalah relasi biner pada himpunan yang bersifat refleksif, antisimetris, dan transitif.

Motivasi

Urutan adalah pengertian umum yang juga kita gunakan dalam kehidupan sehari-hari. Banyak hal dapat kita urutkan dengan cara tertentu — kata-kata menurut abjad, siswa di sekolah menurut tinggi badan, barang menurut harga. Semua ini digambarkan oleh relasi urutan, yang biasanya dilambangkan dengan simbol ≤. Simbol-simbol yang berkaitan adalah: <, >, ≥. Artinya sudah jelas.

Apa yang kita harapkan dari relasi seperti ini? Dari simbolnya saja sudah jelas bahwa elemen-elemen yang sama berada dalam relasi urutan — jadi, kita ingin mendefinisikan sifat-sifat relasi kurang dari atau sama dengan. Karena itu, relasi ini harus refleksif. Harus berlaku a ≤ a.

Apa lagi? Sifat simetris jelas tidak berlaku — jika kita mengurutkan menurut harga dan mobil lebih murah daripada roti, tentu roti tidak lebih murah daripada mobil. Secara umum, apa yang kita harapkan jika ternyata a ≤ b dan sekaligus b ≤ a? Apakah hal itu pernah masuk akal? Ya, jika berlaku a = b. Satu-satunya keadaan ketika urutan elemen dalam relasi tidak penting adalah ketika elemen-elemen itu sama — jadi, relasi urutan bersifat antisimetris.

Terakhir, jika kita tahu bahwa mobil lebih mahal daripada roti dan pesawat lebih mahal lagi daripada mobil, kita berharap pesawat pasti lebih mahal daripada roti. Hal ini digambarkan oleh sifat transitif.

Urutan parsial

Yang baru saja kita definisikan sebenarnya hanyalah urutan parsial, bukan urutan total. Mengapa tidak total? Mari kita coba mendefinisikan urutan pada himpunan-himpunan. Bagaimana cara membandingkan dua himpunan?

Kita katakan bahwa himpunan A kurang dari atau sama dengan himpunan B jika A ⊆ B, yaitu jika A himpunan bagian dari B. Hal ini masuk akal, karena jika A = {1, 2} dan B = {1, 2, 3}, kita bisa mengatakan bahwa A lebih kecil — B memuat elemen-elemen yang sama dengan A dan masih memuat bilangan tiga sebagai tambahan. Jadi, misalnya berlaku:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Masalahnya muncul ketika kita ingin membandingkan himpunan A = {a, b} dan B = {a, c}. Manakah yang lebih kecil atau lebih besar? Kedua himpunan memang memuat elemen a, tetapi elemen keduanya berbeda. Tidak ada himpunan yang merupakan himpunan bagian dari himpunan yang lain, sehingga tidak berlaku A ≤ B maupun B ≤ A. Dengan urutan kita, himpunan-himpunan seperti ini tidak dapat dibandingkan (unsur yang tak terbandingkan).

Karena itu, kita mendefinisikan himpunan terurut total, disebut juga rantai, yaitu himpunan yang setiap dua elemennya dapat dibandingkan. Contoh himpunan seperti ini adalah himpunan bilangan dengan urutan biasa. Untuk setiap dua bilangan real a, b, kamu bisa menentukan apakah a ≤ b atau b ≤ a.

Contoh dari kehidupan sehari-hari

Contoh ketika sebaiknya kita tidak membandingkan adalah urutan menurut kecantikan atau ketampanan; relasi < berarti “kurang menarik”. Mungkin lebih sopan jika kita definisikan sebaliknya, yaitu > sebagai “lebih menarik” :-). Mungkin masuk akal membandingkan dua perempuan, misalnya “Dewi” < “Rina” dalam arti Rina lebih cantik daripada Dewi. Atau dua laki-laki: “Agus” < “Budi” dalam arti Budi lebih tampan daripada Agus.

Masalahnya, sulit membandingkan kecantikan perempuan dengan ketampanan laki-laki. Siapa yang lebih menarik, Rina atau Budi? Siapa yang kurang menarik, Dewi atau Agus? Lebih baik tidak usah diselidiki…

Jika pada contoh terakhir kita membatasi diri, misalnya hanya pada perempuan, kita bisa mengatakan bahwa kita memiliki himpunan terurut total, karena kita dapat membandingkan kecantikan semua perempuan.

Unsur minimal dan maksimal, unsur terkecil dan terbesar

Jika diberikan himpunan terurut M, elemen min ∈ M disebut minimal jika tidak ada x ∈ M yang memenuhi x < min. Artinya, kita tidak dapat menemukan elemen yang lebih kecil daripada elemen min.

Elemen max ∈ M disebut maksimal jika tidak ada x ∈ M yang memenuhi x > max. Artinya, kita tidak dapat menemukan elemen yang lebih besar.

Kedua pengertian ini berbeda dengan pengertian terkecil dan terbesar.

Elemen a ∈ M disebut terkecil jika untuk semua x ∈ M berlaku a ≤ x. Jadi, elemen terkecil a kurang dari atau sama dengan semua elemen lain himpunan M.

Elemen b ∈ M disebut terbesar jika untuk semua x ∈ M berlaku b ≥ x. Elemen terbesar b lebih dari atau sama dengan semua elemen lain himpunan M.

Apa perbedaan antara elemen terbesar dan elemen maksimal? Elemen maksimal bisa lebih dari satu, karena himpunannya belum tentu terurut total. Jika kita kembali ke contoh membandingkan orang menurut penampilan, kita bisa mengatakan bahwa Putri adalah perempuan tercantik dan Rizky adalah laki-laki tertampan. Namun, kedua orang ini tidak dapat kita bandingkan satu sama lain; kita tidak tahu siapa yang lebih menarik, Putri atau Rizky.

Jadi, keduanya adalah elemen maksimal. Kita tidak dapat menemukan orang yang lebih menarik daripada Rizky — Rizky lebih tampan daripada semua laki-laki lain, dan dengan perempuan ia tidak dapat dibandingkan. Begitu pula Putri — ia lebih cantik daripada semua perempuan, dan dengan laki-laki ia tidak dapat dibandingkan.

Namun, tidak satu pun dari keduanya yang terbesar, dalam arti paling menarik. Agar Rizky menjadi yang paling menarik/terbesar, ia harus lebih menarik daripada semua orang, termasuk semua perempuan. Padahal, seperti sudah dikatakan, ia tidak dapat dibandingkan dengan perempuan. Karena itu, ia tidak mungkin menjadi orang yang paling menarik; dalam istilah teori urutan, ia hanya maksimal.

Cukup mudah dilihat bahwa jika suatu himpunan memiliki elemen terbesar, elemen ini sekaligus maksimal. Jika elemen a lebih besar daripada semua elemen lain himpunan tersebut (definisi elemen terbesar), tentu kita tidak akan menemukan elemen yang lebih besar lagi (definisi elemen maksimal).

Contoh himpunan yang memiliki elemen terbesar dan terkecil adalah interval tertutup [0, 1]. Jika kita memilih interval yang sama, tetapi terbuka, interval ini tidak memiliki elemen terbesar maupun terkecil: (0, 1).

Jika kita menginginkan tak hingga banyaknya elemen minimal, kita bisa mendefinisikan urutan R sebagai berikut. Pertama, kita definisikan himpunan bantu M_x. Himpunan-himpunan ini berbentuk sebagai berikut: untuk semua x dari interval (0, 1) kita definisikan himpunan M_x = {y | y = x + n}, dengan n bilangan bulat nonnegatif. Dengan begitu kita memperoleh, misalnya, himpunan-himpunan berikut:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Pada setiap himpunan M_x kita definisikan urutan biasa, yang kita beri lambang R_x. Terakhir, kita gabungkan urutan-urutan ini: R = ∪ R_x. Dalam urutan ini, kita hanya dapat membandingkan elemen-elemen di dalam rantai semula. Kita dapat menentukan apakah 0,5 ≤ 2,5, tetapi tidak dapat menentukan apakah 0,5 ≤ 2,7, karena kedua bilangan ini tidak berada dalam himpunan M_x yang sama, sehingga hubungannya tidak terdefinisi.

Dalam relasi urutan ini, setiap elemen interval (0, 1) merupakan elemen minimal.

Diagram Hasse

Himpunan terurut dapat digambarkan dengan diagram Hasse. Diagram ini adalah graf yang simpulnya mewakili elemen-elemen himpunan, dan sisi antara simpul (a, b) menyatakan bahwa a < b dan tidak ada c yang memenuhi a < c < b. Artinya, di antara elemen a dan b tidak ada elemen lain. Selain itu, dalam graf simpul a harus terletak lebih rendah daripada simpul b. Contoh diagram Hasse:

Diagram Hasse ini menggambarkan himpunan terurut {A, B, C, D, E, F}. Di sini berlaku: A < B, B < E, dan tentu saja juga A < E, tetapi tidak ada sisi di antara kedua simpul ini, karena ada simpul B yang memenuhi A < B < E. Elemen E dan D tidak dapat dibandingkan, karena tidak ada yang berada di atas atau di bawah yang lain.

Meskipun diagram Hasse biasanya digambar serapi ini, hal itu tidak mutlak diperlukan. Diagram Hasse sebelumnya bisa juga terlihat seperti ini:

Contoh lain adalah himpunan: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Himpunan ini berisi faktor-faktor positif dari bilangan 60. Urutan menurut keterbagian dapat digambarkan seperti ini:

Urutan menurut keterbagian berarti (a, b) ∈ R jika dan hanya jika a habis membagi b. Dari diagram terlihat bahwa di atas setiap bilangan terdapat bilangan-bilangan yang habis dibaginya. Misalnya, di atas bilangan 6 terdapat bilangan 12, 30, dan 60. Di atas bilangan 4 terdapat bilangan 12, 20, dan 60. Dan seterusnya. Sebaliknya, bilangan 3 tidak memiliki bilangan 10 di atasnya, karena tidak habis membaginya — hati-hati, secara visual bilangan 10 memang terletak di atas bilangan 3, tetapi tidak ada garis “dari bawah ke atas” yang menuju ke sana. Jika dari bilangan 3 kita hanya bergerak ke atas, kita bisa menuju bilangan 15 dan 6, lalu dari keduanya ke bilangan 30. Bilangan 10 hanya bisa dicapai jika kita turun ke bawah, dan itu tidak boleh.