Simbol "✓" menunjukkan bahwa sifat kolom diperlukan dalam definisi baris. Misalnya, definisi relasi ekuivalen diperlukan menjadi simetris. Semua definisi secara diam-diam memerlukan ketransitifan dan refleksivitas.
Dalam matematika, sebuah total atau urutan (atau tatanan) linear adalah tatanan parsial di mana dua elemen dapat dibandingkan. Artinya, urutan total adalah relasi biner pada beberapa himpunan, yang memenuhi berikut ini untuk semua dan dalam :
Jumlah tatanan terkadang disebut sederhana,[1]koneks,[2] atau tatanan penuh.[3]
Satu himpunan yang dilengkapi dengan urutan total adalah himpunan berurutan total;[4] istilah himpunan berurutan sederhana, [1]himpunan berurutan linear,[2][4] dan loset[5][6] dan penggunaannya. Istilah kaidah terkadang didefinisikan sebagai sinonim dari himpunan berurutan total,[4] tetapi secara umum mengacu pada himpunan bagian berurutan total dari himpunan berurutan sebagian.
Perpanjangan urutan parsial tertentu ke urutan total disebut ekstensi linear dari urutan parsial tersebut.
Urutan total batasan dan non-batasan
Sebuah urutan total batasan pada himpunan adalah urutan parsial batasan di mana dua elemen dapat dibandingkan. Artinya, urutan total adalah relasi biner pada beberapa himpunan, yang memenuhi berikut ini untuk semua dan dalam :
Untuk setiap urutan total (non-batasan) berada dalam relasi terkait dengan yang disebut urutan total batasan untuk mendefinisikan dalam dua cara yang setara:
Jika X adalah himpunan dan f sebuah fungsi injeksi dari X ke himpunan berurutan total maka f sebagai induksi pengurutan total pada X dengan menyetel x1 ≤ x2 jika dan hanya jika f(x1) ≤ f(x2).
Himpunan bilangan riil yang diurutkan oleh hubungan biasa "kurang dari atau sama dengan" (≤) atau "lebih besar dari atau sama dengan" (≥) diurutkan total, dan karenanya himpunan bagian dari bilangan asli, bilangan bulat, dan bilangan rasional. Masing-masing dapat ditampilkan sebagai "contoh awal" unik sebagai tatanan isomorfisma hingga dari himpunan tatanan total dengan sifat tertentu, tatanan total A adalah inisial untuk sifat, jika, setiap B memiliki sifat, dan tatanan isomorfisme dari A ke himpunan bagian dari B:[7][butuh rujukan]
Bilangan asli sebagai bentuk himpunan terurut total tidak kosong awal tanpa batas atas.
Bilangan bulat sebagai bentuk himpunan terurut total tidak kosong awal tanpa batas atas atau pun batas bawah.
Bilangan rasional sebagai bentuk himpunan terurut total awal yang padat dalam bilangan riil. Selain itu, pengurangan refleksif < adalah urutan padat pada bilangan rasional.
Bilangan riil sebagai bentuk himpunan terurut total tak hingga awal yang terhubung di topologi urutan (didefinisikan di bawah).
Medan tatanan diurutkan seluruhnya menurut definisi. Hal tersebut termasuk bilangan rasional dan bilangan riil. Setiap medan tatanan dengan submedan tatanan isomorfik ke bilangan rasional. Setiap kelengkapan Dedekind yang merupakan medan isomorfik ke bilangan riil.
Huruf-huruf alfabet diurutkan menurut standar tatanan kamus, misalnya, A < B < C dll, adalah tatanan total ketat.
Kaidah
Istilah kaidah terkadang didefinisikan sebagai sinonim untuk himpunan tatanan total, namun umumnya digunakan untuk merujuk ke himpunan bagian dari himpunan terurut sebagian tatanan total untuk urutan induksi.[8][9] Biasanya, himpunan parsial diurutkan sebagian adalah himpunan bagian dari himpunan tertentu yang diurutkan dengan penyertaan, dan istilah tersebut digunakan untuk menyatakan sifat dari rangkaian kaidah. Jumlah himpunan bertingkat yang tinggi ini menjelaskan kegunaan istilah tersebut.
Contoh umum penggunaan kaidah untuk merujuk pada himpunan berurutan bagian yang seluruhnya adalah lemma Zorn, jika setiap kaidah dalam rangkaian yang diurutkan sebagian X memiliki batas atas di X, maka X berisi setidaknya satu elemen maksimal.[10] Lemma Zorn biasanya digunakan dengan X yang sebagai himpunan bagian; dalam hal ini, batas atas diperoleh dengan membuktikan bahwa penyatuan elemen kaidah di X yang terdapat pada X. Cara inilah yang umumnya digunakan untuk membuktikan bahwa ruang vektor memiliki basis Hamel dan bahwa gelanggang memiliki ideal maksimal.
Dalam beberapa konteks, kaidah yang dianggap sebagai urutan isomorfik ke bilangan asli dengan urutan biasa atau urutan konversi. Dalam hal ini, kaidah dapat diidentifikasi dengan urutan monoton, dan disebut kaidah tingkatan atau kaidah turunan, tergantung apakah urutannya meningkat atau menurun.[11]
Himpunan berurutan sebagian memiliki kondisi kaidah turunan jika setiap kaidah turunan pada akhirnya stabil.[12] Misalnya, tatanan adalah didirikan jika bersyarat kaidah turunan. Demikian pula, kondisi kaidah tingkatan berarti bahwa setiap kaidah tingkatan pada akhirnya menjadi stabil. Misalnya, gelanggang Noetherian adalah gelanggang ideal yang memenuhi kondisi kaidah tingkatan.
"Kaidah" juga dapat digunakan untuk beberapa himpunan berurutan total dari struktur yang bukan merupakan himpunan berurutan sebagian. Sebuah contoh diberikan oleh kaidah reguler dari polinomial. Contoh lain adalah penggunaan "kaidah" sebagai sinonim untuk berjalan dalam grafik.
Konsep lebih lanjut
Teori kisi
Kita dapat mendefinisikan himpunan terurut total sebagai jenis tertentu dari kekisi, yaitu
Argumen pencacahan sederhana akan memverifikasi bahwa setiap himpunan terurut total hingga tidak kosong, dan karenanya setiap Himpunan bagian tidak kosong yang memiliki elemen terkecil. Jadi, setiap urutan total hingga adalah urutan rapi. Baik dengan pembuktian langsung atau dengan mengamati bahwa setiap urutan sumur urutan isomorfik ke ordinal satu mungkin menunjukkan bahwa setiap total order hingga urutan isomorfik ke segmen awal dari bilangan asli yang diurutkan oleh <. Dengan kata lain, urutan total pada himpunan dengan elemen k menginduksi bijeksi dengan bilangan asli pertama k. Oleh karena itu, adalah umum untuk mengindeks pesanan total hingga atau pesanan sumur dengan jenis pesanan ω dengan bilangan asli dengan cara yang sesuai dengan urutan (baik dimulai dengan nol atau dengan satu).
Sebuah petabijektif antara dua himpunan terurut total dengan dua urutan tersebut adalah sebuah isomorfisme dalam kategori ini.
Urutan topologi
Untuk setiap himpunan terurut total X kita dapat mendefinisikan interval terbuka (a, b) = {x: a < x dan x < b}, (−∞, b) = {x: x < b}, (a, ∞) = {x: a < x} and (−∞, ∞) = X. Kita bisa menggunakan interval terbuka ini untuk mendefinisikan topologi pada himpunan terurut yaitu topologi urutan.
Ketika lebih dari satu urutan digunakan pada satu himpunan, maka satu akan berbicara tentang urutan topologi induksi oleh urutan tertentu. Misalnya jika N adalah bilangan asli, < lebih kecil dari dan > lebih besar dari yang mungkin kita lihat pada topologi urutan pada N induksi oleh < dan topologi urutan pada N induksi oleh >, dalam hal ini keduanya identik tetapi tidak secara umum.
Induksi topologi urutan oleh urutan total dapat ditampilkan secara turun-temurun normal.
Kelengkapan
Sebuah himpunan berurutan total dikatakan kelengkapan jika setiap himpunan bagian tidak kosong yang memiliki batas atas, dan batas atas terkecil. Misalnya, himpunan bilangan riilR sebagai kelengkapan, tetapi himpunan bilangan rasionalQ bukan kelengkapan. Dengan kata lain, berbagai konsep kelengkapan (jangan disamakan dengan "total") tidak terbawa pada pembatas. Misalnya, di atas bilangan riil, sifat dari relasi adalah bahwa setiap himpunan bagian tidak kosongS dari R dengan batas atas dalam R memiliki batas atas terkecil (juga disebut supremum) di R. Namun, untuk bilangan rasional supremum ini belum tentu rasional, sehingga sifat yang sama tidak berpegang pada restriksi relasi ≤ dengan bilangan rasional.
Ada sejumlah hasil yang mengaitkan sifat topologi urutan dengan kelengkapan X:
Jika topologi urutan terhubung pada X, maka X adalah kelengkapan.
X yang terhubung di bawah topologi urutan jika dan hanya jika kelengkapan dan tidak ada celah dalam X. Kesenjangannya adalah dua titik a dan b di X dengan a < b sehingga tidak ada c yang memenuhi a < c < b.)
X adalah kelengkapan jika dan hanya jika setiap himpunan berbatas yang ditutup dalam topologi urutan kompak.
Untuk dua urutan total disjoin dan , terdapat urutan alami dalam himpunan , yang disebut jumlah dari dua tatanan atau terkadang hanya :
Untuk , memegang jika dan hanya jika salah satu dari yang berikut ini membekukan:
dan
dan
dan
Secara intuitif, ini berarti bahwa elemen dari himpunan kedua ditambahkan di atas elemen dari himpunan pertama.
Secara umum, jika adalah satu himpunan indeks berurutan total, dan untuk setiap struktur adalah urutan linear, di mana himpunan adalah perpisahan pasangan, maka total urutan alami pada didefinisikan oleh
Untuk , memegang jika:
Beberapa dengan
atau beberapa in dengan ,
Urutan pada produk Kartesius dari himpunan berurutan total
Untuk meningkatkan kekuatan, yaitu, mengurangi penggunaan himpunan pasangan, tiga dari kemungkinan urutan pada produk Kartesius dari dua himpunan berurutan total adalah:
Urutan leksikografis: (a,b) ≤ (c,d) jika dan hanya jika a < c atau (a = c dan b ≤ d). Ini merupakan urutan total.
(a,b) ≤ (c,d) jika dan hanya jika a ≤ c dan b ≤ d (pesanan produk). Ini merupakan urutan parsial.
(a,b) ≤ (c,d) jika dan hanya jika (a < c dan b < d) or (a = c dan b = d) dari penutupan refleksif dari produk langsung dari total pesanan yang sesuai. Ini juga merupakan urutan parsial.
Ketiganya dapat didefinisikan secara serupa untuk produk Kartesius lebih dari dua himpunan.
Hanya ada beberapa struktur nontrivial yang dapat didefinisikan sebagai reduksi dari suatu tatanan total. Melupakan hasil orientasi dalam relasi keantaraan. Melupakan lokasi hasil akhir dalam urutan siklik. Melupakan kedua hasil data dalam relasi pemisahan.[13]
↑Brian A. Davey and Hilary Ann Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN0-521-36766-2. LCCN89009753. Di hlm. 100
