Urutan total

Dalammatematika, sebuahtotalatauurutan(atautatanan)linearadalahtatanan parsialdimana dua elemen dapat dibandingkan. Artinya, urutan total adalahrelasi biner≤{\displaystyle \leq }pada beberapahimpunanX{\displaystyle X}, yang memenuhi berikut ini untuk semuaa,b{\displaystyle a,b}danc{\displaystyle c}dalamX{\displaystyle X}:
Jumlah tatanan terkadang disebutsederhana,koneks,atautatanan penuh.
Satu himpunan yang dilengkapi dengan urutan total adalahhimpunan berurutan total;istilahhimpunan berurutan sederhana,himpunan berurutan linear,danlosetdan penggunaannya. Istilahkaidahterkadang didefinisikan sebagai sinonim darihimpunan berurutan total,tetapi secara umum mengacu pada himpunan bagian berurutan total dari himpunan berurutan sebagian.
Perpanjangan urutan parsial tertentu ke urutan total disebutekstensi lineardari urutan parsial tersebut.
Sebuahurutan total batasanpada himpunanX{\displaystyle X}adalahurutan parsial batasanX{\displaystyle X}dimana dua elemen dapat dibandingkan. Artinya, urutan total adalahrelasi biner<{\displaystyle <}pada beberapahimpunanX{\displaystyle X}, yang memenuhi berikut ini untuk semuaa,b{\displaystyle a,b}danc{\displaystyle c}dalamX{\displaystyle X}:
Untuk setiap urutan total (non-batasan)≤{\displaystyle \leq }berada dalam relasi terkait dengan<{\displaystyle <}yang disebuturutan total batasan≤{\displaystyle \leq }untuk mendefinisikan dalam dua cara yang setara:
Sebaliknya,penutupan refleksifdari urutan total ketat<{\displaystyle <}adalah urutan total (non-batasan).
Istilahkaidahterkadang didefinisikan sebagai sinonim untuk himpunan tatanan total, namun umumnya digunakan untuk merujuk kehimpunan bagiandarihimpunan terurut sebagiantatanan total untuk urutan induksi.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 penggunaankaidahuntuk merujuk pada himpunan berurutan bagian yang seluruhnya adalahlemma Zorn, jika setiap kaidah dalam rangkaian yang diurutkan sebagianXmemiliki batas atas diX, makaXberisi setidaknya satu elemen maksimal.Lemma Zorn biasanya digunakan denganXyang sebagai himpunan bagian; dalam hal ini, batas atas diperoleh dengan membuktikan bahwa penyatuan elemen kaidah diXyang terdapat padaX. Cara inilah yang umumnya digunakan untuk membuktikan bahwaruang vektormemilikibasis Hameldan bahwagelanggangmemilikiideal maksimal.
Dalam beberapa konteks, kaidah yang dianggap sebagai urutan isomorfik ke bilangan asli dengan urutan biasa atauurutan konversi. Dalam hal ini, kaidah dapat diidentifikasi denganurutan monoton, dan disebutkaidah tingkatanataukaidah turunan, tergantung apakah urutannya meningkat atau menurun.
Himpunan berurutan sebagian memilikikondisi kaidah turunanjika setiap kaidah turunan pada akhirnya stabil.Misalnya, tatanan adalahdidirikanjika bersyarat kaidah turunan. Demikian pula,kondisi kaidah tingkatanberarti bahwa setiap kaidah tingkatan pada akhirnya menjadi stabil. Misalnya,gelanggang Noetherianadalah gelanggangidealyang memenuhi kondisi kaidah tingkatan.
"Kaidah" juga dapat digunakan untuk beberapa himpunan berurutan total daristrukturyang bukan merupakan himpunan berurutan sebagian. Sebuah contoh diberikan olehkaidah regulerdari polinomial. Contoh lain adalah penggunaan "kaidah" sebagai sinonim untukberjalandalamgrafik.
Kita dapat mendefinisikan himpunan terurut total sebagai jenis tertentu darikekisi, yaitu
Maka, kita menulisa≤bjika dan hanya jikaa=a∧b{\displaystyle a=a\wedge b}. Oleh karena itu, himpunan tatanan total adalahkisi distributif.
Argumenpencacahansederhana 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 adalahurutan rapi. Baik dengan pembuktian langsung atau dengan mengamati bahwa setiap urutan sumururutan isomorfikkeordinalsatu mungkin menunjukkan bahwa setiap total order hinggaurutan isomorfikkesegmen awaldari bilangan asli yang diurutkan oleh <. Dengan kata lain, urutan total pada himpunan dengan elemenkmenginduksi bijeksi dengan bilangan asli pertamak. Oleh karena itu, adalah umum untuk mengindeks pesanan total hingga atau pesanan sumur denganjenis pesananω dengan bilangan asli dengan cara yang sesuai dengan urutan (baik dimulai dengan nol atau dengan satu).
Himpunan berurutan total membentuksubkategori lengkapdarikategoridarihimpunan berurutan sebagian, denganmorfismeadalah peta dengan dukungan, yaitu memetakanfsehingga jikaa≤bmakaf(a) ≤f(b).
Sebuahpetabijektifantara dua himpunan terurut total dengan dua urutan tersebut adalah sebuahisomorfismedalam kategori ini.
Untuk setiap himpunan terurut totalXkita dapat mendefinisikaninterval terbuka(a,b) = {x:a<xdanx<b}, (−∞,b) = {x:x<b}, (a, ∞) = {x:a<x} and (−∞, ∞) =X. Kita bisa menggunakan interval terbuka ini untuk mendefinisikantopologipada himpunan terurut yaitutopologi urutan.
Ketika lebih dari satu urutan digunakan pada satu himpunan, maka satu akan berbicara tentang urutan topologi induksi oleh urutan tertentu. Misalnya jikaNadalah bilangan asli, < lebih kecil dari dan > lebih besar dari yang mungkin kita lihat pada topologi urutan padaNinduksi oleh < dan topologi urutan padaNinduksi oleh >, dalam hal ini keduanya identik tetapi tidak secara umum.
Induksi topologi urutan oleh urutan total dapat ditampilkan secara turun-temurunnormal.
Sebuah himpunan berurutan total dikatakankelengkapanjika setiap himpunan bagian tidak kosong yang memilikibatas atas, danbatas atas terkecil. Misalnya, himpunanbilangan riilRsebagai kelengkapan, tetapi himpunanbilangan rasionalQbukan kelengkapan. Dengan kata lain, berbagai konsepkelengkapan(jangan disamakan dengan "total") tidak terbawa padapembatas. Misalnya, di atasbilangan riil, sifat dari relasi adalah bahwa setiap himpunan bagiantidak kosongSdariRdenganbatas atasdalamRmemilikibatas atas terkecil(juga disebut supremum) diR. 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 merupakankisi lengkapadalahkompak. Contohnya adalah interval tertutup dari bilangan riil, misalinterval unit[0,1], danekstensi garis bilangan riil. Adahomeomorfismeyang merupakan kelengkapan di antara contoh-contoh ini.
Untuk dua urutan total disjoin(A1,≤1){\displaystyle (A_{1},\leq _{1})}dan(A2,≤2){\displaystyle (A_{2},\leq _{2})}, terdapat urutan alami≤+{\displaystyle \leq _{+}}dalam himpunanA1∪A2{\displaystyle A_{1}\cup A_{2}}, yang disebut jumlah dari dua tatanan atau terkadang hanyaA1+A2{\displaystyle A_{1}+A_{2}}:
Secara intuitif, ini berarti bahwa elemen dari himpunan kedua ditambahkan di atas elemen dari himpunan pertama.
Secara umum, jika(I,≤){\displaystyle (I,\leq )}adalah satu himpunan indeks berurutan total, dan untuk setiapi∈I{\displaystyle i\in I}struktur(Ai,≤i){\displaystyle (A_{i},\leq _{i})}adalah urutan linear, dimana himpunanAi{\displaystyle A_{i}}adalah perpisahan pasangan, maka total urutan alami pada⋃iAi{\displaystyle \bigcup _{i}A_{i}}didefinisikan oleh
Untuk meningkatkan kekuatan, yaitu, mengurangi penggunaan himpunan pasangan, tiga dari kemungkinan urutan padaproduk Kartesiusdari dua himpunan berurutan total adalah:
Ketiganya dapat didefinisikan secara serupa untuk produk Kartesius lebih dari dua himpunan.
Diterapkan keruang vektorR, masing-masing yang menjadi sebagairuang vektor terurut.
Lihat pulacontoh himpunan berurutan sebagian.
Fungsi riil dari variabel riilnyang ditentukan pada subset dariRmendefinisikan urutan batas lemah dan praorder totalpada himpunan bagian tersebut.
Relasi biner antisimetris, transitif, dan refleksif namun tidak total adalahurutan parsial.
Sebuahgrupdengan urutan total kompatibel adalahgrup terurut total.
Hanya ada beberapa struktur nontrivial yang dapat didefinisikan sebagai reduksi dari suatu tatanan total. Melupakan hasil orientasi dalamrelasi keantaraan. Melupakan lokasi hasil akhir dalamurutan siklik. Melupakan kedua hasil data dalamrelasi pemisahan.