Urutan total

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 :

  (refleksif).
 Jika  dan  maka  (transitif)
 Jika  dan  maka  (antisimetris)
  atau  (terhubung, sebelumnya disebut total).

Jumlah tatanan terkadang disebut sederhana, koneks, atau tatanan penuh.

Satu himpunan yang dilengkapi dengan urutan total adalah himpunan berurutan total; istilah himpunan berurutan sederhana,  himpunan berurutan linear, dan loset dan penggunaannya. Istilah kaidah terkadang didefinisikan sebagai sinonim dari himpunan berurutan total, 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  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 :

  bukan merupakan irrefleksif.
 Jika  dan  maka  merupakan transitif.
 Jika , maka  atau  merupakan terhubung.

Untuk setiap urutan total (non-batasan)  berada dalam relasi terkait dengan  yang disebut urutan total batasan  untuk mendefinisikan dalam dua cara yang setara:
  jika  dan  (reduksi refleksif).
  jika bukan  (yaitu,  adalah komplemen dari konversi dari ).

Sebaliknya, penutupan refleksif dari urutan total ketat  adalah urutan total (non-batasan).

 Contoh 
 Himpunan bagian dari himpunan berurutan total  seluruhnya untuk pembatas urutan pada . 
 Urutan unik pada himpunan kosong , adalah urutan total.
 Setiap himpunan bilangan kardinal atau bilangan ordinal yang merupakan urutan rapi.
 Jika  adalah himpunan dan  sebuah fungsi injeksi dari  ke himpunan berurutan total maka  sebagai induksi pengurutan total pada  dengan menyetel  jika dan hanya jika .
 Tatanan leksikografis dengan produk Kartesius dari suatu grup himpunan tatanan total, indeks oleh himpunan terurut rapi yang merupakan tatanan total.  
 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  adalah inisial untuk sifat, jika, setiap  memiliki sifat, dan tatanan isomorfisme dari  ke himpunan bagian dari :Definisi ini mirip dengan objek awal dari kategori, tetapi nilai tersebut lemah.
 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,  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. Here: Chapter 14 Di hlm. 35 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  memiliki batas atas di , maka  berisi setidaknya satu elemen maksimal. Di hlm. 100 Lemma Zorn biasanya digunakan dengan  yang sebagai himpunan bagian; dalam hal ini, batas atas diperoleh dengan membuktikan bahwa penyatuan elemen kaidah di  yang terdapat pada . 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.Yiannis N. Moschovakis (2006) Notes on set theory, Undergraduate Texts in Mathematics (Birkhäuser) , p. 116

Himpunan berurutan sebagian memiliki kondisi kaidah turunan jika setiap kaidah turunan pada akhirnya stabil.artinya, di luar beberapa indeks, seluruh anggota urutan selanjutnya adalah sama 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 
  for all a, b.

Maka, kita menulis a ≤ b jika dan hanya jika . Oleh karena itu, himpunan tatanan total adalah kisi distributif.

 Urutan total hingga 
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).

 Teori kategori 
Himpunan 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 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 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:
 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.

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 urutan 
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.

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 terkait 
Relasi 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.

 Lihat pula 

 Gelanggang Artinian
 Teori order
 Urutan rapi
 Masalah Suslin
 Garis senegaranya
 Permutasi
 Urutan prefiks - urutan parsial total ke bawah

 Catatan 

 Referensi 



 George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co.  
 John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988.  



 Pranala luar 


Kategori:Relasi biner
Kategori:Teori order
Kategori:Teori himpunan