Urutan total
Dalam matematika, sebuah total atau urutan (atau tatanan) linear adalah tatanan parsial dimana 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-batasanSebuah urutan total batasan pada himpunan adalah urutan parsial batasan dimana 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:
Sebaliknya, penutupan refleksif dari urutan total ketat adalah urutan total (non-batasan). Contoh
KaidahIstilah 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 lanjutTeori kisiKita dapat mendefinisikan himpunan terurut total sebagai jenis tertentu dari kekisi, yaitu
Maka, kita menulis a ≤ b jika dan hanya jika . Oleh karena itu, himpunan tatanan total adalah kisi distributif. Urutan total hinggaArgumen 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). Teori kategoriHimpunan berurutan total membentuk subkategori lengkap dari kategori dari himpunan berurutan sebagian, dengan morfisme adalah peta dengan dukungan, yaitu memetakan f sehingga jika a ≤ b maka f(a) ≤ f(b). Sebuah peta bijektif antara dua himpunan terurut total dengan dua urutan tersebut adalah sebuah isomorfisme dalam kategori ini. Urutan topologiUntuk 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. KelengkapanSebuah himpunan berurutan total dikatakan kelengkapan jika setiap himpunan bagian tidak kosong yang memiliki batas atas, dan batas atas terkecil. Misalnya, himpunan bilangan riil R sebagai kelengkapan, tetapi himpunan bilangan rasional Q 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 kosong S 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:
Satu himpunan berurutan total dengan topologi urutan yang merupakan kisi lengkap adalah kompak. Contohnya adalah interval tertutup dari bilangan riil, misal interval unit [0,1], dan ekstensi garis bilangan riil. Ada homeomorfisme yang merupakan kelengkapan di antara contoh-contoh ini. Jumlah urutanUntuk dua urutan total disjoin dan , terdapat urutan alami dalam himpunan , yang disebut jumlah dari dua tatanan atau terkadang hanya :
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, dimana himpunan adalah perpisahan pasangan, maka total urutan alami pada didefinisikan oleh
Urutan pada produk Kartesius dari himpunan berurutan totalUntuk meningkatkan kekuatan, yaitu, mengurangi penggunaan himpunan pasangan, tiga dari kemungkinan urutan pada produk Kartesius dari dua himpunan berurutan total adalah:
Ketiganya dapat didefinisikan secara serupa untuk produk Kartesius lebih dari dua himpunan. Diterapkan ke ruang vektor Rn, masing-masing yang menjadi sebagai ruang vektor terurut. Lihat pula contoh himpunan berurutan sebagian. Fungsi riil dari variabel riil n yang ditentukan pada subset dari Rn mendefinisikan urutan batas lemah dan praorder total pada himpunan bagian tersebut. Struktur terkaitRelasi biner antisimetris, transitif, dan refleksif namun tidak total adalah urutan parsial. Sebuah grup dengan urutan total kompatibel adalah grup terurut total. 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] Lihat pula
Catatan
Referensi
Pranala luar
|