Urutan total

Relasi biner

	Simetrik	Antisimetrik	Connex	Ditemukan baik	Telah bersambung	Telah bertemu
Relasi ekuivalen	✓	✗	✗	✗	✗	✗
Praurutan (Kuasiorder)	✗	✗	✗	✗	✗	✗
Urutan parsial	✗	✓	✗	✗	✗	✗
Praurutan total	✗	✗	✓	✗	✗	✗
Urutan total	✗	✓	✓	✗	✗	✗
Pra-urutan rapi	✗	✗	✓	✓	✗	✗
Kuasi urutan rapi	✗	✗	✗	✓	✗	✗
Urutan rapi	✗	✓	✓	✓	✗	✗
Kisi	✗	✓	✗	✗	✓	✓
Sambungan-semikekisi	✗	✓	✗	✗	✓	✗
Pertemuan-semikekisi	✗	✓	✗	✗	✗	✓

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 dimana dua elemen dapat dibandingkan. Artinya, urutan total adalah relasi biner $\leq$ pada beberapa himpunan $X$ , yang memenuhi berikut ini untuk semua $a,b$ dan $c$ dalam $X$ :

$a\leq a$ (refleksif).
Jika $a\leq b$ dan $b\leq c$ maka $a\leq c$ (transitif)
Jika $a\leq b$ dan $b\leq a$ maka $a=b$ (antisimetris)
$a\leq b$ atau $b\leq a$ (terhubung, sebelumnya disebut total).

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 $X$ adalah urutan parsial batasan $X$ dimana dua elemen dapat dibandingkan. Artinya, urutan total adalah relasi biner $<$ pada beberapa himpunan $X$ , yang memenuhi berikut ini untuk semua $a,b$ dan $c$ dalam $X$ :

Bukan $a<a$ (tidak refleksif).
Jika $a<b$ dan $b<c$ maka $a<c$ (transitif).
Jika $a\neq b$ , maka $a<b$ atau $b<a$ (terhubung).

Untuk setiap total pesanan (non-batasan) $\leq$ berada relasi yang terkait $<$ , disebut urutan total batasan $\leq$ yang mendefinisikan dalam dua cara yang setara:

$a<b$ jika $a\leq b$ dan $a\neq b$ (reduksi refleksif).
$a<b$ jika bukan $b\leq a$ (yaitu, $<$ adalah komplemen dari konversi dari $\leq$ ).

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

Contoh

Himpunan bagian dari himpunan berurutan total $X$ seluruhnya untuk pembatas urutan pada $X$ .
Urutan unik pada himpunan kosong $\emptyset$ , adalah urutan total.
Setiap himpunan bilangan kardinal atau bilangan ordinal yang merupakan urutan rapi.
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 $x 1 \leq x 2$ jika dan hanya jika $f (x 1) \leq f (x 2)$ .
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 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

\{a\vee b,a\wedge b\}=\{a,b\}

for all a, b.

Maka, kita menulis a ≤ b jika dan hanya jika $a=a\wedge b$ . 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, namun 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 $(A_{1},\leq _{1})$ dan $(A_{2},\leq _{2})$ , terdapat urutan alami $\leq _{+}$ dalam himpunan $A_{1}\cup A_{2}$ , yang disebut jumlah dari dua tatanan atau terkadang hanya $A_{1}+A_{2}$ :

Untuk

x,y\in A_{1}\cup A_{2}

,

x\leq _{+}y

memegang jika dan hanya jika salah satu dari yang berikut ini membekukan:

$x,y\in A_{1}$ dan $x\leq _{1}y$
$x,y\in A_{2}$ dan $x\leq _{2}y$
$x\in A_{1}$ dan $y\in A_{2}$

Secara intuitif, ini berarti bahwa elemen dari himpunan kedua ditambahkan di atas elemen dari himpunan pertama.

Secara umum, jika $(I,\leq )$ adalah satu himpunan indeks berurutan total, dan untuk setiap $i\in I$ struktur $(A_{i},\leq _{i})$ adalah urutan linear, dimana himpunan $A_{i}$ adalah perpisahan pasangan, maka total urutan alami pada $\bigcup _{i}A_{i}$ didefinisikan oleh

Untuk

x,y\in \bigcup _{i\in I}A_{i}

,

x\leq y

memegang jika:

Beberapa $i\in I$ dengan $x\leq _{i}y$
atau beberapa $i<j$ in $I$ dengan $x\in A_{i}$ , $y\in A_{j}$

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 Rⁿ, 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 Rⁿ 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.^[13]

Lihat pula

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

Catatan

^ ^a ^b Birkhoff 1967, hlm. 2.
^ ^a ^b Schmidt & Ströhlein 1993, hlm. 32.
^ Fuchs 1963, hlm. 2.
^ ^a ^b ^c Davey & Priestley 1990, hlm. 3.
^ Strohmeier, Alfred; Genillard, Christian; Weber, Mats (1990-08-01). "Ordering of characters and strings". ACM SIGAda Ada Letters (dalam bahasa Inggris) (7): 84. doi:10.1145/101120.101136.
^ Ganapathy, Jayanthi (1992). "Maximal Elements and Upper Bounds in Posets". Pi Mu Epsilon Journal. 9 (7): 462–464. ISSN 0031-952X. JSTOR 24340068.
^ Definisi ini mirip dengan objek awal dari kategori, namun nilai tersebut lemah.
^ Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. Here: Chapter 14
^ Roland Fraïssé (Dec 2000). Theory of Relations. Studies in Logic and the Foundations of Mathematics. 145 (edisi ke-1st). Elsevier. ISBN 978-0-444-50542-2. Di hlm. 35
^ Brian A. Davey and Hilary Ann Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753. Di hlm. 100
^ Yiannis N. Moschovakis (2006) Notes on set theory, Undergraduate Texts in Mathematics (Birkhäuser) ISBN 0-387-28723-X, p. 116
^ artinya, di luar beberapa indeks, seluruh anggota urutan selanjutnya adalah sama
^ Macpherson, H. Dugald (2011), "A survey of homogeneous structures", Discrete Mathematics, 311 (15): 1599–1634, doi:10.1016/j.disc.2011.01.024

Referensi

Garrett Birkhoff (1967). Lattice Theory. Colloquium Publications. 25. Providence: Am. Math. Soc.
Brian A. Davey; Hilary Ann Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753.
Fuchs, L (1963). Partially Ordered Algebraic Systems. Pergamon Press.
George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4
Rosenstein, Joseph G. (1982). Linear orderings. New York: Academic Press.
Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer-Verlag. ISBN 978-3-642-77970-1.

Pranala luar

Hazewinkel, Michiel, ed. (2001) [1994], "Totally ordered set", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4

[FOOTNOTEBirkhoff19672-1] Birkhoff 1967, hlm. 2.

[FOOTNOTESchmidtStröhlein199332-2] Schmidt & Ströhlein 1993, hlm. 32.

[FOOTNOTEFuchs19632-3] Fuchs 1963, hlm. 2.

[FOOTNOTEDaveyPriestley19903-4] Davey & Priestley 1990, hlm. 3.

[5] Strohmeier, Alfred; Genillard, Christian; Weber, Mats (1990-08-01). "Ordering of characters and strings". ACM SIGAda Ada Letters (dalam bahasa Inggris) (7): 84. doi:10.1145/101120.101136.

[6] Ganapathy, Jayanthi (1992). "Maximal Elements and Upper Bounds in Posets". Pi Mu Epsilon Journal. 9 (7): 462–464. ISSN 0031-952X. JSTOR 24340068.

[7] Definisi ini mirip dengan objek awal dari kategori, namun nilai tersebut lemah.

[8] Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. Here: Chapter 14

[9] Roland Fraïssé (Dec 2000). Theory of Relations. Studies in Logic and the Foundations of Mathematics. 145 (edisi ke-1st). Elsevier. ISBN 978-0-444-50542-2. Di hlm. 35

[10] Brian A. Davey and Hilary Ann Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753. Di hlm. 100

[11] Yiannis N. Moschovakis (2006) Notes on set theory, Undergraduate Texts in Mathematics (Birkhäuser) ISBN 0-387-28723-X, p. 116

[12] rtinya, di luar beberapa indeks, seluruh anggota urutan selanjutnya adalah sama

[13] Macpherson, H. Dugald (2011), "A survey of homogeneous structures", Discrete Mathematics, 311 (15): 1599–1634, doi:10.1016/j.disc.2011.01.024

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]