Hubungan tertib

Hubungan tertib ialah hubungan binari pada set yang refleksif, antisimetri dan transitif.

Motivasi

Tertib ialah konsep biasa yang kita gunakan juga dalam kehidupan seharian. Banyak perkara boleh disusun mengikut tertib tertentu — perkataan mengikut abjad, murid di sekolah mengikut ketinggian, barangan mengikut harga. Semua ini dihuraikan oleh hubungan tertib, yang biasanya ditandakan dengan simbol ≤. Simbol yang berkaitan ialah <, >, ≥. Maknanya jelas.

Apakah yang kita harapkan daripada hubungan seperti ini? Daripada simbolnya sahaja sudah jelas bahawa unsur yang sama juga berada dalam hubungan tertib — jadi kita ingin mentakrifkan sifat hubungan “kurang daripada atau sama dengan”. Oleh itu, hubungan ini sepatutnya refleksif. Mesti berlaku a ≤ a.

Apa lagi? Sifat simetri tentu tidak berlaku — jika kita menyusun mengikut harga dan sebuah kereta lebih murah daripada sebuku roti, tentu roti itu tidak lebih murah daripada kereta itu. Secara umum, apakah yang kita harapkan jika berlaku a ≤ b dan b ≤ a? Adakah keadaan ini pernah bermakna? Ya, jika a = b. Satu-satunya keadaan apabila tertib unsur dalam hubungan tidak penting ialah apabila unsur itu sama — jadi hubungan tertib bersifat antisimetri.

Akhir sekali, jika kita tahu bahawa kereta lebih mahal daripada roti dan kapal terbang lebih mahal lagi daripada kereta, kita mengharapkan bahawa kapal terbang tentu lebih mahal daripada roti. Inilah sifat transitif.

Tertib separa

Apa yang baru kita takrifkan sebenarnya hanyalah tertib separa, bukan tertib total. Mengapa bukan tertib total? Mari kita cuba mentakrifkan tertib pada set. Bagaimanakah kita boleh membandingkan dua set?

Kita katakan bahawa set A kurang daripada atau sama dengan set B jika A ⊆ B, iaitu jika A ialah subset bagi B. Hal ini bermakna, kerana jika A = {1, 2} dan B = {1, 2, 3}, kita boleh mengatakan bahawa A lebih kecil — B mengandungi semua unsur A dan juga nombor tiga. Jadi, contohnya:

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

Masalahnya timbul apabila kita ingin membandingkan set berikut: A = {a, b} dan B = {a, c}. Set manakah yang lebih kecil dan set manakah yang lebih besar? Kedua-dua set mengandungi unsur a, tetapi unsur keduanya berbeza. Tiada set yang merupakan subset bagi set yang lain, jadi A ≤ B tidak benar dan B ≤ A juga tidak benar. Dengan tertib kita, set seperti ini tidak dapat dibandingkan.

Oleh itu, kita takrifkan set tertib total, atau juga rantai, sebagai set yang setiap dua unsurnya dapat dibandingkan. Contoh set seperti ini ialah set nombor dengan tertib biasa. Bagi setiap dua nombor nyata a, b, anda dapat menentukan sama ada a ≤ b atau b ≤ a.

Contoh daripada kehidupan seharian

Satu contoh perkara yang lebih baik tidak dibandingkan ialah tertib mengikut kecantikan, dengan hubungan < bermaksud “kurang cantik”. Mungkin kita patut mentakrifkannya secara terbalik, iaitu > bermaksud “lebih cantik”, supaya lebih sopan :-). Mungkin masuk akal untuk membandingkan dua orang wanita dalam sebuah cerita rekaan, contohnya “Mawar” < “Melati” dalam erti kata Melati lebih cantik daripada Mawar. Atau dua orang lelaki: “Adam” < “Iskandar” dalam erti kata Iskandar lebih kacak daripada Adam.

Masalahnya, kecantikan seorang lelaki dan seorang wanita sukar dibandingkan. Siapakah yang lebih cantik, Melati atau Iskandar? Siapakah yang kurang cantik, Mawar atau Adam? Lebih baik tidak diselidiki…

Jika dalam contoh terakhir ini kita hanya mengambil wanita, kita boleh mengatakan bahawa kita mempunyai set tertib total, kerana kita dapat membandingkan kecantikan semua wanita.

Unsur minimum dan maksimum, unsur terkecil dan terbesar

Jika kita mempunyai set bertertib M, unsur min ∈ M dipanggil minimum jika tidak wujud x ∈ M dengan keadaan x < min. Jadi, kita tidak dapat mencari unsur yang lebih kecil daripada unsur min.

Unsur max ∈ M dipanggil maksimum jika tidak wujud x ∈ M dengan keadaan x > max. Jadi, kita tidak dapat mencari unsur yang lebih besar.

Dua konsep ini berbeza daripada konsep unsur terkecil dan unsur terbesar.

Unsur a ∈ M dipanggil terkecil jika bagi semua x ∈ M berlaku a ≤ x. Jadi, unsur terkecil a kurang daripada atau sama dengan semua unsur lain dalam set M.

Unsur b ∈ M dipanggil terbesar jika bagi semua x ∈ M berlaku b ≥ x. Unsur terbesar b lebih besar daripada atau sama dengan semua unsur lain dalam set M.

Apakah beza antara unsur terbesar dengan unsur maksimum? Unsur maksimum boleh ada lebih daripada satu, kerana set itu tidak semestinya bertertib total. Jika kita kembali kepada contoh membandingkan orang berdasarkan rupa, kita boleh mengatakan bahawa Melati ialah wanita paling cantik dan Iskandar ialah lelaki paling kacak. Akan tetapi, kedua-dua orang ini tidak dapat kita bandingkan antara satu sama lain; kita tidak tahu sama ada Melati atau Iskandar yang lebih cantik.

Oleh itu, kedua-dua unsur ini maksimum. Kita tidak dapat mencari orang yang lebih kacak daripada Iskandar — Iskandar lebih kacak daripada semua lelaki lain, dan dia tidak boleh dibandingkan dengan wanita. Begitu juga dengan Melati — dia lebih cantik daripada semua wanita lain, dan dia tidak boleh dibandingkan dengan lelaki.

Namun, tiada seorang pun daripada mereka yang terbesar, iaitu paling cantik dalam erti kata ini. Untuk menjadi yang paling cantik atau terbesar, Iskandar mesti lebih cantik daripada semua orang, termasuk semua wanita. Tetapi kita sudah mengatakan bahawa dia tidak boleh dibandingkan dengan wanita. Oleh itu, dia tidak boleh menjadi orang yang paling cantik; dalam istilah teori tertib, dia hanya maksimum.

Mudah dilihat bahawa jika suatu set mempunyai unsur terbesar, unsur itu juga maksimum. Jika unsur a lebih besar daripada semua unsur lain dalam set (takrif unsur terbesar), tentu kita tidak dapat mencari unsur yang lebih besar lagi (takrif unsur maksimum).

Contoh set yang mempunyai unsur terbesar dan unsur terkecil ialah selang tertutup [0, 1]. Jika kita memilih selang yang sama tetapi terbuka, selang itu tidak mempunyai unsur terbesar mahupun unsur terkecil: (0, 1).

Jika kita mahukan unsur minimum yang tak terhingga banyaknya, kita boleh mentakrifkan tertib R seperti berikut. Mula-mula kita takrifkan set bantu M_x. Set ini berbentuk seperti berikut: bagi semua x dalam selang (0, 1), kita takrifkan set M_x = {y | y = x + n}, dengan n integer bukan negatif. Dengan itu, kita memperoleh set seperti 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 set M_x, kita takrifkan tertib biasa, yang kita tandakan dengan R_x. Akhir sekali, kita gabungkan semua tertib ini dengan kesatuan: R = ∪ R_x. Dalam tertib ini, kita hanya boleh membandingkan unsur dalam rantai asal yang sama. Kita boleh menentukan sama ada 0.5 ≤ 2.5, tetapi kita tidak dapat menentukan sama ada 0.5 ≤ 2.7, kerana kedua-dua nombor ini tidak terletak dalam set M_x yang sama, jadi hubungan antara kedua-duanya tidak ditakrifkan.

Dalam hubungan tertib ini, setiap unsur dalam selang (0, 1) ialah unsur minimum.

Gambar rajah Hasse

Set bertertib boleh dilukis dengan gambar rajah Hasse. Gambar rajah ini ialah graf yang bucunya mewakili unsur set, dan tepi antara bucu (a, b) menyatakan bahawa a < b dan tidak wujud c dengan keadaan a < c < b. Jadi, tiada unsur lain di antara unsur a dengan unsur b. Selain itu, bucu a mesti terletak lebih rendah daripada bucu b dalam graf. Contoh gambar rajah Hasse:

Gambar rajah Hasse ini mewakili set bertertib {A, B, C, D, E, F}. Dalam set ini, A < B dan B < E; tentu sahaja A < E juga, tetapi tiada tepi antara kedua-dua bucu ini kerana wujud bucu B yang memenuhi A < B < E. Unsur E dan D tidak dapat dibandingkan kerana kedua-duanya tidak terletak di atas atau di bawah satu sama lain.

Walaupun gambar rajah Hasse biasanya dilukis dengan kemas seperti ini, hal itu tidak wajib. Gambar rajah Hasse tadi boleh juga kelihatan seperti ini:

Contoh lain ialah set A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Set ini terdiri daripada faktor positif bagi nombor 60. Tertib mengikut kebolehbahagian boleh digambarkan seperti berikut:

Tertib mengikut kebolehbahagian bermaksud (a, b) ∈ R jika dan hanya jika a membahagi b. Daripada gambar rajah, kita dapat melihat bahawa di atas setiap nombor terdapat nombor yang boleh dibahagi tepat dengannya. Contohnya, di atas nombor 6 terdapat nombor 12, 30 dan 60. Di atas nombor 4 terdapat nombor 12, 20 dan 60. Dan seterusnya. Sebaliknya, nombor 10 tidak berada di atas nombor 3 kerana 3 tidak membahagi 10 — awas, nombor 10 kelihatan berada di atas nombor 3 dalam gambar, tetapi tiada garis yang menghubungkan kedua-duanya “dari bawah ke atas”. Jika kita bergerak dari nombor 3 ke atas sahaja, kita boleh pergi ke nombor 15 dan 6, dan dari situ ke nombor 30. Kita hanya dapat sampai ke nombor 10 jika kita turun ke bawah, dan hal itu tidak dibenarkan.